關(guān)于單鏈表的操作

《關(guān)于單鏈表的操作》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、關(guān)于單鏈表的操作單向鏈表結(jié)構(gòu)描述示例：structlinklist{intdata；structlinklist*next；}；structlinklist*head；單鏈表的建立在鏈表的操作中用到的幾個(gè)函數(shù)：(1)malloc（size）在內(nèi)存的動(dòng)態(tài)存儲(chǔ)區(qū)申請(qǐng)一個(gè)長(zhǎng)度為size字節(jié)的連續(xù)空間。并將此存儲(chǔ)空間的起始地址作為函數(shù)值返回。malloc函數(shù)的原型為：void*malloc(unsignedintsize)函數(shù)值為指針（地址），這個(gè)指針是指向void類型的，也就是不規(guī)定指向任何具體的類型。如

2、果內(nèi)存缺乏足夠大的空間進(jìn)行分配，則malloc的函數(shù)值為“空指針”。(2)calloc（n，size）在內(nèi)存的動(dòng)態(tài)存儲(chǔ)區(qū)申請(qǐng)n個(gè)長(zhǎng)度為size字節(jié)的連續(xù)空間，函數(shù)返回值為分配空間的首地址。若此函數(shù)未被成功執(zhí)行，函數(shù)返回值為0。函數(shù)返回值為該空間的首地址。其函數(shù)原型為：void*calloc(unsignedintn，unsignedintsize)(3)free（p）釋放由指針p所指向的存儲(chǔ)單元，而所釋放的存儲(chǔ)單元的大小是最近一次調(diào)用malloc（）函數(shù)或calloc（）函數(shù)時(shí)所申請(qǐng)的存儲(chǔ)空間。fr

3、ee函數(shù)的原型為：voidfree(void*ptr)系統(tǒng)可以回收所釋放的空間，另行分配作為它用。(4)realloc函數(shù)。其函數(shù)的原型為：voidrealloc(void*ptr，unsignedintsize)其作用是將ptr所指向的存儲(chǔ)區(qū)（原先用malloc函數(shù)分配的）的大小改為size個(gè)字節(jié)?？梢允乖确峙鋮^(qū)擴(kuò)大和縮小。它的函數(shù)返回值是一個(gè)指針，即新的存儲(chǔ)區(qū)的首地址。例1　使用表首插入法建立鏈表。表首插入法建立鏈表，這種方法的特點(diǎn)是：新產(chǎn)生的結(jié)點(diǎn)作為新的表頭插入鏈表。#include

4、io.h>voidmain(）{structlinklist{intdata；structlinklist*next；}；structlinklist*head，*p；/*head頭指針，p申請(qǐng)單元指針*/head=NULL；/*空鏈表*//*申請(qǐng)空間，并將指針p強(qiáng)制轉(zhuǎn)換成所指向的結(jié)構(gòu)體類型*/p=(structlinklist*)malloc(sizeof(structlinklist))；scanf("%d"，&p?>data)；/*得到數(shù)據(jù)，放結(jié)點(diǎn)數(shù)據(jù)域*/while(p?>data>0

5、)/*假設(shè)所給數(shù)據(jù)都大于0*/{p?>next=head；/*建立鏈接，當(dāng)前結(jié)點(diǎn)指針域存放下一結(jié)點(diǎn)地址*/head=p；/*用頭指針保存當(dāng)前結(jié)點(diǎn)*//*為下一個(gè)結(jié)點(diǎn)申請(qǐng)空間*/p=(structlinklist*)malloc(sizeof(structlinklist))；scanf("%d"，&p?>data)；/*得到新結(jié)點(diǎn)數(shù)據(jù)*/}}運(yùn)行該程序，輸入準(zhǔn)備建立鏈表的各數(shù)據(jù)，以0結(jié)束數(shù)據(jù)的輸入，即可得到一個(gè)鏈表。由于是表首添加法，最后輸出鏈表中的數(shù)據(jù)的輸入順序正好與輸入順序相反。例2　表尾插入法

6、建立鏈表若將鏈表的左端固定，鏈表不斷向右延伸，這種建立鏈表的方法稱為表尾插入法。表尾插入法建立鏈表時(shí)，頭指針固定不動(dòng)，故必須設(shè)立一個(gè)搜索指針，向鏈表右邊延伸，則整個(gè)算法中應(yīng)設(shè)立三個(gè)鏈表指針，即頭指針head、搜索指針p2、申請(qǐng)單元指針p1。表尾插入法最先得到的是頭結(jié)點(diǎn)。#includevoidmain(){structlinklist{intdata；structlinklist*next；}；structlinklist*head，*p1，*p2；head=NULL；/*空鏈表*

7、/p1=（structlinklist*）malloc（sizeof（structlinklist））；/*申請(qǐng)空間*/p2=p1;scanf（"%d"，&p1->data）；/*得到數(shù)據(jù)*/while（p1->data>0）{if（head==NULL）head=p1；elsep2->next=p1；/*建立連接*/p2=p1；/*保存當(dāng)前結(jié)點(diǎn)*//*為下一個(gè)結(jié)點(diǎn)申請(qǐng)空間*/p1=(structlinklist*)malloc(sizeof(structlinklist))；scan

8、f("%d"，&p1?>data)；/*得到下一個(gè)結(jié)點(diǎn)數(shù)據(jù)*/}p2?>next=NULL；/*最后的尾結(jié)點(diǎn)指針域?yàn)榭罩羔?/}運(yùn)行該程序，輸入準(zhǔn)備建立鏈表的各數(shù)據(jù)，以0作為結(jié)束數(shù)據(jù)的輸入，即可得到一個(gè)鏈表，該鏈表的輸出順序與輸入順序一致。單鏈表的有關(guān)操作鏈表的基本操作包括建立鏈表、鏈表結(jié)點(diǎn)的插入、刪除、輸出和查找等。下面介紹完成單鏈表的基本操作的函數(shù)。1.輸出鏈表中所有結(jié)點(diǎn)要依次輸出鏈表中各結(jié)點(diǎn)的數(shù)據(jù)比較容易。首先要知道表頭結(jié)點(diǎn)的地址，即要知道head的值，然后設(shè)一