全線索鏈表應(yīng)用

1、實驗三 全線索鏈表應(yīng)用問題定義及需求分析1.1課題目的和任務(wù)問題描述：對二叉樹的二叉鏈表結(jié)點增加兩個指針域，前驅(qū)指針prior和后繼指針next。通過該結(jié)點構(gòu)造全線索二叉鏈表。實驗要求：設(shè)計一個全線索二叉鏈表的應(yīng)用程序。1)創(chuàng)建全線索二叉樹。2)完成全線索二叉樹的主要基本操作。3)給出簡單應(yīng)用實例1.2數(shù)據(jù)形式輸入數(shù)據(jù)形式：通過鍵盤輸入數(shù)據(jù)輸入值的范圍：輸入值的范圍均為float型，范圍為1.2e-38至3.4e+38。 輸出數(shù)據(jù)形式：輸出到顯示器。1.3程序功能將全線索作用于二叉排序樹中，通過對其進(jìn)行中序遍歷線索化，實現(xiàn)通過線索搜索某個節(jié)點的前驅(qū)和后繼，并且利用線索，實現(xiàn)對整個樹中數(shù)據(jù)的中序

2、線索輸出，并且能夠在刪除樹中某個節(jié)點后，實現(xiàn)對該樹的重新線索化。1.4測試數(shù)據(jù)7 /樹中元素的個數(shù)5 2 7 1 3 6 8 /依次輸入的樹中元素值3 /需要輸出前驅(qū)和后繼的元素值7 /刪除的元素值8 /重新線索化后，需要輸出前驅(qū)和后繼的元素值1. 概要設(shè)計2.1抽象數(shù)據(jù)類型需要定義一個全線索二叉樹，該樹中含有數(shù)據(jù)，左右孩子，以及分別指向前驅(qū)和后繼的指針。通過前驅(qū)和后繼指針，將建立的二叉樹中序線索化，從而實現(xiàn)對數(shù)據(jù)更方便和快速的獲取。2.2主程序流程及各模塊之間的調(diào)用關(guān)系2. 詳細(xì)設(shè)計3.1存儲結(jié)構(gòu)實現(xiàn)typedef struct Type/數(shù)據(jù)類型結(jié)構(gòu)體聲明 float num;Type;t

