大数据结构考研讲义.doc

word目录绪论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 树的概念20202．相关术语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第四章 图324.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.5.5 散列表的查找分析53第六章 排序546.1 插入排序546.1.1 直接插入排序546.1.2 折半插入排序546.2 冒泡排序556.3 简单项选择择排序566.4 希尔排序576.5 快速排序586.6 堆排序606.7 二路归并排序626.8 基数排序636.9 各种内部排序算法的比拟64绪论0.1 根本概念1、数据结构数据结构是指互相之间存在着一种或多种关系的数据元素的集合。

数据结构是一个二元组 Data_Structure ＝〔 D， R〕，其中， D 是数据元素的有限集， R 是D 上关系的有限集2、逻辑结构：是指数据之间的相互关系通常分为四类结构：〔 1〕集合：结构中的数据元素除了同属于一种类型外，别无其它关系〔 2〕线性结构：结构中的数据元素之间存在一对一的关系〔 3〕树型结构：结构中的数据元素之间存在一对多的关系〔 4〕图状结构：结构中的数据元素之间存在多对多的关系3、存储结构：是指数据结构在计算机中的表示，又称为数据的物理结构通常由四种根本的存储方法实现：〔 1〕顺序存储方式数据元素顺序存放，每个存储结点只含一个元素存储位置反映数据元素间的逻辑关系存储密度大但有些操作〔如插入、删除〕效率较差〔 2〕链式存储方式每个存储结点除包含数据元素信息外还包含一组〔至少一个〕指针指针反映数据元素间的逻辑关系这种方式不要求存储空间连续，便于动态操作〔如插入、删除等〕，但存储空间开销大〔用于指针〕，另外不能折半查找等〔 3〕索引存储方式除数据元素存储在一组地址连续的内存空间外，还需建立一个索引表，索引表中索引指示存储结点的存储位置〔下标〕或存储区间端点〔下标〕。

〔 4〕散列存储方式通过散列函数和解决冲突的方法，将关键字散列在连续的有限的地址空间内，并将散列函数的值解释成关键字所在元素的存储地址其特点是存取速度快，只能按关键字随机存取，不能顺序存取，也不能折半存取2 算法和算法的衡量1、算法是对特定问题求解步骤的一种描述，是指令的有限序列其中每一条指令表示一个或多个操作算法具有如下特性：⑴有穷性⑵确定性⑶可行性⑷输入⑸输出算法和程序十分相似，但又有区别程序不一定具有有穷性，程序中的指令必须是机器可执行的，而算法中的指令如此无此限制算法代表了对问题的解，而程序如此是算法在计算机上的特定的实现一个算法假设用程序设计语言来描述，如此它就是一个程序2、算法的时间复杂度：以根本运算的原操作重复执行的次数作为算法的时间度量一般情况下，算法中根本运算次数 T(n)是问题规模 n〔输入量的多少，称之为问题规模〕的某个函数f(n)，记作：T(n) ＝ Ο(f(n))；也可表示 T(n) ＝m(f(n))，其中 m 为常量记号“O〞读作“大 O〞，它表示随问题规模 n 的增大，算法执行时间 T(n)的增长率和 f(n)的增长率一样注意：有的情况下，算法中根本操作重复执行的次数还随问题的输入数据集不同而不同。

常见的渐进时间复杂度有：Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜Ο(2n) ＜O(n!) ＜O(nn)3、算法的空间复杂度：是对一个算法在运行过程中临时占用的存储空间大小的量度只需要分析除输入和程序之外的辅助变量所占额外空间原地工作：假设所需额外空间相对于输入数据量来说是常数，如此称此算法为原地工作，空间复杂度为 O(1)第一章 线性表1.1 线性表的定义线性表是一种线性结构，在一个线性表中数据元素的类型是一样的，或者说线性表是由同一类型的数据元素构成的线性结构，定义如下：线性表是具有一样数据类型的n(n≥0)个数据元素的有限序列，通常记为：(a1， a2， … ai-1， ai， ai+1， …an)其中n为表长， n＝0 时称为空表需要说明的是： ai为序号为 i 的数据元素〔 i=1,2,…,n〕，通常将它的数据类型抽象为ElemType， ElemType根据具体问题而定1.2 线性表的实现1.2.1 线性表的顺序存储结构线性表的顺序存储是指在内存中用地址连续的一块存储空间顺序存放线性表的各元素，用这种存储形式存储的线性表称其为顺序表因为内存中的地址空间是线性的，因此，用物理上的相邻实现数据元素之间的逻辑相邻关系是既简单又自然的。

