設(shè)計(jì)出樹結(jié)構(gòu)的相關(guān)函數(shù)庫(kù)以便在程序設(shè)計(jì)中調(diào)用.doc

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 學(xué) 院 專 業(yè) 班 級(jí) 學(xué) 號(hào) 學(xué)生姓名 * 指導(dǎo)教師 課程成績(jī) 完成日期 2013年7月12日課程設(shè)計(jì)成績(jī)?cè)u(píng)定 學(xué) 院 城南學(xué)院專 業(yè) 計(jì)算機(jī)科學(xué)與技術(shù) 班 級(jí) 學(xué) 號(hào) 學(xué)生姓名 指導(dǎo)教師 完成日期 2013年7月12日指導(dǎo)教師對(duì)學(xué)生在課程設(shè)計(jì)中的評(píng)價(jià)評(píng)分項(xiàng)目?jī)?yōu)良中及格不及格課程設(shè)計(jì)中的創(chuàng)造性成果學(xué)生掌握課程內(nèi)容的程度課程設(shè)計(jì)完成情況課程設(shè)計(jì)動(dòng)手能力文字表達(dá)學(xué)習(xí)態(tài)度規(guī)范要求課程設(shè)計(jì)論文的質(zhì)量指導(dǎo)教師對(duì)課程設(shè)計(jì)的評(píng)定意見綜合成績(jī)指導(dǎo)教師簽字 2013年7月12日課程設(shè)計(jì)任務(wù)書 學(xué)院專業(yè) 課程名稱數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)時(shí)間20122013學(xué)年第二學(xué)期1920周學(xué)生姓名 指導(dǎo)老師 題 目設(shè)計(jì)出樹結(jié)構(gòu)的相關(guān)函數(shù)庫(kù),以便在程序設(shè)計(jì)中調(diào)用主要內(nèi)容:使用Microsoft Visual C+ 6.0 設(shè)計(jì)二叉鏈表結(jié)構(gòu)的相關(guān)函數(shù)庫(kù),以便在程序設(shè)計(jì)中調(diào)用設(shè)計(jì)二叉鏈表結(jié)構(gòu)的相關(guān)函數(shù)庫(kù),在程序設(shè)計(jì)中調(diào)用,并實(shí)現(xiàn)二叉樹的各種基本函數(shù)以及常用函數(shù)。要求: (1)包括樹結(jié)構(gòu)的存儲(chǔ)結(jié)構(gòu)及各種基本函數(shù)以及常用函數(shù)(自己確定函數(shù)、函數(shù)形式及理由)。(2)最好能借助語(yǔ)言環(huán)境實(shí)現(xiàn)圖形顯示功能,以便能將抽象的數(shù)據(jù)結(jié)構(gòu)以圖形方式顯示出來,將復(fù)雜的運(yùn)行過程以動(dòng)態(tài)方式顯示出來。 (3)給出若干例程,演示通過調(diào)用自己的庫(kù)函數(shù)來實(shí)現(xiàn)相關(guān)問題的求解。應(yīng)當(dāng)提交的文件: (1)課程設(shè)計(jì)學(xué)年論文。 (2)課程設(shè)計(jì)附件(主要是源程序)。 設(shè)計(jì)出樹結(jié)構(gòu)的相關(guān)函數(shù)庫(kù),以便在程序設(shè)計(jì)中調(diào)用學(xué)生姓名: 指導(dǎo)老師: 摘 要 作為用戶我們極少接觸系統(tǒng)調(diào)用,但是我們熟悉C語(yǔ)言,對(duì)庫(kù)函數(shù)的調(diào)用并不陌生。C語(yǔ)言支持一系列庫(kù)函數(shù)的調(diào)用,而事實(shí)上,庫(kù)函數(shù)的調(diào)用是C語(yǔ)言在較高層次上調(diào)用的一種方式,函數(shù)調(diào)用是操作系統(tǒng)內(nèi)核提供給程序員的程序設(shè)計(jì)界面,它們是內(nèi)核提供給用戶調(diào)用的函數(shù)。使用Microsoft Visual C+ 6.0設(shè)計(jì)二叉鏈表結(jié)構(gòu)的相關(guān)函數(shù)庫(kù),操作系統(tǒng)通過執(zhí)行main函數(shù)開始運(yùn)行一個(gè)C程序。main函數(shù)可以調(diào)用C程序中的其他函數(shù)來完成程序的任務(wù),其他函數(shù)也可以互相調(diào)用,但其他函數(shù)(非main函數(shù))不能調(diào)用main函數(shù)(main函數(shù)只能由操作系統(tǒng)來調(diào)用)。關(guān)鍵詞 設(shè)計(jì)函數(shù)庫(kù);C程序的執(zhí)行;C程序的調(diào)用;C語(yǔ)言;VC+6.0目錄1 引 言11.1 課程設(shè)計(jì)目的11.2 課程設(shè)計(jì)要求12問題的描述22.1問題的模型化描述23數(shù)據(jù)結(jié)構(gòu)33.1定義二叉樹結(jié)點(diǎn)類型34 模塊劃分34.1 入隊(duì)34.2 隊(duì)列判空34.3 出隊(duì)44.4根據(jù)先序遞歸建立二叉樹44.5遞歸遍歷輸出函數(shù)44.6層次遍歷輸出算法54.7 求二叉樹深度得算法54.8求二叉樹葉子結(jié)點(diǎn)數(shù)的算法55 運(yùn)行程序65.1程序運(yùn)行結(jié)果66 結(jié)束語(yǔ)8附錄:源程序代碼91 引 言 Visual C+6.0由許多組件組成,包括編輯器、調(diào)試器以及程序向?qū)ppWizard、類向?qū)lass Wizard等開發(fā)工具。編譯就是把高級(jí)語(yǔ)言變成計(jì)算機(jī)可以識(shí)別的2進(jìn)制語(yǔ)言,計(jì)算機(jī)只認(rèn)識(shí)1和0,編譯程序把人們熟悉的語(yǔ)言換成2進(jìn)制的。編譯程序把一個(gè)源程序翻譯成目標(biāo)程序的工作過程分為五個(gè)階段:詞法分析;語(yǔ)法分析;語(yǔ)義檢查和中間代碼生成;代碼優(yōu)化;目標(biāo)代碼生成。主要是進(jìn)行詞法分析和語(yǔ)法分析,又稱為源程序分析,分析過程中發(fā)現(xiàn)有語(yǔ)法錯(cuò)誤,給出提示信息。將編譯產(chǎn)生的.obj文件和系統(tǒng)庫(kù)連接裝配成一個(gè)可以執(zhí)行的程序。由于在實(shí)際操作中可以直接點(diǎn)擊Build從源程序產(chǎn)生可執(zhí)行程序,將源程序翻譯成可執(zhí)行文件的過程分為編譯和鏈接兩個(gè)獨(dú)立的步驟,之所以這樣做,主要是因?yàn)?在一個(gè)較大的復(fù)雜項(xiàng)目中,有很多人共同完成一個(gè)項(xiàng)目每個(gè)人可能承擔(dān)其中一部分模塊,其中有的模塊可能是用匯編語(yǔ)言寫的,有的模塊可能是用VC寫的,有的模塊可能是用VB寫的,有的模塊可能是購(gòu)買不是源程序模塊而是目標(biāo)代碼或已有的標(biāo)準(zhǔn)庫(kù)模塊,因此,各類源程序都需要先各自編譯成目標(biāo)程序文件,再通過鏈接程序?qū)⑦@些目標(biāo)程序文件連接裝配成可執(zhí)行文件,再調(diào)用函數(shù)或運(yùn)行可執(zhí)行程序文件。1.1 課程設(shè)計(jì)目的(1)使用Microsoft Visual C+6.0 設(shè)計(jì)二叉鏈表結(jié)構(gòu)的相關(guān)函數(shù)庫(kù)(2)在程序設(shè)計(jì)中調(diào)用設(shè)計(jì)二叉鏈表結(jié)構(gòu)的相關(guān)函數(shù)庫(kù)(3)在程序設(shè)計(jì)中調(diào)用并實(shí)現(xiàn)二叉樹的各種基本函數(shù)以及常用函數(shù)。1.2 課程設(shè)計(jì)要求 (1)按要求編寫課程設(shè)計(jì)報(bào)告書,能正確闡述設(shè)計(jì)結(jié)果。 (2)通過課程設(shè)計(jì)培養(yǎng)學(xué)生嚴(yán)謹(jǐn)?shù)目茖W(xué)態(tài)度,認(rèn)真的工作作風(fēng)和團(tuán)隊(duì)協(xié)作精神。 (3)學(xué)會(huì)文獻(xiàn)檢索的基本方法和綜合運(yùn)用文獻(xiàn)的能力。 (4)在老師的指導(dǎo)下,要求每個(gè)學(xué)生獨(dú)立完成課程設(shè)計(jì)的全部?jī)?nèi)容。 2.問題的描述 2.1問題的模型化描述 3 數(shù)據(jù)結(jié)構(gòu)3.1定義二叉樹結(jié)點(diǎn)類型typedef char datatype; typedef struct Nodechar data;struct Node * Lchild;struct Node * Rchild;BiTNode,*BiTree;/二叉樹節(jié)點(diǎn),二叉鏈表typedef struct QueueNodeBiTree data;struct QueueNode *next;LinkQueueNode;/隊(duì)列中的每個(gè)節(jié)點(diǎn)typedef structLinkQueueNode *front;LinkQueueNode *rear;LinkQueue;/隊(duì)列4.模塊劃分4.1入隊(duì)void InitQueueLinkQueue *QQ-front LinkQueueNode *mallocsizeofLinkQueueNode;ifQ-front ! NULLQ-rear Q-front;Q-front-next NULL;else printf分配空間失敗!n;4.2隊(duì)列判空void EnterQueueLinkQueue *Q,BiTree xLinkQueueNode *NewNode;NewNode LinkQueueNode *mallocsizeofLinkQueueNode;ifNewNode ! NULLNewNode-data x;NewNode-next NULL;Q-rear-next NewNode;Q-rear NewNode;4.3出隊(duì)int QueueIsEmptyLinkQueue *QifQ-front Q-rearreturn 1;else return 0;4.4根據(jù)先序遞歸建立二叉樹void DeleteQueueLinkQueue *Q,BiTree *xLinkQueueNode *p;ifQ-front Q-rearreturn ;p Q-front-next;Q-front-next p-next;ifQ-rear pQ-rear Q-front;*x p-data;freep;4.5遞歸遍歷輸出函數(shù) void CreateBiTreeBiTree *btchar ch;ch getchar;ifch . *bt NULL;else*bt BiTreemalloc sizeofBiTNode;*bt-data ch;CreateBiTree&*bt-Lchild;CreateBiTree&*bt-Rchild;/*先序遞歸遍歷二叉樹*/void PreOrderBiTree rootifroot ! NULLprintf%c ,root-data;PreOrderroot-Lchild;PreOrderroot-Rchild;/*后序遞歸遍歷二叉樹 */4.6層次遍歷輸出算法void PostOrderBiTree rootifroot ! NULLPostOrderroot - Lchild;PostOrderroot - Rchild;printf%c ,root-data;void InOrderBiTree rootifroot ! NULLInOrderroot-Lchild;printf%c ,root-data;InOrderroot-Rchild; 4.7求二叉樹深度得算法void depthBiTree root,int &depint dep1,dep2;if!root dep0;elsedepthroot-Lchild,dep1;depthroot-Rchild,dep2;depdep1dep2?dep1+1:dep2+1; 4.8求二叉樹葉子結(jié)點(diǎn)數(shù)的算法void countleafBiTree root,int&nif rootcountleafroot-Lchild,n;if!root-Lchild & !root-Rchild n+;countleafroot-Rchild,n;5 運(yùn)行程序5.1 程序運(yùn)行結(jié)果7 結(jié)束語(yǔ) 本次課程設(shè)計(jì)為時(shí)二周,我選的課題是設(shè)計(jì)出樹結(jié)構(gòu)的相關(guān)函數(shù)庫(kù),以便在程序設(shè)計(jì)中的調(diào)用。其主要研究?jī)?nèi)容在于實(shí)現(xiàn)了二叉鏈表的相關(guān)函數(shù)庫(kù)的調(diào)用。為了實(shí)現(xiàn)以鏈表為存儲(chǔ)結(jié)構(gòu)的二叉樹的有關(guān)操作,要熟練掌握二叉鏈表的特性,但對(duì)于一些算法較為復(fù)雜,代碼量多些,容易出現(xiàn)一些變量的定義、函數(shù)聲明、函數(shù)調(diào)用等細(xì)節(jié)上的問題出錯(cuò)。在本程序的設(shè)計(jì)過程中,為了克服以上困難,采取了一些措施:建立清晰的程序設(shè)計(jì)的步驟方法,分步各個(gè)模塊程序設(shè)計(jì),進(jìn)行仔細(xì)的總體結(jié)構(gòu)設(shè)計(jì),反復(fù)調(diào)試、細(xì)心觀察達(dá)到完善整個(gè)系統(tǒng)等。二叉樹的遞歸算法主要是將二叉樹存儲(chǔ)到鏈表結(jié)構(gòu)中。遍歷是二叉樹各種操作的基礎(chǔ),先序、中序、后序是二叉樹遍歷的三種基本遍歷方法。而這些都是數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)內(nèi)容,是我們必須理解和牢記的基礎(chǔ)知識(shí)。將這些基礎(chǔ)算法綜合起來,更能清晰地認(rèn)識(shí)和理解各種算法的作用。當(dāng)然,要學(xué)會(huì)編程不會(huì)僅局限于課本知識(shí),而是根據(jù)課本知識(shí)進(jìn)行有效的拓展,并且不得不學(xué)會(huì)在眾多的參考資料中搜索有用的自己所需的知識(shí),并迫使自己去學(xué)習(xí)掌握它們,從中不斷提高自己。雖然程序規(guī)模不大,我們依然為此付出了努力,仍免不了各種錯(cuò)誤的出現(xiàn)。編程過程需要很大的毅力和耐心,而且要有良好的思維和扎實(shí)的專業(yè)基礎(chǔ)知識(shí),所以我們需要不斷的學(xué)習(xí),發(fā)現(xiàn)自身不足之處并改正它,逐步提高自身能力,不斷取得進(jìn)步。對(duì)于數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí),一直感到很吃力,也想過放棄。通過實(shí)踐,我們接觸到了很多關(guān)于的Microsoft Visual C+ 6.0編程讓我們認(rèn)識(shí)到知識(shí)的運(yùn)用性,并加深對(duì)基礎(chǔ)知識(shí)的理解,從中了解自己需要學(xué)習(xí)的東西并學(xué)會(huì)自學(xué)。在此我們要感謝我的老師對(duì)我們專心致志的輔導(dǎo),讓我們學(xué)會(huì)了許多分析和解決問題的方法,讓我們受益匪淺。通過幾個(gè)星期的努力,雖然從中也發(fā)現(xiàn)了自己很多不足,可能其中還有不少問題,但我覺得最重要的是自己也從中得到很多;不敢說百分百的完成也應(yīng)該基本上完成了課題任務(wù),成功地實(shí)現(xiàn)課題目標(biāo)。參考文獻(xiàn)1 嚴(yán)蔚敏. 數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版)M. 北京:清華大學(xué)出版社,1997.2譚浩強(qiáng). C程序設(shè)計(jì)(第三版)M. 北京:清華大學(xué)出版社,2005.1附錄:源程序代碼#include#includetypedef struct Nodechar data;struct Node * Lchild;struct Node * Rchild;BiTNode,*BiTree;/二叉樹節(jié)點(diǎn),二叉鏈表typedef struct QueueNodeBiTree data;struct QueueNode *next;LinkQueueNode;/隊(duì)列中的每個(gè)節(jié)點(diǎn)typedef structLinkQueueNode *front;LinkQueueNode *rear;LinkQueue;/隊(duì)列/* 隊(duì)列的初始化 */void InitQueueLinkQueue *QQ-front LinkQueueNode *mallocsizeofLinkQueueNode;ifQ-front ! NULLQ-rear Q-front;Q-front-next NULL;else printf分配空間失敗!n;/* 入隊(duì) */void EnterQueueLinkQueue *Q,BiTree xLinkQueueNode *NewNode;NewNode LinkQueueNode *mallocsizeofLinkQueueNode;ifNewNode ! NULLNewNode-data x;NewNode-next NULL;Q-rear-next NewNode;Q-rear NewNode;/* 隊(duì)列判空*/int QueueIsEmptyLinkQueue *QifQ-front Q-rearreturn 1;else return 0;/* 出隊(duì)*/void DeleteQueueLinkQueue *Q,BiTree *xLinkQueueNode *p;ifQ-front Q-rearreturn ;p Q-front-next;Q-front-next p-next;ifQ-rear pQ-rear Q-front;*x p-data;freep;/* 利用擴(kuò)展先序遍歷序列 創(chuàng)建二叉鏈表*/void CreateBiTreeBiTree *btchar ch;ch getchar;ifch . *bt NULL;else*bt BiTreemalloc sizeofBiTNode;*bt-data ch;CreateBiTree&*bt-Lchild;CreateBiTree&*bt-Rchild;/*先序遞歸遍歷二叉樹*/void PreOrderBiTree rootifroot ! NULLprintf%c ,root-data;PreOrderroot-Lchild;PreOrderroot-Rchild;/*后序遞歸遍歷二叉樹 */void PostOrderBiTree rootifroot ! NULLPostOrderroot - Lchild;PostOrderroot - Rchild;printf%c ,root-data;void InOrderBiTree rootifroot ! NULLInOrderroot-Lchild;printf%c ,root-data;InOrderroot-Rchild;/*層序遍歷 對(duì)給定的二叉樹進(jìn)行層序遍歷 */void LayerOrderBiTree rootBiTree *x; /這里要記得申請(qǐng)空間 x BiTree *mallocsizeofBiTree; ifx NULL printf內(nèi)存分配失敗!n;LinkQueue *Q; Q LinkQueue *mallocsizeofLinkQueue; InitQueueQ; EnterQueueQ,root; while!QueueIs