C語(yǔ)言鏈表詳解課件

第十一章鏈表鏈表詳解珍藏版1精選ppt課件例：跳馬。依下圖將每一步跳馬之后的位置(x,y)放到一個(gè)“結(jié)點(diǎn)”里，再用“鏈子穿起來(lái)”，形成一條鏈，相鄰兩結(jié)點(diǎn)間用一個(gè)指針將兩者連到一起。結(jié)構(gòu)的概念與應(yīng)用2精選ppt課件依上圖有7個(gè)結(jié)點(diǎn)(x1,y1)(x2,y2)(x6,y6)(x7,y7)為了表示這種既有數(shù)據(jù)又有指針的情況，引入結(jié)構(gòu)這種數(shù)據(jù)類(lèi)型。3精選ppt課件11.7用指針處理鏈表鏈表是程序設(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è)新的地方；4精選ppt課件1249A1356B1475C1021DNull1、鏈表中的元素稱(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)的地址5精選ppt課件鏈表中結(jié)點(diǎn)的定義鏈表是由結(jié)點(diǎn)構(gòu)成的，關(guān)鍵是定義結(jié)點(diǎn);鏈表的結(jié)點(diǎn)定義打破了先定義再使用的限制,即可以用自己定義自己；遞歸函數(shù)的定義也違反了先定義再使用；這是C語(yǔ)言程序設(shè)計(jì)上的兩大特例6精選ppt課件

鏈表的基本操作對(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’，使線性表的長(zhǎng)度增1，且ki-1與ki的邏輯關(guān)系發(fā)生如下變化：插入前，ki-1是ki的前驅(qū)，ki是ki-1的后繼；插入后，新插入的結(jié)點(diǎn)k’成為ki-1的后繼、ki的前驅(qū).7精選ppt課件（4）刪除操作是指，刪除結(jié)點(diǎn)ki，使線性表的長(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)打印輸出8精選ppt課件一個(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ù)。換名話說(shuō)：next存放下一個(gè)結(jié)點(diǎn)的地址9精選ppt課件11.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)鏈表”10精選ppt課件11.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í)行失?。悍祷豊ULL11精選ppt課件函數(shù)原形:void*calloc(unsignedn,unsignedsize);作用：在內(nèi)存動(dòng)態(tài)區(qū)中分配n個(gè)

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

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

函數(shù)12精選ppt課件3.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)故障。13精選ppt課件結(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）14精選ppt課件11.7.4建立動(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;15精選ppt課件11.7.4建立動(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í)指向.16精選ppt課件圖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)。17精選ppt課件圖11.14head9910189.5p1p29910390(c)P2指向新結(jié)點(diǎn)p2=p118精選ppt課件圖11.159910189.59910189.5p29910785p1head9910189.59910189.5p29910785p1head(a)(b)19精選ppt課件

圖11.16 99103909910785p200p1head9910189.599103909910785NULLp200p1head9910189.520精選ppt課件例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)21精選ppt課件續(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)賦值此22精選ppt課件11.7.5輸出鏈表鏈表遍歷1.單向鏈表總是從頭結(jié)點(diǎn)開(kāi)始的；2.每訪問(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=NULL23精選ppt課件圖11.18headp

P’P’NULL24精選ppt課件例題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);}25精選ppt課件11.7.6對(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)26精選ppt課件鏈表中結(jié)點(diǎn)刪除需要由兩個(gè)臨時(shí)指針：P1:判斷指向的結(jié)點(diǎn)是不是要?jiǎng)h除的結(jié)點(diǎn)（用于尋找）；P2:始終指向P1的前面一個(gè)結(jié)點(diǎn)；27精選ppt課件圖11.19ABDECABDEC(a)(B)28精選ppt課件圖11.2099101headp19910399107NULL（a）(b)99101head9910399107NULLp2p1原鏈表P1指向頭結(jié)點(diǎn)P2指向p1指向的結(jié)點(diǎn)。P1指向下移一個(gè)結(jié)點(diǎn)。29精選ppt課件圖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)后使之脫離。30精選ppt課件例題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)找到31精選ppt課件11.7.7對(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é)在中間32精選ppt課件

