C語(yǔ)言程序設(shè)計(jì)之入門(mén)課程4

程序設(shè)計(jì)與實(shí)踐C第4集指針與鏈表地址和指針的概念

內(nèi)存區(qū)的每一個(gè)字節(jié)有一個(gè)編號(hào)，這就是“地址”。如果在程序中定義了一個(gè)變量，在對(duì)程序進(jìn)行編譯時(shí)，系統(tǒng)就會(huì)給這個(gè)變量分配內(nèi)存單元。１、按變量地址存取變量值的方式稱(chēng)為“直接訪(fǎng)問(wèn)”方式ｐｒｉｎｔｆ（″％ｄ″，ｉ）；ｓｃａｎｆ（″％ｄ″，＆ｉ）；ｋ＝ｉ＋ｊ；2.另一種存取變量值的方式稱(chēng)為“間接訪(fǎng)問(wèn)”的方式。即，將變量ｉ的地址存放在另一個(gè)變量中。在Ｃ語(yǔ)言中，指針是一種特殊的變量，它是存放地址的。一個(gè)變量的地址稱(chēng)為該變量的“指針”。例如，地址2000是變量ｉ的指針。如果有一個(gè)變量專(zhuān)門(mén)用來(lái)存放另一變量的地址（即指針），則它稱(chēng)為“指針變量”。上述的i_pointer就是一個(gè)指針變量。指針和指針變量的定義：變量的指針和指向變量的指針變量怎樣定義指針變量定義指針變量的一般形式為基類(lèi)型*指針變量名；下面都是合法的定義：float*pointer_３；

char*pointer_４；可以用賦值語(yǔ)句使一個(gè)指針變量得到另一個(gè)變量的地址，從而使它指向一個(gè)該變量。例如：pointer_１＝＆ｉ；pointer_２＝＆ｊ；在定義指針變量時(shí)要注意兩點(diǎn)：指針變量前面的“*”，表示該變量的類(lèi)型為指針型變量。例:float*pointer_1；指針變量名是pointer_1

，而不是*pointer_1

。(2)在定義指針變量時(shí)必須指定基類(lèi)型。需要特別注意的是，只有整型變量的地址才能放到指向整型變量的指針變量中。下面的賦值是錯(cuò)誤的∶

floata;int*pointer_1;pointer_1=&a;在對(duì)指針變量賦值時(shí)需要注意兩點(diǎn)：⑴指針變量中只能存放地址（指針），不要將一個(gè)整數(shù)賦給一個(gè)指針變量。例:pointer_1＝１００；

/*pointer_1是指針變量,１００是整數(shù)，不合法*/(2)賦給指針變量的是變量地址不能是任意的類(lèi)型，而只能是與指針變量的基類(lèi)型具有相同類(lèi)型的變量的地址。

在引用指針變量時(shí)，可能有三種情況：⑴給指針變量賦值。如：

p=&a;⑵引用指針變量的值。如：

printf(“%o”,p);⑶引用指針變量指向的變量。有關(guān)的兩個(gè)運(yùn)算符：＆取地址運(yùn)算符。&a是變量a的地址。*指針運(yùn)算符（或稱(chēng)“間接訪(fǎng)問(wèn)”運(yùn)算符），*p是指針變量p指向的對(duì)象的值。怎樣引用指針變量例10.１通過(guò)指針變量訪(fǎng)問(wèn)整型變量#include<stdio.h>void

main()｛intａ，ｂ；

int*pointer_１，*pointer_２；ａ＝１００；ｂ＝１０；

pointer_１＝＆ａ；/*把變量ａ的地址賦給

pointer_1*/pointer_２＝＆ｂ；/*把變量ｂ的地址賦給

pointer_２*/printf（″%ｄ，%ｄ\ｎ″,ａ,ｂ）；printf（″%ｄ，%ｄ\ｎ″,*pointer_１,*pointer_２）；｝通過(guò)指針引用數(shù)組一個(gè)變量有地址，一個(gè)數(shù)組包含若干元素，每個(gè)數(shù)組元素都在內(nèi)存中占用存儲(chǔ)單元，它們都有相應(yīng)的地址。指針變量既然可以指向變量，當(dāng)然也可以指向數(shù)組元素（把某一元素的地址放到一個(gè)指針變量中）。所謂數(shù)組元素的指針就是數(shù)組元素的地址。數(shù)組元素的指針可以用一個(gè)指針變量指向一個(gè)數(shù)組元素。例如：ｉｎｔａ［１０］；

