数据结构课程设计——漳州通讯网架设方案.doc

漳州通讯网架设方案
一、问题描述
设计要求：在漳州n个区域之间建设通讯网络，只需要保证连通即可，求最经济的架设方案。存储结构采用多种。求解算法多种。
该题目需要运用最小生成树来解决，运用两种方法求最小生成树，分别是PRIM算法和KUSCAL算法。最小生成树的代价之和最小，所以是一种最经济的架设方案。通讯网架设方案中的元素有：
（1） 顶点个数（漳州区域个数）
（2） 边数（区域间的道路个数）
（3） 权值（两区域间的距离）
二、功能需求
该程序是解决城市间架设网络问题的，采用邻接表和邻接矩阵进行存储。要求完成以下功能：
（1）采用不同的存储方式要求输出不同的存储结果
（2）求最小生成树：采用两种不同方法求解最经济的架设方案，输出两区域及其之间的距离（权）
（3）查询：输出所有的顶点和边的个数、输出所有顶点、输出所有边。
（4）增加：增加有效的顶点和边，要求增加的边和顶点不得重复存在。
（5）删除：(a)删除若干个有效的顶点：要求删除的顶点必须存在。
(b)删除若干条边：要求删除的边必须存在
（6）修改：修改若干个顶点名，要求修改的顶点必须存在，且修改后的顶点名不能和已有的顶点名重复，且修改名字后要求修改该顶点对应的边
（7）登录：用户要通过输入用户名和密码登录系统
（8）输入输出：通过文件方式存储了需要信息，修改更新等也同步到文件
三、 实现要点
（1）架设方案中采用邻接矩阵和邻接表进行存储，根据用户的需要选择不同的存储方式
（2）采用Prim算法和kruscal求最小生成树（及最经济的架设方案）Prim算法就是先选择根，把它放入一个集合U中，剩余的顶点放在集合v中。然后选择该顶点与v中顶点之间最小的一条边，以此类推，如果到达最后一个则返回上一个顶点。而kruscal算法是先写出所有顶点，选择权值最小的边，然后写出第二小的，以此类推，最终要有个判断是否生成环，不生成则得到kruscal的最小生成树。
（3）用户可以随意增加区域的顶点数和边数
（4）用户可以删除顶点和边
（5）用户可以更新顶点名，对应系统自动更新边
（6）用户可以查询现有的顶点信息和边信息。

四．定义
1.各类函数说明
Void queryInformation();//查询函数，查询各区域各边信息
Void add1(); //插入新区域和新边
Void Delete_Vertex(); //删除区域（顶点）
Void Delete_adj(); //删除边
Void Update(); //更新顶点和边信息
2.用邻接矩阵存储：
（1）结构体定义
struct MGraph
{
char vexs[20]; //定义一个顶点数组
int arcs[20][20]; //二维数组存储关系与权值
int vexnum,arcnum; //顶点数和边数
};

