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