(定義ａ為包含１０個(gè)整型數(shù)據(jù)的數(shù)組)

ｉｎｔ*ｐ；

(定義ｐ為指向整型變量的指針變量)

ｐ＝＆ａ［０］；

(把ａ［０］元素的地址賦給指針變量ｐ)也就是使ｐ指向ａ數(shù)組的第０號(hào)元素。Ｃ語(yǔ)言規(guī)定在指針指向數(shù)組元素時(shí)，可以對(duì)指針進(jìn)行以下運(yùn)算：加一個(gè)整數(shù)(用+或+=)，如p+1

減一個(gè)整數(shù)(用-或-=)，如p-1

自加運(yùn)算，如p++，++p

自減運(yùn)算，如p--，--p

兩個(gè)指針相減，如p1-p2(只有p1和p2都指向同一數(shù)組中的元素時(shí)才有意義)。指針的運(yùn)算分別說(shuō)明如下：如果指針變量p已指向數(shù)組中的一個(gè)元素，則ｐ＋１指向同一數(shù)組中的下一個(gè)元素，ｐ-１指向同一數(shù)組中的上一個(gè)元素。(2)如果p原來(lái)指向a[0]，執(zhí)行++p后p的值改變了，在p的原值基礎(chǔ)上加d，這樣p就指向數(shù)組的下一個(gè)元素a[1]。(3)如果ｐ的初值為＆ａ[０]，則ｐ＋ｉ和ａ＋ｉ就是數(shù)組元素ａ［ｉ］的地址，或者說(shuō)，它們指向ａ數(shù)組的第ｉ個(gè)元素。*（ｐ＋ｉ）或*（ａ＋ｉ）是ｐ＋ｉ或ａ＋ｉ所指向的數(shù)組元素，即ａ［ｉ］。(5)如果指針變量p1和p2都指向同一數(shù)組，如執(zhí)行p2-p1，結(jié)果是兩個(gè)地址之差除以數(shù)組元素的長(zhǎng)度。通過(guò)指針引用數(shù)組元素引用一個(gè)數(shù)組元素，可以用：

（１）下標(biāo)法，如ａ［ｉ］形式；（２）指針?lè)?，?（ａ＋ｉ）或*（ｐ＋ｉ）。其中ａ是數(shù)組名，ｐ是指向數(shù)組元素的指針變量，其初值ｐ＝ａ。例10.5輸出數(shù)組中的全部元素

假設(shè)有一個(gè)ａ數(shù)組，整型，有１０個(gè)元素。要輸出各元素的值有三種方法：(1)下標(biāo)法#include<stdio.h>voidmain（）｛intａ［１０］；

intｉ；

for（ｉ＝０；ｉ＜１０；ｉ＋＋）

scanf（″％ｄ″，＆ａ［ｉ］）；

printf（″＼ｎ″）；

for（ｉ＝０；ｉ＜１０；ｉ＋＋）

printf（″％ｄ″，ａ［ｉ］）；｝(2)通過(guò)數(shù)組名計(jì)算數(shù)組元素地址，找出元素的值。#include<stdio.h>void

main（）｛intａ［１０］；

intｉ；

for（ｉ＝０；ｉ＜１０；ｉ＋＋）

scanf（″％ｄ″，＆ａ［ｉ］）；

printf（″＼ｎ″）；

for（ｉ＝０；ｉ＜１０；ｉ＋＋）

printf（″％ｄ″，*（ａ＋ｉ））；｝(3)用指針變量指向數(shù)組元素。#include<stdio.h>voidmain（）｛intａ［１０］；

int*ｐ，ｉ；

for（ｉ＝０；ｉ＜１０；ｉ＋＋）

scanf（″％ｄ″，＆ａ［ｉ］）；

printf（″＼ｎ″）；

