二叉平衡樹實現(xiàn)學(xué)生信息管理系統(tǒng)

1、 課程設(shè)計報告( 20112012年度第2學(xué)期)實驗名稱：數(shù)據(jù)結(jié)構(gòu)與算法 題 目：二叉平衡樹學(xué)生信息管理系統(tǒng) 院 系：控制與計算機(jī)工程學(xué)院 班 級：信安1101 學(xué) 號：1111290110 學(xué)生姓名：黃世晨 指導(dǎo)教師：焦?jié)櫤?設(shè)計周數(shù)： 1周 成 績： 日期： 2012年 6 月 28 日18 / 20文檔可自由編輯打印一、課程設(shè)計的目的與要求1 目的: 應(yīng)用數(shù)據(jù)結(jié)構(gòu)和算法來設(shè)計相應(yīng)的程序，培養(yǎng)學(xué)生問題求解模塊的框架設(shè)計和詳細(xì)設(shè)計、相關(guān)程序?qū)崿F(xiàn)和調(diào)試能力，完成創(chuàng)新能力和實踐能力的訓(xùn)練。2 要求: 用高級程序設(shè)計語言C編碼，用VC+開發(fā)平臺調(diào)試。二、設(shè)計正文（一） 課程設(shè)計題目（二） 需求分析

2、（三） 概要設(shè)計（四） 詳細(xì)設(shè)計（五） 調(diào)試分析（六） 使用說明三、課程設(shè)計總結(jié)或結(jié)論1 完成的工作2 未完成的工作3 所需做的改進(jìn)四、參考文獻(xiàn) 1 作者1, 作者2. 書名. 出版單位, 版本. 出版日期附錄（設(shè)計流程圖、程序、測試數(shù)據(jù)等） 一、課程設(shè)計題目編制一個用二叉平衡樹實現(xiàn)學(xué)生信息管理系統(tǒng)的程序，所有信息用文件保存。二、需求分析本演示程序在VC+環(huán)境下用C語言編寫，利用二叉平衡樹完成學(xué)生信息管理系統(tǒng)信息的輸入，顯示所有的學(xué)生信息，查詢指定學(xué)生信息，刪除學(xué)生信息，并將所有信息以TXT文檔形式保存。1、 輸入的形式和輸入值的范圍：創(chuàng)建時首先按照要求依次輸入相應(yīng)信息；插入結(jié)點時需要輸入插入

3、的信息；刪除結(jié)點時輸入刪除結(jié)點的關(guān)鍵字；查找時輸入查找結(jié)點的關(guān)鍵字；在所有輸入中，結(jié)點信息學(xué)號、姓名、專業(yè)、班級、生日為字符串，年齡為整型。2、 輸出的形式：查找操作會輸出查找成功時的信息，若不成功怎輸出無此信息；顯示操作會按遞歸遍歷顯示平衡樹上的所有結(jié)點信息；3、 程序所能達(dá)到的功能：完成二叉平衡樹學(xué)生信息管理系統(tǒng)的創(chuàng)建（從鍵盤中輸入并保存到文件中）、插入、刪除、查找、顯示、保存操作4、測試數(shù)據(jù)：A 創(chuàng)建操作中依次輸入 101 黃世晨 信安 1101 19 1993 y 02 許彬 信安 1101 20 1992 y 03 鄧志光 信安 1101 20 1992 n 構(gòu)建二叉平衡樹 輸入 4

4、 瀏覽信息B 查找操作中依次輸入 5 01C 刪除操作中依次輸入 3 03D插入操作中依次輸入 2 04 曹廷祥 信安 1101 21 1991 輸入 4 瀏覽信息E 凹入顯示操作輸入 7F 保存操作輸入 6G 退出操作輸入 0三、概要設(shè)計 1、為了實現(xiàn)上述程序功能，需要定義二叉平衡樹的抽象數(shù)據(jù)類型：ADT BSTree 數(shù)據(jù)對象D：D是具有相同特性的數(shù)據(jù)元素的集合。 數(shù)據(jù)關(guān)系R：若D為空集，則稱為空樹； 否則: (1) 在D中存在唯一的稱為根的數(shù)據(jù)元素root, (2) 當(dāng)n>1時，其余結(jié)點可分為m (m>0)個互 不相交的有限集T1, T2, , Tm, 其中每一 棵子集本身又

