目录
第1章绪论1
1.1问题求解与程序设计2
1.1.1程序设计的一般过程2
1.1.2数据结构在程序设计中的作用4
1.1.3算法在程序设计中的作用6
1.1.4本书讨论的主要内容7
1.2数据结构的基本概念8
1.2.1数据结构8
1.2.2抽象数据类型11
1.3算法的基本概念12
1.3.1算法及算法的特性12
1.3.2算法的描述方法14
1.4算法分析15<p>目录</p> <p>第1章绪论1</p> <p>1.1问题求解与程序设计2</p> <p>1.1.1程序设计的一般过程2</p> <p>1.1.2数据结构在程序设计中的作用4</p> <p>1.1.3算法在程序设计中的作用6</p> <p>1.1.4本书讨论的主要内容7</p> <p>1.2数据结构的基本概念8</p> <p>1.2.1数据结构8</p> <p>1.2.2抽象数据类型11</p> <p>1.3算法的基本概念12</p> <p>1.3.1算法及算法的特性12</p> <p>1.3.2算法的描述方法14</p> <p>1.4算法分析15</p> <p>1.4.1算法的时间复杂度16</p> <p>1.4.2算法的空间复杂度17</p> <p>1.4.3算法分析举例18</p> <p>1.5扩展与提高20</p> <p>1.5.1从数据到大数据20</p> <p>1.5.2算法分析的其他渐进符号22</p> <p>习题123</p> <p> </p> <p>第2章线性表25</p> <p>2.1引言26</p> <p>2.2线性表的逻辑结构27</p> <p>2.2.1线性表的定义27</p> <p>2.2.2线性表的抽象数据类型定义27数据结构——从概念到C实现目录2.3线性表的顺序存储结构及实现29</p> <p>2.3.1顺序表的存储结构定义29</p> <p>2.3.2顺序表的实现30</p> <p>2.3.3顺序表的使用34</p> <p>2.4线性表的链接存储结构及实现35</p> <p>2.4.1单链表的存储结构定义35</p> <p>2.4.2单链表的实现37</p> <p>2.4.3单链表的使用44</p> <p>2.4.4双链表45</p> <p>2.4.5循环链表47</p> <p>2.5顺序表和链表的比较48</p> <p>2.6扩展与提高48</p> <p>2.6.1线性表的静态链表存储48</p> <p>2.6.2顺序表的动态分配方式51</p> <p>2.7应用实例52</p> <p>2.7.1约瑟夫环问题52</p> <p>2.7.2一元多项式求和55</p> <p>习题259</p> <p> </p> <p>第3章栈和队列63</p> <p>3.1引言64</p> <p>3.2栈65</p> <p>3.2.1栈的逻辑结构65</p> <p>3.2.2栈的顺序存储结构及实现66</p> <p>3.2.3栈的链接存储结构及实现68</p> <p>3.2.4顺序栈和链栈的比较71</p> <p>3.3队列72</p> <p>3.3.1队列的逻辑结构72</p> <p>3.3.2队列的顺序存储结构及实现73</p> <p>3.3.3队列的链接存储结构及实现77</p> <p>3.3.4循环队列和链队列的比较80</p> <p>3.4扩展与提高81</p> <p>3.4.1两栈共享空间81</p> <p>3.4.2双端队列82</p> <p>3.5应用举例83</p> <p>3.5.1括号匹配问题83</p> <p>3.5.2表达式求值85</p> <p>习题388第4章字符串和多维数组91</p> <p>4.1引言92</p> <p>4.2字符串92</p> <p>4.2.1字符串的逻辑结构92</p> <p>4.2.2字符串的存储结构94</p> <p>4.2.3模式匹配94</p> <p>4.3多维数组98</p> <p>4.3.1数组的逻辑结构98</p> <p>4.3.2数组的存储结构与寻址99</p> <p>4.4矩阵的压缩存储100</p> <p>4.4.1特殊矩阵的压缩存储100</p> <p>4.4.2稀疏矩阵的压缩存储102</p> <p>4.5扩展与提高105</p> <p>4.5.1稀疏矩阵的转置运算105</p> <p>4.5.2广义表107</p> <p>4.6应用实例111</p> <p>4.6.1发纸牌111</p> <p>4.6.2八皇后问题112</p> <p>习题4115</p> <p> </p> <p>第5章树和二叉树119</p> <p>5.1引言120</p> <p>5.2树的逻辑结构121</p> <p>5.2.1树的定义和基本术语121</p> <p>5.2.2树的抽象数据类型定义123</p> <p>5.2.3树的遍历操作123</p> <p>5.3树的存储结构124</p> <p>5.3.1双亲表示法124</p> <p>5.3.2孩子表示法125</p> <p>5.3.3孩子兄弟表示法126</p> <p>5.4二叉树的逻辑结构127</p> <p>5.4.1二叉树的定义127</p> <p>5.4.2二叉树的基本性质129</p> <p>5.4.3二叉树的抽象数据类型定义130</p> <p>5.4.4二叉树的遍历操作131</p> <p>5.5二叉树的存储结构133</p> <p>5.5.1顺序存储结构133</p> <p>5.5.2二叉链表134</p> <p>5.5.3三叉链表138</p> <p>5.6森林138</p> <p>5.6.1森林的逻辑结构138</p> <p>5.6.2树、森林与二叉树的转换139</p> <p>5.7*优二叉树141</p> <p>5.7.1哈夫曼算法141</p> <p>5.7.2哈夫曼编码143</p> <p>5.8扩展与提高145</p> <p>5.8.1二叉树遍历的非递归算法145</p> <p>5.8.2线索二叉树148</p> <p>5.9应用实例151</p> <p>5.9.1堆与优先队列151</p> <p>5.9.2并查集154</p> <p>习题5155</p> <p> </p> <p>第6章图159</p> <p>6.1引言160</p> <p>6.2图的逻辑结构161</p> <p>6.2.1图的定义和基本术语161</p> <p>6.2.2图的抽象数据类型定义163</p> <p>6.2.3图的遍历操作164</p> <p>6.3图的存储结构及实现167</p> <p>6.3.1邻接矩阵167</p> <p>6.3.2邻接表170</p> <p>6.3.3邻接矩阵和邻接表的比较174</p> <p>6.4*小生成树175</p> <p>6.4.1Prim算法176</p> <p>6.4.2Kruskal算法178</p> <p>6.5*短路径182</p> <p>6.5.1Dijkstra算法183</p> <p>6.5.2Floyd算法185</p> <p>6.6有向无环图及其应用187</p> <p>6.6.1AOV网与拓扑排序187</p> <p>6.6.2AOE网与关键路径190</p> <p>6.7扩展与提高193</p> <p>6.7.1图的其他存储方法193</p> <p>6.7.2图的连通性194</p> <p>6.8应用实例196</p> <p>6.8.1七巧板涂色问题196</p> <p>6.8.2医院选址问题198</p> <p>习题6200</p> <p> </p> <p>第7章查找技术205</p> <p>7.1概述206</p> <p>7.1.1查找的基本概念206</p> <p>7.1.2查找算法的性能207</p> <p>7.2线性表的查找技术207</p> <p>7.2.1顺序查找207</p> <p>7.2.2折半查找208</p> <p>7.3树表的查找技术211</p> <p>7.3.1二叉排序树211</p> <p>7.3.2平衡二叉树217</p> <p>7.3.3B树220</p> <p>7.4散列表的查找技术225</p> <p>7.4.1散列查找的基本思想225</p> <p>7.4.2散列函数的设计226</p> <p>7.4.3处理冲突的方法227</p> <p>7.4.4散列查找的性能分析231</p> <p>7.4.5开散列表与闭散列表的比较232</p> <p>7.5各种查找方法的比较232</p> <p>7.6扩展与提高233</p> <p>7.6.1顺序查找的改进——分块查找233</p> <p>7.6.2折半查找的改进——插值查找234</p> <p>7.6.3B树的改进——B 树235</p> <p>习题7236</p> <p> </p> <p>第8章排序技术239</p> <p>8.1概述240</p> <p>8.1.1排序的基本概念240</p> <p>8.1.2排序算法的性能241</p> <p>8.2插入排序241</p> <p>8.2.1直接插入排序241</p> <p>8.2.2希尔排序243</p> <p>8.3交换排序245</p> <p>8.3.1起泡排序245</p> <p>8.3.2快速排序247</p> <p>8.4选择排序250</p> <p>8.4.1简单选择排序250</p> <p>8.4.2堆排序252</p> <p>8.5归并排序256</p> <p>8.5.1二路归并排序的递归实现256</p> <p>8.5.2二路归并排序的非递归实现257</p> <p>8.6各种排序方法的比较259</p> <p>8.7扩展与提高261</p> <p>8.7.1排序问题的时间下界261</p> <p>8.7.2基数排序262</p> <p>习题8264</p> <p> </p> <p>附录A预备知识269</p> <p>A.1数学术语269</p> <p>A.2级数求和269</p> <p>A.3集合270</p> <p>A.4关系271</p> <p> </p> <p>附录BC语言基本语法273</p> <p>B.1程序结构273</p> <p>B.2数据的基本表现形式——常量和变量274</p> <p>B.3数据类型275</p> <p>B.4控制语句277</p> <p>B.5函数278</p> <p>B.6动态存储分配281</p> <p> </p> <p>附录C词汇索引283</p> <p> </p> <p>参考文献287</p>显示全部信息前 言前言前言<br />结构是计算机及相关专业的核心课程,也是计算机及相关专业硕士研究生入学考试的必考科目,而且是理工专业的热门公选课程。作为程序设计的重要补充和延伸,数据结构所讨论的知识内容、蕴含的技术方法、体现的思维方式,无论进一步学习计算机专业的其他课程,还是从事计算机领域的各项工作,都有着不可替代的作用。数据结构课程的知识丰富,内容抽象,隐藏在各知识单元的概念和方法较多,贯穿于各知识单元的链表和递归更是加重了学习难度。本书的编写者长期从事数据结构的研究和教学,深切理解学生在学习数据结构过程中遇到的问题和困惑,深入探究掌握数据结构的有效途径和方法,深刻思考数据结构对培养程序设计和计算思维的地位和作用,深度把握课程的教学目标和**难点,本书在教学内容和教学设计等方面进行了如下处理。1. 合理规划教学内容。紧扣《高等学校计算机专业核心课程教学实施方案》和《计算机学科硕士研究生入学考试大纲》,涵盖教学方案及考研大纲要求的全部知识点。2. 遵循认知规律,理清教学主线。根据学生的认知规律和课程的知识结构,按照从已知到未知的思维进程逐步推进教学内容,梳理和规划了各知识单元及其拓扑结构,设计了清晰的教学主线。知识单元及其拓扑结构如图1所示。图1数据结构课程的知识单元及拓扑结构3. 提炼基础知识,适当扩展提高。考虑到不同学校教学要求的差异以及不同学生学习需求的差别,一方面本着“够用、实用”的原则,抓牢核心概念,提炼基础性知识,贯彻数据结构课程的基本教学要求;另一方面对某些知识点进行了适当的扩充和提高(图1中打星号部分),这部分内容可用于选讲,也可用于学生自学或课外阅读(教学建议: 目录中打一个星号可用于选讲,打两个星号可用于课外阅读,其他是必讲的基础知识)。数据结构——从概念到C实现前言4. 兼顾概念层和实现层。从抽象数据类型的角度将数据结构的实现过程分为抽象层、设计层和实现层,其中抽象层定义数据结构和基本操作集合,设计层是数据结构的存储表示和算法设计,实现层用C语言实现数据结构,既强调了数据结构的基本概念和原理方法,又注重了数据结构的程序实现和实际运用。5. 展现求解过程,培养计算思维。通过讲思路讲过程讲方法,按照“问题→想法→算法→程序”的模式进行问题求解,采用“阐述基本思想→伪代码描述算法→C语言实现算法”的模式进行算法设计,这个过程正是计算思维的运用过程。每章通过两个应用实例展示问题求解过程以及算法设计过程。6. 明确**,化解难点。每一章开篇即给出该章的**难点,以及各知识点的教学要求,在具体阐述时还有针对性的处理方法。针对数据结构内容抽象的特点,全书设计了大量插图,将抽象内容进行了具体化处理,降低了理解问题的复杂性。总之,本书在概念的描述、实例的选择、知识的前后衔接、内容的组织结构,以及教学内容的理解、教学目标的实现、教学意图的融入、教学方法的运用等方面进行了系统思考和统筹设计,力图通过本书为读者构建多层次的知识体系。在问题求解层面,以数据表示和数据处理为主线,给出“问题→想法→算法→程序”的思维模式;在算法设计层面,通过伪代码描述算法,强调计算思维的培养;在算法分析层面,理解什么是“好”算法,给出算法分析的基本方法;在存储结构层面,通过存储示意图理解数据表示,再给出存储结构定义;在程序实现层面,给出所有数据结构的C程序实现以及使用范例;在数据结构和算法的运用层面,通过应用实例理解如何为求解问题设计适当的数据结构,如何基于数据结构设计算法,从而将数据结构、算法和程序设计有机地融合在一起。参加本书编写的还有董亚则、王涛、党源源、肖巍、刘冰、王有敬等老师,2015级硕士研究生唐东凯和李芬田同学参与了本书的代码调试工作,本书所有代码均在DevC 5.11、Visual Studio 2013、Microsoft Visual C 6.0编程环境下调试通过,读者可向出版社或作者索要程序源码。由于作者的知识和写作水平有限,书稿虽再三斟酌几经修改,仍难免有缺点和错误,欢迎专家和读者批评指正。作者的电子邮箱是: wanghm@ccut.edu.cn。<br />作者2016年2月显示全部信息媒体评论评论免费在线读第5章树和二叉树教学**二叉树的性质;二叉树和树的存储表示;二叉树的遍历及算法实现;树与二叉树的转换关系;哈夫曼树教学难点二叉树的层序遍历算法;二叉树的建立算法;哈夫曼算法教学内容和教学目标知识点教 学 要 求了解理解掌握熟练掌握树的定义和基本术语√树和二叉树的抽象数据类型定义√树和二叉树的遍历√树的存储结构√二叉树的定义√二叉树的基本性质√二叉树的顺序存储结构√二叉链表√三叉链表√二叉树遍历的递归算法√二叉树的层序遍历算法√二叉树的建立算法√树、森林和二叉树之间的转换√哈夫曼树及哈夫曼编码√教学提示本章的内容由树和二叉树两部分组成,并且由二叉链表存储结构,使得树和二叉树之间具有一一对应关系。对于树的逻辑结构,要从树的定义出发,在与线性表定义比较的基础上,把握要点理解其逻辑特征,通过具体实例识记树的基本术语。对于二叉树的逻辑结构,要从二叉树的定义出发,在与树的定义比较的基础上,理解树和二叉树是两种树结构。对于树和二叉树的存储结构,要以如何表示结点之间的逻辑关系为出发点,掌握不同存储方法以及他们之间的关系。二叉树的遍历是本章的**,首先从逻辑上掌握二叉树的遍历操作,然后给出二叉树遍历的递归算法,在理解二叉树遍历执行过程的基础上给出对应的非递归算法。数据结构——从概念到C实现第5章树和二叉树5.1引言前面讨论的数据结构都属于线性结构,主要描述具有单一的前驱和后继关系的数据。树结构是一种比线性结构更复杂的数据结构,比较适合描述具有层次关系的数据,如祖先——后代、上级——下属、整体——部分以及其他类似的关系。许多问题抽象出的数据模型具有层次关系,请看下面两个例子。【例51】文件系统。Windows操作系统的文件目录结构如图51所示,其中,/表示文件夹,括号内的数字表示文件的大小,单位是KB,假设文件夹本身的大小是1KB,如果要统计每个文件和文件夹的大小,即输出如图52所示的结果,应该如何存储这个文件目录结构并进行统计呢?图5\|1文件系统目录示例图5\|2输出结果

