《大數(shù)據(jù)結(jié)構(gòu)》課程實(shí)驗(yàn)報(bào)告材料

《《大數(shù)據(jù)結(jié)構(gòu)》課程實(shí)驗(yàn)報(bào)告材料》由會(huì)員分享，可在線閱讀，更多相關(guān)《《大數(shù)據(jù)結(jié)構(gòu)》課程實(shí)驗(yàn)報(bào)告材料（39頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、word 4 實(shí)驗(yàn)一 基于二叉鏈表的二叉樹的實(shí)現(xiàn) 4.1 問題描述 基于二叉鏈表和隊(duì)列與其堆棧存儲(chǔ)結(jié)構(gòu)，實(shí)現(xiàn)二叉鏈表的二叉樹的對(duì)數(shù)據(jù)進(jìn)展各種必要的操作。 4.2 系統(tǒng)設(shè)計(jì) 1提供20個(gè)功能，分別是： 1.2.2二叉鏈表的結(jié)構(gòu)試一堆棧和隊(duì)列的形式進(jìn)展儲(chǔ)存的分別是： 1.2.3在程序中所定義的數(shù)據(jù)結(jié)構(gòu)有： 2.3 系統(tǒng)實(shí)現(xiàn) InitTree功能 初始二叉鏈表，傳入的是頭結(jié)點(diǎn)地址。申請(qǐng)一個(gè)存儲(chǔ)空間，并用頭結(jié)點(diǎn)中的首結(jié)點(diǎn)指針指向該空間首地址，相應(yīng)的 時(shí)間復(fù)雜度為1。具體實(shí)現(xiàn)如下： DestroyTree功能 銷毀頭結(jié)點(diǎn)中首結(jié)點(diǎn)址針指向的線性存

2、儲(chǔ)空間，傳入的是頭結(jié)點(diǎn)地址。具體實(shí)現(xiàn)如下： 與DestroyBiTree類似但是又有不同，ClearBiTree并不銷毀物理空間，而是修改邏輯關(guān)系值： 與DestroyBiTree類似但是又有不同，ClearBiTree并不銷毀物理空間，而是修改邏輯關(guān)系值 判空功能，判斷表是否為空表。時(shí)間復(fù)雜度為1，因?yàn)橹恍枧袛嘁淮尉涂梢灾朗欠駷榭?。?shí)現(xiàn)如下： 求二叉鏈表深度的功能，由于創(chuàng)建過程中已經(jīng)把表長(zhǎng)信息包含在頭結(jié)點(diǎn)中，所以直接調(diào)用并顯示即可 1.3.7Root(BiTree T)功能 獲取二叉鏈表的根節(jié)點(diǎn)的元素，通過遍歷二叉鏈表

3、中的元素，來逐個(gè)判斷，時(shí)間復(fù)雜度為〔n〕。 1.3.8Value(BiTree T,TElemType e)功能 求指定元素的前一個(gè)元素的內(nèi)容，傳入頭結(jié)點(diǎn)值、包含指定元素信息的一個(gè)臨時(shí)表結(jié)點(diǎn)值、存儲(chǔ)前一個(gè)元素的表結(jié)點(diǎn)地址。主要思路是遞歸算法。時(shí)間復(fù)雜度為O(n)。具體實(shí)現(xiàn)如下： 求指定元素的后一個(gè)元素的內(nèi)容，傳入頭結(jié)點(diǎn)值、包含指定元素信息的一個(gè)臨時(shí)表結(jié)點(diǎn)值、存儲(chǔ)前一個(gè)元素的表結(jié)點(diǎn)地址。找到后，把新的數(shù)據(jù)值賦給所找到的節(jié)點(diǎn)。時(shí)間復(fù)雜度為O(n)。具體實(shí)現(xiàn)如下： Parent功能 找雙親節(jié)點(diǎn)，找到后輸出 查找左孩子，利用遞歸的算法，與遍歷

