廣工數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告抽象數(shù)據(jù)類型

1、 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)性實(shí)驗(yàn)報(bào)告 課程名稱_數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn) _ 題目名稱 樹(shù) 學(xué)生學(xué)院_ 計(jì)算機(jī)學(xué)院_ 專業(yè)班級(jí) 13計(jì)科3班 _學(xué) 號(hào)_ _學(xué)生姓名_ _ _指導(dǎo)教師_ _2015 年 7 月 3 日（1）設(shè)計(jì)任務(wù)、要求及所用軟件環(huán)境或工具；（2）抽象數(shù)據(jù)類型定義以及各基本操作的簡(jiǎn)要描述；（3）所選擇的存儲(chǔ)結(jié)構(gòu)描述及在此存儲(chǔ)結(jié)構(gòu)上各基本操作的實(shí)現(xiàn)；（4）程序清單（計(jì)算機(jī)打?。?，輸入的數(shù)據(jù)及各基本操作的測(cè)試結(jié)果；（5）實(shí)驗(yàn)總結(jié)和體會(huì)。實(shí)驗(yàn)報(bào)告以規(guī)定格式的電子文檔書(shū)寫(xiě)、打印并裝訂，排版及圖表要清楚、工整。3.9 思考題 對(duì)設(shè)計(jì)性實(shí)驗(yàn)進(jìn)行總結(jié)和討論，包括本實(shí)驗(yàn)的優(yōu)、缺點(diǎn)，數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)的特點(diǎn)，與其它存儲(chǔ)結(jié)構(gòu)之

2、間的比較等。通過(guò)總結(jié)，可以對(duì)抽象數(shù)據(jù)類型有更全面、深入的認(rèn)識(shí)，這是設(shè)計(jì)性實(shí)驗(yàn)不可缺少的重要內(nèi)容。這部分內(nèi)容應(yīng)作為實(shí)驗(yàn)報(bào)告中的一個(gè)組成部分。1. 題目:樹(shù)所用軟件為vs_2013基本操作：createtree(cstree &t) 功能：創(chuàng)建一棵樹(shù) 操作結(jié)果：輸入根節(jié)點(diǎn)及孩子，構(gòu)造一個(gè)用戶自定義的樹(shù)。destroytree(cstree &t)初始條件：樹(shù)t已存在。操作結(jié)果：銷(xiāo)毀樹(shù)t。treedepth(cstree t)初始條件：樹(shù)t已存在。操作結(jié)果：返回t的深度 。empty(cstree t) 初始條件：判斷樹(shù)t是否為空操作結(jié)果：空為返回ture，不空則返回falsesearch(cstr

3、ee t, telemtype e) 初始條件：樹(shù)t已存在操作結(jié)果：查找t的結(jié)點(diǎn)e并返回其指針若這樣的元素不存在，則返回值為0。levelordertraverse(const cstree &t) 初始條件：樹(shù)t已存在 操作結(jié)果：層次遍歷樹(shù)t insertchild(cstree t, int i, cstree c) 初始條件：樹(shù)t已存在且非空，1id+1操作結(jié)果：插入樹(shù)作為t的第i棵子樹(shù)2 存儲(chǔ)結(jié)構(gòu)定義公用頭文件header.h:#include#include#include#define max_tree_size 100#define true 1#define false 0#d

4、efine ok 1#define error 0#define overflow -2typedef int status;typedef int telemtype;樹(shù)操作頭文件：treefunction.h:#includeheader.h#include #include #include /孩子兄弟表示的樹(shù)typedef struct csnodechar data;struct csnode * firstchild, *nextsibling;*cstree;3. 算法設(shè)計(jì)treefunction.h:#includeheader.h#include #include #incl

