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

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

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

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

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

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

函數(shù)12精選ppt課件3.free函數(shù)函數(shù)原形：

voidfree(void*p);作用：釋放由p指向的內存區(qū)。P:是最近一次調用calloc或malloc函數(shù)時返回的值。free函數(shù)無返回值動態(tài)分配的存儲單元在用完后一定要釋放，否則內存會因申請空間過多引起資源不足而出現(xiàn)故障。13精選ppt課件結點的動態(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）14精選ppt課件11.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;15精選ppt課件11.7.4建立動態(tài)鏈表9910189.5headP1p21.任務是開辟結點和輸入數(shù)據(jù)2.并建立前后相鏈的關系待插入的結點p1數(shù)據(jù)部分初始化,該結點被頭結點head、尾結點p2同時指向.16精選ppt課件圖11.149910189.5headp29910390p19910189.5headp29910390p1(a)(b)p1重復申請待插入結點空間，對該結點的數(shù)據(jù)部分賦值（或輸入值）P2->next指向p1新開辟的結點。17精選ppt課件圖11.14head9910189.5p1p29910390(c)P2指向新結點p2=p118精選ppt課件圖11.159910189.59910189.5p29910785p1head9910189.59910189.5p29910785p1head(a)(b)19精選ppt課件

圖11.16 99103909910785p200p1head9910189.599103909910785NULLp200p1head9910189.520精選ppt課件例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的內存區(qū)P1,p2是指向結構體類型數(shù)據(jù)的指針變量，強行轉換成結構體類型假設頭指向空結點21精選ppt課件續(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ù)開辟新結點給新結點賦值此22精選ppt課件11.7.5輸出鏈表鏈表遍歷1.單向鏈表總是從頭結點開始的；2.每訪問一個結點，就將當前指針向該結點的下一個結點移動：

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

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

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

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

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

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

插入到鏈表中正確的位置。 參見下面的圖示40精選ppt課件6head81213nullp15gr說明：這種情況下，p結點已經(jīng)與鏈表的第一個結點比較過了，所以從鏈表的下一個結點開始比較。13>8，繼續(xù)比較。41精選ppt課件6head81213nullp15gr說明：13>12，繼續(xù)比較。42精選ppt課件6head81213p15grnull說明：13<15，找到了正確的插入位置，則插入結點p;語句為：r>next=p;p->next=g;43精選ppt課件//結構7.c#include<stdio.h> //預編譯命令#include<malloc.h> //內存空間分配#definenull0 //定義空指針常量#defineLENsizeof(structnumST) //定義常量，表示結構長度structnumST //結構聲明{ intnum; //整型數(shù) structnumST*next; //numST結構指針};參考程序44精選ppt課件//被調用函數(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;

//返回 }45精選ppt課件

//第三種情況，循環(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; }}46精選ppt課件//被調用函數(shù)，形參為ST結構指針，用于輸出鏈表內容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)體結束} 47精選ppt課件voidmain() //主函數(shù)開始{

//函數(shù)體開始 structnumST*head,*p; //ST型結構指針 head=null; //分配兩個ST結構的內存空間，用于構造鏈表 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);

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

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

union聯(lián)合類型名

{成員列表

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

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

枚舉類型

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

說明（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開始，依次增１。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為類型定義新名字

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

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

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

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

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

structTM＊

next//結構TM的成員，屬TM型}下面的表是馬的跳步方案，從左下角跳到右上角結點n1n2n3n4n5n6n7xy00122443647284結構體與共體例子66精選ppt課件84NULLNULL為空地址下面是形成鏈表的一個參考程序24&n412&n300&n2&n1head67精選ppt課件//結構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;68精選ppt課件//分別對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;69精選ppt課件

p=head; //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; //計數(shù)加1 }while(p!=null); //未到達鏈表尾部，則繼續(xù)循環(huán)} //主函數(shù)結束70精選ppt課件用結構數(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結構的指針};71精選ppt課件voidmain() //主函數(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)體結束72精選ppt課件 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)，用于輸出鏈表內容 { //循環(huán)體開始 //輸出結點內容 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ù)結束73精選ppt課件下面的程序與上面的程序區(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結構的指針};74精選ppt課件voidmain() //主函數(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)體結束75精選ppt課件 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ù)結束76精選ppt課件任務

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

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

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

charsex; //字符，性別

longnum; //電話號碼

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

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

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

structmon

{

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

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

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

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

用鍵盤輸入猴子數(shù)n，輸入數(shù)m，調用函數(shù)create建立一個循環(huán)鏈表，模擬眾猴圍成一圈的情況。該函數(shù)的實參為n。調用函數(shù)select，模擬1至m報數(shù)，讓n-1只猴子逐一出列的過程。即在具有n個結點的循環(huán)鏈表按報數(shù)m刪除結點的過程。該函數(shù)的實參為m，最后輸出猴王的編號。82精選ppt課件4、建立循環(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;headtailq83精選ppt課件5、刪結點的函數(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演示84精選ppt課件這里free(p)是釋放p結點所占用的內存空間的語句。如果mm不是1而是3