数据结构课程设计报告——畅通工程

• 2020 年 6 月 27 日
• 筆記

数据结构课程设计报告

项 目 名 称：           畅通工程                      

所 在 班 级：                              

小 组 成 员：                                

任 课 教 师：                                

起 止 时 间：                                 

项目基本信息

项目评定成绩记录

问题描述及分析

写清楚你要实现的是个什么系统，完成的都是什么功能？

1、建设道路数量问题

[问题描述] 现有城镇道路的统计数据表中列出了每条快速路直接连通的城镇,问最少还

需要建设多少条快速路就可以达到畅通目标?

输人数据包括城镇数目N和快速路数目M;随后的M行对应M条快速路,每行给出一对正

整数,分别是该条快速路直接连通的两个城镇的编号。为简单起见,城镇从1到N编号。

要求输出需要建设的快速路的条数。

[实现方法]我们把已经连通的一片城镇区域看成图的一个连通集,这个问题就等价于问

目前给定的图中有多少个独立的连通集,而连通K个集合,最少需要K-1条边。

利用并查集,将有边相连的结点都并人同一集合,最后数一下有多少个集合即可。

2、最低成本建设问题

[问题描述]现有城镇道路的统计数据表中列出了有可能建设成快速路的若干条道路的成

本,求畅通工程需要的最低成本。

输人数据包括城镇数目N和候选道路数目M;随后的M行对应M条道路,每行给出3个正.

整数,分别是该条道路直接连通的两个城镇的编号以及该道路改建的预算成本。为简单起见,城

镇从1到N编号。要求输出畅通工程需要的最低成本。如果输人数据不足以保证畅通,则输出

“需要建设更多道路”。

[实现方法]我们把道路建设成本看成图中对应边的权重。要保证图中N个结点的连通，

我们至少需要构建N-1条边,使得结点连接成– –棵树;而要求成本最低.就意味着N-1条边的

总权重最小。这个问题就等价于求给定带权图的最小生成树问题。

求最小生成树的算法，在此我们选择Kruskal 算法。

功能模块及数据结构描述

系统划分成几个模块，几个模块之间是什么调用关系？画出系统结构图

1、建设道路数量问题

系统划分6个模块

图1 建设道路数量问题模块划分

2、最低成本建设问题

系统划分12个模块

其中，CreateGraph和InsertEdge分别在main和Kruskal中调用一次

图2 最低成本建设问题模块划分

二、 主要算法流程描述及部分核心算法

主要模块的算法介绍，画出其流程图

1、建设道路数量问题

文件名称：

项目名称：畅通工程问题
创建者：
创建时间：
最后修改时间：
功能： 计算出需要多少条快速路
文件中的函数名称和简单功能描述：

文件中定义的全局变量和简单功能描述：

文件中用到的他处定义的全局变量及其出处：
与其他文件的依赖关系：

算法介绍：

/*道路数量建设*/

#include<stdio.h>

#include<stdlib.h>

#define MAXN 1000

#define MaxVertexNum 100

typedef int ElementType;

typedef int SetName;

typedef ElementType SetType[MAXN];

typedef int Vertex;

void Union(SetType S,SetName Root1,SetName Root2);  //合并集合 保证小集合并入大集合

SetName Find(SetType S,ElementType X);

void Initialization(SetType S,int N); //集合初始化默认从1开始

void InputConnection(SetType S,int M);  //读M条入边，并将所有边相连的节点并入统一集合

int CountConnectedComponents(SetType S,int N);  //计算集合S中连通集的个数

int main(void)

{

SetType S;

int N,M;

while(scanf(“%d”,&N)!=EOF&&N!=0){

scanf(“%d”,&M);

Initialization(S,N);

InputConnection(S,M);

printf(“需要建设道路%d条\n”,CountConnectedComponents(S,N)-1);

/* 测试代码 */

// for(int i=1;i<=N;i++)

// printf(“S[%d]=%d\n”,i,S[i]);  

}

return 0;

}

void Union(SetType S,SetName Root1,SetName Root2)  //合并集合 保证小集合并入大集合

{

if(S[Root2]<S[Root1]) //如果集合2集合1大

{

S[Root2]+=S[Root1]; //集合1并入集合2

S[Root1]=Root2;

}

else //如果集合1比较大

{

S[Root1]+=S[Root2]; //集合2并入集合1

S[Root2]=Root1;

}

}

