数据结构复习

数据结构的基本概念

1. 数据：

   信息的载体，是对客观事物的符号表示，图像，声音，视频等也属于数据的范畴

2. 数据元素：

   • 数据的基本单位，也称元素，结点或记录
   • 由若干个数据项构成，数据项是数据不可分割的最小单位

3. 数据对象：

   • 数据的子集
   • 具有相同性质的数据元素的集合

4. 数据结构：

   数据元素的集合中，元素相互之间的关系：

   • 逻辑结构：集合，线性结构，树型结构，图状结构
   • 物理结构：顺序，链接，索引，散列

5. **算法的特性：**可行性，有穷性，确定性，输入，输出

6. **算法的设计原则：**正确性，可读性，健壮性，高效率，低存储量

队列

队列是一种先进先出的线性表，队头只允许出队，队尾只允许入队。

通常，维护队头的数指向队头所在的下标，维护队尾的数指向队尾的数+1.此时，当队头==队尾的时候队列为空

循环队列

随着出队和入队的进行，数组会整体向右平移，因为数组前面的元素因为出队变成了空白，变得不可使用。造成空间的浪费。使用循环队列可以避免空间的浪费。

一样地，队头==队尾的时候，队列为空。

循环队列里，队头==（队尾+1）%maxsize 时队列为满。

• 队头移动即出队：front=（front+1）%maxsize
• 队尾移动即入队：rear=（rear+1）%maxsize
• 求循环队列中元素的个数：（rear-front+maxsize）%maxsize

几种特殊的链表

循环链表

表尾结点的next指针指向头结点

双向链表

每个数据节点都有两个指针，分别指向直接后继和直接前驱

树

树的一些术语

• 节点的度：节点拥有的子树数量
• 树的度：一棵树中最大的节点度数
• 节点的层次：从根节点算起，根节点为第一层，它的孩子为第二层…依次类推
• 树的深度：从根节点开始（根节点深度记为1），向下每层累加
• 树的高度：从最底部的叶子节点开始（记为1），向上每层累加

树的一些计算公式

所有树都满足的;

• 节点的个数=度总和+1 （即所有的子节点加上根节点）

二叉树：

• 一颗有i层的二叉树，节点数的最大值为：2的i次方再减一

  $$2^i-1$$

  节点数的最小值为i

• 第i层节点数的最大值为：2的i减一次方

  $$2^{i-1}$$

• 二叉树中，叶子节点的个数为：度为2的节点个数+1

• 具有n个节点的完全二叉树，其深度为：(以2为底n的对数，取整再加一)

  $$[log_2n]+1$$

• 二叉树的节点数计算公式：N=N0（度为0的点）+N1（度为1的点）+N2（度为2的点）=N1+N2+（N2+1）=2N2+N1+1

二叉树的一些术语

真二叉树：节点的度要么为0，要么为2

满二叉树：每一个层的结点数都达到最大值

**完全二叉树：**叶子节点只会出现在最后2层，且最后一层的叶子节点都靠左对齐。即所有节点从上往下，从左往右依次排列。

• 满二叉树一定是完全二叉树
• 度为1的节点要么是1个，要么是0个
• 同样节点数的二叉树，完全二叉树的高度最小
• 从根节点到倒数第二层，都是满二叉树

严格二叉树：没有度为1的节点（注意和满二叉树的区别）

已知遍历结果求二叉树

已知先序遍历和后序遍历结果，无法唯一确定一颗二叉树

已知中序遍历+先序/后续，可以确定唯一的一颗二叉树

树的带权路径长度和哈夫曼树

树的路径长度

• 路径：从根节点到某一节点的路径
• 路径长度：路径经过的边数称为路径长度
• 树的路径长度：从根节点到每一个节点的路径长度之和
• 完全二叉树的路径长度最短！

树的带权路径长度（WPL）

• 结点的带权路径长度：结点到树根之间的路径长度（即和根节点之间隔了几条线）与该结点上权的乘积。

• 树的带权路径长度：树的所有叶子节点的带权路径长度之和（只算叶子节点，只算叶子节点，只算叶子节点）

哈夫曼树

哈夫曼树是一种带权路径长度最短的二叉树，也称为最优二叉树

图

图的基本术语

1. 图的定义：

   图是由顶点的有穷非空集合和顶点之间的边的集合组成，表示为G=（V,E）,V为非空有限集合，其元素为顶点，E是边的集合。图不能为空图，图的顶点集V一定不为空，但边集E可以为空。

2. 有向图和无向图：

   • 有向图：

     有序的顶点偶对：<x,y> x称为弧尾，y称为弧头。

     

   • 无向图：

     无序的顶点偶对（x，y）

3. 完全图（即任意两个顶点之间都有边，有向图要互通）

   • 有n（n-1）/2条边的无向图称为完全图
   • 有**n（n-1）**条边的有向图称为有向完全图

4. 度、入度和出度

   • 度：与顶点相关联的边的数目
   • 入度和出度：对于有向图，指向该顶点的有向边的数目为入度，从该顶点指出的有向边的数目称为出度
   • 边的总和=度的总和/2

5. 路径和路径长度

   在无向图中，若存在一个顶点的序列v1，v2，v3…vn，使得(v1,v2)、(v2,v3)、…(vn-1,vn)都属于E，则称顶点V1到顶点vn存在一条路径。若为有向图，则路径也是有向的。

   路径长度：路径上的边或弧的数目。

6. 简单路径，回路和环：

   • 简单路径：顶点不重复出现的路径称为简单路径
   • 回路：第一个顶点和最后一个顶点相同的路径称为回路或环
   • 简单回路：除了第一个顶点和最后一个顶点相同外，其余顶点不重复出现的回路

