数据结构简介
-
在团队有一些其他系的同学可能并没有学过数据结构,所以在此就拿出之前上数据结构课程时候的总结与大家分享。由于数据结构这门课程与使用语言无关，所以以下内容使用的是类c语言的伪码编写，应该比较容易看懂。
伪码基本操作
比较
- 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树(最优二叉树)
for(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; }// 从叶子到根逆向求每个字符的哈夫曼编码 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)
void 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)
void 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算法
void 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算法(并查集思路)
struct 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算法
void 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算法)
void 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)))
int 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;- 二叉查找树
BiTree 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，当循环中没有交换数据时，停止循环。
- 优化方式：
- 快速排序
void 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),不稳定排序)
void 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 } }HeapAdjust(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),稳定排序)
void 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 ); } }void Merge (SR，&TR，i, m, n) { // 将有序的SR[i…m]和SR[m+1…n]归并为有序的TR[i…n] for(k=i , j=m+1; i<=m && j<=n; ++k ) { if ( SR[i]<= SR[j] ) TR[k]=SR[i++]; else TR[k]=SR[j++]; // 将两个SR记录由小到大并入TR } // for if (i<=m) TR[k…n]=SR[i…m]; // 将剩余的SR[i…m]复制到TR if (j<=n) TR[k…n]=SR[j…n]; // 将剩余的SR[j…n]复制到TR } // Merge-
基数排序(时间复杂度O(d(n+radix))，空间复杂度(O(n+radix)),稳定排序)
- MSD 最高位优先法
- LSD 最低位优先法
-
八大排序的比较
参考资料
