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

《程序设计》课程设计

姓 名：王
学 号：20100034
班 级：软件工程00班
指导教师： 王会青
成 绩：

2010年6月

实验一.构造可以使n个城市连接的最小生成树
专业：__软件工程___ 班级：__软件 姓名：_王___ 学号：_20100034
完成日期：_2010/6/26________
一、【问题描述】
给定一个地区的n个城市间的距离网，用Prim算法或Kruskal算法建立最小生成树，并计算得到的最小生成树的代价。
1 城市间的道路网采用邻接矩阵表示，邻接矩阵的存储结构定义采用课本中给出的定义，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。
2 显示出城市间道路网的邻接矩阵。
3 最小生成树中包括的边及其权值，并显示得到的最小生成树的总代价。
4 输入城市数、道路数→输入城市名→输入道路信息→执行Kruskal 算法→执行 Prim 算法→输出最小生成树
二、【问题分析】
1. 抽象数据类型结构体数组的定义：
#ifndef 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]; //顶点向量
AdjMatrix arcs; //邻接矩阵
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<G.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.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; ++i)
{
在其余G.vexnum-1个城市中找到离辅助数组中标记的道路最小值；
显示找到的道路；
标记新找到的城市；
}
}

********************** Minimum*****************
Status Minimum(closedge closeEdge, int n)
{
在辅助数组中找到道路值最小的道路的两点城市：
if ((closeEdge[i].lowcost != 0) && (minTemp > closeEdge[i].lowcost))
返回该城市在 G 中的位置
}

三、【功能实现】
#include <iostream.h>
#include <stdio.h>
#include <string.h>
#include <windows.h>

#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<<endl<<endl;
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个城市连接的最小生成树\n");
printf("请输入城市数、道路数(至少6个城市，10条道路)：");
cin>>G.vexnum>>G.arcnum;

for (i=0; i<G.vexnum; ++i) //构造顶点向量
{
printf("请输入第 %d 个城市名（共 %d 个）:", i+1, G.vexnum);
cin>>G.vexs[i];
}

for (i=0; i<G.vexnum; ++i) //初始化邻接矩阵
{
for (j=0; j<G.vexnum; ++j)
{
G.arcs[i][j].adj = INFINITY;
// G.arcs[i][j].info = NULL;
}
}

printf("请输入一条道路连接的两个城市名及权值:\n");
for (k=0; k<G.arcnum; ++k) //构造邻接矩阵
{
printf("共%3d条道路，第%3d条道路：", G.arcnum,k+1);
cin>>v1>>v2>>w; //输入一条边依附的顶点及权值
i = LocateVex(G, v1); //确定v1、v2在G中的位置
j = LocateVex(G, v2);
G.arcs[i][j].adj = w; //弧<v1,v2>的权值

G.arcs[j][i] = G.arcs[i][j]; //置<v1,v2>的对称弧<v2,v1>
}

return OK;
}//CreateUDN

