西工大姜學(xué)峰C語言課件課件

1、封面2鏈表鏈表概述簡單鏈表建立鏈表輸出鏈表鏈表操作3鏈表概述v 鏈表概述鏈表是一種常見的重要的數(shù)據(jù)結(jié)構(gòu),是動(dòng)態(tài)地進(jìn)行存儲(chǔ)分配的一種結(jié)構(gòu)。鏈表的組成：頭指針：存放一個(gè)地址，該地址指向一個(gè)元素 結(jié)點(diǎn)：用戶需要的實(shí)際數(shù)據(jù)和鏈接節(jié)點(diǎn)的指針4鏈表概述v圖11-1011-105鏈表概述v用結(jié)構(gòu)體建立鏈表struct studentint num；float score；struct student *next ；;其中成員num和score用來存放結(jié)點(diǎn)中的有用數(shù)據(jù)（用戶需要用到的數(shù)據(jù)），next是指針類型的成員，它指向struct student類型數(shù)據(jù)（這就是next所在的結(jié)構(gòu)體類型）6鏈表概述v圖11

2、-1111-117鏈表鏈表概述簡單鏈表建立鏈表輸出鏈表鏈表操作8簡單鏈表v 例11.7 11.7 簡單鏈表#include #define NULL 0struct student long num;float score;struct student *next;接下頁SX11-79簡單鏈表int main()struct student a,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

3、;c.next=NULL;p=head;續(xù)上頁接下頁SX11-710簡單鏈表do printf(%ld %5.1fn,p-num,p-score); p=p-next; while(p!=NULL);return 0;續(xù)上頁SX11-711簡單鏈表(1)開始時(shí)使head指向a結(jié)點(diǎn)，a.next指向b結(jié)點(diǎn)，b.next指向c結(jié)點(diǎn)，這就構(gòu)成鏈表關(guān)系。(2)“c.next=NULL”的作用是使c.next不指向任何有用的存儲(chǔ)單元。(3)在輸出鏈表時(shí)要借助p，先使p指向a結(jié)點(diǎn)，然后輸出a結(jié)點(diǎn)中的數(shù)據(jù)，“p=p-next” 是為輸出下一個(gè)結(jié)點(diǎn)作準(zhǔn)備。p-next的值是b結(jié)點(diǎn)的地址，因此執(zhí)行“p=p-ne

4、xt”后p就指向b結(jié)點(diǎn)，所以在下一次循環(huán)時(shí)輸出的是b結(jié)點(diǎn)中的數(shù)據(jù)。12鏈表鏈表概述簡單鏈表建立鏈表輸出鏈表鏈表操作13建立鏈表v 處理動(dòng)態(tài)鏈表所需的函數(shù)malloc函數(shù)函數(shù)原型為void *malloc(unsigned int size);其作用是在內(nèi)存的動(dòng)態(tài)存儲(chǔ)區(qū)中分配一個(gè)長度為size的連續(xù)空間。此函數(shù)的值（即“返回值”）是一個(gè)指向分配域起始地址的指針（類型為void）。如果此函數(shù)未能成功地執(zhí)行（例如內(nèi)存空間不足），則返回空指針(NULL)。 14建立鏈表v 處理動(dòng)態(tài)鏈表所需的函數(shù)calloc函數(shù)函數(shù)原型為void *calloc(unsigned n，unsigned size);其作

5、用是在內(nèi)存的動(dòng)態(tài)存儲(chǔ)區(qū)中分配個(gè)長度為size的連續(xù)空間。函數(shù)返回一個(gè)指向分配域起始地址的指針；如果分配不成功，返回NULL。用calloc函數(shù)可以為一維數(shù)組開辟動(dòng)態(tài)存儲(chǔ)空間，n為數(shù)組元素個(gè)數(shù)，每個(gè)元素長度為Size。15建立鏈表v 處理動(dòng)態(tài)鏈表所需的函數(shù)free函數(shù)函數(shù)原型為void free(void *p);其作用是釋放由指向的內(nèi)存區(qū)，使這部分內(nèi)存區(qū)能被其他變量使用。是最近一次調(diào)用calloc或malloc函數(shù)時(shí)返回的值。free函數(shù)無返回值。16建立鏈表v 建立動(dòng)態(tài)鏈表建立動(dòng)態(tài)鏈表是指在程序執(zhí)行過程中從無到有地建立起一個(gè)鏈表，即一個(gè)一個(gè)地開辟結(jié)點(diǎn)和輸入各結(jié)點(diǎn)數(shù)據(jù)，并建立起前后相鏈的關(guān)系。

