《数据结构》课程设计报告。
实验题目： 一个有n个节点的无向网，从一个点出发寻找最短hamilton回路。
实验目的：熟悉图和网的操作，了解hamilton回路的概念以及相应的基本算法知识。
◎实验内容：生成一个具有n个节点的无向网，并且找到从一个点出发的最短hamilton回路。
一、需求分析。
本实验的任务是在给定的无向图（网）中寻找从某一顶点出发的最短哈密尔顿路径。
1、输入的形式和输入值的范围；
本实验需要输入的变量有图的阶数、图的顶点信息、图的邻接矩阵及起始顶点。
图的阶数为小于100（可通过修改maxvexnum值修改）的正整数，如：4；
图的顶点信息为以空格分隔的字符，如：a b c d；
由于存在哈密尔顿路径的图中边数较多，故未考虑三元数组输入形式，仅以矩阵输入，如：
起始顶点为以上输入中的任一顶点，如：a。
2、输出的形式；
本实验的输出包括两部分，哈密尔顿路径及哈密尔顿路径长度。按1中输入输出结果为：
最短哈密尔顿路径为：
a c b d a
路径长度为：
3、程序所能达到的功能；
对于给定的输入程序首先通过贪心算法和回溯算法求出近似哈密尔顿路径，然后利用二边逐次修正法修正哈密尔顿路径。
二概要设计。
为了实现上述操作，应以链表为存储结构。
1．基本操作：
void creatgraph()
操作结果：根据建立图；
void find()
初始条件：图已建立；
操作结果：利用贪心算法和回溯算法寻找近似哈密尔顿路径；
void revise()
初始条件：近似哈密尔顿路径已找到；
操作结果：对近似哈密尔顿路径利用二边逐次修正法修正；
void display()
操作结果：输出哈密尔顿路径及其长度。
2．本程序包含五个模块：
1）主程序模块；
2）图创建模块；
3）寻找哈密尔顿路径模块；
4）修正模块；
5）输出模块；
3. 用到的算法：
1）贪心算法；
2）回溯算法；
3）二边逐次修正算法；
1)任取初始h圈：co=v1,v2,…,vi,…,vj,..vn,v1；
2)对所有的i,j，13)对c重复步骤2)，直到条件不满足为止，最后得到的c即为所求。
三详细设计。
1.图相关结构：
char vertex[maxvexnum顶点信息。
int initialmatrix[maxvexnum][maxvexnum初始矩阵。
int matrix[maxvexnum][maxvexnum距离矩阵。
int rank图的阶数。
int visited[maxvexnum访问标志。
int hamiltonpath[maxvexnum+1哈密尔顿路径。
int distance路径长度。
2．每个模块的分析：
1）主程序模块：
int main()
creatgraph();
find();
revise();
display();
return 0;
2）创建图模块：
void creatgraph()
int i,j;
printf("请输入图的阶数：");
scanf("%d",&rank);
getchar();
printf("请输入顶点信息（用空格分隔）：");
for(i=0;i
printf("请输入图的邻接矩阵（无路径为-1，本身为0）：");
for(i=0;i
//令距离矩阵初始值与初始矩阵相同。
for(i=0;i
3)寻找近似哈密尔顿路径模块。
void find()
int i,startoeder,nextpoint,top=-1;
char startpoint;
for(i=0;i
hamiltonpath[rank]=-1;
printf("请输入起始顶点（定点字母）：");
scanf("%c",&startpoint给出起始顶点。
getchar();
for(i=0;i
hamiltonpath[++top]=startoeder起始顶点入栈。
visited[startoeder]=1起始顶点标记为已访问。
while (top
else存在定点未被访问。
下顶点找到。
if(nextpoint!=-1)
下顶点未找到，距离矩阵恢复并退栈。else
4）修正模块：
void revise()
int i,j,k,repoint,dmin,d1,d2,dist,flag=0,t;
数据结构课程设计
课程设计说明书 题目哈夫曼编码问题的设计和实现。课程名称数据结构课程设计。院 系 部 中心。专业。班级。学生姓名。学号。设计地点。指导教师。设计起止时间 2008 年6月 2日至 2008 年 6月 6 日。目录。1 问题描述 2 1.1 题目内容 2 1.2 基本要求 2 1.3 测试数据 2 2...
数据结构课程设计
数据结构 课程设计。实验报告。学院 信息工程学院。班级 姓名 学号 指导老师 题目2 一元多项式的计算。1 实验目的。1 掌握链表的灵活运用 2 学习链表初始化和建立一个新的链表 3 知道怎样去实现链表删除结点操作与插入结点 4 理解链表的基本操作 包括数据域数据的相加 并能灵活运用。2 实验内容。...
数据结构课程设计
班级 信计 1102 姓名 李娜娜。学号 1108060209 设计日期 2013.07.15 西安科技大学计算机学院 1.实验题目 编制一个演绎扫雷游戏的程序。2.问题描述。做一个n x m的扫雷游戏，每个方格包含两种状态 关闭 closed 和打开 opened 初始化时每个方格都是关闭的，一个...