數(shù)據(jù)結(jié)構(gòu)課程設計--二叉樹的遍歷算法分析與設計

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：docx 頁數(shù)：28 大?。?.11MB 人氣指數(shù)：12 舉報 版權申訴

數(shù)據(jù)結(jié)構(gòu)課程設計--二叉樹的遍歷算法分析與設計_第1頁

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

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

文檔簡介

1、　　數(shù)據(jù)結(jié)構(gòu)課程設計　　題目二叉樹的遍歷算法分析與設計 　　學生姓名專業(yè)班級計算機12-1 　　指導教師職稱　　副教授 　　所在單位

2、信息科學系 　　教學部主任 　　完成日期 2014年1月10日　　數(shù)據(jù)結(jié)構(gòu)課程設計任務書　　一、任務及要求：</

3、p>　　設計（研究）任務和要求　　研究內(nèi)容：二叉樹的遍歷算法分析與設計　　任務和要求：　?。?）學習數(shù)據(jù)結(jié)構(gòu)基礎知識，掌握數(shù)據(jù)結(jié)構(gòu)典型的算法的使用。　　（2）對指導教師下達的題目進行系統(tǒng)分析。</p&

4、gt;　　（3）根據(jù)分析結(jié)果完成系統(tǒng)設計。　　（4）編程：在計算機上實現(xiàn)題目的代碼實現(xiàn)。　　（5）完成對該系統(tǒng)的測試和調(diào)試。　　（6）提交課程設計報告。　　要求完成課程設計報告3000字以上(約二十頁)。

5、完成若干綜合性程序設計題目，綜合設計題目的語句行數(shù)的和在100行語句以上。　　2.原始依據(jù)　　結(jié)合數(shù)據(jù)結(jié)構(gòu)課程中的基本理論和基本算法，正確分析出數(shù)據(jù)的邏輯結(jié)構(gòu)，合理地選擇相應的存儲結(jié)構(gòu)，并能設計出解決問題的有效算法。提高程序設計和調(diào)試能力。學生通過上機實習，驗證自己設計的算法的正確性。學會有效利用基本調(diào)試方法，迅速找

6、出程序代碼中的錯誤并且修改。　　3.參考題目：　　二、工作量　　2周（10個工作日）時間　　三、計劃安排　　第1個工

7、作日：查找相關資料、書籍，閱讀示例文檔，選擇題目。　　第2個工作日－第3個工作日：設計程序結(jié)構(gòu)、模塊圖。　　第4個工作日－第9個工作日：完成程序的編碼，并且自己調(diào)試、測試。穿插進行課程設計報告的撰寫。　　第10個工作日：上交課程設計報告，由教師檢查軟件測試效果、檢查課程設計報告，給出學生成績。

8、　　指導教師簽字：　　2013年 12月 30日　　題目一:居民信息管理系統(tǒng)(以二叉樹建立)算法分析與設計　　1.需求分析　　此系統(tǒng)是根據(jù)用戶的需求，主要是對居民的基本信息進

9、行登記，統(tǒng)計，并對居民信息進行管理。系統(tǒng)除了以上功能外還要有基本的管理工作，例如添加居民信息，修改居民信息，刪除居民信息等最基本的操作，還有就是通過本系統(tǒng)還可以統(tǒng)計出在在各個教育程度的人數(shù)，方便應用者更加的快捷的做出統(tǒng)計，提高工作效率。　　2.概要設計　　本系統(tǒng)中定義jumininfo結(jié)構(gòu)體類型用于描述居民信息。ju

10、mininfo結(jié)構(gòu)體類型定義格式如下：　　typedef struct　　{　　char num[18];　　char name[21];　　char sex[5];

11、　　char age[4];　　char xueli[11];　　char addr[51];　　char tel[21];　　}jumininfo;　　其中num用于描述居民的身份證號信息，name用于描述居

12、民的姓名信息，sex用于描述居民的性別信息，age用于描述居民的年齡信息，xueli用于描述居民的教育程度信息，addr用于描述居民的地址信息，tel用于描述居民的聯(lián)系方式信息。　　本系統(tǒng)中定義nodetype結(jié)構(gòu)體類型用于建立二叉樹的節(jié)點。nodetype結(jié)構(gòu)體類型定義格式如下：　　typedef struct node<

13、p>　　{　　jumininfo jumin;　　struct node *L;　　struct node *R;　　}nodetype;　　其中jumin用于存儲居民個人信息，*L為指

