【正文】 n7， n8，則問題的解為 n4， n8， n5， n2， n1， n3， n7， n6。 (c) n4 n8 n5 (d) n4 n8 n5 n2 (a) n4 (b) n4 n8 (e) n4 n8 n5 n2 n1 (f) n4 n8 n5 n2 n1 n3 (g) n4 n8 n5 n2 n1 n3 n7 (h) n4 n8 n5 n2 n1 n3 n7 n6 步驟 ： 1: 建立 順序表 2: 出列 時間復雜度分析 ：出列元素的刪除（移動實現(xiàn)） 為基本運算（每次最多 i1個元素移動，需要 n1次） (n1)+(n2)+……+1 = n(n 1)/2 = O(n2) 順序表方式實現(xiàn) 循環(huán)鏈表方式實現(xiàn) 步驟： 1：建立帶頭結點的 循環(huán)單鏈表 2：尋找第 s個結點，輸出并刪除第 m個結點。 時間復雜度分析 ：三部分時間（ 創(chuàng)建鏈表 ： O(n)+求第 s個結點 ： O(s)+ 求 n個第 m個應出列的元素 ： O(m*n)) 0 1 2 3 4 … n1 0 1 2 3 4 … n2 當前剩下 i個人 ,從 s1數第m個的位置： s1 = (s1+m1)%i 0 1 … i1 開始 pclist … info a1 an head 典型應用 ：一元多項式表達與實現(xiàn) 一元多項式 ： Pn(x)=p0+p1x+p2x2+… +pn xn 線性表表示 ： P=(p0, p1, p2, … , pn) 順序表表示 ： 只存系數 （ 第 i個元素存 xi的系數 ） 特殊問題： p(x) = 1+2x10000+4x40000 浪費空間 鏈表表示 ： 每個結點結構 相加運算 ： 相同指數對應結點的系數項相加 ， 如 “ 和 ”為 0， 刪除結點 ， 否則必定為 “ 和鏈表 ” 的一個結點 。 （ 實質上就是兩個單鏈表的合并問題 ） 系數 指數 0 1 1 0 2 10000 4 40000 ^ 0 1 1 0 2 0 3 0 ... 0 10000 2 … 0 0 0 40000 4 車輛管理 某單位最多 100輛車輛，每輛車的基本信息包括：車號、車型、購買日期、購買價格、駕駛員名稱、違章記錄等。其中，各輛車的違章次數可能差別很大（有的一次沒有，有的可能有數十次）。每次違章記錄中包括：違章時間、違章地點、違章代碼（如闖紅燈、違規(guī)停車等）、違章處理等。 現(xiàn)思考： a) 數據結構？哪種存儲結構能夠有效地表達上述車輛管理問題； b) 如何查找某輛車的違章信息？ c) 如何統(tǒng)計某一個時間段內所有車的違章記錄？ d) 如何統(tǒng)計某一個地點的所有違章記錄？ e) 如何統(tǒng)計某一違章代碼的所有違章記錄？ f) 新買車，車輛報廢問題； g) 新違章記錄加入，違章處理后的修改？ 統(tǒng)計違章記錄時，需要給出車號、違章記錄數目等 。 實現(xiàn)上述車輛管理的程序，包括車輛信息的文件導入 /導出和顯示等。 Car1 Car2 ^ Car3 …… …… Carm 違章 1 違章 2 ^ 違章 1 違章 2 違章 3 ^ 違章 1 違章 2 違章 3 ^ 順序表 單鏈表 //車輛定義 typedef struct { int id。 //車號 char type[32]。 //車型 float price。 //價格 char driver[32]。 //駕駛員 WZ *pWZ。 //違章記錄 } CAR //車輛順序表 define MAX_NUM_CARS 100 typdef struct { CAR cars[MAX_NUM_CARS]。 int m。 //車輛數目 } CarList。 //違章結點定義 typedef struct _tagWZ WZ。 struct _tagWZ { int time。 //時間 char place[64]。 //地點 int code。 //代碼 bool ok。 //是否處理 WZ *next。 //下一個 }。 一種可能的結構 本章主要討論了線性表的概念 、 存儲表示以及基本運算的實現(xiàn) ， 需要重點掌握 。 線性表是一種最簡單的數據結構 ， 它是n個元素的有限序列 。 常用存儲方式： 順序 、 鏈接存儲結構 ； 順序存儲結構 中 ， 物理位置相鄰表達邏輯關系相鄰；只存儲數據元素自身信息 ， 存儲密度大 、 空間利用率高；元素定位通過簡單公式 ， 是隨機存取結構；但數據元素的插入 、 刪除是通過大量的元素移動完成 ， 時間效率低；必須事先估計最大元素數 。 小結 鏈接存儲結構 中 ， 結點空間是動態(tài)申請和釋放的；數據元素之間的邏輯關系通過附加指針表達；插入 、 刪除只需要修改指針即可 ， 不必移動大量的數據元素；缺點是需要附加的指針 ， 存儲密度降低；元素的訪問需要從頭結點開始順鏈一個一個結點進行 ， 是非隨機存取的存儲結構 。 鏈表： 單鏈表 、 循環(huán)鏈表 、 雙向鏈表 、 靜態(tài)鏈表 （ 游標 ） 結合 Josephus問題和一元多項式表達討論了順序表和鏈表的應用 。 另外 ， 常用算法的時間復雜度分析也是需要掌握的 。 書面作業(yè) ：書 p67復習 ( 7)， 算法（ 1 16） 閉卷考試中的大部分題目將從練習題中選擇。 上機作業(yè) ： p68上機練習 1和車輛管理問題（ 2選 1）