for（ｐ＝ａ；ｐ＜（ａ＋１０）；ｐ＋＋）

printf（″％ｄ″，*ｐ）；｝22例：跳馬。依下圖將每一步跳馬之后的位置(x,y)放到一個(gè)“結(jié)點(diǎn)”里，再用“鏈子穿起來(lái)”，形成一條鏈，相鄰兩結(jié)點(diǎn)間用一個(gè)指針將兩者連到一起。結(jié)構(gòu)的概念與應(yīng)用23依上圖有7個(gè)結(jié)點(diǎn)(x1,y1)(x2,y2)(x6,y6)(x7,y7)為了表示這種既有數(shù)據(jù)又有指針的情況，引入結(jié)構(gòu)這種數(shù)據(jù)類(lèi)型。24用指針處理鏈表鏈表是程序設(shè)計(jì)中一種重要的動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)，它是動(dòng)態(tài)地進(jìn)行存儲(chǔ)分配的一種結(jié)構(gòu)。動(dòng)態(tài)性體現(xiàn)為：鏈表中的元素個(gè)數(shù)可以根據(jù)需要增加和減少，不像數(shù)組，在聲明之后就固定不變；元素的位置可以變化，即可以從某個(gè)位置刪除，然后再插入到一個(gè)新的地方；251249A1356B1475C1021DNull1、鏈表中的元素稱(chēng)為“結(jié)點(diǎn)”，每個(gè)結(jié)點(diǎn)包括兩個(gè)域：數(shù)據(jù)域和指針域；2、單向鏈表通常由一個(gè)頭指針（head)，用于指向鏈表頭；3、單向鏈表有一個(gè)尾結(jié)點(diǎn)，該結(jié)點(diǎn)的指針部分指向一個(gè)空結(jié)點(diǎn)(NULL)。Head1249135614751021結(jié)點(diǎn)里的指針是存放下一個(gè)結(jié)點(diǎn)的地址26鏈表中結(jié)點(diǎn)的定義鏈表是由結(jié)點(diǎn)構(gòu)成的，關(guān)鍵是定義結(jié)點(diǎn);鏈表的結(jié)點(diǎn)定義打破了先定義再使用的限制,即可以用自己定義自己；遞歸函數(shù)的定義也違反了先定義再使用；這是C語(yǔ)言程序設(shè)計(jì)上的兩大特例27

鏈表的基本操作對(duì)鏈表的基本操作有：（1）創(chuàng)建鏈表是指，從無(wú)到有地建立起一個(gè)鏈表，即往空鏈表中依次插入若干結(jié)點(diǎn)，并保持結(jié)點(diǎn)之間的前驅(qū)和后繼關(guān)系。（2）檢索操作是指，按給定的結(jié)點(diǎn)索引號(hào)或檢索條件，查找某個(gè)結(jié)點(diǎn)。如果找到指定的結(jié)點(diǎn)，則稱(chēng)為檢索成功；否則，稱(chēng)為檢索失敗。（3）插入操作是指，在結(jié)點(diǎn)ki-1與ki之間插入一個(gè)新的結(jié)點(diǎn)k’，使線(xiàn)性表的長(zhǎng)度增1，且ki-1與ki的邏輯關(guān)系發(fā)生如下變化：插入前，ki-1是ki的前驅(qū)，ki是ki-1的后繼；插入后，新插入的結(jié)點(diǎn)k’成為ki-1的后繼、ki的前驅(qū).28（4）刪除操作是指，刪除結(jié)點(diǎn)ki，使線(xiàn)性表的長(zhǎng)度減1，且ki-1、ki和ki+1之間的邏輯關(guān)系發(fā)生如下變化：刪除前，ki是ki+1的前驅(qū)、ki-1的后繼；刪除后，ki-1成為ki+1的前驅(qū)，ki+1成為ki-1的后繼.(5)打印輸出29一個(gè)指針類(lèi)型的成員既可指向其它類(lèi)型的結(jié)構(gòu)體數(shù)據(jù)，也可以指向自己所在的結(jié)構(gòu)體類(lèi)型的數(shù)據(jù)9910189.599103909910785numScorenextnext是structstudent類(lèi)型中的一個(gè)成員，它又指向structstudent類(lèi)型的數(shù)據(jù)。換名話(huà)說(shuō)：next存放下一個(gè)結(jié)點(diǎn)的地址3011.7.2簡(jiǎn)單鏈表#defineNULL0structstudent{longnum;floatscore;structstudent*next;};main(){structstudenta,b,c,*head,*p;a.num=99101;a.score=89.5;b.num=99103;b.score=90;c.num=99107;c.score=85;head=&a;

