数据结构必背算法

学习笔记
字数统计: 4.2k   |   阅读时长≈ 18 分钟

矩阵快速转置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*稀疏矩阵用三元组表示。
需要设置num和cpot两个向量。
num[col]表示矩阵M中第col列中非零元的个数。
copt[col]指示M中第col列的第一个非零元在转置后的三元组的位置。
cpot[1] = 1; cpot[col] = cpot[col - 1] + num[col - 1],2<=col<=列数nu；
*/
Status FastTransposeSMatrix( TSMatrix M, TSMatrix &T) {
    T.mu = M.nu; T.nu = M.mu; T.tu = M.tu; //T的行数列数=M的列数行数，非零元个数相同
    if(T.tu) {
        for(col = 1; col < M.nu; ++col) num[col] = 0;
        for(t = 1; t <= M.nu; ++t) ++num[M.data[t].j]; //求M中每一列含非零元个数
        cpot[1] = 1;
        for(col =  2; col <= M.nu; ++col)
            cpot[col] = cpot[col - 1] + num[col - 1];
        for(p = 1; p <= M.tu; ++p) {
            col = M.data[p].j; q = cpot[col];
            T.data[q].i = M.data[p].j; T.data[q].j = M.data[p].i;
            T.data[q].e = M.data[p].e; ++cpot[col];
        }
    }
}

二叉树的遍历

  1. 先序遍历：根左右
    递归算法

    1
    2
    3
    4
    5
    6
    7
    void PreOrder(BiTree T) {
     if(T!=NULL) {
           visit(T) ; //访问根结点
         PreOrder(T->lchild) ; //递归遍历左子树
         PreOrder(T->rchild) ; //递归遍历右子树
    }
    }

    非递归算法

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    void PreOrder(BiTree T) {
     InitStack(S); BiTree p=t;     //初始化栈S，p是遍历指针
     while(p || !IsEmpty(S)) {     //栈不空或p不空时循环
         if(p) {                    //遍历左子树
             visit(p); Push(S, p);//访问当前节点并入栈
             p = p->lchild;        //左孩子非空下一次继续遍历左孩子
         } else {                //出栈，访问栈结点右子树
             Pop(S, p);            //栈顶元素出栈
             p=p->rchild;        //访问右子树
         }
     }
    }

  2. 中序遍历：左根右

递归算法

1
2
3
4
5
6
7
void InOrder(BiTree T) {
    if(T!=NULL) {
        InOrder(T->lchild) ; //递归遍历左子树
        visit(T) ; //访问根结点
        InOrder(T->rchild) ; //递归遍历右子树
  }
}

非递归算法

1
2
3
4
5
6
7
8
9
10
11
12
void MidOrder(BiTree T) {
    InitStack(S); BiTree p=t;     //初始化栈S，p是遍历指针
    while(p || !IsEmpty(S)) {     //栈不空或p不空时循环
        if(p) {                    //遍历左子树
            Push(S, p);            //当前节点入栈
            p = p->lchild;        //左孩子非空下一次继续遍历左孩子
        } else {                //出栈，访问栈结点右子树
            Pop(S, p); visit(p); //栈顶元素出栈,并访问
            p=p->rchild;        //下一次循环，访问右子树
        }
    }
}
  1. 后序遍历：左右根

递归算法

1
2
3
4
5
6
7
void PostOrder(BiTree T) {
    if(T!=NULL) {
        PostOrder(T->lchild) ; //递归遍历左子树
        PostOrder(T->rchild) ; //递归遍历右子树
          visit(T) ; //访问根结点
    }
}

非递归算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void PostOrder(BiTree T) {
    InitStack(S);
    p = T;                        //p是遍历指针
    r = NULL;                    //r指向最近访问过的结点，以分清从左子树返回还是右子树返回
    while(p || !IsEmpty(S)) {
        if(p) {                    //走到最左边
            push(S, p);
            p = p->lchild;
        } else {                //向右
            GetTop(S, p);        //读栈顶结点
            if(p->rchild && p->rchild!=r) { //若左子树存在且未被访问过
                p = p->rchild;    //转向右
                push(S, p);        //压入栈
                p = p->lchild;    //再走到左
            } else {            //否则
                pop(S, p);        //将结点弹出
                visit(p->data);    //访问该结点
                r = p;             //记录最近访问过的结点
                p = NULL;        //结点访问完毕后，重置p指针
            }
        }
    }
}
  1. 层次遍历

