华南农业大学信息学院。
课程设计实验。
一、 分析题目要求。
1、在这个课程设计中，我做的是并查集。主要实现以下的功能：
1) 初始化。
2) 合并结合。
3) 查找节点所在集合。
4) 相关应用。
初始化：把每个点所在集合初始化为其自身。
通常来说，这个步骤在每次使用该数据结构时只需要执行一次，无论何种实现方式时间复杂度均为o(n)。
查找：查找元素所在的集合，即根节点。
合并：将两个元素所在的集合合并为一个集合。
通常来说，合并之前，应先判断两个元素是否属于同一集合，这可用上面的“查找”操作实现。
为了在这个程序实现中更好地表现出相关功能，我用了一个具体的例子，也即是判断多个城市之间的并查集，并求出不同城市的距离长短。
2、各个函数命名，包含的参数，返回值类型。
int menu函数主菜单。
void xin_input第二级菜单。
boolcmp(node p1,node p2)
//并查集。
void set(int x初始化。
int find(int x寻找数据的共同祖先。
void union(intx,int y合并函数。
//算法。void kruskalkruskal算法。
int primprim算法。
void shortestpath_dij(intx,int ydijkstra算法。
void shortestpath_floydfloyd算法。
void shuru接收函数（接收输入的数据）
void chaxun查询函数。
//功能函数。
voidchaxun_func()
void judge()
int main主函数。
3、程序的运行。
二、 解题思路。
1、 单链表实现。
一个节点对应一座城市，在同一个集合中的节点串成一条链表就得到了单链表的实现。在集合中我们以单链表的第一个节点作为集合的代表元。于是每个节点x（x也是城市的编号）应包含这些信息：
指向代表元即表首的指针head[x]，指向表尾的指针tail[x]，下一个节点的指针next[x]。
2、 两大优化。
第一个优化是启发式合并。在优化单链表时，我们将较短的表链到较长的表尾，在这里我们可以用同样的方法，将深度较小的树指到深度较大的树的根上。这样可以防止树的退化，最坏情况不会出现。
find-set(x)的时间复杂度为o(log n)，problem-relations时间复杂度为o(n + logn (m+q))。sub-link(a,b)作相应改动。
第二个优化是路径压缩。它非常简单而有效。如图所示，在find-set(1)时，我们“顺便”将节点1, 2, 3的父节点全改为节点4，以后再调用-find-set(1)时就只需o(1)的时间。
三、 调试分析。
由于此程序实现的功能较为简单，故在调试过程中也没遇到很大的问题。主要的问题在于着手写**的时候，由于不熟悉及很多算法未接触过，故陷入了无从下手的境地。但最后通过搜索大量的资料终于解决。
期间用到的测试数据是多组邻接矩阵，没有发现bug；对于算法的不足之处，主要是时间复杂度过大，**未能很好优化，另外对于改进的设想，也就是前面提到的两大优化，但由于自己未能实现，故只好作罢了。
所以，此次最大的感受就是自己的知识基础很薄弱，而且对于很多思维性和逻辑性要求很高的东西自己难以理解。所以自己深知要加强这方面的锻炼。更为自己过去一学期没能好好掌握的知识而感到痛心，有机会一定要补回来吧。
四、附录。带注释的源程序。
#include <>
#include <>
#include
#include
#include<>
using namespace std;
int n = 0;
int a[100][100];
int menu()
int m;
printf并查集");
printfn");
printf1 输入城市之间的信息");
printf2 判断是否能构成一个并查集");
printf3 查询信息");
printf4 退出");
printfn");
printf请输入所选功能1--4");
scanf("%d",&m);
return m;
voidxin_input()
system("cls");
printfn");
printf1遍历所有城市的并查集");
printf2查询两个城市之间的距离");
printf3 退出");
printfn");
/以下为克鲁斯卡尔算法。
typedefstruct node //构造一个结构体，两个城市可以看成起点和终点，之间的路道可以看成一个边。
intst; /起点。
inted; /终点。
int dis;//距离。
node;node p[1000];
int pre[1000],rank[1000];
boolcmp(node p1,node p2)
return <
/下面三个函数是并查集，其作用是检验当一条边添加进去，是否会产生回路。
void set(int x)
pre[x] =x;//初始化。
rank[x] =0;
int find(int x)//找到这个点的祖先。
if(x !=pre[x])
pre[x] =find(pre[x]);
return pre[x];
void union(intx,int y)//将这两个添加到一个集合里去。
x = find(x);
y = find(y);
if(rank[x] >rank[y])
pre[y] =x;
rank[x] +
elsepre[y] =x;
voidkruskal()
intans = 0,i,j,k = 0;
for(i = 1;i <=n;i ++
set(i);
for(i = 1;i <=n;i ++
for(j = i + 1;j <=n;j ++
sort(p + 1,p + k + 1,cmp);/把所有的边按从小到大进行排序。
int count = 0;
for(i = 1;i <=k;i ++
if(find(p[i].st) !find(p[i].ed))/如果这两点连接在一起不构成一个回路，则执行下面操作。
printf("遍历所有城市的最短路程为： %d",ans);/最短遍历的路程。
/printfn");
数据结构课程设计
课程设计说明书 题目哈夫曼编码问题的设计和实现。课程名称数据结构课程设计。院 系 部 中心。专业。班级。学生姓名。学号。设计地点。指导教师。设计起止时间 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 初始化时每个方格都是关闭的，一个...