4、的時(shí)間復(fù)雜度為一樣O(n) 查找右孩子，利用遞歸的算法，與遍歷的時(shí)間復(fù)雜度為一樣O(n) 查找節(jié)點(diǎn)的左邊的堂兄弟的，找到后輸出該節(jié)點(diǎn)的數(shù)據(jù) 查找節(jié)點(diǎn)的右邊的堂兄弟的，找到后輸出該節(jié)點(diǎn)的數(shù)據(jù) 函數(shù) 在二叉鏈表中插入新的節(jié)點(diǎn) 刪除指定編號(hào)的數(shù)據(jù)元素，傳入頭結(jié)點(diǎn)地址、編號(hào)i、表結(jié)點(diǎn)類型結(jié)構(gòu)體地址來返回被刪除元素內(nèi)容。執(zhí)行前先判斷傳入的編號(hào)是否在可尋找X圍內(nèi)。執(zhí)行刪除操作之后，進(jìn)展“移位〞運(yùn)算。時(shí)間復(fù)雜度仍為O(n)。如下： 前序遍歷二叉鏈表中的數(shù)據(jù)，采用先遍歷左孩子，再訪問根節(jié)點(diǎn)，后訪問右孩子的思想來實(shí)現(xiàn)前序遍歷的算法的。

5、 中序遍歷的函數(shù)，對(duì)二叉鏈表的數(shù)據(jù)進(jìn)展訪問，并且利用PreOrderTraverse函數(shù) 采用后續(xù)遍歷的思想，利用先序遍歷的函數(shù)進(jìn)展 完全遍歷二叉鏈表中的數(shù)據(jù)，并進(jìn)展輸出的 定位節(jié)點(diǎn)的函數(shù)，在需要查找二叉鏈表二叉樹的節(jié)點(diǎn)的時(shí)候，可以直接調(diào)用該函數(shù)，進(jìn)展處理，相應(yīng)的代碼如下 1.3.21FILE * fileOpen功能 讀取功能，通過fscanf實(shí)現(xiàn)格式化讀取，同時(shí)結(jié)合CreateList函數(shù)實(shí)現(xiàn)順序 1.3.22BiTNode * Create(FILE *fp)功能 把二叉鏈表二叉樹的數(shù)據(jù)寫入到文件中去 效率分析

6、 在上面介紹各功能時(shí)已經(jīng)提到時(shí)間復(fù)雜度的計(jì)算了，這里再簡(jiǎn)單分析一下。 具有同數(shù)量級(jí)復(fù)雜度的功能在實(shí)現(xiàn)方法上一般近似。 比如InOrderTraverse，PostOrderTraverse，BiTreeDepth，LevelOrderTraverse 它們都是基于PreOrderTraverse 來設(shè)計(jì)的，所以效率都是O(n)； 而Root，Value，Assign，Parent，LeftChild，RightChild，LeftSibling RightSibling，InsertChild，DeleteChild 是基于VisitPoint，平均效率為O(n)； Ini

7、tTree DestroyBiTree所需信息，所以效率為O(1)； CreateBiTreeClearBiTreeBiTreeEmpty都要對(duì)二叉鏈表，平均效率為O(n)。 實(shí)驗(yàn)總結(jié)與評(píng)價(jià) 我做了這個(gè)實(shí)驗(yàn)發(fā)現(xiàn)自己的編程能力很不好，自己的腦袋中有相應(yīng)的想法和主意，但是因?yàn)樽约旱木幊棠芰懿缓靡簿蛯?shí)現(xiàn)不了自己的想法。 二叉鏈表的二叉樹的時(shí)候，實(shí)現(xiàn)二叉鏈表線性的對(duì)我來說還可以實(shí)現(xiàn)，因?yàn)榫€性的所用到方法和技術(shù)，在學(xué)習(xí)十字鏈表的時(shí)候練習(xí)的比擬少，實(shí)現(xiàn)起來難度是很大。特別是有了教師給的框架以后，我們要做的任務(wù)就是向里面填我們自己寫的函數(shù)，在填寫的過程中，我深深的感受到了，認(rèn)

8、真的重要性，因?yàn)槲以趯懞谜{(diào)試的中發(fā)現(xiàn)了很多，因?yàn)樽约旱牟恍⌒暮驮谇么a的過程中的不認(rèn)真而造成的很不應(yīng)該的錯(cuò)誤，這些錯(cuò)誤也給自己在調(diào)試的過程中也造成了很大的麻煩，因?yàn)槭遣徽J(rèn)真而犯的錯(cuò)誤，因此調(diào)試的過程中也很不好發(fā)現(xiàn)。 對(duì)我來說，因?yàn)槲业腃語言的功底很不好，運(yùn)用指針和鏈表的能力還沒有能達(dá)到運(yùn)用自如，理解深刻的地步，所以在順序鏈表的鏈表的實(shí)現(xiàn)中，對(duì)我來說是一個(gè)很大的挑戰(zhàn)，我有很多不會(huì)的地方通過自己看書，問室友和上網(wǎng)查詢，一點(diǎn)一點(diǎn)的寫了出來，肯定現(xiàn)在還是會(huì)有很多的問題，但是這也是我一直在努力把它做的更好，在調(diào)試的中出現(xiàn)了很多的BUG，自己一個(gè)個(gè)的慢慢的消除掉了，做出了，現(xiàn)在的程序。 如果問自己的

