課程設計實驗報告

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

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

3、課程設計題目及分析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、設計總結(jié)樹和二叉樹之層序遍歷二叉樹中的先序遍歷、中序遍歷、后序遍歷、層序遍歷均采用遞歸算法，而構(gòu)建二叉樹時也采用的是遞歸算法。在層序遍歷中采用隊列的入隊進隊的方法從而實現(xiàn)層序遍歷二叉樹。本次實驗通過九個函數(shù)分別多二叉樹進行先序、中序、后序以及層序四種遍歷操作，層序遍歷開始沒有得到預

6、想結(jié)果，原來是自己寫程序不夠謹慎，沒有在層序遍歷中寫相應的輸出語句，另外，在創(chuàng)建隊列時由于自己的粗心大意，沒有很好將空間分配控制語句完善好，最后導致層序遍歷結(jié)果輸出，經(jīng)多次仔細觀察才返現(xiàn)。2、題目二背包問題2.1、問題描述假設有一個能夠裝入總體積為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)提示可利用回溯法的設計思想來解決背包問題。首先

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

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

9、沒有物體可以作為參數(shù)入?；虺鰲Ａ耍醒h(huán)結(jié)束。本算法采用3重while循環(huán)嵌套來實現(xiàn)算出所有不重復的解2.4、運行結(jié)果分析2.5、設計總結(jié)主要是要考慮到用棧和回溯的思想，定義循環(huán)進行回溯。當然，這也用到順序棧，首先進行判斷輸入時否正確。在用到循環(huán)實現(xiàn)每一次的回溯，找出所有的結(jié)果。3、題目三學生成績分析系統(tǒng)3.1、問題描述錄入、保存一個班級學生的多門課程的成績，并對成績進行分析。3.2、基本要求（1）通過鍵盤輸入各學生的多門課程的成績，建立相應的數(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窗體應用程序，將管理系統(tǒng)界面可視化，利用控件的相互關聯(lián)實現(xiàn)對系統(tǒng)的操作，利用sql server數(shù)據(jù)庫來對學生信息的保存，通過dataset將數(shù)據(jù)庫與窗體應用程序相互連接起來，在窗體上實現(xiàn)對數(shù)據(jù)庫中學生信息的操作，并將其更新到數(shù)據(jù)庫中。3.4、運行結(jié)果分析添加學生信息界面：學生成績信息瀏覽、修改：平均成績分析界面：按線性代數(shù)降序排列后的結(jié)果：3.5、設計總結(jié)學生成績管理系統(tǒng)是基于c# window窗

11、體應用開發(fā)的程序，在編寫的過程要用到數(shù)據(jù)庫，最大的難度是在window窗體應用程序與數(shù)據(jù)庫之間的連接問題，在連接字符串上，必需正確的寫好連接字符串的服務器名稱和數(shù)據(jù)庫的名稱。在窗體設計過程中，必須將窗體界面設計的美觀和人性化，每個控件的使用必須合理。最大的難度是在將數(shù)據(jù)庫的信息顯示到window窗體中時，必須將數(shù)據(jù)重新處理一遍，這需要datagridview1控件的使用，而這個控件的最大難度就是就將數(shù)據(jù)庫的表返回顯示到其中。4、 題目四 一元稀疏多項式簡單計算器4.1、問題描述 設計一個一元稀疏多項式簡單計算器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ù)就應該相加；相加的和不為0的話，用頭插法建立一個新的節(jié)點。 p的系數(shù)小于q的系數(shù)的話，就應該復制q接點到多項式中。p的系數(shù)大于q的系數(shù)的話，就應該復制p接點到多項式中。當?shù)?個多項式空，第1個數(shù)不為空時，將第一個數(shù)剩下的全用新節(jié)點產(chǎn)生。當?shù)?個多項式空，第1個數(shù)不為空時，將第2個數(shù)剩下的全用新節(jié)點產(chǎn)生 d：2個多項式的減法 它從2個多項式的頭部開始，2個多項式的某一項都不為空時，如果指數(shù)相等的話，系數(shù)就應該相減；相加的

14、和不為0的話，用頭插法建立一個新的節(jié)點。 p的系數(shù)小于q的系數(shù)的話，就應該復制q接點到多項式中。p的系數(shù)大于q的系數(shù)的話，就應該復制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、設計總結(jié)應該創(chuàng)建鏈表，用以表示多項式的每一項，其中鏈表中有表示x系數(shù)的c和指數(shù)e，以及指向下一個結(jié)點的ne

15、xt指針域，用數(shù)字1，2來表示是否是加或者減。采用冒泡排序，按指數(shù)的大小進行排序最后輸出。在設計當中必須要進行多次判斷，首先就要判斷輸入的只是否相等，相等的才能夠進行加減運算；其次還要判斷是否含有這項指數(shù)的系數(shù)，沒有就直接復制到先得聊表中去，最后輸出。三、附錄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