数据结构复习

已学习的数据结构：

线性表、栈、队列、串、数组、广义表、树、图和散列表

其中：\r\n 栈、队列和串是特殊的线性表\r\n 数组和广义表是广义的线性表\r\n 树和图是非线性的数据结构\r\n 散列表是一种查找数据结构

还学习了在实际应用中应用广泛的查找技术、排序技术

各章重点：

第 1 章绪论

数据结构定义：数据结构（data structure）是指相互间存在一定关系的数据元素的集合。或数据结构是研究非数值问题中计算机的操作对象以及它们之间的关系和操作的学科。

数据结构中的基本术语：\r\n数据元素--数据的基本单位\r\n数据项--是构成数据元素的不可再分的最小单位\r\n数据对象--是具有相同性质的数据元素的集合\r\n数据的逻辑结构--是数据元素间逻辑关系的整体\r\n存储结构--是数据及其逻辑结构在计算机中的物理表示。

数据的逻辑结构和存储结构的关系：

1）数据的逻辑结构是数据的机外表示，数据的存储结构是数据的机内表示。\r\n2）一种逻辑结构可以用多种存储结构来实现。\r\n3）数据的基本操作是定义于逻辑结构，实现于存储结构。\r\n4）采用不同的存储结构，其数据处理的方法和效率往往是不同的。

访问接口：操作的调用形式与规范\r\n数据结构的访问接口：数据结构基本操作接口的全体。

数据类型（data type）是一组值的集合以及定义于这个值集上的一组操作的总称\r\n抽象数据类型（Abstract Data Type，ADT）:一个数据结构以及定义在该结构上的一组操作的总称。\r\n抽象数据类型的定义形式:ADT=

算法（algorithm）是对特定问题求解的一种描述，是指令的有限序列。

算法的五大特征:

⑴ 输入\r\n ⑵ 输出\r\n ⑶ 有穷性\r\n ⑷ 确定性\r\n ⑸ 可行性

算法的描述:\r\n 1）自然语言 \r\n 2）高级语言\r\n 3）伪代码\r\n 4） N-S图

算法分析:

“好”的算法至少应该满足以下几个条件\r\n 1）正确性\r\n 2）容错性\r\n 3）可读性\r\n 4）分级性\r\n 5）高效性*

算法的时间复杂度:刻画的是算法的运行时间

算法的空间复杂度:主要对算法的执行过程中需要用到的辅助空间的度量。

算法的时间复杂度和空间复杂度都用渐近阶来表示。\r\n 通常用O来表示：T(n) =O(f(n))\r\n S(n)=O(f(n))

第 2 章线性表

线性表的定义：线性表（linear list）也简称表。是n(n ≥ 0)个具有相同数据类型的数据元素的有限序列。\r\n L＝（a1, a2 , …, ai-1, ai , …, an)

线性表的几个术语：\r\n表长：线性表中的元素个数；\r\n空表：元素个数为零的线性表，常表示为L=（）；\r\n前驱与后继：a1无前驱, an无后继,其他元素有且仅有一个前驱和一个后继；

性线表特征：\r\n 顺序性、有限性、相同性、抽象性

线性表的顺序存储结构---顺序表\r\n 顺序表是高级语言（C 语言)的一维数组

int MaxSize; //存储表的允许长度\r\n int length; //存储表的实际长度\r\n T *data; //存储数组的初地址

主要函数（操作）说明：所有的操作都设计为函数（C 语言），不要求用C 的类\r\n构造顺序表: SeqList（a,n,m）--构造长为m，并从数组a\r\n 复制n个数据的表\r\n输出顺序表: PrintList（）\r\n顺序表插入: void Insert(int i,T x)\r\n顺序表删除: T Delete(int i)\r\n顺序表查找: T Get(int i) int Locate(T x)

顺序表的优点：\r\n ⑴ 无需为表示表中元素之间的逻辑关系而增加额外的存储空间；\r\n ⑵ 随机存取：可以快速地存取表中任一位置的元素

顺序表的缺点：\r\n ⑴表的容量难以确定，表的容量难以扩充；\r\n ⑵插入和删除操作需要移动大量元素；\r\n ⑶ 造成存储空间的碎片。

线性表的链接存储结构—单链表\r\n 单链表是高级语言（C 语言)的指针

单链表是使用一组任意的内存单元来存储线性表的数据元素，线性表中的逻辑关系是通过指针来表示的。

