實驗二 線性表的順序存儲

1、實驗報告二實驗報告二線性表的順序存儲線性表的順序存儲班級：班級：20102512010251班姓名：姓名：方立春方立春學(xué)號：學(xué)號：2010325920103259專業(yè)：專業(yè)：信息安信息安全一、一、實驗?zāi)康模簩嶒災(zāi)康模海?）掌握順序表的基本操作的實現(xiàn)方法。掌握順序表的基本操作的實現(xiàn)方法。（2）應(yīng)用順序表的基本算法實現(xiàn)集合應(yīng)用順序表的基本算法實現(xiàn)集合A=AUBA=AUB算法。算法。（3）應(yīng)用順序表的基本算法實現(xiàn)兩有序順序表的歸并算法。應(yīng)用順

2、序表的基本算法實現(xiàn)兩有序順序表的歸并算法。二、二、實驗內(nèi)容：實驗內(nèi)容：1、線性表順序存儲結(jié)構(gòu)的基本操作算法實現(xiàn)（要求采用類模板實現(xiàn)）、線性表順序存儲結(jié)構(gòu)的基本操作算法實現(xiàn)（要求采用類模板實現(xiàn)）[實現(xiàn)提示實現(xiàn)提示]（同時可參見教材（同時可參見教材p5822p60p5822p60頁算法、頁算法、pptppt）函數(shù)、類名稱等可自定義，部分）函數(shù)、類名稱等可自定義，部分變量請加上學(xué)號后變量請加上學(xué)號后3位。位。庫函數(shù)載和常量定義：（代碼）庫函數(shù)

3、載和常量定義：（代碼）（1）順序表存儲結(jié)構(gòu)的定義）順序表存儲結(jié)構(gòu)的定義(類的聲明類的聲明)：（代碼）：（代碼）（2）初始化順序表算法實現(xiàn)（不帶參數(shù)的構(gòu)造函數(shù)））初始化順序表算法實現(xiàn)（不帶參數(shù)的構(gòu)造函數(shù)）輸入：無入：無前置條件：順序表不存在前置條件：順序表不存在功能：構(gòu)建一個順序表能：構(gòu)建一個順序表輸出：無出：無后置條件：表長為后置條件：表長為0實現(xiàn)代碼：實現(xiàn)代碼：（3）順序表的建立算法（帶參數(shù)的構(gòu)造函數(shù)））順序表的建立算法（帶參數(shù)的構(gòu)造

4、函數(shù)）輸入：順序表信息的數(shù)組形式入：順序表信息的數(shù)組形式a[]a[]順序表長度順序表長度n前置條件：順序表不存在前置條件：順序表不存在功能：將數(shù)組能：將數(shù)組a[]a[]中元素建為長度為中元素建為長度為n的順序表的順序表輸出：無出：無后置條件：構(gòu)建一個順序表后置條件：構(gòu)建一個順序表實現(xiàn)代碼：實現(xiàn)代碼：（4）在順序表的第）在順序表的第i個位置前插入元素個位置前插入元素e算法算法輸入：插入元素入：插入元素ee插入位置插入位置i前置條件：順序表

5、存在，前置條件：順序表存在，i要合法要合法功能：將元素能：將元素e插入到順序表中位置插入到順序表中位置i處輸出：無出：無后置條件：順序表插入新元素，表長加后置條件：順序表插入新元素，表長加1（9）獲得順序線性表第）獲得順序線性表第i個元素的值個元素的值輸入：查詢元素位置入：查詢元素位置i前置條件：順序表存在，前置條件：順序表存在，i要合法要合法功能：按位查找位置為能：按位查找位置為i的元素并輸出值的元素并輸出值輸出：查詢元素的值出：查詢

6、元素的值后置條件：無后置條件：無實現(xiàn)代碼：實現(xiàn)代碼：（1010）判表空算法）判表空算法輸入：無入：無前置條件：無前置條件：無功能：判表是否為空能：判表是否為空輸出：為空返回出：為空返回1，不為空返回，不為空返回0后置條件：無后置條件：無實現(xiàn)代碼：實現(xiàn)代碼：(11)(11)求直接前驅(qū)結(jié)點算法求直接前驅(qū)結(jié)點算法輸入：要查找的元素入：要查找的元素e，待存放前驅(qū)結(jié)點值，待存放前驅(qū)結(jié)點值e1e1前置條件：無前置條件：無功能：查找該元素的所在位置，

7、獲得其前驅(qū)所在位置。能：查找該元素的所在位置，獲得其前驅(qū)所在位置。輸出：返回其前驅(qū)結(jié)點的位序。出：返回其前驅(qū)結(jié)點的位序。后置條件：后置條件：e1e1值為前驅(qū)結(jié)點的值值為前驅(qū)結(jié)點的值實現(xiàn)代碼：實現(xiàn)代碼：(12)(12)求直接后繼結(jié)點算法求直接后繼結(jié)點算法輸入：要查找的元素入：要查找的元素e，待存放后繼結(jié)點值，待存放后繼結(jié)點值e1e1前置條件：無前置條件：無功能：查找該元素的所在位置，獲得其后繼所在位置。能：查找該元素的所在位置，獲得其后繼

8、所在位置。輸出：返回其后繼結(jié)點的位序。出：返回其后繼結(jié)點的位序。后置條件：后置條件：e1e1值為后繼結(jié)點的值值為后繼結(jié)點的值實現(xiàn)代碼：實現(xiàn)代碼：上機實現(xiàn)以上基本操作，寫出上機實現(xiàn)以上基本操作，寫出main()main()程序：程序：要求對每個算法都加以測試，判斷是否正確；并測試不同類型數(shù)據(jù)的操作。要求對每個算法都加以測試，判斷是否正確；并測試不同類型數(shù)據(jù)的操作。粘貼測試數(shù)據(jù)及運行結(jié)果：粘貼測試數(shù)據(jù)及運行結(jié)果：2、用以上基本操作算法，實現(xiàn)