數(shù)據(jù)結(jié)構(gòu)+實(shí)驗報告+線性表及其應(yīng)用(多項式相加、相乘)等

1、實(shí)驗工程列表序號實(shí)驗工程名稱成績指導(dǎo)教師1線性表及其應(yīng)用(多項式相加、相乘)2哈弗曼樹及哈弗曼編碼譯碼的實(shí)現(xiàn)3Dijkstra最短路徑 或Prim最小生成樹4快速、堆、歸并排序算法的設(shè)計5構(gòu)造平衡二叉排序樹6789101112實(shí)驗一 線性表及其應(yīng)用一、 實(shí)驗?zāi)康暮鸵?、掌握線性表的插入、刪除、查找等根本操作設(shè)計與實(shí)現(xiàn)2、學(xué)習(xí)利用線性表提供的接口去求解實(shí)際問題3、熟悉線性表的的存儲方法二、 實(shí)驗內(nèi)容和原理1、實(shí)驗內(nèi)容：設(shè)計一個一元多項式的簡單計算器，其根本功能有輸入并建立多項式；輸出多項式；多項式相加?？衫脝捂湵砘騿窝h(huán)鏈表實(shí)現(xiàn)之。2、實(shí)驗原理：以線性表來描述一元多項式，存儲結(jié)構(gòu)采用單鏈表，

2、每個結(jié)點(diǎn)存儲的多項式中某一項的系數(shù)和指數(shù)，建立單鏈表時指數(shù)高的結(jié)點(diǎn)列于指數(shù)低的 結(jié)點(diǎn)之后，即線性表的元素按指數(shù)遞增有序排列。三、 實(shí)驗環(huán)境Visual C+ 6.0 及PC機(jī)四、 算法描述及實(shí)驗步驟思想算法：以線性表來描述一元多項式，存儲結(jié)構(gòu)采用單鏈表，每個結(jié)點(diǎn)存儲的多項式中某一項的系數(shù)和指數(shù)，建立單鏈表時指數(shù)高的結(jié)點(diǎn)列于指數(shù)低的結(jié)點(diǎn)之后，即線性表的元素按指數(shù)遞增有序排列。例如構(gòu)造兩個多項式ha: 5X3+4X2+3X+2 hb: X2+X+1多項式加法：定義指針p,q分別指向ha,hbi.p->exp=q->exp ,r->coef=p->coef+q->coe

3、f,pa,pb下移;ii.p->exp<q->exp ,r->coef=q->coef;r->exp=q->exp;,q下移iii.pa->exp>pb->exp, r->exp=p->exp;r->coef=p->coef;,p下移iv.p!=NULL,pb=NULL.相當(dāng)于iii.V.q=NULL,pb!=NULL.相當(dāng)于ii.其流程圖如下： 多項式乘法：定義指針fp,gp分別指向f,g1.將兩多項式最大指數(shù)相加并賦于maxp，并置g3. (fp!=NULL)&&(gp!=NULL), p=

4、fp->exp+gp->exp 1.p>maxp, fp=fp->next; 2. p<maxp, gp=gp->next; 3.p=maxp, x+=fp->coef*gp->coef; fp=fp->next;gp=gp->next;五、 調(diào)試過程將主函數(shù)中的多項式相乘的函數(shù)hd=polymult(ha,hb);/*ha和hb相乘*/的polymult(ha,hb)改為polymulti(ha,hb)即可。六、 實(shí)驗結(jié)果1.分別輸入兩個多項式: 5X3+4X2+3X+2 和X2+X+1,然后輸出結(jié)果如下:2.分別輸入兩個多項式：6

