廣工數(shù)據(jù)結構實驗報告抽象數(shù)據(jù)類型

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

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

3、ee t, telemtype e) 初始條件：樹t已存在操作結果：查找t的結點e并返回其指針若這樣的元素不存在，則返回值為0。levelordertraverse(const cstree &t) 初始條件：樹t已存在 操作結果：層次遍歷樹t insertchild(cstree t, int i, cstree c) 初始條件：樹t已存在且非空，1id+1操作結果：插入樹作為t的第i棵子樹2 存儲結構定義公用頭文件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;樹操作頭文件：treefunction.h:#includeheader.h#include #include #include /孩子兄弟表示的樹typedef struct csnodechar data;struct csnode * firstchild, *nextsibling;*cstree;3. 算法設計treefunction.h:#includeheader.h#include #include #incl

5、ude /孩子兄弟表示的樹typedef struct csnodechar data;struct csnode * firstchild, *nextsibling;*cstree;/*-程序中用到的隊列-*/typedef cstree qelemtype;/隊中的元素 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; /隊頭指針 queueptr rear; /隊尾指針 linkqueue;status initqueue(linkqueue &q)/構造一個空隊列 q.front = q.rear = (queueptr)malloc(sizeof(qnode);/隊頭結點 if (!q.front)exit(overflow);q.front-next = null;return ok;status queueempty(const linkqueue &q)/若隊列為空，則返回true，否則返回false if

7、(q.rear = q.front)return true;return false;status enqueue(linkqueue &q, qelemtype e) /插入元素e為q的新隊尾元素 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) /若隊列不空，則刪除q的隊頭元素，用e返回其值，并返回ok

8、; if (q.front = q.rear)return error; /隊空 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;/*-*/構造空樹void init_cstree(csnode *t)t-firstchild = null;t-nextsibling = null;/創(chuàng)建一棵樹status createtree(cstree &t) /創(chuàng)建一棵樹 linkqueue q;initqueue(q);/構造一個空

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

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

11、a = buffchild0; / e-firstchild = q; /指向第一個孩子 enqueue(q, q); /第一個孩子入隊 cstree p = q; /指向剛入隊的孩子 for (size_t i = 1; i data = buffchildi; / p-nextsibling = q;enqueue(q, q);p = q; /指向剛入隊的孩子 p-nextsibling = null;else/無孩子 e-firstchild = null;elset = null;/空樹 return ok;/銷毀樹void destroytree(cstree t)/樹t存在，銷毀樹

12、t if (t)/樹不空 if (t-firstchild)/左子樹存在，即銷毀以長子為結點的子樹 destroytree(t-firstchild);if (t-nextsibling)/右子樹存在，即銷毀以兄弟為結點的子樹 destroytree(t-nextsibling);free(t); /釋放根結點 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-nex

13、tsibling);dep = dep1 + 1 dep2 ? dep1 + 1 : dep2;return dep; /創(chuàng)建樹cstree maketree(telemtype e, int n)int i;cstree t, p;cstreep1;va_list argptr; /argptr是存放變長信息的數(shù)組t = (cstree)malloc(sizeof(csnode);if (null = t)return null;t-data = e; /根節(jié)點的值為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)/樹t存在，空樹返回true，否則返回false if (t)return true;elsereturn false;/插入第i棵子樹status insertchild(cstree t, int i, cstree c)int j;if (null = t | i nextsibling = t-firstchild;t-firstchild = c;/c成為t的第i棵子樹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過大return ok;/查找t的結點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)/層次遍歷樹 linkqueue q;initqueue(q);if (t)printf(%c, t-data);/訪問結點 enqueue(q, t);/根結點排隊 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;/空樹 4測試printf(創(chuàng)建第一棵樹:n);cstree t;createtree(t);int select;for (;) printf(select 1 遍歷該樹 n);printf(select 2 求樹的深度n);printf(select 3 查找結點 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

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