《数据结构》课程授课教案（讲义，共十章）

数据结构第0章复习提教材内容复习提示1.经典算法2. 绪论，3.线性表4.栈和队列5. 串6.树和二叉树7.图8.查找表。9.内部排序第 1章 绪论基础知识算法二、三、习题第2章线性表基础知识和算法1.线性表及其特点2.顺序表线性表的顺序存储结构.>3.单链表11一线性表的链式存储结构之..164.循环链表.5.双向循环链表.17176.顺序表与单链表的比较习题1819第3章栈和队列..19基础知识和算法191.栈..192.链栈.203.顺序栈4.队列....21225..链队列.....226.循环队列..257.栈和队列比较.8.简化的栈和队列结构25259.栈和队列的应用...27习题第4章串2727基础知识和算法，271.概念...272. 串的基本操作。283.串的存储结构..、习题....2829第6章树和二叉树.29基础知识和算法291.树及有关概念2.二叉树...29-I-

数据结构 - I - 第 0 章 复习提示 . 1 一、 教材内容. 1 二、 复习提示. 1 1. 经典算法 . 1 2. 绪论. 1 3. 线性表 . 2 4. 栈和队列 . 2 5. 串. 2 6. 树和二叉树. 2 7. 图 . 3 8. 查找表 . 3 9. 内部排序 . 3 第 1 章 绪论. 5 一、 基础知识. 5 二、 算法 . 5 三、 习题 . 6 第 2 章 线性表 . 8 一、 基础知识和算法 . 8 1. 线性表及其特点 . 8 2. 顺序表——线性表的顺序存储结构. 8 3. 单链表——线性表的链式存储结构之一 . 11 4. 循环链表 . 16 5. 双向循环链表. 17 6. 顺序表与单链表的比较. 17 二、 习题 . 18 第 3 章 栈和队列 . 19 一、 基础知识和算法 . 19 1. 栈. 19 2. 链栈. 19 3. 顺序栈 . 20 4. 队列. 21 5. 链队列 . 22 6. 循环队列 . 22 7. 栈和队列比较. 25 8. 简化的栈和队列结构. 25 9. 栈和队列的应用 . 25 二、 习题 . 27 第 4 章 串. 27 一、 基础知识和算法 . 27 1. 概念. 27 2. 串的基本操作. 27 3. 串的存储结构. 28 二、 习题 . 28 第 6 章 树和二叉树. 29 一、 基础知识和算法 . 29 1. 树及有关概念. 29 2. 二叉树 . 29

293.二叉树的性质...304.二叉树的存储结构..305.二叉树的五种基本形态...316.遍历二叉树，357.遍历二叉树的应用。.368.线索二叉树..379.树和森林，3910.赫夫曼树及其应用40习题，.41第7章图....41基础知识和算法...411.图的有关概念...412.图的存储结构.3．图的遍历....444.最小生成树...475.拓扑排序..48..486.关键路径...507.最短路径51习题55第9章查找..55基础知识和算法..551.有关概念2.．顺序查找....55....563.．折半查找....584.索引顺序表，.585二叉排序树....616.平衡二叉树...7.B-树和B+树..63638.键树....9. 哈希表.63二、习题...6567第10章内部排序..67基础知识和算法.4671.排序的有关概念..72.直接插入排序.3.折半插入排序...684.希尔排序（缩小增量排序）...69.705.起泡排序6.快速排序707.简单选择排序.72738.堆排序759.归并排序710.基数排序7811.各种排序方法比较- II -