层次遍历常用来求每个元素所在层数、某层结点个数、树的最大宽度、树的高度等
求树的高度的算法，借助队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int BtDepth(BiTree T) {
    if(!T) return 0;    //树空，高度为0
    int front = -1, rear = -1;
    int last = 0, level = 0;    //last指向当前层的最右结点
    BiTree Q[MaxSize];            //设置队列Q
    Q[++rear] = T;                //根结点入队
    BiTree p;
    while(front < rear) {        //队不空，则循环
        p=Q[++front];            //队列元素出队，访问当前结点
        if(p->lchild) 
            Q[++rear] = p->lchild;    //左孩子入队
        if(p->rchild)
            Q[++rear] = p->rchild;    //右孩子入队
        if(front == last) {
            level++;                //层数加一
            last = rear;            //last指向下层最后一个结点
        }
    }
    return level;
}

图的遍历

记忆非递归算法更为合适，因为仅仅是把队列和栈替换。
全局变量：

1
2
Boolean visited[MAX];            //访问标志数组
Status (*VisitFunc)(int V);        //函数变量
  1. 广度优先搜索：

类似于树的按层次遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//按广度优先非递归遍历图G。使用辅助队列Q和访问标志数组visited
//辅助队列Q保存正在访问顶点的下一层顶点
//visited标志顶点是否被访问过，防止被多次访问。
void BFSTraverse(Graph G, Status (*Visit)(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; 
            EnQueue(Q, v);            //v入队列
            while(!QueueEmpty(Q)) {
                DeQueue(Q, u);        //队头元素出队并置为u
                Visit(u);            //访问u
                for(w = FirstNeighbor(G, u); w >= 0; w = NextNeighbor(G, u, w))
                    if(!visited[w]) {        //w为u的尚未访问的临接顶点
                        visited[w] = TRUE;
                        EnQueue(Q, w);
                    }
            }
        }
}

  1. 深度优先搜索：
    递归算法

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    void DFSTraverse(Graph G, Status (*Visit)(int v)) {
    VisitFunc = Visit;        //使用全局变量VisitFunc，使DFS不必设函数指针参数。
    for(v = 0; v < G.vexnum; ++v) visited[v] = FALSE; //访问标志数组初始化
    for(v = 0; v < G.vexnum; ++v)
      if(!visited[v]) DFS(G, v);    //对未访问的顶点调用DFS
    }

    //从第v个顶点出发递归地深度优先遍历图G
    void DFS(Graph G, int v) {
        visited[v] = TRUE; VisitFunc(v);    //访问第v个顶点
        for (w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w))
            if(!visited[w]) DFS(G, w);    //对v的尚未访问的邻接顶点w递归调用DFS
    }

    非递归算法

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    //按深度优先非递归遍历图G，使用辅助栈S和访问标记数组visited
    //栈S来记忆下一步可能访问的顶点
    //visited标记顶点是否被访问过，防止多次访问。
    void DFS(Graph G, int v) {
        int w;            //顶点序号
        InitStack(S);    //初始化栈S
        for(i = 0; i < G.vexnum; i++) visited[i] = FALSE;
        for(v = 0; v < G.vexnum; ++v) 
            if(!visited[v]) {
                Push(S, v); visited[v] = TRUE;    //v入栈
                while(!IsEmpty(S)) {
                    k = Pop(S); visit(k);    //访问栈顶结点
                    for(w = FirstNeighbor(G, k); w >= 0; w = NextNeighbor(G, k, w))
                    if(!visited[w]) {
                        Push(S, w);
                        visited[w] = TRUE;
                    }
                }
            }
    }

