實(shí)用數(shù)據(jù)結(jié)構(gòu)電子教案鏈表市公開(kāi)課獲獎(jiǎng)?wù)n件

1、數(shù)據(jù)結(jié)構(gòu)第三章 鏈表第1頁(yè)第1頁(yè)第三章 鏈表 知 識(shí) 點(diǎn)單鏈表結(jié)點(diǎn)形式、組織辦法和特點(diǎn) 單鏈表基本運(yùn)算和相應(yīng)算法 循環(huán)鏈表組織辦法和基本運(yùn)算算法 雙鏈表結(jié)點(diǎn)形式、組織辦法和特點(diǎn) 雙鏈表基本運(yùn)算和相應(yīng)算法 順序表與鏈表比較，各自?xún)?yōu)、缺點(diǎn) 鏈表應(yīng)用 用十字鏈表表示稀疏矩陣第三章 鏈表第2頁(yè)第2頁(yè)難 點(diǎn) 雙鏈表插入、刪除運(yùn)算算法利用鏈接結(jié)構(gòu)特點(diǎn)設(shè)計(jì)有效算法，處理與鏈表結(jié)構(gòu)相關(guān)應(yīng)用問(wèn)題 要 求 純熟掌握下列內(nèi)容: 單鏈表結(jié)構(gòu)特點(diǎn)、基本運(yùn)算并能設(shè)計(jì)簡(jiǎn)樸算法循環(huán)鏈表結(jié)構(gòu)特點(diǎn)、基本運(yùn)算并能設(shè)計(jì)簡(jiǎn)樸算法雙鏈表結(jié)構(gòu)特點(diǎn)、基本運(yùn)算并能設(shè)計(jì)簡(jiǎn)樸算法 理解下列內(nèi)容： 用十字鏈表表示稀疏矩陣 鏈接堆棧，鏈接隊(duì)列應(yīng)用以及

2、一元多項(xiàng)式加法應(yīng)用實(shí)例 第三章 鏈表第3頁(yè)第3頁(yè)第三章目錄3.1 單鏈表及其運(yùn)算3.2 循環(huán)鏈表與雙向鏈表 3.3 鏈表應(yīng)用舉例3.4 表示稀疏矩陣十字鏈表3.5 應(yīng)用舉例及分析小 結(jié)習(xí)題與練習(xí)第三章 鏈表第4頁(yè)第4頁(yè)3.1.1 單鏈表1. 結(jié)點(diǎn): 在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，結(jié)點(diǎn)不但存儲(chǔ)數(shù)據(jù)元素值，還附加一個(gè)指針（鏈），用來(lái)指向該結(jié)點(diǎn)直接后繼結(jié)點(diǎn)。其中，data部分稱(chēng)為數(shù)據(jù)域，用于存儲(chǔ)線(xiàn)性表一個(gè)元素，next部分稱(chēng)為指針域或鏈域，用于存儲(chǔ)一個(gè)指針，即存儲(chǔ)該結(jié)點(diǎn)直接后繼結(jié)點(diǎn)地址。 第三章 鏈表第5頁(yè)第5頁(yè)2. 單鏈表所有結(jié)點(diǎn)通過(guò)指針鏈接而構(gòu)成線(xiàn)性表稱(chēng)為單鏈表。線(xiàn)性表（a1，a2，an，）單鏈表可直觀(guān)地畫(huà)

3、成：head是單鏈表頭指針，指向開(kāi)始結(jié)點(diǎn)a1, an是終端結(jié)點(diǎn)，其指針域?yàn)榭?，不指向任何結(jié)點(diǎn)。一個(gè)單鏈表由頭指針head唯一標(biāo)識(shí)和擬定，因此，可用頭指針來(lái)命名單鏈表。 第三章 鏈表第6頁(yè)第6頁(yè)3. 單鏈表類(lèi)型定義 假設(shè)線(xiàn)性表中數(shù)據(jù)元素類(lèi)型為datatype，單鏈表類(lèi)型定義下列：typedef struct node * pointer;struct node datatype data; pointer next;typedef pointer linklist; 一個(gè)結(jié)點(diǎn)是由兩個(gè)域data和next構(gòu)成統(tǒng)計(jì),data是結(jié)點(diǎn)數(shù)據(jù)域，next是結(jié)點(diǎn)鏈域。第三章 鏈表第7頁(yè)第7頁(yè)4. 指針概念 假