- II - 3. 二叉树的性质. 29 4. 二叉树的存储结构 . 30 5. 二叉树的五种基本形态. 30 6. 遍历二叉树. 31 7. 遍历二叉树的应用 . 35 8. 线索二叉树. 36 9. 树和森林 . 37 10. 赫夫曼树及其应用 . 39 二、 习题 . 40 第 7 章 图. 41 一、 基础知识和算法 . 41 1. 图的有关概念. 41 2. 图的存储结构. 41 3. 图的遍历 . 44 4. 最小生成树. 47 5. 拓扑排序 . 48 6. 关键路径 . 48 7. 最短路径 . 50 二、 习题 . 51 第 9 章 查找. 55 一、 基础知识和算法 . 55 1. 有关概念 . 55 2. 顺序查找 . 55 3. 折半查找 . 56 4. 索引顺序表. 58 5. 二叉排序树. 58 6. 平衡二叉树. 61 7. B-树和 B +树. 63 8. 键树. 63 9. 哈希表 . 63 二、 习题 . 65 第 10 章 内部排序 . 67 一、 基础知识和算法 . 67 1. 排序的有关概念 . 67 2. 直接插入排序. 67 3. 折半插入排序. 68 4. 希尔排序（缩小增量排序）. 69 5. 起泡排序 . 70 6. 快速排序 . 70 7. 简单选择排序. 72 8. 堆排序 . 73 9. 归并排序 . 75 10. 基数排序 . 77 11. 各种排序方法比较 . 78

第0章 复习提示一、教材内容。使用教材《数据结构》C语言版严蔚敏，清华大学出版社。.章节去掉第5、8、11、12章去掉**部分去掉1.3，2.4，4.4二、复习提示1.经典算法单链表：遍历、插入、删除循环队列：队列空、队列满的条件二叉树：递归遍历及应用有序表的二分法查找快速排序简单选择排序2.绪论掌握几个重要概念数据结构、抽象数据类型、算法时间复杂度的简单计算（C'）掌握几种说法数据元素是..，数据项是数据结构中关系的四种基本结构数据结构的形式定义算法的五个特征「记号C，表示要求掌握计算方法，会计算。本节下同。-1-

- 1 - 第0章 复习提示 一、教材内容  使用教材《数据结构》C 语言版 严蔚敏，清华大学出版社。  章节 去掉 第 5、8、11、12 章 去掉 **部分 去掉 1.3，2.4，4.4 二、复习提示 1. 经典算法 单链表：遍历、插入、删除 循环队列：队列空、队列满的条件 二叉树：递归遍历及应用 有序表的二分法查找 快速排序 简单选择排序 2. 绪论 掌握几个重要概念 数据结构、抽象数据类型、算法 时间复杂度的简单计算（C 1） 掌握几种说法 数据元素是.，数据项是. 数据结构中关系的四种基本结构 数据结构的形式定义 算法的五个特征 1 记号 C，表示要求掌握计算方法，会计算。本节下同

3.线性表线性表的概念和四个特征顺序表和单链表的类型定义在顺序表中查找、插入、删除，灵活运用在单链表中查找、插入、删除，灵活运用循环链表及双向链表的定义、插入、删除算法：单链表的算法，灵活运用、会编程（P）4.栈和队列栈和队列的概念、特点入栈、出栈操作，灵活掌握了解栈的实现：链栈和顺序栈（A"算法，P）了解队列的实现，链队列和循环队列，注意链队列中的出队列操作算法：注意循环队列空和满的条件（A，P）会运用栈和队列5. 串掌握相关概念会运用串的基本操作（C)，特别是Concat()，Substring()，Index()和ReplaceO知道串的三种存储结构及其特点6. 树和二又树树和二叉树的有关概念二叉树的性质熟练掌握遍历二叉树的递归算法，并灵活运用知道线索二叉树，会对二叉树进行线索化树、森林和二叉树的转化，会遍历树和森林赫夫曼树及其应用算法：递归遍历二叉树及其应用（P）构造赫夫曼树和赫夫曼编码（A）树和二叉树的转换（A）森林和二叉树的转换（A）遍历树和森林（A）2记号P，要求达到编写算法和程序的能力。本节下同。3记号A，要求掌握算法思想，会演算。本节下同。-2-

