2016-數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)

數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)(2015級(jí)信息安全專業(yè)適用)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院數(shù)組結(jié)構(gòu)課程組2016年1月

目錄1基于順序存儲(chǔ)結(jié)構(gòu)的線性表實(shí)現(xiàn) 11.1實(shí)驗(yàn)?zāi)康?11.2線性表基本運(yùn)算定義 11.3實(shí)驗(yàn)任務(wù) 22基于二叉鏈表的二叉樹實(shí)現(xiàn) 32.1實(shí)驗(yàn)?zāi)康?32.2二叉樹基本運(yùn)算定義 32.3實(shí)驗(yàn)任務(wù) 5參考文獻(xiàn) 6附錄A順序表實(shí)現(xiàn)框架程序清單 7附錄B數(shù)據(jù)元素的文件讀寫 10附錄C線性表模板實(shí)例 11TOC\h\z\c"圖表"1基于順序存儲(chǔ)結(jié)構(gòu)的線性表實(shí)現(xiàn)1.1實(shí)驗(yàn)?zāi)康耐ㄟ^實(shí)驗(yàn)達(dá)到⑴加深對(duì)線性表的概念、基本運(yùn)算的理解；⑵熟練掌握線性表的邏輯結(jié)構(gòu)與物理結(jié)構(gòu)的關(guān)系；⑶物理結(jié)構(gòu)采用順序表,熟練掌握線性表的基本運(yùn)算的實(shí)現(xiàn)。1.2線性表基本運(yùn)算定義依據(jù)最小完備性和常用性相結(jié)合的原則，以函數(shù)形式定義了線性表的初始化表、銷毀表、清空表、判定空表、求表長和獲得元素等12種基本運(yùn)算，具體運(yùn)算功能定義如下。⑴初始化表：函數(shù)名稱是InitaList(L)；初始條件是線性表L不存在已存在；操作結(jié)果是構(gòu)造一個(gè)空的線性表。⑵銷毀表：函數(shù)名稱是DestroyList(L)；初始條件是線性表L已存在；操作結(jié)果是銷毀線性表L。⑶清空表：函數(shù)名稱是ClearList(L)；初始條件是線性表L已存在；操作結(jié)果是將L重置為空表。⑷判定空表：函數(shù)名稱是ListEmpty(L)；初始條件是線性表L已存在；操作結(jié)果是若L為空表則返回TRUE,否則返回FALSE。⑸求表長：函數(shù)名稱是ListLength(L)；初始條件是線性表已存在；操作結(jié)果是返回L中數(shù)據(jù)元素的個(gè)數(shù)。⑹獲得元素：函數(shù)名稱是GetElem(L,i,e)；初始條件是線性表已存在，1≤i≤ListLength(L)；操作結(jié)果是用e返回L中第i個(gè)數(shù)據(jù)元素的值。⑺查找元素：函數(shù)名稱是LocateElem(L,e,compare())；初始條件是線性表已存在；操作結(jié)果是返回L中第1個(gè)與e滿足關(guān)系compare（）關(guān)系的數(shù)據(jù)元素的位序，若這樣的數(shù)據(jù)元素不存在，則返回值為0。⑻獲得前驅(qū)：函數(shù)名稱是PriorElem(L,cur_e,pre_e)；初始條件是線性表L已存在；操作結(jié)果是若cur_e是L的數(shù)據(jù)元素，且不是第一個(gè)，則用pre_e返回它的前驅(qū)，否則操作失敗，pre_e無定義。⑼獲得后繼：函數(shù)名稱是NextElem(L,cur_e,next_e)；初始條件是線性表L已存在；操作結(jié)果是若cur_e是L的數(shù)據(jù)元素，且不是最后一個(gè)，則用next_e返回它的后繼，否則操作失敗，next_e無定義。⑽插入元素：函數(shù)名稱是ListInsert(L,i,e)；初始條件是線性表L已存在且非空，1≤i≤ListLength(L)+1；操作結(jié)果是在L的第i個(gè)位置之前插入新的數(shù)據(jù)元素e。⑾刪除元素：函數(shù)名稱是ListDelete(L,i,e)；初始條件是線性表L已存在且非空，1≤i≤ListLength(L)；操作結(jié)果：刪除L的第i個(gè)數(shù)據(jù)元素，用e返回其值。⑿遍歷表：函數(shù)名稱是ListTraverse(L,visit())，初始條件是線性表L已存在；操作結(jié)果是依次對(duì)L的每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)visit()。1.3實(shí)驗(yàn)任務(wù)采用順序表作為線性表的物理結(jié)構(gòu)，實(shí)現(xiàn)§1.2的基本運(yùn)算。其中ElemType為數(shù)據(jù)元素的類型名，具體含義可自行定義，其它有關(guān)類型和常量的定義和引用詳見文獻(xiàn)[1]的p10。要求構(gòu)造一個(gè)具有菜單的功能演示系統(tǒng)。其中，在主程序中完成函數(shù)調(diào)用所需實(shí)參值的準(zhǔn)備和函數(shù)執(zhí)行結(jié)果的顯示，并給出適當(dāng)?shù)牟僮魈崾撅@示。附錄A提供了簡易菜單的框架。演示系統(tǒng)可選擇實(shí)現(xiàn)線性表的文件形式保存。其中，①需要設(shè)計(jì)文件數(shù)據(jù)記錄格式，以高效保存線性表數(shù)據(jù)邏輯結(jié)構(gòu)(D,{R})的完整信息；②需要設(shè)計(jì)線性表文件保存和加載操作合理模式。附錄B提供了文件存取的方法。演示系統(tǒng)可選擇實(shí)現(xiàn)多個(gè)線性表管理。撰寫本次實(shí)驗(yàn)報(bào)告，作為課程實(shí)驗(yàn)報(bào)告第一章的內(nèi)容，其內(nèi)容至少包括問題描述、系統(tǒng)設(shè)計(jì)、系統(tǒng)實(shí)現(xiàn)和實(shí)驗(yàn)小結(jié)。實(shí)驗(yàn)報(bào)告需要按照規(guī)范格式要求規(guī)范排版，詳見“2016-數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告格式示例(2014級(jí)信息安全專業(yè)).docx”。演示系統(tǒng)的源程序應(yīng)按照代碼規(guī)范增加注釋和排版，目標(biāo)程序務(wù)必是可以獨(dú)立于IDE運(yùn)行的EXE文件。按照公告的時(shí)間及時(shí)提交電子檔實(shí)驗(yàn)資料，所有資料存儲(chǔ)于每位同學(xué)自己的相應(yīng)文件夾下，其文件夾名稱格式為“專業(yè)班級(jí)-學(xué)號(hào)姓名-n”。如：IS1402-U201414999李某某-n。其中，n表示第n次實(shí)驗(yàn)報(bào)告。資料至少包括實(shí)驗(yàn)報(bào)告、實(shí)驗(yàn)源程序和實(shí)驗(yàn)?zāi)繕?biāo)程序。根據(jù)需要還可以增加測(cè)試用例文件等等。

