課程設(shè)計實驗報告

1、數(shù)據(jù)結(jié)構(gòu) 課程設(shè)計課程設(shè)計成績總評成績指導(dǎo)老師簽名 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告學(xué)院（系）： 計算機科學(xué)與工程學(xué)院 班 級： 112030901 學(xué)生姓名: 余錢 學(xué)號：11203090136 指導(dǎo)教師： 何波 傅由甲時間：從 2014 年 1 月 6 日到 2014 年 1 月 12日目錄一、課程設(shè)計概述2二、課程設(shè)計題目及分析21、題目一21.1、問題描述21.2、基本要求21.3、系統(tǒng)分析31.4、運行結(jié)果分析31.5、設(shè)計總結(jié)32、題目二42.1、問題描述42.2、實現(xiàn)提示42.3、系統(tǒng)分析42.4、運行結(jié)果分析52.5、設(shè)計總結(jié)53、題目三63.1、問題描述63.2、基本要求63.3、系統(tǒng)分

2、析63.4、運行結(jié)果分析63.5、設(shè)計總結(jié)94、 題目四94.1、問題描述94.2、基本要求94.3、系統(tǒng)分析104.4、運行結(jié)果分析104.5、設(shè)計總結(jié)11三、附錄111、源程序清單及結(jié)果111.1、題目一：111.2、題目二：151.3、題目三：171.4、題目四：22四、參考文獻27五、課程設(shè)計心得27一、課程設(shè)計概述本次課程設(shè)計共完成4個題目： 1、二叉排序樹于平衡二叉樹的實現(xiàn) 2、背包問題 3、學(xué)生成績分析系統(tǒng) 4、一元稀疏多項式簡單計算器c語言 c#語言編譯環(huán)境：vc 6.0 microsoft visual studio2010 數(shù)據(jù)庫（sql server 2008 r2）二、

3、課程設(shè)計題目及分析1、題目一二叉排序樹于平衡二叉樹的實現(xiàn)1.1、問題描述分別采用二叉鏈表和順序表作存儲結(jié)構(gòu)，實現(xiàn)對二叉排序樹與平衡二叉樹的操作1.2、基本要求（1）用二叉鏈表作存儲結(jié)構(gòu)。1）以回車（n）為輸入結(jié)束標志，輸入數(shù)列l(wèi)，生成一棵二叉排序樹t；2）對二叉排序樹t作中序遍歷，輸出結(jié)果；3）計算二叉排序樹t查找成功的平均長度，輸出結(jié)果；4）輸入元素x，查找二叉排序樹t，若存在含x的結(jié)點，則刪除該結(jié)點，并作中序遍歷圖；否則，輸出信息“無x”；5）用數(shù)列l(wèi)，生成平衡的二叉排序樹bt；當插入新元素之后，發(fā)現(xiàn)當前的二叉排序樹bt不是平衡二叉排序樹，則立即將它轉(zhuǎn)換成新的平衡的二叉排序樹bt6）計算平

4、衡的二叉排序樹bt的平均查找長度，輸出結(jié)果。（2）用順序表（一位數(shù)組）作存儲結(jié)構(gòu)。1）以回車（n）為輸入結(jié)束標志，輸入數(shù)列l(wèi)，生成一棵二叉排序樹t；2）對二叉排序樹t作中序遍歷，輸出結(jié)果3）計算二叉排序樹t查找成功的平均長度，輸出結(jié)果；4）輸入元素x，查找二叉排序樹t，若存在含x的結(jié)點，則刪除該結(jié)點，并作中序遍歷圖；否則，輸出信息“無x”；1.3、系統(tǒng)分析按先根序序列建立二叉樹的二叉鏈表，在遍歷二叉樹的時候執(zhí)行一個遞歸程序，需要借助棧的作用，因此可以直接使用棧；在查找二叉樹結(jié)點的過程中，按照遍歷的順序?qū)⒚總€結(jié)點遍歷一遍與輸入的值進行比較。用順序表做存儲結(jié)構(gòu)的時候，用帶頭節(jié)點的單鏈表來標明二叉樹

5、的雙親和左右孩子結(jié)點的位置，以便遍歷，遍歷過程中，則按照先后次序遍歷二叉樹的各個結(jié)點。1.4、運行結(jié)果分析測試數(shù)據(jù)：5 6 4 3 2 1 4 0 /0輸入的作為結(jié)束符中序遍歷結(jié)果：1 2 3 4 5 6結(jié)點個數(shù)：6 樹的深度：28 平均長度：4.67輸入查找的元素：5刪除輸入元素后的結(jié)果：1 2 3 4 61.5、設(shè)計總結(jié)樹和二叉樹之層序遍歷二叉樹中的先序遍歷、中序遍歷、后序遍歷、層序遍歷均采用遞歸算法，而構(gòu)建二叉樹時也采用的是遞歸算法。在層序遍歷中采用隊列的入隊進隊的方法從而實現(xiàn)層序遍歷二叉樹。本次實驗通過九個函數(shù)分別多二叉樹進行先序、中序、后序以及層序四種遍歷操作，層序遍歷開始沒有得到預(yù)

