Data Structure Summary
此篇博客为数据结构的学习笔记总结，主要整理了一些重点考察内容。掌握程度主要分为以下三部分 一：背诵理解概念 二：掌握原理及运用 三：掌握算法及其设计；
博客末尾提供了PDF版的下载地址。
date: 2018-01-05 00:00:00
©RoseauHan
掌握程度主要分为以下三部分
一：背诵理解概念
二：掌握原理及运用
三：掌握算法及其设计
( 博客末尾提供了PDF版的下载地址。)
第一章 绪论
一、数据结构等
-
数据结构：给定数据对象及其上面的定义的操作（运算、关系）所形成的系统。
-
数据结构研究的内容：数据的逻辑关系、存储（物理）关系、运算关系。
-
常见的逻辑关系：线性结构、非线性结构（树、图）
-
常见的物理关系：顺序结构、链接结构、索引结构、散列结构。
-
数据结构评价的主要标准：时间效率（时间复杂度）、存储需要量（空间复杂度）
第二章 算法概述
一、算法描述、有效算法等
-
算法：解决某个问题的指令的有限指令集合，符合 “有穷性、确定性、可行性、输入输出” 等准则。
-
算法常见的描述方法：具体程序设计语言、自然语言、PDL语言、流程图。
-
算法设计准则：正确性、易读性、健壮性、高效性。
-
有效算法：以多项式时间为界限的算法称有效算法。
第三章 线性表
一、链表、静态链表等
-
线性表：一个线性表是n≥0个数据元素a1，a2，……，an的有限序列，序列中除第一个和最后一个以外，每个元素都有且仅有一个直接前趋和直接后继。
-
链表：通过指针联系起来的结点的整体。
-
表头结点：增加一个附加结点，放置于链表的最前面，也称头结点。
-
静态链表：以整型变量的值作为存储链表指针值（即地址）联系起来的结点的整体。
-
存储密度：数据本身所占存储量 / 整个结构所占存储量
三、单链表的插入删除
-
单链表表示
TYPE pointer = ↑ node ；
node = RECORD
data : datatype ;
next : pointer ;
END ;
-
链表中插入数据元素
具体框架：
PROC LinkList ( VAR H：link ; a，b ：datatype ) ;
BEGIN NEW( s ) : S↑.data ＝b；
CASE
H ＝ NIL : [ S↑.next nil ; H ← S] ;
H↑.data ＝ a : [ S↑.next H ; H ← S] ;
ELSE [ P ← H ;
WHILE ( P↑.data ≠ a ) and ( P↑.next ≠ nil ) DO
[ SAVE ← P ; P ← P↑.next ] ;
IF P↑.data ＝ a THEN [ S↑.next ← P ; SAVE ↑ next ← S ]
ELSE [ P↑.next ← S ; S↑.next ← nil ]
]
END CASE
END ;
第四章 栈和线性表
一、队列、假溢出等
-
栈：栈是一个下限为常数，上限可变化的向量（或者反之），也称为堆栈或堆阵；可变的一端为栈顶，不变化的一端为栈底。[后进先出]
-
队列：队列是一个下限和上限只能增加而不能减少的向量（或者反之）。取出元素的一端称队首，加入元素的一端称队尾。[先进先出]
-
线性表与栈异同：栈中的插入、删除操作只能在一端，不能在任意点；栈是受限的线性表。
-
线性表与队列异同：队列的插入、删除操作只能在特定的位置；队列是受限的线性表。
-
假溢出：当尾指针已经到了数组的上界，不能再有入队操作，但其实数组中还有空位置。
三、循环队列的出入队
若空间编址范围 m…n
存储结构定义实际上就是一个一维数组：
VAR CQ: Array [m..n] OFdatatype;
front,rear: integer;
（1）入队过程：
PROC AddQ(CQ, x, front, rear)
{front, rear 分别为队列CQ的首尾指针，数据元素 x 入队}
BEGIN rear←rear+1;
IF rear=n+1 THEN rear←m;
IF rear=front THEN write(“queue full”)
ELSE CQ[rear]←x
END;
（2）出队过程：
PROC DelQ(CQ, x, front, rear)
{front, rear 分别为队列CQ的首尾指针，进行出队运算}
BEGIN
IF rear=front THEN write(“queue empty”)
ELSE 【 IF front=n THEN front←m
ELSE front←front+1；
x ←CQ[front] 】
END;
第五章 串
一、串及串的模式匹配
-
串：一个由零个或多个字符组成的有穷序列称为串。
-
匹配：设有两个串P和S：
P= 'p1p2p3…pm'
S= 's1s2s3… sn '
其中0<m<n(通常m<<n),
在S中找出一个与P相同的子串,即子串的定位。
通常把S称为目标(或正文),把P称为模式，把从目标S中查找模式P的过程称为串的模式匹配。
第六章 数组和广义表
一、稀疏数组、广义表
- 数组：
-
一维数组是个向量，它的每个元素是该结构中不可分割的最小单元；
-
n维数组是个向量，它的每个元素是一个n-1维数组，且具有相同的下限和上限。
-
稀疏数组：在一个数组中和某元素比较而言，不相同的元素很少时，称此数组为稀疏数组。
-
稀疏矩阵：是稀疏数组的典例。
-
广义表：广义表是零个或多个原子或子表所组成的有限序列，一般简称为表（或列表）。
二、稀疏矩阵的存储表达
-
三元组：将矩阵的全部非零元素抽象为一个线性表，每个元素含行、列、值三个数据项。
元素结构：行-列-数据
-
十字链表：对于非零元素依据行、列特性,每一行和每一列建立一个循环链表。
第七章 树形结构
一、二叉树、遍历、线索树、霍夫曼树等
- 树：树是具有以下性质的有限个结点组成的非空集合。
-
树中有且只有一个称为根的结点
-
除根结点以外，其余结点分成m（m＞0）个不相关的集合T1,T2,…,Tm ，其中每个Ti都是树，而且都称为T的子树。
- 二叉树：二叉树是满足以下性质的结点的有限集合。
-
T是空集；
-
或者包含一个根结点，且其余结点分成两个不相交的集合，并分别被称为根结点的左子树和右子树。
-
遍历：对于给定数据结构，系统的访问该结构中的每个结点，且每个结点仅被访问一次的操作过程称为遍历。
-
二叉树的遍历规则：
-
层次策略（自上而下，从左到右）
-
深度策略（先中后/根 左右）
-
线索：将二叉树的空指针利用起来，用于表示某线性关系下前趋或后继时，这种指针称为线索。
-
线索化：给二叉树加线索的过程称为线索化。
-
线索树：带线索的二叉树称为线索二叉树，简称为线索树。
-
二叉排序树：二叉排序树或空二叉树，或者是满足以下要求的树、二叉树
-
若是它的左子树非空，则左子树上所有结点的值均小于根结点的值；
-
若是它的右子树非空，则右子树上所有结点的值均大于根结点的值；
-
左右子树也分别是二叉排序树；
-
没有键值相等的结点；
- 霍夫曼树：给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。
二、转换、遍历方法、加线索、霍夫曼树、二叉排序树
-
树转二叉树：
-
加线 ：兄弟结点间加虚线
-
抹线：只保留与长子的连线
-
调整：以根结点为轴心 （注意第一个孩子是结点的左孩子，兄弟转换过来的孩子是结点的右孩子）
-
-
二叉树还原树：
-
加线：左孩子的右链加线
-
抹线：划掉与右孩子间的线
-
调整：层次调整
-
-
森林转二叉树
-
树转换：将每棵树转为二叉树。
-
二叉树连接：保持第一颗二叉树不动，从第二棵二叉树开始，依次把后一颗二叉树的根结点作为前一颗二叉树的根结点的右孩子，用线连接起来。
-
-
二叉树还原森林
-
抹线：从根节点开始，若右孩子存在，则把与右孩子结点的连线删除。再查看分离后的二叉树，若其根节点的右孩子存在，则连线删除… 直到所有这些根节点与右孩子的连线都删除为止。
-
还原：将每棵分离后的二叉树转换为树。
-
-
二叉树的前中后三种遍历方法
-
给二叉树加线索
-
霍夫曼树及霍夫曼编码的构造
-
二叉排序树的构造
三、二叉树遍历方法的应用
-
交换二叉树的左右子树
PROC exchange （ VAR T ：Birary Tree）
BEGIN
IF T ≠ nil THEN [ swap （T.lson , T.rson）;
Call exchange ( T.lson )
Call exchange ( T.rson) ]
-
求二叉树的高度
-
采用一般过程进行设计
PROC high （ VAR T：Binary Tree ; h: integer）:
BEGIN
IF T ＝ nil THEN h ← 0
ELSE [ call high ( T.lson,nil ) ;
call high ( T.rson,nil ) ;
h ← H.max (h1, h2 ) ]
END ;
-
采用函数过程进行设计（最恰当）
FUNC high ( VAR T: Binary Tree )
BEGIN
IF T ＝ nil THEN high ← 0
ELSE high ← H.max (high(T.lson) , high(T.rson) )
END
-
统计二叉树的叶子结点个数
-
采用一般过程设计
PROC leave （VAR T ：Binary Tree）； L：integer）
BEGIN
IF T ＝ nil THEN L ← 0；
ELSE （IF T.lson）＝nil AND T.rson＝ nil THEN ；
ELSE [ Call leave (T.lson,l1)
Call leave (T.ron,l2)
L ← L1 ＋ L2 ；]
-
-
第八章 图结构
一、拓扑排序、关键路径、最小生成树
-
图：由n（n≥1）个结点V1,V2,…，Vn 构成的数据称为图。
-
图的遍历：给出图G和其中的任意一个顶点V0，从V0出发系统的访问G中所有的顶点，且每个顶点仅被访问一次，这一过程称为图的遍历。
-
图的遍历方法：
-
深度优先搜索(DFS,depth-first search)
搜索中，结点扩展的次序向某一个分支纵深推进，到底后再回溯。
-
广度优先搜索(BFS,breadth-first search)
搜索中，对所在层次的所有结点逐个依次进行扩展后，再推进到下一个层次进行扩展。
-
-
拓扑排序：
对于有向图G=(V,E),V中的顶点的线性序列(vi1, vi2, … , vin)，称作一个拓扑序列，若此结点序列满足如下条件：在G中从顶点u到顶点v有一条路径，则在序列中u必在v之前。
寻找拓扑序列的有效手段，就是进行拓扑排序。
-
AOV网：若有向图G中,顶点表示活动或任务,有向边表示活动或任务之间的优先关系,则此有向图称为顶点表示活动的网络。(AOV-网，Activity On Vertex Network)
-
AOE网：若在带权有向图中顶点表示事件，有向边表示活动，权表示活动持续的时间，则此有向图称为边表示活动的网络(AOE-网， Activity On Edge Network).
-
关键路径：任务计划作业图上的需要时间最长的路径(可有多条)。它决定完成总任务的时间。
-
最小生成树：可系统访问所有顶点，图的所有顶点，再加上遍历过程中经历的边所构成的子图实际上是一棵树，我们称做生成树。边的权值之和最小的生成树称为最小生成树。
二、图的存储、构造最小生成树
-
图的存储
-
邻接矩阵：表示顶点之间邻接关系的矩阵
-
邻接表：对图的每个顶点建立一个链表
-
-
构造最小生成树
-
Prim算法：每一步中都找出一个最小权的边
-
Kruskal算法：按照权值递增的顺序逐个考虑E中的每条边
-
第九章 排序
一、分类、稳定性、堆
-
排序：设含有n个记录的集合为R={r1,r2,…,rn},其对应的关键字集合为K={k1,k2,…,kn},给定关系a，按照关系a针对关键字集合K对R进行运算，使得R有如下序列: (ra1, ra2 ,…, ran)，我们将这个操作过程称为排序。
排序(又称分类)通常可以理解为：根据与项目中所包含的关键字或信息项的有关规则，对信息项目加以排列整理的动作过程。
-
排序的稳定性：在排序关系下，假设排序前ri在rj之前，排序之后领先关系不变，则称此排序过程和排序方法是稳定的，否则是不稳定的。
-
排序的分类：依据排序过程中数据所处位置，将排序分为内排序、外排序两大类。
-
堆：设L是长度为n的表，当1≤i≤ 【n/2】（向下取整） 时，其数据元素满足：
L(i)≤L(2i) 且 L(i)≤L(2i+1), 则称L是一个堆。
其中：将 L(1)称为堆顶
L(n)称为堆底
二、对一趟的掌握、堆的构造
-
对“一趟”的掌握
-
直接插入
将要排序的源文件F=R1,R2,…,Rn,视为两部分：
F1=R1; F2= R2,…,Rn
对F1和F2重复如下工作：
①从F2中取出一个记录Ri，并将Ri从F2中删除；
②将Ri插入到F1并使F1线性有序。
-
快速排序
(以下比较指关键的比较，关键字指排序关键字)
在待排序的n个记录中任取一个记录r(例如就取第1个)，作为轴心元素；
以r为标准将所有记录分为两组；
第1组中各记录的关键字都小于r的关键字；
第2组中各记录的关键字都大于r的关键字；
并把r排在这两组中间(最终位置),这一过程称为一趟快排。
然后对这两组分别重复上述方法，直到所有记录都排在应有位置上。
-
二路归并
如果文件中有n个记录，可将文件看成n个有序的子文件，这样就出现文件“部分有序”的状态；因而可以使用合并排序。
不过合并n个有序段，其操作较为复杂；
通常可以先将每两个子文件进行合并，得到n/2个部分有序的较大子文件，每个子文件含有两个记录；
再将这些子文件合并，如此反复，直到最后合并成一个文件时，排序就完成了；
-
基数排序
把每个关键字看成d元组：
Ki=(k1i ,k2i , … , kdi)
其中: C0≤kji≤Cr-1 (1≤i≤n, 1≤j≤d)
排序时先按kdi的值从小到大将记录分配到r个盒子中去，然后依次收集这些记录；
再按kid-1的值从小到大将记录分配到r个盒子，如此反复，直到对k1i的分配和收集后就得到完全有序的文件。
其中r称为基数, 执行基数排序时, 为了实现分配和收集，需设立r个队列。
-
-
堆的构造：插入建堆、删除建堆。
三、二分插入排序
也称折半插入排序。与直接插入排序的区别：在插入第i个时搜索采用二分策略。
仅对比较次数有改善，移动次数无影响。算法过程如下：
PROC DichSort(VARR:ARRAY[1..n] OF datatype);
BEGIN
FOR i←2 TO n DO
【x←R[i]; l←1; h←i-1;
while l≤h DO
【 m←(l+h) DIV 2;
IF x.key＜R[m].key THEN h←m-1
ELSE l←m+1 】 ;
FOR j←i-1 DOWNTO l DO R[j+1]←R[j] ;
R[l]←x】
END;
第十章 数据检索
一、AVL树、散列表等
-
检索：在给定数据结构中查找满足某种条件的数据元素（或结点，记录）的过程。
-
检索的分类：
-
性质（关键字、属性）
-
数据组织（线性、树形、散列）
-
-
平均检索长度：检索过程中对关键字(或属性)要执行的平均运算次数，即平均检索长度(ASL, Average Search Length)。
-
AVL树：
①一棵空二叉树是AVL-树；
②若T是一棵非空二叉树, 其任何结点的左、右子树的高度相差不超过1,则T是AVL-树。
-
散列表：散列表既是一种存储方法, 也是一种常见的检索方法。
散列法的基本思想：将关键字看成一个变量，通过一定的函数关系，将函数值解释为存储地址，将结点存入这样计算得到的地址单元中，检索的过程是存储过程的逆过程。
把用散列法组织存储的线性表称为散列表(hash table)。
-
碰撞：依据散列函数H计算出地址，若发现此地址已经被别的结点占用，即有两个或多个不同的关键字映射到了同一个地址空间的现象。
-
同义词：产生碰撞的两个或多个关键字称为同义词。
-
堆积：把两个同义词子表结合在一起的现象称为“堆积现象”或“群集现象”。
二、AVL树的构造
选择离插入(或删除)结点最近的不平衡结点(其平衡因子为±2)开始调整。
LL型:
RR型:
LR型:
RL型：
三、二分检索
二分检索的基本作法:
先取表的中间位置的记录关键字值与所给关键字值进行比较，如果给定值比该记录的关键字值大，则给定值必在表的后半部分；
在这后半部分中再取中间位置的记录进行比较，又可舍去这部分中的一半；
依次重复，直到找到或查完全表而查不到为止。
算法过程：
PROC dichotomize_search(VAR R:ARRAY[1..max] OF datatype;
n:integer;k:Ktype);
BEGIN low←1; high←n;
WHILE low≤high DO
【 middle←(low+high) DIV 2;
CASE
k＜R[middle].key : high←middle-1;
k=R[middle].key : 【write('success' , middle);exit; 】;
k＞R[middle].key : low←middle+1;
ENDCASE】 ;
write('unsuccess')
END;
第十二章 文件
一、组织分类、静动态索引、外排序等
-
文件：文件，为了进行存取控制、检索和修改而组织在一起的数据记录的集合。
-
逻辑组织分类：
-
字符流文件：有序的字符流序列，文件基本单位为字节或字。
-
记录文件：数据记录的集合，文件的基本单位为记录(定长或变长记录)。
-
-
物理组织分类：
-
顺序文件：按照数据到达的时间先后次序进行组织的文件。
-
散列文件：按照散列方式组织的文件。
-
索引文件：组织数据时需要带一个索引表。按该结构组织的文件。
-
-
静态索引结构：静态索引结构是指索引结构在文件创建，初始装入记录时生成，一旦生成就固定下来，在系统运行(例如插入/删除)过程中索引结构并不发生变化，只有当文件重组时才允许改变索引结构。
-
动态索引结构：动态索引结构是指文件创建，初始装入记录时所生成的索引结构，在系统运行(例如插入/删除)过程中索引结构本身也能够发生改变。
-
B- 树
作用：由于对B树的查找、插入、删除均始终能够保持B树的动态平衡，
本质：一种平衡的多分树。
B+树是B-树的变形,可以在叶结点存储关键字信息。
-
ISAM文件的本质：静态索引文件
-
VSAM文件的本质：动态索引文件
-
外排序的基本方法：合并排序（生成初始顺串、合并初始顺串）
PDF版下载点此
©RoseauHan @2018 - Jan