14、向左孩子的指針，*R為指向右孩子的指針。　　3.詳細設計　　依據(jù)需求分析結(jié)果，居民信息管理系統(tǒng)系統(tǒng)可以分為四個模塊：居民信息查詢模塊、居民信息刪除模塊、居民信息添加模塊和居民信息修改模塊。如下圖所示：　　1. 居民信息查詢模塊　　居民

15、信息查詢模塊主要實現(xiàn)的功能是居民信息的快速查詢。依據(jù)用戶輸入的身份證號查找對應的居民信息。　　2. 居民信息刪除模塊　　居民信息刪除模塊主要實現(xiàn)的功能是對特定居民信息的刪除。　　3. 居民信息添加模塊　　居民信息添加模塊主要是閑的功能是對固定數(shù)量的居民信息的添加。<

16、/p>　　4. 居民信息修改模塊　　居民信息修改模塊主要實現(xiàn)的功能是對特定居民信息的修改。　　5.系統(tǒng)總體流程　　4.調(diào)試分析　　1. 程序設計及過程

17、;　　一、設想將上一次單鏈表的課程設計所編寫的成程序改寫，定義成為二叉樹結(jié)構(gòu)類型。　　結(jié)果：失敗，單鏈表指針指向與二叉樹完全不同，使整個程序指針結(jié)構(gòu)改變工作量變得很大，短時間內(nèi)一人無法完成。　　二、參考書本，重新定義類型結(jié)構(gòu)，取單鏈表課程設計部分顯示函數(shù)進行重新編輯。　　結(jié)果：比較成功，建立

18、了一個以二叉樹結(jié)構(gòu)為基礎的管理系統(tǒng)。　　缺點：將文件存入文件和從文件讀取沒有實現(xiàn)，二叉樹的寫入與單鏈表區(qū)別較大，已經(jīng)找出將樹存入文件的方法，但讀取程序未能編寫成功，因此在本次課程設計中未加入寫入文件模塊。　　目前程序中未能實現(xiàn)的功能除了從文件讀取功能外，還有查找功能。查找功能的程序代碼已經(jīng)編寫完成，但是實際測試中未能達到與其功能，具體問題仍然在分析和De

19、bug中，本次課程設計不便列舉。由于查找功能的缺失，使二叉樹節(jié)點信息的刪除和修改功能也未實現(xiàn)。但本次課程設計的主要目的是成功的建立二叉樹并將其遍歷，鑒于此功能已經(jīng)實現(xiàn)，可以基本確定此次課程設計的基本目的已經(jīng)達到。　　5.測試結(jié)果及運行效果　　進入主菜單，按數(shù)字鍵選擇所需功能：　　選擇錄入居民信息

20、：　　當輸入身份證號不是18位時：　　錄入成功時：　　輸入“#”結(jié)束錄入，返回主菜單。　　選擇顯示居民信息：　　系統(tǒng)自動中序遍歷已建成

21、的二叉樹。　　選擇插入居民信息：　　優(yōu)點：系統(tǒng)自動選擇二叉樹上合適的位置插入信息　　缺點：每次只能插入一個居民信息　　題目二:居民信息管理系統(tǒng)(單鏈表建立含各種排序)算法分析與設計<b&

22、gt;　　1.需求分析　　與題目一相同　　2.概要設計　　本系統(tǒng)中定義jumin結(jié)構(gòu)體類型用于描述居民信息。jumin結(jié)構(gòu)體類型定義格式如下：　　struct jumin<

23、;/p>　　{　　int num;　　char name[20];　　char sex; 　　int age;

24、;　　char xueli[30];　　int wage;　　char addr[30];　　char tel[20];　　}jumin[100]　　其中num用于描述居

25、民的戶籍號信息，name用于描述居民的姓名信息，sex用于描述居民的性別信息，age用于描述居民的年齡信息，xueli用于描述居民的教育程度信息，wage用于描述居民的收入信息，addr用于描述居民的地址信息，tel用于描述居民的聯(lián)系方式信息。　　本系統(tǒng)中定義rectype結(jié)構(gòu)體類型用于建立鏈表，定義格式如下：　　typedef struct</p

26、>　　{　　int key;　　jumininfo info;　　}rectype;　　3.詳細設計</b

27、>　　3.1主函數(shù)模塊　　主函數(shù)模塊主要提供本程序運行的基礎以及供用戶選擇子函數(shù)功能。　　3.1.1. 主函數(shù)模塊描述　　由homepage函數(shù)顯示功能菜單，由用戶選擇需要的功能并連接到對應的功能函數(shù)。&