5、是一棵符合本定義的樹， 稱為根root的子樹。基本操作：void creat(T_N &T)操作結(jié)果：創(chuàng)建學(xué)生信息管理系統(tǒng)二叉平衡樹并輸入初始信息.int insertavl(T_N &T,STU data)操作結(jié)果：將信息插入至二叉平衡樹中，并調(diào)節(jié)二叉樹平衡int find(T_N T,char *x,T_N &f,T_N &c)初始條件：二叉平衡樹T已存在操作結(jié)果：查詢學(xué)生信息 int Deleteavl(T_N &T,char *xuehao)初始條件：二叉平衡樹T已存在操作結(jié)果：刪除學(xué)生信息，并調(diào)節(jié)二叉樹平衡 int disp(T_N T) 初始

6、條件：二叉平衡樹T已存在操作結(jié)果：顯示學(xué)生信息int menu()操作結(jié)果：在屏幕上顯示操作菜單 2、本程序包含16個函數(shù)：1 主函數(shù) main()2 刪除結(jié)點并調(diào)平函數(shù)Deleteavl(T_N &,char * );3 刪除輔助函數(shù)Del(T_N ,T_N &);4 調(diào)平函數(shù)LLbalance(T_N &);5 調(diào)平函數(shù)RRbalance(T_N &);6 調(diào)平函數(shù)LRbalance(T_N &);7 調(diào)平函數(shù)RLbalance(T_N &);8 查找函數(shù)find(T_N ,char *,T_N &,T_N &);9 插入信息

7、并調(diào)平函數(shù)insertavl(T_N &,STU);10 在右子樹上刪除后的調(diào)平函數(shù)Rightadjust(T_N &);11 在左子樹上刪除后的調(diào)平函數(shù)Leftadjust(T_N &);12 菜單函數(shù)menu();13 保存函數(shù)save(T_N,FILE *);14 凹入顯示二叉平衡樹函數(shù)print(T_N ,int );15 創(chuàng)建函數(shù)creat(T_N &);16 顯示函數(shù)disp(T_N );3、函數(shù)間的調(diào)用關(guān)系如下：mainmenucreatinsertavlDeleteavldispfindsaveprint四、詳細(xì)設(shè)計為了實現(xiàn)概要設(shè)計中定義的所有的

8、數(shù)據(jù)類型；對主程序和其他模塊寫出偽代碼算法或者畫出流程圖； 1、結(jié)點類型和指針類型/結(jié)構(gòu)體定義/學(xué)生typedef structchar xuehao10;char name20;char zhuanye10;char banji20;char shengri20;int age;STU;/結(jié)點typedef struct TreeNodeSTU data;struct TreeNode *lchild,*rchild;int ph;TreeNode,*T_N;2)、主要算法的偽代碼或者流程圖/保存int save(T_N T,FILE *fp)if(T=NULL)return 0;elsef

9、printf(fp,"%st%st%st%st%dt%st",T->data.xuehao,T->,T->data.zhuanye,T->data.banji,T->data.age,T->data.shengri);save(T->lchild,fp);save(T->rchild,fp);/插入int insertavl(T_N &T,STU data)if(T=NULL)T=new TreeNode; T->data=data;T->lchild=T->rchild=NULL;

10、T->ph=0;return flag=1;/如果是空的話就生成新節(jié)點并且返回1elseresult=strcmp(T->data.xuehao,data.xuehao);if(result=0)puts("該學(xué)號學(xué)生已經(jīng)存在，不能插入");getch();flag=0;else if(result<0)/往右子樹方向上插入flag=insertavl(T->rchild,data);/這里傳過去的是根的右子樹if(flag=1)switch(T->ph)case 1:T->ph=0;flag=0;break;/直接插入并改變平衡因子，并

11、且改變標(biāo)識變量flagcase 0:T->ph=-1;break;/直接插入并改變平衡因子即可case -1:if(T->rchild->ph=-1)RRbalance(T);/1，注意分清楚這里面的根結(jié)點T->ph=T->lchild->ph=0;/左旋之后并進(jìn)行平衡因子的更改else if(T->rchild->ph=1)if(T->rchild->lchild->ph=0)T->ph=T->rchild->ph=0;/7,注意分清這里面的根結(jié)點else if(T->rchild->lchild

12、->ph=1)T->ph=0;T->rchild->ph=-1;T->rchild->lchild->ph=0;/3,注意分清這里面的根結(jié)點if(T->rchild->lchild->ph=-1)T->ph=1;T->rchild->ph=0;T->rchild->lchild->ph=0;/2,注意分清這里面的根結(jié)點RLbalance(T);/這里要分情況討論是因為旋轉(zhuǎn)過后平衡因子的改變是不一樣的flag=0;break;return flag;else if(result>0)/往左子樹方