设a１的存储地址为Loc(a１)，每个数据元素占d个存储地址，如此第i个数据元素的地址为：Loc(ai)=Loc(a１)+(i-1)*d 1≤i≤n这就是说只要知道顺序表首地址和每个数据元素所占地址单元的个数就可求出第i个数据元素的地址来，这也是顺序表具有按数据元素的序号随机存取的特点线性表的动态分配顺序存储结构：#define LIST_INIT_SIZE 100 //存储空间的初始分配量#define LISTINCREMENT 10 //存储空间的分配增量typedef struct{ElemType *elem; //线性表的存储空间基址int length; //当前长度int listsize; //当前已分配的存储空间}SqList;〔 1〕顺序表的初始化顺序表的初始化即构造一个空表， 这对表是一个加工型的运算， 因此， 将L设为引用参数，首先动态分配存储空间，然后，将length置为0，表示表中没有数据元素int Init_SqList (SqList &L){L.elem = (ElemType * )malloc(LIST_INIT_SIZE * sizeof(ElemType));if (!L.elem) exit (OVERFLOW); //存储分配失败L.length=0;L. listsize = LIST_INIT_SIZE; //初始存储容量return OK;}〔 2〕插入运算线性表的插入是指在表的第i(i的取值X围： 1≤i≤n+1)个位置上插入一个值为 x 的新元素，插入后使原表长为 n的表:(a1， a2， ... ， ai-1， ai， ai+1， ... ， an)成为表长为 n+1 表:(a1， a2， ...， ai-1， x， ai， ai+1， ...， an ) 。

顺序表上完成这一运算如此通过以下步骤进展：① 将ai～an 顺序向下移动，为新元素让出位置；〔注意数据的移动方向：从后往前依次后移一个元素〕② 将 x 置入空出的第i个位置；③ 修改表长int Insert_SqList (SqList &L， int i， ElemType x){if (i < 1 || i > L.length+1) return ERROR; // 插入位置不合法if (L.length >= L.listsize) return OVERFLOW; // 当前存储空间已满,不能插入//需注意的是，假设是采用动态分配的顺序表，当存储空间已满时也可增加分配q = &(L.elem[i-1]); // q 指示插入位置for (p = &(L.elem[L.length-1]); p >= q; --p)*(p+1) = *p; // 插入位置与之后的元素右移*q = e; // 插入e++L.length; // 表长增1return OK;}顺序表上的插入运算， 时间主要消耗在了数据的移动上， 在第i个位置上插入 x ， 从 ai 到an 都要向下移动一个位置，共需要移动 n－i＋1个元素。

〔 3〕删除运算线性表的删除运算是指将表中第 i 〔 i 的取值X围为 ： 1≤ i≤n〕个元素从线性表中去掉，删除后使原表长为 n 的线性表：(a1， a2， ... ， ai-1， ai， ai+1， ...， an)成为表长为 n－1 的线性表：(a1， a2， ... ， ai-1， ai+1， ... ， an)顺序表上完成这一运算的步骤如下：① 将ai+1～an 顺序向上移动；〔注意数据的移动方向：从前往后依次前移一个元素〕② 修改表长int Delete_SqList (SqList &L;int i) {if ((i < 1) || (i > L.length)) return ERROR; // 删除位置不合法p = &(L.elem[i-1]); // p 为被删除元素的位置e = *p; // 被删除元素的值赋给 eq = L.elem+L.length-1; // 表尾元素的位置for (++p; p <= q; ++p)*(p-1) = *p; // 被删除元素之后的元素左移--L.length; // 表长减1return OK;}顺序表的删除运算与插入运算一样，其时间主要消耗在了移动表中元素上，删除第i个元素时，其后面的元素 ai+1～an 都要向上移动一个位置，共移动了 n-i 个元素，顺序表的插入、删除需移动大量元素 O(n)；但在尾端插入、删除效率高 O(1)。

1.2.2 线性表的链式存储结构1.2.2.1 单链表链表是通过一组任意的存储单元来存储线性表中的数据元素的为建立起数据元素之间的线性关系，对每个数据元素ai，除了存放数据元素的自身的信息 ai 之外，还需要和ai一起存放其后继 ai+1 所在的存储单元的地址，这两局部信息组成一个“结点〞，结点的结构如下列图其中，存放数据元素信息的称为数据域，存放其后继地址的称为指针域因此n个元素的线性表通过每个结点的指针域拉成了一个“链〞，称之为链表因为每个结点中只有一个指向后继的指针，所以称其为单链表线性表的单链表存储结构C语言描述下：typedef struct LNode{ElemType。