28、lt;p>　　3.1.2. 主函數(shù)模塊設計實現(xiàn)　　進入程序運行結(jié)果如下截圖：　　若用戶輸入1-7以外的字符，則如下圖：　　3.2錄入居民信息子模塊　　錄入居民信息子模塊主要提供用戶錄入居民信息至系統(tǒng)指定文件并存儲的功能。

29、3.2.1. 錄入居民信息子模塊描述　　經(jīng)由main函數(shù)進入錄入函數(shù)，用戶根據(jù)系統(tǒng)提示按步驟輸入居民信息。　　3.2.2. 錄入居民信息子模塊流程框圖　　3.2.3. 錄入居民信息子模塊設計實現(xiàn)　　進入程序運行結(jié)果如下截圖：　　3

30、.3修改居民信息子模塊　　修改居民信息子模塊主要提供用戶修改已錄入的居民信息并存儲改變的功能。　　3.3.1. 修改居民信息子模塊描述　　經(jīng)由main函數(shù)進入修改函數(shù)，用戶根據(jù)系統(tǒng)提示按步驟選擇需要修改的項目并修改。　　3.3.2. 修改居民信息子模塊流程框圖</p

31、>　　3.3.3. 修改居民信息子模塊設計實現(xiàn)　　當進入系統(tǒng)模塊時未讀取到數(shù)據(jù)庫時　　5秒后系統(tǒng)自動返回主菜單。　　進入系統(tǒng)成功讀取數(shù)據(jù)庫：　　3.4 寫入/讀取信息子模塊　　寫入/讀取信息子模塊主要提

32、供用戶在錄入和編輯信息后將信息存入文件以便下次運行程序繼續(xù)讀取信息的功能。　　此模塊通常在后臺運行，只在讀取或?qū)懭胛募l(fā)生錯誤時顯示"文件打開錯誤!請先錄入信息列表。系統(tǒng)將自動返回主菜單,請稍候... "，并在5秒后自動返回主菜單。　　在進入各模塊時讀取錯誤如下：　　3.5 按年齡直接插入排序

33、子模塊　　按年齡直接插入排序子模塊主要提供用戶在存儲信息后將信息按年齡由小到大順序排序的功能。　　目前還存在在每次排序完成后會在數(shù)據(jù)列表最前端插入一組空數(shù)據(jù)的BUG，且到目前為止并未修復。　　3.6 按戶籍號直接選擇排序子模塊　　按戶籍號直接選擇排序子模塊主要提供用戶在存

34、儲信息后將信息按戶籍號由小到大順序排序的功能。　　目前還存在在每次排序完成后會在數(shù)據(jù)列表最前端插入一組空數(shù)據(jù)的BUG，且到目前為止并未修復。　　總結(jié)　　課程設計終于成功的收尾了,雖然有些疲憊但是頗有收獲,我鞏固了所學到的知識,并動手實踐，更好地理解和運用了數(shù)據(jù)結(jié)構(gòu)的知

35、識。數(shù)據(jù)結(jié)構(gòu)學了近一學期,很多知識掌握得不是很牢,通過平時的復習自己也理解了一些,但讓我有更深的理解和更好的認識則是在這個課程設計。　　通過本次課程設計,復習了上學期的C語言編程知識,學會了怎么去借鑒別人方法和經(jīng)驗,知道了如何整理材料是設計最快的完成這為以后設計畢業(yè)論文打下了基礎。　　此次課程設計鑒于上次的經(jīng)驗我選擇了獨立一人一組。覺得雖然程序編寫有些

36、吃力，但是一個人完成程序時的成就感也加倍了。　　由于臨近期末，復習任務緊張，這次的課程設計完成的還不是很周密，還有很多可以完善的地方，但總的來說已經(jīng)達到我之前預想的程序效果。　　在這次課程設計中，我還幫助了其他小組課程設計的完成，見到了很多的程序錯誤，并幫他們改正，這也鍛煉了我個人在程序debug方面的能力。

37、還著愉快的心情，數(shù)據(jù)結(jié)構(gòu)課程設計結(jié)束了。希望在這次課程設計中所總結(jié)的經(jīng)驗和教訓會讓我以后的課程設計更加順利。　　參考文獻　　[1] 嚴蔚敏.吳偉民著.《數(shù)據(jù)結(jié)構(gòu)》(C語言版). 北京：清華大學出版.1999年第一版　　[2] 陳一華等編. 《數(shù)據(jù)結(jié)構(gòu)》(C 語言). 北京：電

