課程設(shè)計--- 二叉排序樹的實現(xiàn)

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：doc 頁數(shù)：26 大?。?92.00KB 人氣指數(shù)：12 舉報 版權(quán)申訴

已閱讀1頁，還剩25頁未讀，繼續(xù)免費閱讀

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進行舉報或認(rèn)領(lǐng)

文檔簡介

1、　　課程設(shè)計（論文）任務(wù)書　　軟件　學(xué)院　軟件+道路與鐵道　專業(yè) 2 　班　　　 　　一、課程設(shè)計(論文)題目　　二叉排序樹的實現(xiàn) 　　　　二、課程設(shè)計(論文)工作自 2012

2、年 12 月 17日起至2012年 12 月 23日止。　　三、課程設(shè)計(論文) 地點: 15#520 　　四、課程設(shè)計(論文)內(nèi)容要求：　　1．本課程設(shè)計的目的　　(1) （1）要求學(xué)生達(dá)到

3、熟練掌握C 語言的基本知識和技能；　　(2) 基本掌握面向?qū)ο蟪绦蛟O(shè)計的基本思路和方法；　　(3) 能夠利用所學(xué)的基本知識和技能，解決簡單的程序設(shè)計問題。 　　2．課程設(shè)計的任務(wù)及要求　　1）基本要求：<

4、p>　　（1）（1）要求利用TC 的編程思想來完成系統(tǒng)的設(shè)計；　?。?）要求在設(shè)計的過程中，建立清晰的結(jié)構(gòu)體層次；　?。?）在系統(tǒng)的設(shè)計中，至少要做到基本管理要求。　?。?）學(xué)生必須仔細(xì)閱讀《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計方案，認(rèn)真主動完成課設(shè)的要求。有問題及時主動通過各種方式與教師聯(lián)系溝通。&

5、lt;p>　　2）創(chuàng)新要求： 　　在基本要求達(dá)到后，可進行創(chuàng)新設(shè)計，如改善算法性能、友好的人機界面　　等。　　3）課程設(shè)計論文編寫要求　?。?）要按照書稿的規(guī)格打印與寫課程設(shè)計論文</

6、p>　　（2）論文包括目錄、功能描述、設(shè)計思路、具體實現(xiàn)、運行調(diào)試與分析討　　論、設(shè)計體會與小結(jié)、參考文獻、附錄（源代碼）等 　?。?）課程設(shè)計論文裝訂按學(xué)校的統(tǒng)一要求完成　　4）答辯與評分標(biāo)準(zhǔn)： 　　（1）考勤與學(xué)習(xí)態(tài)度：20分； </

7、p>　　（2）設(shè)計思路：20分；　?。?）代碼實現(xiàn)：20分；　　（4）調(diào)試與分析：20分；　?。?）回答問題：10分；　?。?）論文規(guī)范性：10分。　　5）參考文獻

8、　　[1]嚴(yán)蔚敏，吳偉民，《數(shù)據(jù)結(jié)構(gòu)》北京清華大學(xué)出版社　　[2]譚浩強，《C++程序設(shè)計》北京清華大學(xué)出版社　　[3]譚鋒，章偉聰，《Visual c++程序設(shè)計實訓(xùn)教程》北京科學(xué)出版社　　6）課程設(shè)計進度安排　　1．準(zhǔn)備

9、階段(2學(xué)時):選擇設(shè)計題目、了解設(shè)計目的要求、查閱相關(guān)資料　　2．程序模塊設(shè)計分析階段（2學(xué)時）：程序總體設(shè)計、詳細(xì)設(shè)計　　3．代碼編寫調(diào)試階段（6學(xué)時）：程序模塊代碼編寫、調(diào)試、測試　　4．撰寫課程設(shè)計論文階段（2學(xué)時）：總結(jié)課程設(shè)計任務(wù)和設(shè)計內(nèi)容，撰

10、;　　寫課程設(shè)計論文　　課程設(shè)計(論文)評審意見　?。?）考勤與態(tài)度（20分）：優(yōu)（　）、良（?。⒅校ā。?、一般（?。⒉睿ā。?； 　　（2）設(shè)計思路　?。?0分）：優(yōu)（?。⒘迹ā。?、中（　）、一般（?。?、差（　）； 　?。?）代碼實現(xiàn)　　（2