a.next=&b;b.next=&c;

c.next=NULL;p=head;

do{printf("%ld%5.1f\n",p->num,p->score);

p=p->next;}while(p!=NULL);}例11.7建立和輸出一個(gè)簡(jiǎn)單鏈表各結(jié)點(diǎn)在程序中定義，不是臨時(shí)開(kāi)辟的，始終占有內(nèi)容不放，這種鏈表稱(chēng)為“靜態(tài)鏈表”3111.7.3處理動(dòng)態(tài)鏈表所需的函數(shù)C語(yǔ)言使用系統(tǒng)函數(shù)動(dòng)態(tài)開(kāi)辟和釋放存儲(chǔ)單元1.malloc函數(shù)

函數(shù)原形：void*malloc(unsignedintsize);作用：在內(nèi)存的動(dòng)態(tài)存儲(chǔ)區(qū)中分配一個(gè)

長(zhǎng)度為size的連續(xù)空間。返回值：是一個(gè)指向分配域起始地址的指針（基本類(lèi)型void）。執(zhí)行失?。悍祷豊ULL32函數(shù)原形:void*calloc(unsignedn,unsignedsize);作用：在內(nèi)存動(dòng)態(tài)區(qū)中分配n個(gè)

長(zhǎng)度為size的連續(xù)空間。函數(shù)返回值：指向分配域起始地址的指針執(zhí)行失敗：返回null主要用途：為一維數(shù)組開(kāi)辟動(dòng)態(tài)存儲(chǔ)空間。n

為數(shù)組元素個(gè)數(shù)，每個(gè)元素長(zhǎng)度為size2.calloc

函數(shù)333.free函數(shù)函數(shù)原形：

voidfree(void*p);作用：釋放由p指向的內(nèi)存區(qū)。P:是最近一次調(diào)用calloc或malloc函數(shù)時(shí)返回的值。free函數(shù)無(wú)返回值動(dòng)態(tài)分配的存儲(chǔ)單元在用完后一定要釋放，否則內(nèi)存會(huì)因申請(qǐng)空間過(guò)多引起資源不足而出現(xiàn)故障。34結(jié)點(diǎn)的動(dòng)態(tài)分配ANSIC的三個(gè)函數(shù)(頭文件malloc.h)void*malloc(unsignedintsize)void*calloc(unsignedn,unsignedsize)voidfree(void*p)C++的兩個(gè)函數(shù)new類(lèi)型（初值）delete[]指針變量

/*[]表示釋放數(shù)組，可有可無(wú)）*/使用new的優(yōu)點(diǎn)：可以通過(guò)對(duì)象的大小直接分配，而不管對(duì)象的具體長(zhǎng)度是多少（p340例14.10）35建立動(dòng)態(tài)鏈表基本方法:

三個(gè)結(jié)點(diǎn)（頭結(jié)點(diǎn)head、尾結(jié)點(diǎn)NULL和待插入結(jié)點(diǎn)P）第一步：定義頭結(jié)點(diǎn)head、尾結(jié)點(diǎn)

p2

和待插入結(jié)點(diǎn)p1，待插入的結(jié)點(diǎn)數(shù)據(jù)部分初始化；第二步：該結(jié)點(diǎn)被頭結(jié)點(diǎn)、尾結(jié)點(diǎn)同時(shí)指向。P1=p2=(structstudent*)malloc(LEN);頭指針部分為空，head=NULL;

第三步：重復(fù)申請(qǐng)待插入結(jié)點(diǎn)空間，對(duì)該結(jié)點(diǎn)的數(shù)據(jù)部分賦值（或輸入值），將該結(jié)點(diǎn)插入在最前面，或者最后面（書(shū)上在尾部插入）.