结点结构:\r\n struct Node\r\n { T data;\r\n Node*next; \r\n };

三种单链表：

头指针

first

带头结点的单链表：

循环单链表：

rear

一般单链表：

双链表：

templatestruct DulNode\r\n { T data; \r\n DulNode*prior; \r\n DulNode*next;\r\n }

在双向循环链表中求表长，按位置查找等操作与单链表基本相同，不同的是插入和删除操作。由于它是对称结构，使得插入和删除操作都很容易。

也分一般双链表、带头结点的单链表、循环单链表

要求掌握插入和删除指定结点的指针修改的相对顺序

主要函数（操作）说明：所有的操作都设计为函数（C＋＋语言），不要求用C 的类\r\n构造单链表: LinkList(T a[],int n) --构造长为n，并从数组\r\n a复制n个数据的单链表,分头插法和尾插法\r\n输出单链表: PrintList（）\r\n单链表插入: void Insert(int i, T x); //按位置插入（前后）\r\n void Insert(T y, T x); //\r\n单链表删除: T Delete(int i); //按位置删除\r\n T Delete(T x); //\r\n单链表查找: T Get(int i) //按位置查找\r\n Node* Locate(T x ); //按值查找并返回指\r\n 定元素的地址

对线性表，特别是单链表要求掌握相关操作的算法设计

比如：1、查找指定元素的结点按要求插入或删除\r\n 2、将单链表或循环单链表按要求拆分为两个链表\r\n 3、将两个单链表或循环单链表按要求合并为一个链表

第 3 章栈、队列和串

1.栈的定义\r\n 栈（stack）是限在表尾进行插入和删除操作的线性表。允许进行插入和删除操作的一端叫栈顶，另一端称为栈底。后进先出性(last in first out)

顺序栈和链栈

主要函数（操作）：\r\n Stack S //定义栈S\r\n S.Push(r) //r入栈\r\n r=S.Pop() //出栈->r\r\n !S.Empty(); //判断栈空否

第 3 章栈、队列和串

2.队列的定义\r\n 队列（queue）也是特殊的线性表，它的插入和删除分别在线性表的两端分别进行。允许插入的一端叫队尾，删除的一端则称作队首。

循环顺序队列和链接队

主要函数（操作）：\r\n Queue Q ; //定义队Q\r\n Q.Enqueue(d) ; //d入队\r\n d=Q.Dequeue(); //出队->d\r\n !Q.Empty(); //判断队空否

第 3 章栈、队队列和串

对栈和队要求掌握：\r\n 1、模块化引用\r\n 2、操作特性\r\n 3、栈顶和栈底、队首和队尾\r\n 4、循环顺序队的队空和队满的条件\r\n 5、顺序栈两栈共享的栈满和栈空的条件

第 3 章栈、队列和串

3. 串的定义\r\n串（string）也是特殊的线性表，它是由字符构成的线性表。也就是字符序列，通常记为：\r\n S= "s1s2s3s4…sn"

串的几个术语：\r\n 空串：不含字符的串 "" \r\n 空格串：仅含空格字符的串 " "\r\n 串长：串中含有字符的个数\r\n 子串/母串：子串包含在母串中\r\n 子串在母串的位置：子串在母串的起始位置

串的操作：\r\n 主要是关注串的整体性的操作。比如，串的比较，子串的定位，插入，更新等。

⑴ StrLength (s)：求串s的长度。\r\n⑵ StrAssign (s1, s2)：赋值，将s2的值赋值给串s1。\r\n⑶ StrConcat (s1, s2, s)：连接，将串s2放在串s1的后面连接成一个新串s。\r\n⑷ SubStr (s, i, len)：求子串，返回从串s的第i个字符开始取长为 len 的子串。\r\n⑸ StrCmp (s1, s2)：串比较，若s1=s2，返回0；若s1s2, 返回1

模式匹配：在主串中定位子串位置的过程称为模式匹配（子串也称为模式串）

第 4 章广义线性表—多维数组和广义表

1.数组的定义\r\n数组（array）是由类型相同的数据元素构成的有序集合，每个数据元素称为数组元素（简称元素），每个元素受n(n≥1)个线性关系的约束，每个元素在n个线性关系中的序号i1,i2,…in称为该元素的下标，并称该数组为n维数组。

数组采用存储结构是顺序存储结构

