高校专用通信网络建设.doc

. .

淮 海 工 学 院 计算机工程学院
课程设计报告

设计名称： 数据构造课程设计
选题名称：高校专用通信网络建立
姓 名：陈韦迪学 号：2021122778
专业班级：计算机科学与技术 计算机142
系 〔院〕： 计算机工程学院
设计时间： 2021.12.22~2021 .1.4
设计地点：计算机实验室、教室

成绩：
指导教师评语：

签名：
年 月 日

. .word..
. .

1．课程设计目的
1、训练学生灵活应用所学数据构造知识，独立完成问题分析，结合数据构造理论知识，编写程序求解指定问题。
2、初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等根本方法和技能；
3、提高综合运用所学的理论知识和方法独立分析和解决问题的能力；
4、训练用系统的观点和软件开发一般规X进展软件开发，稳固、深化学生的理论知识，提高编程水平，并在此过程中培养他们严谨的科学态度和良好的工作作风。

2．课程设计任务与要求：
任务
根据教材?数据构造-C语言描述?〔耿国华主编〕和参考书?数据构造题集〔C语言版〕?〔严蔚敏、X伟XX编〕选择课程设计题目，要求通过设计，在数据构造的逻辑特性和物理表示、数据构造的选择应用、算法的设计及其实现等方面加深对课程根本内容的理解和综合运用。
设计题目从任务书所列选题表中选取，每班每题不得超过2人。
学生自选课题。
学生原那么上可以结合个人爱好自选课题，要求课题有一定的深度与难度，有一定的算法复杂性，能够稳固数据构造课程所学的知识。学生自选课题需在18周前报课程设计指导教师批准方可生效。
要求：
1、在处理每个题目时，要求从分析题目的需求入手，按设计抽象数据类型、构思算法、通过设计实现抽象数据类型、编制上机程序和上机调试等假设干步骤完成题目，最终写出完整的分析报告。前期准备工作完备与否直接影响到后序上机调试工作的效率。在程序设计阶段应尽量利用已有的标准函数，加大代码的重用率。
2、设计的题目要求到达一定工作量〔300行以上代码〕，并具有一定的深度和难度。
3、程序设计语言推荐使用C/C++，程序书写规X，源程序需加必要的注释;
4、每位同学需提交可独立运行的程序；
5、每位同学需独立提交设计报告书〔每人一份〕，要求编排格式统一、规X、内容充实，不少于10页〔代码不算〕；
6、课程设计实践作为培养学生动手能力的一种手段，单独考核。

3．课程设计说明书
一 需求分析
[ 问题描述 ]
中国移动公司正在积极推广3G通信应用，方案在XX高校之间建立一个专用通信网络，请为其规划一个投资最省的通信线路架设方案。
[根本要求]
（1） 用无向网模拟该系统，顶点表示各高校，边表示线路建立本钱
（2） 高校数量不少于10个，覆盖苏南、苏中、苏北、XX等地的高校
（3） 输出方案的结果直观、明确
（4） 交互式改变某些线路的建立本钱，可重新输出新方案

二 概要设计

3．课程设计说明书 

  二 概要设计 
void menu(graph *g); //菜单
void Editgraph(graph *g); //编辑通信网络系统
int Creategraph(graph *g) //创立通信网络系统
int InsertVex(graph *g,string v) //添加高校
void ChangeVex(graph *g,string v) //修改高校名
int InsertArc(graph *g,string v,string w) //添加高校间的路线
int DeleteArc(graph *g,string v,string w) //删除高校间的路线
void ChangeWeight(graph *g,string v,string w) //修改高校间的路线及其本钱
int Destroygraph(graph *g) //销毁通信网络系统
int Display(graph *g) //输出通信网络系统
void save(graph *g) //保存通信网络系统

根本操作： 

InitList(L)      初始化L为空表 
DestoryList(L)    销毁L 
ClearList(L)     将L置为空表 
ListLength(L)    假设L为空表那么返回0，否那么返回表中元素个数 
Locate(L,e)      假设L中存在元素e那么将当前指针指向e所在位置并返回真 
GetData(L,i)     返回L中第i个元素的值 
InsList(L,I,e)   在L中第i个位置插入e，L的长度增加1 
DelList(L,I,&e)  删除L的第i个元素，并用e返回其值，L长度减少1 
数据定义：

typedef struct Arode
{
int adj;//权值
}Arode;

