数据结构考研讲义

《数据结构考研讲义》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、目录绪论30.1基本概念3第一章线性表41.1线性表的定义41.2线性表的实现41.2.2线性表的链式存储结构6第二章栈、队列和数组112.1栈112.2队列152.3特殊矩阵的压缩存储172.3.1数组172.3.2特殊矩阵17第三章树与二叉树203.1树的概念201.树的定义202．相关术语203.2二叉树213.2.1定义与性质213.2.2二叉树的存储223.2.3二叉树的遍历233.2.4线索二叉树253.3树和森林293.3.1树的存储结构293.3.2森林和二叉树的转换303.3.3树和森林的遍历303.4哈夫曼（Huffman）树和哈夫曼编码31第四章图

2、32894.1图的概念324.2图的存储及基本操作334.2.1邻接矩阵334.2.2邻接表334.3图的遍历354.3.1深度优先搜索354.3.2广度优先搜索354.4图的基本应用374.4.1最小生成树374.4.2最短路径374.4.3拓扑排序394.4.4关键路径40第五章查找425.1查找的基本概念425.2顺序查找法435.3折半查找法445.4动态查找树表455.4.1二叉排序树455.4.2平衡二叉树475.4.3B树及其基本操作、B+树的基本概念495.5散列表515.5.2常用的散列函数515.5.3处理冲突的方法525.5.4散列表的查找525.

3、5.5散列表的查找分析53第六章排序546.1插入排序546.1.1直接插入排序54896.1.2折半插入排序546.2冒泡排序556.3简单选择排序566.4希尔排序576.5快速排序586.6堆排序606.7二路归并排序626.8基数排序636.9各种内部排序算法的比较6489绪论0.1基本概念1、数据结构数据结构是指互相之间存在着一种或多种关系的数据元素的集合。数据结构是一个二元组Data_Structure＝（D，R），其中，D是数据元素的有限集，R是D上关系的有限集。2、逻辑结构：是指数据之间的相互关系。通常分为四类结构：（1）集合：结构中的数据元素除了同属于

4、一种类型外，别无其它关系。（2）线性结构：结构中的数据元素之间存在一对一的关系。（3）树型结构：结构中的数据元素之间存在一对多的关系。（4）图状结构：结构中的数据元素之间存在多对多的关系。3、存储结构：是指数据结构在计算机中的表示，又称为数据的物理结构。通常由四种基本的存储方法实现：（1）顺序存储方式。数据元素顺序存放，每个存储结点只含一个元素。存储位置反映数据元素间的逻辑关系。存储密度大。但有些操作（如插入、删除）效率较差。（2）链式存储方式。每个存储结点除包含数据元素信息外还包含一组（至少一个）指针。指针反映数据元素间的逻辑关系。这种方式不要求存储空间连续，便于动态

5、操作（如插入、删除等），但存储空间开销大（用于指针），另外不能折半查找等。（3）索引存储方式。除数据元素存储在一组地址连续的内存空间外，还需建立一个索引表，索引表中索引指示存储结点的存储位置（下标）或存储区间端点（下标）。（4）散列存储方式。通过散列函数和解决冲突的方法，将关键字散列在连续的有限的地址空间内，并将散列函数的值解释成关键字所在元素的存储地址。其特点是存取速度快，只能按关键字随机存取，不能顺序存取，也不能折半存取。2算法和算法的衡量1、算法是对特定问题求解步骤的一种描述，是指令的有限序列。其中每一条指令表示一个或多个操作。算法具有下列特性：⑴有穷性⑵确定性⑶

6、可行性⑷输入⑸输出。算法和程序十分相似，但又有区别。程序不一定具有有穷性，程序中的指令必须是机器可执行的，而算法中的指令则无此限制。算法代表了对问题的解，而程序则是算法在计算机上的特定的实现。一个算法若用程序设计语言来描述，则它就是一个程序。892、算法的时间复杂度：以基本运算的原操作重复执行的次数作为算法的时间度量。一般情况下，算法中基本运算次数T(n)是问题规模n（输入量的多少，称之为问题规模）的某个函数f(n)，记作：T(n)＝Ο(f(n))；也可表示T(n)＝m(f(n))，其中m为常量。记号“O”读作“大O”，它表示随问题规模n的增大，算法执行时间T(n)的增

7、长率和f(n)的增长率相同。注意：有的情况下，算法中基本操作重复执行的次数还随问题的输入数据集不同而不同。常见的渐进时间复杂度有：Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜Ο(2n)＜O(n!)＜O(nn)。3、算法的空间复杂度：是对一个算法在运行过程中临时占用的存储空间大小的量度。只需要分析除输入和程序之外的辅助变量所占额外空间。原地工作：若所需额外空间相对于输入数据量来说是常数，则称此算法为原地工作，空间复杂度为O(1)。89第一章线性表1.1线性表的定义线性表是一种线性结构，在一个线性表中数据