4、設(shè)p是一個(gè)pointer類(lèi)型，應(yīng)正確區(qū)分指針型變量、指針、指針?biāo)附Y(jié)點(diǎn)和結(jié)點(diǎn)內(nèi)容這四個(gè)密切相關(guān)不同概念：p值（假如有話(huà)）是一個(gè)指針，即是一個(gè)所指結(jié)點(diǎn)地址 。該指針（若不是NULL）指向某個(gè)node型結(jié)點(diǎn)用*p來(lái)標(biāo)識(shí)。結(jié)點(diǎn) *p是由兩個(gè)域組成統(tǒng)計(jì)，這兩個(gè)域分別用pdata域和pnext域來(lái)標(biāo)識(shí)，它們各有自己值，pdata值是一個(gè)數(shù)據(jù)元素，pnext值是一個(gè)指針。 第三章 鏈表第8頁(yè)第8頁(yè)3.1.2 單鏈表基本運(yùn)算 1. 遍歷(Traversal)：依據(jù)已給表頭指針，按由前向后順序訪(fǎng)問(wèn)單鏈表各個(gè)結(jié)點(diǎn)。 在實(shí)際應(yīng)用中遍歷是對(duì)單鏈表最基本運(yùn)算，比如，當(dāng)要打印或顯示出各個(gè)結(jié)點(diǎn)數(shù)值域值、計(jì)算單鏈表長(zhǎng)度(即

5、結(jié)點(diǎn)數(shù)目)或?qū)ふ夷骋粋€(gè)結(jié)點(diǎn)時(shí)都需要遍歷單鏈表。 假設(shè)head是單鏈表頭指針，計(jì)算一個(gè)已建立好單鏈表結(jié)點(diǎn)個(gè)數(shù)算法下列： 第三章 鏈表第9頁(yè)第9頁(yè)計(jì)算結(jié)點(diǎn)個(gè)數(shù)算法int length(node *head) /*求表head長(zhǎng)度*/ int count=0; /*計(jì)數(shù)器置初值*/ node *p=head; /*p指向頭結(jié)點(diǎn)*/ while (p!=NULL) p=p-next; count+; return(count); /*返回表長(zhǎng)值*/ 第三章 鏈表第10頁(yè)第10頁(yè)算法分析此算法關(guān)鍵是while循環(huán)語(yǔ)句，開(kāi)始時(shí)p指針指向頭結(jié)點(diǎn)，每一循環(huán)都修改指針值，讓它指向下一個(gè)結(jié)點(diǎn)，同時(shí)將計(jì)數(shù)鏈表長(zhǎng)度變

6、量count加1。 這樣每循環(huán)一次就向后推移一個(gè)結(jié)點(diǎn)，直到p所指結(jié)點(diǎn)*p鏈域值為NULL為止。空指針NULL起標(biāo)志作用，若無(wú)此標(biāo)志，尾結(jié)點(diǎn)鏈域值為“無(wú)定義”，上述算法中while語(yǔ)句在做最后一次判斷時(shí)將出現(xiàn)“運(yùn)營(yíng)錯(cuò)”，這是應(yīng)予避免。 第三章 鏈表第11頁(yè)第11頁(yè)2. 插入 所謂插入是指在單鏈表中第i個(gè)結(jié)點(diǎn)(i0)之后插入一個(gè)元素為x結(jié)點(diǎn)。實(shí)現(xiàn)插入算法主要完畢三個(gè)基本操作： 1) 在單鏈表上找到插入位置，即找到第i個(gè)結(jié)點(diǎn)。 能夠用遍歷辦法，即從表頭起順次訪(fǎng)問(wèn)單鏈表結(jié)點(diǎn)，直至找到第i個(gè)結(jié)點(diǎn)。 2) 生成一個(gè)以x為值新結(jié)點(diǎn)。 可通過(guò)C庫(kù)函數(shù)malloc(size)來(lái)產(chǎn)生。 3) 將新結(jié)點(diǎn)鏈入單鏈表中

