簡介:數(shù)據(jù)結(jié)構(gòu),李云清楊慶紅揭安全,高等學(xué)校精品課程,人民郵電出版社,(第2版),數(shù)據(jù)結(jié)構(gòu),揭安全,江西省高等學(xué)校精品課程,E_MAILJIEANQUAN163COM,江西師范大學(xué)計(jì)算機(jī)信息工程學(xué)院,第3章線性表的鏈?zhǔn)酱鎯?chǔ),鏈?zhǔn)酱鎯?chǔ),單鏈表,帶頭結(jié)點(diǎn)的單鏈表,循環(huán)單鏈表,,,,雙鏈表,鏈?zhǔn)綏?鏈?zhǔn)疥?duì)列,線性表的存儲(chǔ)方式除了常用的順序存儲(chǔ)外,采用鏈?zhǔn)椒绞酱鎯?chǔ)也是一種常見的方式。本章將介紹一般線性表的幾種鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)方式,如單鏈表、帶頭結(jié)點(diǎn)單鏈表、循環(huán)單鏈表、雙鏈表以及特殊的線性表?xiàng):完?duì)列的鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)。,31鏈?zhǔn)酱鎯?chǔ),數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)方式必須體現(xiàn)它的邏輯關(guān)系。在鏈?zhǔn)酱鎯?chǔ)方式下,實(shí)現(xiàn)中除存放一個(gè)結(jié)點(diǎn)的信息外,還需附設(shè)指針,用指針體現(xiàn)結(jié)點(diǎn)之間的邏輯關(guān)系。如果一個(gè)結(jié)點(diǎn)有多個(gè)后繼或多個(gè)前驅(qū),那么可以附設(shè)相應(yīng)個(gè)數(shù)的指針,一個(gè)結(jié)點(diǎn)附設(shè)的指針指向的是這個(gè)結(jié)點(diǎn)的某個(gè)前驅(qū)或后繼。,線性結(jié)構(gòu)中,每個(gè)結(jié)點(diǎn)最多只有一個(gè)前驅(qū)和一個(gè)后繼,這里暫且設(shè)定更關(guān)心它的后繼,這樣在存儲(chǔ)時(shí)除了存放該結(jié)點(diǎn)的信息外,只要附設(shè)一個(gè)指針即可,該指針指向它的后繼結(jié)點(diǎn)的存放位置。每個(gè)結(jié)點(diǎn)的存儲(chǔ)形式是,例,數(shù)據(jù)的邏輯結(jié)構(gòu)B(K,R)其中K{K1,K2,K3,K4,K5}R{R}R{,,,}是一個(gè)線性結(jié)構(gòu),它的鏈?zhǔn)酱鎯?chǔ)如圖所示,為了清晰,上圖可以更簡潔地用下圖表示。,32單鏈表,單鏈表是線性表鏈?zhǔn)酱鎯?chǔ)的一種形式,其中的結(jié)點(diǎn)一般含有兩個(gè)域,一個(gè)是存放數(shù)據(jù)信息的INFO域,另一個(gè)是指向該結(jié)點(diǎn)的后繼結(jié)點(diǎn)的存放地址的指針域NEXT。一個(gè)單鏈表必須有一個(gè)首指針指向單鏈表中的第一個(gè)結(jié)點(diǎn)。,,◎,,◎,,◎,數(shù)據(jù)域,指針域,,節(jié)點(diǎn),直觀化的描述方法,單鏈表是由表頭唯一確定,因此單鏈表可以用頭指針的名字來命名。例如若頭指針名是HEAD,則把鏈表稱為表HEAD。,,HEAD,,A非空表,HEADNULL,B非空表,322單鏈表的實(shí)現(xiàn),單鏈表結(jié)構(gòu)的C語言描述如下/?????????????????????????????????????????//?鏈表實(shí)現(xiàn)的頭文件,文件名SLNKLISTH?//?????????????????????????????????????????/TYPEDEFINTDATATYPETYPEDEFSTRUCTLINK_NODE{DATATYPEINFOSTRUCTLINK_NODE?NEXT}NODE,單鏈表幾個(gè)基本操作的具體實(shí)現(xiàn),建立一個(gè)空的單鏈表/???????????????????????????????????????????????????//?函數(shù)功能建立一個(gè)空的單鏈表?//?函數(shù)參數(shù)無?//?函數(shù)返回值指向NODE類型變量的指針?//?文件名SLNKLISTC,函數(shù)名INIT?//???????????????????????????????????????????????????/NODE?INIT/?建立一個(gè)空的單鏈表?/{RETURNNULL}算法31建立一個(gè)空的單鏈表,輸出單鏈表中各個(gè)結(jié)點(diǎn)的值VOIDDISPLAYNODE?HEAD{NODE?PPHEADIFPPRINTF“\N單鏈表是空的“ELSE{PRINTF“\N單鏈表各個(gè)結(jié)點(diǎn)的值為\N“WHILEP{PRINTF““,PINFOPPNEXT}}}算法32輸出單鏈表中各個(gè)結(jié)點(diǎn)的值,在單鏈表中查找一個(gè)值為X的結(jié)點(diǎn)NODE?FINDNODE?HEAD,INTI{INTJ1NODE?PHEADIFINEXTJ}RETURNP}算法33在單鏈表中查找一個(gè)值為X的結(jié)點(diǎn),單鏈表的插入過程見下圖所示,,2HEADP,1,1PNEXTHEAD,A在單鏈表的最前面插入一個(gè)值為X的新結(jié)點(diǎn),單鏈表的插入過程見下圖所示,,∧,,,,,,HEAD,2,,2HEADP,A在單鏈表的最前面插入一個(gè)值為X的新結(jié)點(diǎn),1,1PNEXTHEAD,單鏈表的插入過程見下圖所示,,B在Q所指的結(jié)點(diǎn)后插入一個(gè)P所指的值為X的新結(jié)點(diǎn),1PNEXTQNEXT,1,單鏈表的插入過程見下圖所示,HEAD,,,,,,B在Q所指的結(jié)點(diǎn)后插入一個(gè)P所指的值為X的新結(jié)點(diǎn),1PNEXTQNEXT,P,Q,2QNEXTP,1,2,/?????????????????????????????????????????????????????//?函數(shù)功能單鏈表第I個(gè)結(jié)點(diǎn)后插入值為X的新結(jié)點(diǎn)?//?函數(shù)參數(shù)指向NODE類型變量的指針HEAD?//?DATATYPE類型變量X,INT型變量I?//?函數(shù)返回值指向NODE類型變量的指針?//?文件名SLNKLISTC,函數(shù)名INSERT?//?????????????????????????????????????????????????????/NODE?INSERTNODE?HEAD,DATATYPEX,INTI{NODE?P,?QQFINDHEAD,I/?查找第I個(gè)結(jié)點(diǎn)?/IFQELSE{PNODE?MALLOCSIZEOFNODE/?分配空間?/PINFOX/?設(shè)置新結(jié)點(diǎn)?/,IFI0{/插入的結(jié)點(diǎn)作為單鏈表的第一個(gè)結(jié)點(diǎn)/PNEXTHEAD/?插入1?/HEADP/?插入2?/}ELSE{PNEXTQNEXT/?插入1?/QNEXTP/?插入2?/}}RETURNHEAD}算法34在單鏈表中第I個(gè)結(jié)點(diǎn)后插入一個(gè)值為X的新結(jié)點(diǎn),刪除操作見下圖所示,∧,,,,,,,HEAD,1HEADHEADNEXT,A刪除單鏈表的最前面的(第一個(gè))結(jié)點(diǎn),2FREEP,,刪除操作見下圖所示,∧,,,,,HEAD,1HEADHEADNEXT,A刪除單鏈表的最前面的(第一個(gè))結(jié)點(diǎn),2FREEP,B刪除P指向的結(jié)點(diǎn),PRE為P的前驅(qū)結(jié)點(diǎn),1PRENEXTPNEXT,HEAD,,,,B刪除P指向的結(jié)點(diǎn),PRE為P的前驅(qū)結(jié)點(diǎn),1PRENEXTPNEXT,HEAD,,,1,B刪除P指向的結(jié)點(diǎn),PRE為P的前驅(qū)結(jié)點(diǎn),1PRENEXTPNEXT,HEAD,,PRE,,1,2FREEP,/???????????????????????????????????????????????????//?函數(shù)功能在單鏈表中刪除一個(gè)值為X的結(jié)點(diǎn)?//?函數(shù)參數(shù)指向NODE類型變量的指針HEAD?//?DATATYPE類型變量X?//?函數(shù)返回值指向NODE類型變量的指針?//?文件名SLNKLISTC,函數(shù)名DELE?//???????????????????????????????????????????????????/NODE?DELENODE?HEAD,DATATYPEX{NODE?PRENULL,?PIFHEAD{PRINTF“單鏈表是空的“RETURNHEAD}PHEADWHILEPPPNEXT}/?PRE指向P的前驅(qū)結(jié)點(diǎn)?/IFPRE/?刪除1?/,ELSEPRENEXTPNEXTFREEPRETURNHEAD}算法35在單鏈表中刪除一個(gè)值為X的結(jié)點(diǎn),鏈?zhǔn)酱鎯?chǔ)的插入和刪除操作比順序存儲(chǔ)方便,但不能隨機(jī)訪問某個(gè)結(jié)點(diǎn),33帶頭結(jié)點(diǎn)單鏈表,331帶頭結(jié)點(diǎn)單鏈表,帶頭結(jié)點(diǎn)單鏈表見下圖所示,332帶頭結(jié)點(diǎn)單鏈表的實(shí)現(xiàn),一般的單鏈表中,第一個(gè)結(jié)點(diǎn)由HEAD指示,而在帶頭結(jié)點(diǎn)單鏈表中,HEAD指示的是所謂的頭結(jié)點(diǎn),它不是存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)中的實(shí)際結(jié)點(diǎn),第一個(gè)實(shí)際的結(jié)點(diǎn)是HEADNEXT指示的。在帶頭結(jié)點(diǎn)單鏈表的操作實(shí)現(xiàn)時(shí)要注意這一點(diǎn)。,NODE?INIT{NODE?HEADHEADNODE?MALLOCSIZEOFNODEHEADNEXTNULLRETURNHEAD}算法36建立一個(gè)空的帶頭結(jié)點(diǎn)的單鏈表,VOIDDISPLAYNODE?HEAD{NODE?PPHEADNEXT/?從第一個(gè)(實(shí)際)結(jié)點(diǎn)開始?/IFPPRINTF“\N帶頭結(jié)點(diǎn)的單鏈表是空的“ELSE{PRINTF“\N帶頭結(jié)點(diǎn)的單鏈表各個(gè)結(jié)點(diǎn)的值為\N“WHILEP{PRINTF““,PINFOPPNEXT}}}算法37輸出帶頭結(jié)點(diǎn)的單鏈表中各個(gè)結(jié)點(diǎn)的值,/?????????????????????????????????????????????????????//?函數(shù)功能在帶頭結(jié)點(diǎn)的單鏈表中查找第I個(gè)結(jié)點(diǎn)地址?//?函數(shù)參數(shù)指向NODE類型變量的指針HEAD?//?INT類型變量I?//?函數(shù)返回值指向NODE類型變量的指針HEAD?//?文件名HLNKLISTC,函數(shù)名FIND?//?????????????????????????????????????????????????????/NODE?FINDNODE?HEAD,INTI{INTJ0NODE?PHEADIFINEXTJ/?繼續(xù)向后(左)查找,計(jì)數(shù)器加1?/}RETURNP/?返回結(jié)果,I0時(shí),P指示的是頭結(jié)點(diǎn)?/}算法38在帶頭結(jié)點(diǎn)的單鏈表中查找第I個(gè)結(jié)點(diǎn),帶頭結(jié)點(diǎn)單鏈表的插入過程見圖37,帶頭結(jié)點(diǎn)的單鏈表的插入操作的具體實(shí)現(xiàn)見算法39。/????????????????????????????????????????????????????//?函數(shù)功能在帶頭結(jié)點(diǎn)的單鏈表中第I個(gè)結(jié)點(diǎn)后插入一個(gè)值為X的新結(jié)點(diǎn)?//?函數(shù)參數(shù)指向NODE類型變量的指針HEAD?//?DATATYPE類型變量X,INT型變量I?//?函數(shù)返回值指向NODE類型變量的指針HEAD?//?文件名HLNKLISTC,函數(shù)名INSERT?//????????????????????????????????????????????????????/NODE?INSERTNODE?HEAD,DATATYPEX,INTI{NODE?P,?QQFINDHEAD,I/?查找?guī)ь^結(jié)點(diǎn)的單鏈表中的第I個(gè)結(jié)點(diǎn)?//?I0,表示新結(jié)點(diǎn)插入在頭結(jié)點(diǎn)之后,此時(shí)Q指向的是頭結(jié)點(diǎn)?/,IFQ/?沒有找到?/{PRINTF“\N帶頭結(jié)點(diǎn)的單鏈表中不存在第D個(gè)結(jié)點(diǎn)不能插入D“,I,XRETURNHEAD}PNODE?MALLOCSIZEOFNODE/?為準(zhǔn)備插入的新結(jié)點(diǎn)分配空間?/PINFOX/?為新結(jié)點(diǎn)設(shè)置值X?/PNEXTQNEXT/?插入1?/QNEXTP/?插入2,當(dāng)I0時(shí),由于Q指向的是頭結(jié)點(diǎn),本語句等價(jià)于HEADNEXTP?/RETURNHEAD}算法39在帶頭結(jié)點(diǎn)的單鏈表中第I個(gè)結(jié)點(diǎn)后插入一個(gè)值為X的新結(jié)點(diǎn),帶頭結(jié)點(diǎn)單鏈表的刪除過程見圖38。,,,,∧,,,,,,,HEAD,Q,,1HEADNEXTQNEXT,A刪除帶頭結(jié)點(diǎn)單鏈表的最前面的(第一個(gè))實(shí)際結(jié)點(diǎn),11,,NODE?DELENODE?HEAD,DATATYPEX{NODE?PREHEAD,?Q/?首先PRE指向頭結(jié)點(diǎn)?/QHEADNEXT/?Q從帶頭結(jié)點(diǎn)的第一個(gè)實(shí)際結(jié)點(diǎn)開始找值為X的結(jié)點(diǎn)?/WHILEQQQNEXT}/?繼續(xù)查找,PRE指向Q的前驅(qū)?/IFQ{PRENEXTQNEXT/?刪除?/FREEQ}/?釋放空間?/RETURNHEAD}算法310在帶頭結(jié)點(diǎn)的單鏈表中刪除一個(gè)值為X的結(jié)點(diǎn),算法設(shè)計(jì)題1、用單鏈表作為存儲(chǔ)結(jié)構(gòu),實(shí)現(xiàn)線性表(A0,A1,,AN1)就地逆置的操作,所謂就地指輔助空間應(yīng)為O1。2、設(shè)單鏈表L是一個(gè)遞減有序表,試寫一算法將X插入其中后仍保持L的有序性。3、寫一算法將單鏈表中值重復(fù)的結(jié)點(diǎn)刪除,使所得的結(jié)果表中各結(jié)點(diǎn)值均不相同。4、設(shè)計(jì)一個(gè)算法,對單鏈表按結(jié)點(diǎn)值從小到大對結(jié)點(diǎn)進(jìn)行排序。,算法設(shè)計(jì)題5、設(shè)計(jì)一個(gè)算法,將兩個(gè)有序單鏈表合并成一個(gè)有序的單鏈表。6、設(shè)計(jì)一個(gè)算法,求兩個(gè)單鏈表表示的集合的交集,并將結(jié)果用一個(gè)新的單鏈表保存并返回。,10,,,,P,鏈表插入排序演示,50,,,10,,,,,,HEAD,,,S,,50,,10,,,,,,HEAD,,,S,,QHEADNEXT,WHILEQQQNEXT,循環(huán)結(jié)束時(shí),將S結(jié)點(diǎn)加在PRE與Q所指示的結(jié)點(diǎn)之間,50,,10,,,,,,HEAD,,,S,,QHEADNEXT,WHILEQQQNEXT,SNEXTQPRENEXTS,50,,10,,,,,,HEAD,,QHEADNEXT,WHILEQQQNEXT,SNEXTQPRENEXTS,,50,,40,,,10,,,,,,HEAD,,QHEADNEXT,WHILEQQQNEXT,SNEXTQPRENEXTS,,,,,算法設(shè)計(jì)題多相式相加問題AX73X9X85X17BX8X22X79X8,34循環(huán)單鏈表,341循環(huán)單鏈表,循環(huán)單鏈表類型的描述(略),342循環(huán)單鏈表的實(shí)現(xiàn),單鏈表中某個(gè)結(jié)點(diǎn)P是表中最后一個(gè)結(jié)點(diǎn)的特征是PNEXTNULL。對于一個(gè)循環(huán)單鏈表,若首指針為HEAD,表中的某個(gè)結(jié)點(diǎn)P是最后一個(gè)結(jié)點(diǎn)的特征應(yīng)該是PNEXTHEAD。循環(huán)單鏈表的頭文件和單鏈表的相同。,建立一個(gè)空的循環(huán)單鏈表/??????????????????????????????????????????????????//?函數(shù)功能建立一個(gè)空的循環(huán)單鏈表?//?函數(shù)參數(shù)無?//?函數(shù)返回值指向NODE類型變量的指針?//?文件名CLNKLISTC,函數(shù)名INIT?//??????????????????????????????????????????????????/NODE?INIT/?建立一個(gè)空的循環(huán)單鏈表?/{RETURNNULL}算法311建立一個(gè)空的循環(huán)單鏈表,/??????????????????????????????????????????????????????//?函數(shù)功能獲得循環(huán)單鏈表的最后一個(gè)結(jié)點(diǎn)的存儲(chǔ)地址?//?函數(shù)參數(shù)指向NODE類型變量的指針變量HEAD?//?函數(shù)返回值指向NODE類型變量的指針?//?文件名CLNKLISTC,函數(shù)名REAR?//??????????????????????????????????????????????????????/NODE?REARNODE?HEAD{NODE?PIFHEAD/?循環(huán)單鏈表為空?/PNULLELSE{PHEAD/?從第一個(gè)結(jié)點(diǎn)開始?/WHILEPNEXTHEAD/?沒有到達(dá)最后一個(gè)結(jié)點(diǎn)?/PPNEXT/?繼續(xù)向后?/,}RETURNP}算法312獲得循環(huán)單鏈表的最后一個(gè)結(jié)點(diǎn)的存儲(chǔ)地址,/?????????????????????????????????????????????????????//?函數(shù)功能輸出循環(huán)單鏈表中各個(gè)結(jié)點(diǎn)的值?//?函數(shù)參數(shù)指向NODE類型變量的指針變量HEAD?//?函數(shù)返回值空?//?文件名CLNKLISTC,函數(shù)名DISPLAY?//?????????????????????????????????????????????????????/VOIDDISPLAYNODE?HEAD{NODE?PIFHEADPRINTF“\N循環(huán)單鏈表是空的\N“ELSE{PRINTF“\N循環(huán)單鏈表各個(gè)結(jié)點(diǎn)的值分別為\N“PRINTF““,HEADINFO/?輸出非空表中第一個(gè)結(jié)點(diǎn)的值?/,PHEADNEXT/?P指向第一個(gè)結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)?/WHILEPHEAD/?沒有回到第一個(gè)結(jié)點(diǎn)?/{PRINTF““,PINFOPPNEXT}}}算法313輸出循環(huán)單鏈表中各個(gè)結(jié)點(diǎn)的值,/?????????????????????????????????????????????????????//?函數(shù)功能循環(huán)單鏈表中查找值為X的結(jié)點(diǎn)的存儲(chǔ)地址?//?函數(shù)參數(shù)指向NODE類型變量的指針變量HEAD?//?DATATYPE類型的變量X?//?函數(shù)返回值指向NODE類型變量的指針?//?文件名CLNKLISTC,函數(shù)名FIND?//?????????????????????????????????????????????????????/NODE?FINDNODE?HEAD,DATATYPEX{/?查找一個(gè)值為X的結(jié)點(diǎn)?/NODE?QIFHEAD/?循環(huán)單鏈表是空的?/{PRINTF“\N循環(huán)單鏈表是空的無法找指定結(jié)點(diǎn)“RETURNNULL,}QHEAD/?Q指向循環(huán)單鏈表的第一個(gè)結(jié)點(diǎn),準(zhǔn)備查找?/WHILEQNEXTHEAD/?繼續(xù)查找?/IFQINFOXRETURNQELSERETURNNULL}算法314在循環(huán)單鏈表中查找一個(gè)值為X的結(jié)點(diǎn),循環(huán)單鏈表的插入過程如圖,,,,,,,,,HEAD,P,,21,2,,REAR,A在循環(huán)單鏈表的最前面插入一個(gè)值為X的新結(jié)點(diǎn),,,,,33,,1PNEXTHEAD,2HEADP,3REARNEXTP,循環(huán)單鏈表的插入過程如圖,,,,HEAD,,,21,2,QP,,,B循環(huán)單鏈表,在Q所指的結(jié)點(diǎn)后插入一個(gè)P所指的值為X的新結(jié)點(diǎn),1PNEXTQNEXT,,,,,,,2QNEXTP,/???????????????????????????????????????????????????????//?函數(shù)功能循環(huán)單鏈表第I個(gè)結(jié)點(diǎn)后插入值為X的新結(jié)點(diǎn)?//?函數(shù)參數(shù)指向NODE類型變量的指針變量HEAD?//?DATATYPE類型的變量X,INT類型的變量I?//?函數(shù)返回值指向NODE類型變量的指針?//?文件名CLNKLISTC,函數(shù)名INSERT?//???????????????????????????????????????????????????????/NODE?INSERTNODE?HEAD,DATATYPEX,INTI{/I為0時(shí)表示將值為X的結(jié)點(diǎn)插入作為循環(huán)單鏈表的第一個(gè)結(jié)點(diǎn)/NODE?P,?Q,MYREARINTJPNODE?MALLOCSIZEOFNODE/?分配空間?/PINFOX/?設(shè)置新結(jié)點(diǎn)的值?/IFINEXTPHEADPRETURNHEAD}IFI0/?找到循環(huán)單鏈表的最后一個(gè)結(jié)點(diǎn)?/PNEXTHEAD/?插入1?/HEADP/?插入2?/MYREARNEXTP/?插入3最后一個(gè)結(jié)點(diǎn)的指針域指向新插入的表中第一個(gè)結(jié)點(diǎn)?/RETURNHEAD}IFI0FREEPRETURNHEAD}IFI0/?準(zhǔn)備從表中第一個(gè)結(jié)點(diǎn)開始查找?/J1/?計(jì)數(shù)開始?/WHILEIJJ/?繼續(xù)查找,計(jì)數(shù)器加1?/}IFIJ/?找不到指定插入位置,即I的值超過表中結(jié)點(diǎn)的個(gè)數(shù),則不進(jìn)行插入?/{PRINTF“\N表中不存在第D個(gè)結(jié)點(diǎn),無法進(jìn)行插入\N“,IFREEPRETURNHEAD}ELSE,ELSE{/?找到了第I個(gè)結(jié)點(diǎn),插入X?/PNEXTQNEXT/?插入,修改指針1?/QNEXTP/?插入,修改指針2?/RETURNHEAD}}}算法315在循環(huán)單鏈表中第I個(gè)結(jié)點(diǎn)后插入一個(gè)值為X的新結(jié)點(diǎn),循環(huán)單鏈表的刪除過程如圖,,,,,,,,HEAD,Q,,1HEADHEADNEXT2PRENEXTHEAD,A刪除循環(huán)單鏈表的最前面的(第一個(gè))結(jié)點(diǎn),11,,,,,,PRE,,22,循環(huán)單鏈表的刪除過程如圖,/?????????????????????????????????????????????????????//?函數(shù)功能在循環(huán)單鏈表中刪除一個(gè)值為X的結(jié)點(diǎn)?//?函數(shù)參數(shù)指向NODE類型變量的指針變量HEAD?//?DATATYPE類型的變量X?//?函數(shù)返回值指向NODE類型變量的指針?//?文件名CLNKLISTC,函數(shù)名DELE?//?????????????????????????????????????????????????????/NODE?DELENODE?HEAD,DATATYPEX{NODE?PRENULL,?Q/?Q用于查找值為X的結(jié)點(diǎn),PRE指向Q的前驅(qū)結(jié)點(diǎn)?/IFHEAD/?表為空,則無法做刪除操作?/{PRINTF“\N循環(huán)單鏈表為空,無法做刪除操作“RETURNHEAD},QHEAD/?從第1個(gè)結(jié)點(diǎn)開始準(zhǔn)備查找?/WHILEQNEXTHEADQQNEXT/?PRE為Q的前驅(qū),繼續(xù)查找?/}/?循環(huán)結(jié)束后,PRE為Q的前驅(qū)?/IFQINFOX/?沒找到?/{PRINTF“沒有找到值為D的結(jié)點(diǎn)“,X}ELSE/?找到了,下面要?jiǎng)h除Q?/{IFQHEAD{PRENEXTQNEXTFREEQ}ELSE,IFHEADNEXTHEAD{FREEQHEADNULL}ELSE{PREHEADNEXTWHILEPRENEXTQPREPRENEXT/找Q的前驅(qū)結(jié)點(diǎn)位置/HEADHEADNEXTPRENEXTHEADFREEQ}}RETURNHEAD}算法316在循環(huán)單鏈表中刪除一個(gè)值為X的結(jié)點(diǎn),3.循環(huán)單鏈表的整體插入與刪除操作,圖312一個(gè)循環(huán)單鏈表整體插入到一個(gè)單鏈表前部的圖示,35雙鏈表,351雙鏈表,前面的各種鏈?zhǔn)奖碇?,一個(gè)結(jié)點(diǎn)的指針域是指向它的后繼結(jié)點(diǎn)的,如果需要找一個(gè)結(jié)點(diǎn)P的前驅(qū)結(jié)點(diǎn),則必須從表首指針開始查找,當(dāng)某個(gè)結(jié)點(diǎn)PRE的指針域指向的是結(jié)點(diǎn)P時(shí),即PRENEXTP時(shí),則說明PRE是P的前驅(qū)結(jié)點(diǎn)。如果常常需要知道一個(gè)結(jié)點(diǎn)的前驅(qū)和后繼結(jié)點(diǎn),上述的鏈?zhǔn)奖硎遣贿m合的。既然單鏈表中每個(gè)結(jié)點(diǎn)有一個(gè)指針域指向它的后繼結(jié)點(diǎn),那自然地想到再增設(shè)一個(gè)指針域指向它的前驅(qū)結(jié)點(diǎn),這就構(gòu)成了雙鏈表。,雙鏈表的結(jié)點(diǎn)包括三個(gè)域,一個(gè)是存放數(shù)據(jù)信息的INFO域,另外兩個(gè)是指針域,這里用LLINK和RLINK表示,LLINK指向它的前驅(qū)結(jié)點(diǎn),RLINK指向它的后繼結(jié)點(diǎn)。,雙鏈表的一般情形如圖所示,雙鏈表類型的描述(略),352雙鏈表的實(shí)現(xiàn),雙鏈表結(jié)構(gòu)的C語言描述如下/???????????????????????????????????????//?雙鏈表的頭文件,文件名DLNKLISTH?//???????????????????????????????????????/TYPEDEFINTDATATYPETYPEDEFSTRUCTDLINK_NODE{DATATYPEINFOSTRUCTDLINK_NODE?LLINK,?RLINK}DNODE,/??????????????????????????????????????????????????//?函數(shù)功能輸出雙鏈表中各個(gè)結(jié)點(diǎn)的值?//?函數(shù)參數(shù)指向DNODE類型變量的指針HEAD?//?函數(shù)返回值空?//?文件名DLNKLISTC,函數(shù)名DISPLAY?//??????????????????????????????????????????????????/VOIDDISPLAYDNODE?HEAD{DNODE?PPRINTF“\N“PHEADIFPPRINTF“\N雙鏈表是空的\N“ELSE{PRINTF“\N雙鏈表中各個(gè)結(jié)點(diǎn)的值為\N“WHILEP{PRINTF““,PINFOPPRLINK}}}算法318輸出雙鏈表中各個(gè)結(jié)點(diǎn)的值,DNODE?FINDDNODE?HEAD,INTI{INTJ1DNODE?PHEADIFIRLINKJ/?繼續(xù)沿著右指針向后查找,計(jì)數(shù)器加1?/}IFP{PRINTF“\N第D個(gè)結(jié)點(diǎn)不存在\N“,IRETURNNULL}RETURNP}算法319查找雙鏈表中第I個(gè)結(jié)點(diǎn),雙鏈表插入過程如下圖所示,雙鏈表插入過程如下圖所示,,∧,,,,,,,,,HEAD,1PRLINKQRLINK2PLLINKQ3QRLINKLLINKP4QRLINKP,,,,,,,,,2431,Q,,X,,,P,,,43,,B在雙鏈表中Q所指結(jié)點(diǎn)的后面插入一個(gè)值為X的新結(jié)點(diǎn),,雙鏈表插入過程如下圖所示,,∧,,,,,,,,,1PRLINKQRLINKNULL2PLLINKQ4QRLINKP,,,241,Q,X,∧,,P,,,C在雙鏈表中Q所指結(jié)點(diǎn)(是最后一個(gè)結(jié)點(diǎn))的后面插入一個(gè)值為X的新結(jié)點(diǎn),HEAD,,,/?????????????????????????????????????????????????????//?函數(shù)功能雙鏈表第I個(gè)結(jié)點(diǎn)后插入值為X的新結(jié)點(diǎn)?//?函數(shù)參數(shù)指向DNODE類型變量的指針HEAD?//?DATATYPE類型的變量X,INT類型的變量?//?函數(shù)返回值指向DNODE類型變量的指針?//?文件名DLNKLISTC,函數(shù)名INSERT?//?????????????????????????????????????????????????????/DNODEINSERTDNODEHEAD,DATATYPEX,INTI{
下載積分: 4 賞幣
上傳時(shí)間:2024-01-06
頁數(shù): 113
大?。?0.67(MB)
子文件數(shù):