數(shù)據(jù)結構與算法實驗學期總結

1、數(shù)據(jù)結構與算法實驗學期總結我的數(shù)據(jù)結構班級：09計本一班學號：2009810020姓名：吳偉摘要數(shù)據(jù)結構實驗的目的是為了加深對課堂知識的理解，培養(yǎng)實驗者的動手能力和思維能力。實驗中，能體會到了算法和源程序之間的區(qū)別，理解到要實現(xiàn)算法要做的事情，解決編寫源程序時遇到的各類問題。關鍵字：算法、源程序、算法實現(xiàn)、解決問題一、數(shù)據(jù)結構與算法課程實驗的主要意義的目的數(shù)據(jù)結構課程的實踐性很強，許多內(nèi)容如果只進行單純的課堂講授是根本不能夠深刻認識的。例如，第二章線性表的多種存儲結構的對比分析，如不上機練習，就只能靠自己背，但這樣就不能有更直觀、形象的認識了。因此，實驗是數(shù)據(jù)結構課程的一個重要環(huán)節(jié)。首先，在實

2、驗的過程中，可以會體會到源程序與算法的區(qū)別。算法是一種算法描述語言。它不是一種現(xiàn)實存在的編程語言。使用算法的目的是為了使被描述的算法可以容易地以任何一種編程語言(Pascal,C,Java,etc)實現(xiàn)。它可能綜合使用多種編程語言中語法、保留字，甚至會用到自然語言。因此，算法必須結構清晰，代碼簡單，可讀性好，并且類似自然語言。源程序(sourcecode)是指未編譯的按照一定的程序設計語言規(guī)范書寫的，一系列人類可讀的計算機語言指令。其實現(xiàn)起來，有時并不像算法那樣看起來那么簡單。例如，希爾排序的算法：voidShellSort(SSTable&L,intdlta口，intt)/按增量序列

