最小生成树报告详解.docx

题目：最小生成树 存储结构 //1.头文件 #include stdio.h #include stdlib.h #include time.h //2.本地数据类型定义 #define MAX 435 //30*29/2=435 //3.带权边的定义 /* 定义边(x,y)，权为 w */ typedef struct { int x, y; int w; }edge; //4.本地数组和数据定义 edge e[MAX]; int tag[MAX]; //标志 int father[MAX]; //定义 x 的父节点 基本操作 int cmp(const void *a, const void *b); 操作功能: 比较函数，按权值(相同则按 x 坐标)非降序排序 void Make_Set(int x); 操作功能：初始化集合 int Find_Set(int x); 操作功能：查找 x 元素所在的集合,回溯时压缩路径 void Union(int x, int y, int w); 操作功能：合并 x,y 所在的集合 void Select(); 操作功能：初始化界面 算法设计 // 1.比较函数，按权值(相同则按 x 坐标)非降序排序 int cmp(const void *a, const void *b) { if ((*(edge *)a).w == (*(edge *)b).w) { return (*(edge *)a).x - (*(edge *)b).x; } return (*(edge *)a).w - (*(edge *)b).w; } //2. 初始化集合 void Make_Set(int x) { father[x] = x; tag[x] = 0; } //3. 查找 x 元素所在的集合,回溯时压缩路径 int Find_Set(int x) { while(father[x]) { x=father[x]; } return x; } //4. 合并 x,y 所在的集合 void Union(int x, int y, int w) { if (x == y) return; /* 将标志较小的树连接到标志较大的树后 */ if (tag[x] tag[y]) { father[y] = x; } else { if (tag[x] == tag[y]) { tag[y]++; } father[x] = y; } } //5.初始化界面 void Select(){ printf(\n**********************************\n\n); printf(Welcome to here!please selected:\n); printf( 最小生成树 \n); printf( 1. 随机生成权值\n); printf( 2. 人为输入权值\n); printf( 3.退出\n); printf(\n**********************************\n\n); } 6. //堆的实现 int heap[MAX_N],sz=0; void push(int x) { //自己节点的编号 int i=sz++; while(i0) { //父亲节点的编号 int p=(i-1)/2; //如果已经没有大小颠倒则退出 if(heap[p]=x) break; //把父亲节点的数值放下来，而把自己提上去 heap[i]=heap[p]; i=p; } heap[i]=x; } int pop() { int ret=heap[0]; //最小值 int x=heap[--sz];//要提到根的数值 int i=0 ; //从根开始往下交集 while(i*2+1sz) { //比较儿子的值 int a=i*2+1,b=i*2+2; if(bszheap[b]heap[a]) a=b; //如果已经没有大小颠倒则退出 if(heap[a]=x) break; heap[i]=heap[a];