SetName Find(SetType S,ElementType X)

{

for(;S[X]>=0;X=S[X]);

return X;

}

void Initialization(SetType S,int N) //集合初始化默认从1开始

{

int i;

for(i=1;i<=N;i++)

S[i]=-1;

}

void InputConnection(SetType S,int M)  //读M条入边，并将所有边相连的节点并入统一集合

{

Vertex U,V;

Vertex Root1,Root2;

int i;

for(i=0;i<M;i++)

{

scanf(“%d%d”,&U,&V);

Root1=Find(S,U);

Root2=Find(S,V);

if(Root1!=Root2)

Union(S,Root1,Root2);

}

}

int CountConnectedComponents(SetType S,int N)  //计算集合S中连通集的个数

{

int i;

int cnt=0;

for(i=1;i<=N;i++)

{

if(S[i]<0)

cnt++;

}

return cnt;

}

流程图：

流程图1 建设道路数量问题主函数

2、最低成本建设问题

文件名称：

项目名称：畅通工程问题
创建者：
创建时间：
最后修改时间：
功能：
文件中的函数名称和简单功能描述：

文件中定义的全局变量和简单功能描述：
文件中用到的他处定义的全局变量及其出处：
与其他文件的依赖关系：

算法介绍：

/*最低成本建设问题*/

#include <stdlib.h>

#include <stdio.h>

typedef int WeightType;// 边的权值设为整型

typedef int ElementType;

typedef int SetName;

typedef int Vertex;

typedef int* SetType;

/* 邻接点的定义 */

typedef struct AdjVNode *PtrToAdjVNode; //网图的边表结构

struct AdjVNode

{

    Vertex AdjV;

    WeightType Weight;

    PtrToAdjVNode Next;

};

/* 顶点表头结点的定义 */

typedef struct Vnode //顶点结构

{

    PtrToAdjVNode FirstEdge;

}AdjList;

/* 图节点的定义 */

typedef struct GNode *ptrToGNode;

struct GNode

{

    int Nv;

    int Ne;

    AdjList *G;

};

typedef ptrToGNode LGraph;

/* 边的定义 */

struct ENode

{

    Vertex V1;

    Vertex V2;

    WeightType Weight;

};

typedef ENode* Edge;

/****************** 并查集 *********************/

void InitializeVSet(SetType S,int N);  //初始化并查集

void Union(SetType S,SetName Root1,SetName Root2);  //合并集合 保证小集合并入大集合

SetName Find(SetType S,ElementType X);  //路径压缩

//检查连接V1和V2的边是否在现有的最小生成树子集中构成回路

bool CheckCycle(SetType VSet,Vertex V1,Vertex V2);  

/***************** 最小堆 *********************/

//将N个元素的边数组中以ESet[p]为根的子堆调整为关于Weight的最小堆

void PercDown(Edge ESet,int p,int N);  

void InitializeESet(LGraph Graph,Edge ESet);  //将图的边存入数组ESet，并且初始化为最小堆

void Swap(Edge a,Edge b);

int GetEdge(Edge ESet,int CurrentSize);  //给定当前堆的大小CurrentSize，将当前最小边位置弹出并调整堆

/************* 邻接表的图定义 ***************/

LGraph CreateGraph(Vertex MaxNumber);  

void InsertEdge(LGraph MST,Edge edge);

/************* 核心 Kruskal算法 **************/

int Kruskal(LGraph Graph,LGraph MST);  //将最小生成树保存为邻接表存储的图MST，返回最小权重和

int main(void)

{

    Vertex Nv,Ne;

    Vertex V1,V2,i;

    WeightType Weight;

scanf(“%d %d”,&Nv,&Ne);

    LGraph graph=CreateGraph(Nv);

    LGraph MST;

    for(i=0;i<Ne;i++)

{

        Edge edge=(Edge)malloc(sizeof(ENode));

scanf(“%d %d %d”,&V1,&V2,&Weight);

        V1–;

V2–;

        edge->V1=V1;

        edge->V2=V2;

        edge->Weight=Weight;

        InsertEdge(graph,edge);

        ++graph->Ne;

    }

    int total;

    total=Kruskal(graph,MST);

    if(total<0){

     printf(“\n需要建设更多道路\n”);

} else{

printf(“\n最低成本 = %d\n”,total);

}

    return 0;

}