3、dlta0t-1對順序表L做希爾排序for(intk=0;k<t;+k)ShellInsert(L,dltak);/一趟增量為dltak的插入排序/ShellSort看到該算法，基本都會明白：又tL執(zhí)行t次ShellInsert(L,dlatk)操作就能完成希爾排序。然而，要真正的實現(xiàn)該功能，必須有完整的代碼：boolLT(chara,charb)returna<b;/重建靜態(tài)查找表為按關鍵字非降序排序。voidShellInsert(SSTable&L,intdk)inti,j;for(i=dk+1;i<=L.length;+i)if(LT(L.elemi.key,

4、L.elemi-dk.key)/需將L.ri插入有序增量子表L.elem0=L.elemi;/暫存在L.r0for(j=i-dk;j>0&&LT(L.elem0.key,L.elemj.key);j-=dk)L.elemj+dk=L.elemj;/記錄后移，查找插入位置L.elemj+dk=L.elem0;/插入/ShellInvoidShellSort(SSTable&L,intdlta,intt)for(intk=0;k<t;+k)ShellInsert(L,dltak);/一趟增量為dltak的插入排序/ShellSort所以，算法只用來說明復雜的問題

5、，并不一定可以執(zhí)行。再次，實驗會增強你的算法實現(xiàn)能力，鍛煉你的思維和解決問題的能力。在我們的數(shù)據(jù)結構課上，能學到的都是各種功能算法，沒有源代碼。所以，如果要做實驗，你就必須思考，想各種方法來實現(xiàn)算法。在此過程中需要解決各類問題，使源代碼盡可能正確的達到算法的思想。實驗中，算法的實現(xiàn)會讓我更容易的記住所學的知識，用一個開玩笑的引用：“一朝被蛇咬，十年怕井繩”。二、概述本學期的實驗內(nèi)容和目的實驗一實驗名稱：對比算法的時空效率實驗目的及要求：1. 熟悉開發(fā)工具的編程環(huán)境。2. 熟悉算法語言并完成簡單的算法。3. 熟悉C語言的語法，將算法上機編程實現(xiàn)。4. 區(qū)別算法和源程序。5. 體會用不同算法解決同

6、一個問題，體會存儲結構不同對實現(xiàn)算法的影響。6. 學習對算法進行時空分析的基本方法。7. 了解評價一個算法的基本準則。實驗主要內(nèi)容：試編寫求k階(k>=2)裴波那契序列的第m項值的不同算法，并編程實現(xiàn)。k和m均以值調用的形式在函數(shù)參數(shù)中表現(xiàn)。要求：至少用兩種不同的算法(如，遞推、遞歸等等)。實驗中涉及的主要實驗原理：k=1時，fac(0)=0,fac(1)=1fac(n)=fac(n-1)+fac(n-2)n=2,3,4,5k=2時，fac(0)=0,fac(1)=0,fac(2)=1fac(n)=fac(n-1)+fac(n-2)n=3,4,5,6概要設計和存儲結構：首先向內(nèi)存申請大小

7、為k+1的空間，第0號空間用來做輔存。第k號空間放1，其他放0。然后按照斐波那契序列的計算方法計算下一項，再把整個數(shù)組左移，最后把計算出來的數(shù)放在最大位。一直循環(huán)直到算出你要的答案。存儲結構為：一維數(shù)組(int*a=newintk+1;)主要算法：voidfac(intk,intm,inta)/k是斐波那契序列的階數(shù)，m是要輸出的項數(shù)，a是進行排列操作的數(shù)組int*a=newintk+1;for(i=0;i<=k;i+)ai=0;ak=1;/進行階斐波那契序列的輸出，如果要輸出的項m大于階數(shù)k,則直接/輸出數(shù)組的第m+項if(m<=k)fac(m)=am;else/如果項大于階數(shù)，

8、則先進行遞推計算，再輸出for(intl=1;l<=m-k;l+)/因為序列的前k項已經(jīng)給出，所以要輸出第nffi只用循環(huán)m-k次for(i=0;i<k;i+)ai=ai+1;for(t=0,j=0;j<k;j+)t+=aj;fac(m)=t;實驗結果和結論：根據(jù)2斐波那契序列的推導公式：fac(0)=0,fac(1)=1,fac(2)=1,fac(3)=2,fac(4)=3,則上面的結果正確。同理，該結果也正確根據(jù)5斐波那契序列的推導公式：fac(0)=0,fac(1)=0,fac(2)=0,fac(3)=0,fac(4)=1,fac(5)=1,fac(6)=2,fac(7

9、)=4，由此，上面結果正確。實驗分析：我的算法用的是順序存儲結構，并采用遞推的計算法。我感覺好處是，代碼不算太多，不是太累贅；壞處是，for循環(huán)比較多，容易混淆。一開始，程序能運行，但輸出的數(shù)不對，經(jīng)過查找發(fā)現(xiàn)是第四個for語句中的t做完一次后沒有初始化(開始的程序t是在定義時初始化的)。接著，再運行，發(fā)現(xiàn)輸出錯位，經(jīng)檢查，第二個for循環(huán)次數(shù)不對，應該是m-k次，開始是m次，改過之后輸出正確。雖然，該算法有的地方做的還算可以，但是現(xiàn)在看來在實驗的其他方面做的不是很好，還有待改進，例如：沒有考慮到斐波那契序列數(shù)據(jù)的數(shù)據(jù)類型，我用的是int這樣要輸出很大項的時候，int型的數(shù)據(jù)不夠。實驗二實驗名

10、稱：線性表實驗目的及要求：熟悉如何使用單鏈表，掌握單鏈表的基本操作，鞏固對單鏈表知識的認識。實驗主要內(nèi)容：約瑟夫環(huán)。假設有n個編號為1,2,3,，n的人按順時針方向圍坐一圈，每人持有一個密碼（正整數(shù)）。一開始任選一個正整數(shù)作為報數(shù)的上限值m，從第一個人開始按順時針方向自1開始順序報數(shù)，報到m時停止報數(shù)。報m的人出列，并將其密碼值作為新的m值，從他在順時針方向上的下一個人開始重新從1報數(shù)，以此類推下去，直到所有的人全部出列為止。試設計一個程序，可以在用戶確定了人數(shù)和密碼的情況下，求出對應的出列順序。實驗中涉及的主要實驗原理：有n個編號為1,2,3,，n的人按順時針方向圍坐一圈，每人持有一個密碼（

11、正整數(shù)）。一開始任選一個正整數(shù)作為報數(shù)的上限值m,從第一個人開始按順時針方向自1開始順序報數(shù)，報到m時停止報數(shù)。報m的人出列，并將其密碼值作為新的m值，從他在順時針方向上的下一個人開始重新從1報數(shù)，以此類推下去，直到所有的人全部出列為止。概要設計和存儲結構：該算法的實現(xiàn)用循環(huán)鏈表：/data1 存儲參加游戲者的編號/data2 存儲參加游戲者的密碼 /next 為結點指針structLNodeintdata1;intdata2;structLNode*next;/執(zhí)行游戲規(guī)則主要算法：voidBuildGame(LinkList&L,intm,intk)p=(LinkList)mall

12、oc(sizeof(LNode);/參加游戲者為k人，所以循環(huán)/游戲規(guī)則：從第一個人開始報/并將他的密碼作為下一個ms,依p->next=L;for(i=0;i<k;i+)k次后游戲結束for(j=1;j<m;j+)數(shù)，報到初始值m勺人出列，p=p->next;次循環(huán)，直到游戲結束r=p->next;cout<<r->data1<<''m=r->data2;p->next=r->next;p=r;實驗結果和結論:請依次輸入?yún)⒓訙蕬蛎拿艽a，5463411109請輸入初始E：2H依次出列的人K：2a3?

13、91564倩按任意鍵繼續(xù)一.-富密小落吧噂薛堂耦蠢替巧請依七心前八（脂對在的洞r：蓍耙表能入叁加遁或者的宙科-fi9459清輸.Aj初始E!3上次出列的人為.蒲森品餐融勝蟀-根據(jù)約瑟夫環(huán)的游戲規(guī)則，上述三個結果都正確實驗分析：算法用到的是循環(huán)鏈表。在進行鏈表數(shù)據(jù)輸入的時候由于有兩個數(shù)據(jù)，所以要循環(huán)兩次，這樣輔助指針就比較多，后面執(zhí)行游戲規(guī)則的函數(shù)里也用到了比較多的輔助指針，用起來比較復雜，這個算法我感覺在這方面不太好，容易搞混淆。但是，當時能做到這里我感覺已經(jīng)不錯了實驗三實驗名稱：棧和隊實驗目的及要求：熟悉對棧和隊的應用,熟悉其基本操作。增強自己的動手能力和實驗能力。實驗主要內(nèi)容：輸入一個十進

14、制數(shù)(整數(shù)和小數(shù))和進制數(shù)，要求程序輸出轉換后的數(shù)。例如，輸入5，再輸入進制數(shù)為2，則應該輸出101。實驗中涉及的主要實驗原理：十進制數(shù)和其他進制數(shù)之間的轉換。整數(shù)部分為除進制數(shù)(如除2)取余最后逆置，小數(shù)部分為乘進制數(shù)取整，最后順序放置。概要設計和存儲結構：本算法用了棧和隊兩類存儲結構。其中，棧：typedefstructint*base;int*top;intsize;sqstack;用來存儲整數(shù)部分；隊：structQNodedoubledata;structQNode*next;typedefQNode*QueuePtr;typedefstructQueuePtrfront;Queue

15、Ptrrear;Linkqueue;用來存儲小數(shù)部分。主要算法：Statusjzzh(sqstack&s,Linkqueue&Q,SElemTypem,SElemTypen)/進制轉換，包含整數(shù)部分和小數(shù)部分的轉換while(m1!=0)/m1=int(m-modf(m,&p)push(s,m1%n);m1=m1/n;while(modf(m,&p)m=modf(m,&p)*n;enqueue(Q,m-modf(m,&p);returnOK;實驗四實驗名稱：二叉樹實驗目的及要求：熟悉對二叉樹的應用,熟悉其各種遍歷的基本規(guī)則，了解樹的創(chuàng)建的基本原理

16、。增強自己的動手能力和實驗能力。實驗主要內(nèi)容：創(chuàng)建一顆二叉樹，對其進行先序、中序、后序遍歷以及其他操作。概要設計和存儲結構：typedefstructBiTNodeTElemTypedata;structBiTNode*lchild,*rchild;BiTNode,*BiTr主要算法：StatusPreOrderTraverse(BiTreeT)if(T)/cout<<T->data;PreOrderTraverse(T->lchild);PreOrderTraverse(T->rchild);returnOK;StatusInOrderTraverse(BiTr

17、eeT)if(T)InOrderTraverse(T->lchild);cout<<T->data;InOrderTraverse(T->rchild);returnOK;StatusPostOrderTraverse(BiTreeT)if(T)/中序、后序遍歷以及其他操作/數(shù)據(jù)域/指向左右孩子的指針lchild,rchild/先序遍歷判斷二叉樹是否為空/訪問Data/遞歸遍歷左子樹/遞歸遍歷右子樹/中序遍歷/判斷二叉樹是否為空/遞歸遍歷左子樹/遞歸遍歷右子樹/后序遍歷非空二叉樹/ 遞歸遍歷左子樹/ 遞歸遍歷右子樹PostOrderTraverse(T->l

18、child);PostOrderTraverse(T->rchild);cout<<T->data;returnOK;intCountNode(BiTreeT)/統(tǒng)計結點總數(shù)if(T)return1+CountNode(T->lchild)+CountNode(T->rchild);/遞歸遍歷左右子樹，每過一個結點else/加，最后加上根結點return0;intCountLeaf(BiTreeT)/統(tǒng)計葉子總數(shù)if(T)if(!T->lchild&&!T->rchild)return1;elsereturnCountLeaf(T

19、->lchild)+CountLeaf(T->rchild);elsereturn0;StatusExchange(BiTree&T)/交換左右子樹if(T)temp=T->lchild;T->lchild=T->rchild;T->rchild=temp;if(T->lchild)Exchange(T->lchild);if(T->rchild)Exchange(T->rchild);returnOK;實驗結果和結論：宜宜子 7FMFM 丁 n 力福左 0 1 2 3 4 LJ 61 .!V . “里 一 懶 隘饕 孝理 f

20、cIPJJUl B r一曷縣十 中父 & 1 2 3 4 5 6一 耳直子一歷歷歷就舌招葉左 簟中后施福劉 12 3 4 5 6人詵和一廣超嗯察葉左 一麝中后統(tǒng)統(tǒng)交博輸入城Fl一- -功能清單點后翁吉翠圖并先序遍歷請篁入矩束1±y，n,y帝技任意鍵讓綏一由于在該程序中，加了一個可選擇菜單，因此，該程序的執(zhí)行是一直連續(xù)的，如上圖，執(zhí)行順序是從左到右，從上到下。首先，先序創(chuàng)建二叉樹為：AB（$D$EF$G$（$代表空格），由于是先序創(chuàng)建，所以先序遍歷的結果也是ABCDEFG因此第一個結果正確；打一鍵繼續(xù)后選擇后序遍歷，如圖所示二叉樹，后序遍歷的結果為CDBGFEAI此第二個結果正

21、確；由輸入的字母數(shù)可知第三個結果也是正確的；后面兩個結果都是判斷輸入的合法性，并且都判斷正確。'G實驗分析:本次所做的實驗難度不是很高，同時我認為該實驗的創(chuàng)建二叉樹算法并不是很好，因為只有保證輸入空格的數(shù)量和位置絕對正確才能保證創(chuàng)建函數(shù)的結束，否則將無法繼續(xù)。而且這里無法判斷輸入的合法性。實驗五實驗名稱：查找和排序實驗目的及要求：學習和掌握排序和查找這兩個計算機程序設計中的重要操作。加強自己的動手能力和錯誤分析能力。實驗主要內(nèi)容：選擇一種查找和排序算法，實現(xiàn)查找造和排序。概要設計和存儲結構：本程序中用到了順序表存儲結構和兒茶鏈表存儲結構，兩種結構的作用為：順序表用來存儲順序查找表；二叉

22、鏈表用來存儲次優(yōu)查找樹。/順序表的順序存儲表示typedefstructcharkey;intweight;ElemType;typedefstructElemType*elem;intlength;SSTable;/二叉樹的二叉鏈表存儲表示typedefstructBiTNodeElemTypedata;structBiTNode*lchild,*rchild;BiTNode,*BiTree;主要算法：/重建靜態(tài)查找表為按關鍵字非降序排序。voidShellInsert(SSTable&L,intdk)for(i=dk+1;i<=L.length;+i)if(LT(L.elem

23、i.key,L.elemi-dk.key)/需將L.ri插入有序增量子表L.elem0=L.elemi;/暫存在L.r0for(j=i-dk;j>0&&LT(L.elem0.key,L.elemj.key);j-=dk)L.elemj+dk=L.elemj;/記錄后移，查找插入位置L.elemj+dk=L.elem0;/插入/ShellIn/由有序表Rlow.high及其累計權值表sw(其中sw0=0)遞歸構造/次優(yōu)查找樹T。intSecondOptimal(BiTree&T,ElemTypeR,intsw,intlow,inthigh)min=abs(swhig

24、h-swlow);/fabs函數(shù)是求絕對值的dw=swhigh+swlow-1;for(j=low+1;j<=high;+j)/選擇最小的Pi值if(fabs(dw-swj-swj-1)<min)i=j;min=fabs(dw-swj-swj-1);T=(BiTree)malloc(sizeof(BiTNode);if(!T)return0;T->data=Ri;/生成結點if(i=low)T->lchild=NULL;/左子樹空elseSecondOptimal(T->lchild,R,sw,low,i-1);/構造左子樹if(i=high)T->rchild=NULL;/右子樹空elseSecondOptimal(T->rchild,R,sw,i+1,high);/構造右子樹return1;/在次優(yōu)查找樹T中查找關鍵字等于key的元素。找到則返回，否則返回intSearch_SOSTree(SOSTree&T,charkey)while(T)/T非空if(T->data.key=key)return1;elseif(T->data.key>key)T=T->lchild;