操作分析同刪除一樣，需要幾個(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;33精選ppt課件圖11.2299101headp19910399107NULL（a）99102p034精選ppt課件圖11.2299101head9910399107NULL99102p0p2p1(b)35精選ppt課件例題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)之后鏈接36精選ppt課件5head61015null128課堂舉例：已有一個(gè)如圖所示的鏈表；它是按結(jié)點(diǎn)中的整數(shù)域從小到大排序的，現(xiàn)在要插入一個(gè)結(jié)點(diǎn)，該結(jié)點(diǎn)中的數(shù)為10待插入結(jié)點(diǎn)此結(jié)點(diǎn)已插入鏈表37精選ppt課件分析：按三種情況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)前。38精選ppt課件6head8512nullheadpp->next=head;head=p;語(yǔ)句為null39精選ppt課件3、第三種情況，鏈表已建成，待插入結(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)下面的圖示40精選ppt課件6head81213nullp15gr說(shuō)明：這種情況下，p結(jié)點(diǎn)已經(jīng)與鏈表的第一個(gè)結(jié)點(diǎn)比較過(guò)了，所以從鏈表的下一個(gè)結(jié)點(diǎn)開(kāi)始比較。13>8，繼續(xù)比較。41精選ppt課件6head81213nullp15gr說(shuō)明：13>12，繼續(xù)比較。42精選ppt課件6head81213p15grnull說(shuō)明：13<15，找到了正確的插入位置，則插入結(jié)點(diǎn)p;語(yǔ)句為：r>next=p;p->next=g;43精選ppt課件//結(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)指針};參考程序44精選ppt課件//被調(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;

//返回 }45精選ppt課件

//第三種情況，循環(huán)查找正確位置 r=*phead; //r賦值為鏈表頭 q=(*phead)->next; //q賦值為鏈表的下一個(gè)結(jié)點(diǎn) while(q!=null) //利用循環(huán)查找正確位置 { //判斷當(dāng)前結(jié)點(diǎn)num是否小于p結(jié)點(diǎn)的num if(q->num<p->num) { r=q; //r賦值為q，即指向q所指的結(jié)點(diǎn) q=q->next;//q指向鏈表中相鄰的下一個(gè)結(jié)點(diǎn) } else //找到了正確的位置 break; //退出循環(huán) } //將p結(jié)點(diǎn)插入正確的位置 r->next=p; p->next=q; }}46精選ppt課件//被調(diào)用函數(shù)，形參為ST結(jié)構(gòu)指針，用于輸出鏈表內(nèi)容voidprint(structnumST*head)