5、ude /孩子兄弟表示的樹(shù)typedef struct csnodechar data;struct csnode * firstchild, *nextsibling;*cstree;/*-程序中用到的隊(duì)列-*/typedef cstree qelemtype;/隊(duì)中的元素 typedef struct qnodeqelemtype data;struct qnode *next;qnode, *queueptr;/*typedef struct treenamechar name;struct csnode * nametree;struct treename *next;treename

6、 ,*treenamep;*/typedef structqueueptr front; /隊(duì)頭指針 queueptr rear; /隊(duì)尾指針 linkqueue;status initqueue(linkqueue &q)/構(gòu)造一個(gè)空隊(duì)列 q.front = q.rear = (queueptr)malloc(sizeof(qnode);/隊(duì)頭結(jié)點(diǎn) if (!q.front)exit(overflow);q.front-next = null;return ok;status queueempty(const linkqueue &q)/若隊(duì)列為空，則返回true，否則返回false if

7、(q.rear = q.front)return true;return false;status enqueue(linkqueue &q, qelemtype e) /插入元素e為q的新隊(duì)尾元素 queueptr p = (queueptr)malloc(sizeof(qnode);if (!p)exit(overflow);p-data = e;p-next = null;q.rear-next = p;q.rear = p;return ok;status dequeue(linkqueue &q, qelemtype &e) /若隊(duì)列不空，則刪除q的隊(duì)頭元素，用e返回其值，并返回ok

8、; if (q.front = q.rear)return error; /隊(duì)空 queueptr p = q.front-next;e = p-data;q.front-next = p-next;if (q.rear = p)q.rear = q.front;free(p);return ok;/*-*/構(gòu)造空樹(shù)void init_cstree(csnode *t)t-firstchild = null;t-nextsibling = null;/創(chuàng)建一棵樹(shù)status createtree(cstree &t) /創(chuàng)建一棵樹(shù) linkqueue q;initqueue(q);/構(gòu)造一個(gè)空

9、隊(duì)列 char buffchild10; /用于存放孩子們的緩存 memset(buffchild, 0, 10); /初始化緩存數(shù)組，置為null printf(請(qǐng)輸入樹(shù)的根結(jié)點(diǎn)（字符,以#代表空）:n);scanf_s(%c, &buffchild0,10);if (buffchild0 != #)t = (cstree)malloc(sizeof(csnode);/為根結(jié)點(diǎn)開(kāi)辟一個(gè)空間 if (!t)exit(overflow); /開(kāi)辟失敗，終止程序 t-data = buffchild0;t-nextsibling = null; /根結(jié)點(diǎn)無(wú)兄弟 enqueue(q, t); /根結(jié)

10、點(diǎn)入隊(duì) while (!queueempty(q)qelemtype e;dequeue(q, e); /結(jié)點(diǎn)出隊(duì) /cstree p = e; /用以指向隊(duì)頭結(jié)點(diǎn) printf(請(qǐng)按長(zhǎng)幼順序輸入結(jié)點(diǎn)%c的孩子(字符,以#結(jié)束):n, e-data);fflush(stdin); /清空輸入流緩沖區(qū)的數(shù)據(jù) gets_s(buffchild);/scanf(%s,buffchild); if (buffchild0 != #)/有孩子 cstree q;q = (cstree)malloc(sizeof(csnode); /開(kāi)辟孩子結(jié)點(diǎn)空間 if (!q)exit(overflow);q-dat

11、a = buffchild0; / e-firstchild = q; /指向第一個(gè)孩子 enqueue(q, q); /第一個(gè)孩子入隊(duì) cstree p = q; /指向剛?cè)腙?duì)的孩子 for (size_t i = 1; i data = buffchildi; / p-nextsibling = q;enqueue(q, q);p = q; /指向剛?cè)腙?duì)的孩子 p-nextsibling = null;else/無(wú)孩子 e-firstchild = null;elset = null;/空樹(shù) return ok;/銷(xiāo)毀樹(shù)void destroytree(cstree t)/樹(shù)t存在，銷(xiāo)毀樹(shù)

12、t if (t)/樹(shù)不空 if (t-firstchild)/左子樹(shù)存在，即銷(xiāo)毀以長(zhǎng)子為結(jié)點(diǎn)的子樹(shù) destroytree(t-firstchild);if (t-nextsibling)/右子樹(shù)存在，即銷(xiāo)毀以兄弟為結(jié)點(diǎn)的子樹(shù) destroytree(t-nextsibling);free(t); /釋放根結(jié)點(diǎn) t = null;/返回樹(shù)的深度int treedepth(cstree t)int dep1=0, dep2=0, dep=0;if (null = t)dep = 0;elsedep1 = treedepth(t-firstchild);dep2 = treedepth(t-nex

13、tsibling);dep = dep1 + 1 dep2 ? dep1 + 1 : dep2;return dep; /創(chuàng)建樹(shù)cstree maketree(telemtype e, int n)int i;cstree t, p;cstreep1;va_list argptr; /argptr是存放變長(zhǎng)信息的數(shù)組t = (cstree)malloc(sizeof(csnode);if (null = t)return null;t-data = e; /根節(jié)點(diǎn)的值為et-firstchild = t-nextsibling = null;if (n firstchild = p;p1 =

14、p;for (i = 1; i nextsibling = p;p1 = p;va_end(argptr);return t;/判空status empty(cstree t)/樹(shù)t存在，空樹(shù)返回true，否則返回false if (t)return true;elsereturn false;/插入第i棵子樹(shù)status insertchild(cstree t, int i, cstree c)int j;if (null = t | i nextsibling = t-firstchild;t-firstchild = c;/c成為t的第i棵子樹(shù)elset = t-firstchild;

15、for (j = 2; t != null & j nextsibling;/尋找插入位置if (j = i)c-nextsibling = t-nextsibling;t-nextsibling = c;else return error;/參數(shù)i過(guò)大return ok;/查找t的結(jié)點(diǎn)e并返回其指針csnode* search(cstree t, telemtype e)csnode* result = null;if (null = t)return null;if (t-data = e)return t;if (result = search(t-firstchild, e) != n

16、ull)return result;return search(t-nextsibling, e);status levelordertraverse(const cstree &t)/層次遍歷樹(shù) linkqueue q;initqueue(q);if (t)printf(%c, t-data);/訪問(wèn)結(jié)點(diǎn) enqueue(q, t);/根結(jié)點(diǎn)排隊(duì) while (!queueempty(q)qelemtype e, p;dequeue(q, e);p = e-firstchild;while (p)printf(%c, p-data);enqueue(q, p);p = p-nextsibli

17、ng;return ok;return error;/空樹(shù) 4測(cè)試printf(創(chuàng)建第一棵樹(shù):n);cstree t;createtree(t);int select;for (;) printf(select 1 遍歷該樹(shù) n);printf(select 2 求樹(shù)的深度n);printf(select 3 查找結(jié)點(diǎn) n);printf(select 4 刪除該樹(shù) n);printf(select 5 退出 n);printf(select 6 創(chuàng)建一棵樹(shù) n);printf(input your select: );scanf_s(%d, &select,1);switch (select

18、) case 1: printf(遍歷該樹(shù)：n);levelordertraverse(t); printf(n); break;case 2:printf(n樹(shù)的深度為);printf(%d, treedepth(t); printf(n); break;case 3:printf(n查找結(jié)點(diǎn)：n請(qǐng)輸入要查找的結(jié)點(diǎn)：n);csnode* p;telemtype e;for (;)scanf_s(%c, &e, 1);if (e != n)break;p = search(t, e);if (p=null)printf(該結(jié)點(diǎn)不存在n); break;if (p-data = e)printf(查找成功n);printf(n); break;case 4:printf(n刪除第一棵樹(shù)n);destroytree(t);printf(判空：);int empty;empty =