數據結構實驗(2015級信息安全專業適用)計算機科學與技術學院數組結構課程組2016年1月

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

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

參考文獻[1]嚴蔚敏等.數據結構（C語言版）.清華大學出版社[2]LarryNyhoff.ADTs,DataStructures,andProblemSolvingwithC++.

SecondEdition,CalvinCollege,2005[3]殷立峰.QtC++跨平臺圖形界面程序設計基礎.清華大學出版社,2014:192～197[4]嚴蔚敏等.數據結構題集（C語言版）.清華大學出版社

附錄A順序表實現框架程序清單/*LinearTableOnSequenceStructure*/#include<stdio.h>#include<malloc.h>#include<stdlib.h>/*ontextbook*/#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASTABLE-1#defineOVERFLOW-2typedefintstatus;typedefintElemType;//數據元素類型定義/*ontextbook*/#defineLIST_INIT_SIZE100#defineLISTINCREMENT10typedefstruct{//順序表（順序結構）的定義 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("請選擇你的操作[0~12]:"); scanf("%d",&op);switch(op){ case1: //printf("\nIntiaList功能待實現！\n"); if(IntiaList(L)==OK)printf("線性表創建成功！\n"); elseprintf("線性表創建失??！\n"); getchar();getchar(); break; case2: printf("\nDestroyList功能待實現！\n"); getchar();getchar(); break; case3: printf("\nClearList功能待實現！\n"); getchar();getchar(); break; case4: printf("\nListEmpty功能待實現！\n"); getchar();getchar(); break; case5: printf("\nListLength功能待實現！\n"); getchar();getchar(); break; case6: printf("\nGetElem功能待實現！\n"); getchar();getchar(); break; case7: printf("\nLocateElem功能待實現！\n"); getchar();getchar(); break; case8: printf("\nPriorElem功能待實現！\n"); getchar();getchar(); break; case9: printf("\nNextElem功能待實現！\n"); getchar();getchar(); break; case10: printf("\nListInsert功能待實現！\n"); getchar();getchar(); break; case11: printf("\nListDelete功能待實現！\n"); getchar();getchar(); break; case12: //printf("\nListTrabverse功能待實現！\n"); if(!ListTrabverse(L))printf("線性表是空表！\n"); getchar();getchar(); break; case0:break; }//endofswitch}//endofwhileprintf("歡迎下次再使用本系統！\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數據元素的文件讀寫#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次性寫入，對于其它物理結構，可通過遍歷，逐個訪問數據元素//并寫入到文件中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++;//這里從文件中逐個讀取數據元素恢復順序表，對于不同的物理結構，可通過讀//取的數據元素恢復內存中的物理結構。fclose(fp);return0;}