6、17建立鏈表例11.5 寫一函數(shù)建立一個(gè)有3名學(xué)生數(shù)據(jù)的單向動(dòng)態(tài)鏈表。算法的實(shí)現(xiàn)：開辟一個(gè)結(jié)點(diǎn)并使p1指向它，并輸入該結(jié)點(diǎn)的數(shù)據(jù)。v如果輸入的如果輸入的p1-nump1-num，則應(yīng)鏈入第個(gè)結(jié)點(diǎn)，則應(yīng)鏈入第個(gè)結(jié)點(diǎn)v（n=2), n=2), 將新結(jié)點(diǎn)的地址賦給第一個(gè)結(jié)點(diǎn)的將新結(jié)點(diǎn)的地址賦給第一個(gè)結(jié)點(diǎn)的vnextnext成員成員. .v接著使，也就是使指向剛才建接著使，也就是使指向剛才建v立的結(jié)點(diǎn)立的結(jié)點(diǎn)v圖11-1411-1418建立鏈表再開辟一個(gè)結(jié)點(diǎn)并使p1指向它，并輸入該結(jié)點(diǎn)的數(shù)據(jù)。v在第三次循環(huán)中，由于（在第三次循環(huán)中，由于（），又），又v將的值賦給將的值賦給-，也就是將第，也就是將第v個(gè)

7、結(jié)點(diǎn)連接到第個(gè)結(jié)點(diǎn)之后，并使個(gè)結(jié)點(diǎn)連接到第個(gè)結(jié)點(diǎn)之后，并使v，使指向最后一個(gè)結(jié)點(diǎn)，使指向最后一個(gè)結(jié)點(diǎn). .v圖11-1511-1519建立鏈表再開辟一個(gè)新結(jié)點(diǎn)，并使p1指向它，輸入該結(jié)點(diǎn)的數(shù)據(jù)。由于p1-num的值為，不再執(zhí)行循環(huán)，此新結(jié)點(diǎn)不應(yīng)被連接到鏈表中v將將NULLNULL賦給賦給p2-next.p2-next.v建立鏈表過程至此結(jié)束，建立鏈表過程至此結(jié)束，p1p1最后所指的結(jié)點(diǎn)最后所指的結(jié)點(diǎn)v未鏈入鏈表中，第三個(gè)結(jié)點(diǎn)的未鏈入鏈表中，第三個(gè)結(jié)點(diǎn)的nextnext成員的值成員的值v為為NULLNULL，它不指向任何結(jié)點(diǎn)。，它不指向任何結(jié)點(diǎn)。v圖11-1611-1620建立鏈表建立鏈表的函數(shù)

8、如下建立鏈表的函數(shù)如下: #include #include #define NULL 0 /令令NULL代表，用它表示代表，用它表示“空地址空地址#define LEN sizeof(struct student) /令令LEN代表代表struct /student類型數(shù)據(jù)的長度類型數(shù)據(jù)的長度struct student long num; float score; struct student *next;int n; /n為全局變量，本文件模塊中各函數(shù)均可使用它為全局變量，本文件模塊中各函數(shù)均可使用它21建立鏈表struct student *creat()struct student

9、*head; struct student *p1,*p2; n=0;p1=p2=( struct student*) malloc(LEN);scanf(%ld,%f,&p1-num,&p1-score);head=NULL;while(p1-num!=0) n=n+1;if(n=1)head=p1; else p2-next=p1;p2=p1;p1=(struct student*)malloc(LEN);22建立鏈表scanf(%ld,%f,&p1-num,&p1-score);p2-next=NULL;return(head);23鏈表鏈表概述簡單鏈表建

10、立鏈表輸出鏈表鏈表操作24輸出鏈表v 輸出鏈表首先要知道鏈表第一個(gè)結(jié)點(diǎn)的地址，也就是要知道head的值。然后設(shè)一個(gè)指針變量p,先指向第一個(gè)結(jié)點(diǎn)，輸出所指的結(jié)點(diǎn)，然后使后移一個(gè)結(jié)點(diǎn)，再輸出，直到鏈表的尾結(jié)點(diǎn)。 v圖11-17,11-1811-17,11-1825輸出鏈表void print(struct student *head)struct student *p;printf(nNow,These %d records are:n,n);p=head;if(head!=NULL)do printf(%ld %5.1fn,p-num,p-score);p=p-next; while(p!=NU

11、LL);26鏈表鏈表概述簡單鏈表建立鏈表輸出鏈表鏈表操作27鏈表刪除操作v 對(duì)鏈表的刪除操作從一個(gè)動(dòng)態(tài)鏈表中刪去一個(gè)結(jié)點(diǎn)，并不是真正從內(nèi)存中把它抹掉，而是把它從鏈表中分離開來，只要撤銷原來的鏈接關(guān)系即可。v圖11-1911-1928鏈表刪除操作例11.10寫一函數(shù)以刪除動(dòng)態(tài)鏈表中指定的結(jié)點(diǎn)。算法的實(shí)現(xiàn)：從p指向的第一個(gè)結(jié)點(diǎn)開始，檢查該結(jié)點(diǎn)中的num值是否等于輸入的要求刪除的那個(gè)學(xué)號(hào)。如果相等就將該結(jié)點(diǎn)刪除，如不相等，就將p后移一個(gè)結(jié)點(diǎn)，再如此進(jìn)行下去，直到遇到表尾為止。29鏈表刪除操作可以設(shè)兩個(gè)指針變量p1和p2，先使p1指向第一個(gè)結(jié)點(diǎn) 。如果要?jiǎng)h除的不是第一個(gè)結(jié)點(diǎn)，則使p1后移指向下一個(gè)結(jié)點(diǎn)

