由普林姆算法 看数据结构定义的重要性
花了一上午的时间，和下午1小时的时间写了，普林姆算法，从中体会到了，数据结构定义的重要性:
上午的时候，老是想用两个一维数组来定义结点是否被访问过，结果，一会儿就弄糊涂了，但由于本人一向比较执着，因此，即使自己十分不在状态，仍然在撞到南墙之前，仍毫不气馁，继续发狂，直到自己的脑袋实在承受不了脑细胞成数量级的死亡。作罢，中午休息后，改变了一下数据结构，仅仅用了一个一维数组来表示是否被走过，很快就解决了。^~^,轻松一下，自己给自己赏一个香吻吧。
代码如下：（PS:baidu的文字编辑器该升级了，害我代码区需要在WORD里面编辑好才能粘过来）
//测试用例是：《数据结构(第二版)》P174页 #include <stdio.h> #include <stdlib.h> #include <string.h> #define INIFITY 0X7FFFFFFF #define SIZE 6
int flag_true[6];
typedef struct { int index; int adj_index; int value; }* PrimeT,Node;
int zhenlie[SIZE][SIZE] = {0,6,1,5,INIFITY,INIFITY,\ 6,0,5,INIFITY,3,INIFITY,\ 1,5,0,5,6,4,\ 5,INIFITY,5,0,INIFITY,2,\ INIFITY,3,6,INIFITY,0,6,\ INIFITY,INIFITY,4,2,6,0}; PrimeT table;
void Init() { memset(flag_true,0,sizeof(int)*SIZE); flag_true[0]=1; table=(PrimeT)malloc((SIZE-1)*sizeof(Node));//n个点需要n-1个路径,不要忘了，呵呵 }
//HASA函数 //----看是否存在没有被访问过的点，如果存在就返回true,否则返回false bool HasA(int *p) { int i=0; while(i<SIZE) { if(p[i]==0) return true; i++; } return false;
}
void Prim() { int count(0); while(HasA(flag_true)) { int Min=INIFITY; int Min_x=-1; int Min_index=-1; for(int i=0;i<SIZE;i++) { if(flag_true[i]==1) { for(int j=0;j<SIZE;j++) { if(flag_true[j]==0) { if(zhenlie[i][j]<Min) { Min=zhenlie[i][j]; Min_x=j; Min_index=i; }
} } } } flag_true[Min_x]=1; table[count].index=Min_index; table[count].adj_index=Min_x; table[count].value=Min; count++; } }
void main() { int sum(0); int i(0); Init(); Prim();
//格式化输出代码： printf("邻接表如下：\n"); for(printf("index\t"),i=0;i<SIZE-1;i++) {
printf("%d\t",table[i].index); } printf("\n"); for(i=0,printf("a_index\t");i<SIZE-1;i++) {
printf("%d\t",table[i].adj_index); } printf("\n"); for(i=0,printf("value\t");i<SIZE-1;i++) { sum+=table[i].value; printf("%d\t",table[i].value); } printf("\n"); printf("最小值：%d",sum); printf("\n");
}
|
评论
发表评论