7、。 需要改變相關(guān)結(jié)點(diǎn)指針 ，下列面圖所表示。 第三章 鏈表第12頁(yè)第12頁(yè) 假設(shè)指針p指向單鏈表中第i個(gè)結(jié)點(diǎn)，指針s指向已生成新結(jié)點(diǎn)，鏈入新結(jié)點(diǎn)操作下列：將新結(jié)點(diǎn)*s鏈域指向結(jié)點(diǎn)*p后繼結(jié)點(diǎn) (即s-next=p-next)；將結(jié)點(diǎn)*p鏈域指向新結(jié)點(diǎn)(即p-next=s)。第三章 鏈表第13頁(yè)第13頁(yè)插入算法 void insert (node *head, int i, x) node *s,*p; int j; s=(node * )malloc(sizeof(node); /*生成新結(jié)點(diǎn)*/ s-data=x; if(i=0) /*假如i=0,則將s所指結(jié)點(diǎn)插入到表頭*/ s-next=

8、NULL; head=s; else p=head; j=1; /*查找第i個(gè)結(jié)點(diǎn)，由p所指向*/ 第三章 鏈表第14頁(yè)第14頁(yè)插入算法續(xù) while(p!=NULL & jnext; if(p!=NULL) /*把新結(jié)點(diǎn)插入其后*/ s-next=p-next; p-next=s; else printf(“未找到！n”); 第三章 鏈表第15頁(yè)第15頁(yè)3. 刪除當(dāng)需要從單鏈表上刪除結(jié)點(diǎn)時(shí)，就要通過(guò)刪除運(yùn)算來(lái)完畢。刪除單鏈表上一個(gè)其值為x結(jié)點(diǎn)主要操作是：1) 用遍歷辦法在單鏈表上找到該結(jié)點(diǎn)；2) 從單鏈表上刪除該結(jié)點(diǎn)。欲從單鏈表上刪除一個(gè)結(jié)點(diǎn)，需修改該結(jié)點(diǎn)前一個(gè)結(jié)點(diǎn)指針，下列面圖所表示。 第

9、三章 鏈表第16頁(yè)第16頁(yè) 假設(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)（即q-next=p-next）。 第三章 鏈表第17頁(yè)第17頁(yè)刪除算法void delete(node *head, int x) node *p, *q; if (head=NULL) printf(“鏈表下溢！n”); /*判空*/ if(head-data=x) / *如表頭結(jié)點(diǎn)值等于x*/ p=head; head=head-next; free(p); else q=head; /*從第二個(gè)結(jié)點(diǎn)開(kāi)始查找*/ p=head-next; 第

10、三章 鏈表第18頁(yè)第18頁(yè)刪除算法續(xù) while(p!=NULL & p-data!=x) q=p; p=p-next; if(p!=NULL) /*找到該結(jié)點(diǎn)，刪除*/ q-next=p-next; free(p); else printf(“未找到！n”); 返回第三章 鏈表第19頁(yè)第19頁(yè)3.2.1 循環(huán)鏈表循環(huán)鏈表（circular linked list）是一個(gè)首尾相接鏈表，將單鏈表表尾結(jié)點(diǎn)本來(lái)空指針改為指向表頭結(jié)點(diǎn)，就成為循環(huán)鏈表。循環(huán)鏈表并不多占存儲(chǔ)單元，但從循環(huán)鏈表任一個(gè)結(jié)點(diǎn)出發(fā)都能夠訪(fǎng)問(wèn)到此鏈表每一個(gè)結(jié)點(diǎn)，由于當(dāng)訪(fǎng)問(wèn)到表尾結(jié)點(diǎn)后又能返回到頭結(jié)點(diǎn)。 第三章 鏈表第20頁(yè)第20頁(yè)

11、1. 帶頭指針循環(huán)鏈表通常在循環(huán)鏈表表頭結(jié)點(diǎn)前面再加一個(gè)空結(jié)點(diǎn),也叫空表頭結(jié)點(diǎn)。表空時(shí)空表頭結(jié)點(diǎn)指針指向其本身，下列面圖所表示為空循環(huán)鏈表。 空表頭結(jié)點(diǎn)除指針以外數(shù)據(jù)域是沒(méi)有用，但為了將此結(jié)點(diǎn)與普通結(jié)點(diǎn)相區(qū)別，經(jīng)常是將其賦以一個(gè)尤其數(shù)據(jù)，以與普通結(jié)點(diǎn)相區(qū)別。 第三章 鏈表第21頁(yè)第21頁(yè)2. 帶尾指針循環(huán)鏈表另一個(gè)辦法是不設(shè)頭指針而改設(shè)尾指針，這樣無(wú)論是找頭結(jié)點(diǎn)還是尾結(jié)點(diǎn)都很以便。由于尾結(jié)點(diǎn)由尾指針rear來(lái)批示，則頭結(jié)點(diǎn)位置是rear-next-next。 第三章 鏈表第22頁(yè)第22頁(yè)3.2.2 雙鏈表 雙向鏈表中每個(gè)結(jié)點(diǎn)除了有向后指針外，還有指向其前一個(gè)結(jié)點(diǎn)指針，這么形成鏈表中有兩條不同方

