《数据结构(c语言版)》资料

《《数据结构(c语言版)》资料》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一章绪论41.1数据结构讨论的范畴41.2基本概念51.3算法及其量度6本章小结7第二章线性表72.1线性表的抽象数据类型定义82.2线性表类型的实现——顺序映像82.3线性表类型的实现——链式映像82.4线性表的一个应用——一元多项式的表示9本章小结9第三章栈和队列103.1栈的类型定义103.2栈的应用举例113.3栈类型的实现123.4队列的类型定义133.5队列类型的实现13本章小结14第四章串144.1串的抽象数据类型的定义154.2串的表示和实现154.3串的模式匹配算法16本章小结16第五章数组和广义表175.1数组的类型定义175.2数组的顺序表示和实现175.3稀疏矩阵的

2、压缩存储185.4广义表的类型定义195.5广义表的表示方法19101/1015.6广义表操作的递归函数21本章小结21第六章树和二叉树226.1树的类型定义226.2二叉树的类型定义236.3二叉树的存储结构246.4二叉树的遍历256.5线索二叉树276.6树和森林的表示方法276.7树和森林的遍历296.8哈夫曼树与哈弗曼编码29本章小结30第七章图317.1抽象数据类型图的定义317.2图的存储结构327.3图的遍历337.4最小生成树357.5重（双）连通图和关节点357.6两点之间的最短路径问题367.7拓扑排序377.8关键路径38本章小结38第八章动态存储管理39第九章查找表

3、409.1静态查找表409.2动态查找表419.3哈希表43本章小结46第十章排序47101/10110.1概述4710.2插入排序4710.3快速排序4910.4堆排序5010.5归并排序5010.6基数排序5010.7各种排序方法的综合比较5310.8外部排序53本章小结54第十一章外部排序55第十二章文件5612.1有关文件的基本概念5612.2顺序文件5712.3索引文件5712.4索引顺序文件5712.5直接存储文件6012.6多关键字文件60本章小结61101/101第一章绪论1.1数据结构讨论的范畴数据结构讨论什么？简单的回答是数据结构是一门和程序设计密切相关的课程。有言：“算

4、法+数据结构=程序设计”。——美国计算机教授Wirth教授.程序设计：为计算机处理问题编制一组指令集——对某类信息进行处理算法：处理问题的策略——如何进行处理，即处理的策略数据结构：问题的数据模型——处理问题的信息如何表示任何程序设计问题都包含算法和数据结构两方面的问题，例如数值计算和非数值计算的程序设计问题数值计算的程序设计问题例，如根据地球上不同地方的重力值变化，要得到一个虽纬度高低不同重力值变化的线性方程。其数据模型就是该方程，计算机求解的问题即数学所要研究的问题。非数值计算的程序设计问题——现今计算机主要处理的问题例：编写一与计算机下棋的程序算法：下棋的规则和计算对棋手针对的策略模型

5、：棋盘棋子如何表示概括的说，数据结构讨论的是非数值性计算的程序设计问题现实世界实体的数学模型（非数值计算）及其上的操作在计算机中表示和实现。1.2基本概念数据与数据结构数据：所有能被输入到计算机中，且被计算机处理的符号的集合，计算机操作的对象的总称；是计算机处理的信息的某种特定的符号表示形式。数据元素：数据中的一个“个体”101/101，是数据结构中的讨论的基本单位。不是最小单位。课时简单的字符，或者是多个数据项。数据元素师数据项的集合数据项：数据结构中讨论的最小单位。——数据属性。若数据项中还有数据则该数据项被称为组合项。例：运动员（数据元素），姓名、出生日期(年月日)（组合项）、籍贯等（

6、数据项）。数据结构：带结构的数据元素的集合。结构，数据元素之间存在的关系。次序关系等。数据元素之间的关系——数据的逻辑关系，主要有四类：线性结构树形结构图形结构集合结构以后将讨论的数体结构为以上两种。数据结构的形式定义是一个二元组（D，S），D是元素的有限集，S是关系的有限集。只说明里数据结构的一方面，强调的是数据结构中逻辑关系。另一重要的方面是数据的存储结构。也就是怎样在计算机中表示数据的逻辑结构。存储结构就是逻辑结构在计算机中的表示。数据元素的表示：二进制位的位串表示。关系的表示：有序对关系集合表示。有序对在计算机中的表示方法：顺序印象：一个接一个，位置固定，有顺序。链式印象：位置随意，

7、则需要一信息表示其联系——指针。指向其所联系的元素的位置，使之联系在一起。数据类型：一个值的集合和定义在此集合上的一组操作的总称。抽象数据类型（ADT）：一个数据模型以及定义在此数据模型上的一组操作。特征：数据抽象和数据封装。描述方法：用一三元组（D，S，P），D元素集，S关系集，P基本操作集。（基本操作的参数，一、赋值参数，只为操作提供输入值；二、引用参数，即可提供输入值，还将返回操作的结果）表现和实现：用