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

1、實驗一線性表及其應(yīng)用實驗?zāi)康暮鸵?、掌握線性表的插入、刪除、查找等基本操作設(shè)計與實現(xiàn)2、學(xué)習(xí)利用線性表提供的接口去求解實際問題3、熟悉線性表的的存儲方法二、實驗內(nèi)容和原理1、實驗內(nèi)容：設(shè)計一個一元多項式的簡單計算器，其基本功能有 輸入并建立多項式；輸出多項式；多項式相加?？衫脝捂湵?或單循環(huán)鏈表實現(xiàn)之。2、實驗原理：以線性表來描述一元多項式，存儲結(jié)構(gòu)采用單鏈表， 每個結(jié)點存儲的多項式中某一項的系數(shù)和指數(shù)，建立單鏈表時指數(shù) 高的結(jié)點列于指數(shù)低的 結(jié)點之后，即線性表的元素按指數(shù)遞增有序 排列。三、實驗環(huán)境Visual C+ 6.0 及 PC機(jī)四、算法描述及實驗步驟思想算法：以線性表來描述一元多

2、項式，存儲結(jié)構(gòu)采用單鏈表，每個結(jié)點存儲的多項 式中某一項的系數(shù)和指數(shù)，建立單鏈表時指數(shù)高的結(jié)點列于指數(shù)低的結(jié)點之后， 即線性表的元素按指數(shù)遞增有序排列。例如構(gòu)造兩個多項式ha: 5X3+4X2+3X+2hb: X2+X+1多項式加法：定義指針p,q分別指向ha,hbi. p->exp=q->exp ,r->coef=p->coef+q->coef,pa,pb 下移;ii. p->expvq->exp ,r->coef=q->coef;r->exp=q->exp;,q 下移iii. pa->exp>pb->exp

