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

實(shí)驗(yàn)一 基于二叉鏈表的二叉樹的實(shí)現(xiàn)

4.1 問題描述

基于二叉鏈表和隊(duì)列及其堆棧存儲結(jié)構(gòu)，實(shí)現(xiàn)二叉鏈表的二叉樹的對數(shù)據(jù)進(jìn)行各種必要的操作。

4.2 系統(tǒng)設(shè)計(jì)

1.2.1提供20個功能，分別是：

1.2.2二叉鏈表的結(jié)構(gòu)試一堆棧和隊(duì)列的形式進(jìn)行儲存的分別是：

1.2.3在程序中所定義的數(shù)據(jù)結(jié)構(gòu)有：

2.3 系統(tǒng)實(shí)現(xiàn)

1.3.1 InitTree功能

初始二叉鏈表，傳入的是頭結(jié)點(diǎn)地址。申請一個存儲空間，并用頭結(jié)點(diǎn)中的首結(jié)點(diǎn)指針指向該空間首地址，相應(yīng)的 時間復(fù)雜度為1。具體實(shí)現(xiàn)如下：

1.3.2 DestroyTree功能

銷毀頭結(jié)點(diǎn)中首結(jié)點(diǎn)址針指向的線性存儲空間，傳入的是頭結(jié)點(diǎn)地址。具體實(shí)現(xiàn)如下：

1.3.3 CreateBiTree功能

與DestroyBiTree類似但是又有不同，ClearBiTree并不銷毀物理空間，而是修改邏輯關(guān)系值：

1.3.4 ClearBiTree功能

與DestroyBiTree類似但是又有不同，ClearBiTree并不銷毀物理空間，而是修改邏輯關(guān)系值

1.3.5 BiTreeEmpty功能

判空功能，判斷表是否為空表。時間復(fù)雜度為1，因?yàn)橹恍枧袛嘁淮尉涂梢灾朗欠駷榭铡?shí)現(xiàn)如下：

1.3.6 BiTreeDepth功能

求二叉鏈表深度的功能，由于創(chuàng)建過程中已經(jīng)把表長信息包含在頭結(jié)點(diǎn)中，所以直接調(diào)用并顯示即可

1.3.7 Root(BiTree T)功能

獲取二叉鏈表的根節(jié)點(diǎn)的元素，通過遍歷二叉鏈表中的元素，來逐個判斷，時間復(fù)雜度為（n）。

1.3.8 Value(BiTree T,TElemType e)功能

求指定元素的前一個元素的內(nèi)容，傳入頭結(jié)點(diǎn)值、包含指定元素信息的一個臨時表結(jié)點(diǎn)值、存儲前一個元素的表結(jié)點(diǎn)地址。主要思路是遞歸算法。時間復(fù)雜度為O(n)。具體實(shí)現(xiàn)如下：

1.3.9 Assign功能

求指定元素的后一個元素的內(nèi)容，傳入頭結(jié)點(diǎn)值、包含指定元素信息的一個臨時表結(jié)點(diǎn)值、存儲前一個元素的表結(jié)點(diǎn)地址。找到后，把新的數(shù)據(jù)值賦給所找到的節(jié)點(diǎn)。時間復(fù)雜度為O(n)。具體實(shí)現(xiàn)如下：

1.3.10 Parent功能

找雙親節(jié)點(diǎn)，找到后輸出

1.3.11 LeftChild功能

查找左孩子，利用遞歸的算法，與遍歷的時間復(fù)雜度為相同O(n)

1.3.12RightChild功能

查找右孩子，利用遞歸的算法，與遍歷的時間復(fù)雜度為相同O(n)

1.3.13 LeftSibling功能

查找節(jié)點(diǎn)的左邊的堂兄弟的，找到后輸出該節(jié)點(diǎn)的數(shù)據(jù)

1.3.14 RightSibling功能

查找節(jié)點(diǎn)的右邊的堂兄弟的，找到后輸出該節(jié)點(diǎn)的數(shù)據(jù)

1.3.15 InsertChild函數(shù) 在二叉鏈表中插入新的節(jié)點(diǎn)

1.3.15 DeleteChild功能

刪除指定編號的數(shù)據(jù)元素，傳入頭結(jié)點(diǎn)地址、編號i、表結(jié)點(diǎn)類型結(jié)構(gòu)體地址來返回被刪除元素內(nèi)容。執(zhí)行前先判斷傳入的編號是否在可尋找范圍內(nèi)。執(zhí)行刪除操作之后，進(jìn)行“移位”運(yùn)算。時間復(fù)雜度仍為O(n)。如下：