6、想結(jié)果，原來是自己寫程序不夠謹慎，沒有在層序遍歷中寫相應(yīng)的輸出語句，另外，在創(chuàng)建隊列時由于自己的粗心大意，沒有很好將空間分配控制語句完善好，最后導(dǎo)致層序遍歷結(jié)果輸出，經(jīng)多次仔細觀察才返現(xiàn)。2、題目二背包問題2.1、問題描述假設(shè)有一個能夠裝入總體積為t的背包和n件體積分別為w1，w2，w3.wn。的物品，能否從n件物品中挑選出若干件恰好裝滿背包，即使w1+w2+w3+.+wn=t要求找出所有滿足條件的解。例如：當t等于10，各件物品的體積1，8，4，3，5，2時，可以找到下列四組解：（1，4，3，2）（1，4，5）（8，2）（3，5，2）2.2、實現(xiàn)提示可利用回溯法的設(shè)計思想來解決背包問題。首先

7、，將物品排成一列，然后，順序選取物品裝入背包，若已選取第i件物品后未滿，則繼續(xù)選取第i+1件，若該件物品“太大”不能裝入，則棄之，繼續(xù)選取下一件，直至背包裝滿為止。如果在剩余的物品中找不到合適的物品以填滿背包，則說明“剛剛”裝入的物品“不合適”，應(yīng)將它取出“棄之一邊”，繼續(xù)再從“它之后”的物品中選取，如此重復(fù)，直到求得滿足條件的解，或者無解。由于回溯求解的規(guī)則是“后進先出”，自然要用到“?！?。進一步考慮：如果每件物品都有體積和價值，背包又有大小限制，求解背包中存放物品總價值最大的問題解-最優(yōu)解或近似最優(yōu)解。2.3、系統(tǒng)分析本算法采用先進后出的算法來一個一個測試可行的全部解，所以很顯然要用到棧。

8、我通過建立順序表來錄入我要輸入的各個物體的體積，然后通過結(jié)構(gòu)體類型定義棧，把順序表中的各個物體逐一入棧，如果各物體體積總和sum比我預(yù)定的目標體積小，那就繼續(xù)入棧，有合適的組合則輸出，否則說明剛才選入的物體體積即棧最頂端的那個不適合導(dǎo)致后面沒有合適的解，所以把它pop掉，然后從它后面繼續(xù)選取所要考察的物體體積。當?shù)谝粋€物體做棧底的所有情況滿足后，我們就要考慮以第二個物體為棧底的情況，其實我并沒有把第一個物體出棧，只是我讀的時候把第一個物體“屏蔽”了，也就是說它雖然在棧中，但是我不考慮它，而是考慮新的棧也就是總棧中截取的我需要的那部分目標棧段，依次類推，當順序表中所有物體都做過“棧底”后，那么就

9、沒有物體可以作為參數(shù)入?；虺鰲Ａ?，所有循環(huán)結(jié)束。本算法采用3重while循環(huán)嵌套來實現(xiàn)算出所有不重復(fù)的解2.4、運行結(jié)果分析2.5、設(shè)計總結(jié)主要是要考慮到用棧和回溯的思想，定義循環(huán)進行回溯。當然，這也用到順序棧，首先進行判斷輸入時否正確。在用到循環(huán)實現(xiàn)每一次的回溯，找出所有的結(jié)果。3、題目三學(xué)生成績分析系統(tǒng)3.1、問題描述錄入、保存一個班級學(xué)生的多門課程的成績，并對成績進行分析。3.2、基本要求（1）通過鍵盤輸入各學(xué)生的多門課程的成績，建立相應(yīng)的數(shù)據(jù)庫；（2）對數(shù)據(jù)庫中的數(shù)據(jù)進行處理，要求具有如下功能：1）按各門成績排序；2）計算每人的平均成績，按平均成績排序；3）求出各門課程的平均成績、最高

10、分、最低分、不及格人數(shù)、6069分人數(shù)，7079分人數(shù)，8089分人數(shù)，90分以上人數(shù)。4）根據(jù)姓名或?qū)W號查詢某人的各門課成績，重名情況也能處理（3）界面美觀3.3、系統(tǒng)分析利用c#中的window窗體應(yīng)用程序，將管理系統(tǒng)界面可視化，利用控件的相互關(guān)聯(lián)實現(xiàn)對系統(tǒng)的操作，利用sql server數(shù)據(jù)庫來對學(xué)生信息的保存，通過dataset將數(shù)據(jù)庫與窗體應(yīng)用程序相互連接起來，在窗體上實現(xiàn)對數(shù)據(jù)庫中學(xué)生信息的操作，并將其更新到數(shù)據(jù)庫中。3.4、運行結(jié)果分析添加學(xué)生信息界面：學(xué)生成績信息瀏覽、修改：平均成績分析界面：按線性代數(shù)降序排列后的結(jié)果：3.5、設(shè)計總結(jié)學(xué)生成績管理系統(tǒng)是基于c# window窗