typedef struct
{ string vexs[MAX_VERTEX_NUM];//顶点
Arode arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//邻接矩阵
int vexnum,arum;//顶点数和边数
}graph;//图的类型
typedef struct
{
string adjvex;
int lowcost;
}minside;//求最小生成树时的辅助数组的类

三 详细设计

创立通信系统
int Creategraph(graph *g)

{
int i,j,k,w;
string va,vb;
读取文件"通信网络.txt"
if(未找到文件)
{
cout<<"open error!"<<endl;
return 0;
}
从文件读入顶点数
从文件读入边数
顶点向量
infile>>(*g).vexs[i];
初始化邻接矩阵
for(j=0;j<(*g).vexnum;++j)
{
(*g).arcs[i][j].adj=INFINITY; //网
}
for(k=0;k<(*g).arum;++k)
{
infile>>va>>vb>>w;
i=LocateVex(g,va);
j=LocateVex(g,vb);
无向网
}
infile.close();
return 1;
}
添加高校
int InsertVex(graph *g,string v)
{ //在图g中增添新顶点v
if(顶点数为0)
{
cout<<"未建立通信网络系统!\n";
system(暂停);
Editgraph(g);
}
cout<<"请输入要添加的高校名:";
cin>>v;
int n=LocateVex(g,v);
if(高校名重复)
{
cout<<"该高校已存在!\n";
system(暂停);
Editgraph(g);
}
int i;
构造新顶点向量
for(i=0;i<=(*g).vexnum;i++)
{
初始化该行邻接矩阵的值
初始化该列邻接矩阵的值
}
图g的顶点数加1
return 1;
}

删除学校
int DeleteVex(graph *g,string v)
{ // 删除g中顶点v及其相关的弧
if(顶点数为0)
{
cout<<"未建立通信网络系统!\n";
system(暂停);
Editgraph(g);
}
int k=LocateVex(g,v);
if(k<0)
{
cout<<"不存在该学校!\n";
system(暂停);
Editgraph(g);
}
int i,j;
int m=0;
if〔 v不是图g的顶点〕
return 0;
m=无限;
for(j=0;j<(*g).vexnum;j++)
if(有入弧或边)
{
修改弧数
}
for(序号k后面的顶点向量依次前移)
(*g).vexs[j-1]=(*g).vexs[j];
for(i=0;i<(*g).vexnum;i++)
for(j=k+1;j<(*g).vexnum;j++)
移动待删除顶点之后的矩阵元素
for(i=0;i<(*g).vexnum;i++)
for(j=k+1;j<(*g).vexnum;j++)
移动待删除顶点之下的矩阵元素
更新图的顶点数
return 1;
}

修改高校名
void ChangeVex(graph *g,string v)//修改高校名
{
cout<<"请输入要修改的高校名:";
cin>>v;
int n=LocateVex(g,v);
if(n<0)
{
cout<<"不存在该学校!\n";
system(暂停);
Editgraph(g);
}
string s;
cout<<"请输入修改后的高校名:";
cin>>s;
g->vexs[n]=s;
}
添加路线
int InsertArc(graph *g,string v,string w)
{//在g中增添弧<v,w>,假设g是无向的,那么还增添对称弧<w,v>
if(顶点数为0)
{
cout<<"未建立通信网络系统!\n";
system(暂停);
Editgraph(g);
}
cout<<"请输入要添加的线路的两端的高校名:";
cin>>v>>w;
int v1,w1;
v1=LocateVex(g,v); //尾
w1=LocateVex(g,w); //头
if(v1<0||w1<0||v1==w1)
{
cout<<"高校名输入错误!\n";
system(暂停);
Editgraph(g);
}
else if(路线两头高校名重复)
{
cout<<"该线路已存在!\n";
system(暂停);
Editgraph(g);
}
弧或边数加1
cout<<"请输入该条线路的建立费用:";
cin>>(*g).arcs[v1][w1].adj;
bool bRet = cin.good();
if(!bRet)
{
cout<<"输入的本钱不是整型的!\n";
system(暂停);
exit(0);
}
(*g).arcs[w1][v1].adj=(*g).arcs[v1][w1].adj;
return 1;
}
删除线路
int DeleteArc(graph *g,string v,string w)
{ //在g中删除弧<v,w>,假设g是无向的,那么还删除对称弧<w,v>
if(顶点数为0)
{
cout<<"未建立通信网络系统!\n";
system(暂停);
Editgraph(g);
}
cout<<"请输入要删除的线路的两端的高校名:";
cin>>v>>w;
int n=LocateVex(g,v);
int m=LocateVex(g,w);
if(m<0||n<0||m==n)
{
cout<<"学校名输入错误!\n";
system(暂停);
Editgraph(g);
}
else if(花费无限)
{
cout<<"不存在该线路!\n";
system(暂停);
编辑
}
g->arcs[n][m].adj=INFINITY;
(*g).arcs[m][n].adj=(*g).arcs[n][m].adj;
(*g).arum--;
return 1;
}
四 程序设计与调试分析
1.因为前期需求分析的准备工作不充分，程序运行功能不全，程序中运用到大多的插入与删除，比方查找时关于线路的信息不能全部显示出来，并且添加删除时线路的变化不能直接显示出来。程序的强健性不能到达预期的结果，这些都是需要改良的。
2. 在编写程序过程中，因为函数调用不准确，使得循环进不去，在程序中的函数调用是个非常重要的局部，也是经常需要用到的，为了到达了预期结果，后来改变函数的调用关系，。

