数据结构分析与管理讲义.docx

《数据结构分析与管理讲义.docx》由会员分享，可在线阅读，更多相关《数据结构分析与管理讲义.docx（101页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、前言缘起数据结构是一门计算机专业基础课，各类计算机考试都禁不住要考它，专升本考试自然也不例外。我给学生辅导这门课程已经有几个年头了，讲稿换了几次，逐渐丰富起来。加之看到学生们埋头记笔记时辛苦的样子，就产生了写一本小册子的想法。另外，还有一层意思就是对数次辅导进行总结，以便交流之用。说明首先，需要说明的是这本书在语言风格上不太讲究，常有些不严谨的表达，或调侃，或土得掉渣，难登大雅之堂，请勿在正规场合引用这些说法。这样做的目的，仅仅是为了更简练、更直接地描述思想，方便理解、记忆和使用。凡是这种情况，往往都用引号括起来，并加以脚注说明。还有，本书需配合数据结构(严蔚敏)教材使用。由于篇幅有限，多数概

2、念、术语没有详释。 另外，每章之后都配有习题，或多或少，难度不一，并没有局限于专升本的要求。对所有习题都提供了参考答案。致谢我要感谢所有给予我帮助的人。张志老师的大力支持和帮助使得本书得以面世，他还提供了近年专升本试题。李永干老师的帮助使得本书顺利印刷。谭业武老师给了我很大支持，还提出了很多建议。最后，我要感谢隆坤，她总是给我最大的支持，使那些本来只在我想象中的事情变成现实。庄波于滨州学院第0章 复习提示1一、 教材内容1二、 复习提示11. 经典算法12. 绪论13. 线性表14. 栈和队列25. 串26. 树和二叉树27. 图28. 查找表39. 内部排序3第1章 绪论5一、 基础知识5二

3、、 算法5三、 习题6第2章 线性表7一、 基础知识和算法71. 线性表及其特点72. 顺序表线性表的顺序存储结构73. 单链表线性表的链式存储结构之一104. 循环链表155. 双向循环链表156. 顺序表与单链表的比较16二、 习题16第3章 栈和队列17一、 基础知识和算法171. 栈172. 链栈173. 顺序栈184. 队列195. 链队列206. 循环队列207. 栈和队列比较228. 简化的栈和队列结构239. 栈和队列的应用23二、 习题24第4章 串25一、 基础知识和算法251. 概念252. 串的基本操作253. 串的存储结构25二、 习题25第6章 树和二叉树27一、

4、基础知识和算法271. 树及有关概念272. 二叉树273. 二叉树的性质274. 二叉树的存储结构285. 二叉树的五种基本形态286. 遍历二叉树297. 遍历二叉树的应用338. 线索二叉树349. 树和森林3510. 赫夫曼树及其应用36二、 习题37第7章 图39一、 基础知识和算法391. 图的有关概念392. 图的存储结构393. 图的遍历424. 最小生成树445. 拓扑排序466. 关键路径467. 最短路径47二、 习题49第9章 查找51一、 基础知识和算法511. 有关概念512. 顺序查找513. 折半查找524. 索引顺序表545. 二叉排序树546. 平衡二叉树5

5、77. B-树和B+树588. 键树599. 哈希表59二、 习题61第10章 内部排序63一、 基础知识和算法631. 排序的有关概念632. 直接插入排序633. 折半插入排序644. 希尔排序（缩小增量排序）645. 起泡排序656. 快速排序667. 简单选择排序678. 堆排序689. 归并排序7110. 基数排序7211. 各种排序方法比较73第0章 复习提示一、 教材内容l 使用教材数据结构C语言版 严蔚敏，清华大学出版社。l 章节 去掉 第5、8、11、12章 去掉 *部分 去掉1.3，2.4，4.4二、 复习提示1. 经典算法单链表：遍历、插入、删除循环队列：队列空、队列满的

