《自考数据结构笔记(超级详细可做考试条)》由会员分享,可在线阅读,更多相关《自考数据结构笔记(超级详细可做考试条)(86页珍藏版)》请在金锄头文库上搜索。
1、 .自考数据结构笔记(详尽版) 感谢热心自考人:liuii322 笔记特点:图例丰富,超级详细,几乎涵盖本课程所有要求掌握的知识点,。用于复习和做小条概论- 学习数据结构的意义5概论- 算法的描述和分析(一)5线性表 - 链式存储结构- 单链表的运算(一)14三 栈和队列 - 栈 - 栈的定义及基本运算22三栈和队列 - 队列 - 队列的定义及基本运算25三栈和队列 - 队列 - 顺序队列25栈和队列 - 队列 - 链队列26三栈和队列 - 栈和队列的应用实例 - 栈的应用实例(一)27四串的基本概念(一)30图 - 图的概念(一)63图 - 图的存储结构 - 邻接矩阵表示法67图 - 图的遍
2、历 - 深度优先遍历(一)72图 - 图的遍历 - 广度优先遍历 (一)75图 - 生成树和最小生成树 - 生成树77图 - 生成树和最小生成树 - 最小生成树(一)79图 - 最短路径 (一)82图 - 拓扑排序 (一)84排序 - 排序基本概念 (一)86排序 - 插入排序 - 直接插入排序(一)87排序 - 插入排序 - 直接插入排序(二)88排序 - 插入排序 - 希尔排序89排序 - 交换排序 - 冒泡排序(一)90排序 - 交换排序 - 快速排序 (一)92排序 - 选择排序 - 堆排序(一)96排序 - 归并排序(一)98排序 - 分配排序 - 基数排序101排序 - 各种内部排
3、序方法的比较和选择(一)102查找 - 查找的基本概念103查找-线性表的查找-顺序查找104查找 - 线性表的查找 - 二分查找(一)105查找 - 线性表的查找 - 分块查找107查找 - 树上的查找 - 二叉排序树(一)109查找 - 树上的查找 - 树114查找 - 散列技术 - 散列表的概念121查找 - 散列技术 - 散列函数的构造方法122文件 - 文件的基本概念(一)123文件 - 顺序文件125文件 - 索引文件(一)126文件 - 索引顺序文件 - ISAM文件(一)127文件 - 索引顺序文件 - VSAM文件 (一)130文件 - 散列文件131文件 - 多关键字文件
4、- 多重表文件132文件 - 多关键字文件 - 倒排文件133概论-基本概念和术语数据:数据:指能够被计算机识别、存储和加工处理的信息载体。数据元素:就是数据的基本单位,在某些情况下,数据元素也称为元素、结点、顶点、记录。数据元素有时可以由若干数据项组成。数据结构:指的是数据之间的相互关系,即数据的组织形式。1数据结构一般包括以下三方面内容: 数据元素之间的逻辑关系,也称数据的逻辑结构;数据的逻辑结构是从逻辑关系上描述数据,与数据的存储无关,是独立于计算机的。数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。 数据元素及其关系在计算机存储器内的表示称数据的存储结构; 数据的运算,即对数据施
5、加的操作。数据的运算定义在数据的逻辑结构上,每种逻辑结构都有一个运算的集合。最常用的检索、插入、删除、更新、排序等运算实际上只是在抽象的数据上所施加的一系列抽象的操作。(1)逻辑结构:表中每一行是一个数据元素(或记录、结点),由学号、姓名等数据项组成。数据元素之间的逻辑关系是:对表中任一个结点,与它相邻且在它前面的结点称直接前趋最多只有一个; (2)存储结构:该表的存储结构是指用计算机语言如何表示结点之间的这种关系,即表中的结点是顺序邻接地存储在一片连续的单元之中,还是用指针将这些结点链接在一起?2数据的逻辑结构分类:逻辑结构简称为数据结构。 (1)线性结构:逻辑特征是:若结构是非空集,则有且
6、仅有一个开始结点和一个终端结点,并且所有结点都最多只有一个直接前 趋和一个直接后继。 线性表,栈,队列,串等都是线性结构。(2)非线性结构:逻辑特征是:一个结点可能有多个直接前趋和直接后继。数组、广义表、树和图等数据结构都是非线性结构。 3数据的四种基本存储方法(1)顺序存储方法:该方法把逻辑上相邻的结点存储在物理位置上相邻的存储单元里,结点间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构,通常借助程序语言的数组描述。该方法主要应用于线性的数据结构。非线性的数据结构也可通过某种线性化的方法实现顺序存储。(如数组)(2)链接存储方法:该方法不要求逻辑上相邻的结点在物理位
7、置上亦相邻,结点间的逻辑关系由附加的指针字段表示。由此得到的存储表示称链式存储结构,通常借助于程序语言的指针类型描述。(3)索引存储方法:该方法通常在储存结点信息的同时,还建立附加的索引表。 索引表由若干索引项组成。若每个结点在索引表中都有一个索引项,则该索引表称之为稠密索引。若一组结点在索引表中只对应一个索引项,则该索引表称为稀疏索引。索引项的一般形式是:(关键字、地址)关键字是能唯一标识一个结点的那些数据项。稠密索引中索引项的地址指示结点所在的存储位置;稀疏索引中索引项的地址指示一组结点的起始存储位置。(4)散列存储方法:根据结点关键字直接计算出该结点存储地址。 四种存储方法可单独使用也可
8、组合起来对数据结构进行存储映像。 同一逻辑结构采用不同的存储方法,可以得到不同的存储结构。4数据结构三方面的关系:数据的逻辑结构、存储结构及数据的运算这三方面是一个整体。存储结构是数据结构不可缺少的一个方面:同一逻辑结构的不同存储结构可冠不同数据结构名称来标识。 【例】线性表是一种逻辑结构,用顺序方法的存储表示,称其为顺序表;用链式存储方法,称为链表;用散列存储方法,称为散列表。数据的运算也是数据结构不可分割的一个方面。在给定了数据的逻辑结构和存储结构之后,按定义的运算集合及其运算的性质不同,也可能导致完全不同的数据结构。数据类型:是一个值的集合以及在这些值上定义的一组操作的总称。通常数据类型
9、可以看作是程序设计语言中已实现的数据结构。按值是否可分解,可将数据类型划分为两类:原子类型:其值不可分解。通常是由语言直接提供。结构类型:其值可分解为若干个成分(或称为分量)。抽象数据类型(简称ADT):是指抽象数据的组织和与之相关的操作。可以看作是数据的逻辑结构及其在逻辑结构上定义的操作。抽象数据类型可以看作是描述问题的模型,它独立于具体实现。它的优点是将数据和操作封装在一起,使得用户程序只能通过在ADT里定义的某些操作来访问其中的数据,从而实现信息隐藏。ADT和类的概念实际上反映了程序或软件设计的两层抽象:ADT相当于是在概念层(或称为抽象层)上描述问题,而类相当于是在实现层上描述问题。不
10、采用ADT的形式来描述数据结构 概论- 学习数据结构的意义1 计算机处理问题的分类 (1)数值计算问题 (2)非数值性问题 2非数值问题求解 瑞士计算机科学家沃思教授曾提出: 算法+数据结构=程序 数据结构是数据的逻辑结构和存储结构,算法是对数据运算的描述 概论- 算法的描述和分析(一) 数据的运算通过算法(Algorithm)描述 1算法 :非形式地说,算法是任意一个良定义的计算过程。它以一个或多个值作为输入,并产生一个或多个值作为输出。(1)一个算法可以被认为是用来解决一个计算问题的工具。 (2)一个算法是一系列将输入转换为输出的计算步骤。 2算法的描述 ;一个算法可以用自然语言、计算机程
11、序语言或其它语言来说明,惟一的要求是该说明必须精确地描述计算过程。 描述算法最合适的语言是介于自然语言和程序语言之间的伪语言。算法分析 算法分析的目的是(评价算法的效率)1评价算法好坏的标准:首先应是正确的。此外主要考虑三点: 执行算法所耗费的时间;执行算法所耗费的存储空间,主要考虑辅助存储空间;算法应易于理解,易于编码,易于调试等。 算法的效率分为时间效率和空间效率真3算法的时间性能分析 (1)算法所耗费的时间=算法中每条语句的执行时间之和 每条语句的执行时间=语句的执行次数(即频度)语句执行一次所需时间的乘积。【例】求两个n阶方阵的乘积 C=AB,其算法如下: # define n 100
12、 / n 可根据需要定义,这里假定为100 void MatrixMultiply(int Aa,int B nn,int Cnn) int i ,j ,k; (1) for(i=0; in;j+) n+1 (2) for (j=0;jn;j+) n(n+1) (3) Cij=0; n 2 (4) for (k=0; kn; k+) n 2 (n+1) (5) Cij=Cij+Aik*Bkj; n 3 该算法中所有语句的频度之和为: T(n)=2n 3 +3n 2 +2n+1 分析:算法MatrixMultiply的时间耗费T(n)是矩阵阶数n的函数。 (2)问题规模和算法的时间复杂度 算法求
13、解问题的输入量称为问题的规模(Size),用一个整数表示。 【例】一个图论问题的规模则是图中的顶点数或边数。 一个算法的时间复杂度(也称时间复杂性)T(n)是该算法的时间耗费,是该算法所求解问题规模n的函数。当问题的规模n趋向无穷大时,时间复杂度T(n)的数量级(阶)称为算法的渐进时间复杂度。 【例3】算法MatrixMultidy的时间复杂度T(n)如(1.1)式所示,当n趋向无穷大时,显然有 当n充分大时,T(n)和n 3 之比是一个不等于零的常数。即T(n)和n 3 是同阶的,或者说T(n)和n 3 的数量级相同。记作T(n)=O(n 3)是算法MatrixMultiply的渐近时间复杂
14、度。 数学符号O的严格的数学定义: 若T(n)和f(n)是定义在正整数集合上的两个函数,则T(n)=O(f(n)表示存在正的常数C和n0,使得当nn0时都满足0T(n)Cf(n)。 (3)渐进时间复杂度评价算法时间性能 :主要用算法时间复杂度的数量级(即算法的渐近时间复杂度)评价一个算法的时间性能。 将渐近时间复杂度T(n)=O(f(n)简称为时间复杂度,其中的f(n)一般是算法中频度最大的语句频度。 当有若干个循环语句时,算法的时间复杂度由嵌套层数最多的循环语句中最内层语句的频度f(n)决定的。 (4)算法的时间复杂度不仅仅依赖于问题的规模,还与输入实例的初始状态有关。 【例312】在数值A0.n-1中查找给定值K的算法大致如下: (1)i=n-1; (2)while(i=0&(Ai!=k) (3) i-; (4)return i; 此算法中的语句(3)的频度不仅与问题规模n有关,还与输入实例中A的各元素取值及K的取值有关: 若A中没有与K相等的元素,则语句(3)的频度f(n)=n; 若A的最后一个元素等于K,则语句(3)的频度f(n)是常数0。 (5) 平均时间复杂度是指所有可能的输入实例均以等