12、向鏈，因此從某一結(jié)點(diǎn)均可向兩個(gè)方向訪(fǎng)問(wèn)。 雙鏈表結(jié)點(diǎn)形式為： 其中鏈域prior和next分別指向本結(jié)點(diǎn)直接前趨和直接后繼結(jié)點(diǎn)。 第三章 鏈表第23頁(yè)第23頁(yè)假如循環(huán)鏈表結(jié)點(diǎn)再采用雙向指針，就成為雙向循環(huán)鏈表。第三章 鏈表第24頁(yè)第24頁(yè)雙鏈表較單鏈表即使要多占用一些存儲(chǔ)單元，但對(duì)其插入和刪除操作以及查找結(jié)點(diǎn)前趨和后繼都非常以便。 雙鏈表結(jié)構(gòu)是一個(gè)對(duì)稱(chēng)結(jié)構(gòu)，設(shè)指針p指向雙鏈表某一結(jié)點(diǎn)，則雙鏈表對(duì)稱(chēng)性可用下式來(lái)表示： p=(p-prior)-next=(p-next)-prior 即結(jié)點(diǎn)*p地址既存儲(chǔ)在其前趨結(jié)點(diǎn) *(p-prior)后繼指針域中，又存儲(chǔ)在它后繼結(jié)點(diǎn)*(p-next)前趨指針域中

13、。 第三章 鏈表第25頁(yè)第25頁(yè)1. 雙鏈表插入設(shè)要在p所指結(jié)點(diǎn)前面插入一個(gè)新結(jié)點(diǎn)*q，則需要修改4個(gè)指針 ：q-prior=p-prior; q-next=p; (p-prior)-next=q; p-prior=q; 第三章 鏈表第26頁(yè)第26頁(yè)2. 雙鏈表刪除設(shè)p指向待刪除結(jié)點(diǎn)，則刪除該結(jié)點(diǎn)環(huán)節(jié)為：(p-prior) -next=p-next; (p-next) -prior=p-prior; 這兩個(gè)語(yǔ)句執(zhí)行順序能夠顛倒，執(zhí)行這兩個(gè)語(yǔ)句之后，可調(diào)用free(p),將*p結(jié)點(diǎn)釋放。 返回第三章 鏈表第27頁(yè)第27頁(yè)3.3.1 鏈堆棧鏈堆棧是棧鏈接存放表示，它是只允許在表頭進(jìn)行插入和刪除運(yùn)算

