廣工數(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) _ 題目名稱 樹 學(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ù)類型定義以及各基本操作的簡要描述；（3）所選擇的存儲(chǔ)結(jié)構(gòu)描述及在此存儲(chǔ)結(jié)構(gòu)上各基本操作的實(shí)現(xiàn)；（4）程序清單（計(jì)算機(jī)打印），輸入的數(shù)據(jù)及各基本操作的測試結(jié)果；（5）實(shí)驗(yàn)總結(jié)和體會(huì)。實(shí)驗(yàn)報(bào)告以規(guī)定格式的電子文檔書寫、打印并裝訂，排版及圖表要清楚、工整。3.9 思考題 對設(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、間的比較等。通過總結(jié)，可以對抽象數(shù)據(jù)類型有更全面、深入的認(rèn)識(shí)，這是設(shè)計(jì)性實(shí)驗(yàn)不可缺少的重要內(nèi)容。這部分內(nèi)容應(yīng)作為實(shí)驗(yàn)報(bào)告中的一個(gè)組成部分。1. 題目:樹所用軟件為vs_2013基本操作：createtree(cstree &t) 功能：創(chuàng)建一棵樹 操作結(jié)果：輸入根節(jié)點(diǎn)及孩子，構(gòu)造一個(gè)用戶自定義的樹。destroytree(cstree &t)初始條件：樹t已存在。操作結(jié)果：銷毀樹t。treedepth(cstree t)初始條件：樹t已存在。操作結(jié)果：返回t的深度 。empty(cstree t) 初始條件：判斷樹t是否為空操作結(jié)果：空為返回ture，不空則返回falsesea

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

4、gt;#define max_tree_size 100#define true 1#define false 0#define ok 1#define error 0#define overflow -2typedef int status;typedef int telemtype;樹操作頭文件：treefunction.h:#include"header.h"#include <stdarg.h>#include <string.h> #include <stddef.h> /孩子兄弟表示的樹typedef struct csnod

5、echar data;struct csnode * firstchild, *nextsibling;*cstree;3. 算法設(shè)計(jì)treefunction.h:#include"header.h"#include <stdarg.h>#include <string.h> #include <stddef.h> /孩子兄弟表示的樹typedef struct csnodechar data;struct csnode * firstchild, *nextsibling;*cstree;/*-程序中用到的隊(duì)列-*/typedef cs

6、tree qelemtype;/隊(duì)中的元素 typedef struct qnodeqelemtype data;struct qnode *next;qnode, *queueptr;/*typedef struct treenamechar name;struct csnode * nametree;struct treename *next;treename ,*treenamep;*/typedef structqueueptr front; /隊(duì)頭指針 queueptr rear; /隊(duì)尾指針 linkqueue;status initqueue(linkqueue &q)/

7、構(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 (q.rear = q.front)return true;return false;status enqueue(linkqueue &q, qelemtype e) /插入元素e為q的新隊(duì)尾元素 q

8、ueueptr 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; if (q.front = q.rear)return error; /隊(duì)空 queueptr p = q.front->next;e = p->

9、data;q.front->next = p->next;if (q.rear = p)q.rear = q.front;free(p);return ok;/*-*/構(gòu)造空樹void init_cstree(csnode *t)t->firstchild = null;t->nextsibling = null;/創(chuàng)建一棵樹status createtree(cstree &t) /創(chuàng)建一棵樹 linkqueue q;initqueue(q);/構(gòu)造一個(gè)空隊(duì)列 char buffchild10; /用于存放孩子們的緩存 memset(buffchild, 0,

10、 10); /初始化緩存數(shù)組，置為null printf("請輸入樹的根結(jié)點(diǎn)（字符,以#代表空）:n");scanf_s("%c", &buffchild0,10);if (buffchild0 != '#')t = (cstree)malloc(sizeof(csnode);/為根結(jié)點(diǎn)開辟一個(gè)空間 if (!t)exit(overflow); /開辟失敗，終止程序 t->data = buffchild0;t->nextsibling = null; /根結(jié)點(diǎn)無兄弟 enqueue(q, t); /根結(jié)點(diǎn)入隊(duì) whi

11、le (!queueempty(q)qelemtype e;dequeue(q, e); /結(jié)點(diǎn)出隊(duì) /cstree p = e; /用以指向隊(duì)頭結(jié)點(diǎn) printf("請按長幼順序輸入結(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); /開辟孩子結(jié)

12、點(diǎn)空間 if (!q)exit(overflow);q->data = buffchild0; / e->firstchild = q; /指向第一個(gè)孩子 enqueue(q, q); /第一個(gè)孩子入隊(duì) cstree p = q; /指向剛?cè)腙?duì)的孩子 for (size_t i = 1; i < strlen(buffchild) - 1; +i) /孩子存在兄弟 q = (cstree)malloc(sizeof(csnode); /開辟孩子結(jié)點(diǎn)空間 if (!q)exit(overflow);q->data = buffchildi; / p->nextsib

13、ling = q;enqueue(q, q);p = q; /指向剛?cè)腙?duì)的孩子 p->nextsibling = null;else/無孩子 e->firstchild = null;elset = null;/空樹 return ok;/銷毀樹void destroytree(cstree t)/樹t存在，銷毀樹t if (t)/樹不空 if (t->firstchild)/左子樹存在，即銷毀以長子為結(jié)點(diǎn)的子樹 destroytree(t->firstchild);if (t->nextsibling)/右子樹存在，即銷毀以兄弟為結(jié)點(diǎn)的子樹 destroytre

14、e(t->nextsibling);free(t); /釋放根結(jié)點(diǎn) t = null;/返回樹的深度int treedepth(cstree t)int dep1=0, dep2=0, dep=0;if (null = t)dep = 0;elsedep1 = treedepth(t->firstchild);dep2 = treedepth(t->nextsibling);dep = dep1 + 1 > dep2 ? dep1 + 1 : dep2;return dep; /創(chuàng)建樹cstree maketree(telemtype e, int n)int i;cs

15、tree t, p;cstreep1;va_list argptr; /argptr是存放變長信息的數(shù)組t = (cstree)malloc(sizeof(csnode);if (null = t)return null;t->data = e; /根節(jié)點(diǎn)的值為et->firstchild = t->nextsibling = null;if (n <= 0)return t; /若無子樹，則返回根節(jié)點(diǎn)va_start(argptr, n);p = va_arg(argptr, cstree);t->firstchild = p;p1 = p;for (i = 1

16、; i < n; i+) /將n課樹作為根節(jié)點(diǎn)的子樹插入p = va_arg(argptr, cstree);p1->nextsibling = p;p1 = p;va_end(argptr);return t;/判空status empty(cstree t)/樹t存在，空樹返回true，否則返回false if (t)return true;elsereturn false;/插入第i棵子樹status insertchild(cstree t, int i, cstree c)int j;if (null = t | i < 1)return error;if (1 =

17、 i)/c插入為t的第1棵子樹c->nextsibling = t->firstchild;t->firstchild = c;/c成為t的第i棵子樹elset = t->firstchild;for (j = 2; t != null && j < i; j+) t = t->nextsibling;/尋找插入位置if (j = i)c->nextsibling = t->nextsibling;t->nextsibling = c;else return error;/參數(shù)i過大return ok;/查找t的結(jié)點(diǎn)e并返回

18、其指針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) != null)return result;return search(t->nextsibling, e);status levelordertraverse(const cstree &t)/層次遍歷樹 linkqueue q;initqueue(q);if (t)pr

19、intf("%c", t->data);/訪問結(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->nextsibling;return ok;return error;/空樹 4測試printf("創(chuàng)建第一棵樹:n");cstree t;createtree(t);int sel

20、ect;for (;) printf("select 1 遍歷該樹 n");printf("select 2 求樹的深度n");printf("select 3 查找結(jié)點(diǎn) n");printf("select 4 刪除該樹 n");printf("select 5 退出 n");printf("select 6 創(chuàng)建一棵樹 n");printf("input your select: ");scanf_s("%d", &select,1);switch (select) case 1: printf("遍歷該樹：n");levelordertraverse(t); printf("n"); break;case 2:printf("n樹的深度為");printf("%d", treedepth(t); printf("n"); break;case 3:print