9、體會(huì)，那一定是希望我自己以后多多的動(dòng)手，把以前C語言的書好好再復(fù)習(xí)一遍，還有就是把現(xiàn)在正在學(xué)習(xí)的數(shù)據(jù)結(jié)構(gòu)的書上各個(gè)程序，自己要一個(gè)個(gè)的敲一遍，練習(xí)一下自己的熟悉程度。 總的來說，我對(duì)這次的實(shí)驗(yàn)是很有感觸的。因?yàn)?，這次實(shí)驗(yàn)讓我認(rèn)識(shí)到了，自己的編程能力的低下，如果自己再不下一下功夫的話，那么數(shù)據(jù)結(jié)構(gòu)的考試自己就十分的危險(xiǎn)了。因此，我要加緊復(fù)習(xí)C語言的知識(shí)和數(shù)據(jù)結(jié)構(gòu)學(xué)過的內(nèi)容， 爭(zhēng)取自己能在接下來的學(xué)習(xí)中能有些進(jìn)步。 附錄： 參考書《數(shù)據(jù)結(jié)構(gòu)》〔C語言版〕嚴(yán)蔚敏 吳偉民編著 《C語言程序設(shè)計(jì)》 曹計(jì)昌，李開編著 實(shí)驗(yàn)心得體會(huì) 對(duì)于這兩次的實(shí)驗(yàn)，我自己的體會(huì)是很深刻

10、的，也是記憶深刻的。因?yàn)?，正是因?yàn)檫@兩次的實(shí)驗(yàn)深深地讓我認(rèn)識(shí)到了自己的水平是多么的低下，以前，自己還有點(diǎn)夜郎自大的認(rèn)為，自己對(duì)所學(xué)的東西，自己掌握的還差不多了呢。但是，經(jīng)過這次的實(shí)驗(yàn)，我真的是清楚的發(fā)現(xiàn)自己對(duì)所學(xué)的知識(shí)的掌握還差的很多，自己還有很多的功課要補(bǔ)。 第一，以前無論是學(xué)習(xí)C語言還是數(shù)據(jù)結(jié)構(gòu)，我的方法是拿著書本看，還有就是拿著練習(xí)本寫一寫，而自己家上機(jī)的實(shí)踐的時(shí)間是非常少的，因?yàn)槲腋杏X上機(jī)得到的結(jié)構(gòu)一定會(huì)和自己想的和寫的一樣呢，顯然，我是錯(cuò)誤的，因?yàn)樵谶@次的實(shí)驗(yàn)里我就發(fā)現(xiàn)，即使是書上一模一樣的代碼，在機(jī)子上也是有很大 的可能出錯(cuò)的，更不用說是自己寫的了，在寫線性表，線性鏈表和二叉鏈表

11、的時(shí)候，我出現(xiàn)了用書上的代碼不能用的情況，而且是非常嚴(yán)重的錯(cuò)誤。有些聲明和指針的問題會(huì)出現(xiàn)很大的不同。我的體會(huì)是，從現(xiàn)在起，重視上機(jī)的過程，多書上的程序一定要在機(jī)子上跑一下，然后再分析一下，出現(xiàn)這種結(jié)果的原因和整個(gè)程序的流程。 第二，就是實(shí)驗(yàn)的 時(shí)候的規(guī)X的問題，由于，自己寫代碼沒有很好的習(xí)慣和規(guī)如此，于是，在自己寫好的程序出現(xiàn)錯(cuò)誤后自己不能夠很快的 找到出現(xiàn)錯(cuò)誤的位置，比如，對(duì)全局變量聲明的時(shí)候，全局變量的位置問題，在結(jié)構(gòu)和聯(lián)合聲明指針的時(shí)候，指針的形式和指針的命名的形式問題，這些錯(cuò)誤都有在自己的實(shí)驗(yàn)的過程中出現(xiàn)，而且，也給自己帶來了很大的麻煩。我的體會(huì)是，以后再寫程序的時(shí)候一定遵守一定的