11、0分）：優(yōu)（　）、良（　）、中（?。?、一般（　）、差（　）；　　（4）調(diào)試與分析?。?0分）：優(yōu)（　）、良（　）、中（　）、一般（　）、差（　）；　　（5）回答問題　?。?0分）：優(yōu)（?。⒘迹ā。⒅校ā。?、一般（?。⒉睿ā。?lt;/p>　?。?）論文規(guī)范性（10分）：優(yōu)（　）、良（　）、中（　）、一般（?。?、差（

12、?。?；　　評閱人：　　　職稱：講師 　　2012 年12月26日 　　目錄　　緒論- 1 -　　一、功能

13、描述- 2 -　　二、設(shè)計思路- 2 -　　三、具體實現(xiàn)- 6 -　　四、運行調(diào)試及結(jié)果分析- 14 -　　五、設(shè)計體會與小結(jié)- 16 -　　六、參考文獻17　　七、

14、附錄(核心代碼)17　　緒論　　數(shù)據(jù)結(jié)構(gòu)是一門理論性強、思維抽象、難度較大的課程，是基礎(chǔ)課和專業(yè)課之間的橋梁。該課程的先行課程是計算機基礎(chǔ)、程序設(shè)計語言、離散數(shù)學(xué)等，后續(xù)課程有操作系統(tǒng)、編譯原理、數(shù)據(jù)庫原理、軟件工程等。通過本門課程的學(xué)習(xí)，我們應(yīng)該能透徹地理解各種數(shù)據(jù)對象的特點，學(xué)會數(shù)據(jù)的組織方法和實現(xiàn)方法，并

15、進一步培養(yǎng)良好的程序設(shè)計能力和解決實際問題的能力。 　　數(shù)據(jù)結(jié)構(gòu)是計算機科學(xué)與技術(shù)專業(yè)的一門核心專業(yè)基礎(chǔ)課程，在該專業(yè)的課程體系中起著承上啟下的作用，學(xué)好數(shù)據(jù)結(jié)構(gòu)對于提高理論認(rèn)知水平和實踐能力有著極為重要的作用。學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的最終目的是為了獲得求解問題的能力。對于現(xiàn)實世界中的問題，應(yīng)該能從中抽象出一個適當(dāng)?shù)臄?shù)學(xué)模型，該數(shù)學(xué)模型在計算機內(nèi)部用相應(yīng)的數(shù)據(jù)結(jié)構(gòu)來表示，然后設(shè)計一個解此數(shù)學(xué)模型的算法，再

16、進行編程調(diào)試，最后獲得問題的解答。　　實習(xí)課程是為了加強編程能力的培養(yǎng)，鼓勵學(xué)生使用新興的編程語言。相信通過數(shù)據(jù)結(jié)構(gòu)課程實踐，無論是理論知識，還是實踐動手能力，我們都會有不同程度上的提高。　　功能描述　　1) 以回車('\n')為輸入結(jié)束標(biāo)志,輸入數(shù)

17、列L，生成一棵二叉排序樹T； 2) 對二叉排序樹T作中序遍歷，輸出結(jié)果； 3) 輸入元素x,查找二叉排序樹T,若存在含x的結(jié)點,則刪除該結(jié)點,并作中序遍歷(執(zhí)行操作2)；否則輸出信息“無x”；　　設(shè)計思路<b&g

18、t;　　算法設(shè)計思想　　二插鏈表作存儲結(jié)構(gòu)：建立二插排序樹采用邊查找邊插入的方式。查找函數(shù)采用遞歸的方式進行查找。如果查找成功則不應(yīng)再插入原樹，否則返回當(dāng)前結(jié)點的上一個結(jié)點。然后利用插入函數(shù)將該元素插入原樹。　　對二叉樹進行中序遍歷采用遞歸函數(shù)的方式。在根結(jié)點不為空的情況下，先訪問左子樹，再訪問根結(jié)點，最后訪問右子樹。</p

