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