12、(將p1-next賦給p1)，在此之前應(yīng)將p1的值賦給p2 ，使p2指向剛才檢查過的那個(gè)結(jié)點(diǎn) 。30鏈表刪除操作v 圖圖11-2011-20v 31鏈表刪除操作要?jiǎng)h的是第一個(gè)結(jié)點(diǎn)（的值等于的值，如圖1-0（）那樣），則應(yīng)將-賦給。這時(shí)指向原來的第二個(gè)結(jié)點(diǎn)。第一個(gè)結(jié)點(diǎn)雖然仍存在，但它已與鏈表脫離，因?yàn)殒湵碇袥]有一個(gè)結(jié)點(diǎn)或頭指針指向它。雖然還指向它，它仍指向第二個(gè)結(jié)點(diǎn)，但仍無濟(jì)于事，現(xiàn)在鏈表的第一個(gè)結(jié)點(diǎn)是原來的第二個(gè)結(jié)點(diǎn)，原來第一個(gè)結(jié)點(diǎn)已“丟失” ，即不再是鏈表中的一部分了。32鏈表刪除操作如果要?jiǎng)h除的不是第一個(gè)結(jié)點(diǎn)，則將-賦給-，見圖10（）。-原來指向指向的結(jié)點(diǎn)（圖中第二個(gè)結(jié)點(diǎn)），現(xiàn)在-改為指

13、向-所指向的結(jié)點(diǎn)（圖中第三個(gè)結(jié)點(diǎn)）。所指向的結(jié)點(diǎn)不再是鏈表的一部分。還需要考慮鏈表是空表（無結(jié)點(diǎn)）和鏈表中找不到要?jiǎng)h除的結(jié)點(diǎn)的情況。33鏈表刪除操作刪除結(jié)點(diǎn)的函數(shù)刪除結(jié)點(diǎn)的函數(shù)del:struct student *del(struct student *head,long num) struct student *p1,*p2;if (head=NULL)printf(nlist null!n);goto end;p1=head;while(num!=p1-num & p1-next!=NULL) p2=p1;p1=p1-next;34鏈表刪除操作if(num=p1-num) if(

14、p1=head) head=p1-next; else p2-next=p1-next; printf(delete:%ldn,num); n=n-1;else printf(%ld not been found!n,num);end:return(head); 35鏈表插入操作v 對(duì)鏈表的插入操作對(duì)鏈表的插入是指將一個(gè)結(jié)點(diǎn)插入到一個(gè)已有的鏈表中。為了能做到正確插入，必須解決兩個(gè)問題： 怎樣找到插入的位置； 怎樣實(shí)現(xiàn)插入。36鏈表插入操作先用指針變量p0指向待插入的結(jié)點(diǎn)，p1指向第一個(gè)結(jié)點(diǎn)。將p0-num與p1-num相比較，如果p0-nump1- num ，則待插入的結(jié)點(diǎn)不應(yīng)插在p1所指的結(jié)

15、點(diǎn)之前。此時(shí)將p1后移，并使p2指向剛才p1所指的結(jié)點(diǎn)。37鏈表插入操作再將p1-num與p0-num比,如果仍然是p0-num大，則應(yīng)使p1繼續(xù)后移，直到p0-p1- num為止。這時(shí)將p0所指的結(jié)點(diǎn)插到p1所指結(jié)點(diǎn)之前。但是如果p1所指的已是表尾結(jié)點(diǎn)，則p1就不應(yīng)后移了。如果p0- num比所有結(jié)點(diǎn)的num都大，則應(yīng)將p0所指的結(jié)點(diǎn)插到鏈表末尾。 如果插入的位置既不在第一個(gè)結(jié)點(diǎn)之前，又不在表尾結(jié)點(diǎn)之后，則將p0的值賦給p2-next，使p2-next指向待插入的結(jié)點(diǎn)，然后將p1的值賦給p0-next，使得p0-next指向p1指向的變量。38鏈表插入操作39鏈表插入操作插入結(jié)點(diǎn)的函數(shù)插入結(jié)點(diǎn)的函數(shù)insertstruct student *insert(struct student *head, struct student *stud)struct student *p0,*p1,*p2; p1=head;p0=stud; if(head=NULL) head=p0; p0-next=NULL; elsewhile(p0-num