【正文】 課 程 實(shí) 驗(yàn) 報(bào) 告課程名稱： 數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn) 專業(yè)班級(jí)： 信息安全201502 學(xué) 號(hào)： 姓 名： 指導(dǎo)教師： 報(bào)告日期： 2016年 10月 28 日 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院華中科技大學(xué)計(jì)算機(jī)學(xué)院數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告目 1基于順序存儲(chǔ)結(jié)構(gòu)的線性表實(shí)現(xiàn) 1 1 1 1 12 基于二叉鏈表的二叉樹(shù)實(shí)現(xiàn) 2 2 2 2 2指導(dǎo)教師評(píng)定意見(jiàn) 3附錄A 基于順序存儲(chǔ)結(jié)構(gòu)線性表實(shí)現(xiàn)的源程序 4附錄B 基于二叉鏈表二叉樹(shù)實(shí)現(xiàn)的源程序 5章為宋體小4號(hào)加粗，其余宋體小4號(hào)，,段落前后0行華中科技大學(xué)計(jì)算機(jī)學(xué)院數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告1 基于順序存儲(chǔ)結(jié)構(gòu)的線性表實(shí)現(xiàn)黑體小2加粗，居中， 問(wèn)題描述黑體4號(hào)加粗，采用順序表的物理結(jié)構(gòu)，構(gòu)造一個(gè)具有菜單的功能演示系統(tǒng)。其中，在主程序中完成函數(shù)調(diào)用所需實(shí)參值的準(zhǔn)備和函數(shù)執(zhí)行結(jié)果的顯示。定義了線性表的初始化表、銷毀表、清空表、判定空表、求表長(zhǎng)和獲得元素等基本運(yùn)算對(duì)應(yīng)的函數(shù)，并給出適當(dāng)?shù)牟僮魈崾撅@示，可選擇以文件的形式進(jìn)行存儲(chǔ)和加載，即將生成的線性表存入到相應(yīng)的文件中，也可以從文件中獲取線性表進(jìn)行操作。 線性表的基本概念線性表是最常用且最簡(jiǎn)單的一種數(shù)據(jù)結(jié)構(gòu)，即n個(gè)數(shù)據(jù)元素的有限序列。線性表中元素的個(gè)數(shù)n定義為線性表的長(zhǎng)度，n=0時(shí)成為空表。在非空表中的每個(gè)數(shù)據(jù)元素都有一個(gè)確定的位置，如a1是第一個(gè)數(shù)據(jù)元素，an是最后一個(gè)數(shù)據(jù)元素，ai是第i個(gè)數(shù)據(jù)元素。線性表的存儲(chǔ)結(jié)構(gòu)分為線性存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。 邏輯結(jié)構(gòu)與基本運(yùn)算線性表的數(shù)據(jù)邏輯結(jié)構(gòu)定義如下: ADT List｛ 數(shù)據(jù)對(duì)象：D=｛ai|ai∈ElemSet，i=1，2，……，n，n≥0｝ 數(shù)據(jù)關(guān)系：R1=｛ ai1，ai | ai1，ai∈D，i=2，……，n｝ ｝ 依據(jù)最小完備性和常用性相結(jié)合的原則，以函數(shù)形式定義了包括線性表的初始化表、加載表、保存表、銷毀表、清空表、判定空表、求表長(zhǎng)、獲得元素、查找元素、獲得前驅(qū)、獲得后繼、插入元素、刪除元素、遍歷表 14 個(gè)基本運(yùn)算，要求分別定義函數(shù)來(lái)實(shí)現(xià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。⑸求表長(zhǎng)：函數(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,pare())；初始條件是線性表已存在；操作結(jié)果是返回L中第1個(gè)與e滿足關(guān)系pare（）關(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無(wú)定義。⑼獲得后繼：函數(shù)名稱是NextElem(L,cur_e,next_e)；初始條件是線性表L已存在；操作結(jié)果是若cur_e是L的數(shù)據(jù)元素，且不是最后一個(gè)，則用next_e返回它的后繼，否則操作失敗，next_e無(wú)定義。⑽插入元素：函數(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()。 演示系統(tǒng)與數(shù)據(jù)文件要求構(gòu)造一個(gè)具有菜單的功能演示系統(tǒng)。其中，在主程序中完成函數(shù)調(diào)用所需實(shí)參值的準(zhǔn)備和函數(shù)執(zhí)行結(jié)果的顯示，并給出適當(dāng)?shù)牟僮魈崾撅@示。附錄 A 提供了簡(jiǎn)易菜單的框架。 演示系統(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è)線性表管理。 系統(tǒng)設(shè)計(jì)黑體4號(hào)加粗， 數(shù)據(jù)物理結(jié)構(gòu)線性表的數(shù)據(jù)物理結(jié)構(gòu)如下： typedef struct { //順序表（順序結(jié)構(gòu)）的定義 ElemType *elem。 //定義整型指針，為存儲(chǔ)空間基址 int length。 //線性表的長(zhǎng)度 int listsize。 //當(dāng)前分配的存儲(chǔ)容量(以 sizeof(ElemType)為單位) }SqList。 要實(shí)現(xiàn)同時(shí)對(duì)多個(gè)線性表管理，只需要定義一個(gè)結(jié)構(gòu)數(shù)組即可。 演示系統(tǒng) 將菜單演示和用戶選擇寫(xiě)入到while循環(huán)中，用OP獲取用戶的選擇，OP初始化為1，以便第一次能進(jìn)入循環(huán)。進(jìn)入循環(huán)后系統(tǒng)首先顯示功能菜單，然后用戶輸入選擇014，其中114分別代表線性表的一個(gè)基本運(yùn)算，在主函數(shù)中通過(guò)SWITCH語(yǔ)句對(duì)應(yīng)到相應(yīng)的函數(shù)功能，執(zhí)行完該功能后BREAK跳出SWITCH語(yǔ)句，繼續(xù)執(zhí)行while循環(huán)，直至用戶輸入0退出當(dāng)前演示系統(tǒng)。在第一次進(jìn)入循環(huán)while時(shí)首先會(huì)詢問(wèn)用戶對(duì)哪個(gè)線性表進(jìn)行操作，直至退出演示系統(tǒng)之前一直對(duì)指定線性表進(jìn)行操作。演示系統(tǒng)結(jié)構(gòu)如圖11. 運(yùn)算算法思想與設(shè)計(jì) 線性表運(yùn)算算法思想與設(shè)計(jì)如下：1. 初始化線性表思想：將線性表初始化過(guò)程寫(xiě)成函數(shù)，其中傳入函數(shù)的參數(shù)是主函數(shù)中定義的結(jié)構(gòu)型變量L的引用，在函數(shù)中，首先使用malloc函數(shù)分配LISTSIZE大小的連續(xù)內(nèi)存空間，由于線性表的長(zhǎng)度為0，即完成了線性表的初始化。經(jīng)分析，算法的時(shí)間復(fù)雜度為O(1)。2. 銷毀線性表思想：將銷毀線性表的過(guò)程寫(xiě)成函數(shù)，其中傳入函數(shù)是主函數(shù)中定義的結(jié)構(gòu)性變量L。在函數(shù)中，,。經(jīng)分析，該算法的時(shí)間復(fù)雜度為O(1)。3. 清空線性表的思想：將清空表的過(guò)程寫(xiě)成函數(shù)，其中將主函數(shù)中定義的結(jié)構(gòu)性變量L的引用作為函數(shù)參數(shù)，在函數(shù)中，由于清空操作并不釋放內(nèi)存空間，故只需將線性表的長(zhǎng)度置為0即可。經(jīng)分許，該算法的時(shí)間復(fù)雜度為O(1)。4. 求線性表表長(zhǎng)的思想：將求表長(zhǎng)過(guò)程寫(xiě)成函數(shù)，其中主函數(shù)中定義的結(jié)構(gòu)性變量L的引用作為函數(shù)的參數(shù)，在函數(shù)中。經(jīng)分析，該算法的時(shí)間復(fù)雜度為O（1）。5. 獲得元素的算法思想：將獲得線性表元素寫(xiě)成函數(shù)，其中函數(shù)的參數(shù)是結(jié)構(gòu)型變量L以及數(shù)據(jù)元素的序號(hào)i，由于采取的是線性存儲(chǔ)結(jié)構(gòu)，[i1]來(lái)獲取元素，當(dāng)然，在這之前需要判斷合法性。經(jīng)分析，該算法的時(shí)間復(fù)雜度為O（1）。6. 查找元素的算法思想：將查找線性表特定值的數(shù)據(jù)元素寫(xiě)成函數(shù)，其中函數(shù)的參數(shù)是主函數(shù)中定義的結(jié)構(gòu)類型變量L以及查找的數(shù)據(jù)元素的值，通過(guò)循環(huán)對(duì)線性表中的每一個(gè)元素與給定值比較看是否相等，如果相等就返回該元素的次序。經(jīng)分析，該算法的時(shí)間復(fù)雜度為O（n）。查找算法的流程圖如圖12所示。圖12 線性表查找算法流程圖7. 獲得前驅(qū)算法思想：將獲得前驅(qū)過(guò)程寫(xiě)成函數(shù)，函數(shù)的參數(shù)是結(jié)構(gòu)體類型變量以及特定數(shù)據(jù)元素的值，接受前驅(qū)的變量作為另一個(gè)參數(shù)，首先調(diào)用獲得元素的函數(shù)判斷該線性表中特定數(shù)據(jù)元素的位序，首先判斷不為1，否則的話返回FALSE，[j2]。經(jīng)分析，該算法的時(shí)間復(fù)雜度為O（n）。8. 獲得后繼算法思想：將獲得后繼寫(xiě)成函數(shù)，函數(shù)的參數(shù)是結(jié)構(gòu)體類型變量以及特定數(shù)據(jù)元素的值。首先判斷是否為最后一個(gè)元素，如果不是則直接返回其后一個(gè)元素，否則的話返回FALSE，同樣該算法需要調(diào)用獲得元素的函數(shù)來(lái)確定該特定元素在線性表中的次序。經(jīng)分析，該算法的時(shí)間復(fù)雜度為O（n）。9. 插入元素算法思想：將插入函數(shù)寫(xiě)成函數(shù)，函數(shù)的參數(shù)是結(jié)構(gòu)型變量以及插入元素的值大小以及插入位置。在函數(shù)中，首先判斷插入位置的合法性，即是否在線性表中合適的位置，其次還要判斷當(dāng)前存儲(chǔ)空間是否已滿，如果滿了的話要malloc函數(shù)重新分配空間，插入元素時(shí)從該位置起到最后一個(gè)元素從后開(kāi)始以此往后移一個(gè)單元。經(jīng)分析，該算法的時(shí)間復(fù)雜度為O（n）。該算法的程序流程圖如圖13所示。圖13 線性表中插入元素算法流程圖10. 刪除元素算法思想：將刪除線性表中元素寫(xiě)成函數(shù)，函數(shù)的參數(shù)是結(jié)構(gòu)類型變量，首先判斷位序的合法性，在之后直接將刪除元素位置后一個(gè)元素直到最后一個(gè)元素以此從前往后向前移動(dòng)一個(gè)單元。經(jīng)分析，該算法的時(shí)間復(fù)雜度為O（n）。11. 遍歷線性表算法思想：將遍歷線性表寫(xiě)成一個(gè)函數(shù)，函數(shù)的參數(shù)是結(jié)構(gòu)類型變量，直接用一個(gè)循環(huán)來(lái)對(duì)線性表中的每一個(gè)元素進(jìn)行操作。經(jīng)分析，該算法的時(shí)間復(fù)雜度為O(n)。圖內(nèi)容：字體大小參考宋體5號(hào)，居中 系統(tǒng)實(shí)現(xiàn)黑體4號(hào)加粗， 編程環(huán)境、運(yùn)行環(huán)境、項(xiàng)目工程描述 本次實(shí)驗(yàn)采用Microsoft Visual Studio 2015編程軟件編寫(xiě)，并用VS2015進(jìn)行編譯運(yùn)行，項(xiàng)目名稱是linear datastructer。 頭文件及預(yù)定義常量說(shuō)明include include include define TRUE 1define FALSE 0define OK 1define ERROR 0define INFEASTABLE 1define OVERFLOW 2define LIST_INIT_SIZE 100define LISTINCREMENT 10 typedef int status。typedef int ElemType。 系統(tǒng)演示操作。如圖14所示。圖14 系統(tǒng)演示1，進(jìn)入菜單演示界面，如圖15所示。圖15 系統(tǒng)演示2，此時(shí)會(huì)退出當(dāng)前演示界面，即退出對(duì)當(dāng)前線性表的操作，并顯示要求用戶選擇對(duì)哪一個(gè)線性表進(jìn)行操作。如圖16所示。圖16 演示系統(tǒng)3，退出演示系統(tǒng)，結(jié)束操作，如圖17所示。圖17 系統(tǒng)演示4 測(cè)試計(jì)劃測(cè)試功能及序號(hào)輸入要管理的線性表序號(hào)輸入函數(shù)的參數(shù)（具體元素）預(yù)計(jì)輸出此時(shí)線性表的狀態(tài)1無(wú)線性表初始化成功分配了連續(xù)的物理存儲(chǔ)空間，表長(zhǎng)度為0，表尺寸為空間大小1無(wú)線性表刪除成功線性表連續(xù)物理空間被釋放， 1無(wú)線性表清空成功線性表的物理空間保留，但表長(zhǎng)置為0.(多次調(diào)用)1輸入1：1，2：2，3：3，4：4，5：5線性表創(chuàng)建成功創(chuàng)建了一個(gè)線性表，序列為：1，2，3，4，51無(wú)輸出線性表非空同上1無(wú)輸出線性表的長(zhǎng)度為5同上1輸入數(shù)據(jù)元素的位序?yàn)?輸出線性表的第三個(gè)元素為3同上1輸入數(shù)據(jù)元素的值為4輸出4的前面一個(gè)元素是3同上1輸入數(shù)據(jù)元素的值為2輸出2的后面一個(gè)元素是3同上1輸入數(shù)據(jù)元素的置為3輸出元素刪除成功重新生成了一新的線性表，序列為12451輸入數(shù)據(jù)元素的值為4輸出4是線性表中的第三個(gè)數(shù)據(jù)元素同上1輸出文件保存成功同上1輸出文件加載成功同上 測(cè)試，進(jìn)入菜單演示界面，執(zhí)行功能1，初始化線性表，測(cè)試結(jié)果如圖18所示。圖18 初始化線性表的測(cè)試結(jié)果，銷毀線性表，測(cè)試結(jié)果如圖19所示。圖19 刪除線性表的操作結(jié)果，往線性表中添加數(shù)據(jù)元素1,2,3,4,5，測(cè)試結(jié)果如圖110所示。圖110 插入元素的測(cè)試結(jié)果，判斷線性表是否為空，測(cè)試結(jié)果如圖111所示。圖111 判斷線性表非空的測(cè)試結(jié)果，求線性表的長(zhǎng)度，測(cè)試結(jié)果如圖112所示。圖112 求線性表長(zhǎng)度的測(cè)試結(jié)果，查找第三個(gè)數(shù)據(jù)元素的數(shù)值，測(cè)試結(jié)果如圖113所示。圖113 查找數(shù)據(jù)元素的測(cè)試結(jié)果，確定值為4的數(shù)據(jù)元素前驅(qū)數(shù)據(jù)元素，測(cè)試結(jié)果如圖114所示。圖114 查找元素的前驅(qū)數(shù)據(jù)元素，確定值為2的數(shù)據(jù)元素的后繼數(shù)據(jù)元素，測(cè)試結(jié)果如圖115所示。115 查找元素的后繼數(shù)據(jù)元素，刪除第三個(gè)數(shù)據(jù)元素，測(cè)試結(jié)果如圖116所示。圖116 刪除線性表中的數(shù)據(jù)元素測(cè)試結(jié)果，測(cè)試結(jié)果如圖117所示。圖117 保存線性表測(cè)試結(jié)果，在執(zhí)行功能14，加載線性表，測(cè)試結(jié)果如圖118所示。圖118 線性表加載的測(cè)試結(jié)果，遍歷并輸出線性表中的元素，應(yīng)該輸出1245，測(cè)試結(jié)果如圖119所示。