38、子科技大學出版社.1998年第一版　　[3] 譚浩強. 《C語言程序設計（第二版）》.北京：高等教育出版社.2002　　附錄.主要代碼　　題目一　　#include <stdio.h>

39、　　#include <string.h>　　#include <stdlib.h>　　#include <malloc.h>　　#include <windows.h>　　type

40、def struct　　{　　char num[18];　　char name[21];　　char sex[5]; 　　char age[4];

41、　char xueli[11];　　char addr[51];　　char tel[21];　　}jumininfo;　　typedef struct node　　{

42、　　jumininfo jumin;　　struct node *L;　　struct node *R;　　}nodetype;　　typedef nodetype *btree;　　/*void write(b

43、tree k,char * num)　　{　　FILE *fp;　　if((fp=fopen("infolist.txt","a+"))==NULL)<

44、;b>　　{　　printf ("文件打開錯誤!請先錄入信息列表。\n");　　Sleep(3000);　　return;　　}

45、　　if(k)　　{　　fwrite(&k->jumin.num,sizeof(nodetype),1,fp); 　　if(k->L)

46、　　write(k->L,k->L->jumin.num); 　　if(k->R) 　　write(k->R,k->R->jumin.num);　　}　　fclose(f

47、p);　　}*/　　btree bssearch(btree p,char *num)　　{　　while(p!=NULL)　　{<

48、;/b>　　if(strcmp(num,p->jumin.num)==0)　　return p;　　if(strcmp(num,p->jumin.num)<0)　　p=p->L;<

49、/b>　　else p=p->R;　　}　　return p;　　}　　void insert(btre

50、e * root,char * num)　　{　　//FILE *fp;　　btree f,p;　　char name[20],sex[4],age[3],xueli[10],addr[50],tel[20];

51、　　//fp=fopen("infolist.txt","a");　　f=NULL;　　p=*root;　　while(p)

52、;　　{　　if(strcmp(num,p->jumin.num)==0)　　{　　printf("該身份證號居民信息已存在,請重新輸入!\n");

53、　　return;　　}　　f=p;　　p=(strcmp(num,p->jumin.num)<0)?p->L:p->R;<b&

54、gt;　　}　　p=(btree)malloc(sizeof(nodetype));　　strcpy(p->jumin.num,num);　　printf("請輸入姓名(少于10個漢字)：\n");　　scanf("

55、%s",name);　　strcpy(p->jumin.name,name);　　printf("請輸入性別(男或女)：\n");　　scanf("%s",sex);　　strcpy(p->jumin.sex,

56、sex);　　printf("請輸入年齡(少于3個數(shù)字)：\n");　　scanf("%s",age);　　strcpy(p->jumin.age,age);　　printf("請輸入學歷(少于5個漢字)：\n&qu

57、ot;);　　scanf("%s",xueli);　　strcpy(p->jumin.xueli,xueli);　　printf("請輸入家庭住址(少于25個漢字)：\n");　　scanf("%s",ad

58、dr);　　strcpy(p->jumin.addr,addr);　　printf("請輸入電話號碼(少于20個數(shù)字或字符)：\n");　　scanf("%s",tel);　　strcpy(p->jumin.tel,te

59、l);　　p->L=NULL;　　p->R=NULL;　　if(*root==NULL)　　*root=p;　　else

60、　　{　　if(strcmp(num,f->jumin.num)<0)　　f->L=p;　　else

61、　f->R=p;　　}　　//write(p,p->jumin.num);　　/*while(p->L)　　{　　i

62、f (fwrite(&p->jumin.num,sizeof(nodetype),1,fp)!=1)　　printf("File write error!\n");　　if(p->L)　　p=p->L;</

63、b>　　else　　if(p->R)　　p=p->R;　　}*/<p&g

64、t;　　//fclose(fp);　　}　　/*void read(btree k,char *num)　　{　　FILE *fp;

65、　　if((fp=fopen("infolist.txt","a+"))==NULL)　　{　　printf ("文件打開錯誤!請先錄入信息列表。\n");　　Sleep(3000);</p&

66、gt;　　return;　　}　　if((fread(&k->jumin.num,sizeof(nodetype),1,fp))!=1)　　exit(0);<

67、/p>　　insert(&k,k->jumin.num);　　if(k->L)　　read(k->L,k->L->jumin.num);　　if(k->R)