7. 连通图和连通分量（一般指无向图）

   • 连通图：如果图中任意两个顶点都是连通的，称为连通图
   • 连通分量：无向图的极大连通子图，所谓“极大”是指再加一个顶点就成为不连通，类似与极大线性无关组
   • 连通图只有一个连通分量即他自身，非连通图有多个连通分量

8. 强连通图和强连通分量（一般指有向图）

   • 强连通图：有向图中，若每一对顶点vi，vj之间，vi到vj和vj到vi都存在路径，则称G为强连通图
   • 强连通分量：类似于连通分量

9. 生成树和生成森林

   • 连通图的生成树是包含图中全部顶点的一个极小连通子图
   • 非连通图中，连通分量的生成树构成了生成森林

10. 权，网和子图

    在图中每一条边加上一个数字作为权

    带权的图称为网

图的表示方法

1. 邻接表

   逆邻接表只适用于有向图

2. 邻接矩阵

   • 无向图的邻接矩阵对称，可以压缩储存，所需空间为n(n+1)/2
   • 有向图的邻接矩阵不一定对称，所需空间为n^2
   • 纵向表示入度，横向表示出度

3. n个顶点e条边的图，若采用邻接矩阵存储，则空间复杂度为 O(n2) 。

   n个顶点e条边的图，若采用邻接表存储，则空间复杂度为 O(n+e) 。

图的深度优先遍历和广度优先遍历

n个顶点e条边的图：

• 采用邻接矩阵存储，广度优先遍历算法的时间复杂度为 O(n2) ；

• 若采用邻接表存储，该算法的时间复杂度为 O(n+e)

图的最小生成树

生成树：

1. 包含图的所有顶点
2. 边数等于顶点数减一
3. 不产生回路

最小生成树：

边的权重之和最小的生成树，即最小生成树。

最小生成树不唯一，各边权值不等时才唯一，但最小生成树的权值之和是唯一且最小的

构造最小生成树有两种主要算法：

普利姆算法（对节点进行遍历，适用于稠密图）：

克罗斯卡尔算法（对边进行遍历，适用于稀疏图）：

• 用普里姆(Prim)算法求具有n个顶点e条边的图的最小生成树的时间复杂度为 O(n2)
• 用克鲁斯卡尔(Kruskal)算法的时间复杂度是 O(elog2e)

最短路径，拓扑排序，关键路径

最短路径：

如果从有向图中某一顶点(称为源点)到达另一顶点(称为终点)的路径可能不止一条，如何找到一条路径使得沿此路径上各边上的权值总和达到最小（或对于无权图，路径边数最小），这就是最短路径问题。

拓扑排序：

在图论中，拓扑排序（Topological Sorting）是一个有向无环图（DAG, Directed Acyclic Graph）的所有顶点的线性序列。且该序列必须满足下面两个条件：

1. 每个顶点出现且只出现一次。
2. 若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。

拓扑排序方法：

1. 从图中选择一个入度为0的顶点并输出。
2. 从图中删除该顶点和所有以它为起点的有向边。
3. 重复 1 和 2 直到图为空或当前图中不存在无入度的顶点为止。后一种情况说明有向图中必然存在环。

关键路径：

什么是关键路径？

举个栗子。

唐僧师徒从长安出发去西天取经，佛祖规定只有四人一起到达西天方能取得真经。假如师徒四人分别从长安出发，走不同的路去西天：孙悟空一个筋斗云十万八千里，一盏茶的功夫就到了；八戒和沙和尚稍慢点也就一天左右的时间；而唐僧最慢需要14年左右。徒弟到达后是要等着师傅的。那么用时最长的唐僧所走的路，就是取经任务中的关键路径。其他人走的路径属于非关键路径。

排序与查找：

排序算法复杂度：

排序方法	时间复杂度(平均)	时间复杂度(最坏)	时间复杂度(最好)	空间复杂度	稳定性
插入排序	O(n2)	O(n2)	O(n)	O(1)	稳定
希尔排序	O(n1.3)	O(n2)	O(n)	O(1)	不稳定
选择排序	O(n2)	O(n2)	O(n2)	O(1)	不稳定
堆排序	O(nlog2n)	O(nlog2n)	O(nlog2n)	O(1)	不稳定
冒泡排序	O(n2)	O(n2)	O(n)	O(1)	稳定
快速排序	O(nlog2n)	O(n2)	O(nlog2n)	O(nlog2n)	不稳定
归并排序	O(nlog2n)	O(nlog2n)	O(nlog2n)	O(n)	稳定
计数排序	O(n+k)	O(n+k)	O(n+k)	O(n+k)	稳定
桶排序	O(n+k)	O(n2)	O(n)	O(n+k)	稳定
基数排序	O(n*k)	O(n*k)	O(n*k)	O(n+k)	稳定

查找

• 查找表：由同一类型的数据元素或记录构成的集合，是一种数据结构
• 查找：查询特定元素是否在表中
• 查找成功：若表中存在特定元素，则查找成功，应输出该记录
• 查找不成功：否则，称查找不成功
• 静态查找：只查找，不改变集合内的数据元素
• 动态查找：既查找，又改变集合内数据元素
• 关键字：记录中某个数据项的值，可以用来识别的一个记录
  • 主关键字：可以唯一识别一个记录的关键字（例如学号）
  • 次关键字：识别若干记录的关键字（例如“女”）
• 平均查找长度ASL：ASL（Average Search Length），即平均查找长度，在查找运算中，由于所费时间在关键字的比较上，所以把平均需要和待查找值比较的次数称为平均查找长度。