华中科技大学数据结构复习资料

众所周知，数据结构是一门写伪代码的学科，特在此总结各路伪码给大家参考

伪码基本操作

比较

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(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 最低位优先法
八大排序的比较

八大排序的比较

参考资料

八大排序源码与分析

华中科技大学数据结构复习资料

伪码基本操作

比较

线性表

栈

队列

串

广义表

图

基础知识点

线性表

栈与队列

二叉树

图

查找

排序

参考资料

谢谢支持~