《数据结构考研讲义》由会员分享，可在线阅读，更多相关《数据结构考研讲义（45页珍藏版）》请在金锄头文库上搜索。
1、-目录绪论30.1 基本概念3第一章线性表31.1 线性表的定义31.2 线性表的实现31.2.2 线性表的链式存储结构3第二章栈、队列和数组32.1 栈32.2 队列32.3 特殊矩阵的压缩存储32.3.1 数组32.3.2 特殊矩阵3第三章树与二叉树33.1 树的概念31.树的定义32相关术语33.2 二叉树33.2.1 定义与性质33.2.2 二叉树的存储33.2.3 二叉树的遍历33.2.4 线索二叉树33.3 树和森林33.3.1 树的存储结构33.3.2 森林和二叉树的转换33.3.3 树和森林的遍历33.4 哈夫曼（ Huffman）树和哈夫曼编码3第四章图34.1 图的概念34
2、.2 图的存储及基本操作34.2.1 邻接矩阵34.2.2 邻接表34.3 图的遍历34.3.1 深度优先搜索34.3.2 广度优先搜索34.4 图的基本应用34.4.1 最小生成树34.4.2 最短路径34.4.3 拓扑排序34.4.4 关键路径3第五章查找35.1 查找的基本概念35.2 顺序查找法35.3 折半查找法35.4 动态查找树表35.4.1 二叉排序树35.4.2 平衡二叉树35.4.3 B 树及其基本操作、 B+树的基本概念35.5 散列表35.5.2 常用的散列函数35.5.3 处理冲突的方法35.5.4 散列表的查找35.5.5 散列表的查找分析3第六章排序36.1 插入
3、排序36.1.1 直接插入排序36.1.2 折半插入排序36.2 冒泡排序36.3 简单选择排序36.4 希尔排序36.5 快速排序36.6 堆排序36.7 二路归并排序36.8 基数排序36.9 各种部排序算法的比较3绪论0.1 基本概念1、数据结构数据结构是指互相之间存在着一种或多种关系的数据元素的集合。数据结构是一个二元组 Data_Structure （ D， R），其中， D 是数据元素的有限集， R 是D 上关系的有限集。2、逻辑结构：是指数据之间的相互关系。通常分为四类结构：（ 1）集合：结构中的数据元素除了同属于一种类型外，别无其它关系。（ 2）线性结构：结构中的数据元素之间存
4、在一对一的关系。（ 3）树型结构：结构中的数据元素之间存在一对多的关系。（ 4）图状结构：结构中的数据元素之间存在多对多的关系。3、存储结构：是指数据结构在计算机中的表示，又称为数据的物理结构。通常由四种基本的存储方法实现：（ 1）顺序存储方式。数据元素顺序存放，每个存储结点只含一个元素。存储位置反映数据元素间的逻辑关系。存储密度大。但有些操作（如插入、删除）效率较差。（ 2）链式存储方式。每个存储结点除包含数据元素信息外还包含一组（至少一个）指针。指针反映数据元素间的逻辑关系。这种方式不要求存储空间连续，便于动态操作（如插入、删除等），但存储空间开销大（用于指针），另外不能折半查找等。（ 3
5、）索引存储方式。除数据元素存储在一组地址连续的存空间外，还需建立一个索引表，索引表中索引指示存储结点的存储位置（下标）或存储区间端点（下标）。（ 4）散列存储方式。通过散列函数和解决冲突的方法，将关键字散列在连续的有限的地址空间，并将散列函数的值解释成关键字所在元素的存储地址。其特点是存取速度快，只能按关键字随机存取，不能顺序存取，也不能折半存取。2 算法和算法的衡量1、算法是对特定问题求解步骤的一种描述，是指令的有限序列。其中每一条指令表示一个或多个操作。算法具有下列特性：有穷性确定性可行性输入输出。算法和程序十分相似，但又有区别。程序不一定具有有穷性，程序中的指令必须是机器可执行的，而算法
6、中的指令则无此限制。算法代表了对问题的解，而程序则是算法在计算机上的特定的实现。一个算法若用程序设计语言来描述，则它就是一个程序。2、算法的时间复杂度：以基本运算的原操作重复执行的次数作为算法的时间度量。一般情况下，算法中基本运算次数 T(n)是问题规模 n（输入量的多少，称之为问题规模）的*个函数f(n)，记作：T(n) (f(n)；也可表示 T(n) m(f(n)，其中 m 为常量。记号“O”读作“大 O”，它表示随问题规模 n 的增大，算法执行时间 T(n)的增长率和 f(n)的增长率相同。注意：有的情况下，算法中基本操作重复执行的次数还随问题的输入数据集不同而不同。常见的渐进时间复杂度
7、有：(1)(log2n)(n)(nlog2n)(n2)(n3)(2n) O(n!) O(nn)。3、算法的空间复杂度：是对一个算法在运行过程中临时占用的存储空间大小的量度。只需要分析除输入和程序之外的辅助变量所占额外空间。原地工作：若所需额外空间相对于输入数据量来说是常数，则称此算法为原地工作，空间复杂度为 O(1)。第一章线性表1.1 线性表的定义线性表是一种线性结构，在一个线性表中数据元素的类型是相同的，或者说线性表是由同一类型的数据元素构成的线性结构，定义如下：线性表是具有相同数据类型的n(n0)个数据元素的有限序列，通常记为：(a1， a2， ai-1， ai， ai+1，an)其中n
8、为表长， n0 时称为空表。需要说明的是： ai为序号为 i 的数据元素（ i=1,2,n），通常将它的数据类型抽象为ElemType， ElemType根据具体问题而定。1.2 线性表的实现1.2.1 线性表的顺序存储结构1.顺序表线性表的顺序存储是指在存中用地址连续的一块存储空间顺序存放线性表的各元素，用这种存储形式存储的线性表称其为顺序表。因为存中的地址空间是线性的，因此，用物理上的相邻实现数据元素之间的逻辑相邻关系是既简单又自然的。设a的存储地址为Loc(a)，每个数据元素占d个存储地址，则第i个数据元素的地址为：Loc(ai)=Loc(a)+(i-1)*d 1in这就是说只要知道顺序
9、表首地址和每个数据元素所占地址单元的个数就可求出第i个数据元素的地址来，这也是顺序表具有按数据元素的序号随机存取的特点。线性表的动态分配顺序存储结构：*define LIST_INIT_SIZE 100 /存储空间的初始分配量*define LISTINCREMENT 10 /存储空间的分配增量typedef structElemType *elem; /线性表的存储空间基址int length; /当前长度int listsize; /当前已分配的存储空间SqList;2.顺序表上基本运算的实现（ 1）顺序表的初始化顺序表的初始化即构造一个空表，这对表是一个加工型的运算，因此，将L设为引用参
10、数，首先动态分配存储空间，然后，将length置为0，表示表中没有数据元素。int Init_SqList (SqList &L)L.elem = (ElemType * )malloc(LIST_INIT_SIZE * sizeof(ElemType);if (!L.elem) e*it (OVERFLOW); /存储分配失败L.length=0;L. listsize = LIST_INIT_SIZE; /初始存储容量return OK;（ 2）插入运算线性表的插入是指在表的第i(i的取值围： 1in+1)个位置上插入一个值为 * 的新元素，插入后使原表长为 n的表:(a1， a2， .
11、， ai-1， ai， ai+1， . ， an)成为表长为 n+1 表:(a1， a2， .， ai-1， *， ai， ai+1， .， an ) 。顺序表上完成这一运算则通过以下步骤进行：将aian 顺序向下移动，为新元素让出位置；（注意数据的移动方向：从后往前依次后移一个元素）将 * 置入空出的第i个位置；修改表长。int Insert_SqList (SqList &L， int i， ElemType *)if (i L.length+1) return ERROR; / 插入位置不合法if (L.length = L.listsize) return OVERFLOW; / 当前
12、存储空间已满,不能插入/需注意的是，若是采用动态分配的顺序表，当存储空间已满时也可增加分配q = &(L.elemi-1); / q 指示插入位置for (p = &(L.elemL.length-1); p = q; -p)*(p+1) = *p; / 插入位置及之后的元素右移*q = e; / 插入e+L.length; / 表长增1return OK;顺序表上的插入运算，时间主要消耗在了数据的移动上，在第i个位置上插入 * ，从 ai 到an 都要向下移动一个位置，共需要移动 ni1个元素。（ 3）删除运算线性表的删除运算是指将表中第 i （ i 的取值围为： 1 in）个元素从线性表中
13、去掉，删除后使原表长为 n 的线性表：(a1， a2， . ， ai-1， ai， ai+1， .， an)成为表长为 n1 的线性表：(a1， a2， . ， ai-1， ai+1， . ， an)。顺序表上完成这一运算的步骤如下：将ai+1an 顺序向上移动；（注意数据的移动方向：从前往后依次前移一个元素）修改表长。int Delete_SqList (SqList &L;int i) if (i L.length) return ERROR; / 删除位置不合法p = &(L.elemi-1); / p 为被删除元素的位置e = *p; / 被删除元素的值赋给 eq = L.elem+L
14、.length-1; / 表尾元素的位置for (+p; p = q; +p)*(p-1) = *p; / 被删除元素之后的元素左移-L.length; / 表长减1return OK;顺序表的删除运算与插入运算相同，其时间主要消耗在了移动表中元素上，删除第i个元素时，其后面的元素 ai+1an 都要向上移动一个位置，共移动了 n-i 个元素，顺序表的插入、删除需移动大量元素 O(n)；但在尾端插入、删除效率高 O(1)。1.2.2 线性表的链式存储结构1.2.2.1 单链表1.链表表示链表是通过一组任意的存储单元来存储线性表中的数据元素的。为建立起数据元素之间的线性关系，对每个数据元素ai，除了存放数据
