if ( a[j]>a[j+1] ) {
a[j]<—>a[j+1];
change = true;
}
if ( !change ) break;
}
}
说明：
a) 考试中要求写算法时，可用类 C，也可用 C 程序。
b) 尽量书写算法说明，言简意赅。
c)
“
”
技巧：用 边界值验证法 检查下标越界错误。
如上第一个： 第二个循环条件若写作 j<n-i，则当 i=0
时 a[j+1]会越界。
d) 时间复杂度为 O(n
2
)，第 3 个在最好情况下（待排记录有序），时间复杂度为 O(n)。
第二章、线性表
一、基础知识和算法
1、线性表及其特点
线性表是 n 个数据元素的有限序列。
“
” “
”
线性结构的特点： ① 第一个 ② 最后一个 ③前驱 ④后继。
2
—
、顺序表 线性表的顺序存储结构
（1）特点：a) 逻辑上相邻的元素在物理位置上相邻。b) 随机访问。
（2）类型定义
“
简而言之， 数组+
长度
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）基本形态
顺序表空
条件 L.length==0
不允许删除操作
顺序表满
条件 L.length==MAXSIZE
不允许插入操作
2
这里太简炼了，只是为了便于记忆。
3
不准确的说法，只为便于理解和记忆，不要在正式场合引用。凡此情形，都加引号以示提醒。
0
1
MAXSIZE-1
...
L.elem[
]
L.elem[
]
L.elem[
]
L.length==0
L.length==MAXSIZ
E
0<L.length<MAXSI
ZE