printf(\
for(j=0;j<=n-1;j++) if(matrix[k][j] } main( ) { int matrix[n][n]={{max,6,1,5,max,max},{6,max,5,max,3,max},{1,5,max,max,6,4}, {5,max,max,max,max,2},{max,3,6,max,max,6},{max,max,4,2,6,max}}; prim(matrix,5); } 4. 在链式存储结构上实现有向无环图的拓扑排序算法。其中函数createadjlist的功能是实现建立有向图，函数topsort的功能是实现拓补排序。 #include \#include \#define m 100 #define n 7 #define e 8 typedef struct node1{int info;int adjvertex; struct node1 *nextarc;}glinklistnode; typedef struct node2{int vertexinfo;glinklistnode *firstarc;}glinkheadnode; void createadjlist(glinkheadnode g[ ]) { int i,j,k; glinklistnode *p; for(i=0;i scanf(\ p=(glinklistnode *)malloc(sizeof(glinklistnode));p->adjvertex=j; p->nextarc=g[i].firstarc; g[i].firstarc=p; } } void toposort(glinkheadnode g[ ]) { int i,v,w,sum=0, indegree[n]; struct {int s[n];int top;} stack; glinklistnode *p; for (i=0; i for (i=0; i printf(\ v=stack.s[stack.top]; stack.top=stack.top-1; p=g[v].firstarc; while (p!=0) { w=p->adjvertex;indegree[w]=indegree[w]-1; - 16 - if (indegree[w]==0) {stack.top=stack.top+1; stack.s[stack.top]=w;} p=p->nextarc; } } if(sum main( ) { glinkheadnode g[m]; createadjlist(g); toposort(g); } - 17 - 实验六 排序 一、 实验目标 1. 掌握插入排序在顺序存储结构上的实现。 2. 掌握交换排序在顺序存储结构上的实现。 3. 掌握选择排序在顺序存储结构上的实现。 4. 掌握归并排序在顺序存储结构上的实现。 5. 理解基数排序在链式存储结构上的实现。 二、 实验内容 1. 插入排序在顺序存储结构上的实现。其中函数straightinsertsort的功能是实现直接插入排序，函数biinsertsort的功能是实现折半插入排序，函数shellsort的功能是实现希尔排序，库函数random的功能是产生一个随机整数且该随机数的取值范围在0到num-1，其中num是其形式参数。 #include \#include “stdlib.h” typedef int datatype; #define m 10 struct record {int key;datatype others;}; void straightinsertsort(struct record r[ ],int n) { int i,j; struct record temp; for(i=1;i<=n-1;i++) {for(temp=r[i],j=i-1; j>=0; j--) if(temp.key void biinsertsort(struct record r[ ],int n) { int i,j,low,mid,high; struct record temp; for(i=1;i<=n-1;i++) { low=0; high=i-1; while(low<=high){mid=(low+high)/2;if(r[i].key>r[mid].key)low=mid+1; else high=mid-1;} for(temp=r[i],j=i-1; j>=low; j--) r[j+1]=r[j]; r[low]=temp; } } void shellsort(struct record r[ ], int n) { int i,j,h; struct record temp; for(h=n/2;h>=1;h=h/2) for(j=h;j<=n-1;j++) { for(temp=r[j], i=j-h; i>=0; i=i-h) if (r[i].key>temp.key) r[i+h]=r[i];else break; r[i+h]=temp; } } - 18 - main( ) { struct record r[m]; int i; for( i=0; i<=m-1; i++) r[i].key=random(100); straightinsertsort(r,m); for( i=0; i<=m-1; i++) printf(“%d\\t”,r[i].key); printf(“\\n”); for( i=0; i<=m-1; i++) r[i].key=random(100); biinsertsort(r,m); for( i=0; i<=m-1; i++) printf(“%d\\t”,r[i].key); printf(“\\n”); for( i=0; i<=m-1; i++) r[i].key=random(100); shellsort(r,m); for( i=0; i<=m-1; i++) printf(“%d\\t”,r[i].key); printf(“\\n”); } 2. 交换排序在顺序存储结构上的实现。其中函数bubblesort的功能是实现冒泡排序，函数betterbubblesort的功能是实现在冒泡排序的基础上提前结束排序，函数quickpass的功能是实现一趟快速排序，函数quicksort的功能是实现快速排序。 #include \#include “stdlib.h” typedef int datatype; #define m 10 struct record {int key;datatype others;}; void bubblesort(struct record r[ ],int n) { int i,j; struct record temp; for (i=0; i<=n-2; i++) for (j=0;j<=n-i-2;j++) if(r[j].key>r[j+1].key) {temp=r[j];r[j]=r[j+1];r[j+1]=temp;} } void betterbubblesort(struct record r[ ],int n) { int i,j,flag; struct record temp; for (i=0; i<=n-2; i++) { for (flag=0,j=0;j<=n-i-2;j++) if(r[j].key>r[j+1].key) {temp=r[j];r[j]=r[j+1];r[j+1]=temp; flag=1;} if (flag==0) break; } } void quickpass(struct record r[], int s, int t, int &i) { int j=t; struct record x=r[s]; i=s; while(i while (i - 19 - void quicksort(struct record r[ ], int s, int t) { int k; if (s main( ) { struct record r[m]; int i; for( i=0; i<=m-1; i++) r[i].key=random(100); bubblesort(r,m); for( i=0; i<=m-1; i++) printf(“%d\\t”,r[i].key); printf(“\\n”); for( i=0; i<=m-1; i++) r[i].key=random(100); betterbubblesort(r,0,m-1); for( i=0; i<=m-1; i++) printf(“%d\\t”,r[i].key); printf(“\\n”); for( i=0; i<=m-1; i++) r[i].key=random(100); quicksort(r,m); for( i=0; i<=m-1; i++) printf(“%d\\t”,r[i].key); printf(“\\n”); } 3. 选择排序在顺序存储结构上的实现。其中函数simpleselectsort的功能是实现简单选择排序，函数createheap的功能是实现“筛选”建堆，函数heapsort的功能是实现堆排序。 #include \#include “stdlib.h” typedef int datatype; #define m 10 struct record {int key;datatype others;}; void simpleselectsort(struct record r[],int n) { int i,j,k; struct record temp; for(i=0;i<=n-2;i++) { for(k=i,j=i+1;j<=n-1;j++) if (r[j].key } void createheap(struct record r[ ],int k,int n) { int i=k,j=2*i+1; struct record temp=r[i]; while (j<=n-1) { if (j r[i]=temp; } void heapsort(struct record r[ ],int n) { - 20 -