C語言鏈表詳解

會計學1C語言鏈表詳解2例：跳馬。依下圖將每一步跳馬之后的位置(x,y)放到一個“結點”里，再用“鏈子穿起來”，形成一條鏈，相鄰兩結點間用一個指針將兩者連到一起。結構的概念與應用第1頁/共91頁3依上圖有7個結點(x1,y1)(x2,y2)(x6,y6)(x7,y7)為了表示這種既有數(shù)據(jù)又有指針的情況，引入結構這種數(shù)據(jù)類型。第2頁/共91頁411.7用指針處理鏈表鏈表是程序設計中一種重要的動態(tài)數(shù)據(jù)結構，它是動態(tài)地進行存儲分配的一種結構。動態(tài)性體現(xiàn)為：鏈表中的元素個數(shù)可以根據(jù)需要增加和減少，不像數(shù)組，在聲明之后就固定不變；元素的位置可以變化，即可以從某個位置刪除，然后再插入到一個新的地方；第3頁/共91頁51249A1356B1475C1021DNull1、鏈表中的元素稱為“結點”，每個結點包括兩個域：數(shù)據(jù)域和指針域；2、單向鏈表通常由一個頭指針（head)，用于指向鏈表頭；3、單向鏈表有一個尾結點，該結點的指針部分指向一個空結點(NULL)。Head1249135614751021結點里的指針是存放下一個結點的地址第4頁/共91頁6鏈表中結點的定義鏈表是由結點構成的，關鍵是定義結點;鏈表的結點定義打破了先定義再使用的限制,即可以用自己定義自己；遞歸函數(shù)的定義也違反了先定義再使用；這是C語言程序設計上的兩大特例第5頁/共91頁7

鏈表的基本操作對鏈表的基本操作有：（1）創(chuàng)建鏈表是指，從無到有地建立起一個鏈表，即往空鏈表中依次插入若干結點，并保持結點之間的前驅(qū)和后繼關系。（2）檢索操作是指，按給定的結點索引號或檢索條件，查找某個結點。如果找到指定的結點，則稱為檢索成功；否則，稱為檢索失敗。（3）插入操作是指，在結點ki-1與ki之間插入一個新的結點k’，使線性表的長度增1，且ki-1與ki的邏輯關系發(fā)生如下變化：插入前，ki-1是ki的前驅(qū)，ki是ki-1的后繼；插入后，新插入的結點k’成為ki-1的后繼、ki的前驅(qū).第6頁/共91頁8（4）刪除操作是指，刪除結點ki，使線性表的長度減1，且ki-1、ki和ki+1之間的邏輯關系發(fā)生如下變化：刪除前，ki是ki+1的前驅(qū)、ki-1的后繼；刪除后，ki-1成為ki+1的前驅(qū)，ki+1成為ki-1的后繼.(5)打印輸出第7頁/共91頁9一個指針類型的成員既可指向其它類型的結構體數(shù)據(jù)，也可以指向自己所在的結構體類型的數(shù)據(jù)9910189.599103909910785numScorenextnext是structstudent類型中的一個成員，它又指向structstudent類型的數(shù)據(jù)。換名話說：next存放下一個結點的地址第8頁/共91頁1011.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建立和輸出一個簡單鏈表各結點在程序中定義，不是臨時開辟的，始終占有內(nèi)容不放，這種鏈表稱為“靜態(tài)鏈表”第9頁/共91頁1111.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í)行失?。悍祷豊ULL第10頁/共91頁12函數(shù)原形:void*calloc(unsignedn,unsignedsize);作用：在內(nèi)存動態(tài)區(qū)中分配n個

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

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

函數(shù)第11頁/共91頁133.free函數(shù)函數(shù)原形：

voidfree(void*p);作用：釋放由p指向的內(nèi)存區(qū)。P:是最近一次調(diào)用calloc或malloc函數(shù)時返回的值。free函數(shù)無返回值動態(tài)分配的存儲單元在用完后一定要釋放，否則內(nèi)存會因申請空間過多引起資源不足而出現(xiàn)故障。第12頁/共91頁14結點的動態(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）第13頁/共91頁1511.7.4建立動態(tài)鏈表基本方法:三個結點（頭結點head、尾結點NULL和待插入結點P）第一步：定義頭結點head、尾結點

p2

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

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

P2->next=P1;P2=P1;

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

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

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

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

P=NULL第22頁/共91頁24圖11.18headp

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

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

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

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

p0

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

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

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

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

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

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

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

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

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

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

}

else //鏈表不為空 {

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

//將p結點插到鏈表頭部

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

*phead=p;

//將鏈表頭賦值為p

return;

//返回 }第44頁/共91頁46

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

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

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

r=r->next; //取鏈表中相鄰的下一個結點 } //循環(huán)體結束} 第46頁/共91頁48voidmain() //主函數(shù)開始{

