第1章绪论、基础知识概念和术语(黑体字部分)。另外，注意：1、数据元素是数据的基本单位。P42、数据项是数据不可分割的最小单位。P53、数据结构及其形式定义。P5四种基本结构：①集合②线性结构③树形结构④图（网）状结构4、数据结构的逻辑结构（抽象的，与实现无关）物理结构（存储结构）顺序映像（顺序存储结构）位置“相邻”非顺序映像（链式存储结构）指针表示关系P65、数据类型P7抽象数据类型（ADT）P7ADT=（数据对象，数据关系，基本操作）ADT细分为原子类型，固定聚合，可变聚合类型。P86、算法的概念P137、算法的五个特征①有穷性②确定性③可行性④输入（0个或多个）③输出（1个或多个）8、算法设计的要求：①正确性②可读性③健壮性④效率与低存储量其中正确性的四个层次（通常要求达到C层）。9、算法的时间复杂度P15常见有：O(1)，O(n)，O(n)，O(log2n),O(nlog2n)，O(2")语句频度，用归纳法计算。10、算法的空间复杂度P17二、算法起泡排序。P165分析算法的时间复杂度时，logzn常简单记作log n。-5-
- 5 - 第1章 绪论 一、基础知识 概念和术语(黑体字部分)。 另外，注意： 1、数据元素是数据的基本单位。P4 2、数据项是数据不可分割的最小单位。P5 3、数据结构及其形式定义。P5 四种基本结构：①集合②线性结构③树形结构④图（网）状结构 4、数据结构的 逻辑结构（抽象的，与实现无关） 物理结构（存储结构） 顺序映像（顺序存储结构）位置“相邻” 非顺序映像（链式存储结构）指针表示关系 P6 5、数据类型 P7 抽象数据类型（ADT）P7 ADT=（数据对象，数据关系，基本操作） ADT 细分为原子类型，固定聚合，可变聚合类型。P8 6、算法的概念 P13 7、算法的五个特征 ①有穷性 ②确定性 ③可行性 ④输入（0 个或多个） ⑤输出（1 个或多个） 8、算法设计的要求：①正确性②可读性③健壮性④效率与低存储量 其中正确性的四个层次（通常要求达到 C 层）。 9、算法的时间复杂度 P15 常见有： O(1)，O(n)，O(n2 )，O(log2n)5，O(n log2n)，O(2n ) 语句频度，用归纳法计算。 10、算法的空间复杂度 P17 二、算法 起泡排序。P16 5 分析算法的时间复杂度时，log2n 常简单记作 log n
另一种形式void BubbleSort (DataType a[l, int n)for(i=0:i<n-l:i++)for(j=0; j<n-i-1; j++)if(a[i]>a[i+1])a[i<_>a[i+1];1或void BubbleSort(DataType al, int n)for(i=l; <n;, i++)for (j-0; j<n-i, j++ )if(a[i]>a[i+1])a[i<->a[i+1];1或voidBubbleSort(DataTypeall,intn)for(i=0; Kn-1; i++) (change =fasle,for(j=0; j<n-i-1; j++)if(a[]>a[i+1])a[i]<->a[i+1];change = true,3if(!change)break1说明：a）考试中要求写算法时，可用类C，也可用C程序。b）尽量书写算法说明，言简意。c）技巧：用“边界值验证法”检查下标越界错误。如上第一个：第二个循环条件若写作<n-i，则当i=0时ai+1l会越界。d)时间复杂度为O(n)，第3个在最好情况下（待排记录有序），时间复杂度为O(n)。三、习题1.1编写冒泡排序算法，使结果从大到小排列。1.2计算下面语句段中指定语句的频度：1) for(i=1; i<=n; i++)for (j=i: j<=n; j++ )@X++:2) i= 1;-6 -
- 6 - 另一种形式 void BubbleSort ( DataType a[], int n ) { for ( i=0; i<n-1; i++ ) for ( j=0; j<n-i-1; j++ ) 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; } } 说明： a) 考试中要求写算法时，可用类 C，也可用 C 程序。 b) 尽量书写算法说明，言简意赅。 c) 技巧：用“边界值验证法”检查下标越界错误。 如上第一个： 第二个循环条件若写作 j<n-i，则当 i=0 时 a[j+1]会越界。 d) 时间复杂度为 O(n2 )，第 3 个在最好情况下（待排记录有序），时间复杂度为 O(n)。 三、习题 1.1 编写冒泡排序算法，使结果从大到小排列。 1.2 计算下面语句段中指定语句的频度： 1) for ( i=1; i<=n; i++ ) for ( j=i; j<=n; j++ ) x++;- // @ 2) i = 1;
while (i<=n)i=i*2;---|@--7 -
- 7 - while ( i<=n ) i = i*2; - // @
第2章 线性表一、基础知识和算法1.线性表及其特点线性表是Ⅱ个数据元素的有限序列。线性结构的特点：①“第一个”②“最后一个”③前驱后继。62.顺序表一一线性表的顺序存储结构(1)特点a)逻辑上相邻的元素在物理位置上相邻。b）随机访问。(2)类型定义简而言之，“数组+长度”7。constintMAXSIZE=线性表最大长度；typedef struct!DataType elem[MAXSIZE];int length;SqList:注：a)SqList为类型名，可换用其他写法。b)DataType是数据元素的类型，根据需要确定。c)MAXSIZE根据需要确定。如constintMAXSIZE-64,d）课本上的SqList类型可在需要时增加存储空间，在上面这种定义下不可以。（这样做避免了动态内存分配，明显减少了算法的复杂程度，容易理解。而且，原来Pasca版本的《数据结构》（严蔚敏）就是这样做的。）6这里太简炼了，只是为了便于记忆。7不准确的说法，只为便于理解和记忆，不要在正式场合引用。凡此情形，都加引号以示提醒。-8-
- 8 - 第2章 线性表 一、基础知识和算法 1. 线性表及其特点 线性表是 n 个数据元素的有限序列。 线性结构的特点： ①“第一个” ②“最后一个” ③前驱 ④后继。6 2. 顺序表——线性表的顺序存储结构 (1) 特点 a) 逻辑上相邻的元素在物理位置上相邻。 b) 随机访问。 (2) 类型定义 简而言之，“数组+长度”7。 const int MAXSIZE = 线性表最大长度; typedef struct{ DataType elem[MAXSIZE]; int length; } SqList; 注：a) SqList 为类型名，可换用其他写法。 b) DataType 是数据元素的类型，根据需要确定。 c) MAXSIZE 根据需要确定。如 const int MAXSIZE=64; d) 课本上的 SqList 类型可在需要时增加存储空间，在上面这种定义下不可以。(这 样做避免了动态内存分配，明显减少了算法的复杂程度，容易理解。而且，原来 Pascal 版本的《数据结构》（严蔚敏）就是这样做的。) 6 这里太简炼了，只是为了便于记忆。 7 不准确的说法，只为便于理解和记忆，不要在正式场合引用。凡此情形，都加引号以示提醒
e）课本上的SqList类型定义中listsize表示已经分配的空间大小（容纳数据元素的个数）。当插入元素而遇到L.lengthL.listsize时，用realloc（L.elem，L.listsize+增量）重新分配内存，而reallocO函数在必要的时候自动复制原来的元素到新分配的空间中。(3）基本形态1°顺序表空条件L.length-00MAXSIZE-1不允许删除操作L.elem[L.length==02°顺序表满L.elem[L.length=-MAXSIZ条件L.length-MAXSIZEL.elem[0<L.length<MAXSI不允许插入操作3°不空也不满可以插入，删除(4)基本算法—遍历1°顺序访问所有元素for (i=0, i<L.length; i++)visit(L.elem[]),2°查找元素×for (i=0, i<L.length; i++)if(L.elem[i]-=x) break;if(i<L.length)找到;else未找到；(5)插入算法ListInsert(&L,i,x)1°前提：表不满2°合理的插入范围：1≤i≤L.length+1注：位序i在C/C++中对应于下标i-1。-9-
- 9 - e) 课本上的 SqList 类型定义中 listsize 表示已经分配的空间大小（容纳数据元素 的个数）。当插入元素而遇到 L.length==L.listsize 时，用 realloc (L.elem, L.listsize+增量) 重新分配内存，而 realloc()函数在必要的时候自动复制原来的元素到新分配的空间中。 (3) 基本形态 1°. 顺序表空 条件 L.length==0 不允许删除操作 2°. 顺序表满 条件 L.length==MAXSIZE 不允许插入操作 3°. 不空也不满 可以插入，删除 (4) 基本算法——遍历 1°. 顺序访问所有元素 for ( i=0; i<L.length; i++ ) visit ( L.elem[i] ); 2°. 查找元素 x for ( i=0; i<L.length; i++ ) if ( L.elem[i]==x ) break; if ( i<L.length ) 找到; else 未找到; (5) 插入算法 ListInsert(&L,i,x) 1°. 前提：表不满 2°. 合理的插入范围：1≤i≤L.length+1 注：位序 i 在 C/C++中对应于下标 i-1。 0 1 . MAXSIZE-1 L.elem[ ] L.elem[ ] L.elem[ ] L.length==0 L.length==MAXSIZ E 0<L.length<MAXSI ZE