{ intk=0; //整型變量，用于計(jì)數(shù) structnumST*r; //聲明r為ST結(jié)構(gòu)指針 r=head; //r賦值為head，即指向鏈表頭

while(r!=null) //當(dāng)型循環(huán)，鏈表指針不為空則繼續(xù) { //循環(huán)體開(kāi)始 k=k+1; //計(jì)數(shù)加1 printf("%d%d\n",k,r->num);

r=r->next; //取鏈表中相鄰的下一個(gè)結(jié)點(diǎn) } //循環(huán)體結(jié)束} 47精選ppt課件voidmain() //主函數(shù)開(kāi)始{

//函數(shù)體開(kāi)始 structnumST*head,*p; //ST型結(jié)構(gòu)指針 head=null; //分配兩個(gè)ST結(jié)構(gòu)的內(nèi)存空間，用于構(gòu)造鏈表 head=(structnumST*)malloc(LEN); head->next=(structnumST*)malloc(LEN); //為鏈表中的兩個(gè)結(jié)點(diǎn)中的num賦值為5和10 head->num=5; head->next->num=10; head->next->next=null; //鏈表尾賦值為空 //構(gòu)造一個(gè)結(jié)點(diǎn)p，用于插入鏈表 p=(structnumST*)malloc(LEN); p->num=8; p->next=null; insert(&head,p);

//調(diào)用create函數(shù)建立鏈表， print(head); //調(diào)用print函數(shù)，輸出鏈表內(nèi)容} //主函數(shù)結(jié)束48精選ppt課件說(shuō)明：函數(shù)insert()的第一個(gè)形參為structnumST**類(lèi)型，即“指針的指針”。調(diào)用時(shí)送入的實(shí)參是鏈表頭指針的地址，即程序中的&head。這樣對(duì)head的修改才會(huì)在函數(shù)返回后仍有效。如果形參為structnumST*，則傳入的為指針，當(dāng)函數(shù)返回后，head無(wú)法改變。49精選ppt課件11.8共用體

構(gòu)造類(lèi)型之二——聯(lián)合在同一存儲(chǔ)單元里，根據(jù)需要放不同類(lèi)型的數(shù)據(jù)，使用覆蓋技術(shù)。50精選ppt課件11.8.1概念單元起始地址：1000。三個(gè)變量（數(shù)據(jù)）占用同一單元：1000——1003浮點(diǎn)型（4byte）字符型（1byte）整型（2Byte）51精選ppt課件共用體變量的定義格式（一般形式）：

union聯(lián)合類(lèi)型名

{成員列表

}變量列表；11.8.2共用體變量的引用方式同結(jié)構(gòu)類(lèi)型變量的引用格式：變量名.成員名52精選ppt課件格式與結(jié)構(gòu)類(lèi)型的定義和變量聲明形式上類(lèi)似，但實(shí)質(zhì)上有區(qū)別：

結(jié)構(gòu)類(lèi)型的長(zhǎng)度=各成員的長(zhǎng)度和；各成員占獨(dú)立的存儲(chǔ)單元，不共享；聯(lián)合類(lèi)型的長(zhǎng)度為成員中長(zhǎng)度的最大者，各成員共享長(zhǎng)度最大的存儲(chǔ)單元；53精選ppt課件11.8.3共用體類(lèi)型數(shù)據(jù)的特點(diǎn)雖然同一內(nèi)存單元內(nèi)可以存放不同類(lèi)型（同一地址）、不同長(zhǎng)度的數(shù)據(jù)，但任一時(shí)刻，只有一種類(lèi)型數(shù)據(jù)（最后賦值的）起作用；其它的都沒(méi)有意義；不能對(duì)共用體變量整體賦值，也不能對(duì)其初始化。共用變量不可作為函數(shù)的參數(shù)，但可以通過(guò)指針指向；共用體類(lèi)型可以和結(jié)構(gòu)類(lèi)型/數(shù)組類(lèi)型互為基類(lèi)型；p28954精選ppt課件例題12struct{intnum;charname[10];charsex;charjob;union{intclass;charposition[10];}category;}person[2];main(){intn,i;for(i=0;i<2;i++);{scanf("%d，%s，%c，%c”,&person[i].num,person[i].name,&person[i].sex,&person[i].job);55精選ppt課件if(person[i].job=='s')scanf("%d",&person[i].category.class);elseif(person[i].job=='t')scanf("%s",person[i].category.position); elseprintf("inputerror!");}printf("\n");printf("no.namesexjobclass/position\n");for(i=0;i<2;i++){if(person[i].job=='s')printf("%-6d%-10s%-3c%-3c%-6d\n",person[i].num,person[i].name,person[i].sex,person[i].job,person[i].category.class);elseprintf("%-6d%-10s%-3c%-3c%-6s\n",person[i].num,person[i].name,person[i].sex,person[i].job,person[i].category.position);}}續(xù)56精選ppt課件

枚舉類(lèi)型

----構(gòu)造類(lèi)型之三57精選ppt課件11.9枚舉類(lèi)型枚舉類(lèi)型是指能將類(lèi)型所包含的值一一列舉出來(lái)。枚舉值稱(chēng)為枚舉常量定義枚舉類(lèi)型的關(guān)鍵字是enum。其類(lèi)型的定義以及變量的聲明同結(jié)構(gòu)類(lèi)型和聯(lián)合類(lèi)型；聲明格式：enumweekday(sum,mon,tue,wed,thu,fri,sat);定義變量：enumweekdayworkday,week_end;58精選ppt課件關(guān)于枚舉類(lèi)型變量在C編譯中，對(duì)枚舉元素按常量處理；對(duì)枚舉型變量的賦值（枚舉型變量的取值）只能取該變量所屬枚舉類(lèi)型的枚舉常量值；一個(gè)整數(shù)不能直接賦給一個(gè)枚舉變量。進(jìn)行強(qiáng)制性轉(zhuǎn)換；59精選ppt課件

說(shuō)明（1）枚舉型僅適應(yīng)于取值有限的數(shù)據(jù)。例如，根據(jù)現(xiàn)行的歷法規(guī)定，１周７天，１年１２個(gè)月。（2）取值表中的值稱(chēng)為枚舉元素，其含義由程序解釋。例如，不是因?yàn)閷?xiě)成“Sun”就自動(dòng)代表“星期天”。事實(shí)上，枚舉元素用什么表示都可以。（3）枚舉元素作為常量是有值的──定義時(shí)的順序號(hào)（從０開(kāi)始），所以枚舉元素可以進(jìn)行比較，比較規(guī)則是：序號(hào)大者為大！例如，上例中的Sun=0、Mon=1、……、Sat=6，所以Mon>Sun、Sat最大。（4）枚舉元素的值也是可以人為改變的：在定義時(shí)由程序指定。例如，如果enumweekdays{Sun=７,Mon＝１,Tue,Wed,Thu,Fri,Sat}；則Sun=７，Mon=１，從Tue=2開(kāi)始，依次增１。60精選ppt課件例題13/*file1.c文件1*/main(){externenter-string(charstr[80]);externdelete-string(charstr[],charch);externprint-string(charstr[]);charc;charstr[80];enter_string(str);scanf("%c",&c);delete_string(str,c);print_string(str);}/*file2.c文件2*/#include<stdio.h>enter_string(charstr[80]){gets(str);}61精選ppt課件續(xù)for(i=0;i<2;i++){if(person[i].job=='s')printf("%-6d%-10s%-3c%-3c%-6d\n",person[i].num,person[i].name,person[i].sex,person[i].job,person[i].category.class);elseprintf("%-6d%-10s%-3c%-3c%-6s\n",person[i].num,person[i].name,person[i].sex,person[i].job,person[i].category.position);}}62精選ppt課件11.10用typedef為類(lèi)型定義新名字

除可直接使用Ｃ提供的標(biāo)準(zhǔn)類(lèi)型和自定義的類(lèi)型（結(jié)構(gòu)、共用、枚舉）外，也可使用typedef定義已有類(lèi)型的別名。該別名與標(biāo)準(zhǔn)類(lèi)型名一樣，可用來(lái)定義相應(yīng)的變量。定義已有類(lèi)型別名的方法如下：

（1）按定義變量的方法，寫(xiě)出定義體；

（2）將變量名換成別名；

（3）在定義體最前面加上typedef。63精選ppt課件11.10用typeded為類(lèi)型定義新名字任何已有的類(lèi)型可以重新命名typedeflonginteger;

//將long重新命名為integer，使得integer和long同等使用可以和新類(lèi)型定義一起定義名字typedefintARR[10];//定義了一個(gè)數(shù)組名ARR，它是具有10個(gè)元素的整型數(shù)組類(lèi)型typedefstruct{intnum; floatscore; }S;/*定義結(jié)構(gòu)體別名為S*/STUDENTstu1;64精選ppt課件討論：typedef和#define說(shuō)明：（1）用typedef只是給已有類(lèi)型增加１個(gè)別名，并不能創(chuàng)造１個(gè)新的類(lèi)型。就如同人一樣，除學(xué)名外，可以再取一個(gè)小名（或雅號(hào)），但并不能創(chuàng)造出另一個(gè)人來(lái)。（2）typedef與#define有相似之處，但二者是不同的：前者是由編譯器在編譯時(shí)處理的；后者是由編譯預(yù)處理器在編譯預(yù)處理時(shí)處理的，而且只能作簡(jiǎn)單的字符串替換。65精選ppt課件structTM{ intx,y; //結(jié)構(gòu)TM的成員，x,y為整數(shù)型

structTM＊

next//結(jié)構(gòu)TM的成員，屬TM型}下面的表是馬的跳步方案，從左下角跳到右上角結(jié)點(diǎn)n1n2n3n4n5n6n7xy00122443647284結(jié)構(gòu)體與共體例子66精選ppt課件84NULLNULL為空地址下面是形成鏈表的一個(gè)參考程序24&n412&n300&n2&n1head67精選ppt課件//結(jié)構(gòu)1.c#include<stdio.h> //預(yù)編譯命令#definenull0 //定義空指針常量structTM //定義結(jié)構(gòu)TM{ intx,y; //整型變量x,y structTM＊next; //指向TM結(jié)構(gòu)的指針};voidmain() //主函數(shù){ //主函數(shù)開(kāi)始

inti; //聲明整型變量

//聲明TM結(jié)構(gòu)n1~n7,結(jié)構(gòu)指針head,pstructTMn1,n2,n3,n4,n5,n6,n7,＊head,＊p;68精選ppt課件//分別對(duì)TM結(jié)構(gòu)n1~n7中的x,y賦值

n1.x=0;n1.y=0;n2.x=1;n2.y=2;n3.x=2;n3.y=4;n4.x=4;n4.y=4;n5.x=6;n5.y=4;n6.x=7;n6.y=2;n7.x=8;n7.y=4;//head賦值為n1，即head指向n1head=&n1;//n1~n7構(gòu)成鏈表

n1.next=&n2;n2.next=&n3;n3.next=&n4;n4.next=&n5;n5.next=&n6;n6.next=&n7;//n7的next指針賦值為空指針

n7.next=null;69精選ppt課件

p=head; //p賦值為head，即p指向head所指的內(nèi)容

i=1; //i賦值為1 do //直到型循環(huán)

{ //循環(huán)體開(kāi)始

//輸出結(jié)點(diǎn)信息

printf("結(jié)點(diǎn)%d:x=%d,y=%d\n",i,p->x,p->y); p=p->next; //p指向下一個(gè)結(jié)點(diǎn)

i=i+1; //計(jì)數(shù)加1 }while(p!=null); //未到達(dá)鏈表尾部，則繼續(xù)循環(huán)} //主函數(shù)結(jié)束70精選ppt課件用結(jié)構(gòu)數(shù)組，利用鍵盤(pán)輸入結(jié)點(diǎn)中的數(shù)據(jù)。重點(diǎn)看

scanf(“%d”,&a); n[i].x=a;結(jié)構(gòu)數(shù)組，數(shù)組中的元素為結(jié)構(gòu)類(lèi)型的數(shù)據(jù)，如n[8]//結(jié)構(gòu)2.c#include<stdio.h> //預(yù)編譯命令#definenull0 //定義空指針常量structTM //定義TM結(jié)構(gòu){ intx,y; //整型變量x,y structTM*next;

//指向TM結(jié)構(gòu)的指針};71精選ppt課件voidmain() //主函數(shù){ //主函數(shù)開(kāi)始inti,a,b;

//聲明整型變量i,a,b//聲明TM型結(jié)構(gòu)數(shù)組n[8]，TM結(jié)構(gòu)指針head,pstructTMn[8],*head,*p;for(i=1;i<=7;i=i+1)

//循環(huán) { //循環(huán)體開(kāi)始 printf("輸入n[%d]的x\n",i); //提示輸入第i個(gè)結(jié)構(gòu)的x值 scanf("%d",&a); //輸入a n[i].x=a;

//將a的值賦給結(jié)構(gòu)n[i]的元素x

printf("輸入n[%d]的y\n",i); //提示輸入第i個(gè)結(jié)構(gòu)的y值 scanf("%d",&b); //輸入b n[i].y=b;

//將b的值賦給結(jié)構(gòu)n[i]的元素y }

//循環(huán)體結(jié)束72精選ppt課件 head=&n[1]; //鏈表頭部指向n[1] for(i=1;i<=6;i=i+1) //將結(jié)構(gòu)數(shù)組n形成鏈表 {

n[i].next=&n[i+1];

//n[i]的next指針指向下一個(gè)結(jié)構(gòu)n[i+1] } n[7].next=null; //鏈表尾部指向空

p=head; //p指向鏈表頭部head

i=1; //i賦值為1

do //直到型循環(huán)，用于輸出鏈表內(nèi)容 { //循環(huán)體開(kāi)始 //輸出結(jié)點(diǎn)內(nèi)容 printf("結(jié)點(diǎn)%d:x=%d,y=%d\n",i,p->x,p->y); p=p->next; //p指向相鄰的下一個(gè)結(jié)點(diǎn) i=i+1; //計(jì)數(shù)i加1 }while(p!=null);

//未到鏈表尾部，則繼續(xù)循環(huán)} //主函數(shù)結(jié)束73精選ppt課件下面的程序與上面的程序區(qū)別僅在

scanf(“%d”,&(n[i].x));去替換

scanf(“%d”,&a); n[i].x=a;//結(jié)構(gòu)3.c#include<stdio.h> //預(yù)編譯命令#definenull0 //定義空指針常量structTM //定義TM結(jié)構(gòu){ intx,y; //整型變量x,y structTM*next;

//指向TM結(jié)構(gòu)的指針};74精選ppt課件voidmain() //主函數(shù){ //主函數(shù)開(kāi)始inti,a,b;

//聲明整型變量i,a,b

//聲明TM型結(jié)構(gòu)數(shù)組n[8]，TM結(jié)構(gòu)指針head,pstructTMn[8],*head,*p;for(i=1;i<=7;i=i+1) //循環(huán) { //循環(huán)體開(kāi)始 printf("輸入n[%d]的x\n",i); //提示輸入第i個(gè)結(jié)構(gòu)的x值 scanf("%d",&(n[i].x)); //輸入n[i].x

printf("輸入n[%d]的y\n",i); //提示輸入第i個(gè)結(jié)構(gòu)的y值 scanf("%d",&(n[i].y)); //輸入n[i].y } //循環(huán)體結(jié)束75精選ppt課件 head=&n[1]; //鏈表頭部指向n[1] for(i=1;i<=6;i=i+1) //循環(huán) { //循環(huán)體開(kāi)始

n[i].next=&n[i+1]; //n[i].next指向n[i+1] } //循環(huán)體結(jié)束

n[7].next=null; //鏈表尾部賦值為空指針

p=head; //p指向鏈表頭部head

i=1; //i賦值為1

do //直到型循環(huán) { //循環(huán)體開(kāi)始 //提示輸入結(jié)點(diǎn)信息

printf("結(jié)點(diǎn)%d:x=%d,y=%d\n",i,(*p).x,(*p).y);

p=(*p).next; //p指向相鄰的下一個(gè)結(jié)點(diǎn)

i=i+1; //i加1 }while(p!=null);

//未到達(dá)鏈表尾部，則繼續(xù)循環(huán)} //主函數(shù)結(jié)束76精選ppt課件任務(wù)

我們要作一張登記表，登記排隊(duì)求職信息，包括：姓名、年齡、性別、電話四個(gè)參數(shù)。希望便于管理，即可以插入和刪除，這時(shí)可用隊(duì)列，采用結(jié)構(gòu)類(lèi)型變量。

structST { charname[20]; //字符串，姓名

intage; //整數(shù)，年齡

charsex; //字符，性別

longnum; //電話號(hào)碼

structST*next; //ST結(jié)構(gòu)的指針

}; //注意，這里必須有分號(hào)77精選ppt課件循環(huán)鏈表78精選ppt課件循環(huán)鏈表例：猴子選大王。

n只猴子圍成一圈，順時(shí)針?lè)较驈?到n編號(hào)。之后從1號(hào)開(kāi)始沿順時(shí)針?lè)较蜃尯镒訌?，2，…，m依次報(bào)數(shù)，凡報(bào)到m的猴子，都讓其出圈，取消候選資格。然后不停地按順時(shí)針?lè)较蛑鹨蛔寛?bào)出m者出圈，最后剩下一個(gè)就是猴王。79精選ppt課件起始位置猴王123456783615284猴子被淘汰的順序演示：n=8,m=380精選ppt課件說(shuō)明： 如圖1所示有8只猴子圍成一圈，m=3。從1#猴的位置開(kāi)始，順時(shí)針1至3報(bào)數(shù)，第一個(gè)出圈的是3#；第二個(gè)出圈的是6#，第3個(gè)出圈的是1#；第4個(gè)出圈的是5#；第5個(gè)是2#，第6個(gè)是8#；第7個(gè)是4#。最后剩下一個(gè)是7#，它就是猴王。我們用循環(huán)鏈表來(lái)模擬這個(gè)選擇過(guò)程。81精選ppt課件1、定義一個(gè)名為mon的結(jié)構(gòu)