五 用户手册
【使用说明】
1.使用高校专用通信网络系统
2.选择1.构造通信网络系统，那么显示出10个高校45条线路的通信系统矩阵。
3.创立成功，选择2.编辑通信网络系统，显示出功能1~8。
4.销毁系统，选择1.销毁通信网络系统。
5.添加高校，选择2.添加一个高校，并输入要添加的高校名。
6.删除高校，选择3.删除一个高校，并输入要删除的高校名。假设输入的高校名不存在，那么显示 不存在该学校。
7.修改高校名，选择4.修改高校名，并输入要修改的高校名。假设输入的高校名不存在，那么显示不存在该学校。
8.添加高校间的线路，选择5.添加一条高线间的线路，输入要添加线路两端的高校名。假设输入的高校名错误在那么显示学校名输入错误。
9.删除高线间的线路，选择6.删除一条高校间的线路，并输入要删除线路两端的高校名。假设输入的高校名不存在那么显示学校名输入错误。
10.修改线路的本钱，选择7.修改线路的本钱，并输入要删除线路连段的高校名。假设输入的高校名不存在那么显示学校名输入错误。
11.推出编辑通信网络系统，选择8.退出。回到高校专用通信网络建立系统。
12.生成最正确方案，选择3.生成最正确方案。并输入起始学校和要保存的文件名。
13.输出通信网络系统，选择4.输出通信网络系统。
14.保存通信网络系统，选择5.保存通信网络系统。并输入要保存的文件名。
15. 退出，选择6.退出系统。

六 测试成果
1.通信网络系统

2.添加一个高校

3.删除一个高校

4.修改高校名

5.添加一条高校间的线路

6.删除高校间的线路

7.修改高校间的本钱

8.生成最正确路线

9.输出通信网络系统

10.保存通信网络系统

七 附录〔源程序清单〕
#include "stdafx.h"
#include <iostream>
#include <iomanip>
#include <windows.h>
#include <fstream>
#include <string>
#define MAX_VERTEX_NUM 30
#define INFINITY 32768
using namespace std;
typedef struct Arode
{
int adj;//权值
}Arode;
typedef struct
{
string vexs[MAX_VERTEX_NUM];//顶点
Arode arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//邻接矩阵
int vexnum,arum;//顶点数和边数
}graph;//图的类型
void menu(graph *g);
void Editgraph(graph *g);
int LocateVex(graph *g,string v)//求顶点位置函数,假设v存在,输出j;假设不存在,输出0
{
int j=-1,k;
for(k=0;k<g->vexnum;k++)
{
if(g->vexs[k]==v)//判断是否存在顶点v
{
j=k;
break;
}
}
return j;
}
int Creategraph(graph *g)//采用邻接矩阵法,构造有向网g
{
int i,j,k,w;
string va,vb;
ifstream infile("通信网络.txt",ios::in);//从文件中读入数据
if(!infile)
{
cout<<"open error!"<<endl;
return 0;
}
infile>>g->vexnum;//从文件读入顶点数
infile>>g->arum;//从文件读入边数
for(i=0;i<g->vexnum;++i) //顶点向量
infile>>(*g).vexs[i];
for(i=0;i<(*g).vexnum;++i) //初始化邻接矩阵
for(j=0;j<(*g).vexnum;++j)
{
(*g).arcs[i][j].adj=INFINITY; //网
}
for(k=0;k<(*g).arum;++k)
{
infile>>va>>vb>>w;
i=LocateVex(g,va);
j=LocateVex(g,vb);
(*g).arcs[i][j].adj=(*g).arcs[j][i].adj=w; //无向网
}
infile.close();
return 1;
}
int InsertVex(graph *g,string v)
{ //在图g中增添新顶点v
if(g->vexnum==0)
{
cout<<"未建立通信网络系统!\n";
system("pause");
Editgraph(g);
}
cout<<"请输入要添加的高校名:";
cin>>v;
int n=LocateVex(g,v);
if(n>=0&&v==g->vexs[n])
{
cout<<"该高校已存在!\n";
system("pause");
Editgraph(g);
}
int i;
(*g).vexs[(*g).vexnum]=v; //构造新顶点向量
for(i=0;i<=(*g).vexnum;i++)
{
(*g).arcs[(*g).vexnum][i].adj=INFINITY; //初始化该行邻接矩阵的值
(*g).arcs[i][(*g).vexnum].adj=INFINITY; //初始化该列邻接矩阵的值
}
(*g).vexnum+=1; // 图g的顶点数加1
return 1;
}

