數(shù)據(jù)結(jié)構(gòu)與算法實驗學(xué)期總結(jié)

/數(shù)據(jù)結(jié)構(gòu)與算法實驗學(xué)期總結(jié)我的數(shù)據(jù)結(jié)構(gòu)班級：09計本一班學(xué)號：2009810020姓名：吳偉摘要數(shù)據(jù)結(jié)構(gòu)實驗的目的是為了加深對課堂知識的理解，培養(yǎng)實驗者的動手能力和思維能力。實驗中，能體會到了算法和源程序之間的區(qū)別，理解到要實現(xiàn)算法要做的事情，解決編寫源程序時遇到的各類問題。關(guān)鍵字：算法、源程序、算法實現(xiàn)、解決問題數(shù)據(jù)結(jié)構(gòu)與算法課程實驗的主要意義的目的數(shù)據(jù)結(jié)構(gòu)課程的實踐性很強，許多內(nèi)容如果只進行單純的課堂講授是根本不能夠深刻認識的。例如，第二章線性表的多種存儲結(jié)構(gòu)的對比分析，如不上機練習(xí)，就只能靠自己背，但這樣就不能有更直觀、形象的認識了。因此，實驗是數(shù)據(jù)結(jié)構(gòu)課程的一個重要環(huán)節(jié)。首先，在實驗的過程中，可以會體會到源程序與算法的區(qū)別。算法是一種算法描述語言。它不是一種現(xiàn)實存在的編程語言。使用算法的目的是為了使被描述的算法可以容易地以任何一種編程語言(Pascal,C,Java,etc)實現(xiàn)。它可能綜合使用多種編程語言中語法、保留字，甚至?xí)玫阶匀徽Z言。因此，算法必須結(jié)構(gòu)清晰，代碼簡單，可讀性好，并且類似自然語言。源程序(sourcecode)是指未編譯的按照一定的程序設(shè)計語言規(guī)范書寫的，一系列人類可讀的計算機語言指令。其實現(xiàn)起來，有時并不像算法那樣看起來那么簡單。例如，希爾排序的算法：voidShellSort(SSTable&L,intdlta[],intt){//按增量序列dlta[0...t-1]對順序表L做希爾排序for(intk=0;k<t;++k)ShellInsert(L,dlta[k]);//一趟增量為dlta[k]的插入排序}//ShellSort看到該算法，基本都會明白：對L執(zhí)行t次ShellInsert(L,dlat[k])操作就能完成希爾排序。然而，要真正的實現(xiàn)該功能，必須有完整的代碼：boolLT(chara,charb){ returna<b;}//重建靜態(tài)查找表為按關(guān)鍵字非降序排序。voidShellInsert(SSTable&L,intdk){inti,j;for(i=dk+1;i<=L.length;++i)if(LT(L.elem[i].key,L.elem[i-dk].key)){//需將L.r[i]插入有序增量子表L.elem[0]=L.elem[i];//暫存在L.r[0]for(j=i-dk;j>0&<(L.elem[0].key,L.elem[j].key);j-=dk)L.elem[j+dk]=L.elem[j];//記錄后移，查找插入位置L.elem[j+dk]=L.elem[0];//插入}}//ShellInvoidShellSort(SSTable&L,intdlta[],intt){for(intk=0;k<t;++k)ShellInsert(L,dlta[k]);//一趟增量為dlta[k]的插入排序}//ShellSort所以，算法只用來說明復(fù)雜的問題，并不一定可以執(zhí)行。再次，實驗會增強你的算法實現(xiàn)能力，鍛煉你的思維和解決問題的能力。在我們的數(shù)據(jù)結(jié)構(gòu)課上，能學(xué)到的都是各種功能算法，沒有源代碼。所以，如果要做實驗，你就必須思考，想各種方法來實現(xiàn)算法。在此過程中需要解決各類問題，使源代碼盡可能正確的達到算法的思想。實驗中，算法的實現(xiàn)會讓我更容易的記住所學(xué)的知識，用一個開玩笑的引用：“一朝被蛇咬，十年怕井繩”。概述本學(xué)期的實驗內(nèi)容和目的實驗一實驗名稱：《對比算法的時空效率》實驗?zāi)康呐c要求：熟悉開發(fā)工具的編程環(huán)境。熟悉算法語言并完成簡單的算法。熟悉C語言的語法，將算法上機編程實現(xiàn)。區(qū)別算法和源程序。體會用不同算法解決同一個問題，體會存儲結(jié)構(gòu)不同對實現(xiàn)算法的影響。學(xué)習(xí)對算法進行時空分析的基本方法。了解評價一個算法的基本準則。實驗主要內(nèi)容：試編寫求k階（k>=2）裴波那契序列的第m項值的不同算法，并編程實現(xiàn)。k和m均以值調(diào)用的形式在函數(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概要設(shè)計和存儲結(jié)構(gòu)：首先向內(nèi)存申請大小為k+1的空間，第0號空間用來做輔存。第k號空間放1，其他放0。然后按照斐波那契序列的計算方法計算下一項，再把整個數(shù)組左移，最后把計算出來的數(shù)放在最大位。一直循環(huán)直到算出你要的答案。存儲結(jié)構(gòu)為：一維數(shù)組（int*a=newint[k+1];）主要算法：voidfac(intk,intm,inta[]){//k是斐波那契序列的階數(shù)，m是要輸出的項數(shù)，a是進行排列操作的數(shù)組int*a=newint[k+1]; for(i=0;i<=k;i++) a[i]=0; a[k]=1;//進行階斐波那契序列的輸出，如果要輸出的項m不大于階數(shù)k，則直接//輸出數(shù)組的第m+1項 if(m<=k)fac(m)=a[m]; else{//如果項大于階數(shù)，則先進行遞推計算，再輸出 for(intl=1;l<=m-k;l++){//因為序列的前k項已經(jīng)給出，所以要輸出第m項只用循環(huán)m-k次 for(i=0;i<k;i++){ a[i]=a[i+1]; } for(t=0,j=0;j<k;j++) t+=a[j]; fac(m)=t; }}}實驗結(jié)果和結(jié)論：根據(jù)2斐波那契序列的推導(dǎo)公式：fac(0)=0,fac(1)=1,fac(2)=1,fac(3)=2,fac(4)=3,則上面的結(jié)果正確。同理，該結(jié)果也正確。根據(jù)5斐波那契序列的推導(dǎo)公式：fac(0)=0,fac(1)=0,fac(2)=0,fac(3)=0,fac(4)=1,fac(5)=1,fac(6)=2,fac(7)=4，由此，上面結(jié)果正確。實驗分析：我的算法用的是順序存儲結(jié)構(gòu)，并采用遞推的計算法。我感覺好處是，代碼不算太多，不是太累贅；壞處是，for循環(huán)比較多，容易混淆。一開始，程序能運行，但輸出的數(shù)不對，經(jīng)過查找發(fā)現(xiàn)是第四個for語句中的t做完一次后沒有初始化（開始的程序t是在定義時初始化的）。接著，再運行，發(fā)現(xiàn)輸出錯位，經(jīng)檢查，第二個for循環(huán)次數(shù)不對，應(yīng)該是m-k次，開始是m次，改過之后輸出正確。雖然，該算法有的地方做的還算可以，但是現(xiàn)在看來在實驗的其他方面做的不是很好，還有待改進，例如：沒有考慮到斐波那契序列數(shù)據(jù)的數(shù)據(jù)類型，我用的是int這樣要輸出很大項的時候，int型的數(shù)據(jù)不夠。實驗二實驗名稱：《線性表》實驗?zāi)康呐c要求：熟悉如何使用單鏈表，掌握單鏈表的基本操作，鞏固對單鏈表知識的認識。實驗主要內(nèi)容：約瑟夫環(huán)。假設(shè)有n個編號為1，2，3，…，n的人按順時針方向圍坐一圈，每人持有一個密碼（正整數(shù)）。一開始任選一個正整數(shù)作為報數(shù)的上限值m，從第一個人開始按順時針方向自1開始順序報數(shù)，報到m時停止報數(shù)。報m的人出列，并將其密碼值作為新的m值，從他在順時針方向上的下一個人開始重新從1報數(shù)，以此類推下去，直到所有的人全部出列為止。試設(shè)計一個程序，可以在用戶確定了人數(shù)和密碼的情況下，求出對應(yīng)的出列順序。實驗中涉與的主要實驗原理：有n個編號為1，2，3，…，n的人按順時針方向圍坐一圈，每人持有一個密碼（正整數(shù)）。一開始任選一個正整數(shù)作為報數(shù)的上限值m，從第一個人開始按順時針方向自1開始順序報數(shù)，報到m時停止報數(shù)。報m的人出列，并將其密碼值作為新的m值，從他在順時針方向上的下一個人開始重新從1報數(shù)，以此類推下去，直到所有的人全部出列為止。概要設(shè)計和存儲結(jié)構(gòu)：該算法的實現(xiàn)用循環(huán)鏈表：structLNode{ intdata1;//data1存儲參加游戲者的編號 intdata2;//data2存儲參加游戲者的密碼 structLNode*next;//next為結(jié)點指針};主要算法：voidBuildGame(LinkList&L,intm,intk)｛//執(zhí)行游戲規(guī)則 p=(LinkList)malloc(sizeof(LNode)); p->next=L; for(i=0;i<k;i++)｛//參加游戲者為k人，所以循環(huán)k次后游戲結(jié)束 for(j=1;j<m;j++)//游戲規(guī)則：從第一個人開始報數(shù)，報到初始值m的人出列, p=p->next;//并將他的密碼作為下一個m值，依次循環(huán)，直到游戲結(jié)束 r=p->next; cout<<r->data1<<''; m=r->data2; p->next=r->next; p=r; }}實驗結(jié)果和結(jié)論：根據(jù)約瑟夫環(huán)的游戲規(guī)則，上述三個結(jié)果都正確。實驗分析：算法用到的是循環(huán)鏈表。在進行鏈表數(shù)據(jù)輸入的時候由于有兩個數(shù)據(jù)，所以要循環(huán)兩次，這樣輔助指針就比較多，后面執(zhí)行游戲規(guī)則的函數(shù)里也用到了比較多的輔助指針，用起來比較復(fù)雜，這個算法我感覺在這方面不太好，容易搞混淆。但是，當時能做到這里我感覺已經(jīng)不錯了。實驗三實驗名稱：《棧和隊》實驗?zāi)康呐c要求：熟悉對棧和隊的應(yīng)用,熟悉其基本操作。增強自己的動手能力和實驗?zāi)芰?。實驗主要?nèi)容：輸入一個十進制數(shù)（整數(shù)和小數(shù)）和進制數(shù)，要求程序輸出轉(zhuǎn)換后的數(shù)。例如，輸入5，再輸入進制數(shù)為2，則應(yīng)該輸出101。實驗中涉與的主要實驗原理：十進制數(shù)和其他進制數(shù)之間的轉(zhuǎn)換。整數(shù)部分為除進制數(shù)（如除2）取余最后逆置，小數(shù)部分為乘進制數(shù)取整，最后順序放置。概要設(shè)計和存儲結(jié)構(gòu)：本算法用了棧和隊兩類存儲結(jié)構(gòu)。其中，棧：typedefstruct{ int*base; int*top; intsize;}sqstack;用來存儲整數(shù)部分；隊：structQNode{ doubledata; structQNode*next;};typedefQNode*QueuePtr;typedefstruct{ QueuePtrfront; QueuePtrrear;}Linkqueue;用來存儲小數(shù)部分。主要算法：Statusjzzh(sqstack&s,Linkqueue&Q,SElemTypem,SElemTypen){//進制轉(zhuǎn)換，包含整數(shù)部分和小數(shù)部分的轉(zhuǎn)換 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;}實驗四實驗名稱：《二叉樹》實驗?zāi)康呐c要求：熟悉對二叉樹的應(yīng)用,熟悉其各種遍歷的基本規(guī)則，了解樹的創(chuàng)建的基本原理。增強自己的動手能力和實驗?zāi)芰?。實驗主要?nèi)容：創(chuàng)建一顆二叉樹，對其進行先序、中序、后序遍歷以與其他操作。概要設(shè)計和存儲結(jié)構(gòu)：typedefstructBiTNode{ TElemTypedata;//數(shù)據(jù)域 structBiTNode*lchild,*rchild;//指向左右孩子的指針lchild,rchild}BiTNode,*BiTr主要算法：StatusPreOrderTraverse(BiTreeT){//先序遍歷 if(T){//判斷二叉樹是否為空 cout<<T->data;//訪問Data PreOrderTraverse(T->lchild);//遞歸遍歷左子樹 PreOrderTraverse(T->rchild);//遞歸遍歷右子樹 } returnOK;}StatusInOrderTraverse(BiTreeT){//中序遍歷 if(T){//判斷二叉樹是否為空 InOrderTraverse(T->lchild);//遞歸遍歷左子樹 cout<<T->data; InOrderTraverse(T->rchild);//遞歸遍歷右子樹 } returnOK;}StatusPostOrderTraverse(BiTreeT){//后序遍歷 if(T){//非空二叉樹 PostOrderTraverse(T->lchild);//遞歸遍歷左子樹 PostOrderTraverse(T->rchild);//遞歸遍歷右子樹 cout<<T->data; } returnOK;}intCountNode(BiTreeT){//統(tǒng)計結(jié)點總數(shù) if(T) return1+CountNode(T->lchild)+CountNode(T->rchild);//遞歸遍歷左右子樹，每過一個結(jié)點 else//加，最后加上根結(jié)點 return0;}intCountLeaf(BiTreeT){//統(tǒng)計葉子總數(shù) if(T){ if(!T->lchild&&!T->rchild) return1; else returnCountLeaf(T->lchild)+CountLeaf(T->rchild); } else return0;}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;}實驗結(jié)果和結(jié)論：由于在該程序中，加了一個可選擇菜單，因此，該程序的執(zhí)行是一直連續(xù)的，如上圖，執(zhí)行順序是從左到右，從上到下。首先，先序創(chuàng)建二叉樹為：ABC$$D$$EF$G$$$($代表空格),由于是先序創(chuàng)建，所以先序遍歷的結(jié)果也是ABCDEFG，因此第一個結(jié)果正確；打一鍵繼續(xù)后選擇后序遍歷，如圖所示二叉樹，后序遍歷的結(jié)果為CDBGFEA,因此第二個結(jié)果正確；由輸入的字母數(shù)可知第三個結(jié)果也是正確的；后面兩個結(jié)果都是判斷輸入的合法性，并且都判斷正確。ABECDFG實驗分析：本次所做的實驗難度不是很高，同時我認為該實驗的創(chuàng)建二叉樹算法并不是很好，因為只有保證輸入空格的數(shù)量和位置絕對正確才能保證創(chuàng)建函數(shù)的結(jié)束，否則將無法繼續(xù)。而且這里無法判斷輸入的合法性。實驗五實驗名稱：《查找和排序》實驗?zāi)康呐c要求：學(xué)習(xí)和掌握排序和查找這兩個計算機程序設(shè)計中的重要操作。加強自己的動手能力和錯誤分析能力。實驗主要內(nèi)容：選擇一種查找和排序算法，實現(xiàn)查找造和排序。概要設(shè)計和存儲結(jié)構(gòu)：本程序中用到了順序表存儲結(jié)構(gòu)和兒茶鏈表存儲結(jié)構(gòu)，兩種結(jié)構(gòu)的作用為：順序表用來存儲順序查找表；二叉鏈表用來存儲次優(yōu)查找樹。//順序表的順序存儲表示typedefstruct{ charkey; intweight;}ElemType;typedefstruct{ ElemType*elem; intlength; }SSTable;//二叉樹的二叉鏈表存儲表示typedefstructBiTNode{ ElemTypedata; structBiTNode*lchild,*rchild;}BiTNode,*BiTree;主要算法：//重建靜態(tài)查找表為按關(guān)鍵字非降序排序。voidShellInsert(SSTable&L,intdk){for(i=dk+1;i<=L.length;++i)if(LT(L.elem[i].key,L.elem[i-dk].key)){//需將L.r[i]插入有序增量子表L.elem[0]=L.elem[i];//暫存在L.r[0]for(j=i-dk;j>0&<(L.elem[0].key,L.elem[j].key);j-=dk)L.elem[j+dk]=L.elem[j];//記錄后移，查找插入位置L.elem[j+dk]=L.elem[0];//插入}}//ShellIn//由有序表R[low..high]與其累計權(quán)值表sw(其中sw[0]==0)遞歸構(gòu)造//次優(yōu)查找樹T。intSecondOptimal(BiTree&T,ElemTypeR[],intsw[],intlow,inthigh){ min=abs(sw[high]-sw[low]); //fabs函數(shù)是求絕對值的 dw=sw[high]+sw[low-1]; for(j=low+1;j<=high;++j)//選擇最小的△Pi值 if(fabs(dw-sw[j]-sw[j-1])<min){ i=j; min=fabs(dw-sw[j]-sw[j-1]); } T=(BiTree)malloc(sizeof(BiTNode)); if(!T) return0; T->data=R[i];//生成結(jié)點 if(i==low) T->lchild=NULL;//左子樹空 else SecondOptimal(T->lchild,R,sw,low,i-1);//構(gòu)造左子樹 if(i==high) T->rchild=NULL;//右子樹空 el