#include?
#include?“pro.h“
using?namespace?std;

/*
**建立一個(gè)頂點(diǎn)的存儲(chǔ)數(shù)組。數(shù)組類型就是頂點(diǎn)的類型，
**n是頂點(diǎn)的個(gè)數(shù)，返回建立好的數(shù)組地址。
*/
elementtype*?HeadArray1（int?n）????????//用完后要free。
{
????int?i;
????elementtype*?q=（elementtype*）malloc（n*sizeof（elementtype））;
????cout<<“輸入各個(gè)結(jié)點(diǎn)\n“;
????for?（i=0;?i????{
????????cin>>q[i];
????}
????return?q;
}

/*
**建立一個(gè)鄰居矩陣。參數(shù)是：n為頂點(diǎn)個(gè)數(shù)，m為邊的個(gè)數(shù)
**q是定點(diǎn)的存儲(chǔ)數(shù)組，即是上個(gè)函數(shù)的建立結(jié)果
*/
int*?build_juzheng（int?n?int?m?elementtype*?q）???//注意要free
{
????int*?p=（int*）malloc（n*n*sizeof（int））;
????int?ijflag?k?c;
????elementtype?x?y;

????for?（i=0;?i<=n;?i++）
????????for?（j=0;?j<=n;?j++）
????????????p[i*n+j]=MAX;

????cout<<“輸入各個(gè)邊及其權(quán)值:\n“;
????for?（k=0;?k????{
????????cin>>x>>y>>c;
????????flag=0;
????????for?（i=1;?i????????for?（j=1;?j????????if?（i>=n?||?j>=n）flag=1;
????????if?（!flag）
????????{
????????????p[i*n+j]=c;
????????????p[j*n+i]=c;
????????}
????????else
????????{
????????????cout<<“不存在該邊，重輸：\n“;
????????????k--;
????????}
????}
????return?p;
}

/*
**建立鄰接表的頂點(diǎn)數(shù)組，輸入時(shí)頂點(diǎn)個(gè)數(shù)n和頂點(diǎn)數(shù)組head1
**返回建立的鄰接表的頂點(diǎn)的結(jié)構(gòu)數(shù)組。
*/
cell*?HeadArray2（int?n?elementtype*?head1）????//?注意要free
{
????cell*?head=（cell*）malloc（n*sizeof（cell））;
????int?i;
????for?（i=0;?i????{
????????head[i].data=head1[i];
????????head[i].next=NULL;
????}
????return?head;
}

/*
**建立鄰接表。參數(shù)是頂點(diǎn)個(gè)數(shù)n，邊的個(gè)數(shù)m，頂點(diǎn)的結(jié)構(gòu)數(shù)組head。
**即上個(gè)函數(shù)建立的數(shù)組
*/
void?build_biao（int?nint?m?cell*?head）?//n為頂點(diǎn)的個(gè)數(shù)m為邊的個(gè)數(shù)，head為頂點(diǎn)結(jié)點(diǎn)數(shù)組首地址
{
????int?iflag?j?k?c;
????elementtype?x?y;
????edgecell*?p;
????cout<<“輸入邊及其權(quán)值：\n“;
????for?（j=0;?j????{
????????cin>>x>>y>>c;
????????flag=0;
????????for?（i=0;?i????????for?（k=0;?k????????if?（i>=n?||?k>=n）flag=1;
????????if?（!flag）
????????{
????????????p=new?edgecell;
????????????p->cost=c;
????????????p->num=k;
????????????p->next=head[i].next;
????????????head[i].next=p;

????????????p=new?edgecell;
????????????p->cost=c;
????????????p->num=i;
????????????p->next=head[k].next;
????????????head[k].next=p;
????????}
????????else
????????{
????????????cout<<“不存在該邊，重輸：\n“;
????????????j--;
????????}
????}
}

/*
**為了實(shí)現(xiàn)一種搜索算法對(duì)兩個(gè)存儲(chǔ)方式都好用，自己寫了一個(gè)從
**鄰接矩陣到鄰接表的轉(zhuǎn)換函數(shù)。自己只寫了鄰接表的訪問我建立最
**小生成樹。所以需要轉(zhuǎn)換?。參數(shù)是head1頂點(diǎn)的數(shù)組，head2頂點(diǎn)的
**存儲(chǔ)矩陣，n是頂點(diǎn)的個(gè)數(shù)
*/
cell*?juzhengTObiao（elementtype*?head1?int*?head2?int?n）//head1是存儲(chǔ)頂點(diǎn)的字符數(shù)組，head2是鄰接矩陣的首地址，n是頂點(diǎn)個(gè)數(shù)
{
????cell*?head=HeadArray2（n?head1）;
????edgecell*?p;
????int?i?j;

????for?（i=0;?i????{
????????for?（j=0;?j????????{
????????????if?（head2[i*n+j]）
????????????{
????????????????p=new?edgecell;
????????????????p->num=j;
????????????????p->next=head[i].next;
????????????????head[i].next=p;
????????????}
????????}
????}
????return?head;
}

?屬性????????????大小?????日期????時(shí)間???名稱
-----------?---------??----------?-----??----

?????文件???????3304??2009-05-27?07:06??shengchengshu\G_func.cpp

?????文件???????1328??2009-05-26?20:40??shengchengshu\pro.h

?????文件???????1180??2009-05-25?21:27??shengchengshu\shengchengshu.cbp

?????文件????????904??2009-05-27?06:46??shengchengshu\main.cpp

?????文件????????106??2009-05-26?10:05??shengchengshu\1.txt

?????文件????????760??2009-06-02?21:18??shengchengshu\shengchengshu.layout

?????文件?????????65??2009-05-26?10:15??shengchengshu\2.txt

?????文件???????1788??2009-05-27?07:06??shengchengshu\G_view.cpp

?????文件?????118934??2009-05-27?06:46??shengchengshu\obj\Debug\main.o

?????文件?????120980??2009-05-27?07:06??shengchengshu\obj\Debug\G_func.o

?????文件?????119322??2009-05-27?07:06??shengchengshu\obj\Debug\G_view.o

?????文件?????118000??2009-05-27?07:06??shengchengshu\obj\Debug\queue_func.o

?????文件?????120529??2009-05-27?07:06??shengchengshu\obj\Debug\G_build.o

?????文件???????3218??2009-05-27?07:06??shengchengshu\G_build.cpp

?????文件?????602312??2009-05-27?07:06??shengchengshu\shengchengshu.exe

?????文件??????77312??2009-05-28?14:36??shengchengshu\最小生成樹的構(gòu)造算法.doc

?????文件????????528??2009-05-27?07:06??shengchengshu\shengchengshu.depend

?????文件????????926??2009-05-27?07:06??shengchengshu\queue_func.cpp

?????目錄??????????0??2009-05-25?19:02??shengchengshu\obj\Debug

?????目錄??????????0??2009-05-25?19:02??shengchengshu\obj

?????目錄??????????0??2009-05-25?19:00??shengchengshu

-----------?---------??----------?-----??----

??????????????1291496????????????????????21