程序设计》课程设计
姓名：王
学号：20100034
班级：软件工程00 班
指导教师：王会青
成绩：
2010年 6 月
实验一.构造可以使n 个城市连接的最小生成树
专业：__软件工程___ 班级：__软件姓名：_王___ 学号：_20100034
完成日期：_2010/6/26 ________
一、【问题描述】给定一个地区的n 个城市间的距离网，用Prim 算法或Kruskal 算法建立最小生成树，并计算得到的最小生成树的代价。
1 城市间的道路网采用邻接矩阵表示，邻接矩阵的存储结构定义采用课本中给出的定义，若两个城市之间不存在道
路，则将相应边的权值设为自己定义的无穷大值。
2 显示出城市间道路网的邻接矩阵。
3 最小生成树中包括的边及其权值，并显示得到的最小生成树的总代价。
4 输入城市数、道路数→输入城市名→输入道路信息→执行Kruskal 算法→执行Prim 算法→输出最小生成树
二、【问题分析】
1. 抽象数据类型结构体数组的定义：
#ifnd ef ADJACENCYMATRIXED// 防止该头文件被重复引用
#define ADJACENCYMATRIXED // 而引起的数据重复定义
#define INFINITY 32767 // 最大值∞
#define MAX_VERTEX_NUM 20 // 最大顶点个数
typedef int VRType; // 权值，即边的值
typedef char InfoType; // 附加信息的类型，后面使用时会定义成一个指针
typedef char VertexType[MAX_VERTEX_NUM]; // 顶点类型
typedef enum {DG=1, DN, UDG, UDN} GraphKind; //{ 有向图，有向网，无向图，无向网}
typedef struct ArcCell
{
VRType adj; //VRType 是顶点关系类型。对无权图，用1 或0 表示相邻否；对带权图，则为权值类型。
InfoType*info; // 该弧关系信息的指针
}ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct
{
VertexType vexs[MAX_VERTEX_NUM]; // 顶点向量 AdjMatrixarcs; // 邻接矩阵 int vexnum, arcnum; GraphKind kind; }MGraph; typedef struct
{
VertexType adjvex; VRType lowcost; }closedge[MAX_VERTEX_NUM]; #endif
// 结束 if
2 程序模块
MGraph G;
// 网 G ，唯一的全局变量 int main(int argc, char * argv[]);
// 主函数
Status LocateVex(MGraph G, VertexType v); // 判断城市 v 在网 G 中的位置 Status CreateUDN(MGraph &G);
// 创建网 G 的邻接矩阵
void DisplayNet(MGraph G); // 以邻接矩阵的形式显示网 G void MiniSpanTree_KRUSKAL(MGraph G); // 最小生成树的 Kruskal 算法
void MiniSpanTree_PRIM(MGraph G, VertexType u); // 最小生成树的 Prim 算法 Status Minimum(closedge closeEdge, int n);
//Prim 算法中求下一个城市的函数 void DeleteInfo(MGraph &G);
// 释放堆内存上动态申请的空间
3. 流程图
创建用邻接矩阵表示的城市道路网
输入城市数 G.vexnum 、 道路数 G.arcnum
输入城市名 G.vexs[i]
// 图的当前顶点数和弧数 // 图的种类标志
// 普里姆算法辅助数组的定义
输入表示道路的两个城市及道路值
G.arcs[i][j].adj
返回OK
Prim 算法
化辅助数组closeEdge
for (i=1; i 求下一个城市k = Minimum(closeEdge, G.vexnum) 输出找到的道路 标记城市，避免重复 输出总耗费 4.数据类型定义 为了用邻接矩阵表示图G ，先是定义二维数组的每一个元素含道路值然后在图的定义中定义 一个此二维数组的结构成员。并且在图中还定义一个用来存放城市的一维数组及int 型的城市数级道路数。 用二维数组的两个下标表示道路，这两个下标又在一位数组中对应两个城市。 这样就建立起了一个城市到城市之间的道路网。 4. 程序主要模块 说明：该程序共含5 个模块，本人负责其中2 个模块构造：***************LocateVex(MGraph G, VertexType v)**************** Status LocateVex(MGraph G, VertexType v); { while (strcmp(G.vexs[i], v)) {i++;} 返回i； } **************** CreateUDN ************************* { 输入城市数、道路数； for （i=0; i< 城市数; ++i）输入城市名； for （i=0; i< 城市数; ++i） for（j=0; j< 城市数; ++j）初始化邻接矩阵：道路值= INFINITY; for （i=0; i< 城市数; ++i） for（j=0; j< 城市数; ++j） 输入两个城市表示道路，输入道路值； } PRIM 算法 MiniSpanTree_PRIM********* void MiniSpanTree_PRIM(MGraph G, VertexType u) { 定义辅助数组：closedge closeEdge; 初始化：strcpy(closeEdge[j].adjvex, u); closeEdge[j].lowcost = G.arcs[k][j].adj; for (i=1; i { 在其余G.vexnum-1 个城市中找到离辅助数组中标记的道路最小值；显示找到的道路； 标记新找到的城市； } } ********************** Minimum***************** Status Minimum(closedge closeEdge, int n) { 在辅助数组中找到道路值最小的道路的两点城市： if ((closeEdge[i].lowcost != 0) && (minTemp > closeEdge[i].lowcost)) 返回该城市在G 中的位置} 三、【功能实现】 #include #include #include #include #include "TypeDefine.h" #include "AdjacencyMatrix.h" #include "InitializeFunction.h" #include "MiniSpanTree_KRUSKAL.h" #include "MiniSpanTree_PRIM.h" #include "DisplayNet.h" #include "DeleteInfo.h" MGraph G; // 全局变量G int main(int argc, char * argv[]);// 主函数 Status LocateVex(MGraph G, VertexType v);// 判断城市v 在网G 中的位置Status CreateUDN(MGraph &G);// 创建网G 的邻接矩阵 void DisplayNet(MGraph G);// 以邻接矩阵的形式显示网G void MiniSpanTree_KRUSKAL(MGraph G);//最小生成树的Kruskal 算法 void MiniSpanTree_PRIM(MGraph G, VertexType u);// 最小生成树的Prim 算法Status Minimum(closedge closeEdge, int n);//Prim 算法中求下一个城市的函数void DeleteInfo(MGraph &G);// 释放堆内存上动态申请的空间 int main(int argc, char * argv[]) { CreateGraph(G); DisplayNet(G); MiniSpanTree_KRUSKAL(G); MiniSpanTree_PRIM(G, G.vexs[0]); DeleteInfo(G); cout< system("pause"); return 0; } //intializeFunction.h Status CreateDG(MGraph &G){return 0;}; Status CreateDN(MGraph &G){return 0;}; Status CreateUDG(MGraph &G){return 0;}; Status CreateUDN(MGraph &G); Status LocateVex(MGraph G, VertexType v) { // 判断输入的顶点v 在G 中的位置。 // 根据顶点的类型，可重载此函数。目前为char int i=0; while (strcmp(G.vexs[i], v)) {i++;} return i; } Status CreateGraph(MGraph &G) { // 采用数组(邻接矩阵)表示法，构造图G. G.kind = UDN; // 默认构造无向网 /* printf("+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n"); printf("|1: 有向图2:无向图3:有向网4:无向网\n"); printf("| 请选择:[ ]\b\b"); scanf("%d", &G.kind); printf("+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n");*/ switch (G.kind) { case DG: return CreateDG(G); // 构造有向图G case DN: return CreateDN(G); // 构造有向网G case UDG: return CreateUDG(G); // 构造无向图G case UDN: return CreateUDN(G); // 构造无向网G default : return ERROR; } }//CreateGraph Status CreateUDN （MGraph &G ） { // 采用数组（邻接矩阵）表示法，构造图 G. int i, j, k; VertexType v1, v2; VRType w; printf （" 构造可以使 N 个城市连接的最小生成树 printf （" 请输入城市数、道路数 （至少 6 个城市， 10 条道路 ）："）; cin>>G.vexnum>>G.arcnum; for (i=0; i cin>>G.vexs[i]; } for (i=0; i { for (j=0; j { G.arcs[i][j].adj = INFINITY; // G.arcs[i][j].info = NULL; } } printf （" 请输入一条道路连接的两个城市名及权值 :\n"）; for (k=0; k printf(" 共%3d 条道路，第 %3d 条道路： ", G.arcnum,k+1); printf （" 请输入第 %d 个城市名（共 %d 个):", i+1, G.vexnum); \n"); // 构造顶点向量 // 初始化邻接矩阵 // 构造邻接矩阵 cin>>v1>>v2>>w; // 输入一条边依附的顶点及权值 i = LocateVex(G, v1); // 确定v1、v2 在G 中的位置 j = LocateVex(G, v2); G.arcs[i][j].adj = w; // 弧 G.arcs[j][i] = G.arcs[i][j]; // 置 return OK; }//CreateUDN //MiniSpan Tree PRIM.h Status Minimum(closedge closeEdge, int n) { int i, flag, minTemp = INFINITY; for (i=0; i { if ((closeEdge[i].lowcost != 0) && (minTemp > closeEdge[i].lowcost)) { minTemp = closeEdge[i].lowcost; flag = i; return flag; void MiniSpanTree_PRIM(MGraph G, VertexType u) // 用普里姆算法从第u 个顶点出发构造网G 的最小生成树T，输出T 的各条边。 // 记录从顶点集U 到V-U 的代价最小的边的辅助数组 定义见 "AdjacencyMatrix.h" int i, j, k, totalCost=0; closedge closeEdge; k = LocateVex(G, u); for (j=0; j { if (j != k) { strcpy(closeEdge[j].adjvex, u); closeEdge[j].lowcost = G.arcs[k][j].adj; } } cout<<"| 用Prim 算法求最小生成树的各条边依次为：\n ------------- "; closeEdge[k].lowcost = 0; // 初始，U={u}; for (i=1; i k = Minimum(closeEdge, G.vexnum); // 求出T 的下一个结点：第k 顶点// 此时closeEdge[k].lowcost = MIN{closeEdge[vi].lowcost | closeEdge[vi].lowcost > 0, vi ∈V-U} cout<<'<'< closeEdge[k].lowcost; closeEdge[k].lowcost = 0; // 第k 顶点并入U 集 for (j=0; j { if (G.arcs[k][j].adj < closeEdge[j].lowcost) // 新顶点并入U 后重新选择最小边 strcpy(closeEdge[j].adjvex, G.vexs[k]); closeEdge[j].lowcost = G.arcs[k][j].adj; } } } cout<<"\n| 总代价："< cout<<"+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ }//MiniSpanTree 四、【实例测试及运行结果】 五、【心得体会】 通过本周的课程设计，我有不少收获。既巩固和加深了对数据结构的理解，认识到《数据结 构》是计算机专业一门重要的专业技术基础课程，还提高了我综合运用本课程所学知识的能力。而且，并不是单纯的看看教材就能解决我们的实际问题，所以还要去查找各种我们所需要的资料，所以这次课程设计也培养了我选用参考书，查阅手册及文献资料的能力。要完成一个课程设计的 课题并不是一次就能编译成功的，中间会出现很多的大问题小问题，改错是个很繁琐的问题。通 过这次课程设计培养了我独立思考，深入研究，分析问题，解决问题的能力。 在以后的学习过程中我将要注意以下几点：1、认真上好专业实验课，多在实践中锻炼自己。2 、写程序的过程要考虑周到，严密。3、在做设计的时候要有信心，有耐心，切勿浮躁。4、认真的 学习课本知识，掌握课本中的知识点，并在此基础上学会灵活运用。5、在课余时间里多写程序，熟练掌握在调试 程序的过程中所遇到的常见错误，以便能节省调试程序的时间。 实验二：统计数字 专业：__软件工程___ 班级：__软件_ 姓名：_王______ 学号：_20100034 完成日期：_2010/6/28 1.【问题描述】 某次科研调查时得到了n 个自然数，每个数均不超过1500000000( 1.5*109 )。已知不相同的数不超过10000 个，现在需要统计这些自然数各自出现的次数，并按照自然数从小到大的顺序输出统计结果。 2【设计需求及分析】 (1)设计要求 原始数据保存在文件count.in 中，文件包含n+1 行。第1 行是整数n(1<=n<=200000) ，表示自然数的个数；第2~n+1 行每行一个自然数。 结果保存在文件count 的尾部，其中结果包含m 行( m 为n 个自然数中不相同数的个数)，按照自然数从小到大的顺序输出。每行输出两个整数，分别是自然数和该数出现的次数，其间用一个空格隔开。 (2)设计思路首先必须有文件的打开和关闭语句，将文件的内容读取到数组a[] 中，然后对数组进行排列和对比，计数。最终输出数据和次数。并写入文件的尾部。 A[]为容纳数据的数组， 之后的内容由while 设置条 件，用后的排查。最后输 出数据和次数。 下面是关键步骤： FILE* fp=fopen("count.txt","a+"); if(fp==NULL) { printf(" 无文件"); return -1; } for(i=0;i<9;i++) { fscanf(fp,"%d",&a[i]); fscanf(fp,"\n"); } int j,t; for (i=1;i<9;i++) for(j=0;j<9-i;j++) if(a[j]>a[j+1]){ t=a[j]; a[j]=a[j+1]; a[j+1]=t; } for(i=0;i<9;i++) { count=1; if (a[i]!=a[i+1]) { printf("%d\t%d\n",a[i],count); // 用只读/ 的方式打开文件 // 若没有文件则返回—1 // 读取文件 // 冒泡排序 fopen 为文件打开函数，fscanf 为文件读取函数，然后进行冒泡排序。排序 if 进行判断。在不等于时，中间嵌套了一个while 循环，进行往 fprintf(fp,"%d\t%d\n",a[i],a[i]); i++; } if(a[i] == a[i + 1]) { 对数字的循环查找和控制条件， while(a[i] == a[i + 1]) { count++; i++; } } (3) 输入时，为竖行依此输入文件，且为数字。且为 数据，第二列为次数。 3. #include 功能的实现】 int a[100]; FILE* fp=fopen("count.txt","a+"); printf(" 无文件 "); for(i=0;i<9;i++) { fscanf(fp,"%d",&a[i]); int j,t; for (i=1;i<9;i++) for(j=0;j<9-i;j++) if(a[j]>a[j+1]) { t=a[j]; a[j]=a[j+1]; a[j+1]=t; } printf(" 结果为： \n 数据 for(i=0;i<9;i++) { count=1; if(a[i]!=a[i+1]) { printf("%d\t%d\n",a[i],count); printf(fp,"%d\t%d\n",a[i],a[i]); i++; } if(a[i] == a[i + 1]) { while(a[i] == a[i + 1]) { count++; i++; } printf("%d\t%d\n", a[i], count); // 创建容纳文件数据的数组 // 用只读 / 的方式打开文件 // 若没有文件则返回— 1 int i; if(fp==NULL) { return -1; } // 读取文件 // 冒泡排序 fscanf(fp,"\n"); } 结果 \n"); int count; fprintf(fp,"%d\t%d\n", a[i], count); } } fclose(fp); // 关闭文件return 0; } 4．【实例测试及运行结果】 5. 【心得体会】 本次实验使我对于文件的打开和关闭语句有了更深的理解。有打开必须有关闭。同时在这次的设计中，我学习到了用泛洪算法解决实际问题的基本思维和步骤。使我对算法的层次性更加清楚，更加加深了对算法的理解。 实验三．送货 专业：__软件工程___ 班级：__软件姓名：_王_ 学号：_20100034 完成日期：_2010/6/26 1. 【问题描述】 小明希望设计一个方案，从编号为1 的交叉路口出发，每次必须沿街道去往街道另一端的路口，再从新的路口出发去往下一个路口，直到所有的街道都经过了正好一次。 输入数据格式输入的第一行包含两个整数n, m(1 ≤n≤10, n-1 ≤m≤20) ，表示交叉路口的数量和街道的数量，交叉路口从1 到n 标号。 接下来m行，每行两个整数a, b ，表示和标号为a 的交叉路口和标号为b 的交叉路口之间有一条街道，街道是双向的，小明可以从任意一端走向另一端。两个路口之间最多有一条街道。 输出输出格式如果小明可以经过每条街道正好一次，则输出一行包含m+1个整数p1, p 2, p 3, ..., p m+1，表 示小明经过的路口的顺序，相邻两个整数之间用一个空格分隔。如果有多种方案满足条件，则输出字典序最小的一种方案，即首先保证p1最小，p1最小的前提下再保证p2 最小，依此类推。 如果不存在方案使得小明经过每条街道正好一次，则输出一个整数-1 。 2【问题分析】 该算法使用欧拉回路，对于欧拉图，从一个节点出发，从某个节点开始，然后查出一个从这个出发回到这个点的环路径。这种方法不保证每个边都被遍历。如果有某个点的边没有被遍历就让这个点为起点，这条边为起始边，把它和当前的环衔接上。这样直至所有的边都被遍历。这样，整个图就被连接到一起了。 具体步骤: 1。如果此时与该点无相连的点，那么就加入路径中 2。如果该点有相连的点，那么就加入队列之中，遍历这些点，直到没 有相连的点。 3。处理当前的点，删除走过的这条边，并在其相邻的点上进行同样的 操作，并把删除的点加入到路径中去 4。这个其实是个递归过程 3【功能实现】 #include vector< int > vec[maxn]; bool map[maxn][maxn]; int vis[maxn]; int cp[maxn]; int n,m; void pd( int a) { cp[a]=1; vector< int >::iterator it; for (it=vec[a].begin();it!=vec[a].end();it++) { if (!cp[*it]) pd(*it); } } void dfs( int a) { vector< int >::iterator it; for (it=vec[a].begin();it!=vec[a].end();it++) { if (!map[a][*it]) { map[a][*it]=1; map[*it][a]=1; dfs(*it); st.push(*it); } void prt() { st.push(1); while (!st.empty()) { //printf("%d ",st.top()); int ss=st.top(); st.pop(); printf( "%d " ,ss); } } int main() { int num=0; //memset(cp,0,sizeof(cp)); //memset(vis,0,sizeof(vis)); //memset(map,0,sizeof(map)); for (int i=0;i { cp[i]=vis[i]=0; } scanf( "%d %d",&n,&m); int a,b; for (int i=0;i { scanf( "%d %d",&a,&b); vec[a].push_back(b); vec[b].push_back(a); vis[a]++; vis[b]++; } int flag=0; pd(1); for (int i=1;i<=n;++i) { if (cp[i]==0) flag=1; else break ; } if (flag) printf( "-1\n" ); else { for (int i=1;i<=n;++i) { sort(vec[i].begin(),vec[i].end()); if (vis[i]%2==1) ++num; } if (num==0||num==2) { if (num==2) { if (vis[1]%2==1) { dfs(1); prt(); } else printf( "-1\n" ); } else { dfs(1); prt(); } } else { printf( "-1\n" ); } } system( "Pause" ); return 0; }
相关主题
文本预览