6、条件二叉树：递归遍历及应用有序表的二分法查找快速排序简单选择排序2. 绪论掌握几个重要概念数据结构、抽象数据类型、算法时间复杂度的简单计算（C 记号C，表示要求掌握计算方法，会计算。本节下同。）掌握几种说法数据元素是，数据项是数据结构中关系的四种基本结构数据结构的形式定义算法的五个特征3. 线性表线性表的概念和四个特征顺序表和单链表的类型定义在顺序表中查找、插入、删除，灵活运用在单链表中查找、插入、删除，灵活运用循环链表及双向链表的定义、插入、删除算法：单链表的算法，灵活运用、会编程（P 记号P，要求达到编写算法和程序的能力。本节下同。）4. 栈和队列栈和队列的概念、特点入栈、出栈操作，灵活掌

7、握了解栈的实现：链栈和顺序栈（A 记号A，要求掌握算法思想，会演算。本节下同。算法，P）了解队列的实现，链队列和循环队列，注意链队列中的出队列操作算法：注意循环队列空和满的条件（A，P）会运用栈和队列5. 串掌握相关概念会运用串的基本操作（C），特别是Concat()，Substring()，Index()和Replace()知道串的三种存储结构及其特点6. 树和二叉树树和二叉树的有关概念二叉树的性质熟练掌握遍历二叉树的递归算法，并灵活运用知道线索二叉树，会对二叉树进行线索化树、森林和二叉树的转化，会遍历树和森林赫夫曼树及其应用算法： 递归遍历二叉树及其应用（P） 构造赫夫曼树和赫夫曼编码（A

8、） 树和二叉树的转换（A） 森林和二叉树的转换（A） 遍历树和森林（A）7. 图图的有关概念熟练掌握图的各种存储结构图的遍历：深度优先、广度优先（A）最小生成树算法（两个）及其特点（A）拓扑排序（A）关键路径算法（A）最短路径算法（两个）（A，O 记号O，要求掌握算法的时间复杂度。本节下同。：时间复杂度）8. 查找表查找的有关概念，ASL等顺序查找（A，P）熟练掌握有序表的折半查找算法（A，P，C）了解索引顺序表熟练掌握二叉排序树的概念，建立（A），查找（A，P），删除（A），计算ASL（C）平衡二叉排序树的概念，建立（A），判断失去平衡的类型，平衡化（A），计算ASL（C）了解B_树，B+树

9、的概念和特点知道键树（数字查找树）哈希表的概念、特点、构造哈希表（A），计算ASL和装填因子（C）了解各种查找表的性能（O）9. 内部排序直接插入排序（A）折半插入排序（A，P）希尔排序（A）起泡排序（A）快速排序（A，P，O）简单选择排序（P，A，O）堆的概念，调整成堆（A），堆排序（A，O）归并排序（A，O）链式基数排序（A，O）各种排序算法的对比结论（O）第1章 绪论一、 基础知识概念和术语(黑体字部分)。另外，注意：1、数据元素是数据的基本单位。P42、数据项是数据不可分割的最小单位。P53、数据结构及其形式定义。P5四种基本结构：集合线性结构树形结构图（网）状结构4、数据结构的逻辑结

10、构（抽象的，与实现无关）物理结构（存储结构） 顺序映像（顺序存储结构）位置“相邻” 非顺序映像（链式存储结构）指针表示关系P65、数据类型 P7 抽象数据类型（ADT）P7 ADT=（数据对象，数据关系，基本操作） ADT细分为原子类型，固定聚合，可变聚合类型。P86、算法的概念 P137、算法的五个特征 有穷性 确定性 可行性 输入（0个或多个） 输出（1个或多个）8、算法设计的要求：正确性可读性健壮性效率与低存储量其中正确性的四个层次（通常要求达到C层）。9、算法的时间复杂度 P15 常见有： O(1)，O(n)，O(n2)，O(log2n) 分析算法的时间复杂度时，log2n常简单记作l