1.3.16 PreOrderTraverse功能

前序遍歷二叉鏈表中的數(shù)據(jù)，采用先遍歷左孩子，再訪問根節(jié)點(diǎn)，后訪問右孩子的思想來實(shí)現(xiàn)前序遍歷的算法的。

1.3.17 InOrderTraverse功能

中序遍歷的函數(shù)，對二叉鏈表的數(shù)據(jù)進(jìn)行訪問，并且利用PreOrderTraverse函數(shù)

1.3.18 PostOrderTraverse功能

采用后續(xù)遍歷的思想，利用先序遍歷的函數(shù)進(jìn)行

1.3.19 LevelOrderTraverse功能

完全遍歷二叉鏈表中的數(shù)據(jù)，并進(jìn)行輸出的

1.3.20 Point功能 定位節(jié)點(diǎn)的函數(shù)，在需要查找二叉鏈表二叉樹的節(jié)點(diǎn)的時候，可以直接調(diào)用該函數(shù)，進(jìn)行處理，相應(yīng)的代碼如下

1.3.21 FILE * fileOpen功能

讀取功能，通過fscanf實(shí)現(xiàn)格式化讀取，同時結(jié)合CreateList函數(shù)實(shí)現(xiàn)順序

1.3.22 BiTNode * Create(FILE *fp)功能 把二叉鏈表二叉樹的數(shù)據(jù)寫入到文件中去

1.4效率分析

在上面介紹各功能時已經(jīng)提到時間復(fù)雜度的計(jì)算了，這里再簡單分析一下。

具有同數(shù)量級復(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)；

InitTree

DestroyBiTree所需信息，所以效率為O(1)；

CreateBiTreeClearBiTreeBiTreeEmpty都要對二叉鏈表，平均效率為O(n)。

實(shí)驗(yàn)總結(jié)與評價

我做了這個實(shí)驗(yàn)發(fā)現(xiàn)自己的編程能力很不好，自己的腦袋中有相應(yīng)的想法和主意，但是因?yàn)樽约旱木幊棠芰懿缓靡簿蛯?shí)現(xiàn)不了自己的想法。

二叉鏈表的二叉樹的時候，實(shí)現(xiàn)二叉鏈表線性的對我來說還可以實(shí)現(xiàn)，因?yàn)榫€性的所用到方法和技術(shù)，在學(xué)習(xí)十字鏈表的時候練習(xí)的比較少，實(shí)現(xiàn)起來難度是很大。特別是有了老師給的框架以后，我們要做的任務(wù)就是向里面填我們自己寫的函數(shù)，在填寫的過程中，我深深的感受到了，認(rèn)真的重要性，因?yàn)槲以趯懞谜{(diào)試的中發(fā)現(xiàn)了很多，因?yàn)樽约旱牟恍⌒暮驮谇么a的過程中的不認(rèn)真而造成的很不應(yīng)該的錯誤，這些錯誤也給自己在調(diào)試的過程中也造成了很大的麻煩，因?yàn)槭遣徽J(rèn)真而犯的錯誤，因此調(diào)試的過程中也很不好發(fā)現(xiàn)。

對我來說，因?yàn)槲业腃語言的功底很不好，運(yùn)用指針和鏈表的能力還沒有能達(dá)到運(yùn)用自如，理解深刻的地步，所以在順序鏈表的鏈表的實(shí)現(xiàn)中，對我來說是一個很大的挑戰(zhàn)，我有很多不會的地方通過自己看書，問室友和上網(wǎng)查詢，一點(diǎn)一點(diǎn)的寫了出來，肯定現(xiàn)在還是會有很多的問題，但是這也是我一直在努力把它做的更好，在調(diào)試的中出現(xiàn)了很多的BUG，自己一個個的慢慢的消除掉了，做出了，現(xiàn)在的程序。

如果問自己的體會，那一定是希望我自己以后多多的動手，把以前C語言的書好好再復(fù)習(xí)一遍，還有就是把現(xiàn)在正在學(xué)習(xí)的數(shù)據(jù)結(jié)構(gòu)的書上各個程序，自己要一個個的敲一遍，練習(xí)一下自己的熟悉程度。

