《數(shù)據(jù)結(jié)構課程設計二叉連鏈表.doc》由會員分享，可在線閱讀，更多相關《數(shù)據(jù)結(jié)構課程設計二叉連鏈表.doc（14頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、
課程設計指導書
姓 名
學 號
班 級
課程名稱
數(shù)據(jù)結(jié)構
課程性質(zhì)
專業(yè)必修課
設計時間
2010 年 12 月 1日—— 2010 年 12月 20日
設計名稱
設計二叉鏈表結(jié)構的相關函數(shù)庫
設計目的
使用Microsoft Visual C++ 設計二叉鏈表結(jié)構的相關函數(shù)庫，并能夠在程序設計中調(diào)用
設計要求
設計二叉鏈表結(jié)構的相關函數(shù)庫，以便在程序設計中調(diào)用，實現(xiàn)二叉樹的各種基本函數(shù)以及常用函數(shù)；并給出1-2個例子，通過調(diào)用自己的庫函數(shù)來實現(xiàn)問題的求解。
設計思路
與
設計過程
1. 程序需求分析
完成：根據(jù)需求分析，確定
2、各個程序功能的需求；
2. 程序總統(tǒng)設計
完成：根據(jù)程序需求，進行程序大概框架的設計；
3. 主函數(shù)設計
完成：主函數(shù)程序中設計一個菜單，并調(diào)試所用算法；
4. 其他函數(shù)設計
完成：建立二叉鏈表以及遞歸序列遍歷算法
5. 系統(tǒng)程序完善
完成：完善整個程序細節(jié)代碼的要求，進行調(diào)試。
計劃與進度
12.1-12.2 復習對vc++6.0使用，了解關于二叉鏈表的相關特征等。
12.3-12.4 查找有關二叉鏈表基本操作的算法等。
12.5-12.7 根據(jù)需求分析，確立各個函數(shù)程序功能。
12.8-12.10 根據(jù)程序需求，進行相關子函數(shù)
3、程序的編寫。
12.11-12.13 進行主函數(shù)程序功能的設計編寫。
12.14-12.16 進行對整個程序的完善。
12.17-12.18 進行程序的調(diào)試運行。
12.19-12.20 資料歸檔，填寫相關文檔。
任課教師
意 見
備 注
課程設計報告
課程：
學號：
姓名：
班級：
教師
時間：
計算機科學與技術系
設計名稱： 設計二叉鏈表的相關函數(shù)庫
日期：2010年 12 月 20 日
設計內(nèi)容：使用Microsoft Visual C++ 設計二
4、叉鏈表結(jié)構的相關函數(shù)庫，以便在程序設計中調(diào)用
設計目的與要求：設計二叉鏈表結(jié)構的相關函數(shù)庫，在程序設計中調(diào)用，并實現(xiàn)二叉樹的各種基本函數(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é)構設計的一般方法步驟進行設計。
設計過程（步驟）和部分程序代碼(可以加頁)：
一． 題目要求
設計二叉鏈表結(jié)構的相關函數(shù)庫，在程序設計
5、中調(diào)用，并實現(xiàn)二叉樹的各種基本函數(shù)以及常用函數(shù)。
二． 需求分析
建立一棵二叉樹：
（1）二叉樹的鏈表結(jié)構；
（2）進行先序遍歷，輸出結(jié)果；
（3）進行中序遍歷，輸出結(jié)果；
（4）進行后序遍歷，輸出結(jié)果；
（5）進行層次遍歷，輸出結(jié)果。
三． 運行環(huán)境
Windows XP
四． 開發(fā)工具和編程語言
1.開發(fā)工具：Microsoft Visual C++6.0
2.編程語言：C語言
五． 概要設計
1. 數(shù)據(jù)結(jié)構
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) //層次遍歷輸出二叉樹
六． 詳細設計
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、 圖 五
圖 六
圖 七
設計結(jié)果與分析(可以加頁)：
本次課程設計實現(xiàn)了二叉鏈表的相關函數(shù)庫的調(diào)用。為了實現(xiàn)以鏈表為存儲結(jié)構的二叉樹的有關操作，要熟練掌握二叉鏈表的特性，但對于一些算法較為復雜，代碼量多些，容易出現(xiàn)一些變量的定義、函數(shù)聲明、函數(shù)調(diào)用等細節(jié)上的問題出錯。在本程序的設計過程中，為了克服以上困難，采取了一些措施：建立清晰的程序設計的步驟方法，分步各個模塊程序設計，進行仔細的總體結(jié)構設計，反復調(diào)試、細心觀察達到完善整個系統(tǒng)等。
設計體會與建議：數(shù)據(jù)結(jié)構是計算機程序設計的重要理論技術基礎，在理論學習
21、和基礎實驗的基礎上，通過實踐設計一定量的程序，掌握應用計算機解決實際問題的基本方法，是理解和運用數(shù)據(jù)結(jié)構及算法，提高編程能力的有效途徑，并為學習軟件專業(yè)課程積累理論基礎和實踐基礎。程序的設計和開發(fā)過程，不僅要求我們牢固地掌握各種基礎知識，更考查了對基礎知識的綜合運用能力。這次我的實驗課題是二叉樹的基本算法綜合分析。算法是數(shù)據(jù)結(jié)構的核心，是我們學習軟件開發(fā)必須掌握的基本知識。
簡單課程設計最重要的是基礎知識的運用，以及綜合分析問題的能力。二叉樹的遞歸算法主要是將二叉樹存儲到鏈表結(jié)構中。遍歷是二叉樹各種操作的基礎，先序、中序、后序是二叉樹遍歷的三種基本遍歷方法。而這些都是數(shù)據(jù)結(jié)構的基礎內(nèi)容，是我
22、們必須理解和牢記的基礎知識。將這些基礎算法綜合起來，更能清晰地認識和理解各種算法的作用。當然，要學會編程不會僅局限于課本知識，而是根據(jù)課本知識進行有效的拓展，并且不得不學會在眾多的參考資料中搜索有用的自己所需的知識，并迫使自己去學習掌握它們，從中不斷提高自己。例如，課本上只給出了二叉樹的遞歸中序遍歷方法，由此可容易推出遞歸的前序和中序遍歷方法。
二叉樹的基本操作是多種多樣的，由于時間的短促和作者水平有限，因不能做太大規(guī)模的設計。雖然程序規(guī)模不大，我依然為此付出了努力，仍免不了各種錯誤的出現(xiàn)。編程過程需要很大的毅力和耐心，而且要有良好的思維和扎實的專業(yè)基礎知識，所以我需要不斷的學習，發(fā)現(xiàn)自身不足之處并改正它，逐步提高自身能力，不斷取得進步。對于數(shù)據(jù)結(jié)構的學習，我一直感到很吃力，但想過放棄。通過實踐，讓我們認識到知識的運用性，并加深對基礎知識的理解，從中了解自己需要學習的東西并學會自學。在此我要感謝我的老師對我們專心致志的輔導，讓我學會了許多分析和解決問題的方法，讓我受益匪淺。作為一名計算機專業(yè)的學生，今后我將加倍努力學習專業(yè)知識，為自己從事的職業(yè)打下堅實基礎。
設計成績： 教師簽名：
年 月 日
數(shù)據(jù)結(jié)構課程設計二叉連鏈表.doc