/*——————– 并查集——————–*/

void InitializeVSet(SetType S,int N)  //初始化并查集

{

// S=(SetType)malloc(sizeof(int)*N);

    ElementType X;

    for(X=0;X<N;X++)

        S[X]=-1;

}

void Union(SetType S,SetName Root1,SetName Root2)  //合并集合 保证小集合并入大集合

{ /* 这里默认Root1和Root2是不同集合的根结点 ，要保证小集合并入大集合 */

    if(S[Root2]<S[Root1]) /* 如果集合2比较大 */

{

        S[Root2]+=S[Root1];   /* 集合1并入集合2  */

        S[Root1]=Root2;

    }

    else

{                      

        S[Root1]+=S[Root2]; /* 集合2并入集合1  */

        S[Root2]=Root1;

    }

}

 /*路径压缩函数*/

SetName Find(SetType S,ElementType X)  

{ /*默认集合元素全部初始化为-1*/

    if (S[X]<0)//找到集合的根

        return X;// 返回X所属的根节点的下标

    else

        return S[X]=Find(S,S[X]);  //1.找到父节点所属集合的根；2.把根变成X的父节点；3.返回根

}

bool CheckCycle(SetType VSet,Vertex V1,Vertex V2)  //检查连接V1和V2的边是否在现有的最小生成树子集中构成回路

{

    Vertex Root1,Root2;

    Root1=Find(VSet,V1);//得到V1所属的连通集名称

    Root2=Find(VSet,V2); //得到V2所属的连通集名称

    if(Root1==Root2) //如果V1与V2已经连通，这个边就不能要

        return false;

    else //如果没有连通，那么这条边就可以被收录进来，同时将V1、V2并入同一连通集

{

        Union(VSet,Root1,Root2);

        return true;

    }

}

/*——————– 并查集定义结束 ——————–*/

/*——————– 边的最小堆定义 ——————–*/

/*快速得到最小边的函数*/

void PercDown(Edge ESet,int p,int N)  //实现对ESet[]中的元素向下迁移调整的过程

{//将N个元素的边数组中以ESet[p]为根的子堆调整为关于Weight的最小堆

    int Parent,Child;

    struct ENode X;

    X=ESet[p];//用来取出根节点存放的值

    for( Parent=p; (Parent*2+1)<N; Parent=Child )

{   //因为这里的堆下标从0开始，所以需要让Child=Parent*2+1

        Child=Parent*2+1;

        if((Child!=N-1)&&(ESet[Child].Weight>ESet[Child+1].Weight))

            Child++;  //Child指向左右子节点的较小者

        if(X.Weight<=ESet[Child].Weight) //找到合适的位置

break;

        else //下滤X

            ESet[Parent]=ESet[Child];

    }

    ESet[Parent]=X;

}

void InitializeESet(LGraph Graph,Edge ESet)  //将图的边存入数组ESet，并且初始化为最小堆

{

    Vertex V;

    PtrToAdjVNode W;

    int ECount;

    /* 将图的边存入数组ESet */

    ECount=0;/* 边集合初始化为零*/

    for(V=0;V<Graph->Nv;V++)

        for( W=Graph->G[V].FirstEdge;W;W=W->Next)

            if(V<W->AdjV)

{/* 避免重复录入无向图的边，只收V1<V2的边 */

                ESet[ECount].V1=V;

                ESet[ECount].V2=W->AdjV;

                ESet[ECount++].Weight=W->Weight;

            }

            /* 初始化为最小堆 */

    for(ECount=Graph->Ne/2;ECount>=0;ECount–)

        PercDown(ESet,ECount,Graph->Ne);

}

 /*交换两条边的函数*/

void Swap(Edge a,Edge b)

{

    Edge temp=(Edge)malloc(sizeof(struct ENode));

    *temp=*a;

    *a=*b;

    *b=*temp;

    free(temp);

}

int GetEdge(Edge ESet,int CurrentSize)  //给定当前堆的大小CurrentSize，将当前最小边位置弹出并调整堆