2基于二叉鏈表的二叉樹實(shí)現(xiàn)2.1實(shí)驗(yàn)?zāi)康耐ㄟ^實(shí)驗(yàn)達(dá)到⑴加深對(duì)二叉樹的概念、基本運(yùn)算的理解；⑵熟練掌握二叉樹的邏輯結(jié)構(gòu)與物理結(jié)構(gòu)的關(guān)系；⑶以二叉鏈表作為物理結(jié)構(gòu)，熟練掌握二叉樹基本運(yùn)算的實(shí)現(xiàn)。2.2二叉樹基本運(yùn)算定義依據(jù)最小完備性和常用性相結(jié)合的原則，以函數(shù)形式定義了二叉樹的初始化二叉樹、銷毀二叉樹、創(chuàng)建二叉樹、清空二叉樹、判定空二叉樹和求二叉樹深度等20種基本運(yùn)算，具體運(yùn)算功能定義如下。⑴初始化二叉樹：函數(shù)名稱是InitBiTree(T)；初始條件是二叉樹T不存在；操作結(jié)果是構(gòu)造空二叉樹T。⑵銷毀二叉：樹函數(shù)名稱是DestroyBiTree(T)；初始條件是二叉樹T已存在；操作結(jié)果是銷毀二叉樹T。⑶創(chuàng)建二叉樹：函數(shù)名稱是CreateBiTree(T,definition)；初始條件是definition給出二叉樹T的定義；操作結(jié)果是按definition構(gòu)造二叉樹T。⑷清空二叉樹：函數(shù)名稱是ClearBiTree(T)；初始條件是二叉樹T存在； 操作結(jié)果是將二叉樹T清空。⑸判定空二叉樹：函數(shù)名稱是BiTreeEmpty(T)；初始條件是二叉樹T存在；操作結(jié)果是若T為空二叉樹則返回TRUE，否則返回FALSE。⑹求二叉樹深度：函數(shù)名稱是BiTreeDepth(T)；初始條件是二叉樹T存在；操作結(jié)果是返回T的深度。⑺獲得根結(jié)點(diǎn)：函數(shù)名稱是Root(T)；初始條件是二叉樹T已存在；操作結(jié)果是返回T的根。⑻獲得結(jié)點(diǎn)：函數(shù)名稱是Value(T,e)；初始條件是二叉樹T已存在，e是T中的某個(gè)結(jié)點(diǎn)；操作結(jié)果是返回e的值。⑼結(jié)點(diǎn)賦值：函數(shù)名稱是Assign(T,&e,value)；初始條件是二叉樹T已存在，e是T中的某個(gè)結(jié)點(diǎn)；操作結(jié)果是結(jié)點(diǎn)e賦值為value。⑽獲得雙親結(jié)點(diǎn)：函數(shù)名稱是Parent(T,e)；初始條件是二叉樹T已存在，e是T中的某個(gè)結(jié)點(diǎn)；操作結(jié)果是若e是T的非根結(jié)點(diǎn)，則返回它的雙親結(jié)點(diǎn)指針，否則返回NULL。⑾獲得左孩子結(jié)點(diǎn)：函數(shù)名稱是LeftChild(T,e)；初始條件是二叉樹T存在，e是T中某個(gè)節(jié)點(diǎn)；操作結(jié)果是返回e的左孩子結(jié)點(diǎn)指針。若e無左孩子，則返回NULL。⑿獲得右孩子結(jié)點(diǎn)：函數(shù)名稱是RightChild(T,e)；初始條件是二叉樹T已存在，e是T中某個(gè)結(jié)點(diǎn)；操作結(jié)果是返回e的右孩子結(jié)點(diǎn)指針。若e無右孩子，則返回NULL。⒀獲得左兄弟結(jié)點(diǎn)：函數(shù)名稱是LeftSibling(T,e)；初始條件是二叉樹T存在，e是T中某個(gè)結(jié)點(diǎn)；操作結(jié)果是返回e的左兄弟結(jié)點(diǎn)指針。若e是T的左孩子或者無左兄弟，則返回NULL。⒁獲得右兄弟結(jié)點(diǎn)：函數(shù)名稱是RightSibling(T,e)；初始條件是二叉樹T已存在，e是T中某個(gè)結(jié)點(diǎn)；操作結(jié)果是返回e的右兄弟結(jié)點(diǎn)指針。若e是T的右孩子或者無有兄弟，則返回NULL。⒂插入子樹：函數(shù)名稱是InsertChild(T,p,LR,c)；初始條件是二叉樹T存在，p指向T中的某個(gè)結(jié)點(diǎn)，LR為0或1，,非空二叉樹c與T不相交且右子樹為空；操作結(jié)果是根據(jù)LR為0或者1，插入c為T中p所指結(jié)點(diǎn)的左或右子樹，p 所指結(jié)點(diǎn)的原有左子樹或右子樹則為c的右子樹。⒃刪除子樹：函數(shù)名稱是DeleteChild(T.p.LR)；初始條件是二叉樹T存在，p指向T中的某個(gè)結(jié)點(diǎn)，LR為0或1。 操作結(jié)果是根據(jù)LR為0或者1，刪除c為T中p所指結(jié)點(diǎn)的左或右子樹。⒄前序遍歷：函數(shù)名稱是PreOrderTraverse(T,Visit())；初始條件是二叉樹T存在，Visit是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)；操作結(jié)果：先序遍歷t，對(duì)每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)Visit一次且一次，一旦調(diào)用失敗，則操作失敗。⒅中序遍歷：函數(shù)名稱是InOrderTraverse(T,Visit))；初始條件是二叉樹T存在，Visit是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)；操作結(jié)果是中序遍歷t，對(duì)每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)Visit一次且一次，一旦調(diào)用失敗，則操作失敗。⒆后序遍歷：函數(shù)名稱是PostOrderTraverse(T,Visit))；初始條件是二叉樹T存在，Visit是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)；操作結(jié)果是后序遍歷t，對(duì)每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)Visit一次且一次，一旦調(diào)用失敗，則操作失敗。⒇按層遍歷：函數(shù)名稱是LevelOrderTraverse(T,Visit))；初始條件是二叉樹T存在，Visit是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)；操作結(jié)果是層序遍歷t，對(duì)每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)Visit一次且一次，一旦調(diào)用失敗，則操作失敗。2.3實(shí)驗(yàn)任務(wù)采用二叉鏈表表作為二叉樹的物理結(jié)構(gòu)，實(shí)現(xiàn)§2.2的基本運(yùn)算。其中ElemType為數(shù)據(jù)元素的類型名，具體含義可自行定義，其它有關(guān)類型和常量的定義和引用詳見文獻(xiàn)[1]的p10。要求構(gòu)造一個(gè)具有菜單的功能演示系統(tǒng)。其中，在主程序中完成函數(shù)調(diào)用所需實(shí)參值的準(zhǔn)備和函數(shù)執(zhí)行結(jié)果的顯示，并給出適當(dāng)?shù)牟僮魈崾撅@示。演示系統(tǒng)可選擇實(shí)現(xiàn)二叉樹的文件形式保存。其中，①需要設(shè)計(jì)文件數(shù)據(jù)記錄格式，以高效保存二叉樹數(shù)據(jù)邏輯結(jié)構(gòu)(D,{R})的完整信息；②需要設(shè)計(jì)線性表文件保存和加載操作合理模式。附錄B提供了文件存取的方法。演示系統(tǒng)可選擇實(shí)現(xiàn)多個(gè)二叉樹管理?？刹捎镁€性表的方式管理多個(gè)二叉樹，線性表中的每個(gè)數(shù)據(jù)元素為一個(gè)二叉樹的基本屬性，至少應(yīng)包含有二叉樹的名稱?；陧樞虮韺?shí)現(xiàn)的二叉樹管理，其物理結(jié)構(gòu)的參考設(shè)計(jì)如圖2-1所示。圖2-1多二叉樹管理的物理結(jié)構(gòu)示意圖演示系統(tǒng)的源程序應(yīng)按照代碼規(guī)范增加注釋和排版，目標(biāo)程序務(wù)必是可以獨(dú)立于IDE運(yùn)行的EXE文件。撰寫本次實(shí)驗(yàn)報(bào)告，作為課程實(shí)驗(yàn)報(bào)告第二章的內(nèi)容，其內(nèi)容至少包括問題描述、系統(tǒng)設(shè)計(jì)、系統(tǒng)實(shí)現(xiàn)和實(shí)驗(yàn)小結(jié)。實(shí)驗(yàn)報(bào)告需要按照規(guī)范格式要求規(guī)范排版，詳見“2016-數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告格式示例(2014級(jí)信息安全專業(yè)).docx”。按照公告的時(shí)間及時(shí)提交電子檔實(shí)驗(yàn)資料，所有資料存儲(chǔ)于每位同學(xué)自己的相應(yīng)文件夾下，其文件夾名稱格式為“專業(yè)班級(jí)-學(xué)號(hào)姓名-n”。如：IS1402-U201414999李某某-n。其中，n表示第n次實(shí)驗(yàn)報(bào)告。資料至少包括實(shí)驗(yàn)報(bào)告、實(shí)驗(yàn)源程序和實(shí)驗(yàn)?zāi)繕?biāo)程序。根據(jù)需要還可以增加測(cè)試用例文件等等。