int DeleteVex(graph *g,string v)
{ // 删除g中顶点v及其相关的弧
if(g->vexnum==0)
{
cout<<"未建立通信网络系统!\n";
system("pause");
Editgraph(g);
}
int k=LocateVex(g,v);
if(k<0)
{
cout<<"不存在该学校!\n";
system("pause");
Editgraph(g);
}
int i,j;
int m=0;
if(k<0) //v不是图g的顶点
return 0;
m=INFINITY;
for(j=0;j<(*g).vexnum;j++)
if((*g).arcs[j][k].adj!=m) //有入弧或边
{
(*g).arum--; //修改弧数
}
for(j=k+1;j<(*g).vexnum;j++) //序号k后面的顶点向量依次前移
(*g).vexs[j-1]=(*g).vexs[j];
for(i=0;i<(*g).vexnum;i++)
for(j=k+1;j<(*g).vexnum;j++)
(*g).arcs[i][j-1]=(*g).arcs[i][j]; //移动待删除顶点之后的矩阵元素
for(i=0;i<(*g).vexnum;i++)
for(j=k+1;j<(*g).vexnum;j++)
(*g).arcs[j-1][i]=(*g).arcs[j][i]; //移动待删除顶点之下的矩阵元素
(*g).vexnum--; //更新图的顶点数
return 1;
}
void ChangeVex(graph *g,string v)//修改高校名
{
cout<<"请输入要修改的高校名:";
cin>>v;
int n=LocateVex(g,v);
if(n<0)
{
cout<<"不存在该学校!\n";
system("pause");
Editgraph(g);
}
string s;
cout<<"请输入修改后的高校名:";
cin>>s;
g->vexs[n]=s;
}
int InsertArc(graph *g,string v,string w)
{//在g中增添弧<v,w>,假设g是无向的,那么还增添对称弧<w,v>
if(g->vexnum==0)
{
cout<<"未建立通信网络系统!\n";
system("pause");
Editgraph(g);
}
cout<<"请输入要添加的线路的两端的高校名:";
cin>>v>>w;
int v1,w1;
v1=LocateVex(g,v); //尾
w1=LocateVex(g,w); //头
if(v1<0||w1<0||v1==w1)
{
cout<<"高校名输入错误!\n";
system("pause");
Editgraph(g);
}
else if(g->arcs[v1][w1].adj!=INFINITY)
{
cout<<"该线路已存在!\n";
system("pause");
Editgraph(g);
}
(*g).arum++; //弧或边数加1
cout<<"请输入该条线路的建立费用:";
cin>>(*g).arcs[v1][w1].adj;
bool bRet = cin.good();
if(!bRet)
{
cout<<"输入的本钱不是整型的!\n";
system("pause");
exit(0);
}
(*g).arcs[w1][v1].adj=(*g).arcs[v1][w1].adj;
return 1;
}