最小生成树算法

  1. Prim算法：适合边稠密的图

    1. 算法思想：初始时从图中任取一顶点加入树T，此时树中只含有一个顶点，之后选择一个与当前T中顶点集合距离最近的顶点，并将该顶点和相应的边加入T，每次操作后T中顶点数和边数都增1.以此类推，直至图中所有的顶点都并入T，得到的T就是最小生成树。

    2. 所需添加的数据结构closedge[]，记录从U到V-U具有最小代价的边

      1
      2
      3
      4
      struct {
      VertexType adjvex;    //最小代价的边在U中依附的顶点
      VRType lowcost;        //最小代价的边的权值；
      } closedge[ MAX_VERTEX_NUM ]

    3. 算法实现（一般不考）

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      void PRIM(MGraph G, VertexType u) {
      k = LocateVex(G, u);
      for(j = 0; j < G.vexnum; ++j)     //初始化辅助数组
        if(j != k) closedge[j] = {u, G.arcs[k][j].adj};
      closedge[k].lowcost = 0;        //初始，U={u}
      for(i = 1; i < G.vexnum; ++i) {
        k = minimum(closedge);        //离当前生成树距离最短的点作为下一顶点
        printf(closedge[k].adjvex, G.vexs[k]);    //输出生成树的边
        closedge[k].lowcost = 0;    //将该点并入生成树U集
        for(j = 0; j < G.vexnum; ++j) //更新未并入U的点离生成树的距离。
            if(G.arcs[k][j].adj < closedge[j].lowcost)    
                closedge[j] = {G.vexs[k], G.arcs[k][j].adj};
      }
      }

    4. 每一步的状态表（重要）

1A18DDB3-14CA-433F-8F92-A97B744CB996.jpeg

  1. Kruskal算法：适合边稀疏而顶点较多的图
    1. 算法思想：初始时为只有n个顶点而无边的非连通图T={V, {} }，每个顶点自成一个连通分量，然后按照边的权值由小到大的顺序，不断选取当前未被选取过且权值最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入T，否则舍弃此边而选取下一条权值最小的边。以此类推，直至T中所有顶点都在一个连通分量上。

最短路径算法

  1. Dijkstra算法，求单个点到其他点的最短路径。

    1. 所需辅助数组

      1. dist[]：记录从源点到其他各顶点当前的最短路径长度，如两个点未直接相连置为∞
      2. path[]：表示从源点到顶点i之间最短路径上i之前的一个结点。用于最后追溯最短路径。

    2. 算法过程：贪心策略，按长度递增的次序产生各最短路径。

      1. 初始化dist，和集合S={0}

      2. 从顶点集合V-S中选出dist最小的点 j ，并入S

      3. 更新dist[k] = dist[j] + arcs[j][k] < dsit[k] ? dist[j]+arcs[j][k] : dsit[k]

      4. 重复2-3步，直到所有点都并入S

    3. 求解过程表（重要）

850BE2D4-C874-45CF-B587-1C2E74312442.jpeg

  1. Floyd算法，求所有点间的最短距离。

    1. 算法思想：用每个顶点作为中间结点计算路径长度并与原路径长度进行比较，更新矩阵为较小的值。重复n次就得到所有的最短路径长度。

    2. 算法伪代码（不重要）要会算每次迭代的矩阵，初始的矩阵为邻接矩阵。

      1
      2
      3
      4
      5
      6
      7
      8
      void FLOYD(Mgraph G, DistancMatrix D) {
      for(u = 0; u < G.vexnum; ++u)
        for(v = 0; v < G.vexnum; ++v)
            for(w = 0; w < G.vexnum; ++w)
                if(D[v][u] + D[u][w] < D[v][w]) { //从v经过u到w的一条路径更短。
                    D[v][w] = D[v][u] + D[u][w];
                }
      }

排序算法

插入排序

  1. 直接插入排序

思想：假设前部分序列已经有序，从后部分无序序列中选择元素插入到前面有序序列的合适位置，最终整体有序。是稳定的排序方法。