//MiniSpan Tree PRIM.h
Status Minimum(closedge closeEdge, int n)
{
int i, flag, minTemp = INFINITY;
for (i=0; i<n; ++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<G.vexnum; ++j) //辅助数组初始化
{
if (j != k)
{
strcpy(closeEdge[j].adjvex, u);
closeEdge[j].lowcost = G.arcs[k][j].adj;
}
}

cout<<"\n\n+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\\\n";
cout<<"|用Prim算法求最小生成树的各条边依次为：\n-----";
closeEdge[k].lowcost = 0; //初始，U={u};
for (i=1; i<G.vexnum; ++i) //选择其余 G.vexnum-1 个顶点
{
k = Minimum(closeEdge, G.vexnum); //求出 T 的下一个结点：第 k 顶点
//此时 closeEdge[k].lowcost = MIN{closeEdge[vi].lowcost | closeEdge[vi].lowcost > 0, vi∈V-U}
cout<<'<'<<closeEdge[k].adjvex<<','<<G.vexs[k]<<'>'; //输出生成树的边
totalCost += closeEdge[k].lowcost;
closeEdge[k].lowcost = 0; //第 k 顶点并入 U 集

for (j=0; j<G.vexnum; ++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|总代价："<<totalCost<<endl;
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)，表示自然数的个数；第2~n+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;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);
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）输出输入格式
输入时，为竖行依此输入文件，且为数字。且为9个以内的数字。 输出时，分为两行，第一列为数据，第二列为次数。 3. 【设计功能的实现】
#include <stdio.h> int main() {
int a[100]; //创建容纳文件数据的数组 int i;
FILE* fp=fopen("count.txt","a+"); //用只读/的方式打开文件 if(fp==NULL) {
printf("无文件"); //若没有文件则返回—1 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; }
printf("结果为：\n数据 结果\n"); int count;
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);
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, p2, p3, ..., pm+1，表示小明经过的路口的顺序，相邻两个整数之间用一个空格分隔。如果有多种方案满足条件，则输出字典序最小的一种方案，即首先保证p1最小，p1最小的前提下再保证p2最小，依此类推。
如果不存在方案使得小明经过每条街道正好一次，则输出一个整数-1。
测试数据一
输入：
输出：
4 5
1 2
1 3
1 4
2 4
3 4
1 2 4 1 3 4
输出说明：城市的地图和小明的路径如下图所示。

测试数据二
输入：
输出：
4 6
1 2
1 3
1 4
2 4
3 4
2 3
-1

输出说明：城市的地图如下图所示，不存在满足条件的路径。

2【问题分析】
该算法使用欧拉回路，对于欧拉图，从一个节点出发，从某个节点开始，然后查出一个从这个出发回到这个点的环路径。这种方法不保证每个边都被遍历。如果有某个点的边没有被遍历就让这个点为起点，这条边为起始边，把它和当前的环衔接上。这样直至所有的边都被遍历。这样，整个图就被连接到一起了。
具体步骤:
1。如果此时与该点无相连的点，那么就加入路径中
2。如果该点有相连的点，那么就加入队列之中，遍历这些点，直到没有相连的点。
3。处理当前的点，删除走过的这条边，并在其相邻的点上进行同样的操作，并把删除的点加入到路径中去。
4。这个其实是个递归过程。

3【功能实现】
#include<iostream>
#include<stack>
#include<vector>
#include<algorithm>
#include<cstdio>
#include <windows.h>
using namespace std;
const int maxn=10005;
stack<int> st;
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<maxn;++i)
{
cp[i]=vis[i]=0;
}

scanf("%d %d",&n,&m);
int a,b;
for(int i=0;i<m;++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;
}

4 【实验结果】

5【心得体会】
通过这个实验，我掌握了欧拉回路的基本思想。明白了用欧拉算法解决实际问题的具体步骤。而且明白了用算法解决实际问题的思维方法。

实验4.消除类游戏
专业：__软件工程___ 班级：__软件 姓名：_王__ 学号：_20100034
完成日期：_2010/6/28_______
1【问题描述】
消除类游戏是深受大众欢迎的一种游戏，游戏在一个包含有n行m列的游戏棋盘上进行，棋盘的每一行每一列的方格上放着一个有颜色的棋子，当一行或一列上有连续三个或更多的相同颜色的棋子时，这些棋子都被消除。当有多处可以被消除时，这些地方的棋子将同时被消除。
现在给你一个n行m列的棋盘(1≤n,m≤30)，棋盘中的每一个方格上有一个棋子，请给出经过一次消除后的棋盘。
请注意：一个棋子可能在某一行和某一列同时被消除。
输入数据格式：
输入的第一行包含两个整数n, m，用空格分隔，分别表示棋盘的行数和列数。接下来n行，每行m个整数，用空格分隔，分别表示每一个方格中的棋子的颜色。颜色使用1至9编号。
输出数据格式：
输出n行，每行m个整数，相邻的整数之间使用一个空格分隔，表示经过