12、規(guī)如此和習(xí)慣，例如關(guān)鍵詞的命名習(xí)慣，指針的使用形式和結(jié)構(gòu)聯(lián)合中的一些形式的問題，應(yīng)該遵循一定的規(guī)如此和習(xí)慣，因?yàn)?，只有這樣的自己在寫好的調(diào)試和檢查的過程中才不會(huì)走那么多 的彎路，才會(huì)把做事的速度提高上去。 最后，就是自己的一些心得體會(huì)對(duì)這次的實(shí)驗(yàn)。做什么事情都要認(rèn)真對(duì)待，無論事情的大小，因?yàn)橹挥羞@樣自己才會(huì)養(yǎng)成認(rèn)真做事的習(xí)慣，這次的數(shù)據(jù)結(jié)構(gòu)的實(shí)驗(yàn)讓我深深的意識(shí)到了這一點(diǎn)。 附錄： 實(shí)驗(yàn)三代碼： #include #include #include #include #include

13、sert.h> #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASTABLE -1 #define OVERFLOW -2 #define MAX_TREE_SIZE 100 typedef int Status; typedef int TElemType; //數(shù)據(jù)元素類型定義,注意這里是整型的，可以使char typedef TElemType SqBiT

14、ree[MAX_TREE_SIZE]; SqBiTree bt; typedef struct{ TElemType *base; TElemType *top; int stacksize; }SqStack; Status InitStack(SqStack*S); Status Pop(SqStack*S,TElemType e); Status Push(SqStack*S,TElemType e); Status StackEmpty(SqStack*S); //全局變量的聲明 char *m_pCharBuf = NULL; int m_nL