參考文獻(xiàn)[1]嚴(yán)蔚敏等.數(shù)據(jù)結(jié)構(gòu)（C語言版）.清華大學(xué)出版社[2]LarryNyhoff.ADTs,DataStructures,andProblemSolvingwithC++.

SecondEdition,CalvinCollege,2005[3]殷立峰.QtC++跨平臺(tái)圖形界面程序設(shè)計(jì)基礎(chǔ).清華大學(xué)出版社,2014:192～197[4]嚴(yán)蔚敏等.數(shù)據(jù)結(jié)構(gòu)題集（C語言版）.清華大學(xué)出版社

附錄A順序表實(shí)現(xiàn)框架程序清單/*LinearTableOnSequenceStructure*/#include<stdio.h>#include<malloc.h>#include<stdlib.h>/*ontextbook*/#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASTABLE-1#defineOVERFLOW-2typedefintstatus;typedefintElemType;//數(shù)據(jù)元素類型定義/*ontextbook*/#defineLIST_INIT_SIZE100#defineLISTINCREMENT10typedefstruct{//順序表（順序結(jié)構(gòu)）的定義 ElemType*elem; intlength; intlistsize;}SqList;/*ontextbook*/statusIntiaList(SqList&L);//statusDestroyList(SqList&L);//statusClearList(SqList&L);//statusListEmpty(SqListL);//intListLength(SqListL);//statusGetElem(SqListL,inti,ElemType&e);//statusLocateElem(SqListL,ElemTypee);//簡化過//statusPriorElem(SqListL,ElemTypecur,ElemType&pre_e);//statusNextElem(SqListL,ElemTypecur,ElemType&next_e);//statusListInsert(SqList&L,inti,ElemTypee);statusListDelete(SqList&L,inti,ElemType&e);statusListTrabverse(SqListL);//簡化過/**/voidmain(void){SqListL;intop=1;while(op){ system("cls"); printf("\n\n"); printf("MenuforLinearTableOnSequenceStructure\n"); printf("\n"); printf(" 1.IntiaList7.LocateElem\n"); printf(" 2.DestroyList8.PriorElem\n"); printf(" 3.ClearList9.NextElem\n"); printf(" 4.ListEmpty10.ListInsert\n"); printf(" 5.ListLength11.ListDelete\n"); printf(" 6.GetElem12.ListTrabverse\n"); printf(" 0.Exit\n"); printf("\n"); printf("請(qǐng)選擇你的操作[0~12]:"); scanf("%d",&op);switch(op){ case1: //printf("\nIntiaList功能待實(shí)現(xiàn)！\n"); if(IntiaList(L)==OK)printf("線性表創(chuàng)建成功！\n"); elseprintf("線性表創(chuàng)建失??！\n"); getchar();getchar(); break; case2: printf("\nDestroyList功能待實(shí)現(xiàn)！\n"); getchar();getchar(); break; case3: printf("\nClearList功能待實(shí)現(xiàn)！\n"); getchar();getchar(); break; case4: printf("\nListEmpty功能待實(shí)現(xiàn)！\n"); getchar();getchar(); break; case5: printf("\nListLength功能待實(shí)現(xiàn)！\n"); getchar();getchar(); break; case6: printf("\nGetElem功能待實(shí)現(xiàn)！\n"); getchar();getchar(); break; case7: printf("\nLocateElem功能待實(shí)現(xiàn)！\n"); getchar();getchar(); break; case8: printf("\nPriorElem功能待實(shí)現(xiàn)！\n"); getchar();getchar(); break; case9: printf("\nNextElem功能待實(shí)現(xiàn)！\n"); getchar();getchar(); break; case10: printf("\nListInsert功能待實(shí)現(xiàn)！\n"); getchar();getchar(); break; case11: printf("\nListDelete功能待實(shí)現(xiàn)！\n"); getchar();getchar(); break; case12: //printf("\nListTrabverse功能待實(shí)現(xiàn)！\n"); if(!ListTrabverse(L))printf("線性表是空表！\n"); getchar();getchar(); break; case0:break; }//endofswitch}//endofwhileprintf("歡迎下次再使用本系統(tǒng)！\n");}//endofmain()/*ontextbook*/statusIntiaList(SqList&L){ L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!L.elem)exit(OVERFLOW); L.length=0;L.listsize=LIST_INIT_SIZE; returnOK;}statusListTrabverse(SqListL){inti;printf("\nallelements\n");for(i=0;i<L.length;i++)printf("%d",L.elem[i]);printf("\nend\n");returnL.length;}