1
2
3
4
5
6
7
8
9
10
//A[0] 用作哨兵, n为数组长度
void InsertSort(ElemType A[], int n) {
    for(i = 2; i <= n; i++)        // 依次将A[2]-A[n]插入到前面已排序序列
        if(A[i] < A[i-1]) {        //若A[i]<A[i-1]
            A[0] = A[i];        //把A[i]复制为哨兵
            for(j = i-1; A[0] < A[j]; --j)    //在前端有序队列中查找插入位置
                A[j+1] = A[j];    //将前面有序序列的元素后移，空出位置。
            A[j+1] = A[0];        //插入到空出来的位置。
        }
}
  1. 折半插入排序

思想：将直接插入排序中移位操作中的比较单独提出来。变成，折半查找出元素的待插入位置，然后再移动元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void InsertSort(ElemType A[], int n) {
    for(i = 2; i <= n; ++i) {
        A[0] = A[i];
        low = 1; high = i - 1;    //设置折半查找范围
        while(low <= high) {    //折半查找
            mid = (low + high) / 2;
            if(A[mid] > A[0]) high = mid - 1;
            else low = mid + 1;
        }
        for(j = i-1; j >= high+1; --j)
            A[j+1] = A[j];
        A[high+1] = A[0];    //插入
    }
}
  1. 希尔排序

思想（重要）：先将待排序表分割成若干由相隔某个增量的记录组成的一个子表，对各个子表分别进行直接插入排序，当整个表中元素已经基本有序时，再对全体记录进行一次直接插入排序。
不稳定的排序方法。

交换排序

  1. 冒泡排序

思想：从后往前两两比较相邻元素的值，若为逆序，则交换他们，直到序列比较完。若第n趟结束时没有交换，则冒泡排序结束。是一种稳定的排序方法。

1
2
3
4
5
6
7
8
9
10
11
void BubbleSort(ElemType A[], int n) {
    for(i = 0; i < n-1; i++) {
        flag = false;
        for(j = n-1; j > i; j--)     //一趟冒泡过程
            if(A[j-1] > A[j]) {
                swap(A[j-1], A[j]);
                flag = true;
            }
        if(flag == false) return;    //本趟遍历后没有发生交换，已经有序
    }
}
  1. 快速排序（重要）

思想：基于分治思想。通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，再分别对这两部分记录继续进行快速排序。 不稳定的排序方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//一趟快速排序的过程，划分算法
int Partition(ElemTYpe A[], int low, int high) {
    pivot = A[low];            //用子表的第一个记录作枢轴记录，用pivot记录枢轴关键字
    while(low < high) {        //从表两边交替地向中间扫描
        while(low < high && A[high] >= pivot) --high;
        A[low] = A[high];    //将比枢轴小的记录移到低端
        while(low < high && A[low] <= pivot) ++low;
        A[high] = A[low];    //比枢轴大的记录移到高端
    }
    A[low] = pivot;            //枢轴记录到位
    return low;                //返回枢轴位置
}

//递归主程序
void QuickSort(ElemType A[], int low, int high) {
    if(low < high) {
        int pivotpos = Partition(A, low, high);
        QuickSort(A, low, pivotpos-1);
        QuickSort(A, pivotpos+1, high);
    }
}

选择排序

  1. 简单选择排序

思想：第i趟排序从L[i···n]中选择关键字最小的元素与L(i)交换。经过n-1次就得到有序。不稳定的排序算法

1
2
3
4
5
6
7
8
void SelectSort(ElemType A[], int n) {
    for(i = 0; i < n-1; ++i) {
        min = i;
        for(j = i+1; j < n; ++j) 
            if(A[j] < A[min]) min = j;
        if(min != i) swap(A[i], A[min]);
    }
}
  1. 堆排序

堆：是一颗完全二叉树，所有根结点小于等于或大于等于其孩子节点值。为方便运算，A[0]为空。
思想：若在输出堆顶的最小值后，使得剩余n-1个元素的序列重又建成一个堆，则输出n个元素的次小值。如此反复执行，便得到一个有序序列，这个过程称为堆排序。

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
//建立大根堆的算法
void BuildMaxHeap(ElemType A[], int len) {
    for(i = len/2; i > 0; i--)    //从非叶子结点开始调整
        HeadAdjust(A, i, len);
}