int DeleteArc(graph *g,string v,string w)
{ //在g中删除弧<v,w>,假设g是无向的,那么还删除对称弧<w,v>
if(g->vexnum==0)
{
cout<<"未建立通信网络系统!\n";
system("pause");
Editgraph(g);
}
cout<<"请输入要删除的线路的两端的高校名:";
cin>>v>>w;
int n=LocateVex(g,v);
int m=LocateVex(g,w);
if(m<0||n<0||m==n)
{
cout<<"学校名输入错误!\n";
system("pause");
Editgraph(g);
}
else if(g->arcs[n][m].adj==INFINITY)
{
cout<<"不存在该线路!\n";
system("pause");
Editgraph(g);
}
g->arcs[n][m].adj=INFINITY;
(*g).arcs[m][n].adj=(*g).arcs[n][m].adj;
(*g).arum--;
return 1;
}
void ChangeWeight(graph *g,string v,string w)
{
cout<<"请输入要修改的线路的两端的高校名:";
cin>>v>>w;
int m=LocateVex(g,v);
int n=LocateVex(g,w);
if(m<0||n<0)
{
cout<<"输入的学校不存在!\n";
system("pause");
Editgraph(g);
}
else if(g->arcs[n][m].adj==INFINITY)
{
cout<<"不存在该线路!\n";
system("pause");
Editgraph(g);
}
char s;
cout<<"请输入该路线修改后的本钱:";
cin>>s;
fflush(stdin);
bool bRet = cin.good();
if(!bRet)
{
cout<<"输入的本钱不是整型的!\n";
system("pause");
exit(0);
}
else
{
g->arcs[m][n].adj=g->arcs[n][m].adj=s;
}
}
int Destroygraph(graph *g)
{ //销毁图g
if(g->vexnum==0)
{
cout<<"未建立通信网络系统!\n";
system("pause");
Editgraph(g);
}
int i;
for(i=0;i<(*g).vexnum;i++)//删除所有的点和边
DeleteVex(g,g->vexs[i]);
(*g).vexnum=0;
(*g).arum=0;
return 1;
}
int Display(graph *g)//以矩阵方式输出图
{
if(g->vexnum==0)
{
cout<<"未建立通信网络系统!\n";
system("pause");
menu(g);
}
int i,j;
cout<<g->vexnum<<"个高校"<<g->arum<<"条线路的通信系统如下面的矩阵:\n\n";
cout<<" ";
for(i=0;i<g->vexnum;i++)
cout<<setw(2)<<" "<<g->vexs[i]<<" ";
cout<<endl;
for(i=0;i<g->vexnum;i++)
{
cout<<g->vexs[i]<<" ";
for(j=0;j<g->vexnum;j++)
{
if(g->arcs[i][j].adj==INFINITY)
cout<<setw(5)<<"∞"<<" ";
else
cout<<setw(5)<<g->arcs[i][j].adj<<" ";
}
cout<<endl;
}
return 1;
}
//普里姆算法
typedef struct
{
string adjvex;
int lowcost;
}minside;//求最小生成树时的辅助数组的类
int minimum(graph *G,minside closedge[MAX_VERTEX_NUM])
{//求closedge[i].lowcost最小值，并返回i
int i=0,j,k,min;
while(closedge[i].lowcost==0)//找到第一个值不为0的closedge[i].lowcost的序号
i++;
min=closedge[i].lowcost;//min标记第一个不为0的值
k=i;
for(j=i+1;j<G->vexnum;j++)//继续查找
if(closedge[j].lowcost>0&&closedge[j].lowcost<min)
{
min=closedge[j].lowcost;
k=j;
}
return k;//返回当前最小正值的序号
}
void MiniSpanTree_Prim(graph *g,string s)
{
static int sum=0;
if(g->vexnum==0)
{
cout<<"未建立通信网络系统!\n";
system("pause");
menu(g);
}
cout<<"请输入起始学校:";
cin>>s;
int n=LocateVex(g,s);
if(n<0)
{
cout<<"不存在该学校!\n";
system("pause");
menu(g);
}
minside closedge[MAX_VERTEX_NUM];
int k=LocateVex(g,s);
string a[30],b[30];//a[],b[]为中间变量，用来存放边的顶点
closedge[k].lowcost=0;//初始化，U={s}
for(int i=0;i<g->vexnum;i++)//初始化closedge[k]
{
if(i!=k)
{
closedge[i].adjvex=s;
closedge[i].lowcost=g->arcs[k][i].adj;
}
}
char name[20];
cout<<"输入要保存的文件名:";
cin>>name;
strcat(name,".txt");
ofstream outfile(name);
outfile<<"最正确方案:\n";
cout<<"最正确方案:\n";
for(int e=1;e<=g->vexnum-1;e++)//找到n-1条边
{
int k0=minimum(g,closedge);
string u0=closedge[k0].adjvex;
string v0=g->vexs[k0];
a[e]=u0;
b[e]=v0;
int m=LocateVex(g,u0);
int n=