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

伪码基本操作

比较

  • 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
      7
      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;
      }
      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
      17
      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)

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      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算法

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      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算法(并查集思路)

      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
      34
      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算法

      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
      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算法)

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      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)))

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    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;
  • 二叉查找树

    1
    2
    3
    4
    5
    6
    7
    8
    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,当循环中没有交换数据时,停止循环。
    • 快速排序
      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
      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),不稳定排序)

      1
      2
      3
      4
      5
      6
      7
      8
      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
      }
      }
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      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),稳定排序)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    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 );
    }
    }
1
2
3
4
5
6
7
8
9
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 最低位优先法
  • 八大排序的比较

    八大排序的比较
    八大排序的比较

参考资料

八大排序源码与分析