3、, 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.其流程圖如下：fliulpo1yBheb*p ,+q,*s*r;M ultiplnMu lei pkiIH inulpwly *)m«l hvi si.Li midpoly*)makK(si.Muldpln*Mu Id pin多項式乘法：定義指針fp,gp分別指向f,g1. 將兩多項式最大指數(shù)相加并賦于maxp,并置g2用for循環(huán)求指數(shù)等于maxp時相乘的系數(shù)3. (fp!=NUL

4、L)&&( gp!=NULL), p=fp->exp+gp->exp1. p>maxp, fp=fp->n ext;2. pvmaxp, gp=gp->n ext;3. p=maxp, x+=fp->coef*gp->coef; fp=fp->n ext;gp=gp->n ext;mulpo *tp,*gpH+hp,*.r-inpK-01Tuliipkx五、實驗結(jié)果1分別輸入兩個多項式：5X3+4X2+3X+2和X2+X+1,然后輸出結(jié)果如下inuut coef and exp：Q 0The first poly is5x3

5、 4x2 3x1 2x input coef and exp：1 21 11 00 SOe second poly is:1x2 lxl 1x0I he result of po lj/add is:5x3 5x2 4x1 3x0Oe result of polmulti is:BxS 9x4 12x3 9x2 5x1 2x0Press ansF kep to continue.2.分別輸入兩個多項式：6X4+4X2+2和5X+6，然后輸出結(jié)果如下:input coef and exp:b4k 22 S0 0Tlie f irst poly is:6x4 4x2 2x0inpu.t coef

6、and exp =5 16 00 SThe second poly is:5x1 6x0The result of po ladd is:bx4 4x2 5x1 8x0The result of polvnulti is = OSxS 36x4 20x3 24x2 10x1 12x0Press any J<ev to continite_六、總結(jié)此次上機(jī)實驗應(yīng)用了線性表實現(xiàn)了一次實際操作，完成了一個一元多項式的簡單計算器，不僅對此次編譯程序的算法思想有了新的認(rèn)識，還讓我深刻的 體會到了線性表的重要性以及其應(yīng)用的方便，并且對指針加深了映象，應(yīng)用了 書本中的算法思想，對我以后的編譯以及完成新

7、的程序有很大的幫助。附錄：1. 建立多項式列表代碼如下：mulpoly *creatpoly()/*建立多項式列表 */mulpoly *head,*r,*s;/* 設(shè)中間變量 */int m,n;head=(mulpoly *)malloc(sizeof(mulpoly);/*頭結(jié)點申請空間 */prin tf("nin put coef and exp:n");scanf("%d%d",&n,&m);/*輸入多項式系數(shù)和指數(shù)*/r=head;/* 尾指針指向頭指針*/while(n!=0)/*將輸入的多項式存放在 S中*/s=(mul

8、poly*)malloc(sizeof(mulpoly);s->coef= n;s->exp=m;r->n ext=s;r=s;/*prin tf("i nput coef and exp:n" );*/scanf("%d%d",&n,&m);/*再次輸入多項式系數(shù)和指數(shù)*/r->next=NULL;/*將尾指針置空*/head=head->next;/*將head啞結(jié)點向前跑一個結(jié)點，使其不為空 */return (head);/* 返回多項式 */2. 兩個多項式相加代碼如下：mulpoly *polya

9、dd(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é)點空間 */s=hc;while(p!=NULL)&&(q!=NULL)/*兩多項式不為空 */if(p->exp=q->exp)/*指數(shù)相等 */x=p->coef+q->coef;/* 系數(shù)相加 */ if(x!=0)/*系數(shù)不為零*/r=(mulpoly*)malloc(sizeof(mu

10、lpoly);/*結(jié)果放 r 中存放 */r->exp=q->exp;r->coef=x;s->n ext=r;s=r;p=p->next;/*多項式前進(jìn)一項*/q=q->next;/*多項式前進(jìn)一項*/else if(p->expvq->exp)/*比較指數(shù)大小 */r=(mulpoly *)malloc(sizeof(mulpoly);r->coef=q->coef;r->exp=q->exp;s->n ext=r;s=r;q=q->n ext;elser=(mulpoly *)malloc(sizeof(

11、mulpoly);r->exp=p->exp;r->coef=p->coef;s->n ext=r;s=r;p=p->n ext;while(p!=NULL)/* 當(dāng)多項式p中不為空時照抄*/r=(mulpoly *)malloc(sizeof(mulpoly);r->exp=p->exp;r->coef=p->coef;s->n ext=r;s=r;p=p->n ext;while(q!=NULL)/* 當(dāng)多項式q中不為空時照抄*/r=(mulpoly *)malloc(sizeof(mulpoly);r->exp

12、=q->exp;r->coef=q->coef;s->n ext=r;s=r;q=q->next;/*將最終尾指針置空*/s-> next=NULL;r=hc;hc=hc- >n ext;free(r);/* 釋放 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ù)聲明 */

13、maxp=f->exp+g->exp;/*將兩多項式最大指數(shù)相加并賦于maxp*/h=(mulpoly *)malloc(sizeof(mulpoly);hp=h;g=reverse(g);/* 逆置 g*/for(r=maxp;r>=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=

14、fp->next;/*p大，fp到下一個結(jié)點，以確保p等于r*/elseif(p<r)gp=gp->next;/*p 小, gp到下一個結(jié)點，以確保 p等于r*/ else/*p 等于 r*/x+=fp->coef*gp->coef;/*將相乘之后指數(shù)為r時的系數(shù)給x*/fp=fp->n ext;gp=gp-> next;if(abs(x)>1e-6)/*條件限制，使得所求多項式系數(shù)絕對值不能太小*/q=(mulpoly *)malloc(sizeof(mulpoly);q->exp=r;q->coef=x;q->n ext=N

15、ULL;hp->n ext=q;hp=q;/*將所求結(jié)果給hp，h*/hp=h;h=h->next;/*將h的啞結(jié)點前進(jìn)，使不為空*/free(hp);/*釋放 hp*/return h;/*返回結(jié)果*/4. 定義鏈表逆置函數(shù)mulpoly *reverse(mulpoly *q)/*定義鏈表逆置函數(shù) */mulpoly *p1,*p2;if(q!=NULL)/*確保所要逆置多項式不為空*/p1=q->next;/*使p1指向下一個結(jié)點*/q->next=NULL;/* 將 q->next 為空*/while(p1!=NULL)/*循環(huán)使相鄰兩個結(jié)點逆置，直到最后

16、一個逆置為頭結(jié)點*/p2=p1- >n ext;p1- >n ext=q;q=p1;P仁 p2;return q;/*返回逆置結(jié)果*/5. 輸出多項式代碼如下：void polyout(mulpoly *head) /* 輸出多項式 */mulpoly *q,*p;/*p=head->n ext;*/p=head;while(p!=NULL)/*循環(huán)輸出多項式的系數(shù)和指數(shù)*/pri ntf("%dx%d ",p->coef,p->exp);p=p->n ext;prin tf("n");實驗二哈弗曼樹及哈弗曼編碼譯碼的

17、實現(xiàn)一、實驗?zāi)康暮鸵?、掌握樹的有關(guān)圖相關(guān)操作算法；2、熟悉樹的基本存儲方法；3、學(xué)習(xí)利用樹求解實際問題。二、實驗內(nèi)容和原理1、 實驗內(nèi)容：（1）構(gòu)造哈弗曼樹；（2）對單個結(jié)點編碼；（3）輸出樹；（4）編 碼；（5）譯碼。2、實驗原理：通過樹的有關(guān)圖的相關(guān)操作算法，以及樹的基本存儲方法，利用 樹來構(gòu)造哈夫曼樹及哈夫曼編碼，輸出哈夫曼樹及哈夫曼編碼，完成編碼與譯 碼的算法。三、實驗環(huán)境Visual C+ 6.0 及 PC機(jī)四、算法描述及實驗步驟思想算法：一棵有n個葉子結(jié)點的哈夫曼樹有2n-1個結(jié)點，所以可用大小為2n-1個元 素的數(shù)組構(gòu)造靜態(tài)鏈表來存儲哈夫曼樹， 一個數(shù)組元素中存放一個結(jié)點。結(jié)

18、點的 結(jié)構(gòu)可以這樣來考慮，由于每個葉子結(jié)點都有一個權(quán)重，構(gòu)造哈夫曼樹的過程中 每個分枝結(jié)點的權(quán)重等于兩個孩子結(jié)點權(quán)重的和，所以應(yīng)該有一個權(quán)重域和指向 左右孩子的兩個指針域；另外在建成哈夫曼樹之后，為了求得每個葉子結(jié)點的哈 夫曼編碼，需要走一條從葉子結(jié)點到根結(jié)點的路徑， 而譯碼的過程是從根結(jié)點出 發(fā)到葉子結(jié)點的不斷匹配的過程， 所以既需要知道孩子結(jié)點的信息，也需要知道 雙親結(jié)點的信息，應(yīng)該再有一個指向雙親結(jié)點的指針域。 由此可知，每個結(jié)點至 少應(yīng)該有一個權(quán)重域 weight和3個指針域parent,lchild和rchild，也是就是說， 要用靜態(tài)三叉鏈表來表示哈夫曼樹。由于在實際構(gòu)造哈夫曼樹時

19、，是由葉子結(jié)點的權(quán)重逐級構(gòu)造最后生成樹根，且在構(gòu)造過程中公與葉子結(jié)點的權(quán)重有關(guān)而與葉子結(jié)點的數(shù)據(jù)域外無關(guān)，所以構(gòu)造算法的實現(xiàn)中可以不考慮葉子結(jié)點的數(shù)據(jù)域， 并且在靜態(tài)三叉鏈表中從葉子結(jié) 點開始存放，然后不斷地反兩棵權(quán)重最小的子樹合并成為一棵權(quán)值為其和的較大 的子樹，逐步生成各內(nèi)部結(jié)點直到樹根。在建立哈夫曼樹的算法描述中，有效地利用了每個結(jié)點的雙親域pare nt的值 是否為了 -1來區(qū)分該結(jié)點是否是哈夫曼森林中一棵樹的根結(jié)點， 每次是在根結(jié)點 中找出兩個權(quán)重值weight最小的樹作為左右子樹構(gòu)造一棵更大的樹。求哈夫曼編碼的方法是，在已建好的哈夫曼樹中從每個葉子結(jié)點開始沿雙親 鏈域回退到根結(jié)點，

20、每回退一步走過哈夫曼樹的一個分枝得到一位哈夫曼編碼 值，由于每個葉子結(jié)點的哈夫曼編碼是從根結(jié)點到相應(yīng)葉子結(jié)點的路徑上各代碼 所組成的0，1序列，所以先得到的代碼為所求編碼的低位碼而后得到的為高位 碼。對于每個葉子結(jié)點的哈夫曼編碼可以考慮用一個一維數(shù)組bit從后向前依次保存所求得的各位編碼值，并用 start記住編碼在數(shù)組bit中的開始位置。如下面例子，有4個數(shù)2, 4，5，&將其構(gòu)造成哈夫曼樹。Cd)算法設(shè)計分析select(i nt t,i nt *s1,i nt *s2)函數(shù)用來實現(xiàn)選取最小和次最小的權(quán)重的下標(biāo)，其流程圖如下:create_ht_hc（函數(shù)用來構(gòu)造樹和碼，其流程圖如

21、下:showtree(i nt root,i nt tab)為用凹入法顯示樹，其流程圖如下:i+tMvllipk%CLTUb-'endkshowcode(int n)用來顯示01代碼，其流程圖如下:code2char(char t,char s函數(shù)用來譯碼。char2code(char s,char t)函數(shù)用來編碼，其流程圖如下:Lrltijjk.x-O,qx+tjhcyj-CMelk.五、實驗結(jié)果輸入5個葉子結(jié)點a,s,d,f,g。其權(quán)重分別為7, 13, 16, 4, 10。得出結(jié)果如下：Pleaseentern : SPleaseentei*s t r In g ： £

22、;4PJ. ea.seenterstring: a7Pleaseenterstring = s13Pleaseenterstring： d16Pleaseenterstr in sr ： g-10The tree is *S02110<H>114<f >2913<s>16<d>Each吞 code is :F：010s = 10d：llg; 00disggsdsgthe chars are: The code Is :Fle-ase tet* code =The char- ±s - sssdssdsrPi*ess any kep to

23、 conlime.六、總結(jié)本次實驗讓我更加了解了哈夫曼樹的構(gòu)造和生成方法，以及如何用順序存儲 結(jié)構(gòu)來存儲哈夫曼樹及構(gòu)樹過程的信息，如何進(jìn)行編碼、譯碼。也感知到模塊程 序設(shè)計在大程序設(shè)計使用中的普遍性，該實驗是最好的證明，通過模塊程序設(shè)計， 能夠使得程序可度可寫性明顯加強(qiáng)。通過本次實驗，使我初步掌握了二叉樹的結(jié)構(gòu)特性以及各種存儲的結(jié)構(gòu)的特 點及適用范圍，掌握了哈夫曼樹的定義和思想，以及哈夫曼編碼的代碼實現(xiàn)，初步掌握了用凹入法顯示樹。不過程序仍有樹的顯示部分不夠完善的缺點，在今后的學(xué)習(xí)中會注意改變。附錄：選擇最小和次最小的權(quán)重函數(shù)如下：void select(int t,int *s1,int *

24、s2) /*在 1t 之間選取 w最小的下標(biāo) si，次最小的下標(biāo)為s2*/ int i,w1,w2; /*最小的權(quán)重為 w1，次最小的權(quán)重為 w2*/w仁w2=32767; /* 初始化為無窮大*/for(i=1;i<=t;i+)if(hti.parent=O) /*選取最小的和次最小的*/ if(hti.w<w1)/*如果出現(xiàn)一個比w1還小的權(quán)，則把原先的 w1傳給w2,把新的權(quán)重賦給w1*/ w2=w1;*s2=*s1;w 仁hti.w;*s仁i; else if(hti.w<w2) /*如果出現(xiàn)一個比w2還小的權(quán)，則把新的權(quán)重賦給 w2,并記住其下標(biāo)*/ w2=hti.

25、w;*s2=i;構(gòu)造哈夫曼樹的代碼如下：void create_ht_hc() /*構(gòu)造樹和碼 */ int i,s1,s2,child,pare nt,w;char ch; cout<<"Pleaseenter n: " /* 輸入葉子數(shù) */ cin>>n; m=2*n-1;/*總結(jié)點數(shù)*/for(i=1;i<=n;i+) /*輸入數(shù)據(jù) */ cout«"Please en ter stri ng:"fflush(stdin); /*清空鍵盤緩沖區(qū)*/cin>>ch»w; hti.w=w;

26、 /*把初始的數(shù)據(jù)送入存儲空間*/hci.ch=ch;for(i=n+1;i<=m;i+) /* 建樹 */ select(i-1,&s1,&s2); /*選取最小的和次最小的權(quán)重*/hts1.parent=hts2.parent=i; /*把最小的和次最小的權(quán)連成樹*/hti.lch=s1; /*左孩子為最小的，右孩子為次最小的*/ child=i; hci.start=0; /* while(child!=m) /*初始化開始位置*/對葉子結(jié)點逐一求哈夫曼編碼*/hti.rch=s2; hti.w=hts1.w+hts2.w; /*pare nt for(i=1;i&

27、lt;=n;i+)/*建碼 */的權(quán)為孩子之和*/ pare nt=htchild.pare nt; if(child=htpare nt.rch) /* hci.codehci.start=1;左0右1*/elsehci.codehci.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«"

28、; " cout<<htroot.w;if(htroot.lch=0) /*如果為葉子結(jié)點，則輸出葉子結(jié)點*/coutvv” (” <<hcroot.ch<< ” ) ”； coutvvendl;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&

29、lt;<hci.ch<<":"for(j=hci.start-1;j>=0;j-) cout<<hci.codej; cout<<e ndl;對輸入的字符進(jìn)行編碼：void char2code(char s,char t)/* 編碼，若 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.

30、ch)for(k=hcj.start-1;k>=0;k-)tx+=hcj.codek+48; /*把整型轉(zhuǎn)換為字符型 */ tx='0' /*字符串結(jié)束標(biāo)志*/ 對輸入的數(shù)碼進(jìn)行譯碼：void code2char(char t,char s) /* 譯碼，若 t="000110101"，J則 s="abcd"*/ /*用指針掃描t，從根m開始向下遇0向左，遇1向右，直到找到葉子結(jié)點，并 輸出再返回根，從頭開始循環(huán)*/ int i=0,j=0,pare nt=m;/child;while(si) if(si='1')

31、pare nt=htpare nt.rch;else pare nt=htpare nt .l ch;if(htpare nt.lch=0) tj+=hcpare nt.ch;parent=m; i+; tj='0' /*字符串結(jié)束標(biāo)志 */ 實驗三 Dijkstra最短路徑 或Prim最小生成樹（二選一） -、實驗?zāi)康暮鸵?、掌握圖的有關(guān)圖相關(guān)操作算法。2、熟悉圖的基本存儲方法。3、了解掌握圖的基本術(shù)語。二、實驗內(nèi)容和原理實驗內(nèi)容：通過輸入起點、終點和權(quán)重構(gòu)造一個圖；通過輸入，將一個節(jié)點 作為起點；找到從起點到各個節(jié)點的最短路徑； 輸出圖與及到各個節(jié)點的最 短短徑；三、實驗

32、環(huán)境Visual C+ 6.0 及 PC機(jī)四、算法描述及實驗步驟Prim算法是人連通網(wǎng)中的某一個頂點開始，以此作為生成樹的初始狀態(tài)， 然后不斷地網(wǎng)中的其他頂點添加到生成樹上， 直到最后一個頂點添加到生成樹上時得到最小生成樹。（1）從網(wǎng)中任一頂點開始，把該頂點包含生成樹中，此時樹只有一個頂點。（2）找出一個端點在生成樹中另一個端點在生成樹外的所有邊，并把權(quán)值最小的邊連同它所關(guān)聯(lián)的另一個頂點添加到生成樹中；當(dāng)有兩條及以上具有相同最小權(quán)值的邊可供選擇時，選擇其中任意一條都可以。（3）反復(fù)執(zhí)行（2），直到所有頂點都包含在生成樹中時止。算法中由函數(shù) prim定義最小生成樹。由函數(shù)creat_graph建

33、立無向連通網(wǎng)。算法過程如下圖：-條邊四條邊五條邊定義最小生成樹的代碼如下:五、實驗結(jié)果實驗結(jié)果如下七ex numbei? of the graph：7 edsfe(uer'texl,uertex2, weight > =1,2,3 ex2 , ue ight > ： 1,3,2 eds(e<uei*texl j-uertexa, weight? ： 1,4,4 edgfe <uer-texluertex2 » we ight >,6,8edfi(e<uei*texl ,uertex2:2,3,1edge <uer-texluer七童3

34、<2, ue ight > ：2,5,4 edsje<uei*texl ,uertex2, weight> ：3,4,1 edge <uertexlj-uertExg, ue ight > ：3,5,3 edge<vertexl,vertex2,weightJ：4,5,5 edqe <uevtcxlrueytex2,ue ight >：4,6,3 edge <ueptexl,uertex2 we ight >：4,7,5 edfe <ucrtcxl ,ueytex2, ue ight > ：5,7,7 edsie&l

35、t;vertexl ,vertex2, weight > ：6,7,6 edge <ucrtcxl,uertex2 , ue ight > ：8 r 2,6 Min inulincost spann in9 tree <prim> : edeue iQfhl:ulu3 2 u3u21u3u4 1 u3u5 3 u4q& 3 kj4u7 5六、總結(jié)1).通過這次實驗，使我掌握了用prim算法構(gòu)造最小生成樹的思想。掌握了 鄰接矩陣的構(gòu)造思想及其應(yīng)用。3) .掌握圖與網(wǎng)的基本概念和基本存儲方法。4) .掌握有向及無向連通圖的概念及其應(yīng)用。5) .對編程有了更深的

36、理解與掌握。附錄：void creat_graph(graph *p)/*建立無向連通網(wǎng) */int i,j,n ;int v1,v2,w;/*定義兩端點及其權(quán)值為整型*/printf("vertex number of the graph:"); /*輸入無向網(wǎng)的端點數(shù) */sca nf("%d",&n);p->vnum=n; for(i=1;i<=n;i+)/*初始化結(jié)構(gòu)體中的元素 */for(j=1;j<=n ;j+)if(i=j) /*對角線上的元素的權(quán)值為0*/p->arcsij=0;else /*非對角線上的元

37、素的權(quán)值為 MAX即99*/p->arcsij=MAX;do/*執(zhí)行循環(huán)語句*/printf("edge(vertex1,vertex2,weight):"); /*輸入兩個端點及其權(quán)值 */sca nf("%d,%d,%d",&v1,&v2, &w);if(v1>=1 &&v1<=n&&v2>=1 &&v2<=n)p->arcsv1v2=w;p->arcsv2v1=w;while(!(v1=8|v2=8);/*當(dāng) v1, v2 其中一個為

38、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.v nu m;i+)closesti=v; /*填邊在生成樹一端的頂點序號*/lowcosti=G.arcsvi;/*填邊的權(quán)值 */ c=1;p=1;/* 從v1開始構(gòu)造最小生成樹*/for(i=1;i<G.vnum;i+)/*循環(huán)n-1次，選n-1條邊于生成樹中*/min=MAX;/*初定min值為上限值99*/for(j=1;j<

39、=G.vnum;j+)/*選最小權(quán)值及對應(yīng)頂點*/if(lowcostj!=0&&lowcostj<mi n)min=lowcostj; /*最小權(quán)值記在 min 中*/k=j; /*把與邊關(guān)聯(lián)的生成樹外的頂點序號記在k中*/treep1=closestk; /*將所得值存入出發(fā)端點*/treep2=k;/*將k存入另一個端點*/treep3=min;/*存儲兩個端點的最小權(quán)值*/p+; c+=min;lowcostk=0;/* 將頂點k加入生成樹中*/for(j=1;j<=G.v nu m;j+)if(G.arcskj!=0&&G.arcskj&l

40、t;lowcostj)lowcostj=G.arcskj; /*修改權(quán)值域 */closestj=k; retur n c; 實驗四（快速、堆、歸并）排序算法的設(shè)計（三選一）一、實驗?zāi)康暮鸵?、掌握常用的排序方法和各種排序方法的特點。2、熟悉排序的基本概念。二、實驗內(nèi)容和原理1、輸入一個數(shù)組長度隨機(jī)的數(shù)組。2、對數(shù)組中的各個元素進(jìn)行排序。三、實驗環(huán)境Visual C+6.0 及 PC 機(jī)四、算法描述及實驗步驟思想算法：快速排序的算法思想是：有一組待排序的數(shù)組如76，31, 76, 79, 25, 29,12, 78，把每組第一個元素的排序碼為基準(zhǔn)進(jìn)行分組，并采用從兩端往中間收縮的方式為該基準(zhǔn)

41、元素找插入位置。 以第一次分組為例，首先，將元素R1存人 變量R0中，引人變量i（初始值為1）和j（初始值為n）,然后，比較R0和Rj 的排序碼，若Rj的排序碼較大，則j減I，繼續(xù)比較R0和Rj;若R0的排 序碼較小，則將Rj存人Ri中，在i加I后，轉(zhuǎn)而比較R0和Ri的排序碼;若 Ri的排序碼較小，則i加1,繼續(xù)比較R0和Ri;若Ri的排序碼較大，則將Ri存人Rj中，在j減I后，轉(zhuǎn)而比較R0和Rj。如此交替進(jìn)行下去，直至i=j 時，將R0存人Rj中，一次分組過程便告結(jié)束。圖8, 7所示的是對8個元素進(jìn)行一次分組的過程，其中花括號指出待分組的區(qū)間。R0R1R2R3R4R5R6 R7R876 ,3

42、1,76,79,25,29,12,7876 口,j31,76,79,25,29,12,78j1口，i31,76,79,25,29,12,78i12 ,31,i76,79,25,29,j口，7812 ,31,76,79,25,29,j口，78ij12，31,76,79,25,29,口，j7812，31,76,1口，25,29,79,7812，31,76,1口，25,29,j79,7812，31,76,i29,25,ij口，j79,7812，31,76,29,i25,口，79,78ij圖8.7快速排序的一次分組過程4.1算法設(shè)計分析算法 int divideareasort(recordtype

43、R,int s,int t)用于實現(xiàn)一次分組：它以 Ri為 標(biāo)準(zhǔn)，將RiRj分為兩組，使得RiRk-1的排序碼都不大于Rk的排序碼， Rk+1Rk的排序碼都不小于Rk的排序碼，并返回k值。(代碼在附錄)對于待排序文件R利用一次分割敬意排序算法時，令s=1和t=n即可完成第一趟排序；由此得到的兩個更小的敬意R1,i-1和Ri+1,n，繼續(xù)利用算法divideareasort分割為更小的4個敬意；如此一直進(jìn)行下去，直到都分割為 只有一個記錄時排序結(jié)束。調(diào)用 divideareasort對R進(jìn)行快速排序的遞歸算法。 (代碼在附錄)五、實驗結(jié)果輸入一組數(shù)據(jù)如76，31, 76, 79，25, 29，1

44、2, 78，得出結(jié)果如下：六、總結(jié)通過本次上機(jī)實驗我掌握了利用數(shù)組的順序存儲結(jié)構(gòu)的基本操作和快速排 序算法設(shè)計的實現(xiàn)。以及快速排序和冒泡排序，直接插入排序以及其他各種排序 的不同。也讓我看到了他們的優(yōu)點和缺點。 在編程過程中，更加熟練了程序的編 寫步驟及要領(lǐng)。附錄：(1) divideareasort 的代碼如下: int divideareasort(recordtype R,i nt s,i nt t)/對待排序記錄區(qū)間Rs到Rt以為基準(zhǔn)進(jìn)行一次分割排序，并返回基準(zhǔn)記錄 的最終位置int i,j;定義指示器變量recordtype temp;/定義暫存工作單元i=s;j=t;區(qū)間指示器變量

45、初始化temp=Rs; 確定分割基準(zhǔn)dowhile(Rj.key>=temp.key)&&( i<j)j-;自后向前掃描找小于基準(zhǔn)關(guān)鍵字的記錄if(ivj)Ri=Rj；把 Rj移入 Ri中i+;令i指向i+1while(Ri.keyv=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(recordtyp

46、e R,int s,int t)/對排序文件 Rs.t 進(jìn)行快速排序int i;/定義局部變量if(s<t)i=divideareasort(R,s,t);分割區(qū)間并把基準(zhǔn)位置送iquicksort(R,s,i-1);對基準(zhǔn)記錄前的區(qū)間的快速排序quicksort(R,i+1,t);對基準(zhǔn)記錄前的區(qū)間的快速排序 實驗五構(gòu)造平衡二叉排序樹一、實驗?zāi)康暮鸵?、掌握樹型檢索的基本概念2、掌握平衡二叉樹的基本概念及原理二、實驗內(nèi)容和原理1、實驗內(nèi)容：構(gòu)造平衡二叉排序樹，實現(xiàn)平衡二叉樹結(jié)果的輸入與輸出。2、實驗原理：構(gòu)造平衡二叉樹的基本思想是在構(gòu)造的過程中，每當(dāng)插入一個結(jié)點后都去檢查是否由于該結(jié)

47、點的插入而破壞了AVL樹；若出現(xiàn)絕對值超過1的平衡因子，則需要在保持 AVL樹特性的前提下通過先判斷類型后用相應(yīng)的旋轉(zhuǎn)方法調(diào)整使之達(dá)到新的平衡。3、實驗方法：由老師提供程序模板供學(xué)生參考， 學(xué)生在模板的指導(dǎo)下改寫程序， 在老師的指導(dǎo)下編譯、調(diào)試、運(yùn)行。三、實驗環(huán)境Visual C+ 6.0 及 PC 機(jī)四、算法描述及實驗步驟1）對關(guān)鍵碼序列L從小到大進(jìn)行排序得到L'；2）選擇序列L '中中間元素m作為AVL樹的根，在m左邊的元素作為AVL樹的左子樹元素，在m右邊的元素作為AVL樹的右子樹元素。3）按2的方法分別構(gòu)建AVL樹的左子樹和右子樹。構(gòu)建過程如下圖所示。主要函數(shù)void

48、lrflip() ，用于進(jìn)行LR型平衡旋轉(zhuǎn)p-r*-jrclihMiihipkcii imeroctt 缸主要函數(shù)void rlflip() ，用于進(jìn)行RL型平衡旋轉(zhuǎn)Qp-r- deb:chaiigertioU J.,用于增加結(jié)點主要函數(shù) void avlt_insert(int key)T(wr-(bcsiree* )ma lie”rtluni:p-NULUMultiplexMultiplex五、實驗結(jié)果輸入以下數(shù)字：5, 6, 15, 79, 35, 58,結(jié)果如下六、總結(jié)通過本次上機(jī)實驗讓我更了解了平衡二叉樹的定義和它的構(gòu)造。但對于平衡二叉樹的應(yīng)用，還存在的一些問題。經(jīng)過網(wǎng)上的搜索，發(fā)現(xiàn)對平衡二叉樹的構(gòu)造 是一個比較難的問題。很多人都覺得很難，現(xiàn)實中很難用到。當(dāng)然可能是我對平 衡二叉樹還不是很理解。附錄：void llflip() p=r; s