13、向上插入flag=insertavl(T->lchild,data);if(flag=1)switch(T->ph) case 0:T->ph=1;flag=1;break;case -1:T->ph=0;flag=0;break;case 1:if(T->lchild->ph=1)LLbalance(T);T->ph=T->rchild->ph=0;/4,注意分清這里面的根結(jié)點if(T->lchild->ph=-1)if(T->lchild->rchild->ph=-1)T->ph=0;T->lc

14、hild->ph=1;T->lchild->rchild->ph=0;/5,注意分清這里面的根結(jié)點if(T->lchild->rchild->ph=1)T->ph=-1;T->lchild->ph=0;T->lchild->rchild->ph=0;/6,注意分清這里面的根結(jié)點if(T->lchild->rchild->ph=0)T->ph=T->lchild->ph=0;/8,注意分清這里面的根結(jié)點LRbalance(T);flag=0;break;return flag;/查找

15、int find(T_N T,char *x,T_N &f,T_N &c)/T為已經(jīng)存在的樹，x為要查找的數(shù)據(jù)，f,c為將要返回的指針 if(T=NULL)return 0;if(strcmp(T->data.xuehao,x)=0)c=T;return 1;/用返回值來區(qū)別是否找到else if(strcmp(T->data.xuehao,x)<0)/由于根節(jié)點上的數(shù)據(jù)“小于”x的數(shù)據(jù)，因此到根節(jié)點的右子樹上尋找 f=T;returnfind(T->rchild,x,f,c);/f應(yīng)該記得也就是T了else f=T;return find(T->

16、lchild,x,f,c);/刪除int Deleteavl(T_N &T,char *xuehao)if(T=NULL)puts("沒有該學(xué)生");getch();return 0;result=strcmp(T->data.xuehao,xuehao);if(result>0)/往左子樹方向上刪除flag=Deleteavl(T->lchild,xuehao);if(flag=1)flag=Leftadjust(T);else if(result<0)/往右子樹方向上刪除flag=Deleteavl(T->rchild,xuehao

17、);if(flag=1)flag=Rightadjust(T);elseif(T->lchild=NULL)p=T;T=T->rchild;delete p; flag=1;else if(T->rchild=NULL)p=T;T=T->lchild;delete p;flag=1;elseflag=Del(T,T->lchild);if(flag=1)Leftadjust(T);return flag;return 0;/顯示int disp(T_N T)if(T=NULL)return 0;elsedisp(T->lchild);printf("

18、;學(xué)號：%st姓名：%st專業(yè)：%st班級：%st生日：%st年齡：%dn",T->data.xuehao,T->,T->data.zhuanye,T->data.banji,T->data.shengri,T->data.age);disp(T->rchild);/創(chuàng)建void creat(T_N &T)do puts("輸入學(xué)生n學(xué)號 姓名 專業(yè) 班級 年齡 生日:"); scanf("%s%s%s%s%d%s",x.xuehao,,x.zhuanye,x.ba

19、nji,&x.age,x.shengri);getchar();insertavl(T,x); printf("是否繼續(xù)（y/n）：");ch=getchar();while(ch='Y' | ch='y');void print(T_N T,int indent) if(T=NULL ) return;elsefor(i=0;i<indent;i+)printf("-");printf("學(xué)號：%st姓名：%st專業(yè)：%st班級：%st生日：%st年齡：%dn",T->data.x

20、uehao,T->,T->data.zhuanye,T->data.banji,T->data.shengri,T->data.age);print(T->lchild,indent+1);print(T->rchild,indent+1);五、 調(diào)試分析1、原程序在結(jié)束創(chuàng)建時需輸入五次#才能結(jié)束，后調(diào)整為“y/n”判斷是否繼續(xù)。六、使用說明程序名為二叉平衡樹_學(xué)生信息管理系統(tǒng).exe，運(yùn)行環(huán)境為VC+。程序執(zhí)行后顯示 +-+ | | | 歡迎使用學(xué)生信息管理系統(tǒng) | | | +-+ 溫馨提示：為保證您的操作得到保存，請按正常順序退出系統(tǒng)