5、X4+4X2+2和5X+6，然后輸出結(jié)果如下：七、 總結(jié)此次上機(jī)實(shí)驗應(yīng)用了線性表實(shí)現(xiàn)了一次實(shí)際操作，完成了一個一元多項式的簡單計算器，不僅對此次編譯程序的算法思想有了新的認(rèn)識，還讓我深刻的體會到了線性表的重要性以及其應(yīng)用的方便，并且對指針加深了映象，應(yīng)用了書本中的算法思想，對我以后的編譯以及完成新的程序有很大的幫助。附錄： 1.建立多項式列表代碼如下：mulpoly *creatpoly()/*建立多項式列表*/ mulpoly *head,*r,*s;/*設(shè)中間變量*/ int m,n; head=(mulpoly *)malloc(sizeof(mulpoly);/*頭結(jié)點(diǎn)申請空間*/ p

6、rintf("ninput coef and exp:n"); scanf("%d%d",&n,&m);/*輸入多項式系數(shù)和指數(shù)*/ r=head;/*尾指針指向頭指針*/ while(n!=0)/*將輸入的多項式存放在S中*/ s=(mulpoly*)malloc(sizeof(mulpoly); s->coef=n; s->exp=m; r->next=s; r=s; /*printf("input coef and exp:n");*/ scanf("%d%d",&n

7、,&m);/*再次輸入多項式系數(shù)和指數(shù)*/ r->next=NULL;/*將尾指針置空*/ head=head->next;/*將head啞結(jié)點(diǎn)向前跑一個結(jié)點(diǎn)，使其不為空*/ return (head);/*返回多項式*/ 2.兩個多項式相加代碼如下：mulpoly *polyadd(mulpoly *ha,mulpoly *hb)/*兩個多項式相加*/ mulpoly *hc,*p,*q,*s,*r;/*聲明結(jié)構(gòu)體型*/ int x; p=ha; q=hb; hc=(mulpoly *)malloc(sizeof(mulpoly);/*申請結(jié)點(diǎn)空間*/ s=hc; whi

8、le(p!=NULL)&&(q!=NULL)/*兩多項式不為空*/ if(p->exp=q->exp)/*指數(shù)相等*/ x=p->coef+q->coef;/*系數(shù)相加*/ if(x!=0)/*系數(shù)不為零*/ r=(mulpoly*)malloc(sizeof(mulpoly);/*結(jié)果放r中存放*/ r->exp=q->exp; r->coef=x; s->next=r; s=r; p=p->next;/*多項式前進(jìn)一項*/ q=q->next;/*多項式前進(jìn)一項*/ else if(p->exp<q-&

9、gt;exp)/*比擬指數(shù)大小*/ r=(mulpoly *)malloc(sizeof(mulpoly); r->coef=q->coef; r->exp=q->exp; s->next=r; s=r; q=q->next; else r=(mulpoly *)malloc(sizeof(mulpoly); r->exp=p->exp; r->coef=p->coef; s->next=r; s=r; p=p->next; while(p!=NULL)/*當(dāng)多項式p中不為空時照抄*/ r=(mulpoly *)mallo

10、c(sizeof(mulpoly); r->exp=p->exp; r->coef=p->coef; s->next=r; s=r; p=p->next; while(q!=NULL)/*當(dāng)多項式q中不為空時照抄*/ r=(mulpoly *)malloc(sizeof(mulpoly); r->exp=q->exp; r->coef=q->coef; s->next=r; s=r; q=q->next;/*將最終尾指針置空*/ s->next=NULL; r=hc; hc=hc->next; free(r);

11、/*釋放r*/ return(hc);/*返回結(jié)果*/ 3.兩個多項式相乘代碼如下：mulpoly*polymulti(mulpoly *f,mulpoly *g) /*兩個多項式相乘*/ mulpoly *fp,*gp,*hp,*q,*h; int maxp,p,r,x; mulpoly *reverse(mulpoly *q);/*函數(shù)聲明*/ maxp=f->exp+g->exp;/*將兩多項式最大指數(shù)相加并賦于maxp*/ h=(mulpoly *)malloc(sizeof(mulpoly); hp=h; g=reverse(g);/*逆置g*/ for(r=maxp;r

12、>=0;r-)/*循環(huán)求指數(shù)等于r時相乘的系數(shù)*/ x=0;/*設(shè)x初始值為0*/ fp=f; gp=g; while(fp!=NULL)&&(gp!=NULL)/*循環(huán)求相乘之后指數(shù)為r時的系數(shù)*/ p=fp->exp+gp->exp;/*f的指數(shù)加上g逆置后的指數(shù)并給p*/ if(p>r)/*比擬p，r*/ fp=fp->next;/*p大，fp到下一個結(jié)點(diǎn)，以確保p等于r*/ else if(p<r)gp=gp->next;/*p小，gp到下一個結(jié)點(diǎn)，以確保p等于r*/ else/*p等于r*/ x+=fp->coef*gp

13、->coef;/*將相乘之后指數(shù)為r時的系數(shù)給x*/fp=fp->next;gp=gp->next; if(abs(x)>1e-6)/*條件限制，使得所求多項式系數(shù)絕對值不能太小*/ q=(mulpoly *)malloc(sizeof(mulpoly); q->exp=r; q->coef=x; q->next=NULL; hp->next=q; hp=q; /*將所求結(jié)果給hp，h*/ hp=h; h=h->next;/*將h的啞結(jié)點(diǎn)前進(jìn)，使不為空*/ free(hp);/*釋放hp*/ return h;/*返回結(jié)果*/ 4.定義鏈表

14、逆置函數(shù)mulpoly *reverse(mulpoly *q)/*定義鏈表逆置函數(shù)*/ mulpoly *p1,*p2; if(q!=NULL)/*確保所要逆置多項式不為空*/ p1=q->next;/*使p1指向下一個結(jié)點(diǎn)*/ q->next=NULL;/*將q->next為空*/ while(p1!=NULL)/*循環(huán)使相鄰兩個結(jié)點(diǎn)逆置，直到最后一個逆置為頭結(jié)點(diǎn)*/ p2=p1->next; p1->next=q; q=p1; p1=p2; return q;/*返回逆置結(jié)果*/ 5.輸出多項式代碼如下：void polyout(mulpoly *head)

15、 /*輸出多項式*/ mulpoly *q,*p; /*p=head->next;*/ p=head; while(p!=NULL)/*循環(huán)輸出多項式的系數(shù)和指數(shù)*/ printf("%dx%d ",p->coef,p->exp); p=p->next; printf("n");實(shí)驗二 哈弗曼樹及哈弗曼編碼譯碼的實(shí)現(xiàn)一、 實(shí)驗?zāi)康暮鸵?、掌握樹的有關(guān)圖相關(guān)操作算法;2、熟悉樹的根本存儲方法;3、學(xué)習(xí)利用樹求解實(shí)際問題。二、 實(shí)驗內(nèi)容和原理1、實(shí)驗內(nèi)容：1構(gòu)造哈弗曼樹；2對單個結(jié)點(diǎn)編碼；3輸出樹；4編碼；5譯碼。2、實(shí)驗原理：通過

16、樹的有關(guān)圖的相關(guān)操作算法，以及樹的根本存儲方法，利用樹來構(gòu)造哈夫曼樹及哈夫曼編碼，輸出哈夫曼樹及哈夫曼編碼，完成編碼與譯碼的算法。三、 實(shí)驗環(huán)境Visual C+ 6.0 及PC機(jī)四、 算法描述及實(shí)驗步驟思想算法：一棵有n個葉子結(jié)點(diǎn)的哈夫曼樹有2n-1個結(jié)點(diǎn)，所以可用大小為2n-1個元素的數(shù)組構(gòu)造靜態(tài)鏈表來存儲哈夫曼樹，一個數(shù)組元素中存放一個結(jié)點(diǎn)。結(jié)點(diǎn)的結(jié)構(gòu)可以這樣來考慮，由于每個葉子結(jié)點(diǎn)都有一個權(quán)重，構(gòu)造哈夫曼樹的過程中每個分枝結(jié)點(diǎn)的權(quán)重等于兩個孩子結(jié)點(diǎn)權(quán)重的和，所以應(yīng)該有一個權(quán)重域和指向左右孩子的兩個指針域；另外在建成哈夫曼樹之后，為了求得每個葉子結(jié)點(diǎn)的哈夫曼編碼，需要走一條從葉子結(jié)點(diǎn)到根

17、結(jié)點(diǎn)的路徑，而譯碼的過程是從根結(jié)點(diǎn)出發(fā)到葉子結(jié)點(diǎn)的不斷匹配的過程，所以既需要知道孩子結(jié)點(diǎn)的信息，也需要知道雙親結(jié)點(diǎn)的信息，應(yīng)該再有一個指向雙親結(jié)點(diǎn)的指針域。由此可知，每個結(jié)點(diǎn)至少應(yīng)該有一個權(quán)重域weight和3個指針域parent,lchild和rchild，也是就是說，要用靜態(tài)三叉鏈表來表示哈夫曼樹。由于在實(shí)際構(gòu)造哈夫曼樹時，是由葉子結(jié)點(diǎn)的權(quán)重逐級構(gòu)造最后生成樹根，且在構(gòu)造過程中公與葉子結(jié)點(diǎn)的權(quán)重有關(guān)而與葉子結(jié)點(diǎn)的數(shù)據(jù)域外無關(guān)，所以構(gòu)造算法的實(shí)現(xiàn)中可以不考慮葉子結(jié)點(diǎn)的數(shù)據(jù)域，并且在靜態(tài)三叉鏈表中從葉子結(jié)點(diǎn)開始存放，然后不斷地反兩棵權(quán)重最小的子樹合并成為一棵權(quán)值為其和的較大的子樹，逐步生成各內(nèi)

18、部結(jié)點(diǎn)直到樹根。在建立哈夫曼樹的算法描述中，有效地利用了每個結(jié)點(diǎn)的雙親域parent的值是否為了-1來區(qū)分該結(jié)點(diǎn)是否是哈夫曼森林中一棵樹的根結(jié)點(diǎn)，每次是在根結(jié)點(diǎn)中找出兩個權(quán)重值weight最小的樹作為左右子樹構(gòu)造一棵更大的樹。求哈夫曼編碼的方法是，在已建好的哈夫曼樹中從每個葉子結(jié)點(diǎn)開始沿雙親鏈域回退到根結(jié)點(diǎn)，每回退一步走過哈夫曼樹的一個分枝得到一位哈夫曼編碼值，由于每個葉子結(jié)點(diǎn)的哈夫曼編碼是從根結(jié)點(diǎn)到相應(yīng)葉子結(jié)點(diǎn)的路徑上各代碼所組成的0，1序列，所以先得到的代碼為所求編碼的低位碼而后得到的為高位碼。對于每個葉子結(jié)點(diǎn)的哈夫曼編碼可以考慮用一個一維數(shù)組bit從后向前依次保存所求得的各位編碼值，并用

19、start記住編碼在數(shù)組bit中的開始位置。如下面例子，有4個數(shù)2，4，5，8。將其構(gòu)造成哈夫曼樹。 算法設(shè)計分析select(int t,int *s1,int *s2)函數(shù)用來實(shí)現(xiàn)選取最小和次最小的權(quán)重的下標(biāo)，其流程圖如下：create_ht_hc()函數(shù)用來構(gòu)造樹和碼，其流程圖如下：showtree(int root,int tab)為用凹入法顯示樹，其流程圖如下：showcode(int n)用來顯示01代碼，其流程圖如下：code2char(char t,char s)函數(shù)用來譯碼。char2code(char s,char t)函數(shù)用來編碼，其流程圖如下：五、 調(diào)試過程將程序的代碼

20、輸入，再進(jìn)行編譯，發(fā)現(xiàn)以下錯誤。1.修改方法：在代碼開頭參加頭文件#include<string.h>即可正常編譯和組建，最后再進(jìn)行運(yùn)行。2.問題：當(dāng)輸出各個字符的編碼后，程序沒有提醒“the chars are:.而是只能自己輸入一串字符后，才進(jìn)行提示。下一步的譯碼也是如此。六、 實(shí)驗結(jié)果輸入5個葉子結(jié)點(diǎn)a,s,d,f,g。其權(quán)重分別為7，13，16，4，10。得出結(jié)果如下：七、 總結(jié)本次實(shí)驗讓我更加了解了哈夫曼樹的構(gòu)造和生成方法，以及如何用順序存儲結(jié)構(gòu)來存儲哈夫曼樹及構(gòu)樹過程的信息，如何進(jìn)行編碼、譯碼。也感知到模塊程序設(shè)計在大程序設(shè)計使用中的普遍性，該實(shí)驗是最好的證明，通過模塊

21、程序設(shè)計，能夠使得程序可度可寫性明顯加強(qiáng)。通過本次實(shí)驗，使我初步掌握了二叉樹的結(jié)構(gòu)特性以及各種存儲的結(jié)構(gòu)的特點(diǎn)及適用范圍，掌握了哈夫曼樹的定義和思想，以及哈夫曼編碼的代碼實(shí)現(xiàn)，初步掌握了用凹入法顯示樹。不過程序仍有樹的顯示局部不夠完善的缺點(diǎn)，在今后的學(xué)習(xí)中會注意改變。附錄： 選擇最小和次最小的權(quán)重函數(shù)如下：void select(int t,int *s1,int *s2) /*在1t之間選取w最小的下標(biāo)s1，次最小的下標(biāo)為s2*/ int i,w1,w2; /*最小的權(quán)重為w1，次最小的權(quán)重為w2*/ w1=w2=32767; /*初始化為無窮大*/ for(i=1;i<=t;i+)

22、if(hti.parent=0) /*選取最小的和次最小的*/ if(hti.w<w1) /*如果出現(xiàn)一個比w1還小的權(quán)，那么把原先的w1傳給w2，把新的權(quán)重賦給w1*/ w2=w1;*s2=*s1;w1=hti.w;*s1=i; else if(hti.w<w2) /*如果出現(xiàn)一個比w2還小的權(quán)，那么把新的權(quán)重賦給w2，并記住其下標(biāo)*/ w2=hti.w;*s2=i;構(gòu)造哈夫曼樹的代碼如下：void create_ht_hc() /*構(gòu)造樹和碼*/ int i,s1,s2,child,parent,w; char ch; cout<<"Please ente

23、r n: " /*輸入葉子數(shù)*/ cin>>n; m=2*n-1; /*總結(jié)點(diǎn)數(shù)*/ for(i=1;i<=n;i+) /*輸入數(shù)據(jù)*/ cout<<"Please enter string: " fflush(stdin); /*清空鍵盤緩沖區(qū)*/ cin>>ch>>w; hti.w=w; /*把初始的數(shù)據(jù)送入存儲空間*/ hci.ch=ch; for(i=n+1;i<=m;i+) /*建樹*/ select(i-1,&s1,&s2); /*選取最小的和次最小的權(quán)重*/ hts1.par

24、ent=hts2.parent=i; /*把最小的和次最小的權(quán)連成樹*/ hti.lch=s1; /*左孩子為最小的，右孩子為次最小的*/ hti.rch=s2; hti.w=hts1.w+hts2.w; /*parent的權(quán)為孩子之和*/ for(i=1;i<=n;i+) /*建碼*/ child=i; hci.start=0; /*初始化開始位置*/ while(child!=m) /*對葉子結(jié)點(diǎn)逐一求哈夫曼編碼*/ parent=htchild.parent; if(child=htparent.rch) /*左0右1*/hci.codehci.start=1; elsehci.c

25、odehci.start=0; hci.start+; child=parent; /*從下往上編*/用凹入法顯示樹的代碼如下：void showtree(int root,int tab) /*凹入法顯示樹，tab為凹入的字符數(shù)*/if(root) /*如果樹非空*/ int i; for(i=1;i<=tab;i+) /*輸出空格*/ cout<<" " cout<<htroot.w; if(htroot.lch=0) /*如果為葉子結(jié)點(diǎn)，那么輸出葉子結(jié)點(diǎn)*/cout<<(<<hcroot.ch<<);c

26、out<<endl; /cout<<htroot.w; /*輸出權(quán)值*/ showtree(htroot.lch,tab+3); showtree(htroot.rch,tab+3);顯示各字母的代碼：void showcode(int n) /*顯示01代碼，從start-1開始輸出*/ int i,j; for(i=1;i<=n;i+) cout<<hci.ch<<":" for(j=hci.start-1;j>=0;j-) cout<<hci.codej; cout<<endl;對輸入

27、的字符進(jìn)行編碼：void char2code(char s,char t) /*編碼，假設(shè)s="abcd",那么t="000110101"*/ int i,j,k,x=0; for(i=0;i<strlen(s);i+)/*掃描s*/ for(j=1;j<=n;j+) /*開始編碼，把對應(yīng)的字符變成相應(yīng)的代碼*/ if(si=hcj.ch) for(k=hcj.start-1;k>=0;k-) tx+=hcj.codek+48; /*把整型轉(zhuǎn)換為字符型*/ tx='0' /*字符串結(jié)束標(biāo)志*/ 對輸入的數(shù)碼進(jìn)行譯碼：vo

28、id code2char(char t,char s) /*譯碼，假設(shè)t="000110101"，那么s="abcd"*/*用指針掃描t，從根m開始向下遇0向左，遇1向右，直到找到葉子結(jié)點(diǎn)，并輸出再返回根，從頭開始循環(huán)*/ int i=0,j=0,parent=m;/child; while(si) if(si='1') parent=htparent.rch; else parent=htparent.lch; if(htparent.lch=0) tj+=hcparent.ch; parent=m; i+; tj='0'

29、; /*字符串結(jié)束標(biāo)志*/ 實(shí)驗三 Dijkstra最短路徑 或Prim最小生成樹二選一一、 實(shí)驗?zāi)康暮鸵?、 掌握圖的有關(guān)圖相關(guān)操作算法。2、 熟悉圖的根本存儲方法。3、 了解掌握圖的根本術(shù)語。二、 實(shí)驗內(nèi)容和原理實(shí)驗內(nèi)容：通過輸入起點(diǎn)、終點(diǎn)和權(quán)重構(gòu)造一個圖；通過輸入，將一個節(jié)點(diǎn)作為起點(diǎn)；找到從起點(diǎn)到各個節(jié)點(diǎn)的最短路徑；輸出圖與及到各個節(jié)點(diǎn)的最短短徑；三、 實(shí)驗環(huán)境Visual C+ 6.0 及PC機(jī)四、 算法描述及實(shí)驗步驟Prim算法是人連通網(wǎng)中的某一個頂點(diǎn)開始，以此作為生成樹的初始狀態(tài)，然后不斷地網(wǎng)中的其他頂點(diǎn)添加到生成樹上，直到最后一個頂點(diǎn)添加到生成樹上時得到最小生成樹。1從網(wǎng)中任一

30、頂點(diǎn)開始，把該頂點(diǎn)包含生成樹中，此時樹只有一個頂點(diǎn)。2找出一個端點(diǎn)在生成樹中另一個端點(diǎn)在生成樹外的所有邊，并把權(quán)值最小的邊連同它所關(guān)聯(lián)的另一個頂點(diǎn)添加到生成樹中；當(dāng)有兩條及以上具有相同最小權(quán)值的邊可供選擇時，選擇其中任意一條都可以。3反復(fù)執(zhí)行2，直到所有頂點(diǎn)都包含在生成樹中時止。算法中由函數(shù)prim定義最小生成樹。由函數(shù)creat_graph建立無向連通網(wǎng)。算法過程如下列圖：建立無向連通網(wǎng)的流程圖如下： 定義最小生成樹的代碼如下：五、 調(diào)試過程將程序的代碼輸入，再進(jìn)行編譯，沒有發(fā)現(xiàn)錯誤。六、 實(shí)驗結(jié)果實(shí)驗結(jié)果如下七、 總結(jié)1). 通過這次實(shí)驗，使我掌握了用prim算法構(gòu)造最小生成樹的思想。掌握

31、了鄰接矩陣的構(gòu)造思想及其應(yīng)用。3).掌握圖與網(wǎng)的根本概念和根本存儲方法。4). 掌握有向及無向連通圖的概念及其應(yīng)用。5). 對編程有了更深的理解與掌握。附錄： void creat_graph(graph *p) /*建立無向連通網(wǎng)*/int i,j,n ; int v1,v2,w;/*定義兩端點(diǎn)及其權(quán)值為整型*/ printf("vertex number of the graph:"); /*輸入無向網(wǎng)的端點(diǎn)數(shù)*/ scanf("%d",&n); p->vnum=n; for(i=1;i<=n;i+) /*初始化結(jié)構(gòu)體中的元素*/

32、 for(j=1;j<=n;j+) if(i=j) /*對角線上的元素的權(quán)值為0*/ p->arcsij=0; else /*非對角線上的元素的權(quán)值為MAX即99*/ p->arcsij=MAX; do /*執(zhí)行循環(huán)語句*/ printf("edge(vertex1,vertex2,weight):"); /*輸入兩個端點(diǎn)及其權(quán)值*/ scanf("%d,%d,%d",&v1,&v2,&w); if(v1>=1&&v1<=n&&v2>=1&&v2&

33、lt;=n) p->arcsv1v2=w; p->arcsv2v1=w; while(!(v1=8|v2=8); /*當(dāng)v1，v2其中一個為8時循環(huán)終止*/ int prim(graph G,int v, int tree8) /*定義最小生成樹*/int i,j,k,p,min,c; /*定義局部變量*/ int lowcostm,closestm; for(i=1;i<=G.vnum;i+) closesti=v; /*填邊在生成樹一端的頂點(diǎn)序號*/ lowcosti=G.arcsvi;/*填邊的權(quán)值*/ c=1; p=1;/*從v1開始構(gòu)造最小生成樹*/ for(i=1

34、;i<G.vnum;i+) /*循環(huán)n-1次，選n-1條邊于生成樹中*/ min=MAX;/*初定min值為上限值99*/ for(j=1;j<=G.vnum;j+) /*選最小權(quán)值及對應(yīng)頂點(diǎn)*/ if(lowcostj!=0&&lowcostj<min) min=lowcostj; /*最小權(quán)值記在min中*/ k=j; /*把與邊關(guān)聯(lián)的生成樹外的頂點(diǎn)序號記在k中*/ treep1=closestk; /*將所得值存入出發(fā)端點(diǎn)*/ treep2=k; /*將k存入另一個端點(diǎn)*/ treep3=min; /*存儲兩個端點(diǎn)的最小權(quán)值*/ p+; c+=min;

35、lowcostk=0;/*將頂點(diǎn)k參加生成樹中*/ for(j=1;j<=G.vnum;j+) if(G.arcskj!=0&&G.arcskj<lowcostj) lowcostj=G.arcskj; /*修改權(quán)值域*/ closestj=k; return c; 實(shí)驗四 快速、堆、歸并排序算法的設(shè)計(三選一)一、 實(shí)驗?zāi)康暮鸵?、 掌握常用的排序方法和各種排序方法的特點(diǎn)。2、 熟悉排序的根本概念。二、 實(shí)驗內(nèi)容和原理1、 輸入一個數(shù)組長度隨機(jī)的數(shù)組。2、 對數(shù)組中的各個元素進(jìn)行排序。三、 實(shí)驗環(huán)境及PC機(jī)四、 算法描述及實(shí)驗步驟思想算法：快速排序的算法思想是：

36、有一組待排序的數(shù)組如76，31，76，79，25，29，12，78，把每組第一個元素的排序碼為基準(zhǔn)進(jìn)行分組，并采用從兩端往中間收縮的方式為該基準(zhǔn)元素找插入位置。以第一次分組為例，首先，將元素R1存人變量R0中，引人變量i(初始值為1)和j(初始值為n)，然后，比擬R0和Rj的排序碼，假設(shè)Rj的排序碼較大，那么j減l，繼續(xù)比擬R0和Rj；假設(shè)R0的排序碼較小，那么將Rj存人Ri中，在i加l后，轉(zhuǎn)而比擬R0和Ri的排序碼;假設(shè)Ri的排序碼較小，那么i加1，繼續(xù)比擬R0和Ri；假設(shè)Ri的排序碼較大，那么將Ri存人Rj中，在j減l后，轉(zhuǎn)而比擬R0和Rj。如此交替進(jìn)行下去，直至i=j時，將R0存人Rj中

37、，一次分組過程便告結(jié)束。圖8，7所示的是對8個元素進(jìn)行一次分組的過程，其中花括號指出待分組的區(qū)間。R0 R1 R2 R3 R4 R5 R6 R7 R876， 31， 76， 79， 25， 29， 12， 7876 口， 31， 76， 79， 25， 29， 12， 78 i j口， 31， 76， 79， 25， 29， 12， 78 i j12， 31， 76， 79， 25， 29， 口， 78 i j12， 31， 76， 79， 25， 29， 口， 78 i j12， 31， 76， 79， 25， 29， 口， 78 i j12， 31， 76， 口， 25， 29， 79，

38、78 i j12， 31， 76， 口， 25， 29， 79， 78 i j12， 31， 76， 29， 25， 口， 79， 78 i j12， 31， 76， 29， 25， 口， 79， 78 ij4.1 算法設(shè)計分析算法int divideareasort(recordtype R,int s,int t)用于實(shí)現(xiàn)一次分組:它以Ri為標(biāo)準(zhǔn)，將RiRj分為兩組，使得RiRk-1的排序碼都不大于Rk的排序碼，Rk+1Rk的排序碼都不小于Rk的排序碼，并返回k值。(代碼在附錄)對于待排序文件R利用一次分割敬意排序算法時，令s=1和t=n即可完成第一趟排序；由此得到的兩個更小的敬意R1,i

39、-1 和Ri+1,n，繼續(xù)利用算法divideareasort分割為更小的4個敬意；如此一直進(jìn)行下去，直到都分割為只有一個記錄時排序結(jié)束。調(diào)用divideareasort對R進(jìn)行快速排序的遞歸算法。(代碼在附錄)五、 調(diào)試過程將程序的代碼輸入，再進(jìn)行編譯，沒有發(fā)現(xiàn)錯誤。六、 實(shí)驗結(jié)果輸入一組數(shù)據(jù)如76，31，76，79，25，29，12，78，得出結(jié)果如下：七、 總結(jié)通過本次上機(jī)實(shí)驗我掌握了利用數(shù)組的順序存儲結(jié)構(gòu)的根本操作和快速排序算法設(shè)計的實(shí)現(xiàn)。以及快速排序和冒泡排序，直接插入排序以及其他各種排序的不同。也讓我看到了他們的優(yōu)點(diǎn)和缺點(diǎn)。在編程過程中，更加熟練了程序的編寫步驟及要領(lǐng)。附錄： 1d

40、ivideareasort的代碼如下：int divideareasort(recordtype R,int s,int t)/對待排序記錄區(qū)間Rs到Rt以為基準(zhǔn)進(jìn)行一次分割排序，并返回基準(zhǔn)記錄的最終位置int i,j;/定義指示器變量 recordtype temp;/定義暫存工作單元 i=s;j=t;/區(qū)間指示器變量初始化 temp=Rs;/確定分割基準(zhǔn) do while(Rj.key>=temp.key)&&(i<j) j-;/自后向前掃描找小于基準(zhǔn)關(guān)鍵字的記錄 if(i<j) Ri=Rj;/把Rj移入Ri中 i+;/令i指向i+1 while(Ri.k

41、ey<=temp.key)&&(i<j) i+;/撲克前向后掃描找大于基準(zhǔn)關(guān)鍵字的記錄 if(i<j) Rj=Ri;/把Ri移入Rj中 j-;/令j指向j-1 while(i<j);/ Ri=temp;/ return i;/返回基準(zhǔn)記錄的最終位置i 2遞歸的算法如下：void quicksort(recordtype R,int s,int t)/對排序文件Rs.t進(jìn)行快速排序int i;/定義局部變量 if(s<t) i=divideareasort(R,s,t);/分割區(qū)間并把基準(zhǔn)位置送i quicksort(R,s,i-1);/對基準(zhǔn)記錄前

42、的區(qū)間的快速排序 quicksort(R,i+1,t);/對基準(zhǔn)記錄前的區(qū)間的快速排序 實(shí)驗五 構(gòu)造平衡二叉排序樹一、 實(shí)驗?zāi)康暮鸵?、掌握樹型檢索的根本概念2、掌握平衡二叉樹的根本概念及原理二、 實(shí)驗內(nèi)容和原理1、實(shí)驗內(nèi)容：構(gòu)造平衡二叉排序樹，實(shí)現(xiàn)平衡二叉樹結(jié)果的輸入與輸出。2、實(shí)驗原理：構(gòu)造平衡二叉樹的根本思想是在構(gòu)造的過程中，每當(dāng)插入一個結(jié)點(diǎn)后都去檢查是否由于該結(jié)點(diǎn)的插入而破壞了AVL樹；假設(shè)出現(xiàn)絕對值超過1的平衡因子，那么需要在保持AVL樹特性的前提下通過先判斷類型后用相應(yīng)的旋轉(zhuǎn)方法調(diào)整使之到達(dá)新的平衡。3、實(shí)驗方法：由老師提供程序模板供學(xué)生參考，學(xué)生在模板的指導(dǎo)下改寫程序，在老師的

43、指導(dǎo)下編譯、調(diào)試、運(yùn)行。三、 實(shí)驗環(huán)境及PC機(jī)四、 算法描述及實(shí)驗步驟 1)對關(guān)鍵碼序列L從小到大進(jìn)行排序得到L ；2)選擇序列L中中間元素m作為AVL樹的根，在m左邊的元素作為AVL樹的左子樹元素，在m右邊的元素作為AVL樹的右子樹元素。3)按2的方法分別構(gòu)建AVL樹的左子樹和右子樹。構(gòu)建過程如下列圖所示。主要函數(shù)void lrflip()，用于進(jìn)行LR型平衡旋轉(zhuǎn)主要函數(shù)void rlflip()，用于進(jìn)行RL型平衡旋轉(zhuǎn)主要函數(shù)void avlt_insert(int key)，用于增加結(jié)點(diǎn)。五、 調(diào)試過程將程序的代碼輸入，再進(jìn)行編譯，沒有發(fā)現(xiàn)錯誤。六、 實(shí)驗結(jié)果輸入以下數(shù)字：5，6，15，

44、79，35，58，結(jié)果如下。七、 總結(jié)通過本次上機(jī)實(shí)驗讓我更了解了平衡二叉樹的定義和它的構(gòu)造。但對于平衡二叉樹的應(yīng)用，還存在的一些問題。經(jīng)過網(wǎng)上的搜索，發(fā)現(xiàn)對平衡二叉樹的構(gòu)造是一個比擬難的問題。很多人都覺得很難，現(xiàn)實(shí)中很難用到。當(dāng)然可能是我對平衡二叉樹還不是很理解。 附錄：void llflip() p=r; s->lch=p->rch; p->rch=s; s->pf=0; r->pf=0; changeroot();void lrflip() p=r->rch; r->rch=p->lch; p->lch=r; s->lch=p-&g