11、體應(yīng)用開發(fā)的程序，在編寫的過程要用到數(shù)據(jù)庫，最大的難度是在window窗體應(yīng)用程序與數(shù)據(jù)庫之間的連接問題，在連接字符串上，必需正確的寫好連接字符串的服務(wù)器名稱和數(shù)據(jù)庫的名稱。在窗體設(shè)計過程中，必須將窗體界面設(shè)計的美觀和人性化，每個控件的使用必須合理。最大的難度是在將數(shù)據(jù)庫的信息顯示到window窗體中時，必須將數(shù)據(jù)重新處理一遍，這需要datagridview1控件的使用，而這個控件的最大難度就是就將數(shù)據(jù)庫的表返回顯示到其中。4、 題目四 一元稀疏多項式簡單計算器4.1、問題描述 設(shè)計一個一元稀疏多項式簡單計算器4.2、基本要求一元稀疏多項式簡單計算器的基本功能是：（1） 輸入并建立多項式；（2

12、） 輸出多項式，輸出形式為整數(shù)數(shù)列：n，c1，e1，c2，e2，.，cn，en,其中n是多項式的項數(shù)，ci，ei分別是第i項的系數(shù)和指數(shù)，序列按指數(shù)降序列排序；（3） 多項式a和b相加，建立多項式a+b；（4） 多項式a和b相減，建立多項式a-b；（5） 計算多項式在x處的值；（6） 計算器的仿真界面（選做）。4.3、系統(tǒng)分析a：數(shù)據(jù)結(jié)構(gòu)的選用 為了實現(xiàn)任意多項式的加法，減法，因此選擇單鏈表的結(jié)構(gòu)體，它有一個系數(shù)，指數(shù)，下一個指針3個元屬； b：多項式的輸入 采用頭插法的方式，輸入多項式中一個項的系數(shù)和指數(shù)，就產(chǎn)生一個新的節(jié)點，建立起它的右指針，并用頭節(jié)點指向它；為了判斷一個多項式是否輸入結(jié)束

13、，定義一個結(jié)束標志，當輸入非0時就繼續(xù)，當輸入0時，就結(jié)束一個多項式的輸入； c：2個多項式的加法 它從2個多項式的頭部開始，2個多項式的某一項都不為空時，如果指數(shù)相等的話，系數(shù)就應(yīng)該相加；相加的和不為0的話，用頭插法建立一個新的節(jié)點。 p的系數(shù)小于q的系數(shù)的話，就應(yīng)該復(fù)制q接點到多項式中。p的系數(shù)大于q的系數(shù)的話，就應(yīng)該復(fù)制p接點到多項式中。當?shù)?個多項式空，第1個數(shù)不為空時，將第一個數(shù)剩下的全用新節(jié)點產(chǎn)生。當?shù)?個多項式空，第1個數(shù)不為空時，將第2個數(shù)剩下的全用新節(jié)點產(chǎn)生 d：2個多項式的減法 它從2個多項式的頭部開始，2個多項式的某一項都不為空時，如果指數(shù)相等的話，系數(shù)就應(yīng)該相減；相加的

14、和不為0的話，用頭插法建立一個新的節(jié)點。 p的系數(shù)小于q的系數(shù)的話，就應(yīng)該復(fù)制q接點到多項式中。p的系數(shù)大于q的系數(shù)的話，就應(yīng)該復(fù)制p接點到多項式中，并且建立的接點的系數(shù)為原來的相反數(shù)；當?shù)?個多項式空，第1個數(shù)不為空時，將第一個數(shù)剩下的全用新節(jié)點產(chǎn)生。當?shù)?個多項式空，第1個數(shù)不為空時，將第2個數(shù)剩下的全用新節(jié)點產(chǎn)生，并且建立的接點的系數(shù)為原來的相反數(shù)。4.4、運行結(jié)果分析測試多項式：（2x+5x8-3.1x11）+(7-5x8+11x9)=(-3.1x11+11x9+2x+7)4.5、設(shè)計總結(jié)應(yīng)該創(chuàng)建鏈表，用以表示多項式的每一項，其中鏈表中有表示x系數(shù)的c和指數(shù)e，以及指向下一個結(jié)點的ne