{  /* 将最小边与当前堆的最后一个位置的边交换 */

    Swap(&ESet[0],&ESet[CurrentSize-1]);

     /* 将剩下的边继续调整成最小堆 */

    PercDown(ESet,0,CurrentSize-1 );

    return CurrentSize-1; /* 返回最小边所在位置 */

}

/*——————– 最小堆定义结束 ——————–*/

LGraph CreateGraph(Vertex MaxNumber)  //邻接表的图定义

{

Vertex i;

    LGraph graph=(LGraph)malloc(sizeof(struct GNode));

    graph->Nv=MaxNumber;

    graph->Ne=0;

    graph->G=(AdjList*)malloc(sizeof(AdjVNode)*MaxNumber);

    for(i=0;i<graph->Nv;i++)

{

        graph->G[i].FirstEdge=NULL;

    }

    return graph;

}

void InsertEdge(LGraph MST,Edge edge)

{

    PtrToAdjVNode NewNode;

    NewNode=(PtrToAdjVNode)malloc(sizeof(struct AdjVNode));

    NewNode->AdjV=edge->V2;

    NewNode->Weight=edge->Weight;

    NewNode->Next=MST->G[edge->V1].FirstEdge;

    MST->G[edge->V1].FirstEdge=NewNode;

    NewNode=(PtrToAdjVNode)malloc(sizeof(struct AdjVNode));

    NewNode->AdjV=edge->V1;

    NewNode->Weight=edge->Weight;

    NewNode->Next=MST->G[edge->V2].FirstEdge;

    MST->G[edge->V2].FirstEdge=NewNode;

}

int Kruskal(LGraph Graph,LGraph MST)  //将最小生成树保存为邻接表存储的图MST，返回最小权重和

{

    WeightType TotalWeight;

    int ECount,NextEdge;

    SetType VSet;

    Edge ESet;   

    VSet=(SetType)malloc(sizeof(ElementType)*(Graph->Nv));

    InitializeVSet(VSet,Graph->Nv);

    ESet=(Edge)malloc(sizeof(struct ENode)*(Graph->Ne));

    InitializeESet(Graph,ESet);

    MST=CreateGraph(Graph->Nv);

    TotalWeight=0;

    ECount=0;     

    NextEdge=Graph->Ne;

    while (ECount<Graph->Nv-1)

{  

        NextEdge=GetEdge(ESet,NextEdge);

        if(NextEdge<0)

            break;

        if (CheckCycle(VSet,ESet[NextEdge].V1,ESet[NextEdge].V2)==true)

{

            InsertEdge(MST,ESet+NextEdge);

            TotalWeight+=ESet[NextEdge].Weight;

            ECount++;

        }

    }

    if (ECount<Graph->Nv-1)

        TotalWeight=-1;

    return TotalWeight;

}

流程图：

流程图2  最低成本建设问题主函数

流程图3  Kruskal算法

三、 系统使用说明

如何运行你的系统，使用的账号密码？运行时用的什么数据，结果如何？每个过程抓图实现

1、建设道路数量问题

复制“测试数据”到控制台，即可看到结果。

这里给出三组数据，每组数据的第一行为顶点数N和边数M，

随后M行给出相连的两个顶点，最后以0结束程序。

测试数据：

3 2

1 2

1 3

3 0

5 3

1 2

1 3

4 5

0

测试结果：

需要建设道路0条

需要建设道路2条

需要建设道路1条

图片展示：

2、最低成本建设问题

复制“测试数据”到控制台，即可看到结果。

这里给出两组数据，每组数据的第一行为顶点数N和边数M，

随后M行给出相连的两个顶点以及边的权值。

表1 最低成本建设畅通工程问题部分测试数据

图片展示：

四、 问题及解决办法

调试过程中遇到的主要问题有哪些？如何解决的。有何结论？请用（1）（2）（3）分别列举

成员1：

（1） 刚开始准备去写的。自认为应该不会太难，但是真正去写的时候才会发现有很多点都没有注意到，导致出现各种错误。有问题的地方就会认真参考课本进行修改。

