算法程序设计实验报告.doc

程序设计课程设计姓 名：王学 号：20100034班 级：软件工程00班指导教师： 王会青 成 绩：2010年6月实验一.构造可以使n个城市连接的最小生成树专业：_软件工程_ 班级：_软件 姓名：_王_ 学号：_20100034完成日期：_2010/6/26_一、【问题描述】给定一个地区的n个城市间的距离网，用Prim算法或Kruskal算法建立最小生成树，并计算得到的最小生成树的代价。1 城市间的道路网采用邻接矩阵表示，邻接矩阵的存储结构定义采用课本中给出的定义，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。2 显示出城市间道路网的邻接矩阵。3 最小生成树中包括的边及其权值，并显示得到的最小生成树的总代价。4 输入城市数、道路数输入城市名输入道路信息执行Kruskal 算法执行 Prim 算法输出最小生成树二、【问题分析】1. 抽象数据类型结构体数组的定义：#ifndef ADJACENCYMATRIXED/防止该头文件被重复引用#define ADJACENCYMATRIXED/而引起的数据重复定义#define INFINITY32767/最大值#define MAX_VERTEX_NUM20/最大顶点个数typedef intVRType;/权值，即边的值typedef charInfoType;/附加信息的类型，后面使用时会定义成一个指针typedef charVertexTypeMAX_VERTEX_NUM;/顶点类型typedef enum DG=1, DN, UDG, UDN GraphKind;/有向图，有向网，无向图，无向网typedef struct ArcCellVRTypeadj;/VRType 是顶点关系类型。对无权图，用 1 或 0 表示相邻否；对带权图，则为权值类型。InfoType*info;/该弧关系信息的指针ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef structVertexTypevexsMAX_VERTEX_NUM;/顶点向量AdjMatrixarcs;/邻接矩阵intvexnum, arcnum;/图的当前顶点数和弧数GraphKindkind;/图的种类标志MGraph;typedef struct/普里姆算法辅助数组的定义VertexTypeadjvex;VRTypelowcost;closedgeMAX_VERTEX_NUM;#endif/结束if2 程序模块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);/以邻接矩阵的形式显示网 Gvoid 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.vexsi输入表示道路的两个城市及道路值G.arcsij.adj返回 OKPrim算法化辅助数组closeEdgefor (i=1; iG.vexnum; +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.vexsi, 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(closeEdgej.adjvex, u);closeEdgej.lowcost = G.arcskj.adj;for (i=1; i closeEdgei.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.hMGraph G;/全局变量Gint main(int argc, char * argv);/主函数Status LocateVex(MGraph G, VertexType v);/判断城市 v 在网 G 中的位置Status CreateUDN(MGraph &G);/创建网 G 的邻接矩阵void DisplayNet(MGraph G);/以邻接矩阵的形式显示网 Gvoid 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.vexs0);DeleteInfo(G);coutendlG.vexnumG.arcnum;for (i=0; iG.vexsi;for (i=0; iG.vexnum; +i)/初始化邻接矩阵for (j=0; jG.vexnum; +j)G.arcsij.adj = INFINITY;/G. = NULL;printf(请输入一条道路连接的两个城市名及权值:n);for (k=0; kv1v2w;/输入一条边依附的顶点及权值i = LocateVex(G, v1);/确定v1、v2在G中的位置j = LocateVex(G, v2);G.arcsij.adj = w;/弧的权值G.arcsji = G.arcsij;/置的对称弧return OK;/CreateUDN/MiniSpan Tree PRIM.hStatus Minimum(closedge closeEdge, int n)int i, flag, minTemp = INFINITY;for (i=0; i closeEdgei.lowcost)minTemp = closeEdgei.lowcost;flag = i;return flag;void MiniSpanTree_PRIM(MGraph G, VertexType u)/用普里姆算法从第 u 个顶点出发构造网 G 的最小生成树 T，输出 T 的各条边。/记录从顶点集 U 到 V-U 的代价最小的边的辅助数组定义见 AdjacencyMatrix.hint i, j, k, totalCost=0;closedge closeEdge;k = LocateVex(G, u);for (j=0; jG.vexnum; +j)/辅助数组初始化if (j != k)strcpy(closeEdgej.adjvex, u);closeEdgej.lowcost = G.arcskj.adj;coutnn+n;cout|用Prim算法求最小生成树的各条边依次为：n-;closeEdgek.lowcost = 0;/初始，U=u;for (i=1; i 0, viV-UcoutcloseEdgek.adjvex,G.vexsk;/输出生成树的边totalCost += closeEdgek.lowcost;closeEdgek.lowcost = 0;/第 k 顶点并入 U 集for (j=0; jG.vexnum; +j)if (G.arcskj.adj closeEdgej.lowcost)/新顶点并入 U 后重新选择最小边strcpy(closeEdgej.adjvex, G.vexsk);closeEdgej.lowcost = G.arcskj.adj;coutn|总代价：totalCostendl;cout+/n;/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)，表示自然数的个数；第2n+1行每行一个自然数。 结果保存在文件count的尾部，其中结果包含m行（m为n个自然数中不相同数的个数），按照自然数从小到大的顺序输出。每行输出两个整数，分别是自然数和该数出现的次数，其间用一个空格隔开。 (2)设计思路 首先必须有文件的打开和关闭语句，将文件的内容读取到数组a中，然后对数组进行排列和对比，计数。最终输出数据和次数。并写入文件的尾部。 A为容纳数据的数组，fopen为文件打开函数，fscanf为文件读取函数，然后进行冒泡排序。排序之后的内容由while设置条件，用if进行判断。在不等于时，中间嵌套了一个while循环，进行往后的排查。最后输出数据和次数。 下面是关键步骤： FILE* fp=fopen(count.txt,a+); /用只读/的方式打开文件 if(fp=NULL) printf(无文件); /若没有文件则返回1 return -1; for(i=0;i9;i+) fscanf(fp,%d,&ai); /读取文件 fscanf(fp,n); int j,t; for (i=1;i9;i+) for(j=0;jaj+1) /冒泡排序 t=aj; aj=aj+1; aj+1=t; for(i=0;i9;i+) count=1; if (ai!=ai+1) printf(%dt%dn,ai,count); fprintf(fp,%dt%dn,ai,ai); i+; 对数字的循环查找和控制条件， if(ai = ai + 1) while(ai = ai + 1) count+; i+; （3）输出输入格式 输入时，为竖行依此输入文件，且为数字。且为9个以内的数字。 输出时，分为两行，第一列为数据，第二列为次数。 3. 【设计功能的实现】 #include int main() int a100; /创建容纳文件数据的数组 int i; FILE* fp=fopen(count.txt,a+); /用只读/的方式打开文件 if(fp=NULL) printf(无文件); /若没有文件则返回1 return -1; for(i=0;i9;i+) fscanf(fp,%d,&ai); /读取文件 fscanf(fp,n); int j,t; for (i=1;i9;i+) for(j=0;jaj+1) /冒泡排序 t=aj; aj=aj+1; aj+1=t; printf(结果为：n数据 结果n); int count; for(i=0;i9;i+) count=1; if(ai!=ai+1) printf(%dt%dn,ai,count); printf(fp,%dt%dn,ai,ai); i+; if(ai = ai + 1) while(ai = ai + 1) count+; i+; printf(%dt%dn, ai, count); fprintf(fp,%dt%dn, ai, count); fclose(fp); /关闭文件 return 0; 4【实例测试及运行结果】 5.【心得体会】 本次实验使我对于文件的打开和关闭语句有了更深的理解。有打开必须有关闭。同时在这次的设计中，我学习到了用泛洪算法解决实际问题的基本思维和步骤。使我对算法的层次性更加清楚，更加加深了对算法的理解。实验三送 货专业：_软件工程_ 班级：_软件 姓名：_王_ 学号：_20100034完成日期：_2010/6/26_1.【问题描述】小明希望设计一个方案，从编号为1的交叉路口出发，每次必须沿街道去往街道另一端的路口，再从新的路口出发去往下一个路口，直到所有的街道都经过了正好一次。输入数据格式输入的第一行包含两个整数n, m(1n10, n-1m20)，表示交叉路口的数量和街道的数量，交叉路口从1到n标号。接下来m行，每行两个整数a, b，表示和标号为a的交叉路口和标号为b的交叉路口之间有一条街道，街道是双向的，小明可以从任意一端走向另一端。两个路口之间最多有一条街道。输出输出格式如果小明可以经过每条街道正好一次，则输出一行包含m+1个整数p1, p2, p3, ., pm+1，表示小明经过的路口的顺序，相邻两个整数之间用一个空格分隔。如果有多种方案满足条件，则输出字典序最小的一种方案，即首先保证p1最小，p1最小的前提下再保证p2最小，依此类推。如果不存在方案使得小明经过每条街道正好一次，则输出一个整数-1。测试数据一输入：输出：4 51 21 31 42 43 41 2 4 1 3 4输出说明：城市的地图和小明的路径如下图所示。测试数据二输入：输出：4 61 21 31 42 43 42 3-1输出说明：城市的地图如下图所示，不存在满足条件的路径。2【问题分析】 该算法使用欧拉回路，对于欧拉图，从一个节点出发，从某个节点开始，然后查出一个从这个出发回到这个点的环路径。这种方法不保证每个边都被遍历。如果有某个点的边没有被遍历就让这个点为起点，这条边为起始边，把它和当前的环衔接上。这样直至所有的边都被遍历。这样，整个图就被连接到一起了。具体步骤:1。如果此时与该点无相连的点，那么就加入路径中2。如果该点有相连的点，那么就加入队列之中，遍历这些点，直到没有相连的点。3。处理当前的点，删除走过的这条边，并在其相邻的点上进行同样的操作，并把删除的点加入到路径中去。4。这个其实是个递归过程。3【功能实现】#include #include #include #include #include#include using namespace std; const int maxn=10005; stack st; vector vecmaxn; bool mapmaxnmaxn; int vismaxn; int cpmaxn; int n,m; void pd(int a) cpa=1; vector:iterator it; for(it=veca.begin();it!=veca.end();it+) if(!cp*it) pd(*it); void dfs(int a) vector:iterator it; for(it=veca.begin();it!=veca.end();it+) if(!mapa*it) mapa*it=1; map*ita=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;imaxn;+i) cpi=visi=0; scanf(%d %d,&n,&m); int a,b; for(int i=0;im;+i) scanf(%d %d,&a,&b); veca.push_back(b); vecb.push_back(a); visa+; visb+; int flag=0; pd(1); for(int i=1;i=n;+i) if(cpi=0) flag=1; else break; if(flag) printf(-1n); else for(int i=1;i=n;+i) sort(veci.begin(),veci.end(); if(visi%2=1) +num; if(num=0|num=2) if(num=2) if(vis1%2=1) dfs(1); prt(); else printf(-1n); else dfs(1); prt(); else printf(-1n); system(Pause); return 0; 4 【实验结果】5【心得体会】 通过这个实验，我掌握了欧拉回路的基本思想。明白了用欧拉算法解决实际问题的具体步骤。而且明白了用算法解决实际问题的思维方法。 实验4.消除类游戏 专业：_软件工程_ 班级：_软件 姓名：_王_ 学号：_20100034完成日期：_2010/6/28_1【问题描述】消除类游戏是深受大众欢迎的一种游戏，游戏在一个包含有n行m列的游戏棋盘上进行，棋盘的每一行每一列的方格上放着一个有颜色的棋子，当一行或一列上有连续三个或更多的相同颜色的棋子时，这些棋子都被消除。当有多处可以被消除时，这些地方的棋子将同时被消除。现在给你一个n行m列的棋盘(1n,m30)，棋盘中的每一个方格上有一个棋子，请给出经过一次消除后的棋盘。请注意：一个棋子可能在某一行和某一列同时被消除。输入数据格式：输入的第一行包含两个整数n, m，用空格分隔，分别表示棋盘的行数和列数。接下来n行，每行m个整数，用空格分隔，分别表示每一个方格中的棋子的颜色。颜色使用1至9编号。输出数据格式：输出n行，每行m个整数，相邻的整数之间使用一个空格分隔，表示经过一次消除后的棋盘。如果一个方格中的棋子被消除，则对应的方格输出0，否则输出棋子的颜色编号。【测试数据】为方便调试程序，可将输入数据先写入一个文本文件，然后从文件读取数据处理，这样可避免每次运行程序时都要从键盘输入数据。测试数据一输入：输出：4 52 2 3 1 23 4 5 1 42 3 2 1 32 2 2 4 42 2 3 0 23 4 5 0 42 3 2 0 30 0 0 4 4输出说明：棋盘中第4列的1和第4行的2可以被消除，其他的方格中的棋子均保留。测试数据二输入：输出：4 52 2 3 1 23 1 1 1 12 3 2 1 32 2 3 3 32 2 3 0 23 0 0 0 02 3 2 0 32 2 0 0 0输出说明：棋盘中所有的1以及最后一行的3可以被同时消除，其他的方格中的棋子均保留。2【问题分析】3【功能实现】#include stdafx.h#include #include using namespace std;int