資料結構實踐項目——順序表

1. 導學

2. 線性表的邏輯結構與基本運算

3. 線性表的順序存儲結構

4. 建立線性表的實作(暨參數類型的讨論)

5. 順序表基本運算的實作

6. 線性表順序存儲的應用

7. 實踐指導：用程式實踐算法

【項目1 - 順序表的基本運算】

　　作為第一個這種類型的實踐（後續每一部分均有這種實踐，這是我們學習的基礎，也是實踐成果積累的基礎），結合相關的算法，給出建議的過程：

　　（1）目的是要測試“建立線性表”的算法createlist，為檢視建表的結果，需要實作“輸出線性表”的算法displist。在研習displist中發現，要輸出線性表，還要判斷表是否為空，這樣，實作判斷線性表是否為空的算法listempty成為必要。這樣，再加上main函數，這個程式由4個函數構成。main函數用于寫測試相關的代碼。

程式的結構如下所示：

　　若在上面的指導性提示基礎上還難于下手，請到課程首頁，找到相關連結，觀摩後再做。

　　切記：（1）無從下手時，要找到參考，這是要“借力”；（2）找到參考，并未解決問題，觀摩之後，丢開參考，自行完成，這是根本的目标。用這樣的“抄之有道”，抄來的在心裡，最終的成果，來自你的心中、腦中和手中。

　　（2）在已經建立線性表的基礎上，求線性表的長度listlength、求線性表l中指定位置的某個資料元素getelem、查找元素locateelem的算法都可以實作了。就在原程式的基礎上增加：

　　增加求線性表的長度listlength的函數并測試；

　　增加求線性表l中指定位置的某個資料元素getelem的函數并測試；

　　增加查找元素locateelem的函數并測試；

　　（3）其餘的4個基本運算：插入資料元素listinsert、删除資料元素listdelete、初始化線性表initlist、銷毀線性表destroylist都可以同法完成，請自行安排實踐路線。

　　請完成後，釋出博文，展示你的實踐成果。

【項目2 - 建設“順序表”算法庫】

　　領會“0207将算法變程式”部分建議的方法，建設自己的專業基礎設施算法庫。這一周，建的是順序表的算法庫。

　　算法庫包括兩個檔案：

　　頭檔案：list.h，包含定義順序表資料結構的代碼、宏定義、要實作算法的函數的聲明；

　　源檔案：list.cpp，包含實作各種算法的函數的定義

　　請采用程式的多檔案組織形式，在項目1的基礎上，建立如上的兩個檔案，另外再建立一個源檔案，編制main函數，完成相關的測試工作。

【項目3 - 求集合并集】

　　假設有兩個集合 a 和 b 分别用兩個線性表 la 和 lb 表示，即線性表中的資料元素即為集合中的成員。設計算法，用函數unionlist(list la, list lb, list &lc )函數實作該算法，求一個新的集合c=a∪b，即将兩個集合的并集放線上性表lc中。

提示： （1）除了實作unnionlist函數外，還需要在main函數中設計代碼，調用unionlist進行測試和示範； （2）可以充分利用前面建好的算法庫，在程式頭部直接加 <code>#include&lt;list.h&gt;</code>即可（工程中最普遍的方法，建議采納）； （3）也可以将實作算法中需要的線性表的基本運算對應的函數，與自己設計的所有程式放在同一個檔案中。

【項目4 - 順序表應用】

　　定義一個采用順序結構存儲的線性表，設計算法完成下面的工作：

　　1、删除元素在[x, y]之間的所有元素，要求算法的時間複雜度為o(n)，空間複雜度為o(1)；

　　2、将所在奇數移到所有偶數的前面，要求算法的時間複雜度為o(n)，空間複雜度為o(1)。

（1）充分利用前面建立的算法庫解決建立順序表、輸出線性表的問題； （2）為保證複雜度的要求，設計算法并用專門的函數實作算法； （3）每項工作寫一個程式，并釋出博文，展示你的實踐成果。