数据结构课程设计

发布 2022-10-05 01:40:28 阅读 1509

华南农业大学信息学院。

课程设计实验。

一、 分析题目要求。

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 初始化时每个方格都是关闭的,一个...