P2->next=P1;P2=P1;

最后:P2->next=NULL;*head,*p1,*p2使用malloc(LEN)P2->next=NULL;36建立動(dòng)態(tài)鏈表9910189.5headP1p21.任務(wù)是開(kāi)辟結(jié)點(diǎn)和輸入數(shù)據(jù)2.并建立前后相鏈的關(guān)系待插入的結(jié)點(diǎn)p1數(shù)據(jù)部分初始化,該結(jié)點(diǎn)被頭結(jié)點(diǎn)head、尾結(jié)點(diǎn)p2同時(shí)指向.37圖11.149910189.5headp29910390p19910189.5headp29910390p1(a)(b)p1重復(fù)申請(qǐng)待插入結(jié)點(diǎn)空間，對(duì)該結(jié)點(diǎn)的數(shù)據(jù)部分賦值（或輸入值）P2->next指向p1新開(kāi)辟的結(jié)點(diǎn)。38圖11.14head9910189.5p1p29910390(c)P2指向新結(jié)點(diǎn)p2=p139圖11.159910189.59910189.5p29910785p1head9910189.59910189.5p29910785p1head(a)(b)40

圖11.16 99103909910785p200p1head9910189.599103909910785NULLp200p1head9910189.541例11.8建立一個(gè)有3名學(xué)生數(shù)據(jù)的單向動(dòng)態(tài)鏈表#defineNULL0#defineLENsizeof(structstudent)structstudent{longnum;floatscore;structstudent*next;};intn;structstudent*creat(void){structstudent*head;structstudent*p1,*p2;n=0;p1=p2=(structstudent*)malloc(LEN);scanf("%1d,%f",&p1->num,&p1->score);head=NULL;結(jié)構(gòu)體類(lèi)型數(shù)據(jù)的長(zhǎng)度，sizeof是“字節(jié)數(shù)運(yùn)算符”定義指針類(lèi)型的函數(shù)。帶回鏈表的起始地址開(kāi)辟長(zhǎng)度為L(zhǎng)EN的內(nèi)存區(qū)P1,p2是指向結(jié)構(gòu)體類(lèi)型數(shù)據(jù)的指針變量，強(qiáng)行轉(zhuǎn)換成結(jié)構(gòu)體類(lèi)型假設(shè)頭指向空結(jié)點(diǎn)42續(xù)while(p1->num!=0){n=n+1;/*n是結(jié)點(diǎn)的個(gè)數(shù)*/if(n==1)head=p1;elsep2->next=p1;p2=p1;p1=(structstudent*)malloc(LEN);scanf("%1d,%f",&p1->num,&p1->score);}p2->next=NULL;return(head);}//返回鏈表的頭指針?biāo)惴ǎ簆1指向新開(kāi)的結(jié)點(diǎn):p1=(stuctstudent*)malloc(LEN);p1的所指向的結(jié)點(diǎn)連接在p2所指向結(jié)點(diǎn)后面，用p2->next=p1來(lái)實(shí)現(xiàn)。p2指向鏈表中最后建立的結(jié)點(diǎn)，:p2=p1;

頭指針指向p1結(jié)點(diǎn)P1開(kāi)辟的新結(jié)點(diǎn)鏈到了p2的后面P1繼續(xù)開(kāi)辟新結(jié)點(diǎn)給新結(jié)點(diǎn)賦值此43輸出鏈表鏈表遍歷1.單向鏈表總是從頭結(jié)點(diǎn)開(kāi)始的；2.每訪(fǎng)問(wèn)一個(gè)結(jié)點(diǎn)，就將當(dāng)前指針向該結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)移動(dòng)：

p=p->next;3.直至下一結(jié)點(diǎn)為空

P=NULL44圖11.18headp

