目录
第1章绪论 1
1.1数据结构的概念 2
1.1.1引言 2
1.1.2数据结构的有关概念与术语 5
1.2抽象数据类型 7
1.3算法描述与分析 11
1.3.1什么是算法 11
1.3.2算法分析技术初步 13
1.4基本的算法策略 17
1.4.1穷举法 17
1.4.2递推法与迭代法 18
1.4.3分治法 20
1.4.4贪心算法 22<p> 目录</p> <p>第1章绪论 1</p> <p>1.1数据结构的概念 2</p> <p>1.1.1引言 2</p> <p>1.1.2数据结构的有关概念与术语 5</p> <p>1.2抽象数据类型 7</p> <p>1.3算法描述与分析 11</p> <p>1.3.1什么是算法 11</p> <p>1.3.2算法分析技术初步 13</p> <p>1.4基本的算法策略 17</p> <p>1.4.1穷举法 17</p> <p>1.4.2递推法与迭代法 18</p> <p>1.4.3分治法 20</p> <p>1.4.4贪心算法 22</p> <p>1.4.5动态规划 22</p> <p>1.5案例分析 25</p> <p>1.6小结 26</p> <p>讨论小课堂1 27</p> <p>习题1 28第2章线性表 30</p> <p>2.1线性表的定义及其运算 30</p> <p>2.1.1线性表的定义 30</p> <p>2.1.2线性表的抽象数据类型 31</p> <p>2.2线性表的顺序存储结构及实现 32</p> <p>2.2.1顺序存储结构 32</p> <p>2.2.2线性表在向量中基本运算的实现 34</p> <p>2.3线性表的链表存储结构 39</p> <p>2.3.1单链表 39</p> <p>2.3.2线性链表基本运算的实现 42</p> <p>2.4循环链表和双向链表 49</p> <p>2.4.1循环链表 49</p> <p>2.4.2双向链表 50</p> <p>2.4.3顺序存储结构与链表存储结构的综合分析与比较 51</p> <p>2.5单链表的应用 52</p> <p>2.5.1多项式相加的链表存储结点 52</p> <p>2.5.2多项式相加的算法实现 53</p> <p>2.6小结 54</p> <p>讨论小课堂2 55</p> <p>习题2 55第3章栈和队列 57</p> <p>3.1栈 57</p> <p>3.1.1栈的定义 57</p> <p>3.1.2栈的抽象数据类型 58</p> <p>3.2栈的顺序存储结构及实现 59</p> <p>3.2.1栈的顺序存储结构 59</p> <p>3.2.2顺序栈的定义 60</p> <p>3.3栈的链表存储结构及实现 62</p> <p>3.4栈的应用 65</p> <p>3.4.1表达式的计算 65</p> <p>3.4.2子程序的嵌套调用 67</p> <p>3.4.3递归调用 68</p> <p>3.5队列 69</p> <p>3.5.1队列的定义及运算 69</p> <p>3.5.2队列的抽象数据类型 70</p> <p>3.6队列的顺序存储结构及实现 70</p> <p>3.7队列的链表存储结构及实现 74</p> <p>3.8队列的应用 77</p> <p>3.9算法实例——Hanoi塔问题 78</p> <p>3.10小结 79</p> <p>讨论小课堂3 80</p> <p>习题3 81第4章串 83</p> <p>4.1串的基本概念 83</p> <p>4.1.1串的定义 83</p> <p>4.1.2串的抽象数据类型 84</p> <p>4.2串的存储与基本操作的实现 85</p> <p>4.2.1定长顺序串 86</p> <p>4.2.2堆串 86</p> <p>4.2.3块链串 87</p> <p>4.2.4串操作的实现 88</p> <p>4.3串的模式匹配 91</p> <p>4.3.1朴素模式匹配算法 92</p> <p>4.3.2模式匹配的KMP算法 92</p> <p>4.4串的应用举例: 文本编辑 97</p> <p>4.5小结 99</p> <p>讨论小课堂4 99</p> <p>习题4 100第5章数组和广义表 101</p> <p>5.1数组 102</p> <p>5.1.1数组的基本概念 102</p> <p>5.1.2二维数组 102</p> <p>5.1.3数组的顺序存储方式 103</p> <p>5.2矩阵的压缩存储 104</p> <p>5.2.1特殊矩阵 104</p> <p>5.2.2稀疏矩阵 107</p> <p>5.3广义表 112</p> <p>5.3.1广义表的定义 112</p> <p>5.3.2广义表的存储结构 113</p> <p>5.4案例分析 116</p> <p>5.4.1概述和方法 116</p> <p>5.4.2算法和程序 118</p> <p>5.5小结 120</p> <p>讨论小课堂5 120</p> <p>习题5 120第6章树与二叉树 122</p> <p>6.1树的概念及术语 123</p> <p>6.1.1树的定义 123</p> <p>6.1.2树的抽象数据类型 124</p> <p>6.1.3树的表示方式 125</p> <p>6.2二叉树 125</p> <p>6.2.1二叉树的定义 125</p> <p>6.2.2二叉树的抽象数据类型 126</p> <p>6.2.3二叉树的重要性质 127</p> <p>6.2.4二叉树的存储结构 128</p> <p>6.3二叉树的遍历 130</p> <p>6.3.1先序遍历 131</p> <p>6.3.2中序遍历 131</p> <p>6.3.3后根遍历 132</p> <p>6.3.4按层遍历 133</p> <p>6.3.5非递归遍历算法 133</p> <p>6.3.6二叉树的建立 136</p> <p>6.3.7二叉树遍历的应用举例 137</p> <p>6.4二叉树与树、森林的转换 139</p> <p>6.4.1树与二叉树的转换 139</p> <p>6.4.2森林与二叉树的转换 140</p> <p>6.5树的存储结构 141</p> <p>6.5.1树的双亲表示法 142</p> <p>6.5.2孩子表示法 142</p> <p>6.5.3孩子兄弟表示法 143</p> <p>6.6树的遍历 144</p> <p>6.6.1一般树的遍历 144</p> <p>6.6.2森林的遍历 145</p> <p>6.7二叉树的应用 146</p> <p>6.7.1哈夫曼树 146</p> <p>6.7.2哈夫曼树的构造 146</p> <p>6.7.3哈夫曼树的实现算法 148</p> <p>6.7.4哈夫曼编码 149</p> <p>6.8小结 150</p> <p>讨论小课堂6 150</p> <p>习题6 150第7章图 153</p> <p>7.1图的基本概念 153</p> <p>7.1.1图的定义 153</p> <p>7.1.2图的术语 155</p> <p>7.1.3图的抽象数据类型 156</p> <p>7.2图的存储结构 157</p> <p>7.2.1图的邻接矩阵 157</p> <p>7.2.2邻接矩阵表示法的描述 159</p> <p>7.2.3邻接矩阵表示下的基本操作的实现 160</p> <p>7.2.4图的邻接链表 161</p> <p>7.2.5图的邻接表表示法的描述 162</p> <p>7.2.6邻接表表示下基本操作的实现 163</p> <p>7.3图的遍历与图的连通性 165</p> <p>7.3.1图的深度优先遍历 166</p> <p>7.3.2图的广度优先遍历 168</p> <p>7.3.3非连通图和连通分量 170</p> <p>7.4图的*小生成树 170</p> <p>7.4.1*小生成树的基本概念 170</p> <p>7.4.2普里姆(Prim)算法 171</p> <p>7.4.3克鲁斯卡尔(Kruskal)算法 174</p> <p>7.5*短路径 175</p> <p>7.5.1从某顶点到其余各顶点的*短路径 175</p> <p>7.5.2每对顶点之间的*短路径 178</p> <p>7.6拓扑排序与关键路径 180</p> <p>7.6.1拓扑排序 180</p> <p>7.6.2关键路径 183</p> <p>7.7图的应用 189</p> <p>7.7.1图在路由器寻径中的应用 189</p> <p>7.7.2图在物流信息系统中应用 190</p> <p>7.8小结 190</p> <p>讨论题7 191</p> <p>习题7 191第8章查找 193</p> <p>8.1查找的基本概念 194</p> <p>8.2静态查找表 195</p> <p>8.2.1顺序表的查找 195</p> <p>8.2.2有序表的折半查找 196</p> <p>8.2.3索引顺序表查找 200</p> <p>8.3动态查找表 201</p> <p>8.3.1二叉排序树 201</p> <p>8.3.2平衡二叉树 210</p> <p>8.4案例分析 214</p> <p>8.4.1直方图问题 214</p> <p>8.4.2箱子装载问题 216</p> <p>8.5小结 218</p> <p>讨论小课堂8 218</p> <p>习题8 219第9章排序 220</p> <p>9.1排序的基本概念 220</p> <p>9.2插入排序 221</p> <p>9.2.1直接插入排序 221</p> <p>9.2.2折半插入排序 222</p> <p>9.2.3希尔排序 222</p> <p>9.3交换排序 224</p> <p>9.3.1冒泡排序 224</p> <p>9.3.2快速排序 225</p> <p>9.4选择排序 229</p> <p>9.4.1简单选择排序 229</p> <p>9.4.2堆排序 230</p> <p>9.5归并排序 233</p> <p>9.6基数排序 235</p> <p>9.7小结 239</p> <p>讨论小课堂9 240</p> <p>习题9 240第10章索引结构与哈希 242</p> <p>10.1静态索引结构 242</p> <p>10.1.1索引表 242</p> <p>10.1.2索引表查找 242</p> <p>10.2动态索引结构(B-树和B 树) 245</p> <p>10.2.1B-树的定义 245</p> <p>10.2.2B-树的运算 246</p> <p>10.2.3B 树 249</p> <p>10.3键树及Trie树 250</p> <p>10.3.1键树的定义 250</p> <p>10.3.2双链树 251</p> <p>10.3.3Trie树 252</p> <p>10.4哈希表及其查找 253</p> <p>10.4.1哈希表与哈希函数 253</p> <p>10.4.2构造哈希函数的常用方法 254</p> <p>10.4.3解决冲突的主要方法 256</p> <p>10.4.4哈希查找的性能分析 260</p> <p>10.5小结 261</p> <p>讨论小课堂10 262</p> <p>习题10 262参考文献 265</p>显示全部信息前 言前言数据结构与算法是计算机专业重要的专业基础课程与核心课程之一。从理论上讲,通过学习数据结构可以使学生掌握对不同数据结构的组织方法和对具体数据结构所实施的若干算法,并能分析算法的优劣。学习数据结构与算法的*终目的是提高学生的程序设计水平和能力。对于应用型人才培养应该注重能力的培养,而不是只满足于理论的掌握。因此,在本书的编写过程中遵循谭浩强教授提出的新三部曲“提出问题—解决问题—归纳分析”的写法,强调从实践中获取知识。本书给出了能够解决实际问题的大量算法,希望学生在阅读和总结这些算法的基础上提高程序设计的水平。因此,本书的大部分算法只要经过简单的修改就能上机运行,具有很好的实用价值,也给学习者带来了方便。(1) 深入浅出,通俗易懂。对数据结构的基本概念、基本理论的阐述注重科学严谨。同时从应用出发,对新概念的引入从实例着手。对各种基本算法描述尽量详细,叙述清楚。本书在讲解数据的存储结构时,使用了大量的图示和表格,有助于学生对数据结构的理解。(2) 理论联系实际。为了巩固所学的理论知识,每章都附有练习题和讨论题,供学生进行书面练习、上机作业时选用和讨论。针对学生中普遍存在的“只懂概念不懂编程”的问题,配套有完整的习题与实验指导书,每一章节都给出了完整的C语言和C 源程序示例,供学生参考模拟,从而提高学生的程序设计能力。数据结构课程的一个重要任务是培养学生进行复杂程序设计的能力,目的在于提高学生的程序设计能力和进行规���化程序设计的素养。(3) 循序渐进,逐步加深。由于采用了C语言和C 语言面向对象的方法描述数据结构,对于低年级学生来说存在一定难度。为了使读者更好地学习数据结构自身的知识内容,克服描述工具所带来的困难,本书对此做了独特处理。本书可以作为普通高等院校计算机专业本科和专升本的教材。由于资源翔实、通俗易懂,对书中内容适当取舍之后,也可作为高等职业技术和专科教育的计算机专业教材。同时,本书还可作为研究生考试和各类认证考试的复习参考书,以及计算机应用工作者和工程技术人员的参考书。本书由汪沁、奚李峰主编。其中,第1~3章、第9章和实验指导由汪沁、奚李峰编写;第6章、第10章由邓芳编写;第4章、第7章由刘晓利编写;第5章、第8章由金冉、陈慧编写。全书由汪沁、奚李峰统编。考虑到在数据结构与算法的学习中,教师需要在课堂上对大量的算法进行讲解,而学生应该在此基础上大量阅读并理解数据结构经典算法,因此本书对算法都进行了较为详细的注释。对一些难度比较大的算法,在用语言描述之前,还对算法进行了分析。由于编者水平有限,疏漏在所难免,欢迎广大读者批评指正并提出宝贵意见。前言数据结构与算法是计算机专业重要的专业基础课程与核心课程之一。从理论上讲,通过学习数据结构可以使学生掌握对不同数据结构的组织方法和对具体数据结构所实施的若干算法,并能分析算法的优劣。学习数据结构与算法的*终目的是提高学生的程序设计水平和能力。对于应用型人才培养应该注重能力的培养,而不是只满足于理论的掌握。因此,在本书的编写过程中遵循谭浩强教授提出的新三部曲“提出问题—解决问题—归纳分析”的写法,强调从实践中获取知识。本书给出了能够解决实际问题的大量算法,希望学生在阅读和总结这些算法的基础上提高程序设计的水平。因此,本书的大部分算法只要经过简单的修改就能上机运行,具有很好的实用价值,也给学习者带来了方便。(1) 深入浅出,通俗易懂。对数据结构的基本概念、基本理论的阐述注重科学严谨。同时从应用出发,对新概念的引入从实例着手。对各种基本算法描述尽量详细,叙述清楚。本书在讲解数据的存储结构时,使用了大量的图示和表格,有助于学生对数据结构的理解。(2) 理论联系实际。为了巩固所学的理论知识,每章都附有练习题和讨论题,供学生进行书面练习、上机作业时选用和讨论。针对学生中普遍存在的“只懂概念不懂编程”的问题,配套有完整的习题与实验指导书,每一章节都给出了完整的C语言和C 源程序示例,供学生参考模拟,从而提高学生的程序设计能力。数据结构课程的一个重要任务是培养学生进行复杂程序设计的能力,目的在于提高学生的程序设计能力和进行规范化程序设计的素养。(3) 循序渐进,逐步加深。由于采用了C语言和C 语言面向对象的方法描述数据结构,对于低年级学生来说存在一定难度。为了使读者更好地学习数据结构自身的知识内容,克服描述工具所带来的困难,本书对此做了独特处理。本书可以作为普通高等院校计算机专业本科和专升本的教材。由于资源翔实、通俗易懂,对书中内容适当取舍之后,也可作为高等职业技术和专科教育的计算机专业教材。同时,本书还可作为研究生考试和各类认证考试的复习参考书,以及计算机应用工作者和工程技术人员的参考书。本书由汪沁、奚李峰主编。其中,第1~3章、第9章和实验指导由汪沁、奚李峰编写;第6章、第10章由邓芳编写;第4章、第7章由刘晓利编写;第5章、第8章由金冉、陈慧编写。全书由汪沁、奚李峰统编。考虑到在数据结构与算法的学习中,教师需要在课堂上对大量的算法进行讲解,而学生应该在此基础上大量阅读并理解数据结构经典算法,因此本书对算法都进行了较为详细的注释。对一些难度比较大的算法,在用语言描述之前,还对算法进行了分析。由于编者水平有限,疏漏在所难免,欢迎广大读者批评指正并提出宝贵意见。<br /> 编者2018年5月显示全部信息免费在线读第3章栈 和 队 列栈和队列是使用频率*高的数据结构。栈和队列是两种特殊的线性结构。它们都与第2章中的线性表有密切的联系(经过某种限制以后)。一方面,栈和队列的逻辑结构与线性表相同;另一方面,栈和队列的基本运算与线性表的基本运算十分类似,可以看成线性表运算的子集。因此,可将栈和队列看成两种特殊的线性表。【案例引入】在日常生活中经常会遇到栈或队列的实例。例如,单车道的死胡同,铁路调度等都是栈的例子。比如,可以把放在桌上的一叠书看成一个栈,并约定不能把书插入中间,或从中间把书抽出,只能从上面取书或放书。等待购物的顾客和民航机票订购中都用到队列。栈和队列还广泛应用于各种软件系统之中。3.1栈〖*4/5〗3.1.1栈的定义栈可以看成一种“特殊的”线性表,这种线性表上的插入和删除运算限定在表的某一端进行。允许进行插入和删除的这一端称为栈顶,另一端称为栈底。处于栈顶位置的数据元素称为栈顶元素。在如图3.1(b)所示的栈中,元素是以a1,a2,…,an的顺序进栈,因此栈底元素是a1,栈顶元素是an。不含任何数据元素的栈称为空栈。图3.1羊肉串和栈可以用一个例子说明栈结构的特征。我们经常吃的羊肉串,假设是图3.1(a)中的,铁签子可以穿上若干羊肉块。现有五小块羊肉,分别编号为①~⑤,按编号的顺序穿进铁签子上,如图3.1(a)所示。此时若吃第④块羊肉,必须先拿掉或者吃掉第⑤块后才有可能(当然此处排除直接从中间咬的可能性)。若要吃第①块羊肉,则必须等到⑤④③②依次都退出后才行。这里,吃羊肉的原则是后穿上去的先吃到。换句话说,先穿上去的后吃到。问题: 你还能举出在我们生活中和栈相关的实例吗?栈可以比作这里的死胡同,栈顶相当于胡同口,栈底相当于胡同的另一端,进、出胡同可看作栈的插入、删除操作,也称为进栈、出栈操作。进栈、出栈都在栈顶进行,进出都经过胡同口。这表明栈的操作原则是先进后出(First In Last Out,FILO)或称后进先出(Last In First Out,LIFO)。因此,栈又称为后进先出线性表。栈的基本操作除了进栈、出栈外,还有初始化、判空和取栈顶元素等。3.1.2栈的抽象数据类型〖*4/5〗1. 栈的抽象数据类型ADT Stack{ 数据对象: D={ai| ai∈ElemSet,i=1,2,…,nn≥0;} 数据关系: R={ ai, ai+1 |,ai, ai+1∈D, i=1,2,…,n; a1 无前驱,an无后继;} 约定a1 端为栈底,an端为栈顶。 基本操作: (1) 初始化一个空栈;(2) 判栈空,空栈返回True,否则返回False;(3) 入栈,在栈顶插入一个元素;(4) 出栈,在栈顶删除一个元素;(5) 取栈顶元素值;(6) 置栈为空状态;(7) 求栈中数据元素的个数;(8) 销毁栈; 等等} ADTStack;2. 下面先举一个简单例子来说明栈的应用例3.1程序员在终端输入程序时,不能保证不出差错,但可以在发现敲错时及时纠正。例如,每当敲错了一个键的时候,可以补敲一个退格符'#',以表示前一个字符无效;如果发现当前一行有错,可以敲入一个退行符'@',以表示'@'与前一个换行符之间的字符全部无效。例如,假设在终端上输入了这样两行字符:BGE##EGIM#NRAD(A@READ(A)则实际有效的是下面两行字符:BEGINREAD(A)为此,需要一个简单的输入处理程序来完成上述修改。程序中设一个栈来逐行处理从终端输入的字符串。每次从终端接收一个字符后先做如下判别: 如果它既不是退格符也不是退行符,则将该字符压入栈顶;如果是退格符,则从栈顶删去一个字符;如果它是退行符,就把字符栈清为空栈。上述处理过程可用类C的算法如下。void LineEdit() { /利用字符栈S,从终端接收一行并传送至调用过程的数据区/InitStack(S);/构造空栈S/ch=getchar(); /从终端接收**个字符/while(ch!=EOF) /EOF为全文结束符/{ while(ch!=EOF ch!='\\n'){switch(ch){ case '#': Pop(S,ch); break; /仅当栈非空时退栈/case '@': InitStack(S);break;/重置S为空栈/default: Push(S,ch); /有效字符进栈,未考虑栈满的情况/}ch=getchar(); /从终端接收下一个字符/}/将从栈底到栈顶的栈内字符传送至调用过程的数据区/ClearStack(S);/重置S为空栈/if(ch!=EOF) ch=getchar();}DestroyStack(S);/释放栈空间/}/LineEdit/本算法并不是C语言源代码,而是一种方法和思路的示意。栈在计算机内究竟怎样存储、怎样进栈和出栈,将在下面做详细介绍。问题: 栈和线性表有什么不同?3.2栈的顺序存储结构及实现与线性表类似栈也有两种存储结构,即顺序存储和链表存储结构。本节介绍栈的顺序存储结构。栈的顺序存储结构亦称顺序栈。3.2.1栈的顺序存储结构栈的顺序存储结是利用一批地址连续的存储单元依次存放自栈底到栈顶的数据元素,同时设指针top指向栈顶元素的当前位置。通常用一维数组来实现栈的顺栈存储,习惯上以数组小下标的一端做栈底,当top=0时为空栈。在数据元素不断进栈时,栈顶指针top不断地加1,当top达到数组的*大下标值时为栈满。栈的顺序存储结构描述为:#define MAXSIZE 100typedef int ElemType;typedef struct { ElemType elem[MAXSIZE];int top;}SqStack;/顺序栈的类型标识符/SqStackS;/说明S是栈变量/其中SqStack是顺序栈的类型标识符,S是一个栈。假设MAXSIZE取值为6,图3.2展示了顺序栈S中数据元素和栈顶指针top的关系。为了与前面所述top=0为空栈相一致,图中未画出S.elem[0]。逻辑上可利用有效空间为S.elem[1],…,S.elem[5]。图3.2栈的顺序存储结构其中图3.2(a)是空栈状态;图3.2(b)是进栈一个元素A之后的状态;图3.2(c)是在图3.2(b)状态基础上连续将元素B、C、D、E进栈之后的状态,显然已经达到栈满状态,此时不允许任何元素进栈。图3.2(d)是在图3.2(c)状态基础上,出栈一个元素后的栈状态。在面向对象的程序设计中,通常将数据元素的存储和对数据的操作封装在一个类之中。在各种版本的使用C数据结构教材中,对于顺序存储结构描述在具体实现形式有所不同,但是本质上是相同的。3.2.2顺序栈的定义栈采用的顺序存储结构,可以作为类的数据成员。栈的各种操作的处理,可以作为类的函数成员。本节介绍顺序栈的类的定义,**讨论栈的各种操作的算法。1. 初始化栈void InitStack(SqStack S)/构造一个空栈/{ S- top=-1;} /InitStack/2.进栈操作void Push(SqStack S, DataType x) /插入元素x为新的栈顶元素/{if(S- top MAXSIZE-1){ S- top ;S- elem\[S- top\]=x;}else printf("Overflow ! \\n"); /栈满/}/Push/3. 出栈操作/若栈不空,则删除栈顶元素,元素值由函数名返回。/ElemType Pop(SqStack p){if(S- top==-1){ printf("Underflow!\\n"); return -1;}/栈空,返回-1/else {x=S- elem[S- top];S- top--;return x;}
本书系统地介绍了各种数据结构的特点、存储结构及相关算法。书中采用C语言描述算法。主要内容包括:数据结构的基本概念、算法描述和算法分析初步;线性表、堆栈、队列、串、数组、树、图等结构;查找、排序等。每章后面配有小节、习题、讨论题。有配套的完整的习题与实验指导书,每一章节都给出了完整C语言和C 源程序示例。本书叙述清晰、深入浅出、注意实践、便于教学与实践。本书可作为高等院校计算机专业的教材,也可供从事计算机应用与工程工作的科技工作者自学参考。