附錄B數(shù)據(jù)元素的文件讀寫#include<stdio.h>#include<stdlib.h>typedefstruct{ charc; intd; floatf;}ElemType;typedefstruct{ ElemTypeelem[10]; intlength; }SqList;SqListL={{{'a',1,1.1},{'b',2,2.2},{'c',3,3.3},{'d',4,4.4}},4};intmain(intargc,char*argv[]){FILE*fp;charfilename[30];inti;printf("inputfilename:");scanf("%s",filename);//寫文件的方法if((fp=fopen(filename,"w"))==NULL) { printf("Fileopenerroe\n"); return1; }fwrite(L.elem,sizeof(ElemType),L.length,fp);//這里是1次性寫入，對(duì)于其它物理結(jié)構(gòu)，可通過遍歷，逐個(gè)訪問數(shù)據(jù)元素//并寫入到文件中fclose(fp); //讀文件的方法L.length=0;if((fp=fopen(filename,"r"))==NULL) { printf("Fileopenerroe\n"); return1; }while(fread(&L.elem[L.length],sizeof(ElemType),1,fp))L.length++;//這里從文件中逐個(gè)讀取數(shù)據(jù)元素恢復(fù)順序表，對(duì)于不同的物理結(jié)構(gòu)，可通過讀//取的數(shù)據(jù)元素恢復(fù)內(nèi)存中的物理結(jié)構(gòu)。fclose(fp);return0;}