（2）创建邻接矩阵
int creatMGraph(MGraph &G)
{
char v1,v2;
int i,j,w;
cout<<"请输入漳州市区域数（顶点数）和总道路的个数（弧的个数）："<<endl;
cin>>G.vexnum>>G.arcnum;
for(i=0;i!=G.vexnum;i++)
{
cout<<"输入地区名"<<i+1<<endl;
cin>>G.vexs[i];
}
for(i=0;i!=G.vexnum;++i)
{
for(j=0;j!=G.vexnum;++j)
{
G.arcs[i][j]=int_max;
}
}

for(int k=0;k<G.arcnum;k++)
{
cout<<"请输入两区域间的距离（权）:"<<endl;
cin>>v1>>v2>>w; //输入一条边依附的两点及权值
i=localvex(G,v1);
j=localvex(G,v2);
G.arcs[i][j]=w;
G.arcs[j][i]=w;
}
cout<<"*******************"<<endl;
cout<<"图创建成功"<<endl;
cout<<"请根据如下进行操作"<<endl;
return G.vexnum;
}
（3）输出邻接矩阵
void MGraphPrint(MGraph G) //输出邻接矩阵
{
int i,j;
for(i=0;i<G.vexnum;i++)
{
for(j=0;j<G.vexnum;j++)

if(G.arcs[i][j]==int_max)
{
cout<<"0"<<" ";
}

else
{
cout<<G.arcs[i][j]<<" ";
}
cout<<endl;
}
}
3.邻接表存储
（1）结构体定义
struct ArcNode //边表，包含权值、顶点信息
{
int weight; //该弧中相邻顶点之间的权值
ArcNode *next; //弧尾相同的下一条弧
char info; //该弧信息
};
struct VertexNode //顶点表
{
char data; //节点信息
ArcNode *firstedge; //指向第一条依附该节点的弧的指针
};
struct algraph//图的定义
{
VertexNode adjlist[max]; //存放顶点表的数组
int vexnum,arcnum; //图的顶点数和边数
};
（2）创建邻接表
void creatadj(algraph &gra,MGraph G) //用邻接表储存图
{
int i=0,j=0;
ArcNode *arc;
for(i=0;i!=G.vexnum;++i)
{
gra.adjlist[i].data=G.vexs[i];
gra.adjlist[i].firstedge=NULL;
}
for(i=0;i!=G.vexnum;++i)
{
for(j=0;j!=G.vexnum;++j)
{
if(G.arcs[i][j]!=int_max&&j!=G.vexnum)
{
arc=new ArcNode;
arc->weight=G.arcs[i][j];
arc->info=G.vexs[j];
arc->next=gra.adjlist[i].firstedge;
gra.adjlist[i].firstedge=arc;
}
}
}
gra.vexnum=G.vexnum;
gra.arcnum=G.arcnum;
}
（2）输出邻接表
void adjprint(algraph gra,MGraph G) //输出邻接表
{
int i;
for(i=0;i!=gra.vexnum;++i)
{
ArcNode *p;
p=gra.adjlist[i].firstedge;
while(p!=NULL)
{
cout<<"("<<G.vexs[i]<<","<<p->info<<")"<<p->weight<<" ";
p=p->next;
}
cout<<endl;
}
}
4.prim算法求最小生成树
void prim(int g[][max],int n,MGraph G)//最小生成树PRIM算法
{
int lowcost[max],prevex[max]; //LOWCOST[]存储当前集合U分别到其余各点的最短路径//prevex[]存储最短路径在U中的结点
int i,j,k,min;
for(i=1;i<n;i++) //n个顶点，n-1条边
{
lowcost[i]=g[0][i]; //初始化
prevex[i]=0; //顶点未加入最小生成树中
}
lowcost[0]=0; //标志顶点0加入U集合
for(i=1;i<n;i++) //形成n-1条边的生成树
{
min=inf;
k=0;
for(j=1;j<n;j++) //寻找满足边的一个顶点在U,另一个顶点在v的最小边
if(lowcost[j]<min&&lowcost[j]!=0)
{
min=lowcost[j];
k=j;
}
printf("(%c,%c)%d\t",G.vexs[prevex[k]],G.vexs[k],min);
//输出最小边
lowcost[k]=0; //顶点k加入U
for(j=1;j<n;j++) //修改由顶点k到其他顶点边的权值
if(g[k][j]<lowcost[j])
{lowcost[j]=g[k][j];
prevex[j]=k;}
printf("\n");
}
}

5.kruscal算法求最小生成树
struct edg
{
int from;//弧的一结点
int to;//弧的另一结点
int weight;//弧的权
};
int FindRoot(int parent[],int f)
{
while(parent[f]>0)
f=parent[f];
return f;
}
void kruscal(MGraph G,algraph gra) //最小生成树KUSCAL算法
{
edg edgs[20];
int i,j,k=0;
for(i=0;i<G.vexnum;i++)
for(j=i;j<G.vexnum;j++)
{
if(G.arcs[i][j]!=9999)
{
edgs[k].from=i;
edgs[k].to=j;
edgs[k].weight=G.arcs[i][j];
++k;
}
}
int x,y,m,n;
int vex2,vex1; //分别表示两个顶点所在树的根节点
for(i=0;i<gra.arcnum;i++)
parent[i]=0;
for(j=0;j<G.arcnum;j++)
{
m=10000;
for(i=0;i<G.arcnum;i++)
{
if(edgs[i].weight<m)
{
m=edgs[i].weight;
x=edgs[i].from;
y=edgs[i].to;
n=i;}
}
vex2=FindRoot(parent,x);
vex1=FindRoot(parent,y);
edgs[n].weight=10000;
if(vex2!=vex1)
{
parent[vex2]=vex1;
cout<<"("<<G.vexs[x]<<","<<G.vexs[y]<<")"<<m；
//输出加入的边
cout<<endl;
}
}
}

