【正文】 基本運(yùn)算 ? 線性表的基本運(yùn)算 ： 1. 查找操作 2. 插入操作 3. 刪除操作 4. 順序表 合并算法 ? 線性表順序存儲結(jié)構(gòu)的優(yōu)缺點(diǎn)分析 2022/8/26 12 查找操作 線性表的兩種基本查找運(yùn)算 1. 按序號查找 GetData(L,i)： 要求查找線性表 L中第 i個(gè)數(shù)據(jù)元素，其結(jié)果是 [i1]或 Lelem[i1]。 /*若沒找到 ， 則返回空序號 */ } 2022/8/26 14 插入操作 線性表的插入運(yùn)算是指在表的第 i (1≤i≤n+1)個(gè)位置，插入一個(gè)新元素 e，使長度為 n的線性表 (e1， … ， ei1， ei， … ， en) 變成長度為 n+1的線性表（ e1， … ,ei1， e， ei， … ， en）。k) /*為插入元素而移動位置 */ Lelem[k+1]=Lelem[k]。 if((i1)||(iLlast+1)) { printf(“刪除位置不合法 ！ ” )； return(ERROR)； } *e= Lelem[i1]。 ? 算法實(shí)現(xiàn) ? 此處連接算法演示 2022/8/26 21 順序表 合并算法實(shí)現(xiàn) void merge(SeqList *LA, SeqList *LB, SeqList *LC) { i=0。 } else { LCelem[k]=LBelem[j]。 k++。 單鏈表 ：鏈表中的每個(gè)結(jié)點(diǎn)只有一個(gè)指針域，我們將這種鏈表稱為單鏈表。 /* 設(shè)置一個(gè)標(biāo)志 ， 初值為 1， 當(dāng)輸入 “ $”時(shí) ， flag為 0， 建表結(jié)束 */ L=(Linklist)malloc(sizeof(Node))； /*為頭結(jié)點(diǎn)分配存儲空間 */ Lnext=NULL。 Node *r, *s。 sdata=c。amp。 / * 找到結(jié)點(diǎn) key， 退出循環(huán) * / return p。ki1) /*先找到第 i1個(gè)數(shù)據(jù)元素的存儲位置 ,使指針 Pre指向它 */ { pre=prenext。 p a1 … ai1 ai … an ∧ p a1 … L … an ∧ ai1 ai ai+1 r L 2022/8/26 41 單鏈表刪除算法實(shí)現(xiàn) void DelList(LinkList L,int i,ElemType *e) /*在帶頭結(jié)點(diǎn)的單鏈表 L中刪除第 i個(gè)元素 ， 并保存其值到變量 *e中 */ { Node *p,*r。 return ERROR。 j ++。 LinkList LC； /*將 LC初始置空表。pb!=NULL) {if(padata=pbdata) {rnext=pa。 free(LB)。 2022/8/26 50 循環(huán)單鏈表合并算法實(shí)現(xiàn) LinkList merge_1(LinkList LA,LinkList LB) /*此算法將兩個(gè)鏈表的首尾連接起來 */ { Node *p, *q。 return(LA)。 ppriornext=s。 ? /*首先檢查待插入的位置 i是否合法 */ ? /*若位置 i合法 ， 則讓指針 p指向它 */ *e=pdata。數(shù)組的第 0個(gè)分量可以設(shè)計(jì)成表的頭結(jié)點(diǎn)，頭結(jié)點(diǎn)的 next域指示了表中第一個(gè)結(jié)點(diǎn)的位置，為 0表示靜態(tài)單鏈表的結(jié)束。 設(shè) space為靜態(tài)單鏈表的名字 ， av為備用單鏈表的頭指針 ，其算法如下： void initial(StaticList space,int *av) { int k。 *av=space[*av].cur。采用這種存儲方法使得多項(xiàng)式的相加運(yùn)算的算法定義十分簡單，只需將下標(biāo)相同的單元的內(nèi)容相加即可。 系數(shù) coef 指數(shù) exp 指針 next 2022/8/26 68 建立一元多項(xiàng)式鏈?zhǔn)酱鎯Φ乃惴? ? 【 算法思想 】 通過鍵盤輸入一組多項(xiàng)式的系數(shù)和指數(shù)，用尾插法建立一元多項(xiàng)式的鏈表。/*鍵入多項(xiàng)式的系數(shù)和指數(shù)項(xiàng) */ while(c!=0) /*若 c=0， 則代表多項(xiàng)式的輸入結(jié)束 */ { s=(Polynode*)malloc(sizeof(Polynode))。 } rearnext=NULL。 若系數(shù)為 0則刪除 p， q節(jié)點(diǎn) */} else{ … /*將 q結(jié)點(diǎn)加入到和多項(xiàng)式中 */} } … ../*將多項(xiàng)式 polya或 polyb中剩余的結(jié)點(diǎn)加入到和多項(xiàng)式中 */ } 2022/8/26 72 順序表和鏈表的比較 ? 1．基于空間的考慮 ? 2．基于時(shí)間的考慮 ? 3．基于語言的考慮 2022/8/26 73 線性表鏈?zhǔn)酱鎯Ψ绞降谋容^ 操作名稱 鏈表名稱 找表頭結(jié)點(diǎn) 找表尾結(jié)點(diǎn) 找 P結(jié)點(diǎn)前驅(qū)結(jié)點(diǎn) 帶頭結(jié)點(diǎn)單鏈表 L Lnext 時(shí)間耗費(fèi) O(1) 一重循環(huán) 時(shí)間耗費(fèi) O(n) 順 P結(jié)點(diǎn)的 next域無法找到 P結(jié)點(diǎn)的前驅(qū) 帶頭結(jié)點(diǎn)循環(huán)單鏈表（頭指針） L Lnext 時(shí)間耗費(fèi) O(1) 一重循環(huán) 時(shí)間耗費(fèi) O(n) 順 P結(jié)點(diǎn)的 next域可以找到 P結(jié)點(diǎn)的前驅(qū) 時(shí)間耗費(fèi) O(n) 帶尾指針的循環(huán)單鏈表 R Rnext O(1) R 時(shí)間耗費(fèi) O(1) 順 P結(jié)點(diǎn)的 next域可以找到 P結(jié)點(diǎn)的前驅(qū) 時(shí)間耗費(fèi) O(n) 帶頭結(jié)點(diǎn)雙向循環(huán)鏈表 L Lnext O(1) Lprior 時(shí)間耗費(fèi) O(1) Pprior 時(shí)間耗費(fèi) O(1) 2022/8/26 74 總結(jié)與提高 ? 主要知識點(diǎn) ? 線性表的特征 ：線性表中每個(gè)數(shù)據(jù)元素有且僅有一個(gè)直接前驅(qū)和一個(gè)直接后繼，第一個(gè)結(jié)點(diǎn)無前驅(qū)，最后一個(gè)結(jié)點(diǎn)無后繼。既然要求空間復(fù)雜度為O(1)，說明只能借助 1個(gè)輔助空間。}/*交換 */ } }/*end of AdjustSqlist*/ 2022/8/26 79 ? 例 2：算法實(shí)現(xiàn)帶頭結(jié)點(diǎn)單鏈表的就地逆置問題。 /* P為原鏈表的當(dāng)前處理結(jié)點(diǎn) */ Lnext=NULL。 ? 【 問題分析 】 – ① 建鏈表 ：帶二進(jìn)制數(shù)可用帶頭結(jié)點(diǎn)的單鏈表存儲，第一個(gè)結(jié)點(diǎn)存儲二進(jìn)制數(shù)的最高位，依次存儲，最后一個(gè)結(jié)點(diǎn)存儲二進(jìn)制數(shù)的最低位。 q = qnext。 } r = rnext。 rnext = s。 r=l。（提示：此題可以利用頭插法） 2022/8/26 83 ? 例 建立一個(gè)帶頭結(jié)點(diǎn)的線性鏈表，用以存放輸入的二進(jìn)制數(shù)，鏈表中每個(gè)結(jié)點(diǎn)的 data域存放一個(gè)二進(jìn)制位。 ? 根據(jù)單鏈表的特點(diǎn)，通過頭指針 L我們可以順著每個(gè)結(jié)點(diǎn)的 next域，依次訪問到 a1,a2,a3… an1,an； 2）我們可以借鑒前面講到過的頭插入法建鏈表的方法，因?yàn)轭^插入法建鏈表又稱為逆序建表法 3）唯一不同的是，我們不需要重新申請結(jié)點(diǎn)空間，而只需要從原有單鏈表上依次 “ 摘下 ” 結(jié)點(diǎn)，之后插入到單鏈表頭結(jié)點(diǎn)和表中第一個(gè)結(jié)點(diǎn)之間即可。 Lelem[i]= Lelem[j]。 2022/8/26 77 例 1【 問題分析 】 ? 初見此題，可能會想到額外申請 1個(gè)順序表空間，之后依次從順序表 L中選擇奇數(shù)放入新表前部分，選擇偶數(shù)放在新表的后半部分。amp。c,amp。c,amp。 Polynode *next。 – 法 只存儲該一元多項(xiàng)式各項(xiàng)的系數(shù)，每個(gè)系數(shù)所對應(yīng)的指數(shù)項(xiàng)則隱含在存儲系數(shù)的順序表的下標(biāo)中。 /*標(biāo)記鏈尾 */ *av=1。 }Component, StaticList[Maxsize]。當(dāng)申請結(jié)點(diǎn)時(shí)，每個(gè)結(jié)點(diǎn)應(yīng)含有兩個(gè)域：data域和 next域。 2022/8/26 56 雙向鏈表的刪除操作 ? 算法描述： 欲刪除雙向鏈表中的第 i個(gè)結(jié)點(diǎn)，則指針的變化情況如圖所示。 if (s) { sdata=e。/*修改表 LB 的尾指針 ， 使之指向表 LA 的頭結(jié)點(diǎn) */ pnext=LBnext。 2022/8/26 48 帶頭結(jié)點(diǎn)的循環(huán)單鏈表示意圖 L a1 … … ai1 ai an L a1 … … ai1 ai an rear *(rearnext) *rear 空鏈表 帶 頭 結(jié)點(diǎn)的一般形式 帶 尾 結(jié)點(diǎn)的一般形式 2022/8/26 49 循環(huán)單鏈表合并為一個(gè)循環(huán)單鏈表 已知 ： 有兩個(gè)帶頭結(jié)點(diǎn)的循環(huán)單鏈表 LA、 LB，編寫一個(gè)算法，將兩個(gè)循環(huán)單鏈表合并為一個(gè)循環(huán)單鏈表，其頭指針為 LA。} } if(pa) /*若表 LA未完，將表 LA中后續(xù)元素鏈到新表 LC表尾 */ rnext=pa。 */ while(pa!=NULLamp。 【 算法描述 】 要求利用現(xiàn)有的表 LA和 LB中的結(jié)點(diǎn)空間來建立新表 LC,可通過更改結(jié)點(diǎn)的 next域來重建新的元素之間的線性關(guān)系，為保證新表仍然遞增有序，可以利用尾插入法建立單鏈表的方法，只是新建表中的結(jié)點(diǎn)不用malloc，而只需要從表 LA和 LB中選擇合適的點(diǎn)插入到新表 LC中即可。 j=0。 k=k+1。 prenext=s。 while(pre!=NULLamp。 / * 從表中第一個(gè)結(jié)點(diǎn)比較 * / while (p!=NULL) if (pdata!=key) p=pnext。 2022/8/26 35 按序號查找算法實(shí)現(xiàn) / * 在帶頭結(jié)點(diǎn)的單鏈表 L中查找第 i個(gè)結(jié)點(diǎn) ， 若找到 (1≤i≤n) ， 則返回該結(jié)點(diǎn)的存儲位置 。 輸入 “ $”時(shí) flag為 0， 建表結(jié)束 */