用顺序存储结构来存储多维数组需要解决多维结构到一维结构的映射问题。

二维数组的映射方式：按行优先和按列优先\r\n三维数组A[n1][n2][n3]按高位优先存储的原则，先存储第0页，再存储第1页，再存储……，最后存储第n1-1页。

第 4 章广义线性表—多维数组和广义表

数组的寻址方式:

一维数组的存储方式及寻址方式:\r\n LOC(ai)= LOC(a0) i*c \r\n c为每个元素占用的内存单元数

二维数组的寻址方式:\r\n按行优先存储时的寻址方式为：\r\n LOC(aij)= LOC(a00) (i*n j)*c\r\n按列优先存储时的寻址方式为:\r\n LOC(aij)= LOC(a00) ( j*m i )*c

第 4 章广义线性表—多维数组和广义表

三维数组的存储与寻址方式:\r\n LOC(aijk)= LOC(a000) ( i*n2*n3 j*n3 k )*c

对称矩阵的寻址方式: sak = aij

i*(i 1)/2 j 当 i≥j时

j*(j 1)/2 i 当 i < j时

下三角矩阵的寻址方式: sak = aij

i*(i 1)/2 j 当 i≥j时

n*(n 1)/2 当 i < j时

第 4 章广义线性表—多维数组和广义表

上三角矩阵的寻址方式: sak = aij

三对角阵An按主对角线压缩存储到一维数组SA3n中，具体的寻址方式是：

(2*n-i 1)*i/2 j-i 当 j≥i时

n*(n 1)/2 当 j < i 时

sa(j-i 1)*n i |i-j|<2）时< p="">

0 |i-j|>1）时

aij=

第 4 章广义线性表—多维数组和广义表

三对角阵An按按行压缩存储到一维数组SA3n中，具体的寻址方式是：

sa2*i j |i-j|<2）时< p="">

0 |i-j|>1）时

aij=

稀疏矩阵压缩存储: 三元组表\r\nstruct element\r\n { \r\n int row, col; //行号，列号\r\n T item //非零元素值\r\n };

第 4 章广义线性表—多维数组和广义表

广义表：n（n≥0）个数据元素的有限序列，记作：\r\n LS＝(a1，a2，……，an)\r\n其中：LS是广义表的名称，ai（1≤i≤n）是LS的成员（或直接元素），它可以是单个的数据元素，也可以是一个广义表，分别称为LS的单元素（或原子）和子表。

广义表的两个重要操作：取头元素和取表尾操作

.广义表的存储结构:

子表

原子

.要求会画出广义表的存储结构示意图:

第 5 章树和二叉树

1、树的定义\r\n 树(tree)是n（n≥0）个结点的有限集合。当n＝0时，称为空树；任意一棵非空树满足以下条件：\r\n ⑴当n=1时，有且仅有一个特定的称为根的结点；\r\n ⑵ 当n＞1时，除根结点之外的其余结点被分成m（m>0）个互不相交的有限集合T1,T2,… ,Tm，其中每个集合又是一棵树，并称为这个根结点的子树。

树的定义是递归的

树的基本术语：\r\n结点的度、叶结点、分枝结点、孩子结点、双亲结点、\r\n兄弟结点、路径、路径长度、祖先、子孙、结点的层数、树的高度、层序号、有序树、无序树、森林、同构

第 5 章树和二叉树

树的遍历操作：\r\n 前序（先根）遍历\r\n 后序（后根）遍历\r\n 层序遍历

树的存储结构：\r\n双亲表示法：用静态指针来存储双亲树\r\n孩子表示法：多重链表表示和孩子链表表示\r\n双亲孩子表示法：\r\n孩子兄弟表示法：

第 5 章树和二叉树

2、二叉树的定义：\r\n 二叉树（binary tree）是度不超过2的有序树。

二叉树的特点：\r\n 1）每个结点最多有两个孩子（度可为0/1/2）；\r\n 2）孩子之间有顺序（常以左孩子，右孩子来表示）。

几种特殊的二叉树：\r\n 1）斜树\r\n 2）满二叉树\r\n 3）完全二叉树

第 5 章树和二叉树

二叉树的基本性质：

性质5-1：二叉树的第i层上最多可有2i-1个结点。

性质5-3：二叉树中叶结点个数为n０,度为２的结点为n２，\r\n 则n０=n２ 1。

性质5-2：深度为k二叉树中最多可有2k -1个结点，最少有\r\n k个结点(斜树)。

性质5-4：具有n个结点的完全二叉树的深度为\r\n 「log2n」 1。

第 5 章树和二叉树

二叉树的基本性质：

性质5-5：对具有n个结点的完全二叉树进行层序编号，则编号为i的结点满足：\r\n 1)i=1时，为根结点；i>1时，双亲结点编号为i/2；\r\n 2)若2i≤n，i有左孩子，左孩子编号为2i；否则，i无左孩子（必无右孩子）；\r\n 3)若2i 1≤n， i有右孩子，右孩子编号为2i＋1，否则i无右孩子。

