【正文】 se /*找到位序為 i1的結(jié)點 *p*/ { q=pnext。 /*q指向要刪除的結(jié)點 */ if (q==NULL) return 0。 /*若不存在第 i個結(jié)點 ,返回 0*/ pnext=qnext。 /*從單鏈表中刪除 *q結(jié)點 */ free(q)。 /*釋放 *q結(jié)點 */ return 1。 } } 例 設(shè) C={a1,b1,a2,b2,… ,an,bn}為一線性表 ,采用帶頭結(jié)點的 hc單鏈表存放 ,編寫一個算法 ,將其拆分為兩個線性表 ,使得 : A={a1,a2,… ,an},B={b1,b2,… ,bn} 解 :設(shè)拆分后的兩個線性表都用帶頭結(jié)點的單鏈表存放 。 先建立兩個頭結(jié)點 *ha和 *hb,它們用于存放拆分后的線性表 A和 B,ra和 rb分別指向這兩個單鏈表的表尾 ,用 p指針掃描單鏈表 hc,將當(dāng)前結(jié)點 *p鏈到 ha未尾 ,p沿next域下移一個結(jié)點 ,若不為空 ,則當(dāng)前結(jié)點 *p鏈到 hb未尾 ,p沿 next域下移一個結(jié)點 ,如此這樣 ,直到 p為空 。 最后將兩個尾結(jié)點的 next域置空 。 對應(yīng)算法如下 : void fun(LinkList *hc, LinkList *amp。ha, LinkList *amp。hb) { LinkList *p=hcnext,*ra,*rb。 ha=hc。 /*ha的頭結(jié)點利用 hc的頭結(jié)點 */ ra=ha。 /*ra始終指向 ha的末尾結(jié)點 */ hb=(LinkList *)malloc(sizeof(LinkList))。 /*創(chuàng)建 hb頭結(jié)點 */ rb=hb。 /*rb始終指向 hb的末尾結(jié)點 */ while (p!=NULL) { ranext=p。ra=p。 /*將 *p鏈到 ha單鏈表未尾 */ p=pnext。 if (p!=NULL) { rbnext=p。 rb=p。 /*將 *p鏈到 hb單鏈表未尾 */ p=pnext。 } } ranext=rbnext=NULL。 /*兩個尾結(jié)點的 next域置空 */ } 本算法實際上是采用尾插法建立兩個新表 。所以 ,尾插法建表算法是很多類似習(xí)題的基礎(chǔ) ！ 例 有一個帶頭結(jié)點的單鏈表 head,其ElemType類型為 char,設(shè)計一個算法使其元素遞增有序 。 解 :若原單鏈表中有一個或以上的數(shù)據(jù)結(jié)點 ,先構(gòu)造只含一個數(shù)據(jù)結(jié)點的有序表 (只含一個數(shù)據(jù)結(jié)點的單鏈表一定是有序表 )。 掃描原單鏈表余下的結(jié)點 *p(直到 p==NULL為止 ),在有序表中通過比較找插入 *p的前驅(qū)結(jié)點 *q,然后將 *p插入到*q之后 (這里實際上采用的是直接插入排序方法 )。 void Sort(LinkList *amp。head) { LinkList *p=headnext,*q,*r。 if (p!=NULL) /*head有一個或以上的數(shù)據(jù)結(jié)點 */ { r=pnext。 /*r保存 *p結(jié)點后繼結(jié)點的指針 */ pnext=NULL。 /*構(gòu)造只含一個數(shù)據(jù)結(jié)點的有序表 */ p=r。 while (p!=NULL) { r=pnext。 /*r保存 *p結(jié)點后繼結(jié)點的指針 */ q=head。 while (qnext!=NULL amp。amp。 qnextdatapdata) q=qnext。 /*在有序表中找插入 *p的前驅(qū)結(jié)點 *q*/ pnext=qnext。 /*將 *p插入到 *q之后 */ qnext=p。 p=r。 /*掃描原單鏈表余下的結(jié)點 */ } } } 雙鏈表 對于雙鏈表 ,采用類似于單鏈表的類型定義 ,其DLinkList類型的定義如下 : typedef struct DNode /*定義雙鏈表結(jié)點類型 */ { ElemType data。 struct DNode *prior。 /*指向前驅(qū)結(jié)點 */ struct DNode *next。 /*指向后繼結(jié)點 */ } DLinkList。 在雙鏈表中 ,有些操作如求長度、取元素值和查找元素等操作算法與單鏈表中相應(yīng)算法是相同的 ,這里不多討論。但在單鏈表中 ,進行結(jié)點插入和刪除時涉及到前后結(jié)點的一個指針域的變化。而在雙鏈表中 ,結(jié)點的插入和刪除操作涉及到前后結(jié)點的兩個指針域的變化。 雙鏈表中插入結(jié)點示意圖 歸納起來 ,在雙鏈表中 p所指的結(jié)點之后插入一個 *s結(jié)點。其操作語句描述為 : snext=pnext。/*將 *s插入到 *p之后 */ pnextprior=s。 sprior=p。 pnext=s。 刪除結(jié)點示意圖 在 雙 鏈 表中刪除一個結(jié)點的過程如右圖所示 : 歸納起來 ,刪除雙鏈表 L中 *p結(jié)點的后續(xù)結(jié)點。其操作語句描述為 : pnext=qnext。 qnextprior=p。 循環(huán)鏈表 循環(huán)鏈表 是另一種形式的鏈?zhǔn)酱鎯Y(jié)構(gòu)。它的特點是表中最后一個結(jié)點的指針域不再是空 ,而是指向表頭結(jié)點 ,整個鏈表形成一個環(huán)。由此 ,從表中任一結(jié)點出發(fā)均可找到鏈表中其他結(jié)點。 帶頭結(jié)點的循環(huán)單鏈表和循環(huán)雙鏈表的示意圖 例 編寫出判斷帶頭結(jié)點的雙向循環(huán)鏈表 L是否對稱相等的算法 。 解 :p從左向右掃描 L,q從右向左掃描 L,若對應(yīng)數(shù)據(jù)結(jié)點的 data域不相等 ,則退出循環(huán) ,否則繼續(xù)比較 ,直到 p與 q相等或 p的下一個結(jié)點為 *q為止 。 對應(yīng)算法如下 : int Equeal(DLinkList *L) { int same=1。 DLinkList *p=Lnext。 /*p指向第一個數(shù)據(jù)結(jié)點 */ DLinkList *q=Lprior。 /*q指向最后數(shù)據(jù)結(jié)點 */ while (same==1) if (pdata!=qdata) same=0。 else { if (p==q) break。 /*數(shù)據(jù)結(jié)點為偶數(shù)的情況 */ q=qprior。 if (p==q) break。 /*數(shù)據(jù)結(jié)點為奇數(shù)的情況 */ p=pnext。 } return same。 } 靜態(tài)鏈表 靜態(tài)鏈表借用一維數(shù)組來描述線性鏈表。數(shù)組中的一個分量表示一個結(jié)點 ,同時使用 游標(biāo) (指示器 cur即為 偽指針 )代替指針以指示結(jié)點在數(shù)組中的相對位置。數(shù)組中的第 0個分量可以看成頭結(jié)點 ,其指針域指示靜態(tài)鏈表的第一個結(jié)點。 這種存儲結(jié)構(gòu)仍然需要預(yù)先分配一個較大空間 ,但是在進行線性表的插入和刪除操作時不需要移動元素 ,僅需要修改“指針” ,因此仍然具有鏈?zhǔn)酱鎯Y(jié)構(gòu)的主要優(yōu)點。 1 0 張斌 2 1 劉麗 3 2 李英 4 3 陳華 5 4 王奇 6 5 董強 7 6 王萍 0 7 8 9 數(shù)據(jù)域 游標(biāo)域 1 0 張斌 2 1 劉麗 3 2 李英 5 3 陳華 5 4 王奇 6 5 董強 7 6 王萍 0 7 8 9 數(shù)據(jù)域 游標(biāo)域 刪除“陳華” （ a ） 1 0 張斌 2 1 劉麗 8 2 李英 5 3 4 王奇 6 5 董強 7 6 王萍 0 7 王華 3 8 9 數(shù)據(jù)域 游標(biāo)域 在“劉麗”之后插入“王華” （ b ） （ c ） 下圖給出了一個靜態(tài)鏈表的示例。圖 (a)是一個修改之前的靜態(tài)鏈表 ,圖 (b)是刪除數(shù)據(jù)元素“陳華”之后的靜態(tài)鏈表 ,圖(c)插入數(shù)據(jù)元素“王華”之后的靜態(tài)鏈表 ,圖中用陰影表示修改的游標(biāo)。 線性表的應(yīng)用 計算任意兩個表的簡單自然連接過程討論線性表的應(yīng)用。假設(shè)有兩個表 A和 B,分別是 m1行、 n1列和 m2行、 n2列 ,它們簡單自然連接結(jié)果 C=A B,其中 i表示表 A中列號 ,j表示表 B中的列號 ,C為 A和 B的笛卡兒積中滿足指定連接條件的所有記錄組 ,該連接條件為表 A的第 i列與表 B的第 j列相等。例如 : i=j ???????????111332321A???????????436153BC=A B的計算結(jié)果如下 : 3=1 ????????????????6111143332533324332153321 由于每個表的行數(shù)不確定 ,為此 ,用單鏈表作為表的存儲結(jié)構(gòu) ,每行作為一個數(shù)據(jù)結(jié)點 。 另外 ,每行中的數(shù)據(jù)個數(shù)也是不確定的 ,但由于提供隨機查找行中的數(shù)據(jù) ,所以每行的數(shù)據(jù)采用順序存儲結(jié)構(gòu) ,這里用長度為 MaxCol的數(shù)組存儲每行的數(shù)據(jù) 。 因此 ,該單鏈表中數(shù)據(jù)結(jié)點類型定義如下 : define MaxCol 10 /*最大列數(shù) */ typedef struct Node1 /*定義數(shù)據(jù)結(jié)點類型 */ { ElemType data[MaxCol]。 struct Node1 *next。 /*指向后繼數(shù)據(jù)結(jié)點 */ } DList。 另外 ,需要指定每個表的行數(shù)和列數(shù) ,為此將單鏈表的頭結(jié)點類型定義如下 : typedef struct Node2 /*定義頭結(jié)點類型 */ { int Row,Col。 /*行數(shù)和列數(shù) */ DList *next。 /*指向第一個數(shù)據(jù)結(jié)點 */ } HList。 采用尾插法建表方法創(chuàng)建單鏈表 ,用戶先輸入表的行數(shù)和列數(shù) ,然后輸入各行的數(shù)據(jù) ,為了簡便 ,假設(shè)表中數(shù)據(jù)為 int型 ,因此定義 : typedef int ElemType。 對應(yīng)的建表算法如下 : void create(HList *amp。h) { int i,j。 DList *r,*s。 h=(HList *)malloc(sizeof(HList))。hnext=NULL。 printf(表的行數(shù) ,列數(shù) :)。 scanf(%d%d,amp。hRow,amp。hCol)。 for (i=0。ihRow。i++) { printf( 第 %d行 :,i+1)。 s=(DList *)malloc(sizeof(DList))。 for (j=0。jhCol。j++) scanf(%d,amp。sdata[j])。 if (hnext==NULL) hnext=s。 else rnext=s。 r=s。 /*r始終指向最后一個數(shù)據(jù)結(jié)點 */ } rnext=NULL。 } 對應(yīng)的輸出表的算法如下 : void display(HList *h) { int j。 DList *p=hnext。