//函數(shù)體開始 structnumST*head,*p; //ST型結構指針 head=null; //分配兩個ST結構的內(nèi)存空間，用于構造鏈表 head=(structnumST*)malloc(LEN); head->next=(structnumST*)malloc(LEN); //為鏈表中的兩個結點中的num賦值為5和10 head->num=5; head->next->num=10; head->next->next=null; //鏈表尾賦值為空 //構造一個結點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ù)結束第47頁/共91頁49說明：函數(shù)insert()的第一個形參為structnumST**類型，即“指針的指針”。調(diào)用時送入的實參是鏈表頭指針的地址，即程序中的&head。這樣對head的修改才會在函數(shù)返回后仍有效。如果形參為structnumST*，則傳入的為指針，當函數(shù)返回后，head無法改變。第48頁/共91頁5011.8共用體

構造類型之二——聯(lián)合在同一存儲單元里，根據(jù)需要放不同類型的數(shù)據(jù)，使用覆蓋技術。第49頁/共91頁5111.8.1概念單元起始地址：1000。三個變量（數(shù)據(jù)）占用同一單元：1000——1003浮點型（4byte）字符型（1byte）整型（2Byte）第50頁/共91頁52共用體變量的定義格式（一般形式）：

union聯(lián)合類型名

{成員列表

}變量列表；11.8.2共用體變量的引用方式同結構類型變量的引用格式：變量名.成員名第51頁/共91頁53格式與結構類型的定義和變量聲明形式上類似，但實質(zhì)上有區(qū)別：

結構類型的長度=各成員的長度和；各成員占獨立的存儲單元，不共享；聯(lián)合類型的長度為成員中長度的最大者，各成員共享長度最大的存儲單元；第52頁/共91頁5411.8.3共用體類型數(shù)據(jù)的特點雖然同一內(nèi)存單元內(nèi)可以存放不同類型（同一地址）、不同長度的數(shù)據(jù)，但任一時刻，只有一種類型數(shù)據(jù)（最后賦值的）起作用；其它的都沒有意義；不能對共用體變量整體賦值，也不能對其初始化。共用變量不可作為函數(shù)的參數(shù)，但可以通過指針指向；共用體類型可以和結構類型/數(shù)組類型互為基類型；p289第53頁/共91頁55例題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);第54頁/共91頁56if(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("sexjobclass/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ù)第55頁/共91頁57

枚舉類型

----構造類型之三第56頁/共91頁5811.9枚舉類型枚舉類型是指能將類型所包含的值一一列舉出來。枚舉值稱為枚舉常量定義枚舉類型的關鍵字是enum。其類型的定義以及變量的聲明同結構類型和聯(lián)合類型；聲明格式：enumweekday(sum,mon,tue,wed,thu,fri,sat);定義變量：enumweekdayworkday,week_end;第57頁/共91頁59關于枚舉類型變量在C編譯中，對枚舉元素按常量處理；對枚舉型變量的賦值（枚舉型變量的取值）只能取該變量所屬枚舉類型的枚舉常量值；一個整數(shù)不能直接賦給一個枚舉變量。進行強制性轉換；第58頁/共91頁60

說明（1）枚舉型僅適應于取值有限的數(shù)據(jù)。例如，根據(jù)現(xiàn)行的歷法規(guī)定，１周７天，１年１２個月。（2）取值表中的值稱為枚舉元素，其含義由程序解釋。例如，不是因為寫成“Sun”就自動代表“星期天”。事實上，枚舉元素用什么表示都可以。（3）枚舉元素作為常量是有值的──定義時的順序號（從０開始），所以枚舉元素可以進行比較，比較規(guī)則是：序號大者為大！例如，上例中的Sun=0、Mon=1、……、Sat=6，所以Mon>Sun、Sat最大。（4）枚舉元素的值也是可以人為改變的：在定義時由程序指定。例如，如果enumweekdays{Sun=７,Mon＝１,Tue,Wed,Thu,Fri,Sat}；則Sun=７，Mon=１，從Tue=2開始，依次增１。第59頁/共91頁61例題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);}第60頁/共91頁62續(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);}}第61頁/共91頁6311.10用typedef為類型定義新名字

除可直接使用Ｃ提供的標準類型和自定義的類型（結構、共用、枚舉）外，也可使用typedef定義已有類型的別名。該別名與標準類型名一樣，可用來定義相應的變量。定義已有類型別名的方法如下：

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

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

（3）在定義體最前面加上typedef。第62頁/共91頁6411.10用typeded為類型定義新名字任何已有的類型可以重新命名typedeflonginteger;

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

structTM＊

next//結構TM的成員，屬TM型}下面的表是馬的跳步方案，從左下角跳到右上角結點n1n2n3n4n5n6n7xy00122443647284結構體與共體例子第65頁/共91頁6784NULLNULL為空地址下面是形成鏈表的一個參考程序24&n412&n300&n2&n1head第66頁/共91頁68//結構1.c#include<stdio.h> //預編譯命令#definenull0 //定義空指針常量structTM //定義結構TM{ intx,y; //整型變量x,y structTM＊next; //指向TM結構的指針};voidmain() //主函數(shù){ //主函數(shù)開始