3、ypedef struct BiTNode/二叉樹結(jié)構(gòu)體聲明 struct Type data; struct BiTNode* lchild,* rchild,* prior,* next;BiTNode,*BiTree;3.2負(fù)責(zé)模塊的偽碼算法（1）int visit(Type e,BiTree T)/找到相同元素并返回它的前驅(qū)和后繼 if(T-data =e) return 1; else return 0;（2）const int InOrderTraverse_Thr(BiTree T,Type e,int (*visit)(Type e,BiTree T),Type& prior,

4、Type& next)/中序遍歷二叉排序線索樹，并返回符合visit函數(shù)的元素的前驅(qū)和后繼 B=T-next; while(B非空且不等于T) if(visit(e,B)/找到等于e的B結(jié)點值 if(B前驅(qū)等于T) next=B-next-data;/B只有后繼 return 2; else if(B后繼等于T) prior=B-prior-data;/B只有前驅(qū) return 3; else/B前驅(qū)和后繼都不等于T (prior,next)=(B-prior-data,B-next-data); return 1;/前驅(qū)和后繼都存在 B=B-next; return 0;（3）const i

5、nt SearchPN(BiTree Thrt,BiTree T)/利用全線索查找所需元素的前驅(qū)和后繼 cine;/輸入要查找的元素m=InOrderTraverse_Thr(Thrt,e,(*visit),prior,next);/全線索中序查找某個元素的前驅(qū)和后繼 if(m=1)輸出前驅(qū)和后繼 else if(m=2)前驅(qū)不存在，輸出后繼 else if(m=3)后繼不存在，輸出前驅(qū) else查找失敗，樹中無該元素 return 1;3. 調(diào)試分析4.1問題分析與解決方法對于給定輸入數(shù)，查找它的前驅(qū)和后繼，需要考慮該數(shù)是否存在前驅(qū)和后繼，如果沒有前驅(qū)和后繼，則需要輸出不存在標(biāo)志。利用線索指

6、針很容易進(jìn)行判斷，如果需要查找的元素的前驅(qū)是線索的頭（線索的頭是個空結(jié)點），那么該元素就不存在前驅(qū)，只存在后繼；而如果需要查找的元素的后繼是線索的頭，那么它就不存在后繼，只有前驅(qū)。因此通過if進(jìn)行判斷，就可以成功輸出需要查詢的元素的前驅(qū)和后繼。4.2算法的時空分析在樹中查找某個元素并輸出該元素的前驅(qū)和后繼的整個時間復(fù)雜度最多為，空間復(fù)雜度為。4.3算法的改進(jìn)設(shè)想 全線索的應(yīng)用主要是為了方便樹的遍歷，能夠快速的訪問某個節(jié)點的前驅(qū)和后繼，因此可以考慮將線索應(yīng)用于平衡二叉樹上，從而進(jìn)一步提高平衡二叉樹獲取數(shù)據(jù)的速度。4.4經(jīng)驗和體會 在整個程序的編寫過程中，出現(xiàn)一個問題，如果是首次線索化，便可以通過

7、線索成功輸出該樹，但當(dāng)刪除某個節(jié)點后，再次進(jìn)行線索化，然后利用線索輸出該樹就無法得到完整的樹。后來經(jīng)過調(diào)試發(fā)現(xiàn)，由于第一次的線索化，該樹內(nèi)的各個線索指針已被賦值，所以第二次線索化實際上是失敗的，因此需要先對樹進(jìn)行去線索化操作（把線索指針指空）后，再對其進(jìn)行線索化，這樣才能輸出正確的數(shù)據(jù)。 可見，程序各個模塊之間的影響不容小覷，必須對程序各個模塊的功能和影響有個整體的把握才不至于出現(xiàn)不合設(shè)想的錯誤。4. 使用說明按照操作提示，通過鍵盤輸入數(shù)據(jù)即可。輸入的節(jié)點數(shù)據(jù)可以為小數(shù)，但是數(shù)量數(shù)據(jù)必須為正整數(shù)。5. 測試結(jié)果（截屏）（1）前驅(qū)和后繼都存在的數(shù)：（2）只存在前驅(qū)的數(shù)：（3）只存在后繼的數(shù)：6.

8、 附錄7.1個人負(fù)責(zé)模塊的程序代碼int visit(Type e,BiTree T)/找到相同元素并返回它的前驅(qū)和后繼 if(T-data.num=e.num) return 1; else return 0;const int InOrderTraverse_Thr(BiTree T,Type e,int (*visit)(Type e,BiTree T),Type& prior,Type& next)/中序遍歷二叉排序線索樹，并返回符合visit函數(shù)的元素的前驅(qū)和后繼 BiTree B=T-next; while(B!=NULL&B!=T) if(visit(e,B) if(B-prio

9、r=T)/該點的前驅(qū)為T，說明它無前驅(qū) next.num=B-next-data.num; return 2; else if(B-next=T)/該點的后繼為T，說明它無后繼 prior.num=B-prior-data.num; return 3; else/該點既有前驅(qū)也有后繼 prior.num=B-prior-data.num; next.num=B-next-data.num; return 1; B=B-next; return 0;const int SearchPN(BiTree Thrt,BiTree T)/利用全線索查找所需元素的前驅(qū)和后繼 Type e,prior,ne

10、xt; int m; coutPlease input a number to be searched and print its prior and next:e.num; m=InOrderTraverse_Thr(Thrt,e,(*visit),prior,next);/全線索中序查找某個元素的前驅(qū)和后繼 if(m=1)/前驅(qū)和后繼均有的情形 coutThe prior of number e.num is prior.num,; coutand its next is next.num.endl; else if(m=2)/只有后繼的情形 coutThe prior of number

11、 e.num is not existed,; coutand its next is next.num.endl; else if(m=3)/只有前驅(qū)的情形 coutThe prior of number e.num is prior.num,; coutand its next is not existed.endl; else/未找到該數(shù)的情形 coutThe number searched is not existedendl; return 1;7.2程序全部代碼#include#includeusing namespace std;typedef struct Type/數(shù)據(jù)類型結(jié)

12、構(gòu)體聲明 float num;Type;typedef struct BiTNode/二叉排序樹結(jié)構(gòu)體聲明 struct Type data; struct BiTNode* lchild,* rchild,* prior,* next;BiTNode,*BiTree;int InitTree(BiTree& T,Type e)/創(chuàng)建二叉排序樹 T=(BiTree)malloc(sizeof(BiTNode); if(!T)return 0; T-data.num=e.num; T-lchild=T-rchild=NULL; T-prior=T-next=NULL; return 1;int

13、DestroyTree(BiTree& T)/遞歸銷毀二叉排序樹 if(T=NULL) return 0; DestroyTree(T-lchild); DestroyTree(T-rchild); free(T); return 1;int SearchTree(BiTree T,Type key,BiTree& p)/非遞歸算法，搜索二叉排序樹中元素 while(T) if(key.num=T-data.num)p=T;return 1; else if(key.numdata.num) p=T; T=T-lchild; else p=T; T=T-rchild; return 0;int

14、 InsertTree(BiTree& T, Type e)/二叉排序樹中元素插入 BiTree p; if(!SearchTree(T,e,p) BiTree s; s=(BiTree)malloc(sizeof(BiTNode); s-data.num=e.num; s-lchild=s-rchild=NULL; s-prior=s-next=NULL; if(!p)T=s; else if(e.numdata.num) p-lchild=s; else p-rchild=s; return 1; coutThe number has been existed!data.num) Dele

15、te(T); return 1; else if(e.numdata.num) DeleteTree(T-lchild,e); elseDeleteTree(T-rchild,e); return 1;int Delete(BiTree& p)/結(jié)點刪除算法 if(!p-lchild)/沒有左孩子 BiTree q; q=p; p=p-rchild; free(q); else if(!p-rchild)/沒有右孩子 BiTree q; q=p; p=p-lchild; free(q); else/兩個孩子都有 BiTree q,s; q=p; s=p-lchild; while(s-rchi

16、ld) q=s; s=s-rchild; p-data.num=s-data.num; if(q!=p) q-rchild=s-lchild; elseq-lchild=s-lchild; free(s); return 1;int visit(Type e,BiTree T)/找到相同元素并返回它的前驅(qū)和后繼 if(T-data.num=e.num) return 1; else return 0;const int InOrderTraverse_Thr(BiTree T,Type e,int (*visit)(Type e,BiTree T),Type& prior,Type& next

17、)/中序遍歷二叉排序線索樹，并返回符合visit函數(shù)的元素的前驅(qū)和后繼 BiTree B=T-next; while(B!=NULL&B!=T) if(visit(e,B) if(B-prior=T) next.num=B-next-data.num; return 2; else if(B-next=T) prior.num=B-prior-data.num; return 3; else prior.num=B-prior-data.num; next.num=B-next-data.num; return 1; B=B-next; return 0;int InOrderThreadin

18、g(BiTree& Thrt,BiTree& T)/中序遍歷二叉排序樹T，并將其線索化,頭結(jié)點為Thrt void InThreading(BiTree& ,BiTree& ); if(!T)return 0; else Thrt=(BiTree)malloc(sizeof(BiTNode); Thrt-next=Thrt-prior=NULL; BiTree pre; pre=Thrt; InThreading(T,pre); pre-next=Thrt; Thrt-prior=pre; return 1;void InThreading(BiTree& T,BiTree& pre)/將結(jié)點

19、線索化 if(T) InThreading(T-lchild,pre); if(T-prior=NULL)T-prior=pre; if(pre-next=NULL)pre-next=T; pre=T; InThreading(T-rchild,pre); const int InOrderThrPrint(BiTree Thrt)/中序線索遍歷輸出樹 if(!Thrt) return 0; BiTree B=Thrt-next; while(B!=Thrt) coutdata.numnext; coutendl; return 1;const int SearchPN(BiTree Thrt

20、,BiTree T)/利用全線索查找所需元素的前驅(qū)和后繼 Type e,prior,next; int m; coutPlease input a number to be searched and print its prior and next:e.num; m=InOrderTraverse_Thr(Thrt,e,(*visit),prior,next);/全線索中序查找某個元素的前驅(qū)和后繼 if(m=1) coutThe prior of number e.num is prior.num,; coutand its next is next.num.endl; else if(m=2) coutThe prior of number e.num is not existed,; coutand its next is next.num.endl; else if(m=3) coutThe prior of number e.num is prior.num,; coutand its next is not existed.endl; else coutThe number searched is not existednext=T-prior=NULL; RemoveThr(T-lchild); RemoveThr(T-rchild); r