exp1--順序表實(shí)驗(yàn).ppt

1、張先宜,數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn),Data Structure Experiment,實(shí)驗(yàn)一 順序表實(shí)驗(yàn),.1 實(shí)驗(yàn)?zāi)康?熟練掌握線性表的順序存儲(chǔ)結(jié)構(gòu)。 熟練掌握順序表的有關(guān)算法設(shè)計(jì)。 根據(jù)具體問題的需要，設(shè)計(jì)出合理的表示數(shù)據(jù)的順序結(jié)構(gòu)，并設(shè)計(jì)相關(guān)算法。,1.2 實(shí)驗(yàn)要求 順序表結(jié)構(gòu)和運(yùn)算定義，算法的實(shí)現(xiàn)以庫文件方式實(shí)現(xiàn)，不得在測試主程序中直接實(shí)現(xiàn)； 實(shí)驗(yàn)程序有較好可讀性，各運(yùn)算和變量的命名直觀易懂，符合軟件工程要求； 程序有適當(dāng)?shù)淖⑨尅?1.3 實(shí)驗(yàn)任務(wù) 編寫算法實(shí)現(xiàn)下列問題的求解。 求順序表中第i個(gè)元素（函數(shù)），若不存在，報(bào)錯(cuò)。 實(shí)驗(yàn)測試數(shù)據(jù)基本要求： 第一組數(shù)據(jù)：順序表長度

2、n10，i分別為5，n，0，n+1，n+2 第二組數(shù)據(jù)：順序表長度n=0，i分別為0，2 在第i個(gè)結(jié)點(diǎn)前插入值為x的結(jié)點(diǎn)。 實(shí)驗(yàn)測試數(shù)據(jù)基本要求： 第一組數(shù)據(jù)：順序表長度n10，x=100, i分別為5,n,n+1,0,1,n+2 第二組數(shù)據(jù)：順序表長度n=0，x=100，i=5,刪除順序表中第i個(gè)元素結(jié)點(diǎn)。 實(shí)驗(yàn)測試數(shù)據(jù)基本要求： 第一組數(shù)據(jù)：順序表長度n10，i分別為5,n,1,n+1,0 第二組數(shù)據(jù)：順序表長度n=0， i=5 在一個(gè)遞增有序的順序表L中插入一個(gè)值為x的元素，并保持其遞增有序特性。 實(shí)驗(yàn)測試數(shù)據(jù)基本要求： 順序表元素為 （10,20,30,40,50,60,70,80,9

3、0,100）, x分別為25，85，110和8,將順序表中的奇數(shù)項(xiàng)和偶數(shù)項(xiàng)結(jié)點(diǎn)分解開（元素值為奇數(shù)、偶數(shù)），分別放入新的順序表中，然后原表和新表元素同時(shí)輸出到屏幕上，以便對照求解結(jié)果。 實(shí)驗(yàn)測試數(shù)據(jù)基本要求： 第一組數(shù)據(jù)：順序表元素為 （1,2,3,4,5,6,7,8,9,10,20,30,40,50,60） 第二組數(shù)據(jù)：順序表元素為 （10,20,30,40,50,60,70,80,90,100）,求兩個(gè)遞增有序順序表L1和L2中的公共元素，放入新的順序表L3中。 實(shí)驗(yàn)測試數(shù)據(jù)基本要求： 第一組 第一個(gè)順序表元素為 （1，3，6，10，15，16，17，18，19，20） 第二個(gè)順序表元素為

4、 （1，2，3，4，5，6，7，8，9，10，18，20，30） 第二組 第一個(gè)順序表元素為 （1，3，6，10，15，16，17，18，19，20） 第二個(gè)順序表元素為 （2，4，5，7，8，9，12，22） 第三組 第一個(gè)順序表元素為 （） 第二個(gè)順序表元素為 （1，2，3，4，5，6，7，8，9，10）,刪除遞增有序順序表中的重復(fù)元素，并統(tǒng)計(jì)移動(dòng)元素次數(shù)，要求時(shí)間性能最好。 實(shí)驗(yàn)測試數(shù)據(jù)基本要求： 第一組數(shù)據(jù)：順序表元素為 （1,2,3,4,5,6,7,8,9） 第二組數(shù)據(jù)：順序表元素為 （1,1,2,2,2,3,4,5,5,5,6,6,7,7,8,8,9） 第三組數(shù)據(jù)：順序表元素為 （

5、1,2,3,4,5,5,6,7,8,8,9,9,9,9,9）,1.4* 順序表擴(kuò)展實(shí)驗(yàn) 非必做內(nèi)容，有興趣的同學(xué)選做， 遞增有序順序表L1、L2，對2表進(jìn)行合并，并使得合并后成為一個(gè)集合，集合的元素放回L1表中保存，要求時(shí)間性能最好。 （遞增有序）順序表表示集合A、B，實(shí)現(xiàn)： C=AB，C=AB，C=A-B A=AB，A=AB，A=A-B （遞增有序）順序表表示集合A、B，判定A是否B的子集。,(2011)（15 分）一個(gè)長度為L（L1）的升序序列S，處在第 個(gè)位置的數(shù)稱為S 的中位數(shù)。例如，若序列S1=(11, 13, 15, 17, 19)，則S1 的中位數(shù)是15。兩個(gè)序列的中位數(shù)是含它們所有元素的升序序列的中位數(shù)。例如，若S2=(2, 4, 6, 8, 20)，則S1 和S2 的中位數(shù)是11。 現(xiàn)有兩個(gè)等長升序序列A 和B，試設(shè)計(jì)一個(gè)在時(shí)間和空間兩方面都盡可能高效的算法，找出兩個(gè)序列A 和B 的中位數(shù)。要求： （1）給出算法