版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領
文檔簡介
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 =
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經(jīng)權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
- 6. 下載文件中如有侵權或不適當內容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 氣象課程設計素材
- 北京林業(yè)大學《白描與工筆重彩》2022-2023學年第一學期期末試卷
- 電子技術課程設計i
- GRP75-IN-1-hydrochloride-生命科學試劑-MCE
- 北京聯(lián)合大學《小學信息技術活動與競賽專題》2022-2023學年第一學期期末試卷
- 手繪人物速寫課程設計
- 妝前乳市場環(huán)境與對策分析
- 原電池相關項目建議書
- 北京聯(lián)合大學《教育學》2021-2022學年第一學期期末試卷
- 噴灌系統(tǒng)課課程設計
- 物業(yè)工程部日常工作安全知識
- 第一章城市設計導論
- 中醫(yī)康復技術專業(yè)設置論證報告
- 冠心病診斷與治療指南課件
- 《玻璃知識培訓》課件
- 小兒灌腸培訓課件
- 骨巨細胞瘤學習課件
- 安全教育培訓課件:食品安全法律法規(guī)
- 心律失常門診工作制度
- 國際貨物獨家代理協(xié)議書
- 2024年湖北交投集團招聘筆試參考題庫含答案解析
評論
0/150
提交評論