众所周知,数据结构是一门写伪代码的学科,特在此总结各路伪码给大家参考
伪码基本操作
比较
- EQ // EQUAL等于
- NE // NOT EQUAL不等于
- GT // GREATER THAN大于
- LT // LESS THAN小于
- GE // GREATER THAN OR EQUAL 大于等于
- LE // LESS THAN OR EQUAL 小于等于
线性表
- InitList( &L ); //建空表,初始化
- DestoryList( &L ); //撤销表,释放内存
- int LengthList( L ); //求表中元素个数,即表长
- POSITION LocateElem (L,ElemType e,compare() ) //查找e
- PriorElem( L, cur_e, &pre_e ); //求当前元素e的前驱
- NextElem( L, cur_e, &next_e ); //求当前元素e的后继
- ListInsertBefore(&L, i, e ); //把e插入到第i个元素之前
- ListDelete( &L, i,&e ); //删除第i个元素并“看”此元素
- ListTraverse( L, Visit() ); // “看”表中全部元素(遍历)
栈
- InitStack(&S); //构造一个空栈
- DestroyStack(&S); //销毁栈s
- ClearStack(&S); //将S清为空栈
- StackEmpty(S); //若栈S为空栈,返回True; 否则返回 False
- StackLength(S); //返回栈S的元素个数,即栈的长度
- GetTop(S, &e); //用e返回栈S的栈顶元素
- Push(&S, e); //插入元素e为新的栈顶元素
- Pop(&S, &e); //删除S的栈顶元素,并用e返回其值
队列
- InitQueue(&Q); //构造一个空队列Q
- DestroyQueue(&Q); //销毁队列Q
- QueueLength(Q); //返回队列Q的长度
- ClearQueue(&Q); //将队列清为空队列
- GetHead(Q, &e); //用e返回Q的队头元素
- EnQueue(&Q, e); //插入元素e为Q的新的队尾元素
- DeQueue(&Q, &e); //删除Q的队头元素,并用e返回其值
串
- StrAssign(&T, chars); // 串赋值,生成值为chars的串T
- StrCompare(S,T); // 串比较,若S>T,返回值大于0…
- StrLength(S); // 求串长,即返回串S中的元素个数
- Concat(&T, S1, S2); // 串连接,用T返回S1+S2的新串
- SubString(&Sub, S, pos, len); //求S中pos起长度为len的子串
广义表
- GetHead(L); //取广义表L的头
- GetTail(L); //取广义表L的尾
图
- CreateGraph(&G, num); //构造一个顶点数为num,边数为0的图
- DestroyGraph(&G); //销毁图 G
- FirstAdjVex(G, v); //返回 v 的第一个邻接点
- NextAdjVex(G, v, w); //返回 v 的(相对于 w 的)下一个邻接点
- InsertEdge(&G, v, w); //在 G 中增添以v, w为顶点的边
- DeleteEdge(&G, v, w); //在 G 中删除以v, w为顶点的边
基础知识点
线性表
- 顺序表的插入与删除(时间复杂度O(n))
- 链表节点的插入,删除,查找
- 插入方法有头插法和尾插法,删除类比插入
- 单链表查找的时间复杂度为O(n)
- 插入与删除时间复杂度为O(1)
- 双向链表,循环链表,双向循环链表,静态链表的基本操作
栈与队列
栈与队列是特殊的链表
- 栈的应用——表达式求值
- 分别运用运算符栈和操作数栈分解表达式
- 逆波兰表达式
- 循环队列
- 在循环队列中,空队和队满时都有front=rear;判决条件将出现二义性
- 解决方法:
- 使用一个计数单元记录队列中的元素个数
- 加设标志位,删除时置1,插入时置0(分离插入后和删除后出现判决条件)
- 空一个单元,队满特征改为front=(rear+1)%N
二叉树
二叉树的遍历:
- 先序遍历
- 中序遍历
- 后序遍历
- 层次遍历
- 遍历算法的应用:
- 输出二叉树的节点
- 输出二叉树的叶子节点
- 统计叶子节点数目
- 求二叉树的高度
- 遍历主要分为整体遍历和分别遍历左右子树两种
线索二叉树:空指针指向父节点
树和二叉树之间的转换
- 树转二叉树(兄弟相连 长兄为父 头树为根 孩子靠左)
- 二叉树转树(右孩子变为兄弟)
Huffman树(最优二叉树)
-
1
2
3
4
5
6
7for(i=n+1;i<=m;++i)
{ //建哈夫曼树,并保存树的父子关系
Select(Ht,i-1,s1,s2);
Ht[s1].parent=i;Ht[s2].parent=i;
Ht[i].lchild=s1;Ht[i].rchild=s2;
Ht[i].weight=Ht[s1].weight+Ht[s2].weight;
}1
2
3
4
5
6
7
8
9
10
11
12
13// 从叶子到根逆向求每个字符的哈夫曼编码
cd[n-1]='\0'; //编码结束符
int start;
for(i=1;i<=n;++i){ //逐个字符求哈夫曼编码
start=n-1;
for(c=i,f=Ht[i].parent;f!=0;c=f,f=Ht[f].parent)
{if(Ht[f].lchild==c)cd[--start]='0';
else cd[--start]='1';
}
//cd[n-1]='\0';
Hc[i]=(char *)malloc((n-start)*sizeof(char));
strcpy(Hc[i],&cd[start]);
}
-
图
图的遍历
深度优先搜索(DFS)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17void DFSTraverse(Graph G,int v)
{ /* 对图 G 作深度优先遍历 */
for (v=0; v<G.vexnum; ++v)
visited[v] = FALSE; // 访问标志数组初始化
for (v=0; v<G.vexnum; ++v)
if (!visited[v]) // 对尚未访问的顶点调用DFS
DFS(G, v);
}
void DFS(Graph G, int v) {
/* 从顶点v出发,深度优先搜索遍历连通图 G */
visited[v] = TRUE; //访问第v个顶点
VisitFunc(v);
for( w=FirstAdjVex(G,v) ; w!=0 ; w=NextAdjVex(G,v,w ) )
if (!visited[w])
DFS(G, w);
} // DFS广度优先搜索(BFS)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18void BFSTraverse(Graph G,int v) {
for (v=0; v<G.vexnum; ++v)
visited[v] = FALSE; //初始化
InitQueue(Q); //置空的辅助队列Q
for (v=0; v<G.vexnum; ++v) //最外层大循环,每个顶点都要搜索
if (!visited[v]) { //v尚未访问
visited[v]=TRUE; visit(v);
EnQueue(Q, v); //v入队列
while (!QueueEmpty(Q)) {
DeQueue(Q, u); //对头元素出队,记为u
for (w=FirstAdjVex(G,u); w; w=NextAdjVex(G,u,w))
if (! visisted[w]) {//w为u的尚未访问的邻接顶点
visisted[w] = TRUE;
EnQueue(Q,w);
}
}
}
}//BFSTraverse
最小生成树问题
Prim算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17void Prim(MGraph G, VertexType u)
{//用PRIM算法从第u个顶点出发构造网G的最小生成树T。
k=LocateVex(G,u);
closedge[k].lowcost = 0;
for (j=0; j<G.vexnum; ++j) //辅助数组初始化
if (j!=k) // adjvex, lowcost
closedge[j]={u, G.arcs[k][j].adj;}
for (i=1; i<G.vexnum; ++i)
{
k=minimum(closedge); //求出T的下一个节点
printf(closedge[k].adjvex, G.vexs[k]); //输出生成树的边
closedge[k].lowcost = 0; // 第k顶点并入U集
for (j=0; j<G.vexnum; ++j) //更新节点间的距离
if (G.arc[k][j].adj<closedge[j].lowcost)
closedge[j]={G.vexs[k], G.arcs[k][j].adj};
}
}Kruskal算法(并查集思路)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34struct Edge{
int a;
int b;
int weight;
}; //a->b=weight
void Kruskal(MGraph G) //图以边集数组的形式存储
{
int parent[MAXVEX];
for(i=0;i<G->numVertexes;++i) //初始化,
parent[i]=0;
//元素值parent[i]非0时表示结点i与parent[i]之间的边已确定
i=min(G->edges).index //找到最短边
while(1)
{
n=Find(parent,G->edges[i].a);
m=Find(parent,G->edges[i].b);
if(n!=m) //m,n原本没有连接(避免成环)
{
parent[n]=m; //连接m,n
printf("xxx");
}
i=min(G->edges).index //找到最短边
if(IsCompleted(parent)) //判断最小生成树是否完成
return;
}
}
int Find(int *parent,int f) //找到f的最前父节点
{
while(parent[f]!=0)
f=parent[f];
return f;
}
最短路径问题
Dijkstra算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30void Dijkstra(MGraph G, int v0, PathMatrix *P, ShortPathTable *D)
{
for (v=0; v<G.vexnum; ++v) //初始化
{
final[v] = FALSE; //判断是否得到最短路径
D[v] = G.arcs[v0][v];
if (D[v]<INFINITY) { P[v0][v] = v;}
for (w=0; w<G.vexnum; ++w)
if(G.arcs[v][w]<INFINITY)
P[v][w] = w;
}
D[v0]=0; final[v0]=TRUE
for (i=1; i<G.vexnum; ++i)
{
min = INFINITY;
for (w=0; w<G.vexnum; ++w) //找到最近顶点
if (!final[w])
if (D[w]<min) { v=w; min = D[w] } //w顶点离v0顶点更近
final[v] = TURE; //离v0顶点最近的v加入S集
for (w=0; w<G.vexnum; ++w) //更新当前最短路径及距离
{
if (!final[w] && (D[v]+G.arcs[v][w]<D[w]))
{
D[w] = D[v] + G.arcs[v][w];
P[v0][w] = v;
}
}
}
}Floyd算法(kij算法)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20void Floyd(MGraph G,PathMatrix *P, ShortPathTable *D)
{
for(v=0;v<G->numVertexes;++v) //初始化
{
for(w=0;w<G->numVertexes;++w)
{
D[v][w]=G->arc[v][w];
P[v][w]=w;
}
}
for(k=0;k<G->numVertexes;++k)
for(v=0;v<G->numVertexes;++v)
for(w=0;w<G->numVertexes;++w)
if( D[v][w]>D[v][k]+D[k][w] )
{
D[v][w] = D[v][k] + D[k][w];
P[v][w] = P[v][k];
}
}
查找
二分查找(O(log(n)))
1
2
3
4
5
6
7
8
9
10
11int Search_Bin ( SSTable ST , KeyType key )
{ low = 1; high = ST.length; // 置区间初值
while (low <= high) //二分查找
{ mid = (low + high) / 2;
if (EQ (key , ST.elem[mid].key) )
return mid; // 找到待查元素
else if ( LT (key , ST.elem[mid].key) )
high = mid - 1; // 继续在前半区间进行查找
else low = mid + 1; // 继续在后半区间进行查找
}
return 0;二叉查找树
1
2
3
4
5
6
7
8BiTree SearchBST (BiTree T, KeyType key, )
{ // 在根指针 T 所指二叉排序树中递归地查找其关键字等于 key的数据元素,若查找成功,则//返回指向该数据元素 的指针否则表明查找不成功,返回空指针NULL
if( (!T)||EQ(key,T->data.key) ) return(T);
else
if ( LT(key,T->data.key) )
return(SearchBST(T->lchild,key));
else return (SearchBST(T->rchild,key));
} // SearchBST二叉平衡树(log(n))
Hash表冲突处理方法
- 开放定址法
- 线性探测法
Hi=(Hash(key)+di) mod m
(di为i) - 二次探测法
Hi=(Hash(key)±di) mod m
(di为i的平方) - 若di=伪随机序列,就称为伪随机探测法
- 线性探测法
- 链地址法
- 再哈希法
Hi=RHi(key)
- 建立一个公共溢出区
- 开放定址法
排序
- 稳定排序与不稳定排序
内部排序与外部排序
插入排序
- 直接插入排序(时间复杂度O(n2),空间复杂度O(1),稳定排序)
- 折半插入排序,2-路插入排序,表插入排序
- 希尔排序(时间复杂度(O(n1.25)~O(1.6n1.25)),空间复杂度O(1),不稳定排序)
交换排序
- 冒泡排序((时间复杂度O(n2),空间复杂度O(1),稳定排序))
- 优化方式:
- 双向冒泡排序
- 设置一个标记变量flag,当循环中没有交换数据时,停止循环。
- 优化方式:
- 快速排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27void quick_sort(int s[],int l,int r)
{
if(l < r)
{
int i=l,j=r,m=s[l];
while(i<j)
{
while(i<j && s[j]>=m) //从右到左找到第一个小于m的数
j--;
while(i<j && s[i]<=m) //从左往右找到第一个大于m的数
i++;
if(i<j)
{
int temp1 = s[j];
s[j] = s[i];
s[i] = temp1;
}
}
int temp2 = s[j];
s[j] = s[i];
s[i] = temp2;
quick_sort(s,i,m-1); //递归调用
quick_sort(s,i+1,r);
}
}
- 冒泡排序((时间复杂度O(n2),空间复杂度O(1),稳定排序))
选择排序
- 简单选择排序
- 锦标赛排序(时间复杂度O(nlog2n),空间复杂度O(n),稳定排序)
堆排序(时间复杂度O(nlog2n),空间复杂度O(1),不稳定排序)
1
2
3
4
5
6
7
8void HeapSort (HeapType &H ) {
for ( i = H.length / 2; i >0; - - i )
HeapAdjust(H,i, H.length ); //for,建立初始堆
for ( i = H.length; i > 1; - -i) {
H.r[1] ←→ H.r[i]; //交换,要借用temp
HeapAdjust( H, 1,i-1 ); //重建最大堆, i-1=m
}
}1
2
3
4
5
6
7
8
9
10
11
12
13HeapAdjust(HeapType *H,current,m){
child = 2 * current;
while(child<=m){
//选取child中的较大值
child = (H[child].key>H[child+1].key) ? child : child+1 ;
if(H[current].key<H[child].key){ //将较大值上移
H[current] ←→ H[child];
current = child;
child *= 2;
}
else break;
}
}
归并排序(时间复杂度O(nlog2n),空间复杂度O(n),稳定排序)
1
2
3
4
5
6
7
8
9
10void MSort (SR[ ],&TR1[ ],s, t) {
// 将无序的SR[s…t]归并排序为TR1[s…t]
if ( s==t ) TR1[s]=SR[s];
else{
m=(s+t)/2;
MSort (SR,&TR2,s, m);
MSort (SR,&TR2,m+1, t );
Merge(TR2, TR1, s, m, t );
}
}
1 | void Merge (SR,&TR,i, m, n) { |
基数排序(时间复杂度O(d(n+radix)),空间复杂度(O(n+radix)),稳定排序)
- MSD 最高位优先法
- LSD 最低位优先法
八大排序的比较
八大排序的比较