- 题目
- 第一题
- 维护小根堆性质
- 建大根堆
- 堆排序
- 返回优先队列中优先级最高的元素
- 返回优先队列中优先级最高的元素并删除
- 提高元素优先级
- 添加新元素
- 主函数
- 第二题
- 第三题
题目
第一题 维护小根堆性质
作业要求是维护小根堆性质，但是思想和维护大根堆性质都是一样的，只需要把大于小于符号换一下就可以。
维护大根堆性质伪代码：
维护小根堆性质代码：（有个swap交换函数，很简单，自己添加即可）
void Min_Heapify(int A[], int i, int heapsize){
int l = 2*i;
int r = 2*i + 1;
int smallest = i;
if(l <= heapsize && A[l - 1] < A[i - 1] ){
smallest = l;
}
else
smallest = i;
if(r <= heapsize && A[r - 1] < A[smallest - 1]){
smallest = r;
}
if(smallest != i){
swap(&A[i - 1],&A[smallest - 1]);
Min_Heapify(A, smallest, heapsize);
}
}
建大根堆
同上，换符号即可。
建大根堆伪代码如下：
建立小根堆代码：
void Built_Min_Heap(int A[], int heapsize){
int n = heapsize;
for(int i = n / 2; i > 0; i--)
Min_Heapify(A, i, n);
}
堆排序
堆排序伪代码：
C语言实现堆排序：
void HeapSort(int A[], int heapsize){
Built_Min_Heap(A, heapsize);
for(int i = heapsize; i > 0; i--){
swap(&A[i - 1], &A[0]);
heapsize--;
Min_Heapify(A, 1, heapsize);
}
}
返回优先队列中优先级最高的元素
返回优先队列中优先级最高的元素伪代码：
C语言实现返回优先队列中优先级最高的元素：
int Get_Min(int A[]){
return A[0];
}
返回优先队列中优先级最高的元素并删除
返回优先队列中优先级最高的元素并删除伪代码：
C语言实现返回优先队列中优先级最高的元素并删除：
int Extract_Min(int A[], int heapsize){
int min = A[0];
A[0] = A[heapsize - 1];
heapsize--;
Min_Heapify(A, 1, heapsize);
return min;
}
提高元素优先级
提高元素优先级伪代码：
C语言实现提高元素优先级：
void Decrease_Key(int A[], int i, int k){
A[i] = k;
while (i > 1 && A[i] < A[i/2]){
swap(&A[i], &A[i/2]);
i = i/2;
}
}
添加新元素
添加新元素伪代码：
C语言实现添加新元素：
void Insert(int A[], int key, int heapsize){
heapsize++;
A[heapsize - 1] = 100000000; //最后的位置插入正无穷
Decrease_Key(A, heapsize - 1, key);
}
主函数
int main(){
int a[10] = {6,8,1,2,4,3,9,16,22,5};
int i,heapsize=10;
printf("n堆中的元素是------------------n");
for (i = 0; i < heapsize; i++) //输入堆中元素
printf("%d ", a[i]);
//建立最小堆
printf("n最小堆------------------n");
Built_Min_Heap(a,heapsize);
for (i = 0; i < heapsize; i++)
printf("%d ", a[i]); //输出
//返回优先队列中优先级最小的元素
printf("n优先队列中优先级最小的元素是：%dn",Get_Min(a));
Extract_Min(a,heapsize);
printf("n调用后Extract_Min的最小堆:n");
for (i = 0; i < heapsize-1; i++)
printf("%d ", a[i]); //输出结果
printf("n");
//插入7
Insert(a, 7, heapsize-1);
printf("插入7后的最小堆n");
for (i = 0; i < heapsize; i++)
printf("%d ", a[i]); //输出结果
printf("n插入7后的堆排序n");
HeapSort(a, heapsize);
for (i = 0; i < heapsize; i++)
printf("%d ", a[i]); //输出结果
return 0;
}
第二题
注释写得很详细，就不再细说。
#include#define N 999 #define NUM 10 //元素的数据结构 struct Node{ struct S *head; struct Node *next; int nnum; //元素名字 }; //集合的数据结构 struct S{ struct Node *head; struct Node *tail; int length; //集合内的元素个数（链表长度） int num; //集合名字 }; struct S s[N]; //集合数组 struct Node node[N];//集合内元素数组 int i = 1; void Make_Set(struct Node *x){ x->head = &s[i]; x->next = NULL; x->nnum = i; s[i].tail = x; s[i].head = x; s[i].num = i; s[i].length = 1; //每一个单点集的长度都是‘1’ i++; } void Union(struct S *x,struct S *y){ x->length = x->length + y->length; //实现中间部分断开且连接 x->tail->next = y->head; //实现上部分断开且连接 while (y->head != NULL ){ y->head->head = NULL; y->head->head = x; y->head = y->head->next; } y->head = NULL; //实现下部分断开且连接 x->tail = NULL; x->tail = y->tail; y->tail = NULL; } void Unions(struct S *x,struct S *y){ if(x->length >= y->length) Union(x,y); else Union(y,x); } int Find(struct Node *x){ int flag = 0; for (int i = 0; i < NUM; i++){ while (s[i].head != NULL) { if(s[i].head->nnum == x->nnum){ return s[i].num; //找到名字并返回 flag = 1; } s[i].head = s[i].head->next; } } if (flag == 0){ printf("没有该元素！n"); } } void MyPrint(){ printf("head lethn"); for (int j = 1; j <= NUM; j++){ if(s[j].head != NULL)//判断集合是否为空，如果是空集合就不打印 printf(" %d %dn",s[j].num, s[j].length); } } int main(){ int n; for(int i = 1; i <= NUM; i++) { Make_Set(&node[i]); //创建单点集合 } //合并单点集2和单点集合3 Unions(&s[2],&s[3]); //合并单点集2和单点集合5 Unions(&s[2],&s[5]); //合并单点集7和单点集合8 Unions(&s[7],&s[8]); //合并单点集7和单点集合10 Unions(&s[7],&s[10]); MyPrint(); printf("请输入要找的结点名字："); scanf("%d",&n); printf("n结点%d在集合%d里",n,Find(&node[n])); return 0; }
第三题
注：prim算法并未完全实现，只有思路
prim算法伪代码：
C语言实现prim算法：
#includevoid Min_Heapify(int A[], int i, int heapsize){ int l = 2*i; int r = 2*i + 1; int smallest = i; if(l <= heapsize && A[l] < A[i] ){ smallest = l; } else smallest = i; if(r <= heapsize && A[r] < A[smallest]){ smallest = r; } if(smallest != i){ swap(A[i],A[smallest]); Min_Heapify(A, smallest, heapsize); } } int Extract_Min(int A[], int heapsize){ int min = A[1]; A[1] = A[heapsize - 1]; heapsize--; Min_Heapify(A, 1, heapsize); return min; } void Decrease_Key(int A[], int i, int k){ A[i] = k; while (i > 1 && A[i] < A[i/2]){ swap(&A[i], &A[i/2]); i = i/2; } } //book数组用来记录哪些顶点已经放入生成树中 int dis[7], book[7] = {0}; //h数组用来保存堆，pos数组用来存储每个顶点在堆中的位置，heapsize为堆的大小 int h[7], pos[7], heapsize; //交换函数，用来交换堆中的两个元素的值 void swap(int x,int y) { int t; t=h[x]; h[x]=h[y]; h[y]=t; //同步更新pos t=pos[h[x]]; pos[h[x]]=pos[h[y]]; pos[h[y]]=t; } int main(){ int inf = 99999999; //count用来记录生成树中顶点的个数，sum用来记录存储路径之和 int count=0, sum=0; //将1号顶点加入生成树，book数组来标记一个顶点是否已经加入生成树 book[1] = 1; count++; int n, m, i, j,k; int u[19], v[19], w[19], first[7], next[19]; //读入n和m,n表示顶点个数,m表示边的条数 printf("请输入顶点数和边数："); scanf("%d %d",&n,&m); //开始读入边 for(i = 1; i <= m; i++) { scanf("%d%d%d",&u[i] ,&v[i] ,&w[i]); } //这里是无向图，所以需要将所有的边再反向存储一次 for(i = m + 1; i <= 2*m; i++) { u[i] = v[i-m]; v[i] = u[i-m]; w[i] = w[i-m]; } //开始使用邻接表存储边 for( i= 1; i <= n; i++) { first[i] = -1; } for(i = 1; i <= 2*m; i++) { next[i] = first[u[i]]; first[u[i]] = i; } //初始化dis数组，这里是1号顶点到其余各个顶点的初始距离 dis[1] = 0; for(i = 2; i <= n; i++) { dis[i] = inf; } k = first[1]; while(k != -1) { dis[v[k]] = w[k]; k = next[k]; } //初始化堆 heapsize = n; for(i = 1; i <= heapsize; i++) { h[i] = i; pos[i] = i; } for(i = heapsize/2; i >= 1; i--) { Min_Heapify(h,i,heapsize); } //先弹出一个堆顶元素，因为此时堆顶是1号顶点 Extract_Min(h,heapsize); while(count < n) { j = Extract_Min(h,heapsize); book[j] = 1; count++; sum = sum + dis[j]; //扫描当前顶点j所有的边，再以j为中间结点，更新生成树到每一个非树顶点的距离 k = first[j]; while(k != -1) { if(book[v[k]] == 0 && dis[v[k]] > w[k]) { //更新距离 dis[v[k]] = w[k]; //pos[v[k]]存储的是顶点v[k]在堆中的位置 Decrease_Key(h,pos[v[k]], w[k]); } k = next[k]; } } printf("最短路径长度为：%d",sum); return 0; }
