C語言程序設計之入門課程4

程序設計與實踐C第4集指針與鏈表地址和指針的概念

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

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

，而不是*pointer_1

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

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

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

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

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

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

main()｛intａ，ｂ；

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

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

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

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

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

ｉｎｔ*ｐ；

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

ｐ＝＆ａ［０］；

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

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

自加運算，如p++，++p

自減運算，如p--，--p

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

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

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

intｉ；

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

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

printf（″＼ｎ″）；

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

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

鏈表的基本操作對鏈表的基本操作有：（1）創(chuàng)建鏈表是指，從無到有地建立起一個鏈表，即往空鏈表中依次插入若干結(jié)點，并保持結(jié)點之間的前驅(qū)和后繼關系。（2）檢索操作是指，按給定的結(jié)點索引號或檢索條件，查找某個結(jié)點。如果找到指定的結(jié)點，則稱為檢索成功；否則，稱為檢索失敗。（3）插入操作是指，在結(jié)點ki-1與ki之間插入一個新的結(jié)點k’，使線性表的長度增1，且ki-1與ki的邏輯關系發(fā)生如下變化：插入前，ki-1是ki的前驅(qū)，ki是ki-1的后繼；插入后，新插入的結(jié)點k’成為ki-1的后繼、ki的前驅(qū).28（4）刪除操作是指，刪除結(jié)點ki，使線性表的長度減1，且ki-1、ki和ki+1之間的邏輯關系發(fā)生如下變化：刪除前，ki是ki+1的前驅(qū)、ki-1的后繼；刪除后，ki-1成為ki+1的前驅(qū)，ki+1成為ki-1的后繼.(5)打印輸出29一個指針類型的成員既可指向其它類型的結(jié)構體數(shù)據(jù)，也可以指向自己所在的結(jié)構體類型的數(shù)據(jù)9910189.599103909910785numScorenextnext是structstudent類型中的一個成員，它又指向structstudent類型的數(shù)據(jù)。換名話說：next存放下一個結(jié)點的地址3011.7.2簡單鏈表#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建立和輸出一個簡單鏈表各結(jié)點在程序中定義，不是臨時開辟的，始終占有內(nèi)容不放，這種鏈表稱為“靜態(tài)鏈表”3111.7.3處理動態(tài)鏈表所需的函數(shù)C語言使用系統(tǒng)函數(shù)動態(tài)開辟和釋放存儲單元1.malloc函數(shù)

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

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

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

為數(shù)組元素個數(shù)，每個元素長度為size2.calloc

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

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

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

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

p2

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

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

P2->next=P1;P2=P1;

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

圖11.16 99103909910785p200p1head9910189.599103909910785NULLp200p1head9910189.541例11.8建立一個有3名學生數(shù)據(jù)的單向動態(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é)構體類型數(shù)據(jù)的長度，sizeof是“字節(jié)數(shù)運算符”定義指針類型的函數(shù)。帶回鏈表的起始地址開辟長度為LEN的內(nèi)存區(qū)P1,p2是指向結(jié)構體類型數(shù)據(jù)的指針變量，強行轉(zhuǎn)換成結(jié)構體類型假設頭指向空結(jié)點42續(xù)while(p1->num!=0){n=n+1;/*n是結(jié)點的個數(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);}//返回鏈表的頭指針算法：p1指向新開的結(jié)點:p1=(stuctstudent*)malloc(LEN);p1的所指向的結(jié)點連接在p2所指向結(jié)點后面，用p2->next=p1來實現(xiàn)。p2指向鏈表中最后建立的結(jié)點，:p2=p1;

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

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

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對鏈表的刪除操作刪除結(jié)點原則：不改變原來的排列順序，只是從鏈表中分離開來，撤消原來的鏈接關系。兩種情況：1、要刪的結(jié)點是頭指針所指的結(jié)點則直接操作；2、不是頭結(jié)點，要依次往下找。另外要考慮：空表和找不到要刪除的結(jié)點47鏈表中結(jié)點刪除需要由兩個臨時指針：P1:判斷指向的結(jié)點是不是要刪除的結(jié)點（用于尋找）；P2:始終指向P1的前面一個結(jié)點；48圖11.19ABDECABDEC(a)(B)49圖11.2099101headp19910399107NULL（a）(b)99101head9910399107NULLp2p1原鏈表P1指向頭結(jié)點P2指向p1指向的結(jié)點。P1指向下移一個結(jié)點。50圖11.2099101head9910399107NULLp199101head9910399107NULLp2p1(c)(d)經(jīng)判斷后，第1個結(jié)點是要刪除的結(jié)點，head指向第2個結(jié)點，第1個結(jié)點脫離。經(jīng)P1找到要刪除的結(jié)點后使之脫離。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);}找到了沒找到52對鏈表的插入操作插入結(jié)點：將一個結(jié)點插入到已有的鏈表中插入原則：1、插入操作不應破壞原鏈接關系2、插入的結(jié)點應該在它該在的位置實現(xiàn)方法：應該有一個插入位置的查找子過程共有三種情況：1、插入的結(jié)最小2、插入的結(jié)點最大3、插入的結(jié)在中間53

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

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

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

p0

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

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

if(head==p1)head=p0;p0->next=p1插到原來第一個結(jié)點之前；elsep2->next=p0;p0->next=p1;

插到p2指向的結(jié)點之后；還有另外一種情況：插到最后的結(jié)點之后；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);}原來的鏈表是空表P0指向要插的結(jié)點使p0指向的結(jié)點作為頭結(jié)點使p2指向剛才p1指向的結(jié)點插到原來第一個結(jié)點之前插到p2指向的結(jié)點之后插到最后的結(jié)點之后鏈接575head61015null128課堂舉例：已有一個如圖所示的鏈表；它是按結(jié)點中的整數(shù)域從小到大排序的，現(xiàn)在要插入一個結(jié)點，該結(jié)點中的數(shù)為10待插入結(jié)點此結(jié)點已插入鏈表58分析：按三種情況1、第一種情況，鏈表還未建成（空鏈表），待插入結(jié)點p實際上是第一個結(jié)點。這時必然有head==null。只要讓頭指針指向p

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

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

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

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

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

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

}

else //鏈表不為空 {

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

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

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

*phead=p;

//將鏈表頭賦值為p

return;

//返回 }6