P’P’NULL45例題9voidprint(structstudent*head){structstudent*p;printf("\nNow,These%drecordsare:\n",n);

p=head;if(head!=NULL)do{printf("%ld%5.lf\n",p->num,p->score);

p=p->next;}while(p!=NULL);}46對(duì)鏈表的刪除操作刪除結(jié)點(diǎn)原則：不改變?cè)瓉?lái)的排列順序，只是從鏈表中分離開(kāi)來(lái)，撤消原來(lái)的鏈接關(guān)系。兩種情況：1、要?jiǎng)h的結(jié)點(diǎn)是頭指針?biāo)傅慕Y(jié)點(diǎn)則直接操作；2、不是頭結(jié)點(diǎn)，要依次往下找。另外要考慮：空表和找不到要?jiǎng)h除的結(jié)點(diǎn)47鏈表中結(jié)點(diǎn)刪除需要由兩個(gè)臨時(shí)指針：P1:判斷指向的結(jié)點(diǎn)是不是要?jiǎng)h除的結(jié)點(diǎn)（用于尋找）；P2:始終指向P1的前面一個(gè)結(jié)點(diǎn)；48圖11.19ABDECABDEC(a)(B)49圖11.2099101headp19910399107NULL（a）(b)99101head9910399107NULLp2p1原鏈表P1指向頭結(jié)點(diǎn)P2指向p1指向的結(jié)點(diǎn)。P1指向下移一個(gè)結(jié)點(diǎn)。50圖11.2099101head9910399107NULLp199101head9910399107NULLp2p1(c)(d)經(jīng)判斷后，第1個(gè)結(jié)點(diǎn)是要?jiǎng)h除的結(jié)點(diǎn)，head指向第2個(gè)結(jié)點(diǎn)，第1個(gè)結(jié)點(diǎn)脫離。經(jīng)P1找到要?jiǎng)h除的結(jié)點(diǎn)后使之脫離。51例題10structstudent*del(structstudent*head,longnum){structstudent*p1,*p2;if(head==NULL){printf("\nlistnull!\n");gotoend;}p1=head;while(num!=p1->num&&p1->next!==NULL){p2=p1;p1=p1->next;}

if(num==p1->num)

{if(p1==head)head=p1->next;elsep2->next=p1->next;printf("delete:%ld\n",num);n=n-1;}elseprintf("%ldnotbeenfound!\n",num);

end:return(head);}找到了沒(méi)找到52對(duì)鏈表的插入操作插入結(jié)點(diǎn)：將一個(gè)結(jié)點(diǎn)插入到已有的鏈表中插入原則：1、插入操作不應(yīng)破壞原鏈接關(guān)系2、插入的結(jié)點(diǎn)應(yīng)該在它該在的位置實(shí)現(xiàn)方法：應(yīng)該有一個(gè)插入位置的查找子過(guò)程共有三種情況：1、插入的結(jié)最小2、插入的結(jié)點(diǎn)最大3、插入的結(jié)在中間53

操作分析同刪除一樣，需要幾個(gè)臨時(shí)指針：P0:指向待插的結(jié)點(diǎn);初始化：p0=數(shù)組stu;P1:指向要在P1之前插入結(jié)點(diǎn)；初始化:p1=head;P2:指向要在P2之后插入結(jié)點(diǎn)；插入操作：當(dāng)符合以下條件時(shí)：p0->num與p1->num比較找位置if(p0->num>p1->num)&&(p1->next!=NULL)

則插入的結(jié)點(diǎn)不在p1所指結(jié)點(diǎn)之前；指針后移，交給p2；

p1=p1->next;p2=p1;則繼續(xù)與

p0

指向的數(shù)組去比，直到（p1->next!=NULL)為止。

否則有兩種情況發(fā)生：

if(head==p1)head=p0;p0->next=p1插到原來(lái)第一個(gè)結(jié)點(diǎn)之前；elsep2->next=p0;p0->next=p1;