11、og n。，O(n log2n)，O(2n) 语句频度，用归纳法计算。10、算法的空间复杂度 P17二、 算法起泡排序。P16另一种形式void BubbleSort ( DataType a, int n ) for ( i=0; in-1; i+ ) for ( j=0; jaj+1 ) ajaj+1;或void BubbleSort ( DataType a, int n ) for ( i=1; in; i+ ) for ( j=0; jaj+1 ) ajaj+1;或void BubbleSort ( DataType a, int n ) for ( i=0; in-1; i+ )

12、change = fasle; for ( j=0; jaj+1 ) ajaj+1; change = true; if ( !change ) break; 说明：a) 考试中要求写算法时，可用类C，也可用C程序。b) 尽量书写算法说明，言简意赅。c) 技巧：用“边界值验证法”检查下标越界错误。 如上第一个： 第二个循环条件若写作jn-i，则当i=0时 aj+1会越界。d) 时间复杂度为O(n2)，第3个在最好情况下（待排记录有序），时间复杂度为O(n)。三、 习题1.1 编写冒泡排序算法，使结果从大到小排列。1.2 计算下面语句段中指定语句的频度： 1) for ( i=1; i=n; i

13、+ ) for ( j=i; j=n; j+ ) x+;/ 2) i = 1; while ( i=n ) i = i*2;/ 第2章 线性表一、 基础知识和算法1. 线性表及其特点线性表是n个数据元素的有限序列。线性结构的特点： “第一个” “最后一个” 前驱 后继。 这里太简炼了，只是为了便于记忆。2. 顺序表线性表的顺序存储结构(1) 特点a) 逻辑上相邻的元素在物理位置上相邻。b) 随机访问。(2) 类型定义简而言之，“数组+长度” 不准确的说法，只为便于理解和记忆，不要在正式场合引用。凡此情形，都加引号以示提醒。const int MAXSIZE = 线性表最大长度;typedef

14、structDataType elemMAXSIZE;int length; SqList;注：a) SqList为类型名，可换用其他写法。 b) DataType是数据元素的类型，根据需要确定。 c) MAXSIZE根据需要确定。如const int MAXSIZE=64; d) 课本上的SqList类型可在需要时增加存储空间，在上面这种定义下不可以。(这样做避免了动态内存分配，明显减少了算法的复杂程度，容易理解。而且，原来Pascal版本的数据结构（严蔚敏）就是这样做的。) e) 课本上的SqList类型定义中listsize表示已经分配的空间大小（容纳数据元素的个数）。当插入元素而遇到L

15、.length=L.listsize时，用realloc (L.elem, L.listsize+增量) 重新分配内存，而realloc()函数在必要的时候自动复制原来的元素到新分配的空间中。(3) 基本形态1. 顺序表空01MAXSIZE-1.L.elemL.elemL.elemL.length=0L.length=MAXSIZE0L.lengthMAXSIZE条件 L.length=0不允许删除操作2. 顺序表满条件 L.length=MAXSIZE不允许插入操作3. 不空也不满可以插入，删除(4) 基本算法遍历1. 顺序访问所有元素for ( i=0; iL.length; i+ ) v

16、isit ( L.elemi );2. 查找元素xfor ( i=0; iL.length; i+ ) if ( L.elemi=x ) break;if ( iL.length ) 找到;else 未找到;(5) 插入算法 ListInsert(&L,i,x)1. 前提：表不满2. 合理的插入范围：1iL.length+1注：位序i在C/C+中对应于下标i-1。3. 步骤 第i至最后所有元素后移一个元素 在第i个位置插入元素x 表长增14. 算法bool 这里返回true表示正确插入，返回false表示插入失败。以下常用来区分操作是否正确执行。 ListInsert ( SqList& L,

17、 int i, DataType x ) if ( L.length=MAXSIZE | iL.length+1 ) return false; / 失败 / 元素后移 for ( j=L.length-1; j=i-1; j- ) / 这里j为下标，从L.length-1到i-1 L.elemj+1 = L.elemj; / 若作为位序，有如何修改？ / 插入x L.elemi-1 = x; / 表长增1 L.length+; return true; / 插入成功(6) 删除算法 ListDelete(&L,i,&x)1. 前提：表非空2. 合理的删除范围：1iL.length3. 步骤取