14、單鏈表。它與普通單鏈表沒(méi)有什么不同，只是將頭指針head改稱(chēng)為棧頂指針top。 第三章 鏈表第28頁(yè)第28頁(yè)鏈堆棧入棧算法 在棧頂指針是top鏈堆棧中插入一個(gè)值為x結(jié)點(diǎn)算法：void push (node *top, int x) node *s; s=(node *)malloc(sizeof(node); /*建立一個(gè)結(jié)點(diǎn)指針*/ s-data=x; s-next=top; top=s; 第三章 鏈表第29頁(yè)第29頁(yè)鏈堆棧出棧算法int pop(node *top) int x; node *p; if(top=NULL) printf(“棧為空!n”); else x=top-data;

15、 p=top; top=top-next; free(p); return(x); 第三章 鏈表第30頁(yè)第30頁(yè)3.3.2 鏈隊(duì)列鏈隊(duì)列需要兩個(gè)指針，其中隊(duì)首指針front指向鏈表表頭，隊(duì)尾指針rear指向鏈表表尾。 普通插入時(shí)只修改隊(duì)尾結(jié)點(diǎn)指針和隊(duì)尾指針rear，刪除時(shí)只修改隊(duì)首指針front。當(dāng)將第一個(gè)元素插入空隊(duì)列或刪除了最后一個(gè)元素而使隊(duì)列為空時(shí)，front和rear都需要修改。 第三章 鏈表第31頁(yè)第31頁(yè)鏈隊(duì)列插入算法void insert(node *front, rear, int x) node *s; s= (node *) malloc (sizeof (node); s

16、-data=x; s-next=NULL; if (rear =NULL) /*處理空隊(duì)列情況*/ front=s; rear=s; else rear-next=s; rear=s; 第三章 鏈表第32頁(yè)第32頁(yè)鏈隊(duì)列刪除算法int delete(node *front,rear) node *p; int x; if (front=NULL) printf(“空隊(duì)列!n”); else x=front-data; p=front; if ( front = rear) front=NULL; rear=NULL; else front=front-next; free(p); return

17、(x); 第三章 鏈表第33頁(yè)第33頁(yè)3.3.3 一元多項(xiàng)式算術(shù)運(yùn)算設(shè)一個(gè)一元多項(xiàng)式為1. 假如用數(shù)組來(lái)表示一元多項(xiàng)式，以各項(xiàng)指數(shù)作為下標(biāo)，將各個(gè)系數(shù)存入一維數(shù)組中。 第三章 鏈表第34頁(yè)第34頁(yè)2. 用單鏈表表示一元多項(xiàng)式將單鏈表每個(gè)結(jié)點(diǎn)相應(yīng)著一元多項(xiàng)式中一個(gè)非零項(xiàng)，它由三個(gè)域構(gòu)成，分別表示非零項(xiàng)系數(shù)、指數(shù)和指向下一個(gè)結(jié)點(diǎn)指針。設(shè)兩個(gè)一元多項(xiàng)式為: 求此兩一元多項(xiàng)式之和C(x)=A(x)+B(x)。 第三章 鏈表第35頁(yè)第35頁(yè)3. 運(yùn)算規(guī)則將二個(gè)一元多項(xiàng)式中所有指數(shù)相同項(xiàng)系數(shù)相加，相加后，若和不為零，則構(gòu)成“和一元多項(xiàng)式”中一項(xiàng)；若和為零，則“和一元多項(xiàng)式”中無(wú)此項(xiàng)；所有指數(shù)不相同項(xiàng)均抄到

18、“和一元多項(xiàng)式”中。第三章 鏈表第36頁(yè)第36頁(yè)返回第三章 鏈表第37頁(yè)第37頁(yè)3.4 表示稀疏矩陣十字鏈表在十字鏈表中，矩陣每個(gè)非零元素相應(yīng)著一個(gè)含有五個(gè)域結(jié)點(diǎn)，這五個(gè)域分別為該非零元素在稀疏矩陣中行號(hào)、列號(hào)、元素?cái)?shù)值以及兩個(gè)指針，其中一個(gè)指針指向同一列下一個(gè)非零元素結(jié)點(diǎn)，另一個(gè)指針指向同一行右邊一個(gè)非零元素結(jié)點(diǎn)。 第三章 鏈表第38頁(yè)第38頁(yè)將每行非零元素結(jié)點(diǎn)鏈接成循環(huán)鏈表，又將每列非零元素結(jié)點(diǎn)鏈接成循環(huán)鏈表，就構(gòu)成了十字形鏈接結(jié)構(gòu)。對(duì)于每行、每列循環(huán)鏈表都有一個(gè)空表頭結(jié)點(diǎn)，以利于元素插入和刪除運(yùn)算。這些空表頭結(jié)點(diǎn)行號(hào)、列號(hào)都標(biāo)成零，以便和其它結(jié)點(diǎn)相區(qū)別。整個(gè)十字鏈表有一個(gè)總空表頭結(jié)點(diǎn)，在

19、普通結(jié)點(diǎn)標(biāo)以行號(hào)、列號(hào)之處，此結(jié)點(diǎn)是標(biāo)出矩陣行數(shù)m和列數(shù)n。有一個(gè)指針HM指向這個(gè)總空表頭結(jié)點(diǎn)。 第三章 鏈表第39頁(yè)第39頁(yè)例：稀疏矩陣M及其相應(yīng)十字鏈表如圖所表示。第三章 鏈表第40頁(yè)第40頁(yè)第三章 鏈表第41頁(yè)第41頁(yè)空表頭結(jié)點(diǎn)結(jié)構(gòu)因各列、各行空表頭結(jié)點(diǎn)中行號(hào)和列號(hào)都是零，且每列空表頭結(jié)點(diǎn)只用到向下指針，每行空表頭結(jié)點(diǎn)只用到向右指針，故可將這組空表頭結(jié)點(diǎn)合用。由于數(shù)值域也沒(méi)有用，可將空表頭結(jié)點(diǎn)數(shù)值域改為一個(gè)指針域，將各個(gè)空表頭結(jié)點(diǎn)也鏈接成一個(gè)循環(huán)鏈表。 返回第三章 鏈表第42頁(yè)第42頁(yè)例3.1有一個(gè)單鏈表L(至少有一個(gè)結(jié)點(diǎn))，其頭結(jié)點(diǎn)指針為head，編寫(xiě)一個(gè)函數(shù)將L逆置，即最后一個(gè)結(jié)點(diǎn)變