目录
第1章绪论1
1.1问题求解与程序设计2
1.1.1程序设计的一般过程2
1.1.2数据结构在程序设计中的作用4
1.1.3算法在程序设计中的作用6
1.1.4本书讨论的主要内容7
1.2数据结构的基本概念8
1.2.1数据结构8
1.2.2抽象数据类型11
1.3算法的基本概念12
1.3.1算法及算法的特性12
1.3.2算法的描述方法14
1.4算法分析15

本书在概念的描述、实例的选择、知识的前后衔接、内容的组织结构,以及教学内容的理解、教学目标的实现、教学意图的融入、教学方法的运用等方面进行了系统思考和统筹设计,力图通过本书为读者构建多层次的知识体系。在问题求解层面,给出“问题?想法?算法?程序”的思维模式;在算法设计层面,采用“阐述基本思想→伪代码描述算法→C语言实现算法”的过程模式;在算法分析层面,理解什么是“好”算法,给出算法分析的基本方法;在存储结构层面,通过存储示意图理解数据表示,再给出存储结构定义;在程序实现层面,给出所有数据结构的C程序实现以及使用举例;在数据结构和算法的运用层面,通过应用实例理解如何为求解问题设计适当的数据结构,如何基于数据结构设计算法,从而将数据结构、算法设计和程序实现有机地融合在一起。本书是一本难得的易学易教的好教材。