數(shù)據(jù)結(jié)構(gòu)課程設(shè)計二叉連鏈表.doc
《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計二叉連鏈表.doc》由會員分享,可在線閱讀,更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計二叉連鏈表.doc(14頁珍藏版)》請在裝配圖網(wǎng)上搜索。
1、 課程設(shè)計指導(dǎo)書 姓 名 學(xué) 號 班 級 課程名稱 數(shù)據(jù)結(jié)構(gòu) 課程性質(zhì) 專業(yè)必修課 設(shè)計時間 2010 年 12 月 1日—— 2010 年 12月 20日 設(shè)計名稱 設(shè)計二叉鏈表結(jié)構(gòu)的相關(guān)函數(shù)庫 設(shè)計目的 使用Microsoft Visual C++ 設(shè)計二叉鏈表結(jié)構(gòu)的相關(guān)函數(shù)庫,并能夠在程序設(shè)計中調(diào)用 設(shè)計要求 設(shè)計二叉鏈表結(jié)構(gòu)的相關(guān)函數(shù)庫,以便在程序設(shè)計中調(diào)用,實現(xiàn)二叉樹的各種基本函數(shù)以及常用函數(shù);并給出1-2個例子,通過調(diào)用自己的庫函數(shù)來實現(xiàn)問題的求解。 設(shè)計思路 與 設(shè)計過程 1. 程序需求分析 完成:根據(jù)需求分析,確定
2、各個程序功能的需求; 2. 程序總統(tǒng)設(shè)計 完成:根據(jù)程序需求,進行程序大概框架的設(shè)計; 3. 主函數(shù)設(shè)計 完成:主函數(shù)程序中設(shè)計一個菜單,并調(diào)試所用算法; 4. 其他函數(shù)設(shè)計 完成:建立二叉鏈表以及遞歸序列遍歷算法 5. 系統(tǒng)程序完善 完成:完善整個程序細節(jié)代碼的要求,進行調(diào)試。 計劃與進度 12.1-12.2 復(fù)習(xí)對vc++6.0使用,了解關(guān)于二叉鏈表的相關(guān)特征等。 12.3-12.4 查找有關(guān)二叉鏈表基本操作的算法等。 12.5-12.7 根據(jù)需求分析,確立各個函數(shù)程序功能。 12.8-12.10 根據(jù)程序需求,進行相關(guān)子函數(shù)
3、程序的編寫。 12.11-12.13 進行主函數(shù)程序功能的設(shè)計編寫。 12.14-12.16 進行對整個程序的完善。 12.17-12.18 進行程序的調(diào)試運行。 12.19-12.20 資料歸檔,填寫相關(guān)文檔。 任課教師 意 見 備 注 課程設(shè)計報告 課程: 學(xué)號: 姓名: 班級: 教師 時間: 計算機科學(xué)與技術(shù)系 設(shè)計名稱: 設(shè)計二叉鏈表的相關(guān)函數(shù)庫 日期:2010年 12 月 20 日 設(shè)計內(nèi)容:使用Microsoft Visual C++ 設(shè)計二
4、叉鏈表結(jié)構(gòu)的相關(guān)函數(shù)庫,以便在程序設(shè)計中調(diào)用 設(shè)計目的與要求:設(shè)計二叉鏈表結(jié)構(gòu)的相關(guān)函數(shù)庫,在程序設(shè)計中調(diào)用,并實現(xiàn)二叉樹的各種基本函數(shù)以及常用函數(shù)。 設(shè)計環(huán)境或器材、原理與說明: 器材:計算機一臺 硬件環(huán)境: 處理器:Intel core i3 內(nèi)存: 1GB 硬盤空間:320GB 顯卡:ATI Mobility Radeon 軟件環(huán)境: Windows XP,Microsoft Visual C++6.0 使用數(shù)據(jù)結(jié)構(gòu)設(shè)計的一般方法步驟進行設(shè)計。 設(shè)計過程(步驟)和部分程序代碼(可以加頁): 一. 題目要求 設(shè)計二叉鏈表結(jié)構(gòu)的相關(guān)函數(shù)庫,在程序設(shè)計
5、中調(diào)用,并實現(xiàn)二叉樹的各種基本函數(shù)以及常用函數(shù)。 二. 需求分析 建立一棵二叉樹: (1)二叉樹的鏈表結(jié)構(gòu); (2)進行先序遍歷,輸出結(jié)果; (3)進行中序遍歷,輸出結(jié)果; (4)進行后序遍歷,輸出結(jié)果; (5)進行層次遍歷,輸出結(jié)果。 三. 運行環(huán)境 Windows XP 四. 開發(fā)工具和編程語言 1.開發(fā)工具:Microsoft Visual C++6.0 2.編程語言:C語言 五. 概要設(shè)計 1. 數(shù)據(jù)結(jié)構(gòu) typedef char datatype; typedef struct node //定
6、義二叉樹結(jié)點類型 { datatype data; struct node *lchild; struct node *rchild; }Btnode,* Btree; 2.模塊劃分 1.根據(jù)先序遞歸建立二叉樹 Btree pre_creat() 2.遞歸遍歷輸出函數(shù) void preorder_btree(Btree root) //由先根序列遍歷輸出二叉樹 void inorder_btree(Btree root) //由中根序列遍歷輸出二叉樹 void postorder_btree(Btree ro
7、ot) //由后根序列遍歷輸出二叉樹 3.層次遍歷輸出算法 void level_btree(Btree root) //層次遍歷輸出二叉樹 六. 詳細設(shè)計 1.創(chuàng)建二叉樹的實現(xiàn) Btree pre_creat() //使用先根序列建立二叉樹,返回指針 { Btree t; char ch; fflush(stdin); scanf("%c",&ch); //輸入一個結(jié)點數(shù)據(jù) if(ch==@) return NULL; //空結(jié)點 else { t=(Btnode *)m
8、alloc(sizeof(Btnode)); //申請結(jié)點空間,根節(jié)點 t->data=ch; t->lchild=pre_creat(); //生成左子樹 t->rchild=pre_creat(); //生成右子樹 } return t; } 2.先序、中序、后序遞歸遍歷輸出算法 void preorder_btree(Btree root) //由先根序列輸出二叉樹 { Btree p=root; if(p!=NULL) { printf("%3c",p->data); //輸出結(jié)點值
9、 preorder_btree(p->lchild); //輸出左子樹 preorder_btree(p->rchild); //輸出右子樹 } } void inorder_btree(Btree root) //由中根序列輸出二叉樹 { Btree p=root; if(p!=NULL) { inorder_btree(p->lchild); //輸出左子樹 printf("%3c",p->data); //輸出結(jié)點值 inorder_btree(p->rchild); //輸出右子樹 } }
10、void postorder_btree(Btree root) //由后根序序列輸出二叉樹 { Btree p=root; if(p!=NULL) { postorder_btree(p->lchild); //輸出左子樹 postorder_btree(p->rchild); //輸出右子樹 printf("%3c",p->data); //輸出結(jié)點值 } } 3.層次遍歷輸出算法 void level_btree(Btree root) //層次遍歷輸出二叉樹 {
11、 Btree p; p=(Btnode *)malloc(sizeof(Btnode)); //申請一個新結(jié)點 p->data=@; p->lchild=p->rchild=NULL; //為新結(jié)點賦初值 int front, rear; front=rear=0; //置空隊列 p=root; //工作結(jié)點指向根節(jié)點 if(p!=NULL) { rear ++; Q[rear]=p;
12、 //結(jié)點不為空就入隊 if(rear==1) { front=1; Q[front]=p; //根節(jié)點入隊作為隊列頭結(jié)點 rear ++; } while(front!=rear) { p=Q[front]; //隊頭結(jié)點出隊 front ++; printf("%3c",p->data); if(p->lchild!=NULL) { Q[rear]=p->lchild;
13、 rear ++; } if(p->rchild!=NULL) { Q[rear]=p->rchild; rear ++; } } } } 這三個函數(shù)實現(xiàn)了二叉樹的遞歸遍歷方法。先序思想是先根、后左孩子、再右孩子,中序遍歷思想是先左孩子、后根、再右孩子,后序是先左孩子、后右孩子、再根。 4.主函數(shù) int main() { Btree boot; boot=(Btnode *)malloc(sizeof(Btnode)); boot=NULL; int x; do { printf
14、("_____________________________________\n"); printf("--------------歡迎使用!-------------\n"); printf("_____________________________________\n"); printf("\n***************主菜單****************\n"); printf(" x=1... 先序遍歷建立二叉樹!\n"); printf(" x=2... 先序遍歷輸出二叉樹!\n");
15、 printf(" x=3... 中序遍歷輸出二叉樹!\n"); printf(" x=4... 后序遍歷輸出二叉樹!\n"); printf(" x=5... 層次遍歷輸出二叉樹!\n"); printf(" x=0... 退出\n"); printf("****************************************\n"); do { fflush(stdin); printf("請輸入x的值:"); scanf("%d",&x);
16、 if((x!=1)&&(x!=2)&&(x!=3)&&(x!=4)&&(x!=0)&&(x!=5)) { printf("請輸入正確的x的值\n"); } }while((x!=1)&&(x!=2)&&(x!=3)&&(x!=4)&&(x!=0)&&(x!=5)); switch(x) { case 1: printf("\t先序遍歷建立二叉樹:\n"); printf("\t請輸入二叉樹結(jié)點的值!:\n"); printf("(可以輸n個值均為字母或@(n<100)字符間以回車
17、符換行,想結(jié)束時輸多個@):\n"); boot=pre_creat(); //順序表的逆置 printf("\n\n"); break; case 2: printf("\t先序遍歷輸出二叉樹!:\n"); printf("建立的二叉樹是: "); preorder_btree(boot); printf("\n\n"); break; case 3: printf("\t中序遍歷輸出二叉樹!:\n");
18、 printf("建立的二叉樹是: "); inorder_btree(boot); printf("\n\n"); break; case 4: printf("\t后序遍歷輸出二叉樹!:\n"); printf("建立的二叉樹是: "); postorder_btree(boot); printf("\n\n"); break; case 5: printf("\
19、t層次遍歷輸出二叉樹!:\n"); printf("建立的二叉樹是: "); level_btree(boot); printf("\n\n"); break; } }while(x!=0); printf("ByeBye!"); return x; } 7. 運行結(jié)果: 圖 一 圖 二 圖 三 圖 四
20、 圖 五 圖 六 圖 七 設(shè)計結(jié)果與分析(可以加頁): 本次課程設(shè)計實現(xiàn)了二叉鏈表的相關(guān)函數(shù)庫的調(diào)用。為了實現(xiàn)以鏈表為存儲結(jié)構(gòu)的二叉樹的有關(guān)操作,要熟練掌握二叉鏈表的特性,但對于一些算法較為復(fù)雜,代碼量多些,容易出現(xiàn)一些變量的定義、函數(shù)聲明、函數(shù)調(diào)用等細節(jié)上的問題出錯。在本程序的設(shè)計過程中,為了克服以上困難,采取了一些措施:建立清晰的程序設(shè)計的步驟方法,分步各個模塊程序設(shè)計,進行仔細的總體結(jié)構(gòu)設(shè)計,反復(fù)調(diào)試、細心觀察達到完善整個系統(tǒng)等。 設(shè)計體會與建議:數(shù)據(jù)結(jié)構(gòu)是計算機程序設(shè)計的重要理論技術(shù)基礎(chǔ),在理論學(xué)習(xí)
21、和基礎(chǔ)實驗的基礎(chǔ)上,通過實踐設(shè)計一定量的程序,掌握應(yīng)用計算機解決實際問題的基本方法,是理解和運用數(shù)據(jù)結(jié)構(gòu)及算法,提高編程能力的有效途徑,并為學(xué)習(xí)軟件專業(yè)課程積累理論基礎(chǔ)和實踐基礎(chǔ)。程序的設(shè)計和開發(fā)過程,不僅要求我們牢固地掌握各種基礎(chǔ)知識,更考查了對基礎(chǔ)知識的綜合運用能力。這次我的實驗課題是二叉樹的基本算法綜合分析。算法是數(shù)據(jù)結(jié)構(gòu)的核心,是我們學(xué)習(xí)軟件開發(fā)必須掌握的基本知識。 簡單課程設(shè)計最重要的是基礎(chǔ)知識的運用,以及綜合分析問題的能力。二叉樹的遞歸算法主要是將二叉樹存儲到鏈表結(jié)構(gòu)中。遍歷是二叉樹各種操作的基礎(chǔ),先序、中序、后序是二叉樹遍歷的三種基本遍歷方法。而這些都是數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)內(nèi)容,是我
22、們必須理解和牢記的基礎(chǔ)知識。將這些基礎(chǔ)算法綜合起來,更能清晰地認識和理解各種算法的作用。當(dāng)然,要學(xué)會編程不會僅局限于課本知識,而是根據(jù)課本知識進行有效的拓展,并且不得不學(xué)會在眾多的參考資料中搜索有用的自己所需的知識,并迫使自己去學(xué)習(xí)掌握它們,從中不斷提高自己。例如,課本上只給出了二叉樹的遞歸中序遍歷方法,由此可容易推出遞歸的前序和中序遍歷方法。 二叉樹的基本操作是多種多樣的,由于時間的短促和作者水平有限,因不能做太大規(guī)模的設(shè)計。雖然程序規(guī)模不大,我依然為此付出了努力,仍免不了各種錯誤的出現(xiàn)。編程過程需要很大的毅力和耐心,而且要有良好的思維和扎實的專業(yè)基礎(chǔ)知識,所以我需要不斷的學(xué)習(xí),發(fā)現(xiàn)自身不足之處并改正它,逐步提高自身能力,不斷取得進步。對于數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí),我一直感到很吃力,但想過放棄。通過實踐,讓我們認識到知識的運用性,并加深對基礎(chǔ)知識的理解,從中了解自己需要學(xué)習(xí)的東西并學(xué)會自學(xué)。在此我要感謝我的老師對我們專心致志的輔導(dǎo),讓我學(xué)會了許多分析和解決問題的方法,讓我受益匪淺。作為一名計算機專業(yè)的學(xué)生,今后我將加倍努力學(xué)習(xí)專業(yè)知識,為自己從事的職業(yè)打下堅實基礎(chǔ)。 設(shè)計成績: 教師簽名: 年 月 日
- 溫馨提示:
1: 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2: 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3.本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 裝配圖網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 2023年六年級數(shù)學(xué)下冊6整理和復(fù)習(xí)2圖形與幾何第7課時圖形的位置練習(xí)課件新人教版
- 2023年六年級數(shù)學(xué)下冊6整理和復(fù)習(xí)2圖形與幾何第1課時圖形的認識與測量1平面圖形的認識練習(xí)課件新人教版
- 2023年六年級數(shù)學(xué)下冊6整理和復(fù)習(xí)1數(shù)與代數(shù)第10課時比和比例2作業(yè)課件新人教版
- 2023年六年級數(shù)學(xué)下冊4比例1比例的意義和基本性質(zhì)第3課時解比例練習(xí)課件新人教版
- 2023年六年級數(shù)學(xué)下冊3圓柱與圓錐1圓柱第7課時圓柱的體積3作業(yè)課件新人教版
- 2023年六年級數(shù)學(xué)下冊3圓柱與圓錐1圓柱第1節(jié)圓柱的認識作業(yè)課件新人教版
- 2023年六年級數(shù)學(xué)下冊2百分數(shù)(二)第1節(jié)折扣和成數(shù)作業(yè)課件新人教版
- 2023年六年級數(shù)學(xué)下冊1負數(shù)第1課時負數(shù)的初步認識作業(yè)課件新人教版
- 2023年六年級數(shù)學(xué)上冊期末復(fù)習(xí)考前模擬期末模擬訓(xùn)練二作業(yè)課件蘇教版
- 2023年六年級數(shù)學(xué)上冊期末豐收園作業(yè)課件蘇教版
- 2023年六年級數(shù)學(xué)上冊易錯清單十二課件新人教版
- 標(biāo)準工時講義
- 2021年一年級語文上冊第六單元知識要點習(xí)題課件新人教版
- 2022春一年級語文下冊課文5識字測評習(xí)題課件新人教版
- 2023年六年級數(shù)學(xué)下冊6整理和復(fù)習(xí)4數(shù)學(xué)思考第1課時數(shù)學(xué)思考1練習(xí)課件新人教版