第 5 章树和二叉树

二叉树的遍历操作:

先序遍历，中序遍历，后序遍历，层序遍历

由中序和先（后）序遍历结果可惟一确定一棵二叉树。

二叉树的顺序存储结构：

二叉树的顺序存储结构：可采用完全二叉树一样的编号方法（左子：两倍，右子：两倍多1）。

第 5 章树和二叉树

二叉链表存储结构：

struct BiNode\r\n{\r\n T data;\r\n BiNode*lchild, *rchild; //存储左/右孩子指针\r\n};

第 5 章树和二叉树

二叉链表主要函数（操作）：

BiTree(BiNode*root); //有参构造函数\r\n void PreOrder(BiNode*root); //前序遍历二叉树\r\n void InOrder(BiNode*root); //中序遍历二叉树\r\n void PostOrder(BiNode*root); //后序遍历二叉树\r\n void LeverOrder(BiNode*root); //层序遍历二叉树

构造函数：利用扩展二叉树的先序遍历序列建立二叉树\r\n求二叉树t的深度：int Depth(BiNode * r)\r\n求二叉树t的叶子数：int Leaf(BiNode *r)\r\n交换二叉树t的所有左右孩子：void exchange (BiNode *r)\r\n求二叉树的结点个数： void Count(BiNode * r)

第 5 章树和二叉树

要求掌握：\r\n 1、二叉树的顺序存储表示←→二叉树的图形表示\r\n 2、给定树和二叉树，能写出各种遍历结果 \r\n 3、给定扩展二叉树的先序遍历序列→画出此二叉树的图形表示\r\n 给定先序（或后序）和中序遍历序列→画出此二叉树的图形表示\r\n 5、树和二叉树的形态\r\n 4、二叉树的基本性质\r\n 5、树和二叉树各有几种存储结构\r\n 6、二叉树的先序遍历和中序遍历的非递归算法\r\n 7、利用二叉树的先序遍历和中序遍历的非递归算法求二叉树t的深度、求叶子数、交换所有左右孩子、求结点个数

第 5 章树和二叉树

线索链表

以中序遍历线索二叉树能绘出线索链表的示意图

第 5 章树和二叉树

树、森林与二叉树的转换

树转换为二叉树：\r\n 1）加线（兄弟间）\r\n 2）去线（父子间仅保留长子）\r\n 3）调整

森林转换为二叉树：\r\n 1）将森林的每棵树转换为二叉树\r\n 2）将后继树作为前趋树的右孩子

二叉树转换为森林（树）：\r\n 1）加线-----某结点x是其双亲y的左孩子，则把结点x的右孩子、右孩子的右孩子、…，都与结点y用线连起来；\r\n 2）去线-----删去原二叉树中所有的双亲结点与右孩子结点的连线；\r\n 3）调整-----整理由1）和2)所得到的树或森林。

第 5 章树和二叉树

二叉树应用—哈夫曼树及哈夫曼编码

几个概念：\r\n叶结点的权值\r\n带权二叉树\r\n叶结点的路径长度\r\n树的带权路径长度 WPL=

哈夫曼树（Hhffman tree）--带权路径长度最小的二叉\r\n 树，也称为最优二叉树。

要求：\r\n 给定一组权值能构建出哈夫曼树\r\n 可求出每一个权值所对应的哈夫曼编码\r\n 能计算该哈夫曼树的带权路径长度。

第 6 章图

1.图的定义

图（graph）是由有穷非空的顶点集和连接这些顶点的边集构成的整体，通常表示为：

G=〈V,E〉\r\n其中，G表示一个图，V是图G的顶点集，E是图G的集。