19、>　　刪除結(jié)點函數(shù)，采用邊查找邊刪除的方式。如果沒有查找到，則不對樹做任何的修改；如果查找到結(jié)點，則分四種情況分別進行討論：1、該結(jié)點左右子樹均為空；2、該結(jié)點僅左子樹為空；3、該結(jié)點僅右子樹為空；4、該結(jié)點左右子樹均不為空。　　在進行算法設(shè)計時，應(yīng)將題目分為五個函數(shù)模塊：　　1、中序遍歷，符合升序輸出

20、　　void inorder(node *&root) 　　{　　if(root!=NULL)　　{　　inorder(root->left);</

21、p>　　cout<<root->data<<' ';　　inorder(root->right);　　}　　}　　2

22、、在查找樹中插入元素　　void insert(node *&ptr,int item) 　　{　　if(ptr==NULL)　　ptr=new node(item);　　else

23、 if(item<ptr->data)　　insert(ptr->left,item);　　else insert(ptr->right,item);　　}　　3、在查找樹中查找元素 &

24、lt;p>　　node *find(node *&ptr,int item) 　　{　　if(ptr==NULL)　　return NULL;　　if(ptr->data==item)&

25、lt;p>　　return ptr;　　else if(item<ptr->data)　　find(ptr->left,item);　　else find(ptr->right,item);　　}<

26、/p>　　4、在查找樹中查找肯定存在的元素,并返回其引用　　node *&findy(node *&ptr,int item) 　　{　　if(ptr->data==item)　　r

27、eturn ptr;　　else if(item<ptr->data)　　findy(ptr->left,item);　　else findy(ptr->right,item);　　}&

28、lt;p>　　node* rl()　　{　　return left;　　}　　node* rr()　　{<

29、;/p>　　return right;　　}　　5、刪除指定值為所在結(jié)點　　void dele(node *&ptr) 　　{

30、　　if(ptr->rl()==NULL&&ptr->rr()==NULL)　　ptr=NULL;　　else if(ptr->rr()==NULL)　　ptr=ptr->rl();<p

31、>　　else　　ptr=ptr->rr();　　}　　private:　　int data;</p&

32、gt;　　node *left; 　　node *right; 　　};　　具體實現(xiàn)　　1.調(diào)入文件&

33、lt;/b>　　#include <iostream>　　2.主函數(shù)　　int main()　　{　　int t,i=0,j;</

34、p>　　cout<<" 謝岳松-218-二叉排序樹的實現(xiàn) "<<endl;　　cout<<"1.二叉排序樹T的輸入:"<<endl;　　cout<<"輸入數(shù)字個數(shù)(結(jié)點個數(shù)):";

35、　　cin>>t;　　cout<<"輸入"<<t<<"個數(shù)字，數(shù)字之間用空格隔開:";　　cin>>j;　　node

36、*x=new node(j);　　for(;i<t-1;i++)　　{　　cin>>j;　　x->insert(x,j);<

37、b>　　}　　cout<<"中序遍歷為:";　　x->inorder(x); //作中序遍歷　　cout<<"\n";　　cout<<&

38、quot;2.二叉排序樹T的元素查找和刪除:"<<endl;　　cout<<"\n輸入操作(當(dāng)輸入-1時程序結(jié)束):"<<endl;　　cin>>j;　　while(j!=-1)

39、　　{　　node *t=x->find(x,j); //定位結(jié)點　　if(t!=NULL)　　{　　node *&y=x->findy

40、(x,j);　　x->dele(y);　　cout<<"中序遍歷為:";　　x->inorder(x);　　}　　else cout<<

41、"無"<<j;　　cout<<"\n輸入操作(當(dāng)輸入-1時程序結(jié)束):"<<endl;　　cin>>j;　　}

42、;　　return 0;　　}　　3.程序編碼　　#include <iostream>　　using namespace std;</p&

43、gt;　　class node　　{　　public:　　node(int i):data(i), lchild (NULL), rchild (NULL){}　　void

44、inorder(node *&root) //中序遍歷，符合升序輸出　　{　　if(root!=NULL)　　{　　inorder(root-> lchild);</

45、p>　　cout<<root->data<<' ';　　inorder(root-> rchild);　　}　　}

