二叉排序树的建立_怎么建立二叉排序树_二叉排序树的创建(5)

if ( a[j]>a[j+1] )

a[j]<—>a[j+1];

}

或

void BubbleSort ( DataType a[], int n )

{

for ( i=1; i<n; i++ )

for ( j=0; j<n-i; j++ )

if( a[j]>a[j+1] )

a[j]<—>a[j+1];

}

或

void BubbleSort ( DataType a[], int n )

{

for ( i=0; i<n-1; i++ ) {

change = fasle;

for ( j=0; j<n-i-1; j++ )

if ( a[j]>a[j+1] ) {

a[j]<—>a[j+1];

change = true;

}

if ( !change ) break;

}

} 1 分析算法的时间复杂度时，log2n常简单记作log n。

说明：

a) 考试中要求写算法时，可用类C，也可用C程序。 b) 尽量书写算法说明，言简意赅。

c) 技巧：用“边界值验证法”检查下标越界错误。

如上第一个： 第二个循环条件若写作j<n-i，则当i=0时 a[j+1]会越界。

2

d) 时间复杂度为O(n)，第3个在最好情况下（待排记录有序），时间复杂度为O(n)。 第二章、线性表 一、基础知识和算法 1、线性表及其特点

线性表是n个数据元素的有限序列。

2

线性结构的特点： ①“第一个” ②“最后一个” ③前驱 ④后继。 2、顺序表—线性表的顺序存储结构

（1）特点：a) 逻辑上相邻的元素在物理位置上相邻。b) 随机访问。 （2）类型定义

3

简而言之，“数组+长度”。

const int MAXSIZE = 线性表最大长度; typedef struct{

DataType elem[MAXSIZE]; int length; } SqList;

注：a) SqList为类型名，可换用其他写法。

b) DataType是数据元素的类型，根据需要确定。c) MAXSIZE根据需要确定。如 const int MAXSIZE=64;

d) 课本上的SqList类型可在需要时增加存储空间，在上面这种定义下不可以

e) 课本上的SqList类型定义中listsize表示已经分配的空间大小（容纳数据元素的个数）。当插入元素而遇到L.length==L.listsize时，用realloc (L.elem, L.listsize+增量) 重新分配内存，而realloc()函数在必要的时候自动复制原来的元素到新分配的空间中。

（3）基本形态 a) 顺序表空

条件 L.length==0 不允许删除操作

b) 顺序表满

条件 L.length==MAXSIZE 不允许插入操作

0 1 ... MAXSIZE-1

L.length==0

L.length==MAXSIZ0<L.length<MAXSI

23

这里太简炼了，只是为了便于记忆。

不准确的说法，只为便于理解和记忆，不要在正式场合引用。凡此情形，都加引号以示提醒。

c) 不空也不满

可以插入，删除

（4）基本算法——遍历

d) 顺序访问所有元素for ( i=0; i<L.length; i++ ) visit ( L.elem[i] );5 查找元素x

for ( i=0; i<L.length; i++ )

if ( L.elem[i]==x ) break;

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-25557-5.html