15、ist[100]; int m_nCount = 0; char* openFileOnlyRead(char * fileName); void writeQuickSortResult(char *pResult); char* openFileOnlyRead(char * fileName) { int nLen = 0; FILE *pFile = fopen(fileName, "r"); //打開文件 fseek(pFile, 0, SEEK_END); //文件指針移到文件尾 nLen = fte

16、ll(pFile); //得到當(dāng)前指針位置, 即是文件的長(zhǎng)度 rewind(pFile); //文件指針恢復(fù)到文件頭位置 //動(dòng)態(tài)申請(qǐng)空間, 為保存字符串結(jié)尾標(biāo)志\0, 多申請(qǐng)一個(gè)字符的空間 m_pCharBuf = (char*)malloc(sizeof(char)* nLen + 1); if (!m_pCharBuf) { perror("內(nèi)存不夠!\n"); exit(0); } //讀取文件內(nèi)容//讀取的長(zhǎng)度和源文

17、件長(zhǎng)度有可能有出入，這里自動(dòng)調(diào)整 nLen nLen = fread(m_pCharBuf, sizeof(char), nLen, pFile); m_pCharBuf[nLen] = '\0'; //添加字符串結(jié)尾標(biāo)志 //printf("%s\n", pchBuf); //把讀取的內(nèi)容輸出到屏幕 fclose(pFile); //關(guān)閉文件 //free(pchBuf); //釋放空間 return m_pCharBuf; } //寫入排序完成后的結(jié)果 void writeQuickSortResult

18、(char *pResult) { FILE *pFile = fopen("QuickSortResult.txt", "w"); //打開文件 fputs(pResult, pFile); //寫入數(shù)據(jù) fclose(pFile); //關(guān)閉文件 } typedef struct BiTNode{ TElemType data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; typedef BiTree QElemType; type

19、def struct QNode{ QElemType data; struct QNode *next; }QNode,*QueuePtr; typedef struct LinkQueue { QueuePtr front,rear; }LinkQueue; void InitTree(BiTree*T); void DestroyBiTree(BiTree *T); void CreateBiTree(BiTree *T); Status ClearBiTree(BiTree T); Status BiTreeEmpty(BiTree T)

20、; Status BiTreeDepth(BiTree T); Status Root(BiTree T); Status Value(BiTree T,TElemType e); Status Assign(BiTree T,TElemType e,int value); Status Parent(BiTree T,TElemType e); Status LeftChild(BiTree T,TElemType e); Status RightChild(BiTree T,TElemType e); Status LeftSibling(BiTree T,TElemTyp

21、e e); Status RightSibling(BiTree T,TElemType e); Status InsertChild(BiTree T,int LR,BiTree C); Status DeleteChild(BiTree T,int LR); Status PreOrderTraverse(BiTree T,Status(*Visit)(TElemType e)); Status InOrderTraverse(BiTree T,Status(*Visit)(TElemType e)); Status PostOrderTraverse(BiTree T,Sta

22、tus(*Visit)(TElemType e)); Status LevelOrderTraverse(BiTree T,Status(*Visit)(TElemType e)); Status Visit(TElemType e); BiTree Point(BiTree T,TElemType s); //返回二叉樹中指向元素值為s的結(jié)點(diǎn)的指針 void InitQueue(LinkQueue Q);//構(gòu)造一個(gè)空隊(duì)列 Status QueueEmpty(LinkQueue Q);//判斷隊(duì)列是否為空 void EnQueue(LinkQueue Q,QElemType

23、 e);//插入元素為新的隊(duì)尾元素 Status DeQueue(LinkQueue Q,QElemType e);//刪除隊(duì)頭元素 BiTNode * Create(FILE *fp); FILE * fileOpen(); void main(void){ int i; //文件內(nèi)容讀取出來 char *pText = openFileOnlyRead("resource.txt"); printf("%s\n\n", pText); BiTree T; FILE *p; TElemType e;

24、 int n; int value; int op=1; while(op){ system("cls"); printf("\n\n"); printf(" Menu for Linear Table On Sequence Structure \n"); printf("----------------------------------------------------------\n"); printf(" 1. InitTree 11. LeftChild\n"); printf("

25、2. DestroyBiTree 12. RightChild\n"); printf(" 3. CreateBiTree 13. LeftSibling\n"); printf(" 4. ClearBiTree 14. RightSibling\n"); printf(" 5. BiTreeEmpty 15. InsertChild\n"); printf(" 6. BiTreeDepth 16. DeleteChild\n"); printf("

26、7. Root 17. PreOrderTraverse\n"); printf(" 8. Value 18. InOrderTraverse\n"); printf(" 9. Assign 19. PostOrderTraverse\n"); printf(" 10. Parent 20. LevelOrderTraverse\n"); printf(" 0. Exit\n"); printf("----------------

27、------------------------------------------\n"); printf(" 請(qǐng)選擇你的操作[0~20]:"); scanf("%d",&op); switch(op){ case 1: InitTree(&T); BiTNode * Create(p); FILE * fileOpen(); if(!(T)==NULL) printf("\n----二叉樹初始化成功！\n"); el

28、se printf("二叉樹創(chuàng)建失??！\n"); getchar();getchar(); break; case 2: printf("是否要銷毀二叉樹！(1為是，0是否)\n"); scanf("%d",&n); if(n==1) DestroyBiTree(&T); else return 0; if(T!=NULL) printf("\n----二叉樹成功銷毀實(shí)現(xiàn)！\n"); else

29、 printf("\n---DestroyList功能待實(shí)現(xiàn)"); getchar();getchar(); break; case 3: //InitTree(&T); printf("Please input the char:e=\n"); scanf("%d",&e); CreateBiTree(T); if((T)!=NULL) printf("\n----CreateBiTree功能實(shí)現(xiàn)！\n"); else

30、 printf("\n----CreateBiTree功能待實(shí)現(xiàn)！\n"); getchar();getchar(); break; case 4: ClearBiTree(T); if(T) printf("\n----ClearBiTree功能待實(shí)現(xiàn)！\n"); else printf("\n----ClearBiTree功能實(shí)現(xiàn)！\n");0- getchar();getchar(); break; case 5: BiTreeEmpty(T); if(T) print

31、f("\n----BiTreeEmpty功能實(shí)現(xiàn)！\n"); else printf("\n----BiTreeEmpty功能待實(shí)現(xiàn)！\n"); getchar();getchar(); break; case 6: BiTreeDepth(T); if(T) printf("\n----BiTreeDepth功能實(shí)現(xiàn)！\n"); else printf("\n----BiTreeDepth功能待實(shí)現(xiàn)！\n"); getchar();getchar(); break; case 7: Root(

32、T); if(T) printf("\n----Root功能實(shí)現(xiàn)！\n"); else printf("\n----Root功能待實(shí)現(xiàn)！\n"); getchar();getchar(); break; case 8: printf("Please input the node of you want:e=\n"); scanf("%c",&e); Value(T,e); if(T==NULL) printf("\n----Value功能實(shí)現(xiàn)！\n"); else pri

33、ntf("\n----Value功能待實(shí)現(xiàn)！\n"); getchar();getchar(); break; case 9: printf("Please input the node and number of you want:e=\nvalue=\n"); scanf("%c%d",&e,&value); Assign(T,e,value); if(T==NULL) printf("\n----Assign功能實(shí)現(xiàn)！\n"); else printf("\n----Assi

34、gn功能待實(shí)現(xiàn)！\n"); getchar();getchar(); break; case 10: printf("Please input the node of you want:e=\n"); scanf("%c",&e); Parent(T,e); if(T==NULL) printf("\n----Parent功能實(shí)現(xiàn)！\n"); else printf("\n----Parent功能待實(shí)現(xiàn)！\n"); getchar();getchar(

35、); break; case 11: printf("Please input the node of you want:e=\n"); scanf("%c",&e); LeftChild(T,e); if(T!=NULL) printf("\n----LeftChild功能實(shí)現(xiàn)！\n"); else printf("\n----LeftChild功能待實(shí)現(xiàn)\n"); getchar();getchar(); break; case 12: printf("Please input the node

36、 of you want:e=\n"); scanf("%c",&e); RightChild(T,e); if(T!=NULL) printf("\n----RightChild功能實(shí)現(xiàn)\n"); else printf("\n----RightChild功能待實(shí)現(xiàn)！\n"); getchar();getchar(); break; case 13: printf("Please input the node of you want:e=\n"); scanf("%c",&e);

37、 LeftSibling(T,e); if(T!=NULL) printf("\n----LeftSibling功能實(shí)現(xiàn)！\n"); else printf("\n----LeftSibling功能待實(shí)現(xiàn)\n"); getchar();getchar(); break; case 14: printf("Please input the node of you want:e=\n"); scanf("%c",&e); RightSibling(T,e

38、); if(T!=NULL) printf("\n----LeftSibling功能實(shí)現(xiàn)！\n"); else printf("\n----LeftSibling功能待實(shí)現(xiàn)！\n"); getchar();getchar(); break; case 15: //printf("Please input the node of you want:p,e,LR and C=\n"); // scanf("%c",&e); // InsertChil

39、d(T,P,LR,C); printf("線性表是空表！\n"); getchar();getchar(); break; case 16: printf("線性表是空表！\n"); getchar();getchar(); break; case 17: printf("線性表是空表！\n"); getchar();getchar(); break; case 18: printf("線性表是空表！\n"); getchar();getchar(

40、); break; case 19: printf("Please input the node of you want:e=\n"); scanf("%c",&e); PostOrderTraverse(T,e); if(T!=NULL) printf("功能實(shí)現(xiàn)了！\n"); else printf("功能待實(shí)現(xiàn)了！\n"); getchar();getchar(); break; case 20: printf("線性表是空表！\n"); getchar();ge

41、tchar(); break; case 0: break; }//end of switch }//end of while char result[1000] = { "QuickSortResult:" }; for(i = 0; i < m_nCount; ++i) { printf("%d ", m_nList[i]); char number[100] = {}; _itoa(m_nList[i], number, 10); strca

42、t(result, " "); strcat(result, number); } //將結(jié)果寫出到文件： writeQuickSortResult(result); getchar(); free(m_pCharBuf); printf("歡迎下次再使用本系統(tǒng)！\n"); }//end of main() void InitTree(BiTree *T){ T=(BiTree)malloc(sizeof(BiTNode)); (*T)->data=NULL; return OK; }

43、 void DestroyBiTree(BiTree *T){ if(T!=NULL){ DestroyBiTree((*T)->lchild); DestroyBiTree((*T)->rchild); free(T); T=NULL; } return OK; } void CreateBiTree(BiTree *T) { /* 算法6.4:按先序次序輸入二叉樹中結(jié)點(diǎn)的值〔可為字符型或整型，在主程中 */ /* 定義〕，構(gòu)造二叉鏈表表示的二叉樹T。變

44、量Nil表示空〔子〕樹。有改動(dòng) */ TElemType ch; #ifdef CHAR scanf("%c",&ch); #endif #ifdef INT scanf("%d",&ch); #endif if(ch==' ') /* 空 */ *T=NULL; else { *T=(BiTree)malloc(sizeof(BiTNode)); if(!*T) exit(OVERFLOW); (*T)->data=ch; /* 生成根結(jié)點(diǎn) */ Cre

45、ateBiTree(&(*T)->lchild); /* 構(gòu)造左子樹 */ CreateBiTree(&(*T)->rchild); /* 構(gòu)造右子樹 */ } } Status ClearBiTree(BiTree T){ BiTree pl,pr; if(T==NULL) return ; if(T){ pl=T->lchild; pr=T->rchild; T->lchild=NULL; T->rchild=NULL; free(T);

46、 T=NULL; ClearBiTree(pl); ClearBiTree(pr); } return OK; } Status BiTreeEmpty(BiTree T){ if(T==NULL) return TRUE; else return FALSE; } Status BiTreeDepth(BiTree T){ int lchildHigh,rchildHigh; if(T==NUL

47、L)return 0; else lchildHigh=BiTreeDepth(T->lchild); rchildHigh=BiTreeDepth(T->rchild); return lchildHigh>rchildHigh ? (lchildHigh+1):(rchildHigh+1); } Status Root(BiTree T){ if(T==NULL)return ERROR; printf("%c",T->data); Root(T->lchild);

48、 Root(T->rchild); return OK; } Status Value(BiTree T,TElemType e){ if(T==NULL)return ERROR; else if(T->data==e)return (T->data); Value(T->lchild,e); Value(T->rchild,e); return OK; } Status Assign(BiTree T,TElemType e,int valu

49、e){ if(T==NULL)return ERROR; if(T->data==e) T->data=value; else Assign(T->lchild,e,value); Assign(T->rchild,e,value); return OK; } Status Parent(BiTree T,TElemType e){ if(T==NULL)return ERROR; if(T->data==e) if(T->lchild || T-

50、>rchild) return (T->data); else Parent(T->lchild,e); Parent(T->rchild,e); return OK; } Status LeftChild(BiTree T,TElemType e){ if(T==NULL) return; if(T->data==e){ if(!(T->lchild)) printf("%c",T->lchil

51、d); else return NULL; } else{ T->lchild; LeftChild(T->lchild,e); T->rchild; LeftChild(T->rchild,e); } return OK; } Status RightChild(BiTree T,TElemType e){ if(T==NULL) return; if(T->data==e){ if(!(T->rchild))

52、 printf("%c",T->rchild); else return NULL; } else{ T->lchild; RightChild(T->lchild,e); T->rchild; RightChild(T->rchild,e); } return OK; } Status LeftSibling(BiTree T,TElemType e) { //返回左兄弟 TElemType a; BiTree p; if(T) {

53、 a=Parent(T,e);//a為e的雙親 if(a!=NULL) { p=Point(T,a);//p指向結(jié)點(diǎn)a的指針 if(p->lchild&&p->rchild&&p->rchild->data==e)//p存在左右孩子而且右孩子是e return p->lchild->data; } } return NULL; } Status RightSibling(BiTree T,TElemType e){ TElemType a; BiTree p; if(T) { a=Parent(T,e);//

54、a為e的雙親 if(a!=NULL) { p=Point(T,a);//p為指向結(jié)點(diǎn)的a的指針 if(p->lchild&&p->rchild&&p->lchild->data==e) return p->lchild->data; } } return NULL; } Status InsertChild(BiTree T,int LR,BiTree C){ if(T) { if(LR==0){ C->rchild=T->lchild; T->lc

55、hild=C; } else{ C->rchild=T->rchild;//T指結(jié)點(diǎn)的原有右子樹成為C的右子樹 T->rchild=C; } return OK; } return ERROR; } Status DeleteChild(BiTree T,int LR) { if(T) { if(LR==0) DestroyBiTree(T->lchild); else DestroyBiTree(T->rchild); return OK;

56、 } return ERROR; } Status PreOrderTraverse(BiTree T,Status(*Visit)(TElemType e)){ Status PrintElement(TElemType e){ printf(e); return OK; if(T){ if(Visit(T->data)) if(PreOrderTraverse(T->lchild,Visit)) if(PreOrderTraverse(T->rchild,Vis

57、it)) return OK; return ERROR; } else return OK; } }//PreOrderTraaverse Status InOrderTraverse(BiTree T,Status(*Visit)(TElemType e)){ Status PrintElement(TElemType e){ printf(e); return OK; if(T){ if(PreOrderTraverse(T->lchild,Visit))

58、 if(Vist(T->data)); if(PreOrderTraverse(T->rchild,Visit)) return OK; return ERROR; } else return OK; } }//InOrderTraverse Status PostOrderTraverse(BiTree T,Status(*Visit)(TElemType e)){ Status PrintElement(TElemType e){ printf(e);