46、　void insert(node *&ptr,int item) //在查找樹中插入元素　　{　　if(ptr==NULL)　　ptr=new node(item);　　else if(item<ptr->da

47、ta)　　insert(ptr-> lchild,item);　　else insert(ptr-> rchild,item);　　}　　node *find(node *&ptr,int item) //在查找

48、樹中查找元素,找到返回所在結(jié)點指針，找不到返回空指針。　　{　　if(ptr==NULL)　　return NULL;　　if(ptr->data==item)　　return ptr;

49、　　else if(item<ptr->data)　　find(ptr-> lchild,item);　　else find(ptr-> rchild,item);　　}

50、;　　node *&findy(node *&ptr,int item) //在查找樹中查找肯定存在的元素,并返回其引用　　{　　if(ptr->data==item)　　return ptr;　　else i

51、f(item<ptr->data)　　findy(ptr-> lchild,item);　　else findy(ptr-> rchild,item);　　}　　node* rl(){return lchild

52、;}　　node* rr(){return rchild;}　　void dele(node *&ptr) //刪除值為item所在結(jié)點　　{　　if(ptr->rl()==NULL&&ptr

53、->rr()==NULL)　　ptr=NULL;　　else if(ptr->rr()==NULL)　　ptr=ptr->rl();　　else<p

54、>　　ptr=ptr->rr();　　}　　private:　　int data;　　node * lchild; /

55、/左孩子結(jié)點　　node * rchild; //右孩子結(jié)點　　};　　int main()　　{　　int t,i=0,j;&

56、lt;/p>　　cout<<" 謝岳松-218-二叉排序樹的實現(xiàn) "<<endl;　　cout<<"1.二叉排序樹T的輸入:"<<endl;　　cout<<"輸入數(shù)字個數(shù)(結(jié)點個數(shù)):";<

57、;/p>　　cin>>t;　　cout<<"輸入"<<t<<"個數(shù)字，數(shù)字之間用空格隔開:";　　cin>>j;

58、;　　node *x=new node(j);　　for(;i<t-1;i++)　　{　　cin>>j;　　x->insert(x,j);<p

59、>　　}　　cout<<"中序遍歷為:";　　x->inorder(x); //作中序遍歷　　cout<<"\n";　　cout&

60、lt;<"2.二叉排序樹T的元素查找和刪除:"<<endl;　　cout<<"\n輸入操作(當(dāng)輸入-1時程序結(jié)束):"<<endl;　　cin>>j;　　while(j!=-1)&l

61、t;/p>　　{　　node *t=x->find(x,j); //定位結(jié)點　　if(t!=NULL)　　{　　node *&y=x-&

62、gt;findy(x,j);　　x->dele(y);　　cout<<"中序遍歷為:";　　x->inorder(x);　　}　　else cout

63、<<"無"<<j;　　cout<<"\n輸入操作(當(dāng)輸入-1時程序結(jié)束):"<<endl;　　cin>>j;　　}

64、　　return 0;　　}　　運行調(diào)試及結(jié)果分析　　輸入節(jié)點數(shù)　　輸入二叉樹數(shù)，并輸出中序遍歷<

65、;/p>　　當(dāng)輸入25時，二叉樹中無該數(shù)據(jù)，輸出無25　　輸入-1表示退出　　設(shè)計體會與小結(jié)　　基于我對編程的極大興趣，我對這次的課程設(shè)計非常重視。通過這次實驗我也著實又感受了一次編程的樂趣，從中也學(xué)到了不少知

66、識。在這段時間里，我遇到過的問題主要就是C語言和C++語言有些混淆，一些用法記不太清楚。在石紅芹老師的指導(dǎo)幫助下，同學(xué)們課余時間的討論中，這些問題都一一得到了解決。在程序的調(diào)試能力上，無形中得到了許多的提高。這樣無形中就提高了自己編寫的程序的質(zhì)量。在實際的上機操作過程中，不僅是讓我們了解數(shù)據(jù)結(jié)構(gòu)的理論知識，更重要的是培養(yǎng)解決實際問題的能力，所以相信通過此次實習(xí)可以提高我們分析設(shè)計能力和編程能力，為后續(xù)課程的學(xué)習(xí)及實踐打下良好的基礎(chǔ)<

