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

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