inti; //聲明整型變量

//聲明TM結構n1~n7,結構指針head,pstructTMn1,n2,n3,n4,n5,n6,n7,＊head,＊p;第67頁/共91頁69//分別對TM結構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構成鏈表

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

n7.next=null;第68頁/共91頁70

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

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

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

//輸出結點信息

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

i=i+1; //計數(shù)加1 }while(p!=null); //未到達鏈表尾部，則繼續(xù)循環(huán)} //主函數(shù)結束第69頁/共91頁71用結構數(shù)組，利用鍵盤輸入結點中的數(shù)據(jù)。重點看

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

//指向TM結構的指針};第70頁/共91頁72voidmain() //主函數(shù){ //主函數(shù)開始inti,a,b;

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

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

//將a的值賦給結構n[i]的元素x

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

//將b的值賦給結構n[i]的元素y }

//循環(huán)體結束第71頁/共91頁73 head=&n[1]; //鏈表頭部指向n[1] for(i=1;i<=6;i=i+1) //將結構數(shù)組n形成鏈表 {

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

//n[i]的next指針指向下一個結構n[i+1] } n[7].next=null; //鏈表尾部指向空

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

i=1; //i賦值為1

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

//未到鏈表尾部，則繼續(xù)循環(huán)} //主函數(shù)結束第72頁/共91頁74下面的程序與上面的程序區(qū)別僅在

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

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

//指向TM結構的指針};第73頁/共91頁75voidmain() //主函數(shù){ //主函數(shù)開始inti,a,b;

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

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

printf("輸入n[%d]的y\n",i); //提示輸入第i個結構的y值 scanf("%d",&(n[i].y)); //輸入n[i].y } //循環(huán)體結束第74頁/共91頁76 head=&n[1]; //鏈表頭部指向n[1] for(i=1;i<=6;i=i+1) //循環(huán) { //循環(huán)體開始

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

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

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

i=1; //i賦值為1

do //直到型循環(huán) { //循環(huán)體開始 //提示輸入結點信息

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

p=(*p).next; //p指向相鄰的下一個結點

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

//未到達鏈表尾部，則繼續(xù)循環(huán)} //主函數(shù)結束第75頁/共91頁77任務

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

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

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

charsex; //字符，性別

longnum; //電話號碼

structST*next; //ST結構的指針

}; //注意，這里必須有分號第76頁/共91頁78循環(huán)鏈表第77頁/共91頁79循環(huán)鏈表例：猴子選大王。

n只猴子圍成一圈，順時針方向從1到n編號。之后從1號開始沿順時針方向讓猴子從1，2，…，m依次報數(shù)，凡報到m的猴子，都讓其出圈，取消候選資格。然后不停地按順時針方向逐一讓報出m者出圈，最后剩下一個就是猴王。第78頁/共91頁80起始位置猴王123456783615284猴子被淘汰的順序演示：n=8,m=3第79頁/共91頁81說明： 如圖1所示有8只猴子圍成一圈，m=3。從1#猴的位置開始，順時針1至3報數(shù)，第一個出圈的是3#；第二個出圈的是6#，第3個出圈的是1#；第4個出圈的是5#；第5個是2#，第6個是8#；第7個是4#。最后剩下一個是7#，它就是猴王。我們用循環(huán)鏈表來模擬這個選擇過程。第80頁/共91頁821、定義一個名為mon的結構

structmon

{

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

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

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

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

用鍵盤輸入猴子數(shù)n，輸入數(shù)m，調(diào)用函數(shù)create建立一個循環(huán)鏈表，模擬眾猴圍成一圈的情況。該函數(shù)的實參為n。調(diào)用函數(shù)select，模擬1至m報數(shù)，讓n-1只猴子逐一出列的過程。即在具有n個結點的循環(huán)鏈表按報數(shù)m刪除結點的過程。該函數(shù)的實參為m，最后輸出猴王的編號。第81頁/共91頁834、建立循環(huán)鏈表的函數(shù)create(intnn)

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

tail=q;tail->next=head;headtailq第82頁/共91頁845、刪結點的函數(shù)select(intmm)

mm為形式參數(shù)，從1至m報數(shù)，凡報到mm者刪除其所在的結點。

設計兩個指針p和q。一開始讓q指向鏈表的尾部q=tail。讓p指向q的下一個結點。開始時讓p指向1#猴所在的結點。用一個累加器x，初始時x=0，從1#猴所在結點開始讓x=x+1=1，如果mm是1的話，1#猴所在的p結點就要被刪除。有三條語句

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

q->next=p->next;

free(p);1head28tailqp演示第83頁/共91頁85這里free(p)是釋放p結點所占用的內(nèi)存空間的語句。如果mm不是1