6.主函数
int main()
{
cout<<"欢迎来到漳州通讯网管理系统!"<<endl;
string Account="zhengyumei";
string Password="123456";
string ac,pa;
cout<<"用户名：";
cin>>ac;
cout<<"密码：";
cin>>pa;
while(ac!=Account||pa!=Password)
{
cout<<"用户名或密码错误！"<<endl;
cout<<"用户名：";
cin>>ac;
cout<<"密码：";
cin>>pa;
}
if(pa==Password&&ac==Account)
{int f=0,f1=0;
string num;
cout<<endl;
cout<<" **************************************"<<endl;
cout<<" * 1.进入主页面构建架设方案 *"<<endl;
cout<<" * 2.查询漳州通讯区域现状 *"<<endl;
cout<<" * 3.增加信息 *"<<endl;
cout<<" * 4.删除信息 *"<<endl;
cout<<" * 5.修改信息 *"<<endl;
cout<<" * 6.退出 *"<<endl;
cout<<"**************************************"<<endl;
cout<<endl;
cout<<"请选择您要的菜单:"<<endl;
num="1";
while(num=="1"||num=="2"||num=="3"||num=="4"||num=="5"||num=="6")
{
if(f==0)
{
cin>>num;
}
f=0;
if(num=="1")//选择1所要实现功能的代码
{
algraph gra;//邻接表
MGraph G;//邻接矩阵
int i,j,d,g[20][20];
d=creatMGraph(G);//返回顶点个数
creatadj(gra,G);
cout<<"****************************************"<<endl;
cout<<"* 1.用邻接矩阵储存： *"<<endl;
cout<<"* 2.用邻接表存储： *"<<endl;
cout<<"* 3.PRIM算法求最经济的架设方案 *"<<endl;
cout<<"* 4.KRUSCAL算法求最经济的架设方案 *"<<endl;
cout<<"* 5.返回 *"<<endl;
cout<<"****************************************"<<endl;
string s;
cout<<"请选择菜单："<<endl;
s="1";
while(s=="1"||s=="2"||s=="3"||s=="4"||s=="5")
{ if(f1==0)
{cin>>s; }
f1=0;
if(s=="1")
{
cout<<"用邻接矩阵存储为："<<endl;
MGraphPrint(G); }
else if(s=="2")
{
cout<<"用邻接表存储为："<<endl;
adjprint(gra,G);
}
else if(s=="3")
{
for(i=0;i<G.vexnum;i++)
for(j=0;j<G.vexnum;j++)
g[i][j]=G.arcs[i][j];
cout<<"PRIM算法最经济的架设方案为："<<endl;
prim(g,d,G);
}
else if(s=="4")
{
cout<<"KRUSCAL算法最经济的架设方案为："<<endl;
kruscal(G,gra);
}
else if(s=="5")
{
break;
}
else//当用户选择菜单不为1234时，容错处理
{
while(s!="1"&&s!="2"&&s!="3"&&s!="4")
{
cout<<"您的输入不正确，请重新选择菜单："<<endl;
cin>>s;
f1=1;
}
}
}
if(s=="5")
{
cout<<"请选择菜单:"<<endl;
cout<<"**************************************"<<endl;
cout<<"* 1.进入主页面构建架设方案 *"<<endl;
cout<<"* 2.查询漳州通讯区域现状 *"<<endl;
cout<<"* 3.增加信息 *"<<endl;
cout<<"* 4.删除信息 *"<<endl;
cout<<"* 5.修改信息 *"<<endl;
cout<<"* 6.退出 *"<<endl;
cout<<"**************************************"<<endl;
continue;
}
}
else if(num=="2")
{queryInformation();
continue;}
else if(num=="3")
{
add1();
continue;
}
else if(num=="4")
{
string n;
cout<<"请选择删除对象："<<endl;
cout<<"___1.删除顶点"<<endl;
cout<<"___2.删除边"<<endl;
cin>>n;
if(n=="1")
Delete_Vertex();
else if(n=="2")
Delete_adj();
continue;
}
else if(num=="5")
{
Update();
continue;
}
else if(num=="6")
{return 0; }
else
{while((num!="1")&&(num!="2")&&(num!="3")&&(num!="4")&&(num!="5"))
{
cout<<"您的输入不正确，请重新输入！"<<endl;
cin>>num;
f=1;
}
}
}
}
return 0;
}
四、 演示结果
1. 用户使用初始界面，需输入用户名密码

2. 选择1进入主页面构建架设方案

说明：出现各个区域及其各边信息，可以通过提示选择储存方式和对应的算法求最经济的架设方案。
选择菜单1,2,3,4出现的界面分别如下：
选择1：

选择2：

选择3：

选择4：

3. 选择菜单2进入查询页面如下：

4. 选择菜单3进行插入（假设插入2顶点2个边）

说明：顶点和边信息如果输入不合规范则会提错，插入的顶点和边如果已经存在则不能插入。插入成功后文件增加了顶点和边，如下所示：

5. 选择菜单4进行删除操作
（1）删除顶点

说明：删除顶点不能重复删除已经删除过的顶点，也不能删除原有顶点以外的顶点。删除顶点同时也把对应顶点相连的边删除。
（2）删除边

说明：删除的边必须存在，不能重复删除已经删除的边
6.修改信息

说明：修改顶点的名称，要求所修改的顶点必须存在，修改顶点后对应边也要更新。
7.退出

选择菜单6则结束程序
18