赞
踩
基于王道数据结构进行的保研面试复习
数据结构的三要素分别为:逻辑结构、存储结构、数据的运算
优点:可以实现随机存取
缺点:存储空间必须连续,可能产生外部碎片
优点:不会产生外部碎片
缺点:每个节点要储存指向下一个节点的指针,指针会占用存储空间
又称哈希存储
方法:设置索引表,索引表重存储关键字和对应节点的地址
优点:检索速度快
缺点:索引表会占用空间,每次增删的时候除了增删元素还要增删索引表表项
方法:设置散列函数,直接根据关键字计算出应存放的地址
优点:检索速度快、增删也很快
缺点:如果散列函数设置不合理,会导致出现存储单元冲突,处理冲突会浪费大量时间
施加在数据之上的运算的定义和实现。运算的定义是针对数据逻辑结构的,指出运算的功能;运算的实现是针对数据的存储结构的,指出运算的具体实现步骤。
有穷性:算法需要在有穷步骤、有穷时间内完成
确定性:算法指令含义明确,对于指定输入,其输出结果确定
可行性:算法描述的操作可以实现
输入
输出
最坏情况下所需时间的数量级
计算:
O
(
T
(
n
)
)
+
O
(
G
(
n
)
)
=
O
(
m
a
x
(
T
(
n
)
+
G
(
n
)
)
)
O(T(n)) + O(G(n)) = O(max(T(n) + G(n)))
O(T(n))+O(G(n))=O(max(T(n)+G(n)))
O ( T ( n ) ) ∗ O ( G ( n ) ) = O ( T ( n ) ∗ G ( n ) ) O(T(n))*O(G(n)) = O(T(n)*G(n)) O(T(n))∗O(G(n))=O(T(n)∗G(n))
常见循环的时间复杂度:
int i = 1;
while(i < n){
i = i * 2;
}
for(int i = 1; i <= n; i++)
for(int j = 1; j <= i; j++)
do-something;
如果有三层循环for(int k = 1; k <= j; k++)则为O(n3)
特点:存储空间连续,逻辑位序与物理位序相同
地址分配方式:
动态内存分配:
C语言:
int *data = malloc(sizeof(int) * init_size);
C++:
int *data = new int[init_size];
访问某位置元素:O(1)
在指定位置插入元素:O(n)
删除指定位置元素:O(n)
查找指定值元素:O(n)
struct list_node{
int data; //数据域
struct list_node *next;
};
头指针:是一个指针,类型是struct list_node *,指向链表的第一个节点
头结点:是一个结点,类型是struct list_node,有的链表会放置一个不存储数据信息的结点作为第一个结点,用于存储表长等信息
对于有头结点的链表,头指针指向头结点
头插法(每次将结点插在最前面)
list_node *head;
int temp;
head = (list_node*)malloc(sizeof(list_node));
head->next = NULL;
scanf("%d", &x);
while(x != 9999){
list_node *s;
s->data = x;
s->next = L->next;
L->next = s;
scanf("%d", &x);
}
尾插法
list_node *head;
int x;
scanf("%d", &x);
head = (list_node*)malloc(sizeof(list_node));
list_node *r = head;
while(x != 9999){
list_node *s;
s = (list_node*)malloc(sizeof(list_node));
s->data = x;
r->next = s;
r = s;
scanf("%d", &x);
}
r->next = NULL;
按序号查找:O(n)
按值查找:O(n)
插入元素:查找O(n),插入O(1)
删除元素:查找O(n),删除O(1)
每个结点存放其前序、后序结点的指针
struct list_node{
int data;
list_node *prior; // 前一个结点
list_node *next; // 后一个结点
};
循环单链表与单链表的区别在于,循环单链表的最后一个结点的next指向第一个结点
循环双链表与双链表的区别在于,循环单链表的最后一个结点的next指向第一个结点,循环单链表的第一个结点的prior指向最后一个结点
构成一个环
静态链表借助数组实现。
typedef struct{
int data;
int next; // 下一个元素的数组下标
}SLinkList[MaxSize];
遍历链表的每个元素,将该元素的next改为prev
遍历链表的每个元素{
temp_next = curr->next;
curr->next = prev;
prev = curr;
curr = temp_next;
}
typedef struct{
int data[50];
int top; // 栈顶指针
}SqStack;
初始化:栈顶指针为-1
入栈:栈顶指针++,元素入栈
出栈:元素出栈,栈顶指针–
两个顺序栈共用一个数据空间,栈A的栈底为0,元素入栈的操作为topA++;栈B的栈底为MaxSize-1,元素入栈的操作为topB–。当topA==topB时,说明栈满。
规定栈顶为链表的第一个结点,入栈时采用栈的头插法,出栈时弹出第一个结点
栈和队列的逻辑结构是一样的,都是属于线性结构,其区别在于数据的运算不同
只能从队尾入队,从队头出队
front指向队列队头的元素,rear指向队列的下一个元素
typedef struct{
int data[50];
int front, rear; // 队头和队尾指针
}SqQueue;
初始化:front=rear=0
进队:front不变,将元素放在rear处,rear++
出队:rear不变,将front处元素弹出,front++
将队列想象为首尾相接
初始化:front=rear=0
入队:( rear + 1 ) % MaxSize
出队:( front + 1 ) % MaxSize
队列长度:( rear + MaxSize - front ) % MaxSize
当rear==front时无法判断是队空还是队满,可以增设一个代表队列长度的变量size,用以判断队空还是队满
typedef struct LinkNode{
int data;
struct LinkNode *next;
}LinkNode; // 链表的结点结构体
typedef struct{
LinkNode *front, *rear; // 链式队列的队头和队尾指针
}LinkQueue;
初始化:设置一个头结点,front和rear都指向该结点
入队:front不变,头结点的next指向新结点,rear也指向该节点
出队:rear不变,存储front的next,并将front的next修改为front->next->next
队列两端分别命名为前端和后端,两端都可以进行入队和出队
压缩目的:对多个值相同的元素只分配一个存储空间,对零元素不分配存储空间。
所有元素都满足aij = aji
存储方式:只存储下三角区和对角线上的元素,将其按行存储在数组中。则矩阵第一行有一个元素需要存储,第二行有2个,第三行有3个……
对于下三角区或对角线上的元素aij,它的前面的元素个数为((i-1)×i)/2+j-1,故它在数组中的位置k等于该值
对于上三角区的元素aij,相当于aji,将i、j互换即可
对于下三角矩阵,其上三角区全部为一个常量,将其存储在数组的(n×(n+1))/2位置,而其下三角区和对角线上元素与对称矩阵相同
对角矩阵,只存储对角线上元素即可
三对角矩阵元素aij,其前面的元素个数为:
3 × (i - 1) - 1 + j - (i - 1)
每行3个元素(除了第一行只有两个之外),所以前i-1行元素个数为3 × (i - 1) - 1 ;
对于第i行,元素aij前面的元素个数为j - (i - 1)
故元素在压缩后的数组中的下标为2i + j - 3
对于元素个数非常少的稀疏矩阵,其存储方式是存储一个三元组,记录非零元素的行、列和其值
命名:模式串为pattern、文本串为text、next表中next[i]存放的是该元素之前子串的最长公共前后缀
算法实现:当pattern的第j位与text的第i位匹配失败时,将pattern的j指针跳到next[j]处与第i位重新匹配
原因:因为next[j]存放的是pattern[0, j-1]部分的最长公共前后缀,已知pattern的[0, j-1]部分与text匹配,而pattern的前缀与自己的后缀相同,则pattern的前缀与text该部分的后缀匹配,因此无需再次比较,只需继续比较第next[j]位即可。
next[i]表示的是[0, i-1]子串的最长公共前后缀长度
计算pattern前后缀,i为前缀末尾,j为后缀末尾,当pattern[i] == pattern[j]时,i和j都++,next[j] = i
当pattern[i] != pattern[j]时,将i修改为next[i]继续和j处元素匹配。因为对于[0, j -1]的子串,其公共前后缀长度为next[j-1],
则前缀[0, i-1]和后缀[j-1-i, j-1]完全相同,又因为前缀[0, i-1]本身也有公共前后缀,长度为next[i],则前缀[0, i -1]的前缀[0, next[i] - 1]和后缀[j-1-i, j-1]的后缀[j-next[i], j-1]相同,不用重复比较,继续比较next[i]和j即可
例如:
a b a c a b a b
i = 2,j = 6时匹配,前后缀都为a b a
i = 3,j = 7时不匹配,此时通过next[3] = 1可知,前缀a b a和前缀pattern[0]=a与后缀a b a和后缀pattern[6]=a匹配,下一步比较next[3]=1和j=7是否匹配即可,不需要再比较0和6
树的高度:树有几层
结点的度:该结点儿子的数量
树的度:树中结点最大度数
树的结点数=树的所有结点的度数之和+1
度大于0的结点(有儿子的结点)称为分支节点,度为0的结点(无儿子的结点)称为叶子节点
结点的深度:从根结点开始累加结点在第几层深的位置(从上往下)
结点的高度:从结点的叶子节点开始累加(从下往上)
有序树:树中结点各子树从左到右是有顺序的
无序树:无顺序
路径和路径长度:树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的,路径长度是路径上经过的边的个数
(因为树中分支是有方向的,只能从父指向子,所以树种的路径是从上到下的,同一父亲的两个儿子之间不存在路径)
森林:多棵树
存储:顺序存储、链式存储
存储普通树的方法:
每个节点存储当前节点的父亲节点在数组中的位置
struct node{
int data; // 当前节点的值
int parent; // 当前节点的父亲节点的下标
};
struct Tree{
node node_list[MAX_N]; // 存储所有节点的数组
int r; // 根的位置下标
int n; // 结点数
};
每个结点用一个链表存储当前节点的所有孩子是数组中的位置
struct child{ // 孩子链表的结点
int position;
struct child *next;
};
struct node{ // 树中的结点
int data; // 当前节点的值
struct child * first_child;
};
struct Tree{
node node_list[MAX_N];
int r;
int n;
};
每个节点存储当前节点的第一个孩子和当前节点的下一个兄弟
struct node{
int data;
struct node *first_child, *next_brother;
};
左右子树不能颠倒且树的度小于等于2
二叉树与度为2的有序树的区别:
性质:
二叉树的顺序存储:
链式存储:
完全二叉树的编号:
普通树转二叉树
(这样转化出的二叉树没有右孩子)
森林转二叉树
二叉树还原成普通树
递归前、中、后序:
void postOrder(TreeNodePoint root){
if(root != NULL){
visit(root);
postOrder(root->lchild);
postOrder(root->rchild);
}
}
栈进行前中后序遍历:
void postOrderByStack(TreeNodePoint root){ stack<TreeNodePoint> node_stack; TreeNodePoint temp = root; while(temp != NULL || !node_stack.empty()){ if(temp != NULL){ // temp不为空,一路将其左孩子入栈 node_stack.push(temp->lchild); temp = temp->lchild; } else{ temp = node_stack.top(); node_stack.pop(); visit(temp); temp = temp->rchild; } } }
队列进行层次遍历:
思路:将根节点入队,然后出队,访问出队节点,将其左、右孩子分别入队,等本层遍历完后再将下一层节点依次出队,重复操作。
void levelOrder(TreeNodePoint root){
queue<TreeNodePoint> node_queue;
TreeNodePoint temp;
node_queue.push(root);
while(!node_queue.empty()){
temp = node_queue.front();
node_queue.pop();
visit(temp);
if(temp->lchild != NULL)
node_queue.push(temp->lchild);
if(temp->rchild != NULL)
node_queue.push(temp->rchild);
}
}
前序/后序 再加上一个中序即可恢复二叉树
前序+中序:
前序的第一个元素即为根节点,在中序序列中寻找这个根节点,即可区分左右子树
除最后一层外,其他每个节点度都为2,高为h的满二叉树节点个数为2h-1
除最后一层外都是满的,最后一层的节点集中于左侧
(注意最后一层和倒数第二层都有叶子节点,不只在最后一层)
如果二叉树某节点左儿子指针空闲,将其用于存放前驱节点,右儿子指针空闲,将其用于存放后继节点。并设置左、右两个标志变量,用以标记其存放的是儿子节点还是线索。
线索二叉树有前序、中序、后序三种。此处以中序为例:
线索二叉树的建立:
线索二叉树的使用:
所有节点其左子树上的节点小于自己,右子树上的节点大于自己
对二叉排序树进行中序遍历,得到的是单调递增的序列
二叉排序树的建立:逐点找位置插入即可
二叉排序树的查找:递归或循环
平均查找长度ASL:所有节点查找所需比较次数的和
删除:
每个叶子节点带权,带权路径长度WPL=sum(叶子节点权值*该叶节点深度)
使WPL最小的树为哈夫曼树
哈夫曼树的构造:
这样得到的树可以保证权值大的叶子节点深度低,从而使得WPL最小
哈夫曼编码:
当编码长度不一致时,出现频率高的字符赋以短编码、出现频率低的字符赋以长编码,有利于缩短编码长度
前缀编码:没有任何一个字符的二进制编码是其他字符的前缀,这样不会造成误解,哈夫曼编码就是一种前缀编码
由哈夫曼树得到哈夫曼编码:
统计所有字符的出现频率作为其权值,根据这一权值构建哈夫曼树,左边为0、右边为1,得到最终编码。WPL即为最终编码长度。
图G、顶点集V、边集E
用一维数组存储V,用二维矩阵存储E
对于无权图,若<i, j>之间存在边,则E[i, j] = 1,否则E[i, j] = 0;(无向图应把E[i, j]和E[j, i]都赋为1)
对于有权图,若<i, j>之间存在边,则E[i, j] = 权值,否则E[i, j] = ∞;
// 邻接矩阵
int data[MAX_V]; // 存点
int edge[MAX_V][MAX_V]; // 用矩阵存i, j之间是否有边
// 稀疏矩阵
typedef struct edge{
int v1, int v2;
int weight;
}Edge;
int data[MAX_V]; // 存点
Edge G[MAX_E]; // 存边
每个顶点v用一个单链表表示与该节点相连的边
typedef struct edge{
int adjvex; // 位置域(该边终点的位置)
int weight; // 权值域
struct edge *next;
}Elink; // 以某结点起始的边的链表中的一个
typedef struct ver{
int vervex;
Elink *first_link;
}Vlink; // 结点结构体
Vlink G[MAX_V];
C++中可以用vector来存储
struct edge{
int to;
int weigth;
};
vector<edge> graph[MAX_V_NUM]; // graph[i]是一个vector,存储所有以i为起点的边
对于顶点,其存放的信息包括:顶点信息data、以该顶点为弧头的第一个弧first_in、以该顶点为弧尾的第一个弧first_out
对于弧,其存放的信息包括:
针对无向图的链式存储结构
对于顶点,其存放的信息包括:顶点信息data,依附于该顶点的第一条边的指针firstedge
对于边,其存放的信息包括:标志域mark,ivex、jvex表示边依附的两个点,ilink、jlink表示下一条依附于ivex、jvex的边
队列
typedef struct edge{
int adjvex;
int weight;
struct edge *next;
}Elink;
typedef struct ver{
int vervex;
Elink *first;
}Vlink;
typedef struct graph{
Vlink g[MAX_V_NUM];
int v_num;
}Graph;
bool visited[MAX_V_NUM]; queue<int> Q; void BFS_graph(Graph G){ for(int i = 0; i < G.v_num; i++) visited[i] = false; for(int i = 0; i < G.v_num; i++) if(!visited[i]) BFS_ver(G, i); } void BFS_ver(Graph G, int v){ visit(v); visited[v] = true; Q.push(v); while(!Q.empty()){ int temp = Q.front(); Q.pop(); for(Elink *i = G.g[temp].first; i != NULL; i = i -> next){ visit(i->adjvex); visited[i->adjvex] = true; Q.push(i->adjvex); } } }
递归或栈
bool visited[MAX_V_NUM]; void DFS_graph(Graph G){ for(int i = 0; i < G.v_num; i++) visited[i] = false; for(int i = 0; i < G.v_num; i++) if(!visited[i]) DFS_ver(G, i); } void DFS_ver(Graph G, int v){ visit(v); visited[v] = true; for(Elink *i = G.g[v].first; i != NULL; i = i -> next){ if(!visited[i->adjvex]) DFS_ver(G, i->adjvex); } }
对于连通图,在BFS_graph()、DFS_graph()函数中调用一次BFS_ver()或DFS_ver()即可遍历完成,对于非连通图,调用BFS_ver()或DFS_ver()的次数即为其连通分量的个数。
BFS可以用于解决单源最短路问题,因为BFS遍历总是从近到远的。
方法是:
int distance[MAX_V_NUM]; bool visited[MAX_V_NUM]; queue<int> Q; void BFS_ver(Graph G, int begin){ for(int i = 0; i < G.v_num; i++){ distance[i] = MAX_MUM; visited[i] = false; } distance[begin] = 0; visited[begin] = true; Q.push(begin); while(!Q.empty()){ int temp = Q.front(); Q.pop(); for(Elink *i = G.g[temp].first; i != NULL; i = i->next){ if(!visited[i->adjvex]){ distance[i->adjvex] = distance[temp] + 1; visited[i->adjvex] = true; Q.push(i->adjvex); } } } }
基于贪心策略
集合S:存储已经找到最短路径的结点,初始时将v0放入其中
集合T:V-S
dist[]:记录源点v0到其他所有点的最短距离,初始时将与v0直接连通的点写入
path[]:记录到v0的最短路径中的前驱节点
不优化:O(V2)
优先队列优化:O(ElogV)
算法:
初始时S中只包含v0,每次从T中选取一个距离v0最近的点u加入S中,并对与u相连的所有点进行松弛操作。
注意:Dijkstra算法的权值不能为负
struct Edge{ int to; // 边的终点 int length; // 边的长度 Edge(int t, int l): to(t), length(l){} }; struct Point{ int number; // 点的编号 int distance; // 点到源点的距离 Point(int n, int d): number(n), distance(d){} bool operator< (const Point& p) const{ return distance > p.distance; // 距离小的优先级高 } }; vector<Edge> graph[MAX_V_NUM]; // 邻接表 graph[i]是一个存储所有与i相邻的 int distance[MAX_V_NUM]; int path[MAX_V_NUM]; void dijkstra(int s){ priority_queue<point> priorityQ; dis[s] = 0; priorityQ.push(Point(s, dis[s])); while(!priorityQ.empty()){ int u = priorityQ.top().number; priorityQ.pop(); for(int i = 0; i < graph[u].size; i++){ int v = graph[u][i].to; int d = graph[u][i].length; if(dis[v] > dis[u] + d){ dis[v] = dis[u] + d; priorityQ.push(Point(v, dis[v])); path[v] = u; } } } } int main(){ int n, m; // n为点的个数,m为边的个数 scanf("%d %d", &n, &m); memset(graph, 0, sizeof(graph)); fill(dis, dis+n+1, INT_MAX); // 编号从1到n+1 while(m--){ int from, to, length; scanf("%d %d %d", &from, &to, &length); graph[from].push_back(Edge(to, length)); graph[to].push_back(Edge(from, length)); } int s, t; // 起点和终点 Dijkstra(s); if(dis[t] == INF) dis[t] = -1; printf("%d\n", dis[t]); }
k是中间结点,i、j是两边的结点。算法思路是,尝试在所有i、j之间加入中间结点k,看是否会得出更近的路径。遍历所有结点让其作为中间结点,并在确定k后遍历所有i、j。
const int max_n = 505; int dis[max_n][max_n]; void Floyd(int n){ for(int k = 1; k <= n; k++) for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]); } int main(){ int n, m; int u, v; scanf("%d %d", &n, &m); fill(dis, dis + max_n * max_n, INT_MAX); for(int i = 0; i < m; i++){ scanf("%d %d", &u, &v); scanf("%d", &dis[u][v]); } Floyd(n); return 0; }
并查集的处理对象:多个无交集的集合的合并和查询问题,要求将集合在逻辑上表示为树结构
并查集的两个功能:
查找:对于每个元素,不断向上查找,直到找到它的根,根据根是否相同来判断两个元素是否在同一个集合中
合并:将一棵树作为另一棵树的子树,从而将两棵树变成一棵更大的树
注意,是树合并的过程中如果不加约束,有可能导致树高越来越高,这样查找时就会面临不便,因此在合并时需要进行路径压缩
使用方法:一开始所有结点都单独成树(Initial函数),如果两个结点连通,就将两个结点Union,最后得到一个并查集
int father[MAX_N]; // 每个结点的父亲节点 int height[MAX_N]; // 以顶点x为根的树的高度 void Initial(int n){ for(int i = 0; i <= n; i++){ father[i] = i; height[i] = 0; } } int Find(int x){ if(x != father[x]){ father[x] = Find(father[x]); // 路径压缩过程,将该结点直接放入根节点的一级孩子中 } return father[x]; } void Union(int x, int y){ x = Find(x); y = Find(y); if(x != y){ // 如果传入的两个点不是一个集合中的 // 矮树作为高树的子树 if(height[x] < height[y]){ // x并入y,x的父亲是y,由于y高度比x高,height[y]的高度并不会变 father[x] = y; } else if(height[x] > height[y]){ // y并入x,y的父亲是x,由于x高度比y高,height[x]的高度并不会变 father[y] = x; } else{ // y并入x,y的父亲是x,由于x、y一样高,y并入x后x的高度加一 father[y] = x; height[x]++; } } return; }
生成树:包含所有顶点和n-1条边的子树,若加一条会导致回路,若减一条会导致不连通
最小生成树:边权值和最小的生成树
首先任取一个顶点加入S,然后每次选取一个与S中元素距离最近的点及边加入S中,最后得到最小生成树。
算法如下,其中priorityQ存的是所有T到所有S的点对及其距离,每次选一个T中最小的。priorityQ中的点可能重复,因为对于同一个点,它的距离是与多个S中的点之间的,只需在某一次作为最近的点被找出来即可。
struct Edge{ int pos; int length; Edge(int p, int l): pos(p), length(l) {} }; vector<Edge> graph[MAX_N]; struct Point{ int to; int length; Point(int t, int l): to(t), length(l) {} bool operator< (const Point& p) const{ return length > p.length; } }; bool S[MAX_N]; int Prim(int n){ int cost = 0, cnt = 0; priority_queue<Point> pointQ; pointQ.push(Point(1, 0)); while(!pointQ.empty()){ int u = pointQ.top().to; // 22~28行:选取一个离S中点u最近的点加入S int d = pointQ.top().length; pointQ.pop(); if(S[u]) continue; // 如果该点已经被加入S了,只将其pop出去而不进行下面的操作 S[u] = true; cnt++; cost += d; if(cnt == n) break; // 如果所有点都已经加入了S,结束算法 for(int i = 0; i < graph[u].size(); i++){ // 找到u后,将所有与u相连且不在S中的点加入优先队列,等待在以后的寻找中作为最近的点被加入S int v = graph[u][i].pos; int c = graph[u][i].length; if(S[v]) continue; priorityQ.push(Point(v, c)); } } return total; } int main(){ int n, m; scanf("%d %d", &n, &m); while(m--){ int a, int b, int d; scanf("%d %d %d", &a, &b, &d); graph[a].push_back(Edge(b, d)); graph[b].push_back(Edge(a, d)); } fill(S, S+n+1, false); printf("%d", Prim(n)); return 0; }
初始时S中包含所有的点,不包含任何一条边,每次选取一条权值最小的边,如果加入该边后S不含回路,则加入,如果含回路,则舍弃
struct Edge{ int from; int to; int length; bool operator< (const Edge& e) const{ return length < e.length; } }; Edge edge_graph[MAX_N * MAX_N]; int father[MAX_N]; int height[MAX_N]; // height[x]存的是以结点x为根的树的高度 void Initial(int n){ for(int i = 0; i <= n; i++){ father[i] = i; height[i] = 0; } } int Find(int x){ if(x != father[x]) father[x] = Find(father[x]); return father[x]; } void Union(int x, int y){ x = Find(x); y = Find(y); if(height[x] > height[y]){ father[y] = x; } else if(height[x] < height[y]){ father[x] = y; } else{ father[y] = x; height[x]++; } } int Kruskal(int n, int m){ Initial(n); sort(edge_graph, edge_graph + m); // 对所有边的长度进行排序 int sum = 0; for(int i = 0; i < m; i++){ Edge temp = edge_graph[i]; if(Find(temp.from) != Find(temp.to)){ // 如果from和to目前不在同一个集合中,即不连通,则加入该边不会成环 Union(temp.from, temp.to); sum += temp.length; } } return sum; } int main(){ int n; while(scanf("%d", &n) != EOF){ if(n == 0) break; int m = n * (n - 1) / 2; for(int i = 0; i < m; i++) scanf("%d %d %d", &edge_graph[i].from, &edge_graph[i].to, &edge_graph[i].length); printf("%d\n", Kruskal(n, m)); } return 0; }
DAG图:有向无环图
若用DAG图表示一个工程,用<Vi, Vj>表示Vi必须在Vj之前完成的这样一种关系,则称这种有向图为顶点表示活动的网络,即AOV网
拓扑排序:
#include<iostream> #include<cstdio> #include<vector> #include<queue> using namespace std; vector<int> graph[MAX_N]; // 存储图,graph[i]是一个vector,存储所有i直接到达的顶点 int in_degree[MAX_N]; // degree[i]存储i的入度 bool TopologicalSort(int n){ // 拓扑排序,如果有环返回True,否则返回False vector<int> topology; queue<int> node_in0; // 存储入度为0的结点 for(int i = 1; i <= n; i++) if(in_degree[i] == 0) node_in0.push(i); // int remain_num = n; while(!node_in0.empty()){ int temp = node_in0.front(); node_in0.pop(); topology.push_back(temp); // remain_num--; for(int i = 0; i < graph[temp].size(); i++){ int v = graph[temp][i]; inDegree[v]--; if(inDegree[v] == 0) node_in0.push(v); } } // return remain_num == 0; return topology.size() == n; } int main(){ int n, m; scanf("%d %d", &n, &m); memset(in_degree, 0, sizeof(in_degree)); while(m--){ int from, to; scanf("%d %d", &from, &to); graph[from].push_back(to); in_degree[to]++; } if(TopologicalSort(n)) printf("有环\n"); else printf("无环\n"); return 0; }
以顶点表示事件,以有向边表示活动,以边上权值表示该活动持续的时间。
从源点到汇点的所有路径中,具有最大路径长度的路径称为关键路径,关键路径上的活动称为关键活动。
每个活动的
非关键活动可以拖延,不会影响整个工程的完成。而关键活动的拖延会影响整个工程的完成。因此求关键路径可以转化为求所有活动的最早和最晚开始时间,判断二者是否相等。
计算方式是:通过拓扑排序找出活动的前序和后序活动,那么活动的最早开始时间就是其所有前序活动的最晚完成时间,活动的最晚开始时间就是其所有后序活动的最早开始时间减去该活动所需时间。
#include<iostream> #include<cstdio> #include<vector> using namespace std; vector<int> graph[MAX_N]; // graph[i]存放结点i的后序结点 int inDegree[MAX_N]; long long earliest[MAX_N]; // 最早开始时间 long long latest[MAX_N]; // 最晚开始时间 long long time[MAX_N]; // 花费时间 long long CriticalPath(int n){ vector<int> topology; // 拓扑序列 queue<int> node_in0; // 存入度为0的点 long long total_time = 0; for(int i = 1; i <= n; i++) if(inDegree[i] == 0) node_in0.push(i); while(!node_in0.empty()){ int u = node_in0.front(); topology.push_back(u); node_in0.pop(); for(int i = 0; i < graph[u].size(); i++){ // 遍历u的所有后序结点 int v = graph[u][i]; earliest[v] = max(earliest[v], earliest[u] + time[u]); inDegree[v]--; if(inDegree[v] == 0){ node_in0.push(v); totalTime = max(totalTime, earliest[v] + time[v]); } } } for(int i = topology.size() - 1; i >= 0; i--){ int u = topology[i]; if(graph[u].size() == 0){ // 如果u是最后的结点,在totalTime最后完成可以不耽误工期 latest[u] = totalTime - time[u]; } else{ // 如果u不是最晚结点,将其初始化为INT_MAX latest[u] = INT_MAX; } // 遍历u的所有后序结点,寻找其中要求最早的 for(int j = 0; j < graph[i].size(); j++){ int v = graph[u][j]; latest[u] = min(latest[u], latest[v] - time[u]); } } return totalTime; } int main(){ int n, m; scanf("%d %d", &n, &m); memset(inDegree, 0, sizeof(inDegree)); memset(earliest, 0, sizeof(earliest)); memset(latest, 0, sizeof(latest)); for(int i = 1; i <= n; i++) scanf("%lld", &time[i]); while(m--){ int from, to; // from是to的前序结点 scanf("%d %d", &from, &to); graph[from].push_back(to); inDegree[to]++; } long long total_time = CriticalPath(n); }
算法 | 算法作用 | 时间复杂度 | 存储结构 |
---|---|---|---|
BFS | 深搜(可以用来解决无权图的单源最短路问题) | 邻接矩阵O(n2),邻接表O(n+m) | 邻接表 |
DFS | 广搜 | 邻接矩阵O(n2),邻接表O(n+m) | 邻接表 |
Dijkstra | 有权图的单源最短路问题 | O(n2) | 邻接表 |
Floyd | 有权图的多源最短路问题 | O(n3) | 邻接矩阵 |
Prim | 稠密图的最小生成树 | O(n2) | 邻接表 |
Kruskal | 稀疏图的最小生成树 | O(mlogm) | 边数组 |
AOV拓扑排序 | 判断有向图是否有环,对图中活动进行拓扑排序 | 邻接矩阵O(n2),邻接表O(n+m) | 邻接表 |
AOE | 求带权有向图的关键路径 | 邻接表 |
int arr[MAXN]; int BinarySearch(int n, int target){ int left = 0; int right = n - 1; while(left <= right){ int middle = left + (right - left) / 2; if(arr[middle] < target){ left = middle + 1; } else if(arr[middle] > target){ right = middle - 1; } else return middle; } return -1; }
又称索引顺序查找。其基本思路是,将整个表分成几个块,每块选取一个代表值,将所有块的代表值与块的起始地址放在一起构建索引表。
ASL为索引查找的平均查找长度LI和块内查找的长度LS两部分构成。
若对索引表采用二分查找,还可以进一步加速。
左子树上所有结点小于根节点,右子树上所有节点大于根节点
BST的查找
BSTNode *BST_search(Tree T, int key){
while(T != NULL && T->data != key){
if(T->data > key) T = T->lchild;
else T = T->rchild;
}
return T;
}
BST的插入(递归)
bool BST_insert(Tree T, int k){
if(T == NULL){
T = (Tree)malloc(sizeof(BSTNode));
T->data = k;
T->lchild = T->rchild = NULL;
return True; // 插入成功
}
else if(k == T->data)
return False; // 树中存在相同关键词,插入失败
else if(k < T->data)
return BST_insert(T->lchild, k);
else if(k > T->data)
return BST_insert(T->rchild, k);
}
BST的构造
Tree create_BST(int arr[], int n){
Tree T = NULL;
for(int i = 0; i < n; i++){
BST_insert(T, arr[i]);
}
return T;
}
BST的删除
平衡因子:左右子树的高度差
平衡二叉树的平衡因子只能是-1、0或1
平衡二叉树的插入:
如果插入后导致二叉树不平衡,那么寻找最小不平衡二叉树,对其进行旋转操作:
平衡二叉树的删除:
算法 | 时间复杂度 | 要求 | ASL |
---|---|---|---|
顺序查找 | O(n) | 无特殊要求 | 查找成功的ASL是(n+1)/2,不成功是n+1 |
二分查找 | O(logn) | 要求表有序,且物理结构是可以随机存取的顺序存储 | log2(n+1)-1 |
分块查找 | 块内不要求有序,块之间要求有序 | ||
二叉排序树 | |||
平衡二叉树 | |||
将每一个待排序元素插入前面已经排好的元素序列中
void insertSort(int[] arr, int n){
for(int i = 2; i < n; i++){
if(arr[i] < arr[i - 1]){
for(int j = i - 1; j >= 0; j++){
A[j + 1] = A[j];
if(A[j] <= A[i]) break;
}
A[j + 1] = A[i];
}
}
}
void BinaryInsertSort(int[] arr, int n){ int i, j, low, high, mid; for(int i = 2; i <= n; i++){ low = 1; high = i - 1; while(low <= high){ mid = low + (high - low) / 2; if(arr[mid] > arr[i]) high = mid - 1; else low = mid + 1; } // 插入high+1位置,从high+1到i-1统一后移一个位置 for(int j = i - 1; j >= high + 1; j--){ arr[j + 1] = arr[j]; } arr[high + 1] = arr[i]; } }
与直接插入排序相比,比较次数减少,但是后移操作导致时间复杂度仍然为O(n2)
先将待排序列表分为若干等长子表,对各子表进行直接插入排序,当所有子表完成排序后,整个表已呈“基本有序”,此时再对全体记录进行一次插入排序。
void ShellSort(int[] arr, int n){
for(dk = n / 2; dk >= 1; dk = dk / 2){
for(i = dk + 1; i <= n; i++){
if(A[i] < A[i - dk]){
for(j = i - dk; j >= 0 && A[i] < A[j]; j -= dk)
A[j + dk] = A[j];
}
}
}
}
冒泡排序的基本思想是:第一趟排序时,从后往前两两比较相邻元素值,若为逆序则交换他们,最终结果是将最小的元素放在了序列最前面;第二趟排序时,比较范围是n-1到1,最终结果是将次小元素放在序列第二位;依次这样进行直到本轮遍历没有发生交换,说明表已经有序。
在冒泡排序中,关键字小的元素像气泡一样依次向上漂浮到水面上。
void BubbleSort(int[] arr, int n){
bool flag;
for(int i = 0; i < n; i++){
flag = false; // 标识本轮遍历是否发生交换
for(int j = n - 1; j > i; j-){
if(arr[j] < arr[j - 1]){
// 逆序
swap(arr[j], arr[j - 1]);
flag = true;
}
}
if(flag == false) // 如果本轮遍历没有发生交换,说明表已经有序
return;
}
}
快速排序是基于分治法的排序,其思路是:首先选择一个元素,通过一趟排序找出比它小的所有元素[0, k-1]和比它大的元素[k, n-1],则该元素应该放在arr[k]的位置。然后分别对左右两个序列再进行这个操作。
void QuickSort(int[] arr, int low, int high){ if(low < high){ int pivotpos = Partition(arr, low, high); // 对表进行划分 QuickSort(arr, low, pivotpos - 1); QuickSort(arr, pivotpos + 1, high); } } int Partition(int[] arr, int low, int high){ int pivot = arr[low]; // 将序列第一个元素作为枢轴 while(low < high){ while(low < high && arr[high] >= pivot) high--; // 从后往前找到第一个比枢轴小的元素 arr[low] = arr[high]; // 放在枢轴左边 while(low < high && arr[low] <= pivot) low++; // 从前往后找到第一个比枢轴大的元素 arr[high] = arr[low]; // 放在枢轴右边 } A[low] = pivot; return low; }
第i趟排序时,选择[i, n - 1]之间最小的元素与arr[i]交换,获得arr[i]位置应当存放的元素。直到i=n-1,排序完成。
void SelectSort(int[] arr, int n){
int min_pos;
for(int i = 0; i < n - 1; i++){
min_pos = i;
for(int j = i + 1; j < n; j++)
if(arr[j] < arr[min]) min = j;
if(min != i)
swap(arr[i], arr[min]);
}
}
大根堆:对于树及其中所有子树,最大元素放在根上
小根堆:对于树及其中所有子树,最小元素放在根上
堆排序的基本思路是:首先将序列构建为初始堆,输出堆顶元素(即最大值),然后将堆底元素送入堆顶,此时堆已经不符合大根堆要求,因此将堆顶元素向下调整,调整后再次输出堆顶元素,即第二大的值,如此重复进行。
构建初始大根堆:
首先按照层次构建一颗完全二叉树,然后从根节点[n / 2]的子树开始,一直到根节点为1的整棵树,逐步调整树(如果根节点是最大的,不需要再调整,否则将它较大的孩子拿上来作为根节点)。
堆排序:
将最大元素根节点输出,然后将最底层的叶节点提上来作为根节点,最后对堆进行调整,调整方法是,从上到下依次判断该节点是否大于它的两个孩子,如果不是,将其较大的孩子拿上来作为根节点。
堆插入:
插入元素时,先将该元素放在堆的末端,然后再对这个新的节点逐步向上调整。
堆排序适合在一亿个数中选取最大的一百个的情况,方法是:
取前一百个元素建立小顶堆,然后依次读入剩下的数,如果小于堆顶则舍弃,否则就用该数代替堆顶并调整堆,读入完成后堆中一百个元素即为所求。(如果一个数小于堆顶,那么它一定也小于堆中其他元素,那么它不可能是最大的前一百个)
将一个表分为两个子表,分别排序后归并
// 调用 MergeSort(arr, 0, n - 1); void MergeSort(int[] arr, int low, int high){ if(low <= high){ int mid = low + (high - low) / 2; MergeSort(arr, low, mid); // 对左侧子表进行递归 MergeSort(arr, mid + 1, high); Merge(arr, low, mid, high); } } int *temp = (int*)malloc((n + 1) * sizeof(int)); // 辅助数组temp void Merge(int[] arr, int low, int mid, int high){ // 左子表是[low, mid],右子表是[mid+1, high] for(int i = low; i <= high; i++) temp[i] = arr[i]; int i, j, k; for(i = low, j = mid + 1, k = i; i <= mid && j <= high; k++){ if(temp[i] <= temp[j]) arr[k] = temp[i++]; else arr[k] = temp[j++]; } while(i <= mid) arr[k++] = temp[i++]; while(j <= high) arr[k++] = temp[j++]; return; }
排序算法 | 时间复杂度 | 空间复杂度 | 稳定性 | 适用的物理结构 | 备注 |
---|---|---|---|---|---|
直接插入排序 | O(n2) | O(1) | 稳定 | 适用顺序存储和链式存储 | |
折半插入排序 | O(n2) | O(1) | 稳定 | ||
希尔排序 | 最好情况O(n1.3)最坏情况O(n2) | O(1) | 不稳定 | ||
冒泡排序 | O(n2) | O(1) | 稳定 | ||
快速排序 | 最好情况O(nlogn)最坏情况O(n2) | O(log2n) | 不稳定 | ||
简单选择排序 | O(n2) | O(1) | 不稳定 | ||
堆排序 | O(nlogn) | O(1) | 不稳定 | ||
归并排序 | O(nlogn) | O(n) | 稳定 | ||
基数排序 | O(n+rd) | ||||
数据结构的三要素:
逻辑结构(线性结构(线性表、栈、队列)、非线性结构(树、图))
存储结构(顺序存储、链式存储、索引存储、散列存储)
数据的运算
链表增加头结点的作用:便于对首结点的处理,便于空链表与非空链表的统一处理
顺序存储和链式存储:
顺序存储可以随机存取,按位置访问元素复杂度为O(1),但插入、删除时需移动后面元素,复杂度为O(n)
链式存储按位置访问元素需要从头开始遍历,复杂度为O(n),但一旦找到后插入、删除操作复杂度为O(1)
一个递归算法必须包含终止条件和递归部分
描述KMP算法的思路,以及next数组的计算方法 TODO
树的性质:
二叉树的性质:
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。