- 2 - 3. 线性表 线性表的概念和四个特征 顺序表和单链表的类型定义 在顺序表中查找、插入、删除，灵活运用 在单链表中查找、插入、删除，灵活运用 循环链表及双向链表的定义、插入、删除 算法： 单链表的算法，灵活运用、会编程（P 2） 4. 栈和队列 栈和队列的概念、特点 入栈、出栈操作，灵活掌握 了解栈的实现：链栈和顺序栈（A 3算法，P） 了解队列的实现，链队列和循环队列，注意链队列中的出队列操作 算法： 注意循环队列空和满的条件（A，P） 会运用栈和队列 5. 串 掌握相关概念 会运用串的基本操作（C），特别是 Concat()，Substring()，Index()和 Replace() 知道串的三种存储结构及其特点 6. 树和二叉树 树和二叉树的有关概念 二叉树的性质 熟练掌握遍历二叉树的递归算法，并灵活运用 知道线索二叉树，会对二叉树进行线索化 树、森林和二叉树的转化，会遍历树和森林 赫夫曼树及其应用 算法： 递归遍历二叉树及其应用（P） 构造赫夫曼树和赫夫曼编码（A） 树和二叉树的转换（A） 森林和二叉树的转换（A） 遍历树和森林（A） 2 记号 P，要求达到编写算法和程序的能力。本节下同。 3 记号 A，要求掌握算法思想，会演算。本节下同

7. 图图的有关概念熟练掌握图的各种存储结构图的遍历：深度优先、广度优先（A）最小生成树算法（两个）及其特点（A）拓扑排序（A）关键路径算法（A）最短路径算法（两个）（A，O：时间复杂度）8.查找表查找的有关概念，ASL等顺序查找（A，P）熟练掌握有序表的折半查找算法（A，P，C）了解索引顺序表熟练掌握二叉排序树的概念，建立（A)，查找（A，P)，删除（A)，计算ASL（C）平衡二叉排序树的概念，建立（A），判断失去平衡的类型，平衡化（A），计算ASL(C)了解B树，B+树的概念和特点知道键树（数字查找树）哈希表的概念、特点、构造哈希表（A)，计算ASL和装填因子α（C)了解各种查找表的性能（O）9.内部排序直接插入排序（A）折半插入排序（A，P)希尔排序（A）起泡排序（A）快速排序（A，P，O)简单选择排序（P，A，O）堆的概念，调整成堆（A），堆排序（A，O）归并排序（A，O)链式基数排序（A，O)各种排序算法的对比结论（O）4记号O，要求掌握算法的时间复杂度。本节下同。-3 -

- 3 - 7. 图 图的有关概念 熟练掌握图的各种存储结构 图的遍历：深度优先、广度优先（A） 最小生成树算法（两个）及其特点（A） 拓扑排序（A） 关键路径算法（A） 最短路径算法（两个）（A，O 4：时间复杂度） 8. 查找表 查找的有关概念，ASL 等 顺序查找（A，P） 熟练掌握有序表的折半查找算法（A，P，C） 了解索引顺序表 熟练掌握二叉排序树的概念，建立（A），查找（A，P），删除（A），计算 ASL（C） 平衡二叉排序树的概念，建立（A），判断失去平衡的类型，平衡化（A），计算 ASL （C） 了解 B_树，B+树的概念和特点 知道键树（数字查找树） 哈希表的概念、特点、构造哈希表（A），计算 ASL 和装填因子α （C） 了解各种查找表的性能（O） 9. 内部排序 直接插入排序（A） 折半插入排序（A，P） 希尔排序（A） 起泡排序（A） 快速排序（A，P，O） 简单选择排序（P，A，O） 堆的概念，调整成堆（A），堆排序（A，O） 归并排序（A，O） 链式基数排序（A，O） 各种排序算法的对比结论（O） 4 记号 O，要求掌握算法的时间复杂度。本节下同

第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:ia[i+1])a[ia[i+1];1或void BubbleSort(DataType al, int n)for(i=l; a[i+1])a[ia[i+1];1或voidBubbleSort(DataTypeall,intn)for(i=0; Kn-1; i++) (change =fasle,for(j=0; ja[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; ia[j+1] ) a[j]a[j+1]; } 或 void BubbleSort ( DataType a[], int n ) { for ( i=1; ia[j+1] ) a[j]a[j+1]; } 或 void BubbleSort ( DataType a[], int n ) { for ( i=0; ia[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