《樹地綜合操作 大數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》由會(huì)員分享，可在線閱讀，更多相關(guān)《樹地綜合操作 大數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)（23頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、word
數(shù)據(jù)結(jié)構(gòu)
課程設(shè)計(jì)(論文)
樹的綜合操作
院〔系〕名稱
專業(yè)班級(jí)
學(xué)號(hào)
學(xué)生
指導(dǎo)教師
—
課程設(shè)計(jì)〔論文〕任務(wù)與評(píng)語
院〔系〕：電子與信息工程學(xué)院 教研室：軟件工程
學(xué)號(hào)
學(xué)生
專業(yè)班級(jí)
課程設(shè)計(jì)〔論文〕題目
樹的綜合操作
課程設(shè)計(jì)〔論文〕任務(wù)
任務(wù)要求：
樹的綜合操作實(shí)現(xiàn)以下幾個(gè)功能：〔1〕創(chuàng)建二叉樹的存儲(chǔ)結(jié)構(gòu)并保存；〔2〕非遞歸實(shí)現(xiàn)中序遍歷二叉樹〔3〕非遞歸實(shí)現(xiàn)先序遍歷二叉樹。〔4〕遞歸實(shí)現(xiàn)層次遍歷二叉樹；〔5〕求出二叉樹的葉子結(jié)點(diǎn)數(shù)和層次數(shù)。
技術(shù)要求：
1、數(shù)據(jù)的邏輯結(jié)
2、構(gòu)采用樹形結(jié)構(gòu)，物理結(jié)構(gòu)采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)〔二叉鏈表〕。
2、軟件能正常運(yùn)行，界面清晰，操作要簡(jiǎn)單。
3、系統(tǒng)要有主界面設(shè)計(jì)，調(diào)用各個(gè)功能項(xiàng)。
4、采用Viscal C++編寫代碼，可讀性強(qiáng)。
5、數(shù)據(jù)類型用typedef 定義。
指導(dǎo)教師評(píng)語與成績(jī)
平時(shí)成績(jī)：辯論成績(jī)：論文成績(jī)：
總成績(jī)：指導(dǎo)教師簽字：
年月日
注：平時(shí)成績(jī)占20%，辯論成績(jī)占40%，論文成績(jī)占40%。
19 / 23
摘 要
這次的課題主要是創(chuàng)建二叉樹的存儲(chǔ)結(jié)構(gòu)并保存，通過這一過程了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計(jì)方法，具備初步的獨(dú)立分析和設(shè)計(jì)能力并提高綜合運(yùn)用所學(xué)
3、的理論知識(shí)和方法獨(dú)立分析和解決問題的能力
主要解決以下問題
①創(chuàng)建二叉樹的存儲(chǔ)結(jié)構(gòu)并保存；
②非遞歸實(shí)現(xiàn)中序遍歷二叉樹；
③非遞歸實(shí)現(xiàn)先序遍歷二叉樹；
④遞歸實(shí)現(xiàn)層次遍歷二叉樹；
⑤求出二叉樹的葉子節(jié)點(diǎn)數(shù)和層次樹；
關(guān)鍵詞：存儲(chǔ)結(jié)構(gòu)；二叉樹；C++
目 錄
第1章緒論1
系統(tǒng)的開發(fā)背景1
開發(fā)工具與語言1
第2章概要設(shè)計(jì)1
模塊劃分1
2.2 數(shù)據(jù)結(jié)構(gòu)的選擇1
第3章系統(tǒng)詳細(xì)設(shè)計(jì)與編碼2
完整的源程序2
程序的輸入和輸出3
調(diào)試程序中遇到的問題與解決方案4
第4章思考題解析5
4.1 思考題的選擇5
類C算法5
程序分
4、析5
第5章總結(jié)6
參考文獻(xiàn)7
附錄8
第1章 緒論
系統(tǒng)的開發(fā)背景
二叉樹結(jié)構(gòu)是C語言中的難點(diǎn)，但是近年來二叉樹的應(yīng)用越發(fā)的廣泛，實(shí)用性越來越強(qiáng)。為了應(yīng)對(duì)日新月異的時(shí)代變化，我參與了這個(gè)課題來提高自己對(duì)二叉樹的掌握
與語言
本系統(tǒng)使用Viscal C++語言開發(fā)，主界面清晰顯示所有功能項(xiàng)，使用簡(jiǎn)單。各個(gè)功能項(xiàng)均定義一個(gè)函數(shù)來實(shí)現(xiàn)，在主函數(shù)中調(diào)用各個(gè)子函數(shù)實(shí)現(xiàn)不同的功能。
第2章 概要設(shè)計(jì)
模塊劃分
1〕題目應(yīng)實(shí)現(xiàn)的具體功能；
①創(chuàng)建二叉樹的存儲(chǔ)結(jié)構(gòu)并保存；
②非遞
5、歸實(shí)現(xiàn)中序遍歷二叉樹；
③非遞歸實(shí)現(xiàn)先序遍歷二叉樹；
④遞歸實(shí)現(xiàn)層次遍歷二叉樹；
⑤求出二叉樹的葉子節(jié)點(diǎn)數(shù)和層次樹；
2.2 數(shù)據(jù)結(jié)構(gòu)的選擇
系統(tǒng)數(shù)據(jù)的邏輯結(jié)構(gòu)采用樹形結(jié)構(gòu)，物理結(jié)構(gòu)采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)〔二叉鏈表〕。
存儲(chǔ)結(jié)構(gòu)定義如下：
typedef struct lnode
{char data;
struct lnode *lchild,*rchild;
}lnode,*tree;
第3章 系統(tǒng)詳細(xì)設(shè)計(jì)與編碼
完整的源程序
#include
#include
#i
6、nclude
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define MaxSize 100
typedef char TElemType;
typedef int Status;
//二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
typedef struct BiTNode{
TElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
//棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
typedef struct LNode
{
BiTree data;
str
7、uct LNode *next;
}LNode,*LinkList;
//進(jìn)棧
Status Push(LinkList& S,BiTree T)
{
LinkList stack;
stack=(LinkList)malloc(sizeof(LNode)); //分配空間
stack->data=T;
stack->next=S->next; //進(jìn)棧
S->next=stack;
return OK;
}//Push
//出棧
Status Pop(LinkList &S,BiTree &T)
{
LinkList stack;
stac
8、k=S->next; //出棧
S->next=stack->next; //棧頂指向下個(gè)元素
T=stack->data;
return OK;
}//Pop
//是否為空棧
Status StackEmpty(LinkList S)
{
if(S->next==NULL)
return OK;
else
return ERROR;
}
//以先序次序建立二叉樹
Status CreatBiTree(BiTree &T)
{
TElemType ch;
cin>>ch;
if(ch=='#') T=NULL;
else{
9、 if(!(T=(BiTree)malloc(sizeof(BiTNode)))) exit(OVERFLOW); //分配存儲(chǔ)空間
T->data=ch; //生成根節(jié)點(diǎn)
CreatBiTree(T->lchild); //生成左子樹
CreatBiTree(T->rchild); //生成右子樹
}
return OK; //創(chuàng)建成功
}//CreatBiTree
//非遞歸中序訪問二叉樹
BiTree GoFarLeft(BiTree T,LinkList &
10、S) //指到二叉樹最左邊結(jié)點(diǎn)
{
if(!T) return NULL;
while(T->lchild)
{
Push(S,T); //結(jié)點(diǎn)進(jìn)棧
T=T->lchild;
}
return T; //返回樹頭結(jié)點(diǎn)
}
void Inorder_I(BiTree T)
{
BiTree t;
LinkList S;
S=(LinkList)malloc(sizeof(LNode));
S->next=NULL;
t=GoFarLeft(T,S); //找到最左下的結(jié)點(diǎn)
while (t)
{
11、 cout<data<<" ";
if(t->rchild)
t=GoFarLeft(t->rchild,S);
else if(!StackEmpty(S)) //棧空明確遍歷完畢
Pop(S,t);
else t=NULL;
}//while
cout<
12、>0)
{
while(p!=NULL)
{
cout<data<<" "; //輸出結(jié)點(diǎn)data
Stack[top]=p; //左樹進(jìn)棧
top++;
p=p->lchild;
}
if(top>0)
{
top--;
p=Stack[top];
p=p->rchild;
}
}
cout<
13、p;
p=(BiTree)malloc(sizeof(BiTree));
stack=(LinkList)malloc(sizeof(LinkList));
stack->next=NULL;
Push(stack,b); //二叉樹頭結(jié)點(diǎn)進(jìn)棧
while(!StackEmpty(stack)) //是否為空
{
Pop(stack,p); //出棧
while (p)
{
cout<data<<" "; //輸出當(dāng)前指向結(jié)點(diǎn)
if(p->rchild)Push(stack,p->rchild); //訪
14、問右指點(diǎn)
p=p->lchild;
}
}
cout<lchild;
}
while (top>0&&stack[top]->rchild==p)
{
p=stack[top--]; //棧頂結(jié)點(diǎn)出棧
15、 cout<data<<" "; //訪問p所指向的結(jié)點(diǎn)
}
if (top>0)
p=stack[top]->rchild; //開始遍歷右子樹
}while(top>0);
cout<lchild)&&(!T->rchild))
count++;
CountLeaf(T->lchild,count); //左子樹葉子個(gè)數(shù)
CountLeaf(T
16、->rchild,count); //右子樹葉子個(gè)數(shù)
}
}//CountLeaf
//計(jì)算雙結(jié)點(diǎn)個(gè)數(shù)
void CountParent(BiTree T,int &count)
{
if(T)
{
if(T->lchild&&T->rchild)
count++;
CountParent(T->lchild,count); //左子樹雙結(jié)點(diǎn)個(gè)數(shù)
CountParent(T->rchild,count); //右子樹雙結(jié)點(diǎn)個(gè)數(shù)
}
}
//計(jì)算二叉樹結(jié)點(diǎn)個(gè)數(shù)
void Count(BiTree T,int &count)
{
if(T)
{
17、 Count(T->lchild,count);
Count(T->rchild,count);
count++; //結(jié)點(diǎn)個(gè)數(shù)
}
}
//單結(jié)點(diǎn)個(gè)數(shù)
void CountChild(BiTree T,int &count)
{
if(T)
{
if((T->lchild&&(!T->rchild))||(T->rchild&&(!T->lchild)))
count++;
CountChild(T->lchild,count); //左子樹單結(jié)點(diǎn)個(gè)數(shù)
CountChild(T->rchild,count);
18、 //右子樹單結(jié)點(diǎn)個(gè)數(shù)
}
}
//計(jì)算樹的高度
int Depth(BiTree T)
{ int depthval,depthLeft,depthRight;
if(!T) depthval=0;
else
{depthLeft=Depth(T->lchild); //左子樹高度
depthRight=Depth(T->rchild); //右子樹高度
depthval=1+(depthLeft>depthRight ?depthLeft:depthRight); //取高度最高
}
return depthval; //返回
19、}
//計(jì)算任意結(jié)點(diǎn)所在的層次
int NodeLevel(BiTree T,TElemType &p,int &count)
{
if(T==NULL)
return 0;
if(T->data==p)
return 1;
if(NodeLevel(T->lchild,p,count)||(NodeLevel(T->rchild,p,count)))
{
count++;
return 1;
}
return 0;
}
//主函數(shù)
void main()
{
char flag;
cout<<"操作選項(xiàng)"<
20、t<<"1,非遞歸打印二叉樹(前序，中序，后序)"<>item;
switch (item)
{
case 1 :
{
BiTree T;
cout<<"請(qǐng)輸入要建立的二叉樹,以'#'表示空樹"<
21、;
CreatBiTree(T);
cout<<"先序非遞歸輸出二叉樹(兩種算法)"<
22、)"<>flag;
break;
}
case 2:
{
BiTree T;
int nodeCount=0,leafCount=0,childCount=0,parentCount=0;
cout<<"請(qǐng)輸入要建立的二叉樹,以'#'表示空樹"<
23、 CountLeaf(T,leafCount);
cout<<"結(jié)點(diǎn)總數(shù)目為:"<>flag;
break;
}
case 3:
{
BiTree T;
24、
cout<<"請(qǐng)輸入要建立的二叉樹,以'#'表示空樹"<>flag;
break;
}
case 4:
{
BiTree T;
int n=0;
char ch;
cout<<"請(qǐng)輸入要建立的二叉樹,以'#'表示空樹"<
25、T);
cout<<"請(qǐng)輸入要查詢的結(jié)點(diǎn):";
cin>>ch;
if(T==NULL)
cout<<"空樹"<>flag;
break;
}
default : cout<<"無此選項(xiàng)請(qǐng)確定后再輸入!"<
26、 }
} while (flag=='y'||flag=='Y');
}
問題： 首先要按照提示輸入，在創(chuàng)建二叉樹的時(shí)候，要注意二叉樹的輸入，要用“#〞代替空，否如此程序不能正確運(yùn)行；每次執(zhí)行新的任務(wù)的時(shí)候都要重新輸入新的二叉樹。
解決方案：按照先序遍歷輸入二叉樹，如果結(jié)點(diǎn)左孩子或右孩子為空如此用“#〞代替；求葉子結(jié)點(diǎn)數(shù)和求層次時(shí)，所先用的子函數(shù)中的參數(shù)初始賦值為零，再從頭結(jié)點(diǎn)出發(fā)開始計(jì)數(shù)，直到所求結(jié)點(diǎn)。
第4章 思考題解析
4.1 思考題
27、的選擇
所選擇的思考題：編寫一個(gè)算法，求一顆二叉樹中每個(gè)結(jié)點(diǎn)平衡因子
類C算法
int btheight(BitTNode *BT)
{
int lh,rh,t;
if(BT==NULL)
return 0;
else
{
lh=btheight(BT->lchild);/*計(jì)算左子數(shù)的高度*/
rh=btheight(BT->rchild);/*計(jì)算右子數(shù)的高度*/
if(lh<=rh)
t=rh;
else
t=lh;
BT->num=lh-rh;/*計(jì)算結(jié)點(diǎn)的平衡因子*/
return t+1
}
}
結(jié)點(diǎn)的平衡因子等于其左子樹結(jié)點(diǎn)層次減去
28、其右子樹結(jié)點(diǎn)層次，因此要想求得每個(gè)結(jié)點(diǎn)的平衡因子，就得在遍歷每個(gè)結(jié)點(diǎn)的時(shí)候，算出其左，右子樹的層次，程序中用到了遞歸調(diào)用子函數(shù) btheight(bitnode *bt)
第5章 總結(jié)
這是一門純屬于設(shè)計(jì)的科目，它需用把理論變?yōu)樯蠙C(jī)調(diào)試。剛開始學(xué)的時(shí)候確實(shí)有很多地方我很不理解，每次上課時(shí)教師都會(huì)給我們出不同的設(shè)計(jì)題目，對(duì)于我們一個(gè)初學(xué)者來說，無疑是一個(gè)具大的挑戰(zhàn)，撞了幾次壁之后，我決定靜下心來，仔細(xì)去寫程序。教師會(huì)給我們需要編程的容一些講解，順著教師的思路，來完成自己的設(shè)計(jì)，我們可以開始運(yùn)行自己的程序。?
29、
剛開始學(xué)的時(shí)候確實(shí)有很多地方我很不理解，每次上上機(jī)課時(shí)教師都會(huì)給我們出不同的設(shè)計(jì)題目，對(duì)于我們一個(gè)初學(xué)者來說，無疑是一個(gè)具大的挑戰(zhàn)，撞了幾次壁之后，我決定靜下心來，仔細(xì)去寫程序。教師會(huì)給我們需要編程的容一些講解，順著教師的思路，來完成自己的設(shè)計(jì)，我們可以開始運(yùn)行自己的程序，可是好多處的錯(cuò)誤讓人看的可怕，還看不出到底是哪里出現(xiàn)了錯(cuò)誤，但是程序還是得繼續(xù)下去，我屢次請(qǐng)教了教師和同學(xué)，逐漸能自己找出錯(cuò)誤，并加以改正。TC里檢查錯(cuò)誤都是用英文來顯示出來的，經(jīng)過了這次課程設(shè)計(jì)，現(xiàn)在已經(jīng)可以了解很多錯(cuò)誤在英文里的提示，這對(duì)我來說是一個(gè)突破性的進(jìn)步，眼看著一個(gè)個(gè)錯(cuò)誤通過自己的努力在我眼前消失，覺得很是開心
30、。此次的程序設(shè)計(jì)能夠成功，是我和我的同學(xué)三個(gè)人共同努力作用的結(jié)果。在這一段努力學(xué)習(xí)的過程中，我們的編程設(shè)計(jì)有了明顯的提高。?
其實(shí)現(xiàn)在想起來，收獲還真是不少，雖然說以前非常不懂這門語言，在它上面花費(fèi)了好多心血，覺得它很難，是需用花費(fèi)了大量的時(shí)間編寫出來的?，F(xiàn)在真正的明白了一些代碼的應(yīng)用，每個(gè)程序都有一些共同點(diǎn)，通用的結(jié)構(gòu)，相似的格式。只要努力去學(xué)習(xí)，就會(huì)靈活的去應(yīng)用它。
本人簽字：
參考文獻(xiàn)
[1] 徐孝凱編著. 數(shù)據(jù)結(jié)構(gòu)[M]第一版
[2] 文博編著.數(shù)據(jù)結(jié)構(gòu)[M]第二版
[3] 許卓群編著.數(shù)據(jù)結(jié)構(gòu)[M]第一版
[4] 廉治編著.數(shù)據(jù)結(jié)構(gòu)教程[M]第一版
[5] 晉良潁編著.數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)明教程[M]第三版
樹地綜合操作 大數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)