18、出第i个元素第i个元素之后的元素向前移动一个位置表长减14. 算法bool ListDelete ( SqList& L, int i, DataType& x ) if ( L.length=0 | iL.length ) return false; / 失败 x = L.elemi-1; for ( j=i; jnext = 02. 单链表不空条件：L-next != 0(5) 基本算法 （遍历）1. 顺序访问所有元素借助指针，“顺藤摸瓜”(沿着链表访问结点)。p = L-next; / 注意起始位置的考虑while ( p!=NULL ) / 判表尾，另外 (p!=0)或(p)均可 vi

19、sit( p-data ); / 访问:可以换成各种操作 p = p-next; / 指针沿着链表向后移动例：打印单链表中的数据。void PrintLinkList ( LinkList L ) p = L-next; while ( p!=NULL ) print ( p-data ); / 访问：打印数据域 p = p-next; 2. 查找元素x/ 在单链表L中查找元素x/ 若找到，返回指向该结点的指针；否则返回空指针LinkList Find ( LinkList L, DataType x ) p = L-next; while ( p!=NULL ) if ( p-data =

20、x ) return p; / 找到x p = p-next; return NULL; / 未找到/ 在单链表L中查找元素x/ 若找到，返回该元素的位序；否则返回0int Find ( LinkList L, DataType x ) p = L-next; j = 1; while ( p!=NULL ) if ( p-data = x ) return j; / 找到x p = p-next; j+; / 计数器随指针改变 return 0; / 未找到前一个算法的另一种写法：p = L-next;while ( p & p-data!=x ) p = p-next;if ( p & p

21、-data=x ) return p;else return 0;或者p = L-next;while ( p & p-data!=x ) p = p-next;return p; / 为什么3. 查找第i个元素LinkList Get ( LinkList L, int i ) p = L-next; j = 1; while ( p & jnext; j+; if ( p & j=i ) return p; else return 0;4. 查找第i-1个元素p = L; j = 0;while ( p & jnext; j+;if ( p & j=i-1 ) return p;else

22、return 0;(6) 插入算法 ListInsert(&L,i,x)技巧：画图辅助分析。思路： 先查找第i-1个元素 若找到，在其后插入新结点bool 这里返回true表示正确插入，返回false表示插入失败。 ListInsert ( LinkList &L, int i, DataType x ) / 查找第i-1个元素p p = L; j = 0; while ( p & jnext; j+; / 若找到，在p后插入xai-1-插入前执行之后执行之后-pxsai-1-px-sai-1-px-s if ( p & j=i-1 ) s = (LinkList) malloc(sizeof

23、(LNode); s-data = x; s-next = p-next; / p-next = s; / return true; / 插入成功 else return false; / 插入失败注意： a) 要让p指向第i-1个而不是第i个元素（否则，不容易找到前驱以便插入）。 b) 能够插入的条件： p & j=i-1 。即使第i个元素不存在，只要存在第i-1个元素，仍然可以插入第i个元素。 c) 新建结点时需要动态分配内存。 s = (LinkList) malloc(sizeof(LNode); 若检查是否分配成功，可用 if ( s=NULL ) exit(1); / 分配失败则终

24、止程序 d) 完成插入的步骤：。技巧：先修改新结点的指针域。(7) 删除算法 ListDelete(&L,i,&x)思路： 先查找第i-1个元素 若找到且其后存在第i个元素，则用x返回数据，并删除之ai-1-删除前ai-p-sai-1-执行之后ai-p-sai-1-执行之后ai-p-bool ListDelete ( LinkList &L, int i, int &x ) / 查找第i-1个元素p p = L; j = 0; while ( p & jnext; j+; /若存在第i个元素，则用x返回数据，并删除之 if ( p & j=i-1 & p-next ) / 可以删除 s = p

25、-next; / p-next = s-next; / x = s-data; free (s); return true; else return false;注意： a) 要求p找到第i-1个而非第i个元素。为什么？ b) 能够进行删除的条件： p & j=i-1 & p-next 。条件中的p-next就是要保证第i个元素存在，否则无法删除。若写成p-next & j=i-1也不妥，因为此时(循环结束时)可能有p=NULL，所以必须先确定p不空。技巧：将条件中的“大前提”放在前面。该条件也不可以写成p-next & p & j=i-1，因为先有p!=0才有p-next，上式颠倒了这一关系

26、。 c) 释放结点的方法。 free(s); d) 完成删除的步骤：。(8) 建立链表的两种方法思路： 建立空表（头结点）； 依次插入数据结点（每次插入表尾得(a1,a2,an)，每次插入表头得(an,a2,a1)）。1. 顺序建表void CreateLinkList ( LinkList &L, int n) / 建立空表 L = (LinkList) malloc(sizeof(LNode); L-next = NULL; / 空表 p = L; / 用p指向表尾 / 插入元素 for ( i=0; idata = x; / 插入表尾 s-next = p-next; p-next =

27、s; p = s; / 新的表尾 2. 逆序建表void CreateLinkList ( LinkList &L, int n) / 建立空表 L = (LinkList) malloc(sizeof(LNode); L-next = NULL; / 空表 / 插入元素 for ( i=0; idata = x; / 插入表头 s-next = L-next; L-next = s; 4. 循环链表(1) 特点最后一个结点的指针指向头结点。anCBA(b)(a)Ea1L.L(2) 类型定义同单链表。(3) 基本形态空表：L-next = L。非空表。(4) 与单链表的联系判断表尾的方法不同：

28、单链表用p=NULL；循环链表用p=L。其余操作相同。5. 双向循环链表(1) 特点一个结点包含指向后继(next)和指向前驱(prior)两个指针，两个方向又分别构成循环链表。datapriornext(2) 类型定义typedef struct DuLNode DataType data; struct DuLNode *prior, *next; / 两个指针 DuLNode, *DuLinkList;(3) 基本形态空表：用后向指针判断L-next = L，或者用前向指针判断L-prior = L。非空表。a1a2anLL. .(4) 与单链表和循环链表的联系最大不同：前驱容易求得，可

29、以向前遍历。判断表尾的方法与循环链表相同：p=L。插入和删除时需要修改两个方向的指针。(5) 插入和删除需要修改两个方向的指针。例如：(见下表)表 2.2 双向循环链表的插入和删除p之后插入sp之前插入s删除p之后继s删除ps-next = p-next;p-next = s;s-prior = p;s-next-prior = s;s-prior = p-prior;p-prior = s;s-next = p;s-prior-next = s;s = p-next;p-next = s-next;p-next-prior = p;p-prior-next = p-next;p-next-p

30、rior = p-prior;6. 顺序表与单链表的比较表 2.3 顺序表和单链表的比较顺序表单链表以地址相邻表示关系用指针表示关系随机访问，取元素O(1)顺序访问，取元素O(n)插入、删除需要移动元素O(n)插入、删除不用移动元素O(n)(用于查找位置)总结：需要反复插入、删除，宜采用链表；反复提取，很少插入、删除，宜采用顺序表。二、 习题2.1 将顺序表中的元素反转顺序。2.2 在非递减有序的顺序表中插入元素x，并保持有序。2.3 删除顺序表中所有等于x的元素。2.4 编写算法实现顺序表元素唯一化(即使顺序表中重复的元素只保留一个)，给出算法的时间复杂度。2.5 非递减有序的顺序表元素唯一

31、化(参见习题2.4)，要求算法的时间复杂度为O(n)。2.6 将单链表就地逆置，即不另外开辟结点空间，而将链表元素翻转顺序。2.7 采用插入法将单链表中的元素排序。2.8 采用选择法将单链表中的元素排序。2.9 将两个非递减有序的单链表归并成一个，仍并保持非递减有序。第3章 栈和队列一、 基础知识和算法1. 栈栈，栈顶，栈底，空栈，后进先出(LIFO)，入栈(Push)，出栈(Pop)。顺序栈：栈的顺序存储结构；链栈：栈的链式存储结构。2. 链栈(1) 存储结构a1/anS.an-1用不带头结点的单链表实现。(2) 类型定义同单链表。(3) 基本形态a1/anS.an-1S/1. 栈空条件:

32、S = NULL2. 栈非空3. 栈满（一般不出现）(4) 基本算法1. 入栈 Push (&s, x)bool Push ( LinkList &s, DataType x ) / 新建结点 p = (LinkList) malloc (sizeof(LNode); if ( !p ) return false; / 失败 p-data = x; / 插入栈顶 p-next = s; s = p; return true;2. 出栈 Pop (&s, &x)前提：栈非空。bool Pop ( LinkList &s, DataType &x ) if ( s=NULL ) return fa

33、lse; / 栈空 / 删除栈顶元素 p = s; s = s-next; x = p-data; free ( p ); return true;3. 栈顶元素前提：栈非空。bool Top ( LinkList &s, DataType &x ) if ( s=NULL ) return false; / 栈空 x = s-data; return true;3. 顺序栈(1) 存储结构类似于顺序表，插入和删除操作固定于表尾。(2) 类型定义简单说，“数组 + 长度” 不准确的说法，只为便于理解和记忆，不要在正式场合引用。const int MAXSIZE = 栈的最大容量；typedef

34、 struct DataType elemMAXSIZE; int top; SqStack;(3) 基本形态1. 栈空条件 s.top = 0;2. 栈满条件 s.top = MAXSIZE3. 栈不空、不满(4) 基本算法1. 入栈 Push (&s, x)前提：栈不满bool Push ( SqStack& s, DataType x ) if ( s.top = MAXSIZE ) return false; / 栈满 s.elemtop = x; / 或者s.elemtop+ = x; top+; / 代替这两行 return true;2. 出栈 Pop (&s, &x)前提：栈非

35、空bool Pop ( SqStack &s, DataType &x ) if ( s.top=0 ) return false; top-; / 可用x=s.elem-top; x = s.elemtop; / 代替这两行 return true;3. 栈顶元素前提：栈非空s.elemtop-1 即是。4. 队列队列，队头，队尾，空队列，先进先出(FIFO)。链队列：队列的链式存储结构。循环队列：队列的顺序存储结构之一。5. 链队列(1) 存储结构/-a1-a2-an/.Q.frontQ.rearQ.frontQ.rear简而言之，“单链表 + 尾指针” 不准确的说法，只为便于理解和记忆，

36、不要在正式场合引用。(2) 类型定义课本P61。typedef struct LinkList front; LinkList rear; LinkQueue;(3) 基本形态队列空：Q.front=Q.rear。非空队列。(4) 基本算法1. 入队列课本P62。插入队尾，注意保持Q.rear指向队尾。2. 出队列课本P62。删除队头元素，特别注意：如果队列中只有一个元素，则队头也同时是队尾，删除队头元素后也需要修改队尾指针。6. 循环队列(1) 存储结构简单说，“数组 + 头、尾位置” 不准确的说法，只为便于理解和记忆，不要在正式场合引用。(2) 类型定义const int MAXSIZE = 队列最大容量;typedef struct DataType elemMAXSIZE;