（2） 主函数如何输入数据的时候，一开始想着先输入顶点数、边数，然后依次输入0下标开始的每个顶点下标和边的权值，最后输入顶点数据。后来感觉没有必要输入顶点数据，就用两个临时变量接收两个顶点的值，再把两个临时变量分别减1后再传给InsertEdge函数。

（3） 核心Kruskal函数的实现开始没有真正理解究竟是如何调用其他函数的，导致如何判断回路时总是编译错误，后来又认真看了看课本关于Kruskal算法的具体实现，才有了更加深入的了解。

成员2：

（1） 并查集遇到的问题：一开始不确定自己是否能够十分顺利的利用并查集去实现这些功能，也不明白如何去进行并查集的初始化，后来将课本好好翻看了几遍，对项目有了更深入的理解，找到了并查集的相关内容，了解了使用并查集去实现的好处；

（2） 最小堆遇到的问题：一开始忘记了对边集的初始化，不过后来发现这个问题时就及时改正了；在进行边的收录时也是频频报错，总是混淆边与顶点的关系；在进行最小边与当前堆的最后一个位置的边交换时总是不能交换成功，最后想到利用指针去进行交换，解决了这个问题；

（3） 在项目设计和实现过程中，总是会遇到各种各样的问题，首先要独立思考，另外，要善于去理解和运用课本代码，所谓万变不离其宗，其实书本把各种主要的代码已经提供出来了，我们要自己把这些函数去串起来，组成一个完整的系统。

成员3：

（1） 开始很多细节问题不注意，总是字母错了或者符号的中英文导致开始时候找不到错误在哪。然后一个一个仔细对照发现错误并一一改成规范代码。

（2） 犹豫不决用图的邻接表深度优先搜索还是用并查集的方法，最后通决定实际运行效果较快的并查集。并查集的使用不是很明确，理解的很表面。因此我翻阅课本相关内容加深印象有了更深的理解，并完成我的相对应部分。

（3） 知识点串联的并不顺也不牢固，这段时间就又重新将知识系统地复习一遍。

五、 项目总结

项目和你的预期相符与否，功能是否均实现？系统的特色在哪儿？还有哪些有待改进的地方？

在项目设计和实现过程中，你收获了哪些？意识到自己的不足之处有哪些？

请用（1）（2）（3）分别列举出来。
成员1：

（1） 项目和我的预期完全相符，想要实现的功能也都实现了；

（2） 从刚开始对Kruskal算法书上表面的理解，到后来从计算机方面深入地了解，同时巩固了我对图这一章节的知识。

（3） 通过本次项目设计我意识到团队合作的重要性，各成员之间应该互相交流，在交流的基础上才可以使得程序更加的完善。

成员二 ：

（1） 项目和我的预期是完全相符的，想要实现的功能也都实现了；

（2） 它的特色之处在于利用了一种更为简单的方法——并查集：将所有相连的结点都并入同一个集合，最后数一下集合个数即可。路径压缩不仅让我复习了以前地知识，也优化了并查集大大提高了效率；

（3） 此外，另一个特色之处就是运用了维护一个关于边权重的最小堆，每次从堆中取出最小元的方法。这样做的好处是不需要对全部M条边进行排序，在最好情况下，如果结果需要的N-1条边都排在最前面，我们只需要O(NlogM)的时间就可以得到结果；在最坏情况下，这种方法与排序的方法持平。所以我选择了利用最小堆实现GetEdge函数；

（4） 在项目设计和实现过程中，我意识到了团队协作的重要性，当你的代码多次报错自己却找不到问题所在时可以和队友进行交流，因为大家对项目都有自己的理解，你的方法行不通时，那别人的想法可能就会给你一个大的启发。

成员3：

（1） 项目和我的预期是完全相符的，想要实现的功能也都实现了；

（2） 系统的特色在于使用并查集统计连通集个数。

（3） 我的收获就是通过着这个项目过程又重新系统的复习了相关知识并学会了之前没有那么明白的问题。并且我意识到了团队协作的重要性，我的代码多次报错却找不到问题所在时是和队友进行交流，发现那些细节错误。

（4） 我的不足是马虎不认真导致犯一些很不该犯的错误。 

参考文献：

【2】陈越主编，何钦铭等编著 . 数据结构 . 北京：高等教育出版社 . 2016.6（2019.12重印） .  

p159~p163 p211~214 p301~308