【正文】 ( amp。在 L的第 i個(gè)元素之前 插入新的元素 e， L的長(zhǎng)度增 1。L, i, amp。刪除 L的第 i個(gè)元素，并用e返回其值， L的長(zhǎng)度減 1。 現(xiàn)要求一個(gè)新的集合 A＝ A∪ B。上述問(wèn)題可演繹為：1． 從線性表 LB中依次察看每個(gè)數(shù)據(jù)元素 。 3． 若不存在，則插入之。 // 取 Lb中第 i個(gè)數(shù)據(jù)元素賦給 e if (!LocateElem(La, e, equal( )) ) ListInsert(La, ++La_len, e)。La, List Lb) { La_len = ListLength(La)。 for (i = 1。 i++) {}} // union 已知 一個(gè) 非純集合 B， 試 構(gòu)造 一個(gè)純集合 A， 使 A中只包含 B 中所有值各不相 同的數(shù)據(jù)元素 。例 22集合 B 集合 A從集合 B 取出物件放入集合 A要求集合 A中 同樣物件不能有兩件以上因此， 算法的策略應(yīng)該和例 21相同void union(List amp。 Lb_len=ListLength(Lb)。 // 取 Lb中第 i 個(gè)數(shù)據(jù)元素賦給 e if (!LocateElem(La, e, equal( )) ) ListInsert(La, ++La_len, e)。 i = Lb_len。 // 構(gòu)造 (空的 )線性表 LA若線性表中的數(shù)據(jù)元素相互之間可以 比較 ，并且數(shù)據(jù)元素在線性表中 依值非遞減或非遞增有序 排列，即 ai≥a i1 或 ai≤a i1(i = 2,3,…, n) ，則稱該線性表為 有序表 (Ordered List)。例如 ： 如果集合 B ，（ 2， 3， 3， 5， 6， 6， 6， 8， 12）對(duì)集合 B 而言， 值相同的數(shù)據(jù)元素必定相鄰；如果構(gòu)造一個(gè)純集合 A， 對(duì)集合 A 而言， 數(shù)據(jù)元素依值從小至大的順序插入。void purge(List amp。 La_len = ListLength(La)。 // 求線性表的長(zhǎng)度 for (i = 1。 i++) { }} // purge GetElem(Lb, i, e)。 en = e。線性表的存儲(chǔ)結(jié)構(gòu)主要有如下兩類：(1)順序存儲(chǔ)結(jié)構(gòu) (2)鏈?zhǔn)?存儲(chǔ)結(jié)構(gòu) 線性表類型的實(shí)現(xiàn) —— 順序映像 用一組 地址連續(xù) 的存儲(chǔ)單元 依次存放 線性表中的數(shù)據(jù)元素 （邏輯關(guān)系相鄰 , 物理位置相鄰。設(shè)首元素 a0的存放地址為 LOC(a0)（ 稱 為首地址 ），設(shè)每個(gè)元素占用存儲(chǔ)空間（地址長(zhǎng)度）為 L字節(jié)，則表中任一數(shù)據(jù)元素的 存放地址 為： LOC ( ai+1 ) = LOC( ai ) + L LOC ( ai ) = LOC( a0 ) + L *i 對(duì)上述公式的解釋如圖所示線性表順序存儲(chǔ)特點(diǎn)：a0a1……aiai+1……an1 地址 內(nèi)容 元素在表中的位序0i1n1空閑區(qū)i+1Lb=LOC(a0)b + Lb +iLb +(n1)Lb +(MaxSize1)LLOC ( ai ) = LOC( a0 ) + L *i線性表的順序存儲(chǔ)結(jié)構(gòu)示意圖順序映像的 C 語(yǔ)言描述typedef struct { } SqList。 // 存儲(chǔ)空間基址int length。 // 當(dāng)前分配的存儲(chǔ)容量 // (以 sizeof(ElemType)為單位 )線性表的基本操作在順序表中的實(shí)現(xiàn)InitList(amp。L, i, e) // 插入元素ListDelete(amp。 L ) { // 構(gòu)造一個(gè)空的線性表 } // InitList_Sq 算法 時(shí)間復(fù)雜度 ： O(1) = (ElemType*) malloc (LIST_ INIT_SIZE?sizeof (ElemType))。 = 0。定位：判斷某個(gè)元素是否存在，存在給出其位置，否則為 023 75 41 38 54 62 17e = 38p p p p pi 1234850可見(jiàn)，基本操作是：將順序表中的元素逐個(gè)和給定值 e 相比較。 // i 的初值為第 1 元素的位序p = 。amp。if (i = ) return i。(*pare)(*p++, e)) int LocateElem_Sq(SqList L, ElemType e,) { p=。i=。 else return 0。L, i, e)的實(shí)現(xiàn)：首先分析 :插入元素時(shí)，線性表的 邏輯結(jié)構(gòu) 發(fā)生什么變化 ？ (a1, …, ai1, ai, …, a n) 改變?yōu)? (a1, …, ai1, e, ai, …, a n)a1 a2 … ai1 ai … ana1 a2 … ai1 …ai e anai1, ai ai1, e, e, ai表的長(zhǎng)度增加 Status ListInsert_Sq(SqList amp。([i1])。([])。 p) *(p+1) = *p。 // 插入 e++?！赜乙?1 18 30 75 42 56 8721 18 30 75例如： ListInsert_Sq(L, 5, 66) pppq87564266q = amp。 // q 指示插入位置for (p = amp。 p = q。 *q = 66。L, i, amp。L, int i, ElemType amp。 p = q。 // 被刪除元素之后的元素左移。 算法時(shí)間復(fù)雜度 為 : O( ListLength(L))p = amp。 // p 為被刪除元素的位置e = *p。 // 表尾元素的位置if ((i 1) || (i )) return ERROR。([i1])。for (++p。 ++p) *(p1) = *p。（ a1, a2, … ai1， ai, ai+1 ， …, a n）常見(jiàn)做法：① 從前往后掃描，見(jiàn)到 0元素則與尾部非 0元素互換；② 從后往前掃描，見(jiàn)到 0元素則后面元素統(tǒng)統(tǒng)前移；③ 從前往后掃描，見(jiàn)到 0元素先計(jì)數(shù)，再將后續(xù)的一個(gè)非 0元素前移，全部掃完后再把后續(xù)部分（長(zhǎng)度為 0元素的個(gè)數(shù)）清 0。if(Llenghth = =0) return(0)。 iLlenghth1。 else zerosum++。i=Llenghth。 //表的后部補(bǔ) 0其它一些操作實(shí)現(xiàn)167。 L) {L. length =0。 L) {return (L. length ==0)。// else return false。有關(guān)查表的操作 void TraverseList(SqList amp。 iL. length1。 coutendl。 L, int pos){ if(pos1 || pos) { cerrpos is out range!endl。 } return [pos1]。 算法時(shí)間主要耗費(fèi)在 移動(dòng)元素 的操作上，因此計(jì)算時(shí)間復(fù)雜度的基本操作（最深層語(yǔ)句頻度） T(n)= O (移動(dòng)元素次數(shù) )而移動(dòng)元素的個(gè)數(shù)取決于插入或刪除元素的位置 .思考：若插入在尾結(jié)點(diǎn)之后，則根本無(wú)需移動(dòng)（特別快）；若插入在首結(jié)點(diǎn)之前，則表中元素全部要后移（特別慢）；應(yīng)當(dāng)考慮在各種位置插入（共 n+1種可能）的平均移動(dòng)次數(shù)才合理。將所有位置的執(zhí)行時(shí)間相加，然后取平均。……若在 an1后面插入，要后移 1個(gè)元素；若在尾結(jié)點(diǎn) an之后插入，則后移 0個(gè)元素；所有可能的元素移動(dòng)次數(shù)合計(jì) ： 0+1+…+ n = n(n+1)/2故插入時(shí)的平均移動(dòng)次數(shù)為： n(n+1)/2247。解決問(wèn)題的思路 ： 改用另一種線性存儲(chǔ)方式： 線性表類型的實(shí)現(xiàn)—— 鏈?zhǔn)接诚矜湵恚?linked list）：是用動(dòng)態(tài)申請(qǐng)存儲(chǔ)空間，并通過(guò)指針來(lái)鏈接結(jié)點(diǎn)，按照線性表的前驅(qū)關(guān)系把一個(gè)個(gè)結(jié)點(diǎn)鏈接起來(lái)。存儲(chǔ)方式：用任意存儲(chǔ)空間單元來(lái)存放線性表的各個(gè)元素，為了能體現(xiàn)元素之間的邏輯關(guān)系（線性），在存放每個(gè)元素的同時(shí)，也存放相關(guān)元素的信息（相關(guān)元素的存儲(chǔ)地址），即用指針來(lái)表示元素之間