//调整以元素k为根的子树为堆
void HeadAdjust(ElemType A[], int k, int len) {
    A[0] = A[k];                        //A[0]暂存子树的根结点。
    for(i = 2*k; i <= len; i *= 2) {    //沿key较大的子节点向下筛选
        if(i < len && A[i] < A[i+1])
            i++;                        //取key较大的子节点的下标
        if(A[0] >= A[i]) break;            //筛选结束
        else {                            
            A[k] = A[i];                //将A[i]调整到双亲结点上
            k = i;                        //修改k，继续向下筛选。
        }
    }
    A[k] = A[0];                        //被筛选节点的值放入最终位置
}

//堆排序算法
void HeapSort(ElemType A[], int len) {
    BuildMaxHeap(A, len);
    for(i = len; i > 1; i--) {
        Swap(A[i], A[1]);
        HeadAdjust(A, 1, i-1);
    }
}

其他

  1. 归并排序

思想：将两个或两个以上的有序表组合成一个新的有序表。稳定的排序方法

1
2
3
4
5
6
7
8
9
10
11
12
ElemType *B = (ElemTYpe *)malloc((n+1) * sizeof(ElemType));
void Merge(ElemType A[], int low, int high) {
    for(k = low; k <= high; k++) 
        B[k] = A[k];
    for(i = low, j = mid+1; k = i; i <= mid && j <= high; k++) {
        if(B[i] <= B[j])
            A[k] = B[i++];
        else A[k] = B[j++];
    }
       while(i <= mid) A[k++] = B[i++];    //如果表1未检测完，直接复制
    while(j <= high) A[k++] = B[j++];    //如果表2未检测完，直接复制
}
  1. 基数排序

思想：一种借助多关键字排序的思想对单逻辑关键字进行排序的方法。
链式基数排序：收集时是从下往上收集的。
AFA561CF-09F2-4A79-823D-B99981F78B38.jpeg

真题中的多次考到的算法

树的孩子兄弟表示法的遍历

以求家族中共有多少代并输出最后一代的所有成员为例。
思想：根据孩子兄弟表示法，创建结构体，包括名字，第一个孩子节点和兄弟节点。再将此结构体与其结点高度组成一个新结构体（在不同类型的题目中，该结构体内容根据需要进行修改）。通过求层次遍历最后一个结点的高度得到共有多少代，再通过遍历所有结点找到高度最大的结点，即最后一代。

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
35
36
37
38
39
40
41
42
typedef struct {
    char name;
    struct BTNode *firstchild;
    struct BTNode *brother;
}BTNode;

typedef struct {
    int lno; //表示结点高度;
    BTNode *p;
}NodeInfo;         //这个结构体及后续队列的变形应用是精髓。

void FamilyTree(BTNode &b) {
    NodeInfo Q[maxsize];
    int front = 0, rear = 0; //初始化自定义队列
    int Lno;        //暂存结点高度；
    int i, j = 0;    //j记录最后一代人数
    BTNode *q;
    ++rear;
    Q[rear].p = b; Q[rear].lno=1;
    while (rear != front) {
        ++front;
        q = Q[front].p; Lno = Q[front].lno;    //出队
        if(q->brother != null) {
            ++rear;
            Q[rear].p = q->brother;
            Q[rear].lno = Lno;        //兄弟结点与该结点高度一致；
        }
        if(q->firstchild != null) {
            ++rear;
            Q[rear].p = q->firstchild;
            Q[rear].lno = Lno + 1;    //孩子结点比当前结点高1
        }
    }
    print(Lno); //输出共有多少代
    for(i = 1; i <= rear; i++) {    //输出最后一代成员并计算人数
        if(Q[i].lno == Lno) {
            j++;
            print(Q[i].p->name);
        }
    }
    print(j);
}
  • 版权声明： 本博客所有文章除特别声明外，著作权归作者所有。转载请注明出处！
  • Copyrights © 2022-2024 Konsin
  • 访问人数: | 浏览次数:

请我喝杯咖啡吧~

支付宝
微信