67、;/p>　　參考文獻　　[1]嚴(yán)蔚敏，吳偉民，《數(shù)據(jù)結(jié)構(gòu)》北京清華大學(xué)出版社　　[2]譚浩強，《C++程序設(shè)計》北京清華大學(xué)出版社　　[3]譚鋒，章偉聰，《Visual c++程序設(shè)計實訓(xùn)教程》北京科學(xué)出版社<p

68、>　　附錄(核心代碼)　　#include <iostream>　　using namespace std;　　class node　　{

69、;　　public:　　node(int i):data(i), lchild (NULL), rchild (NULL){}　　void inorder(node *&root) //中序遍歷，符合升序輸出　　{<

70、;/p>　　if(root!=NULL)　　{　　inorder(root-> lchild);　　cout<<root->data<<' ';　　ino

71、rder(root-> rchild);　　}　　}　　void insert(node *&ptr,int item) //在查找樹中插入元素　　{</b

72、>　　if(ptr==NULL)　　ptr=new node(item);　　else if(item<ptr->data)　　insert(ptr-> lchild,item);　　else insert

73、(ptr-> rchild,item);　　}　　node *find(node *&ptr,int item) //在查找樹中查找元素,找到返回所在結(jié)點指針，找不到返回空指針。　　{<p&g

74、t;　　if(ptr==NULL)　　return NULL;　　if(ptr->data==item)　　return ptr;　　else if(item<ptr->data)　　find(ptr->

75、lchild,item);　　else find(ptr-> rchild,item);　　}　　node *&findy(node *&ptr,int item) //在查找樹中查找肯定存在的元素,并返回其引用

76、;　　{　　if(ptr->data==item)　　return ptr;　　else if(item<ptr->data)　　findy(ptr-> lchild,item);<

77、;p>　　else findy(ptr-> rchild,item);　　}　　node* rl(){return lchild;}　　node* rr(){return rchild;}　　void dele(node

78、*&ptr) //刪除值為item所在結(jié)點　　{　　if(ptr->rl()==NULL&&ptr->rr()==NULL)　　ptr=NULL;

79、　else if(ptr->rr()==NULL)　　ptr=ptr->rl();　　else　　ptr=ptr->rr();　　}&l

80、t;b>　　private:　　int data;　　node * lchild; //左孩子結(jié)點　　node * rchild; //右孩子結(jié)點<

81、b>　　};　　int main()　　{　　int t,i=0,j;　　cout<<" 謝岳松-218-二叉排序樹的實現(xiàn) "<<endl;</

82、p>　　cout<<"1.二叉排序樹T的輸入:"<<endl;　　cout<<"輸入數(shù)字個數(shù)(結(jié)點個數(shù)):";　　cin>>t;　　cout<<&q

83、uot;輸入"<<t<<"個數(shù)字，數(shù)字之間用空格隔開:";　　cin>>j;　　node *x=new node(j);　　for(;i<t-1;i++)<

84、b>　　{　　cin>>j;　　x->insert(x,j);　　}　　cout<<"中序遍歷為:";

85、;　　x->inorder(x); //作中序遍歷　　cout<<"\n";　　cout<<"2.二叉排序樹T的元素查找和刪除:"<<endl;　　cout<<"

86、;\n輸入操作(當(dāng)輸入-1時程序結(jié)束):"<<endl;　　cin>>j;　　while(j!=-1)　　{　　node *t=x->find(x,j);

87、 //定位結(jié)點　　if(t!=NULL)　　{　　node *&y=x->findy(x,j);　　x->dele(y);　　cout<<&qu

88、ot;中序遍歷為:";　　x->inorder(x);　　}　　else cout<<"無"<<j;　　cout<<"\n輸入操作(當(dāng)輸入-1時程序結(jié)束

89、):"<<endl;　　cin>>j;　　}　　return 0;　　}</p&

眾賞文庫> 全部分類> 畢業(yè)設(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. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

課程設(shè)計--- 二叉排序樹的實現(xiàn)

文檔簡介

溫馨提示

最新文檔

評論

課程設(shè)計--- 二叉排序樹的實現(xiàn)

文檔簡介

溫馨提示

最新文檔

評論

免費下載