• 数据结构手写算法整理(考研)


    题目限制O(n+e)用邻接表初始化图。
    题目限制O(n^2)用邻接矩阵初始化图。
    邻接表的适用范围大于邻接矩阵

    拓扑排序
    利用拓扑排序判断图中是否存在有向回路

    prim算法

    :增加一顶点求最小生成树o(n^2)
    适用于求边稠密网的最小支撑树
    邻接矩阵代码实现:

    1. 基本定义
    // 邻接矩阵
    typedef struct _graph
    {
        char vexs[MAX];       // 顶点集合
        int vexnum;           // 顶点数
        int edgnum;           // 边数
        int matrix[MAX][MAX]; // 邻接矩阵
    }Graph, *PGraph;
    
    // 边的结构体
    typedef struct _EdgeData
    {
        char start; // 边的起点
        char end;   // 边的终点
        int weight; // 边的权重
    }EData;
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    1. 普里姆算法
    /*参数说明:
     *       G -- 邻接矩阵图
     *   start -- 从图中的第start个元素开始,生成最小树
     */
    void prim(Graph G, int start)
    {
        int min,i,j,k,m,n,sum;
        int index=0;   // prim最小树的索引,即prims数组的索引
        char prims[MAX];   // prim最小树的结果数组
        int weights[MAX];  // 顶点间边的权值
       // prim最小生成树中第一个数是"图中第start个顶点"
       //因为是从start开始的。
        prims[index++] = G.vexs[start];
       // 初始化"顶点的权值数组",
       // 将每个顶点的权值初始化为"第start个顶点"到"该顶点"的权值。
        for (i = 0; i < G.vexnum; i++ )
            weights[i] = G.matrix[start][i];
       // 将第start个顶点的权值初始化为0。
       // 可以理解为"第start个顶点到它自身的距离为0"。
        weights[start] = 0;
        for (i = 0; i < G.vexnum; i++)
        {
      //由于从start开始的,因此不需要再对第start个顶点进行处理。
            if(start == i)
                continue;
            j = 0;
            k = 0;
            min = INF;
         // 在未被加入到最小生成树的顶点中,找出权值最小的顶点。
            while (j < G.vexnum)
            {
     // 若weights[j]=0,意味着"第j个节点已经被排序过
     //(或者说已经加入了最小生成树中)。
                if (weights[j] != 0 && weights[j] < min)
                {
                    min = weights[j];
                    k = j;
                }
                j++;
            }
     // 经过上面的处理后,在未被加入到最小生成树的顶点中,
     //权值最小的顶点是第k个顶点。
    // 将第k个顶点加入到最小生成树的结果数组中
            prims[index++] = G.vexs[k];
    // 将"第k个顶点的权值"标记为0
    //意味着第k个顶点已经排序过了(或者说已经加入了最小树结果中)。
            weights[k] = 0;
    // 当第k个顶点被加入到最小生成树的结果数组中之后
    //更新其它顶点的权值。
            for (j = 0 ; j < G.vexnum; j++)
            {
             // 当第j个节点没有被处理,并且需要更新时才被更新。
       if (weights[j] != 0 && G.matrix[k][j] < weights[j])
                   weights[j] = G.matrix[k][j];
            }
        }
        // 计算最小生成树的权值
        sum = 0;
        for (i = 1; i < index; i++)
        {
            min = INF;
            // 获取prims[i]在G中的位置
            n = get_position(G, prims[i]);
            // 在vexs[0...i]中,找出到j的权值最小的顶点。
            for (j = 0; j < i; j++)
            {
                m = get_position(G, prims[j]);
                if (G.matrix[m][n]<min)
                    min = G.matrix[m][n];
            }
            sum += min;
        }
        // 打印最小生成树
        printf("PRIM(%c)=%d: ", G.vexs[start], sum);
        for (i = 0; i < index; i++)
            printf("%c ", prims[i]);
        printf("\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
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78

    Kruskal

    :增加一条边求最小生成树
    适用于稀疏网络

    void kruskal(Graph G)
    {
        int i,m,n,p1,p2;
        int length;
        int index = 0;          // rets数组的索引
        int vends[MAX]={0};     
        // 用于保存"已有最小生成树"中每个顶点在该最小树中的终点。
        EData rets[MAX];        // 结果数组,保存kruskal最小生成树的边
        EData *edges;           // 图对应的所有边
    
        // 获取"图中所有的边"
        edges = get_edges(G);
        // 将边按照"权"的大小进行排序(从小到大)
        sorted_edges(edges, G.edgnum);
    
        for (i=0; i<G.edgnum; i++)
        {
            p1 = get_position(G, edges[i].start); // 获取第i条边的"起点"的序号
            p2 = get_position(G, edges[i].end);   // 获取第i条边的"终点"的序号
    
            m = get_end(vends, p1);      // 获取p1在"已有的最小生成树"中的终点
            n = get_end(vends, p2);      // 获取p2在"已有的最小生成树"中的终点
            // 如果m!=n,意味着"边i"与"已经添加到最小生成树中的顶点"没有形成环路
            if (m != n)
            {
                vends[m] = n;           // 设置m在"已有的最小生成树"中的终点为n
                rets[index++] = edges[i];   // 保存结果
            }
        }
        free(edges);
        // 统计并打印"kruskal最小生成树"的信息
        length = 0;
        for (i = 0; i < index; i++)
            length += rets[i].weight;
        printf("Kruskal=%d: ", length);
        for (i = 0; i < index; i++)
            printf("(%c,%c) ", rets[i].start, rets[i].end);
        printf("\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
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39

    迪杰斯特拉(Dijkstra)算法

    最短路径算法,用于计算一个节点到其他节点的最短路径。

    /*
     * Dijkstra最短路径。
     * 即,统计图(G)中"顶点vs"到其它各个顶点的最短路径。
     * 参数说明:
     *        G -- 图
     *       vs -- 起始顶点(start vertex)。即计算"顶点vs"到其它顶点的最短路径。
     *     prev -- 前驱顶点数组。即,prev[i]的值是"顶点vs"到"顶点i"的最短路径所经历的全部顶点中,位于"顶点i"之前的那个顶点。
     *     dist -- 长度数组。即,dist[i]是"顶点vs"到"顶点i"的最短路径的长度。
     */
    void dijkstra(Graph G, int vs, int prev[], int dist[])
    {
        int i,j,k;
        int min;
        int tmp;
        int flag[MAX];      
        // flag[i]=1表示"顶点vs"到"顶点i"的最短路径已成功获取。
        // 初始化
        for (i = 0; i < G.vexnum; i++)
        {
            flag[i] = 0;              // 顶点i的最短路径还没获取到。
            prev[i] = 0;              // 顶点i的前驱顶点为0。
            dist[i] = G.matrix[vs][i];
            // 顶点i的最短路径为"顶点vs"到"顶点i"的权。
        }
        // 对"顶点vs"自身进行初始化
        flag[vs] = 1;
        dist[vs] = 0;
    
        // 遍历G.vexnum-1次;每次找出一个顶点的最短路径。
        for (i = 1; i < G.vexnum; i++)
        {
            // 寻找当前最小的路径;
            // 即,在未获取最短路径的顶点中,找到离vs最近的顶点(k)。
            min = INF;
            for (j = 0; j < G.vexnum; j++)
            {
                if (flag[j]==0 && dist[j]<min)
                {
                    min = dist[j];
                    k = j;
                }
            }
            // 标记"顶点k"为已经获取到最短路径
            flag[k] = 1;
            // 修正当前最短路径和前驱顶点
            // 即,当已经"顶点k的最短路径"之后
            //更新"未获取最短路径的顶点的最短路径和前驱顶点"。
            for (j = 0; j < G.vexnum; j++)
            {
                tmp = (G.matrix[k][j]==INF ? INF : (min + G.matrix[k][j])); 
                // 防止溢出
                if (flag[j] == 0 && (tmp  < dist[j]) )
                {
                    dist[j] = tmp;
                    prev[j] = k;
                }
            }
        }
        // 打印dijkstra最短路径的结果
        printf("dijkstra(%c): \n", G.vexs[vs]);
        for (i = 0; i < G.vexnum; i++)
            printf("  shortest(%c, %c)=%d\n", G.vexs[vs], G.vexs[i], dist[i]);
    }
    
    • 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
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63

    弗洛伊德(Floyd)算法

    /*
     * floyd最短路径。
     * 即,统计图中各个顶点间的最短路径。
     *
     * 参数说明:
     *        G -- 图
     *     path -- 路径。path[i][j]=k表示,"顶点i"到"顶点j"的最短路径会经过顶点k。
     *     dist -- 长度数组。即,dist[i][j]=sum表示,"顶点i"到"顶点j"的最短路径的长度是sum。
     */
    void floyd(Graph G, int path[][MAX], int dist[][MAX])
    {
        int i,j,k;
        int tmp;
    
        // 初始化
        for (i = 0; i < G.vexnum; i++)
        {
            for (j = 0; j < G.vexnum; j++)
            {
                dist[i][j] = G.matrix[i][j];    // "顶点i"到"顶点j"的路径长度为"i到j的权值"。
                path[i][j] = j;                 // "顶点i"到"顶点j"的最短路径是经过顶点j。
            }
        }
    
        // 计算最短路径
        for (k = 0; k < G.vexnum; k++)
        {
            for (i = 0; i < G.vexnum; i++)
            {
                for (j = 0; j < G.vexnum; j++)
                {
                    // 如果经过下标为k顶点路径比原两点间路径更短,则更新dist[i][j]和path[i][j]
                    tmp = (dist[i][k]==INF || dist[k][j]==INF) ? INF : (dist[i][k] + dist[k][j]);
                    if (dist[i][j] > tmp)
                    {
                        // "i到j最短路径"对应的值设,为更小的一个(即经过k)
                        dist[i][j] = tmp;
                        // "i到j最短路径"对应的路径,经过k
                        path[i][j] = path[i][k];
                    }
                }
            }
        }
    
        // 打印floyd最短路径的结果
        printf("floyd: \n");
        for (i = 0; i < G.vexnum; i++)
        {
            for (j = 0; j < G.vexnum; j++)
                printf("%2d  ", dist[i][j]);
            printf("\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
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53

    快速排序

    使用分治法策略。
    它的基本思想是:选择一个基准数,通过一趟排序将要排序的数据分割成独立的两部分;其中一部分的所有数据都比另外一部分的所有数据都要小。然后,再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
    递归;
    快速排序流程:
    (1) 从数列中挑出一个基准值。
    (2) 将所有比基准值小的摆放在基准前面,所有比基准值大的摆在基准的后面(相同的数可以到任一边);在这个分区退出之后,该基准就处于数列的中间位置。
    (3) 递归地把"基准值前面的子数列"和"基准值后面的子数列"进行排序。

    /*参数说明:
     *     a -- 待排序的数组
     *     l -- 数组的左边界(例如,从起始位置开始排序,则l=0)
     *     r -- 数组的右边界(例如,排序截至到数组末尾,则r=a.length-1)
     */
    void quick_sort(int a[], int l, int r)
    {
        if (l < r)
        {
            int i,j,x;
            i = l;
            j = r;
            x = a[i];
            while (i < j)
            {
                while(i < j && a[j] > x)
                    j--; // 从右向左找第一个小于x的数
                if(i < j)
                    a[i++] = a[j];
                while(i < j && a[i] < x)
                    i++; // 从左向右找第一个大于x的数
                if(i < j)
                    a[j--] = a[i];
            }
            a[i] = x;
            quick_sort(a, l, i-1); /* 递归调用 */
            quick_sort(a, i+1, r); /* 递归调用 */
        }
    }
    
    • 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

    非递归:

    int _fastsortnonr(int* a, int left, int right)//栈实现快排子函数
    {
    	int pivot = left;
    	int begin = left, end = right, key = a[left];
    	while (begin < end)
    	{
    		while (begin < end && a[end] >= key) end--;
    		a[pivot] = a[end];
    		pivot = end;
    		while (begin < end && a[begin] <= key) begin++;
    		a[pivot] = a[begin];
    		pivot = begin;
    	}
    	a[pivot] = key;
    	return pivot;
    }
    void fastsortnonR(int* a, int left, int right)//栈实现快排,非递归
    {
    	steak* st;
    	init(&st);
    	push(&st, right);
    	push(&st, left);
    	while (!empty(&st))
    	{
    		int left = back(&st);
    		pop(&st);
    		int right = back(&st);
    		pop(&st);
    		int mid = _fastsortnonr(a, left, right);
    		if (mid + 1 < right)
    		{
    			push(&st, right);
    			push(&st, mid + 1);
    		}
    		if (left < mid - 1)
    		{
    			push(&st, mid - 1);
    			push(&st, left);
    		}
    	}
    }
    
    • 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

    堆排序

    堆的定义
    这里所说的堆是数据结构中的堆,而不是内存模型中的堆。堆通常是一个可以被看做一棵树,它满足下列性质:
    [性质一] 堆中任意节点的值总是不大于(不小于)其子节点的值;
    [性质二] 堆总是一棵完全树。
    将任意节点不大于其子节点的堆叫做最小堆或小根堆,而将任意节点不小于其子节点的堆叫做最大堆或大根堆。
    最大堆通常被用来进行"升序"排序,而最小堆通常被用来进行"降序"排序。

    /* 
     * (最大)堆的向下调整算法
     * 注:数组实现的堆中,第N个节点的左孩子的索引值是(2N+1),右孩子的索引是(2N+2)。
     *     其中,N为数组下标索引值,如数组中第1个数对应的N为0。
     * 参数说明:
     *     a -- 待排序的数组
     *     start -- 被下调节点的起始位置(一般为0,表示从第1个开始)
     *     end   -- 截至范围(一般为数组中最后一个元素的索引)
     */
    void maxheap_down(int a[], int start, int end)
    {
        int c = start;            // 当前(current)节点的位置
        int l = 2*c + 1;        // 左(left)孩子的位置
        int tmp = a[c];            // 当前(current)节点的大小
        for (; l <= end; c=l,l=2*l+1)
        {
            // "l"是左孩子,"l+1"是右孩子
            if ( l < end && a[l] < a[l+1])
                l++;        // 左右两孩子中选择较大者,即m_heap[l+1]
            if (tmp >= a[l])
                break;        // 调整结束
            else            // 交换值
            {
                a[c] = a[l];
                a[l]= tmp;
            }
        }
    }
    /*
     * 堆排序(从小到大)
     * 参数说明:
     *     a -- 待排序的数组
     *     n -- 数组的长度
     */
    void heap_sort_asc(int a[], int n)
    {
        int i;
        // 从(n/2-1) --> 0逐次遍历。遍历之后,得到的数组实际上是一个(最大)二叉堆。
        for (i = n / 2 - 1; i >= 0; i--)
            maxheap_down(a, i, n-1);
        // 从最后一个元素开始对序列进行调整,不断的缩小调整的范围直到第一个元素
        for (i = n - 1; i > 0; i--)
        {
            // 交换a[0]和a[i]。交换后,a[i]是a[0...i]中最大的。
            swap(a[0], a[i]);
            // 调整a[0...i-1],使得a[0...i-1]仍然是一个最大堆。
            // 即,保证a[i-1]是a[0...i-1]中的最大值。
            maxheap_down(a, 0, i-1);
        }
    }
    
    • 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
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
  • 相关阅读:
    Java for循环语句
    投标管理与工程实施管理的关键步骤及策略
    zkLogin构建者的最佳实践和业务思考
    这个好玩又实用的jupyter插件我真的爱了
    STM32移植LVGL8.2
    抖店都需要什么费用?2024具体费用标准,新手必看!
    解决ERROR: No matching distribution found for yaml
    RK3568平台开发系列讲解(网络篇)socket内核对象的创建过程
    NtyCo 协程设计原理与汇编实现
    RISC-V 芯片架构新规范
  • 原文地址:https://blog.csdn.net/qq_45899321/article/details/126358152