【正文】 5. 已知一個(gè)遞增有序的單鏈表，編寫(xiě)一個(gè)函數(shù)向該單鏈表中插入一個(gè)元素為 x的結(jié)點(diǎn)，使插入后該鏈表仍然遞增有序。 } if(p!=NULL) /*若查找成功 ， 把 s插入到 p之后 */ if(pnext==NULL) /*若 p是最后一個(gè)結(jié)點(diǎn)，則直接把 s結(jié)點(diǎn)鏈入 */ 例3.3算法續(xù) { pnext=s。 qnext=head1。 p=head。 ?這兩個(gè)語(yǔ)句的執(zhí)行順序可以顛倒，執(zhí)行這兩個(gè)語(yǔ)句之后，可調(diào)用 free(p),將 *p結(jié)點(diǎn)釋放。因?yàn)槲步Y(jié)點(diǎn)由尾指針 rear來(lái)指示，則頭結(jié)點(diǎn)的位置是 rearnextnext。 h e a d ?若 pnext=head，則 p就是指向最后一個(gè)結(jié)點(diǎn)； ?若 headnext=head，則為空表。 } else { qnext=pnext。 } else { snext=p。 while ((p!=null) $$ (kI)) { p=pnext。 /*p指向頭結(jié)點(diǎn) */ while (p!=NULL) { p=pnext。 return(0)。 k； k++) [k1] = [k]。 ?線(xiàn)性表的基本運(yùn)算： 1. 求線(xiàn)性表的長(zhǎng)度 n； 2. 在第 i個(gè)數(shù)據(jù)元素前面插入一個(gè)新的數(shù)據(jù)元素； 3. 刪除第 i個(gè)數(shù)據(jù)元素； 4. 存取或更新線(xiàn)性表第 i個(gè)元素； 5. 將兩個(gè)或兩個(gè)以上的線(xiàn)性表合并成一個(gè)線(xiàn)性表； 6. 將一個(gè)線(xiàn)性表拆成多個(gè)線(xiàn)性表； 7. 將線(xiàn)性表中各數(shù)據(jù)元素按某個(gè)域值（如關(guān)鍵字） 遞增或遞減的順序重新排列； 8. 在線(xiàn)性表中查找滿(mǎn)足某種條件的數(shù)據(jù)元素； 線(xiàn)性表的順序存儲(chǔ) ?線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu) (順序表） 例：一順序表 A=（ 3， 6， 8， 9， 2） 順序存放在一維數(shù)組中 順序存儲(chǔ)的特點(diǎn)： 邏輯順序與物理順序一致， 元素之間的關(guān)系由物理位置的相鄰關(guān)系體現(xiàn) 3 6 8 9 2 線(xiàn)性表的順序存儲(chǔ) ?地址計(jì)算 設(shè)順序表的每個(gè)元素占 c個(gè)存儲(chǔ)單元，并且元素所占的第一個(gè)單元的存儲(chǔ)地址作為順序表的存儲(chǔ)位置，則順序表中第 I個(gè)元素的存儲(chǔ)位置 Loc（ ai）滿(mǎn)足 Loc（ ai） =Loc（ ai1） + c Loc（ ai） =Loc（ a1） +（ i1） * c 線(xiàn)性表的順序存儲(chǔ) ?結(jié)點(diǎn)描述 define Maxlen 順序表的最大長(zhǎng)度 typedef struct seqenlist {elementtype elements [maxlen]。 ?線(xiàn)性表的元素個(gè)數(shù) n稱(chēng)為這個(gè)表的長(zhǎng)度，當(dāng)n=0時(shí)，這個(gè)表叫做空表。 if (i1 || i+1) printf(“i值錯(cuò) ！ \n”)。 ?用數(shù)量級(jí)的形式表示線(xiàn)性表插入、刪除運(yùn)算的時(shí)間復(fù)雜性均為 O(n)。 ?一個(gè)單鏈表由頭指針 head唯一標(biāo)識(shí)和確定，因此，可用頭指針來(lái)命名單鏈表。 ?空指針 NULL起標(biāo)志的作用，若無(wú)此標(biāo)志，尾結(jié)點(diǎn)鏈域的值為“無(wú)定義”，上述算法中的 while語(yǔ)句在做最后一次判斷時(shí)將出現(xiàn)“運(yùn)行錯(cuò)”，這是應(yīng)予避免的。 head的單鏈表的第 K個(gè) elementtype x。 假設(shè)指針 q指向待刪除結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)，指針 p指向要?jiǎng)h除的結(jié)點(diǎn)，刪除該結(jié)點(diǎn)的操作如下：將該結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn) *q的鏈域指向 *p的后繼結(jié)點(diǎn)（即 qnext=pnext）。 int next。 ?結(jié)點(diǎn)定義為： Typedef struct Jnode { int no。 ?雙鏈表結(jié)構(gòu)是一種對(duì)稱(chēng)結(jié)構(gòu)，設(shè)指針 p指向雙鏈表的某一結(jié)點(diǎn)，則雙鏈表的對(duì)稱(chēng)性可用下式來(lái)表示： p=(pprior)next=(pnext)prior 即結(jié)點(diǎn) *p的地址存放在其前趨結(jié)點(diǎn) *(pprior)的后繼指針域中，又存放在它的后繼結(jié)點(diǎn) *(pnext)的前趨指針域中。 4654)( 2345 ????? xxxxxAxxxxxB ???? 245 623)(結(jié)點(diǎn)的定義如下： typedef struct pnode { real coef。 q=r。 s=(dnode *)malloc(sizeof(dnode))。 pnext=s。 10. 已知一個(gè)單循環(huán)鏈表，編寫(xiě)一個(gè)函數(shù)，將所有箭頭方向取反。 5. 寫(xiě)出在單鏈表中的 p所指結(jié)點(diǎn)之前插入一個(gè) s所指結(jié)點(diǎn)的操作。 /*查找第 i個(gè)結(jié)點(diǎn) ， 由 p指向 */ j=1。 p=head1。 A,B后移。 qnext=p。 i0。 循環(huán)鏈表 ?循環(huán)鏈表（ circular linked list）是一種首尾相接的鏈表，將單鏈表表尾結(jié)點(diǎn)原來(lái)的空指針改為指向表頭結(jié)點(diǎn)，就成為循環(huán)鏈表。 while((p!=null) amp。 /*結(jié)點(diǎn) pre j++ } 插入算法續(xù) if(j!=k) { printf(“k超出鏈表的長(zhǎng)度 ” )。 3) 將新結(jié)點(diǎn)鏈入單鏈表中 。 結(jié)點(diǎn) *p是由兩個(gè)域組成的記錄，這兩個(gè)域分別用p?data域和 p?next域來(lái)標(biāo)識(shí)，它們各有自己的值，p?data的值是一個(gè)數(shù)據(jù)元素， p?next的值是一個(gè)指針。 else { for (j=I+1。 /*順序表長(zhǎng)度加 1*/ return(0)。 線(xiàn)性表元素之間是有序的，而集合元素 之間是無(wú)序的。 ? 線(xiàn)性表的定義 例：Ａ＝｛ Monday,Tuesday， Wednesday