插到p2指向的結(jié)點(diǎn)之后；還有另外一種情況：插到最后的結(jié)點(diǎn)之后；p1->next=p0;p0->next=NULL;54圖11.2299101headp19910399107NULL（a）99102p055圖11.2299101head9910399107NULL99102p0p2p1(b)56例題11structstudentinsert(structstudent*head,struct

student*stud){structstudent*p0,*p1,*p2;p1=head;p0=stud;if(head==NULL;){head=p0;p0->next=NULL;}elsewhile((p0->num>p1->num)&&(p1->next!=NULL)){p2=p1;p1=p1->next;}if(p0->num<=p1->num) {if(head==p1)head=p0; elsep2->next=p0;p0->next=p1;}else{p1->next=p0;p0->next=NULL;}n=n+1;return(head);}原來(lái)的鏈表是空表P0指向要插的結(jié)點(diǎn)使p0指向的結(jié)點(diǎn)作為頭結(jié)點(diǎn)使p2指向剛才p1指向的結(jié)點(diǎn)插到原來(lái)第一個(gè)結(jié)點(diǎn)之前插到p2指向的結(jié)點(diǎn)之后插到最后的結(jié)點(diǎn)之后鏈接575head61015null128課堂舉例：已有一個(gè)如圖所示的鏈表；它是按結(jié)點(diǎn)中的整數(shù)域從小到大排序的，現(xiàn)在要插入一個(gè)結(jié)點(diǎn)，該結(jié)點(diǎn)中的數(shù)為10待插入結(jié)點(diǎn)此結(jié)點(diǎn)已插入鏈表58分析：按三種情況1、第一種情況，鏈表還未建成（空鏈表），待插入結(jié)點(diǎn)p實(shí)際上是第一個(gè)結(jié)點(diǎn)。這時(shí)必然有head==null。只要讓頭指針指向p

就可以了。語(yǔ)句為6nullheadphead=p;p->next=null;2、第二種情況，鏈表已建成，待插入結(jié)點(diǎn)p

的數(shù)據(jù)要比頭結(jié)點(diǎn)的數(shù)據(jù)還要小，這時(shí)有

(p->num)<(head->num)當(dāng)然p結(jié)點(diǎn)要插在head結(jié)點(diǎn)前。596head8512nullheadpp->next=head;head=p;語(yǔ)句為null603、第三種情況，鏈表已建成，待插入結(jié)點(diǎn)p的數(shù)據(jù)比頭結(jié)點(diǎn)的數(shù)據(jù)大，需要找到正確的插入位置。這時(shí)，可以借助兩個(gè)結(jié)構(gòu)指針r和g，利用循環(huán)比較來(lái)找到正確位置。然后將結(jié)點(diǎn)p

插入到鏈表中正確的位置。 參見(jiàn)下面的圖示616head81213nullp15gr說(shuō)明：這種情況下，p結(jié)點(diǎn)已經(jīng)與鏈表的第一個(gè)結(jié)點(diǎn)比較過(guò)了，所以從鏈表的下一個(gè)結(jié)點(diǎn)開(kāi)始比較。13>8，繼續(xù)比較。626head81213nullp15gr說(shuō)明：13>12，繼續(xù)比較。636head81213p15grnull說(shuō)明：13<15，找到了正確的插入位置，則插入結(jié)點(diǎn)p;語(yǔ)句為：r>next=p;p->next=g;64//結(jié)構(gòu)7.c#include<stdio.h> //預(yù)編譯命令#include<malloc.h> //內(nèi)存空間分配#definenull0 //定義空指針常量#defineLENsizeof(structnumST) //定義常量，表示結(jié)構(gòu)長(zhǎng)度structnumST //結(jié)構(gòu)聲明{ intnum; //整型數(shù) structnumST*next; //numST結(jié)構(gòu)指針};參考程序65//被調(diào)用函數(shù)insert()，兩個(gè)形參分別表示鏈表和待插入的結(jié)點(diǎn)voidinsert(structnumST**phead,structnumST*p){ //函數(shù)體開(kāi)始

structnumST*q,*r; //定義結(jié)構(gòu)指針q,r if((*phead)==null) //第一種情況，鏈表為空

{ *phead=p; //鏈表頭指向p return; //完成插入操作，返回

}

else //鏈表不為空 {

//第二種情況，p結(jié)點(diǎn)num值小于鏈表頭結(jié)點(diǎn)的num值 if((*phead)->num>p->num) {

//將p結(jié)點(diǎn)插到鏈表頭部

p->next=*phead;//將p的next指針指向鏈表頭(*phead)

*phead=p;

//將鏈表頭賦值為p

return;

//返回 }6