68、　read(k->R,k->R->jumin.num);　　fclose(fp);　　}*/　　void inorder(btree t)//中序遍歷　　{

69、　　//read(t,t->jumin.num);　　if(t)　　{　　inorder(t->L);　　printf(" 戶籍號\t 姓名\t\

70、t 性別\t\t年齡 \n");　　printf("\n %s\t\t %s\t\t %s\t\n",t->jumin.num,t->jumin.sex,t->jumin.age);　　printf("\n 學歷\t\t 住址\t\t電話 \n");</p&g

71、t;　　printf("\n %s\t\t %s\t\t%s\n",t->jumin.xueli,t->jumin.addr,t->jumin.tel);　　inorder(t->R);　　}<b

72、>　　}　　btree createbtree(void)　　{　　btree root;　　char num[19];　　root=NULL;

73、　　printf("\n請輸入18位身份證號,輸入#取消錄入\n");　　scanf("%s",num);　　while(strcmp(num,"#")!=0)　　{<

74、;p>　　while(strlen(num)!=18)　　{　　printf("錯誤!輸入的身份證號不是18位,請重新輸入:\n");　　scanf("%s",num);

75、　　}　　insert(&root,num);　　printf("\n請輸入18位身份證號,輸入#取消錄入\n");　　scanf("%s",num);　　}<

76、/p>　　return root;　　}　　btree Delete(btree bt,char *num)　　{　　btree p,q;<

77、;p>　　if(strcmp(bt->jumin.num,num)==0)　　{　　if(bt->L==NULL&&bt->R==NULL)　　{<b

78、>　　free(bt);　　return NULL;　　}　　else　　if(bt->L==NULL)

79、　　{　　p=bt->R;　　free(bt);　　return p;　　}

80、;　　else　　if(bt->R==NULL)　　{　　p=bt->L;　　free(bt);</

81、b>　　return p;　　}　　else　　{　　p=q=bt-&g

82、t;R;　　while(q->L!=NULL)　　q=q->L;　　q->L=bt->L;　　free(bt);

83、　　return p;　　}　　}　　else　　{　　i

84、f(strcmp(bt->jumin.num,num)>0&&bt->L!=NULL)　　bt->L=Delete(bt->L,num);　　if(strcmp(bt->jumin.num,num)<0&&bt->R!=NULL)

85、bt->R=Delete(bt->R,num);　　return bt;　　}　　}　　void quit()　　{(略)}

86、　　void homepage() /*菜單函數(shù)*/　　{(略)}　　void main()　　{(略)}　　題

87、目二　　此處只給出排序函數(shù)，其他部分同C語言課程設計　　void insertsort(rectype r[])//按年齡直接插入排序　　{　　int i,j;</p&g

88、t;　　int m=load();　　printf("\n 原來的居民信息:\n");　　display();　　printf("\n\n\n\n");　　for(i=1;i<m;i++)</p&g

89、t;　　{　　r[i].key=r[i].info.age;　　}　　for(i=2;i<=m;i++)　　{r[m+1]=r[i];<p

90、>　　j=i-1;　　while(r[m+1].key<r[j].key)　　{r[j+1]=r[j--];　　r[j+1]=r[m+1];　　}save(m+1);　　}prin

91、tf("\n 排序后的居民信息:\n");　　display();}　　void selectsort(rectype r[])//按戶籍號直接選擇排序　　{rectype x;　　int m=load();

92、　int i,j,k;　　printf("\n 原來的居民信息:\n");　　display();　　for(i=0;i<m;i++)　　{r[i].key=r[i].info.num; };　　for(

93、i=0;i<m;i++)　　{k=i;　　for(j=i+1;j<=m;j++)　　if(r[j].key<r[k].key)　　k=j;

94、;　　if(k!=i)　　{x=r[i];　　r[i]=r[k];　　r[k]=x;　　}save(m+1)；}

眾賞文庫> 全部分類> 畢業(yè)設計

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
4. 未經(jīng)權益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負責。
6. 下載文件中如有侵權或不適當內(nèi)容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

數(shù)據(jù)結(jié)構(gòu)課程設計--二叉樹的遍歷算法分析與設計

文檔簡介

溫馨提示

最新文檔

評論

數(shù)據(jù)結(jié)構(gòu)課程設計--二叉樹的遍歷算法分析與設計

文檔簡介

溫馨提示

最新文檔

評論

免費下載