總的來說，我對這次的實(shí)驗(yàn)是很有感觸的。因?yàn)椋@次實(shí)驗(yàn)讓我認(rèn)識到了，自己的編程能力的低下，如果自己再不下一下功夫的話，那么數(shù)據(jù)結(jié)構(gòu)的考試自己就十分的危險(xiǎn)了。因此，我要加緊復(fù)習(xí)C語言的知識和數(shù)據(jù)結(jié)構(gòu)學(xué)過的內(nèi)容，爭取自己能在接下來的學(xué)習(xí)中能有些進(jìn)步。

附錄：

參考書《數(shù)據(jù)結(jié)構(gòu)》（C語言版）嚴(yán)蔚敏 吳偉民編著

《C語言程序設(shè)計(jì)》 曹計(jì)昌，李開編著

實(shí)驗(yàn)心得體會

對于這兩次的實(shí)驗(yàn)，我自己的體會是很深刻的，也是記憶深刻的。因?yàn)?，正是因?yàn)檫@兩次的實(shí)驗(yàn)深深地讓我認(rèn)識到了自己的水平是多么的低下，以前，自己還有點(diǎn)夜郎自大的認(rèn)為，自己對所學(xué)的東西，自己掌握的還差不多了呢。但是，經(jīng)過這次的實(shí)驗(yàn)，我真的是清楚的發(fā)現(xiàn)自己對所學(xué)的知識的掌握還差的很多，自己還有很多的功課要補(bǔ)。

第一，以前無論是學(xué)習(xí)C語言還是數(shù)據(jù)結(jié)構(gòu)，我的方法是拿著書本看，還有就是拿著練習(xí)本寫一寫，而自己家上機(jī)的實(shí)踐的時間是非常少的，因?yàn)槲腋杏X上機(jī)得到的結(jié)構(gòu)一定會和自己想的和寫的一樣呢，顯然，我是錯誤的，因?yàn)樵谶@次的實(shí)驗(yàn)里我就發(fā)現(xiàn)，即使是書上一模一樣的代碼，在機(jī)子上也是有很大 的可能出錯的，更不用說是自己寫的了，在寫線性表，線性鏈表和二叉鏈表的時候，我出現(xiàn)了用書上的代碼不能用的情況，而且是非常嚴(yán)重的錯誤。有些聲明和指針的問題會出現(xiàn)很大的不同。我的體會是，從現(xiàn)在起，重視上機(jī)的過程，多書上的程序一定要在機(jī)子上跑一下，然后再分析一下，出現(xiàn)這種結(jié)果的原因和整個程序的流程。

第二，就是實(shí)驗(yàn)的 時候的規(guī)范的問題，由于，自己寫代碼沒有很好的習(xí)慣和規(guī)則，于是，在自己寫好的程序出現(xiàn)錯誤后自己不能夠很快的 找到出現(xiàn)錯誤的位置，比如，對全局變量聲明的時候，全局變量的位置問題，在結(jié)構(gòu)和聯(lián)合聲明指針的時候，指針的形式和指針的命名的形式問題，這些錯誤都有在自己的實(shí)驗(yàn)的過程中出現(xiàn)，而且，也給自己帶來了很大的麻煩。我的體會是，以后再寫程序的時候一定遵守一定的規(guī)則和習(xí)慣，例如關(guān)鍵詞的命名習(xí)慣，指針的使用形式和結(jié)構(gòu)聯(lián)合中的一些形式的問題，應(yīng)該遵循一定的規(guī)則和習(xí)慣，因?yàn)?，只有這樣的自己在寫好的調(diào)試和檢查的過程中才不會走那么多 的彎路，才會把做事的速度提高上去。

最后，就是自己的一些心得體會對這次的實(shí)驗(yàn)。做什么事情都要認(rèn)真對待，無論事情的大小，因?yàn)橹挥羞@樣自己才會養(yǎng)成認(rèn)真做事的習(xí)慣，這次的數(shù)據(jù)結(jié)構(gòu)的實(shí)驗(yàn)讓我深深的意識到了這一點(diǎn)。

附錄：

實(shí)驗(yàn)三代碼： #include #include #include #include #include

#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 SqBiTree[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_nList[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 = ftell(pFile);//得到當(dāng)前指針位置, 即是文件的長度 rewind(pFile);//文件指針恢復(fù)到文件頭位置

//動態(tài)申請空間, 為保存字符串結(jié)尾標(biāo)志