【文章內(nèi)容簡介】 ) *(p+1) = *p。 *q = 66。 // 插入 ep線性表操作 ListDelete(amp。L, i, amp。e)的實(shí)現(xiàn) ：首先分析：刪除元素時(shí)，線性表的邏輯結(jié)構(gòu)發(fā)生什么變化？ (a1, …, ai1, ai, ai+1, …, a n) 改變?yōu)? (a1, …, ai1, ai+1, …, a n)ai+1 … anai1, ai, ai, ai+1 ai1, ai+1表的長度減少a1 a2 … ai1 ai ai+1 … ana1 a2 … ai1 Status ListDelete_Sq (SqList amp。L, int i, ElemType amp。e) {} // ListDelete_Sqfor (++p。 p = q。 ++p) *(p1) = *p。 // 被刪除元素之后的元素左移。 // 表長減 1return OK。 算法時(shí)間復(fù)雜度 為 : O( ListLength(L))p = amp。([i1])。 // p 為被刪除元素的位置e = *p。 // 被刪除元素的值賦給 eq = +。 // 表尾元素的位置if ((i 1) || (i )) return ERROR。 // 刪除位置不合法元素左移21 18 30 75 42 56 8721 18 30 75ppp q8756p = amp。([i1])。q = +。for (++p。 p = q。 ++p) *(p1) = *p。 例如： ListDelete_Sq(L, 5, e) p例： 試用 C或類 C語言編寫一高效算法，將一 順序存儲的線性表 （設(shè)元素均為整型量）中所有零元素向表尾集中，其他元素則 順序 向表頭方向集中。（ a1, a2, … ai1， ai, ai+1 ， …, a n）常見做法：① 從前往后掃描，見到 0元素則與尾部非 0元素互換；② 從后往前掃描，見到 0元素則后面元素統(tǒng)統(tǒng)前移；③ 從前往后掃描，見到 0元素先計(jì)數(shù)，再將后續(xù)的一個(gè)非 0元素前移，全部掃完后再把后續(xù)部分（長度為 0元素的個(gè)數(shù)）清 0。√√深圳華為公司來某校招聘面試題解： void SortA(SeqList *L){ int i=0, zerosum =0。if(Llenghth = =0) return(0)。 //空表則結(jié)束 else { for( i=0。 iLlenghth1。 i++){ if (Lelem[i]0) L elem[i zerosum]= L elem[i]。 else zerosum++。 } }for( i= Llenghth zerosum。i=Llenghth。 i++) Lelem[i]=0。 //表的后部補(bǔ) 0其它一些操作實(shí)現(xiàn)167。 清空操作 void ClearList(SqList amp。 L) {L. length =0。 } 刪除 L中所有元素，使之成為一個(gè)空表2. 判空操作 bool ListEmpty(SqList amp。 L) {return (L. length ==0)。}// { if （ L. length ==0）// return true。// else return false。} 若 L為空表，返回真，否則返回假167。有關(guān)查表的操作 void TraverseList(SqList amp。 L){ for(int i=0。 iL. length1。 i++) cout[i]。 coutendl。} 依次訪問 L中每一個(gè)元素一次 2. 查找指定序號的元素 ElemType GetElem(SqList amp。 L, int pos){ if(pos1 || pos) { cerrpos is out range!endl。 exit(1)。 } return [pos1]。} //注意序號與下標(biāo)的不同 順序表操作的效率分析167。 算法時(shí)間主要耗費(fèi)在 移動元素 的操作上，因此計(jì)算時(shí)間復(fù)雜度的基本操作（最深層語句頻度） T(n)= O (移動元素次數(shù) )而移動元素的個(gè)數(shù)取決于插入或刪除元素的位置 .思考：若插入在尾結(jié)點(diǎn)之后，則根本無需移動（特別快）；若插入在首結(jié)點(diǎn)之前，則表中元素全部要后移（特別慢）；應(yīng)當(dāng)考慮在各種位置插入（共 n+1種可能）的平均移動次數(shù)才合理。時(shí)間效率 分析 :推導(dǎo) ： 假定在每個(gè)元素位置上插入 x的可能性都一樣（即概率 P相同），則應(yīng)當(dāng)這樣來計(jì)算平均執(zhí)行時(shí)間：將所有位置的執(zhí)行時(shí)間相加，然后取平均。將所有位置的執(zhí)行時(shí)間相加，然后取平均。若在首結(jié)點(diǎn)前插入，需要移動的元素最多，后移 n次；若在 a1后面插入，要后移 n1個(gè)元素，后移次數(shù)為 n1。……若在 an1后面插入，要后移 1個(gè)元素；若在尾結(jié)點(diǎn) an之后插入，則后移 0個(gè)元素；所有可能的元素移動次數(shù)合計(jì) ： 0+1+…+ n = n(n+1)/2故插入時(shí)的平均移動次數(shù)為： n(n+1)/2247。 （ n+1）＝n/2≈ O(n) 共有多少種插入形式 ?—— 連頭帶尾有 n+1種!同理可證 ： 順序表刪除一元素的時(shí)間效率為 :T（ n)=(n1)/2 ≈ O(n) 插入效率：刪除效率：教材 P25有對執(zhí)行效率的推導(dǎo)： （與課本略有區(qū)別）即插入、刪除算法的平均時(shí)間復(fù)雜度為 O(n)鏈?zhǔn)酱鎯Y(jié)構(gòu)線性表 順序存儲結(jié)構(gòu)特點(diǎn) ： 邏輯關(guān)系上相鄰的兩個(gè)元素在物理存儲位置上也相鄰；優(yōu)點(diǎn)： 可以隨機(jī)存取表中任一元素，方便快捷；缺點(diǎn)： 在插入或刪除某一元素時(shí)，需要移動大量元素。解決問題的思路 ： 改用另一種線性存儲方式： 線性表類型的實(shí)現(xiàn)—— 鏈?zhǔn)接诚矜湵恚?linked list）：是用動態(tài)申請存儲空間，并通過指針來鏈接結(jié)點(diǎn)，按照線性表的前驅(qū)關(guān)系把一個(gè)個(gè)結(jié)點(diǎn)鏈接起來。鏈表所需要的存儲空間可以根據(jù)線性元素的多少而動態(tài)地改變。存儲方式：用任意存儲空間單元來存放線性表的各個(gè)元素，為了能體現(xiàn)元素之間的邏輯關(guān)系（線性），在存放每個(gè)元素的同時(shí)，也存放相關(guān)元素的信息（相關(guān)元素的存儲地址），即用指針來表示元素之間的邏輯關(guān)系。存放一個(gè)元素占用的空間為：指針域數(shù)據(jù)域數(shù)據(jù)域 nextdata或樣式：數(shù)據(jù)域 ： 存儲元素?cái)?shù)值數(shù)據(jù)指針域： 存儲直接后繼的存儲位置 用一組 地址任意 的存儲單元 存放 線性表中的數(shù)據(jù)元素。一、單鏈表以 元素 (數(shù)據(jù)元素的映象 ) + 指針 (指示后繼元素存儲位置 ) = 結(jié)點(diǎn) (表示數(shù)據(jù)元素 或 數(shù)據(jù)元素的映象 )以 “結(jié)點(diǎn)的序列 ”表示線性表 ?? 稱作 鏈表例：請畫出 26個(gè)英文字母表的鏈?zhǔn)酱鎯Y(jié)構(gòu) 。該 字母表在內(nèi)存中鏈?zhǔn)酱娣诺臉邮脚e例如下： 解：該字母表的邏輯結(jié)構(gòu)為： （ a, b, … ,y, z）鏈表存放示意圖如下 ： a1head a2 /\an……單鏈表、雙鏈表、多鏈表、循環(huán)鏈表： ? 結(jié)點(diǎn)只有一個(gè)指針域的鏈表，稱為 單鏈表或線性鏈表；? 有兩個(gè)指針域的鏈表，稱為 雙鏈表 （但未必是雙向鏈表）；? 有多個(gè)指針域的鏈表，稱為 多鏈表 ；? 首尾相接的鏈表稱為 循環(huán)鏈表 。a1head a2 an……循環(huán)鏈表 示意圖：head頭結(jié)點(diǎn) a1 a2 … ... a n ^頭指針頭指針 空指針線性表為空表時(shí)，頭結(jié)點(diǎn)的指針域?yàn)榭?頭指針 是指向鏈表中第一個(gè)結(jié)點(diǎn)（或?yàn)轭^結(jié)點(diǎn)、或?yàn)槭自Y(jié)點(diǎn)）的指針；頭結(jié)點(diǎn) 是在鏈表的首元結(jié)點(diǎn)之前附設(shè)的一個(gè)結(jié)點(diǎn)；數(shù)據(jù)域內(nèi)只放空表標(biāo)志和表長等信息，它不計(jì)入表長度。首元結(jié)點(diǎn) 是指鏈表中存儲線性表第一個(gè)數(shù)據(jù)元素 a０ 的結(jié)點(diǎn)。 答：討論 1. 在鏈表中設(shè)置 頭結(jié)點(diǎn) 有什么好處？討論 2. 如何表示 空表 ？頭結(jié)點(diǎn) 即在鏈表的首元結(jié)點(diǎn)之前附設(shè)的一個(gè)結(jié)點(diǎn)，該結(jié)點(diǎn)的 數(shù)據(jù)域可以為空，也可存放數(shù)據(jù)域可以為空，也可存放 表長度表長度 等附加信息，其作用是為了對鏈表進(jìn)行操作