課程設(shè)計(jì)實(shí)驗(yàn)報(bào)告

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

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

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

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

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

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

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

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

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

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

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

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

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

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

15、xt指針域，用數(shù)字1，2來(lái)表示是否是加或者減。采用冒泡排序，按指數(shù)的大小進(jìn)行排序最后輸出。在設(shè)計(jì)當(dāng)中必須要進(jìn)行多次判斷，首先就要判斷輸入的只是否相等，相等的才能夠進(jìn)行加減運(yùn)算；其次還要判斷是否含有這項(xiàng)指數(shù)的系數(shù)，沒(méi)有就直接復(fù)制到先得聊表中去，最后輸出。三、附錄1、源程序清單及結(jié)果1.1、題目一：二叉排序樹(shù)于平衡二叉樹(shù)的實(shí)現(xiàn)源程序清單：/ 二叉排序樹(shù)與平衡二叉樹(shù)的實(shí)現(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插入到二叉排序樹(shù)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)建二叉樹(shù)dnode * ht;int x;ht=(dnode *)malloc(sizeof(dnode);printf(創(chuàng)建二叉樹(shù):);scanf(%d,&x);ht-data=x;n+;ht-left=ht-right=null; /先將二叉樹(shù)的初始結(jié)點(diǎn)全部置為空scanf(%d,&x);w

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

19、址給a0，其父結(jié)點(diǎn)的地址給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é)點(diǎn)是否相等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é)點(diǎn)dnode *

20、p,* q,* s,* f,* a2;int flag=0,x;p=(dnode *)malloc(sizeof(dnode);f=(dnode *)malloc(sizeof(dnode);printf(請(qǐng)輸入x的值:);scanf(%d,&x);find(t,x,a);p=a0;f=a1;if(p=null) /當(dāng)遍歷到最后也沒(méi)有該結(jié)點(diǎn)元素時(shí)printf(沒(méi)有該結(jié)點(diǎn)數(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é)點(diǎn)后標(biāo)記為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、題目二：背包問(wèn)題源程序清單：/ stdafx.cpp : source file that includes just the standard includes/背包問(wèn)題.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請(qǐng)輸入選擇的物品的數(shù)目：);scanf(%d,&n);printf(n請(qǐng)輸入選擇的物品的體積n);for(i=0;in;i+)printf(n第%d個(gè)物品的體積為：,i+1);scanf(%d,&wi);printf(n請(qǐng)輸入背包最大容量：);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 /*當(dāng)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