15、xt指針域，用數(shù)字1，2來表示是否是加或者減。采用冒泡排序，按指數(shù)的大小進行排序最后輸出。在設(shè)計當中必須要進行多次判斷，首先就要判斷輸入的只是否相等，相等的才能夠進行加減運算；其次還要判斷是否含有這項指數(shù)的系數(shù)，沒有就直接復(fù)制到先得聊表中去，最后輸出。三、附錄1、源程序清單及結(jié)果1.1、題目一：二叉排序樹于平衡二叉樹的實現(xiàn)源程序清單：/ 二叉排序樹與平衡二叉樹的實現(xiàn).cpp : defines the entry point for the console application./#include stdafx.h#include stdio.h#include malloc.h#inclu

16、de stdlib.h#define null 0#define maxsize 100typedef struct nodeint data; /數(shù)據(jù)域struct node * left, * right; /*left指向左孩子，*right 指向右孩子dnode;int n,m,total;void sort(dnode *t,int c) /將c插入到二叉排序樹t中dnode * p;if(c=t-data)if(t-right=null)p=(dnode *)malloc(sizeof(dnode);p-data=c;p-left=p-right=null;t-right=p;el

17、se sort(t-right,c);if(cdata)if(t-left=null)p=(dnode *)malloc(sizeof(dnode);p-data=c;p-left=p-right=null;t-left=p;else sort(t-left,c); dnode * creat() /創(chuàng)建二叉樹dnode * ht;int x;ht=(dnode *)malloc(sizeof(dnode);printf(創(chuàng)建二叉樹:);scanf(%d,&x);ht-data=x;n+;ht-left=ht-right=null; /先將二叉樹的初始結(jié)點全部置為空scanf(%d,&x);w

18、hile(x0) /0作為結(jié)尾sort(ht,x);n+;scanf(%d,&x); return ht;void inorder(dnode * t) /中序遍歷二叉排序樹if(t!=null)m+;inorder(t-left);printf(%d,t-data);total+=m;inorder(t-right);void asl() /計算平均長度float w;w=(float)total/n;printf(結(jié)點個數(shù)為:%d,數(shù)的深度:%d,平均長度:%3.2fn,n,total,w);void find(dnode * b,int x,dnode * a) /將數(shù)據(jù)域為x的結(jié)點的地

19、址給a0，其父結(jié)點的地址給a1dnode * stackmaxsize,*p;int top;a1=null;if(b!=null)top=1;stacktop=b;while(top0)p=stacktop;top-;if(p-left-data=x|p-right-data=x) /查找兩結(jié)點是否相等a1=p;if(p-data=x)a0=p;return;if(p-right!=null)top+;stacktop=p-right;if(p-left!=null)top+;stacktop=p-left;a0=p;dnode * del(dnode *t) /刪除 x結(jié)點dnode *

20、p,* q,* s,* f,* a2;int flag=0,x;p=(dnode *)malloc(sizeof(dnode);f=(dnode *)malloc(sizeof(dnode);printf(請輸入x的值:);scanf(%d,&x);find(t,x,a);p=a0;f=a1;if(p=null) /當遍歷到最后也沒有該結(jié)點元素時printf(沒有該結(jié)點數(shù)據(jù));exit(0);if(p-left=null)s=p-right;else if(t-right=null)s=p-left;elseq=p;s=q-left;while(s-right!=null)q=s;s=s-ri

21、ght;if(q=p) /找到后執(zhí)行刪除操作q-left=s-right;elseq-right=s-left;p-data=s-data;free(s);flag=1; /找到結(jié)點后標記為1if(flag=0)if(f=null)t=s;else if(f-left=p)f-left=s;elsef-right=s;return t;int main(int argc, char* argv)dnode * h;n=m=total=0;h=creat();printf(中序遍歷結(jié)果為 :);inorder(h);printf(n);asl();h=del(h);inorder(h);getc

22、har();return 0;1.2、題目二：背包問題源程序清單：/ stdafx.cpp : source file that includes just the standard includes/背包問題.pch will be the pre-compiled header/stdafx.obj will contain the pre-compiled type information#include stdafx.h#include#define m 100int main()int wm;int t=0;int n=0;int k=0;int i=0;int j=1;struct

23、int sm;int top;things;printf(n請輸入選擇的物品的數(shù)目：);scanf(%d,&n);printf(n請輸入選擇的物品的體積n);for(i=0;in;i+)printf(n第%d個物品的體積為：,i+1);scanf(%d,&wi);printf(n請輸入背包最大容量：);scanf(%d,&t);for(i=0;i0&k=wk)things.sthings.top+=k;/入棧操作t-=wk;k+;if(t=0)printf(n第%d種挑選方法（ ,j );for(i=0;inext=null;do /*當n小于1，則重新輸入*/printf(enter n:);scanf(%d,&n);while(n1);for(i=1;ic=c;p-e=e;p-next=h-next;/*用頭插法建立鏈表*/h-next=p;return