structmon

{

intnum; //整數(shù)，表示猴子的編號(hào)

structmon*next; //指針，指向相鄰的下一只猴子

}2、將鏈表的頭指針head定義為全局變量。

structmon*head;3、主函數(shù)

用鍵盤(pán)輸入猴子數(shù)n，輸入數(shù)m，調(diào)用函數(shù)create建立一個(gè)循環(huán)鏈表，模擬眾猴圍成一圈的情況。該函數(shù)的實(shí)參為n。調(diào)用函數(shù)select，模擬1至m報(bào)數(shù)，讓n-1只猴子逐一出列的過(guò)程。即在具有n個(gè)結(jié)點(diǎn)的循環(huán)鏈表按報(bào)數(shù)m刪除結(jié)點(diǎn)的過(guò)程。該函數(shù)的實(shí)參為m，最后輸出猴王的編號(hào)。82精選ppt課件4、建立循環(huán)鏈表的函數(shù)create(intnn)

其中nn為形式參數(shù)。要從編號(hào)1到編號(hào)nn。思路是（1）先做第1個(gè)結(jié)點(diǎn)，讓其中的數(shù)據(jù)域p->num賦值為1，讓指針域賦值為null。之后讓鏈頭指針head指向第1個(gè)結(jié)點(diǎn)。利用指針q記住這個(gè)結(jié)點(diǎn)，以便讓指針p去生成下面的結(jié)點(diǎn)。（2）利用一個(gè)計(jì)數(shù)循環(huán)結(jié)構(gòu)，做出第2個(gè)結(jié)點(diǎn)到第nn個(gè)結(jié)點(diǎn)。并將相鄰結(jié)點(diǎn)一個(gè)接一個(gè)鏈接到一起。（3）最后一個(gè)結(jié)點(diǎn)要和頭結(jié)點(diǎn)用下一語(yǔ)句鏈接到一起

tail=q;tail->next=head;headtailq83精選ppt課件5、刪結(jié)點(diǎn)的函數(shù)select(intmm)

mm為形式參數(shù)，從1至m報(bào)數(shù)，凡報(bào)到mm者刪除其所在的結(jié)點(diǎn)。

設(shè)計(jì)兩個(gè)指針p和q。一開(kāi)始讓q指向鏈表的尾部q=tail。讓p指向q的下一個(gè)結(jié)點(diǎn)。開(kāi)始時(shí)讓p指向1#猴所在的結(jié)點(diǎn)。用一個(gè)累加器x，初始時(shí)x=0，從1#猴所在結(jié)點(diǎn)開(kāi)始讓x=x+1=1，如果mm是1的話，1#猴所在的p結(jié)點(diǎn)就要被刪除。有三條語(yǔ)句

printf(“被刪掉的猴子號(hào)為%d號(hào)\n”,p->num);

q->next=p->next;

free(p);1head28tailqp演示84精選ppt課件這里free(p)是釋放p結(jié)點(diǎn)所占用的內(nèi)存空間的語(yǔ)句。如果mm不是1而是3