图的基本术语：\r\n 无向边、有向边、无向图、有向图、简单图、邻接、依附、完全图、稠密/稀疏图、无向图的度、有向图的入/出度、权、网图、路径、路径长度、回路、简单路径、简单回路、子图、连通图、连通分量、强连通图、强连通分量、生成树、生成森林\r\nn个顶点的无向完全图中，有n*(n-1)/2条边\r\nn个顶点的有向完全图中，有n*(n-1)条边

第 6 章图

图的遍历：

深度优先遍历 DFSTraverse()

广度优先遍历 BFSTraverse()

图的存储结构：\r\n 邻接矩阵和邻接表

图的操作（算法）：\r\n MGraph(T a[ ], int n, int e) //构造函数n个顶点e条边\r\n DFSTraverse(int v) //深度优先遍历\r\n BFSTraverse(int v ) //广度优先遍历

不同的存储结构（邻接矩阵和邻接表）的算法\r\n 邻接矩阵中（无向图、有向图、网图）\r\n 邻接表中（无向图、有向图、网图）及逆邻接表

第 6 章图

给定一个图的邻接矩阵或邻接表（无向图、有向图、网图）

能画出相应的图\r\n 能写出从给定结点出发进行广度、深度优先遍历的结点序列\r\n 能分别按Prim和Kruskal算法构造该图的最小生成树，写出构造过程。\r\n n个顶点的连通图其生成树有且仅有n-1条边

无向图的连通性和有向图的连通性

最小生成树：\r\n Prim(普里姆）算法\r\n Kruskal（克鲁斯卡尔）算法\r\n 要求掌握基本思想和构造过程

第 6 章图

最短路径：

单源最短路径的Dijkstra（狄杰斯特拉）算法\r\n每一对顶点间的最短路径的Folyd(弗洛伊德）算法

要求掌握基本思想和各顶点的最小路径长度及具体路径

AOV网与拓朴排序：顶点表示活动的网\r\n 要求掌握定义及基本方法求得拓朴排序序列

AOE网与关键路径：顶点表示事件，边表示活动的网\r\n 要求掌握定义及基本方法求得关键路径\r\n事件的最早发生时间ve[k]、最迟发生时间vl[k] 、活动的最早开始时间e[i]、活动的最晚开始时间l[i]及活动的缓冲时间t[k]\r\n关键路径(critical path)：始点到终点最大长度的路径

第 7 章查找技术

查找的基本概念:

查找（search）是数据处理中使用最频繁的一种操作。是在具有相同类型的记录构成的集合中找出满足条件的记录。

关键码(Key)---能够惟一标识一个记录的数据项。\r\n 关键码在数据集合中最多只会出现一次。

静态查找：\r\n 不涉及记录插入和删除操作的查找。静态查找不会影响数据源，仅返回待查记录的地址信息。

动态查找：\r\n 涉及记录插入和删除操作的查找。动态查找会影响数据源，会将待查记录插入到数据源集合中或从数据源中删除。

第 7 章查找技术

查找的存储结构:

逻辑上讲，查找基于的数据结构是记录集合，说明我们只关注记录本身的地址，不关心记录间的其它关系。

在某些应用中，查找操作是主要的操作，为了提高；查找效率，需要专门为查找操作设置数据结构，这种面向查找操作的数据结构称为查找结构。

查找算法的性能:\r\n 平均查找长度(average search length)是指所有关键码查找的次数的平均值。

第 7 章查找技术

查找方法:

1、顺序表的顺序查找（哨兵）\r\n 单链表的顺序查找

2、折半查找（二分查找）

3、斐波那契查找\r\n 4、插值查找

5、二叉排序树的查找

6、散列表的查找技术

第 7 章查找技术

平衡二叉树：

最小不平衡子树是指距离插入点（叶结点）最近的且平衡因子的绝对值大于1的结点为根的子树。

平衡二叉树的调整方法：

①LL型顺时针旋转，结点A为结点B的右孩子，结点B的右孩子为A的左孩子

②RR型逆时针旋转，结点A为结点B的左孩子，结点B的左孩子为A的右孩子

③LR型 ⅰ. B为支撑点逆时针旋转，同RR型\r\n ⅱ. A为支撑点顺时针旋转，同LL型

④RL型 ⅰ. B为支撑点顺时针旋转，同LL型\r\n ⅱ. A为支撑点逆时针旋转，同RR型

第 7 章查找技术

散列表的查找技术：

热门分类

热门标签

推荐阅读