【正文】 /*插入到頭結(jié)點之后 */ r = s。 while(q!=NULL) /*查找最后一個值域為 0的結(jié)點 */ {if(qdata == 0) r = q。并在此鏈表上實現(xiàn)對二進制數(shù)加 1的運算 。如圖所示 2022/8/26 81 … a1 … an ∧ a2 ai (a)初始狀態(tài) L p為原鏈表當前處理結(jié)點 斷開 Lnext, 使逆置表初始為空表 (b)將單鏈表 L初始為空表 … a1 … an ∧ a2 ai ∧ L p q q指向原鏈表當前處理結(jié)點的下一個 p ① ai a2 a1 ∧ L … … an ∧ a3 q (c)將 p指向的結(jié)點插入到逆置表 L的表頭 ② 2022/8/26 82 例 2【 算法描述 】 void ReverseList(LinkList L) /*逆置帶頭結(jié)點的單鏈表 L */ { p=Lnext。 Lelem[j]=t。但是題目要求空間復雜度為 O(1),很顯然上述方法是不可行的。 q!=NULL） { if （ pexp qexp） { … /*將 p結(jié)點加入到和多項式中 */} else if ( pexp= =qexp） { … /*若指數(shù)相等 ， 則相應的系數(shù)相加 。e)。e)。 } Polynode , * Polylist。即 p[0]存系數(shù) p0，對應為 x0的系數(shù)， p[1]存系數(shù) p1，對應為 x1的系數(shù)， …… p[n]存系數(shù) pn，對應為 xn的系數(shù)。 /*設置備用鏈表頭指針初值 */ } 2022/8/26 62 靜態(tài)鏈表 分配結(jié)點與結(jié)點回收 ? 分配結(jié)點 int getnode(int *av)/*從備用鏈表摘下一個結(jié)點空間 ， 分配給待插入靜態(tài)鏈表中的元素 */ { int i=*av。 2022/8/26 60 靜態(tài)鏈表的插入和刪除操作示例 已知 ： 線性表 a， b， c， d， f， g， h， i）， Maxsize=11 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 1 a 2 b 3 c 4 d 9 f 6 g 8 h 8 i 0 e 5 1 a 2 b 3 c 4 d 9 f 6 g 7 h 8 i 0 e 5 1 a 2 b 3 c 4 d 5 f 6 g 7 h 8 i 0 0 1 2 3 4 5 6 7 8 9 10 (a)初始化 (b)插入 e后 (c)刪除 h后 2022/8/26 61 靜態(tài)鏈表 初始化 算法描述 ：初始化操作是指將這個靜態(tài)單鏈表初始化為一個備用靜態(tài)單鏈表 。 data域存放結(jié)點的數(shù)據(jù)信息， next域為游標指示器，指示后繼結(jié)點在結(jié)構數(shù)組中的相對位置（即數(shù)組下標）。 a b c p ② ① … … 2022/8/26 57 雙向鏈表的刪除操作算法實現(xiàn) int DlinkDel(DoubleList L,int i,ElemType *e) { DNode *p。 sprior=pprior。/*修改表 LA的尾指針 ， 使之指向表 LB 中的第一個結(jié)點 */ free(LB)。 算法思想 ：先找到兩個鏈表的尾，并分別由指針p、 q指向它們，然后將第一個鏈表的尾與第二個表的第一個結(jié)點鏈接起來，并修改第二個表的尾Q，使它的鏈域指向第一個表的頭結(jié)點。 else /*否則將表 LB中后續(xù)元素鏈到新表 LC表尾 */ rnext=pb。amp。 2022/8/26 44 2022/8/26 45 兩個有序單鏈表的合并的算法實現(xiàn) LinkList MergeLinkList(LinkList LA, LinkList LB) /*將遞增有序的單鏈表 LA和 LB合并成一個遞增有序的單鏈表 LC*/ { Node *pa,*pb。 /*用來存放單鏈表的長度 */ while(p!=NULL) { p=pnext。 } if(k!=i1) /* 即 while循環(huán)是因為 pnext=NULL而跳出的 */ { printf(“刪除結(jié)點的位置 i不合理 ！ ” )。 } 2022/8/26 40 單鏈表刪除 ? 算法描述： 欲在帶頭結(jié)點的單鏈表 L中刪除第 i個結(jié)點，則首先要通過計數(shù)方式找到第 i1個結(jié)點并使 p指向第 i1個結(jié)點，而后刪除第 i個結(jié)點并釋放結(jié)點空間。amp。 else break。 否則返回 NULL * / Node * Get(LinkList L, int i) { Node *p； p=L； j=0； / * 從頭結(jié)點開始掃描 * / while ((pnext!=NULL)amp。 if(c!=’$’) { s=(Node*)malloc(sizeof(Node))。 } } 2022/8/26 32 尾插法建表 C1 ∧ s r ∧ L c1 r s c2 ∧ L c1 ∧ r s L 2022/8/26 33 尾插法建表算法 Linklist CreateFromTail() /*將新增的字符追加到鏈表的末尾 */ { LinkList L。 int flag=1。 2022/8/26 24 ? 單鏈表 ? 單鏈表上的基本運算 ? 循環(huán)鏈表 ? 雙向鏈表 ?* 靜態(tài)鏈表 ? 順序表和鏈表的比較 鏈表 2022/8/26 25 單鏈表 結(jié)點（ Node） 為了正確地表示結(jié)點間的邏輯關系，必須在存儲線性表的每個數(shù)據(jù)元素值的同時，存儲指示其后繼結(jié)點的地址（或位置）信息，這兩部分信息組成的存儲映象叫做 結(jié)點（ Node） 。 j++。 k++。 ? 算法思想 ： 設表 LC是一個空表，為使 LC也是非遞減有序排列，可設兩個指針 i、 j分別指向表 LA和 LB中的元素，若[i][j]，則當前先將 [j]插入到表 LC中，若[i]≤ [j] ，當前先將 [i]插入到表 LC中，如此進行下去，直到其中一個表被掃描完畢，然后再將未掃描完的表中剩余的所有元素放到表 LC中。 序號 1 2 3 4 5 6 7 8 10 9 4 9 15 21 28 30 30 42 62 51 4 9 15 21 30 30 42 51 62 刪除 28后 2022/8/26 19 刪除 算法 int DelList(SeqList *L,int i,ElemType *e) /*在順序表 L中刪除第 i個數(shù)據(jù)元素 ， 并用指針參數(shù) e返回其值 */ { int k。k=i1。 /*若找到值為 e的元素 ， 則返回其序號 */ else return(1)。 假設線性表中每個元素占 k個單元，第一個元素的地址為 loc(a1)，則第 k個元素的地址為： loc(ai) =loc(a1)+(i1) k 2022/8/26 9 順序存儲結(jié)構示意圖 存儲地址 內(nèi)存空間狀態(tài) 邏輯地址 Loc(a1) a1 1 Loc(a1)+(21)k a2 2 … … … loc(a1)+(i1)k ai i … … … loc(a1)+(n1)k an n ... loc(a1)+(maxlen1)k 空閑 2022/8/26 10 順序存儲結(jié)構的 C語言定義 define maxsize=線性表可能達到的最大長度； typedef struct { ElemType elem[maxsize]； /* 線性表占用的數(shù)組空間 */ int last； /*記錄線性表中最后一個元素在數(shù)組 elem[ ] 中的位置 （ 下標值 ） ， 空表置為 1*/ } SeqList； 注意區(qū)分元素的序號和數(shù)組的下標 ， 如 a1的序號為 1， 而其對應的數(shù)組下標為 0。 2022/8/26 6 線性表的抽象數(shù)據(jù)類型定義 ? 抽象數(shù)據(jù)類型定義 ： ADT LinearList{ 數(shù)據(jù)元素 ： D={ai| ai∈ D0, i=1,2,… ， n n≥0 ， D0為某一數(shù)據(jù)對象 } 關系 ：Ｓ＝｛ ai,ai+1 | ai, ai+1∈ D0， i=1,2, … ,n1｝ 基本操作 ： （ 1） InitList（ L） 操作前提： L為未初始化線性表。2022/8/26 1 數(shù)據(jù)結(jié)構課件 西北大學計算機系 本演示文稿可能包含觀眾討論和即席反應。 操作結(jié)果：將 L初始化為空表。 2022/8/26 11 線性表順序存儲結(jié)構的