59、return OK; if(T){ if(PreOrderTraverse(T->lchild,Visit)) if(PreOrderTraverse(T->rchild,Visit)) if(Vist(T->data)) return OK; return ERROR; } else return OK; } }//PostOrderTraverse Status LevelOrderTraverse(BiTree T,Status(*Visit)(TElemType e)){ BiTree

60、 p,newNode; Status PrintElement(TElemType e){ printf(e); return OK; if(T){ if(p=T->lchild){ newNode=(BiTree)malloc(sizeof(BiTNode)); newNode->data=e; newNode->rchild=NULL; newNode->lchild=p; T->lchild=newNode; } else return ERROR;

61、 } else return ERROR; } return OK; }//LevelOrderTraverse //Status Visit(TElemType e) //{ printf("%c",e); //} BiTree Point(BiTree T,TElemType s)//返回二叉樹T中指向元素值為S的結(jié)點(diǎn)指針 { LinkQueue q; QElemType a; if(T) { InitQueue(q);//初始化隊(duì)列 EnQueue(q,T);//根指針入隊(duì) while(!Que

62、ueEmpty(q))//隊(duì)不空 { DeQueue(q,a);//出隊(duì)，隊(duì)列元素賦給e if(a->data==s)//a所指結(jié)點(diǎn)為的值為s return a; if(a->lchild)//有左孩子 EnQueue(q,a->lchild);//入隊(duì)左孩子 if(a->rchild)//有右孩子 EnQueue(q,a->rchild);//入隊(duì)右孩子 } } return NULL; } void InitQueue(LinkQueue Q) {//初始化一個(gè)隊(duì)列 Q.front=Q.rear=(QueuePtr)

