自考数据结构笔记(超级详细可做考试条)

《自考数据结构笔记(超级详细可做考试条)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、资料自考数据结构笔记(详尽版)感谢热心自考人：liuii322笔记特点：图例丰富，超级详细，几乎涵盖本课程所有要求掌握的知识点，。。。用于复习和做小条概论-学习数据结构的意义5概论-算法的描述和分析(一)5线性表-链式存储结构-单链表的运算（一）14三栈和队列-栈-栈的定义及基本运算22三栈和队列-队列-队列的定义及基本运算25三栈和队列-队列-顺序队列25栈和队列-队列-链队列26三栈和队列-栈和队列的应用实例-栈的应用实例（一）27四—串的基本概念（一）30图-图的概念（一）63图-图的存储

2、结构-邻接矩阵表示法67图-图的遍历-深度优先遍历（一）72图-图的遍历-广度优先遍历（一）75图-生成树和最小生成树-生成树77图-生成树和最小生成树-最小生成树（一）79图-最短路径（一）82图-拓扑排序（一）84排序-排序基本概念（一）86排序-插入排序-直接插入排序（一）87排序-插入排序-直接插入排序（二）88排序-插入排序-希尔排序89排序-交换排序-冒泡排序（一）90排序-交换排序-快速排序（一）92排序-选择排序-堆排序（一）96排序-归并排序（一）98排序-分配排序-基数排序1

3、01排序-各种内部排序方法的比较和选择（一）102查找-查找的基本概念103查找-线性表的查找-顺序查找104查找-线性表的查找-二分查找（一）105查找-线性表的查找-分块查找107查找-树上的查找-二叉排序树（一）109查找-树上的查找-Ｂ－树114查找-散列技术-散列表的概念121查找-散列技术-散列函数的构造方法122文件-文件的基本概念（一）123文件-顺序文件125文件-索引文件（一）126文件-索引顺序文件-ISAM文件（一）127文件-索引顺序文件-VSAM文件（一）130文件-

4、散列文件131文件-多关键字文件-多重表文件132.资料文件-多关键字文件-倒排文件133概论--基本概念和术语数据：数据：指能够被计算机识别、存储和加工处理的信息载体。数据元素：就是数据的基本单位，在某些情况下，数据元素也称为元素、结点、顶点、记录。数据元素有时可以由若干数据项组成。数据结构：指的是数据之间的相互关系，即数据的组织形式。1．数据结构一般包括以下三方面内容：①数据元素之间的逻辑关系，也称数据的逻辑结构；　　数据的逻辑结构是从逻辑关系上描述数据，与数据的存储无关，是独立于计算机的。

5、数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。②数据元素及其关系在计算机存储器内的表示称数据的存储结构；③数据的运算，即对数据施加的操作。　　数据的运算定义在数据的逻辑结构上，每种逻辑结构都有一个运算的集合。最常用的检索、插入、删除、更新、排序等运算实际上只是在抽象的数据上所施加的一系列抽象的操作。（1）逻辑结构：表中每一行是一个数据元素(或记录、结点)，由学号、姓名等数据项组成。数据元素之间的逻辑关系是：对表中任一个结点，与它相邻且在它前面的结点称直接前趋最多只有一个；（2）存储结构：

6、该表的存储结构是指用计算机语言如何表示结点之间的这种关系，即表中的结点是顺序邻接地存储在一片连续的单元之中，还是用指针将这些结点链接在一起？2．数据的逻辑结构分类：逻辑结构简称为数据结构。（1）线性结构：逻辑特征是：若结构是非空集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。线性表,栈,队列,串等都是线性结构。（2）非线性结构：逻辑特征是：一个结点可能有多个直接前趋和直接后继。数组、广义表、树和图等数据结构都是非线性结构。3．数据的四种基本存储方法（1

7、）顺序存储方法：该方法把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构 ，通常借助程序语言的数组描述。该方法主要应用于线性的数据结构。非线性的数据结构也可通过某种线性化的方法实现顺序存储。（如数组）（2）链接存储方法：该方法不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系由附加的指针字段表示。由此得到的存储表示称链式存储结构,通常借助于程序语言的指针类型描述。（3）索引存储方法：该方法通常在储存结点信息的

8、同时，还建立附加的索引表。索引表由若干索引项组成。若每个结点在索引表中都有一个索引项，则该索引表称之为稠密索引。若一组结点在索引表中只对应一个索引项，则该索引表称为稀疏索引。索引项的一般形式是：(关键字、地址)关键字是能唯一标识一个结点的那些数据项。稠密索引中索引项的地址指示结点所在的存储位置；稀疏索引中索引项的地址指示一组结点的起始存储位置。（4）散列存储方法：根据结点关键字直接计算出该结点存储地址。四种存储方法可单独使用也可组合起来对数据结构进行存储映像。   同一逻辑结构采用不同的存储方法