20、成第1個(gè)結(jié)點(diǎn)，本來(lái)倒數(shù)第二個(gè)結(jié)點(diǎn)變成第二個(gè)結(jié)點(diǎn)如此等等。解：本題采用算法是，從頭到尾遍歷單鏈表L，并設(shè)置3個(gè)附加指針p、q、r,p指向當(dāng)前處理結(jié)點(diǎn)，q指向p下一個(gè)結(jié)點(diǎn)，r指向q下一個(gè)結(jié)點(diǎn)，q、r作用是為了預(yù)防倒置指針時(shí)，下一個(gè)結(jié)點(diǎn)丟失而設(shè)置，有了這三個(gè)指針，就能夠以便地實(shí)現(xiàn)指針倒置。最后將第一個(gè)結(jié)點(diǎn)next域置為NULL，并將頭指針指向最后一個(gè)結(jié)點(diǎn)，這樣達(dá)到了本題要求。 第三章 鏈表第43頁(yè)第43頁(yè)例3.1算法void invert(node *head) node *p,*q,*r; p=head; q=p-next; while(q!=NULL) /*沒(méi)有后繼時(shí)停止*/ r=q-next;

21、 q-next=p; p=q; q=r; head-next=NULL; head=p; 第三章 鏈表第44頁(yè)第44頁(yè)例3.2有兩個(gè)循環(huán)單鏈表，頭指針?lè)譃閔ead1和head2，編寫(xiě)函數(shù)將鏈表head2鏈接到鏈表head1之后，鏈接后鏈表仍保持是循環(huán)鏈表形式。解：先分別找到兩個(gè)鏈表表尾，將head2放入鏈表head1表尾，將兩個(gè)鏈表鏈接起來(lái)，然后將head1放入原h(huán)ead2鏈表表尾，構(gòu)成新循環(huán)鏈表。 第三章 鏈表第45頁(yè)第45頁(yè)例3.2算法link(node *head1,head2) node *p,*q; p=head1; while(p-next!=head1) p=p-next; q=

22、head2; while(q-next!=head2) q=q-next; p-next=head2; q-next=head1; 第三章 鏈表第46頁(yè)第46頁(yè)例3.3給出在雙鏈表中第i個(gè)結(jié)點(diǎn)(i0)之后插入一個(gè)元素為x結(jié)點(diǎn)函數(shù)。 解：在前面雙鏈表一節(jié)中，已經(jīng)給出了在一個(gè)結(jié)點(diǎn)之前插入一個(gè)新結(jié)點(diǎn)辦法，在一個(gè)結(jié)點(diǎn)之后插入一個(gè)新結(jié)點(diǎn)思想與前面是同樣。第三章 鏈表第47頁(yè)第47頁(yè)例3.3算法void insert(dnode *head,int i,x) dnode *s,*p; int j; s=(dnode *)malloc(sizeof(dnode); /*建立一個(gè)待插入結(jié)點(diǎn)，由s指向*/ s-

23、data=x; if(i=0) /*如i=0,將s所指結(jié)點(diǎn)插入到表頭后返回*/ s-next=head; head-prior=s; head=s; 第三章 鏈表第48頁(yè)第48頁(yè)例3.3算法續(xù) else p=head; /*查找第i個(gè)結(jié)點(diǎn)，由p指向*/ j=1; while(p!=NULL & jnext; if(p!=NULL) /*若查找成功，把s插入到p之后*/ if(p-next=NULL)/*若p是最后一個(gè)結(jié)點(diǎn)，則直接把s結(jié)點(diǎn)鏈入*/ 第三章 鏈表第49頁(yè)第49頁(yè)例3.3算法續(xù) p-next=s; s-next=NULL; s-prior=p; else s-next=p-next; p-next-prior=s; p-next=s; s-prior=p; else printf(“未找到!n”); 返回第三章 鏈表第50頁(yè)第50頁(yè)小結(jié)單鏈表 循環(huán)鏈表雙向鏈表 雙向循環(huán)鏈表 十字鏈表 返回第三章 鏈表第51頁(yè)第51頁(yè)習(xí)題與練習(xí)一