63、malloc(sizeof(QNode)); if(!Q.front)//生成頭結(jié)點(diǎn)失敗 exit(OVERFLOW); Q.front->next=NULL; } Status QueueEmpty(LinkQueue Q) { //判斷隊(duì)列是否為空 if(Q.front->next==NULL) return TRUE; else return FALSE; } void EnQueue(LinkQueue Q,QElemType e) { //插入元素e為隊(duì)列Q的新的隊(duì)尾元素 QueuePtr p; p=(Q

64、ueuePtr)malloc(sizeof(QNode)); //動(dòng)態(tài)生成新結(jié)點(diǎn) if(!p) exit(OVERFLOW); p->data=e;//將e的值賦給新結(jié)點(diǎn) p->next=NULL;//新結(jié)點(diǎn)的指針為空 Q.rear->next=p;//原隊(duì)尾結(jié)點(diǎn)的指針域?yàn)橹赶蛐陆Y(jié)點(diǎn) Q.rear=p;//尾指針指向新結(jié)點(diǎn) } Status DeQueue(LinkQueue Q,QElemType e) { //假如隊(duì)列不為空，刪除Q的隊(duì)頭元素，用e返回其值 QueuePtr p; if(Q.front==Q.re

65、ar)//隊(duì)列為空 return ERROR; p=Q.front->next;//p指向隊(duì)頭結(jié)點(diǎn) e=p->data;//隊(duì)頭元素賦給e Q.front->next=p->next;//頭結(jié)點(diǎn)指向下一個(gè)結(jié)點(diǎn) if(Q.rear==p)//如果刪除的隊(duì)尾結(jié)點(diǎn) Q.rear=Q.front;//修改隊(duì)尾指針指向頭結(jié)點(diǎn) free(p); return OK; } FILE * fileOpen() { FILE *fp; fp = fopen("test.txt", "r"); assert(fp !

66、= NULL); return fp; } BiTNode * Create(FILE *fp) { char ch; BiTNode * bt = NULL; if ((ch = fgetc(fp)) == EOF) { return NULL; } if ('#' != ch) { bt = (BiTNode *)malloc(sizeof(BiTNode)); bt->data = ch; bt->lchild = Create(fp); bt->rchild = Create(fp); } return bt; } Status InitStack(SqStack*S){ S->base=(TElemType*)malloc(MAX_TREE_SIZE*sizeof(TElemType)); if(!(S->base))exit(OVERFLOW);