第11章結(jié)構(gòu)體與共用體

1、2021-10-121第十一章第十一章 結(jié)構(gòu)體結(jié)構(gòu)體與共用體與共用體 結(jié)構(gòu)體的結(jié)構(gòu)體的定義定義 結(jié)構(gòu)體的結(jié)構(gòu)體的初始化初始化 訪問(wèn)結(jié)構(gòu)體成員訪問(wèn)結(jié)構(gòu)體成員 結(jié)構(gòu)體和函數(shù)結(jié)構(gòu)體和函數(shù)構(gòu)造的數(shù)據(jù)類(lèi)型構(gòu)造的數(shù)據(jù)類(lèi)型2021-10-1222、定義結(jié)構(gòu)的同時(shí)定義結(jié)構(gòu)變量：、定義結(jié)構(gòu)的同時(shí)定義結(jié)構(gòu)變量： struct student studend1, student2;（變量表列（變量表列）3、直接定義結(jié)構(gòu)變量：、直接定義結(jié)構(gòu)變量： struct studend1, student2;注意注意 （1）類(lèi)型類(lèi)型與與變量變量是不同的概念；是不同的概念； （2）對(duì)結(jié)構(gòu)中的成員可以單獨(dú)使用；）對(duì)結(jié)構(gòu)中的成員可以

2、單獨(dú)使用； （3）成員可以是結(jié)構(gòu)變量成員可以是結(jié)構(gòu)變量；賦值賦值.存取存取.運(yùn)算運(yùn)算;在在編譯時(shí)分配內(nèi)存編譯時(shí)分配內(nèi)存2021-10-12311.1 概述概述 結(jié)構(gòu)結(jié)構(gòu):一種構(gòu)造類(lèi)型數(shù)據(jù)一種構(gòu)造類(lèi)型數(shù)據(jù) (一條記錄一條記錄) 不同類(lèi)型的數(shù)據(jù)組合成不同類(lèi)型的數(shù)據(jù)組合成一個(gè)整體一個(gè)整體,以便引用以便引用為什么引入結(jié)構(gòu)型數(shù)據(jù)為什么引入結(jié)構(gòu)型數(shù)據(jù)?10010li gangm1887.5beijing num name sex age score addr結(jié)構(gòu)的定義結(jié)構(gòu)的定義：struct student int num; char name20; char sex; int age; float sc

3、ore; char addr30; ; struct student stu;結(jié)構(gòu)結(jié)構(gòu)類(lèi)型類(lèi)型2021-10-12411.2 定義結(jié)構(gòu)體類(lèi)型變量的方法定義結(jié)構(gòu)體類(lèi)型變量的方法 結(jié)構(gòu)體類(lèi)型的形式：結(jié)構(gòu)體類(lèi)型的形式： struct 結(jié)構(gòu)體名結(jié)構(gòu)體名 類(lèi)型名類(lèi)型名1 成員名成員名1； 類(lèi)型名類(lèi)型名2 成員名成員名2； ：；這個(gè)結(jié)構(gòu)就是一種這個(gè)結(jié)構(gòu)就是一種數(shù)據(jù)類(lèi)型數(shù)據(jù)類(lèi)型結(jié)構(gòu)體類(lèi)型許多種結(jié)構(gòu)體類(lèi)型許多種關(guān)鍵關(guān)鍵字字2021-10-125成員可以是結(jié)構(gòu)變量struct dateint month;int day;int year;struct studentint num;char name20;str

4、uct date birthday;char addr30 ;student1,student2;numnamebirthdaymonthdayyearaddr2021-10-12611.3 結(jié)構(gòu)體變量的引用結(jié)構(gòu)體變量的引用 結(jié)構(gòu)體變量不能整體引用，只能引用其成員結(jié)構(gòu)體變量不能整體引用，只能引用其成員 1） 結(jié)構(gòu)體變量中成員的引用方式結(jié)構(gòu)體變量中成員的引用方式 結(jié)構(gòu)體變量名結(jié)構(gòu)體變量名.成員名成員名 student1.num （“.”是成員運(yùn)算符是成員運(yùn)算符,優(yōu)先級(jí)最高）優(yōu)先級(jí)最高）2）如果成員本身又屬一個(gè)結(jié)構(gòu)體類(lèi)型）如果成員本身又屬一個(gè)結(jié)構(gòu)體類(lèi)型,則要找到最則要找到最 低一級(jí)的成員低一級(jí)的成

5、員,對(duì)它進(jìn)行賦值或存取以及運(yùn)算對(duì)它進(jìn)行賦值或存取以及運(yùn)算. student1.birthday.month student1.birthday3）成員可以像普通變量一樣進(jìn)行各種運(yùn)算）成員可以像普通變量一樣進(jìn)行各種運(yùn)算. student2.score= student1.score; student1.age+;例如：例如：student1.num = 10010;2021-10-12711.4 結(jié)構(gòu)體變量的初始化 在定義時(shí)初始化在定義時(shí)初始化(eg11.1)struct studentlong int num;char name20;char sex;char addr20;a=89031,l

6、i lin,m,123 beijing road;僅在定義時(shí)可整體初始化僅在定義時(shí)可整體初始化 a.num=89031; a.sex=m; a; name如何賦初值如何賦初值?2021-10-12811.5 結(jié)構(gòu)體數(shù)組 1 )定義結(jié)構(gòu)體數(shù)組定義結(jié)構(gòu)體數(shù)組 將結(jié)構(gòu)體定義中的變量定義為數(shù)組即可將結(jié)構(gòu)體定義中的變量定義為數(shù)組即可 struct student int num; char name20; char sex; int age; float score; char addr30; ; struct student stu3;2021-10-1292 )結(jié)構(gòu)體數(shù)組的初始化結(jié)構(gòu)體數(shù)組的初始化

7、struct student stu3=10101,lilin,m,18,87.5,123 beijing,10102,“zhangfun,m,19,99,123 shanghai,10104,“wang min,f,20,78.5,123 nanjing;struct student int num; char name20; char sex; int age; float score; char addr30; ; 2021-10-121010101“l(fā)i lin”1887.5“123 beijing”10102“zhang fun”stu0stu159bmm1999“123 shang

8、hai”3）結(jié)構(gòu)體數(shù)組的應(yīng)用舉例）結(jié)構(gòu)體數(shù)組的應(yīng)用舉例例例 11.2 對(duì)候選人得票的統(tǒng)計(jì)程對(duì)候選人得票的統(tǒng)計(jì)程序。有序。有3個(gè)候選人，每次輸入一個(gè)個(gè)候選人，每次輸入一個(gè)得票的候選人的名字，要求最后輸?shù)闷钡暮蜻x人的名字，要求最后輸出各人的得票結(jié)果。出各人的得票結(jié)果。2021-10-1211#include#includestruct personchar name20;int count;leader3=li,0,zhang,0,fun,0;void main()int i,j;char leader_name20;for(i=1;i=5;i+)scanf(%s,leader_name);for

9、(j=0;j3;j+)if(strcmp(leader_name,)=0)leaderj.count+;printf(n);for(i=0;inum=10010;(1)結(jié)構(gòu)體變量結(jié)構(gòu)體變量.成員名成員名(2)(*p).成員名成員名(3) p- .成員名成員名2021-10-1213#includevoid main()struct student long int num;char name20;char sex;float score;/ stu_1 =89031,li lin,m,89.5;struct student stu_1; struct student *

10、p; p=&stu_1;stu_1.num=89031;strcpy(stu_1.name,li lin);stu_1.sex=m; stu_1.score=89.5;printf(no.:%ldnname:%snsex:%cnscore:%fn,stu_1.num,stu_1.name,stu_1.sex,stu_1.score);printf(no.:%ldnname:%snsex:%cnscore:%fn,(*p).num,(*p).name,(*p).sex,(*p).score);eg11.32021-10-12142）指向結(jié)構(gòu)體數(shù)組的指針例 11.4#include struct

11、student int num; char name20; char sex; int age;stu3=10101,li lin,m,18, 10102,zhang fun,m,19, 10104,wang min,f,20;void main() struct student *p; for(p=stu;pnum,p-name,p-sex,p-age);10101li lin m18stu0pstu1stu2p+12021-10-12153)用結(jié)構(gòu)體變量和指向結(jié)構(gòu)體的指針作函數(shù)參數(shù)用結(jié)構(gòu)體變量和指向結(jié)構(gòu)體的指針作函數(shù)參數(shù)把結(jié)構(gòu)傳遞給函數(shù)有三種方式：把結(jié)構(gòu)傳遞給函數(shù)有三種方式： 單個(gè)成員單個(gè)

12、成員 整個(gè)結(jié)構(gòu)整個(gè)結(jié)構(gòu) 指向結(jié)構(gòu)的指針指向結(jié)構(gòu)的指針1、成員傳遞成員傳遞：用結(jié)構(gòu)變量成員作為實(shí)參：用結(jié)構(gòu)變量成員作為實(shí)參(值傳遞）值傳遞） 例如：對(duì)于上面定義的結(jié)構(gòu)變量例如：對(duì)于上面定義的結(jié)構(gòu)變量stu_1有四個(gè)成員。有四個(gè)成員。其中任何一個(gè)都可以做實(shí)參。其中任何一個(gè)都可以做實(shí)參。 void main() prin(stu_1.num); : 2021-10-12162、結(jié)構(gòu)傳遞（全體傳遞，多值傳遞）結(jié)構(gòu)傳遞（全體傳遞，多值傳遞）： 用結(jié)構(gòu)變量作實(shí)參用結(jié)構(gòu)變量作實(shí)參 將結(jié)構(gòu)變量所占的內(nèi)存單元內(nèi)容全部順序傳遞給形參（將結(jié)構(gòu)變量所占的內(nèi)存單元內(nèi)容全部順序傳遞給形參（值值傳遞傳遞），由于采用值傳遞內(nèi)

13、存開(kāi)銷(xiāo)大、在被調(diào)函數(shù)中改變），由于采用值傳遞內(nèi)存開(kāi)銷(xiāo)大、在被調(diào)函數(shù)中改變的形參值不能返回主調(diào)用函數(shù)，因此在使用上很不方便。的形參值不能返回主調(diào)用函數(shù)，因此在使用上很不方便。 eg11.5.c3、傳引用調(diào)用（地址傳遞傳引用調(diào)用（地址傳遞）：）： 定義結(jié)構(gòu)指針變量并以此指針作為實(shí)參定義結(jié)構(gòu)指針變量并以此指針作為實(shí)參 從而完成將結(jié)構(gòu)變量的指針傳給函數(shù)。主調(diào)函數(shù)和被調(diào)函從而完成將結(jié)構(gòu)變量的指針傳給函數(shù)。主調(diào)函數(shù)和被調(diào)函 數(shù)共用一段內(nèi)存空間。數(shù)共用一段內(nèi)存空間。 eg11.6.c傳遞數(shù)組（自動(dòng)實(shí)現(xiàn)傳引用調(diào)用）和傳遞結(jié)構(gòu)不同；傳遞數(shù)組（自動(dòng)實(shí)現(xiàn)傳引用調(diào)用）和傳遞結(jié)構(gòu)不同；用指針作函數(shù)參數(shù)能提高程序運(yùn)行效率

14、，有時(shí)節(jié)約內(nèi)存。用指針作函數(shù)參數(shù)能提高程序運(yùn)行效率，有時(shí)節(jié)約內(nèi)存。2021-10-1217 11.8 共用體&構(gòu)造數(shù)據(jù)類(lèi)型構(gòu)造數(shù)據(jù)類(lèi)型,也叫聯(lián)合體也叫聯(lián)合體&用途：使幾個(gè)不同類(lèi)型的變量共占一段內(nèi)存用途：使幾個(gè)不同類(lèi)型的變量共占一段內(nèi)存(相互覆蓋相互覆蓋) 共用體類(lèi)型定義定義形式：union 共用體名共用體名 類(lèi)型標(biāo)識(shí)符類(lèi)型標(biāo)識(shí)符 成員名；成員名； 類(lèi)型標(biāo)識(shí)符類(lèi)型標(biāo)識(shí)符 成員名；成員名； .；例 union data int i; char ch; float f; ;fchi類(lèi)型定義不分配內(nèi)存2021-10-1218形式一: union data int i; char ch; float f

15、; a,b;形式二: union data int i; char ch; float f; ; union data a,b,c,*p,d3;形式三: union int i; char ch; float f; a,b,c; 共用體變量的定義fchifchiab共用體變量定義分配內(nèi)存,長(zhǎng)度=最長(zhǎng)成員所占字節(jié)數(shù)共用體變量任何時(shí)刻只有一個(gè)成員存在2021-10-1219 共用體變量引用 引用方式：例 a.i=1; a.ch=a; a.f=1.5; printf(“%d”,a.i); (編譯通過(guò)，運(yùn)行結(jié)果不對(duì)) 引用規(guī)則 不能引用共用體變量，只能引用其成員共用體指針名共用體指針名-成員名成員名共

16、用體變量名共用體變量名.成員名成員名(*共用體指針名共用體指針名).成員名成員名union data int i; char ch; float f; ; union data a,b,c,*p,d3; p=&a;a.i a.ch a.fp-i p-ch p-f(*p).i (*p).ch (*p).fd0.i d0.ch d0.f 共用體變量中起作用的成員是最后一次存放的成員例 union int i; char ch; float f; a; a=1; () 不能在定義共用體變量時(shí)初始化例 union int i; char ch; float f; a=1,a,1.5; () 可以用一個(gè)

17、共用體變量為另一個(gè)變量賦值例 float x; union int i; char ch; float f; a,b; a.i=1; a.ch=a; a.f=1.5; b=a; () x=a.f; ()2021-10-1220 結(jié)構(gòu)體與共用體 區(qū)別: 存儲(chǔ)方式不同struct node char ch2; int k;a;union node char ch2; int k;b;achkbch k變量的各成員同時(shí)存在任一時(shí)刻只有一個(gè)成員存在 聯(lián)系: 兩者可相互嵌套2021-10-1221例 結(jié)構(gòu)體中嵌套共用體eg11.12 name numsexjobclasspositionliwang10

18、112086fmst501prof循環(huán)n次讀入姓名、號(hào)碼、性別、職務(wù)job=s真真假假讀入class讀入position輸出“輸入錯(cuò)”循環(huán)n次job=s真假輸出:姓名,號(hào)碼,性別,職業(yè),班級(jí)輸出:姓名,號(hào)碼,性別,職業(yè),職務(wù)job=tstruct int num; char name10; char sex; char job; union int class; char position10; category;person2;2021-10-122211.9 枚舉類(lèi)型如果一個(gè)變量只有幾種可能的值，可定義為枚舉類(lèi)型。一、枚舉類(lèi)型定義定義的一般形式為：enum 枚舉名 枚舉值表 ; 在枚舉值表

19、中應(yīng)羅列出所有可用值，這些值也稱(chēng)為枚舉元素，被說(shuō)明為該“枚舉”類(lèi)型的變量取值不能超過(guò)定義的范圍例如：enum weekday sun,mon,tue,wed,thu,fri,sat ; 2021-10-1223枚舉變量的定義同結(jié)構(gòu)體相同，有三種形式enum weekday sun,mou,tue,wed,thu,fri,sat ;enum weekday a,b,c;或者：enum weekday sun,mou,tue,wed,thu,fri,sat a,b,c;或者：enum sun,mou,tue,wed,thu,fri,sat a,b,c;2021-10-1224二、賦值和使用1.枚舉

20、值（枚舉元素）是常量，不能在程序中用賦值語(yǔ)句再對(duì)它賦值例如：sun=5; 錯(cuò)誤mon=2; 錯(cuò)誤2021-10-12252.枚舉元素本身由系統(tǒng)定義了一個(gè)表示序號(hào)的數(shù)值，從0開(kāi)始順序定義為0，1，2例如：sun的值是0，mon的值是12021-10-12263.枚舉值可以用來(lái)作判斷比較按其在定義時(shí)的順序號(hào)比較例如：enum weekday sun,mon,tue,wed,thu,fri,sat a;sunmonif( anum=202; ps-name=zhang san; ps-sex=m; ps-score=86.5; printf(number=%dnname=%sn,ps-num,ps-

21、name); printf(sex=%cnscore=%fn,ps-sex,ps-score); free(ps);整個(gè)程序包含了申請(qǐng)內(nèi)存空間、使用內(nèi)存空間、釋放內(nèi)存整個(gè)程序包含了申請(qǐng)內(nèi)存空間、使用內(nèi)存空間、釋放內(nèi)存空間三個(gè)步驟，實(shí)現(xiàn)存儲(chǔ)空間的動(dòng)態(tài)分配?？臻g三個(gè)步驟，實(shí)現(xiàn)存儲(chǔ)空間的動(dòng)態(tài)分配。2021-10-1238鏈表及其基本操作鏈表及其基本操作在上例中采用了動(dòng)態(tài)分配的辦法為一個(gè)結(jié)構(gòu)分配內(nèi)存在上例中采用了動(dòng)態(tài)分配的辦法為一個(gè)結(jié)構(gòu)分配內(nèi)存空間。每一次分配一塊空間可用來(lái)存放一個(gè)學(xué)生的數(shù)據(jù)，空間。每一次分配一塊空間可用來(lái)存放一個(gè)學(xué)生的數(shù)據(jù)，我們可稱(chēng)之為一個(gè)結(jié)點(diǎn)。有多少個(gè)學(xué)生就應(yīng)該申請(qǐng)分配多我們可稱(chēng)之

22、為一個(gè)結(jié)點(diǎn)。有多少個(gè)學(xué)生就應(yīng)該申請(qǐng)分配多少塊內(nèi)存空間，也就是說(shuō)要建立多少個(gè)結(jié)點(diǎn)。當(dāng)然用結(jié)構(gòu)少塊內(nèi)存空間，也就是說(shuō)要建立多少個(gè)結(jié)點(diǎn)。當(dāng)然用結(jié)構(gòu)數(shù)組也可以完成上述工作。如果事先不知道學(xué)生人數(shù)，也數(shù)組也可以完成上述工作。如果事先不知道學(xué)生人數(shù)，也就無(wú)法確定數(shù)組大小。而且當(dāng)學(xué)生留級(jí)、退學(xué)之后也不能就無(wú)法確定數(shù)組大小。而且當(dāng)學(xué)生留級(jí)、退學(xué)之后也不能把該元素占用的空間從數(shù)組中釋放出來(lái)。把該元素占用的空間從數(shù)組中釋放出來(lái)。2021-10-1239用動(dòng)態(tài)存儲(chǔ)的方法可以很好地解決這些問(wèn)題。有一個(gè)學(xué)用動(dòng)態(tài)存儲(chǔ)的方法可以很好地解決這些問(wèn)題。有一個(gè)學(xué)生就分配一個(gè)結(jié)點(diǎn)，無(wú)須預(yù)先確定學(xué)生的準(zhǔn)確人數(shù)，某學(xué)生生就分配一個(gè)結(jié)點(diǎn)

23、，無(wú)須預(yù)先確定學(xué)生的準(zhǔn)確人數(shù)，某學(xué)生退學(xué)，可刪去該結(jié)點(diǎn)，并釋放該結(jié)點(diǎn)占用的存儲(chǔ)空間。從而退學(xué)，可刪去該結(jié)點(diǎn)，并釋放該結(jié)點(diǎn)占用的存儲(chǔ)空間。從而節(jié)約了寶貴的內(nèi)存資源。另一方面，用數(shù)組的方法必須占用節(jié)約了寶貴的內(nèi)存資源。另一方面，用數(shù)組的方法必須占用一塊連續(xù)的內(nèi)存區(qū)域。而使用動(dòng)態(tài)分配時(shí)，每個(gè)結(jié)點(diǎn)之間可一塊連續(xù)的內(nèi)存區(qū)域。而使用動(dòng)態(tài)分配時(shí)，每個(gè)結(jié)點(diǎn)之間可以是不連續(xù)的以是不連續(xù)的(結(jié)點(diǎn)內(nèi)是連續(xù)的結(jié)點(diǎn)內(nèi)是連續(xù)的)。結(jié)點(diǎn)之間的聯(lián)系可以用指。結(jié)點(diǎn)之間的聯(lián)系可以用指針實(shí)現(xiàn)。即在結(jié)點(diǎn)結(jié)構(gòu)中定義一個(gè)成員項(xiàng)用來(lái)存放下一結(jié)點(diǎn)針實(shí)現(xiàn)。即在結(jié)點(diǎn)結(jié)構(gòu)中定義一個(gè)成員項(xiàng)用來(lái)存放下一結(jié)點(diǎn)的首地址，這個(gè)用于存放地址的成員，常把它稱(chēng)為

24、的首地址，這個(gè)用于存放地址的成員，常把它稱(chēng)為指針域指針域?？稍诘谝粋€(gè)結(jié)點(diǎn)的指針域內(nèi)存入第二個(gè)結(jié)點(diǎn)的首地址，可在第一個(gè)結(jié)點(diǎn)的指針域內(nèi)存入第二個(gè)結(jié)點(diǎn)的首地址，在第二個(gè)結(jié)點(diǎn)的指針域內(nèi)又存放第三個(gè)結(jié)點(diǎn)的首地址，如此在第二個(gè)結(jié)點(diǎn)的指針域內(nèi)又存放第三個(gè)結(jié)點(diǎn)的首地址，如此串連下去直到最后一個(gè)結(jié)點(diǎn)。最后一個(gè)結(jié)點(diǎn)因無(wú)后續(xù)結(jié)點(diǎn)連串連下去直到最后一個(gè)結(jié)點(diǎn)。最后一個(gè)結(jié)點(diǎn)因無(wú)后續(xù)結(jié)點(diǎn)連接，其指針域可賦為接，其指針域可賦為null。這樣一種連接方式，在數(shù)據(jù)結(jié)。這樣一種連接方式，在數(shù)據(jù)結(jié)構(gòu)中稱(chēng)為構(gòu)中稱(chēng)為“鏈表鏈表”。2021-10-1240下圖為一簡(jiǎn)單鏈表的示意圖。下圖為一簡(jiǎn)單鏈表的示意圖。圖圖8-1 單鏈表示意圖單鏈表示

25、意圖圖中，圖中，head為為“頭指針頭指針”變量，它存放第一個(gè)結(jié)點(diǎn)的首變量，它存放第一個(gè)結(jié)點(diǎn)的首地址，它沒(méi)有數(shù)據(jù)，只是一個(gè)指針變量。以下的每個(gè)結(jié)點(diǎn)都地址，它沒(méi)有數(shù)據(jù)，只是一個(gè)指針變量。以下的每個(gè)結(jié)點(diǎn)都分為兩個(gè)域，一個(gè)是數(shù)據(jù)域，存放各種實(shí)際的數(shù)據(jù)，如學(xué)號(hào)分為兩個(gè)域，一個(gè)是數(shù)據(jù)域，存放各種實(shí)際的數(shù)據(jù)，如學(xué)號(hào)num，和成績(jī)，和成績(jī)score等。另一個(gè)域?yàn)橹羔樣颍娣畔乱唤Y(jié)點(diǎn)等。另一個(gè)域?yàn)橹羔樣?，存放下一結(jié)點(diǎn)的首地址。鏈表中的每一個(gè)結(jié)點(diǎn)都是同一種結(jié)構(gòu)類(lèi)型。的首地址。鏈表中的每一個(gè)結(jié)點(diǎn)都是同一種結(jié)構(gòu)類(lèi)型。2021-10-1241上圖中的結(jié)點(diǎn)可以定義為以下結(jié)構(gòu)：上圖中的結(jié)點(diǎn)可以定義為以下結(jié)構(gòu)：struct

26、 studentint num;float score;struct student *next;前兩個(gè)成員項(xiàng)組成數(shù)據(jù)域，后一個(gè)成員項(xiàng)前兩個(gè)成員項(xiàng)組成數(shù)據(jù)域，后一個(gè)成員項(xiàng)next構(gòu)成指針域，它是一個(gè)指向構(gòu)成指針域，它是一個(gè)指向student結(jié)構(gòu)類(lèi)型的指結(jié)構(gòu)類(lèi)型的指針變量。針變量。2021-10-1242對(duì)鏈表的主要操作有以下幾種：對(duì)鏈表的主要操作有以下幾種：（1 1）建立鏈表；）建立鏈表；（2 2）鏈表的遍歷；）鏈表的遍歷；（3 3）插入一個(gè)結(jié)點(diǎn)；）插入一個(gè)結(jié)點(diǎn)；（4 4）刪除一個(gè)結(jié)點(diǎn)；）刪除一個(gè)結(jié)點(diǎn)；下面通過(guò)例題來(lái)說(shuō)明這些操作。下面通過(guò)例題來(lái)說(shuō)明這些操作。2021-10-12431、建立鏈表

27、、建立鏈表(p297 例例11.8)在本節(jié)算法和例題中假設(shè)在本節(jié)算法和例題中假設(shè)n是已定義的全局變量，表示結(jié)點(diǎn)個(gè)數(shù)，是已定義的全局變量，表示結(jié)點(diǎn)個(gè)數(shù)，其初值為零。建立鏈表的算法如下其初值為零。建立鏈表的算法如下(圖圖11-13,圖圖11-14,15,16 )（1）開(kāi)辟一個(gè)新結(jié)點(diǎn)，并使）開(kāi)辟一個(gè)新結(jié)點(diǎn)，并使p1、p2指向該結(jié)點(diǎn)指向該結(jié)點(diǎn)（2）讀入一個(gè)學(xué)生數(shù)據(jù)給）讀入一個(gè)學(xué)生數(shù)據(jù)給p1所指向的結(jié)點(diǎn)所指向的結(jié)點(diǎn)（3）head=null,n=0（4）當(dāng)讀入的）當(dāng)讀入的p1-num不是不是0時(shí)做循環(huán)：時(shí)做循環(huán)： n+ 如果如果n=1則則head=p1否則否則p2-next=p1 p2=p1 再開(kāi)辟一個(gè)新

28、結(jié)點(diǎn)，并使再開(kāi)辟一個(gè)新結(jié)點(diǎn)，并使p1指向它該結(jié)點(diǎn)指向它該結(jié)點(diǎn) 讀入一個(gè)學(xué)生數(shù)據(jù)給讀入一個(gè)學(xué)生數(shù)據(jù)給p1所指向的結(jié)點(diǎn)所指向的結(jié)點(diǎn)（5）將表尾結(jié)點(diǎn)的指針域置）將表尾結(jié)點(diǎn)的指針域置null2021-10-1244【例【例11.8】寫(xiě)一個(gè)函數(shù)建立一個(gè)單向鏈表，當(dāng)輸入數(shù)據(jù)為零時(shí)表示完成鏈表】寫(xiě)一個(gè)函數(shù)建立一個(gè)單向鏈表，當(dāng)輸入數(shù)據(jù)為零時(shí)表示完成鏈表的建立。的建立。根據(jù)建立鏈表的算法，函數(shù)設(shè)計(jì)如下：根據(jù)建立鏈表的算法，函數(shù)設(shè)計(jì)如下： #define null 0 #define len sizeof(struct student) #include #include struct student long

29、num; float score; struct student *next; ; int n; struct student *creat() struct student *head,*p1,*p2; n=0;2021-10-1245 p1=p2=(struct student *) malloc(len); /*建立新結(jié)點(diǎn)建立新結(jié)點(diǎn)*/ scanf(%ld,%f,&p1-num,& p1-score); head=null; while(p1-num!=0) /*輸入數(shù)據(jù)不等于輸入數(shù)據(jù)不等于0時(shí)執(zhí)行循環(huán)時(shí)執(zhí)行循環(huán)*/ n=n+1; if(n=1) head=p1; /*把新結(jié)點(diǎn)作為第一個(gè)

30、結(jié)點(diǎn)把新結(jié)點(diǎn)作為第一個(gè)結(jié)點(diǎn)(11-13) */ else p2-next=p1; /*把新結(jié)點(diǎn)加入到鏈表后面把新結(jié)點(diǎn)加入到鏈表后面(15b) */ p2=p1; /*p2指向鏈尾指向鏈尾(15c) */ p1=(struct student *)malloc(len); /*再建立新結(jié)點(diǎn)再建立新結(jié)點(diǎn)*/ scanf(%ld,%f,&p1- num,&p1-score); p2-next=null; /*將表尾結(jié)點(diǎn)的指針域置將表尾結(jié)點(diǎn)的指針域置null (16b) */ return(head); 2021-10-12462、鏈表的遍歷、鏈表的遍歷 鏈表的遍歷就是從頭結(jié)點(diǎn)開(kāi)始依次訪問(wèn)鏈表的每鏈表

31、的遍歷就是從頭結(jié)點(diǎn)開(kāi)始依次訪問(wèn)鏈表的每個(gè)結(jié)點(diǎn)。鏈表的查找與輸出都是遍歷的例子。鏈表輸個(gè)結(jié)點(diǎn)。鏈表的查找與輸出都是遍歷的例子。鏈表輸出的算法如下：出的算法如下：（1）p=head（2）如果）如果p指向的不是尾結(jié)點(diǎn)，則指向的不是尾結(jié)點(diǎn)，則 輸出輸出p所指向的結(jié)點(diǎn)所指向的結(jié)點(diǎn) p移動(dòng)，指向下一個(gè)結(jié)點(diǎn)移動(dòng)，指向下一個(gè)結(jié)點(diǎn) 直到直到p指向尾結(jié)點(diǎn)為止指向尾結(jié)點(diǎn)為止2021-10-1247【例【例11.9】寫(xiě)一個(gè)函數(shù)用來(lái)輸出一個(gè)已知的單向鏈表。】寫(xiě)一個(gè)函數(shù)用來(lái)輸出一個(gè)已知的單向鏈表。設(shè)結(jié)構(gòu)設(shè)結(jié)構(gòu)student的定義與例的定義與例11.8相同，根據(jù)鏈表輸出的算法，函相同，根據(jù)鏈表輸出的算法，函數(shù)設(shè)計(jì)如下：數(shù)設(shè)

32、計(jì)如下：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!=null); 2021-10-12483 3、在鏈表中插入一個(gè)結(jié)點(diǎn)、在鏈表中插入一個(gè)結(jié)點(diǎn)設(shè)鏈表已按學(xué)號(hào)升序排序。如圖設(shè)鏈表已按學(xué)號(hào)升序排序。如圖8-2所示，要在鏈表中插入所示，要在鏈表中插入結(jié)點(diǎn)，首先確定插入位置，將插入位置的前一個(gè)結(jié)點(diǎn)的指針結(jié)點(diǎn)，首先

33、確定插入位置，將插入位置的前一個(gè)結(jié)點(diǎn)的指針域指向插入結(jié)點(diǎn)的首地址，將插入結(jié)點(diǎn)的指針域設(shè)置為與插域指向插入結(jié)點(diǎn)的首地址，將插入結(jié)點(diǎn)的指針域設(shè)置為與插入位置的前一結(jié)點(diǎn)原來(lái)的指針域相同即可。若要插入結(jié)點(diǎn)的入位置的前一結(jié)點(diǎn)原來(lái)的指針域相同即可。若要插入結(jié)點(diǎn)的首地址為首地址為stud，則在鏈表中插入一個(gè)結(jié)點(diǎn)的算法如下：，則在鏈表中插入一個(gè)結(jié)點(diǎn)的算法如下：圖圖8-2 插入結(jié)點(diǎn)示意圖插入結(jié)點(diǎn)示意圖2021-10-1249（1）p1=head，p0=stud（2）如果鏈表是空表，則將）如果鏈表是空表，則將p0所指向的結(jié)點(diǎn)直接插入到表所指向的結(jié)點(diǎn)直接插入到表頭，結(jié)束頭，結(jié)束（3）當(dāng)）當(dāng)p0-nump1-num且

34、且p1不指向表尾時(shí)不指向表尾時(shí) p2=p1 p1=p1-next （循環(huán)結(jié)束時(shí)（循環(huán)結(jié)束時(shí)p1指向插入位置）指向插入位置）（4）如果）如果p0-nump1-num，則，則 如果如果p1指向表頭，則指向表頭，則head=p0， 否則否則p2-next=p0 p0-next=p1 否則否則p1-next=p0 p0-next=null （插到表尾后）（插到表尾后）2021-10-1250【例【例11.11】寫(xiě)一個(gè)函數(shù)用來(lái)在一個(gè)已排序的鏈表中插入一個(gè)結(jié)點(diǎn)。】寫(xiě)一個(gè)函數(shù)用來(lái)在一個(gè)已排序的鏈表中插入一個(gè)結(jié)點(diǎn)。設(shè)結(jié)構(gòu)設(shè)結(jié)構(gòu)student的定義與前相同，根據(jù)在鏈表中插入一個(gè)結(jié)點(diǎn)算法，的定義與前相同，根據(jù)在鏈

35、表中插入一個(gè)結(jié)點(diǎn)算法，函數(shù)設(shè)計(jì)如下：函數(shù)設(shè)計(jì)如下：struct student * insert(struct student * head, struct student * stud) struct student *p0,*p1,*p2;p1=head;p0=stud;2021-10-1251if(head=null) /*原來(lái)的鏈表為空表原來(lái)的鏈表為空表*/ head=p0;p0-next=null; /*結(jié)點(diǎn)直接作為表頭結(jié)點(diǎn)直接作為表頭*/else while(p0-nump1-num) &(p1-next!=null) /*(a)*/ p2=p1; p1=p1-next; /*循環(huán)

36、結(jié)束時(shí)循環(huán)結(jié)束時(shí)p1指向插入位置指向插入位置(b) */2021-10-1252 if(p0-numnum) if(head=p1) head=p0; /*結(jié)點(diǎn)插入到表頭結(jié)點(diǎn)插入到表頭(d) */ else p2-next=p0; /*結(jié)點(diǎn)插入到結(jié)點(diǎn)插入到p1前前(c) */ p0-next=p1; else p1-next=p0;p0-next=null; /*結(jié)點(diǎn)插入到表尾結(jié)點(diǎn)插入到表尾(e)*/ n=n+1; return(head);2021-10-12534 4、在鏈表中刪除一個(gè)結(jié)點(diǎn)、在鏈表中刪除一個(gè)結(jié)點(diǎn)如圖如圖8-3所示，要在鏈表中刪除結(jié)點(diǎn)，在確定要?jiǎng)h除的結(jié)點(diǎn)所示，要在鏈表中刪除結(jié)

37、點(diǎn)，在確定要?jiǎng)h除的結(jié)點(diǎn)后，將其前一個(gè)結(jié)點(diǎn)的指針域用被刪除結(jié)點(diǎn)的指針域代替即后，將其前一個(gè)結(jié)點(diǎn)的指針域用被刪除結(jié)點(diǎn)的指針域代替即可。在鏈表中刪除一個(gè)結(jié)點(diǎn)的算法如下：可。在鏈表中刪除一個(gè)結(jié)點(diǎn)的算法如下：圖8-3 刪除結(jié)點(diǎn)示意圖2021-10-1254（1）如果鏈表是一個(gè)空表，則輸出信息，轉(zhuǎn)（）如果鏈表是一個(gè)空表，則輸出信息，轉(zhuǎn)（5）（2）p1=head（3）nump1-num以及以及p1指向的不是尾結(jié)點(diǎn)時(shí)指向的不是尾結(jié)點(diǎn)時(shí) p2=p1 p1=p1-next （找出要?jiǎng)h除的結(jié)點(diǎn)（找出要?jiǎng)h除的結(jié)點(diǎn)p1）（4）如果）如果p1是要?jiǎng)h除的結(jié)點(diǎn)，則是要?jiǎng)h除的結(jié)點(diǎn)，則 如果如果p1是表頭則是表頭則head=p1

38、-next 否則否則p2-next=p1-next 否則輸出否則輸出“找不到找不到”的信息的信息（5）結(jié)束）結(jié)束2021-10-1255【例【例8.12】寫(xiě)一個(gè)函數(shù)用來(lái)在給定鏈表中刪除一個(gè)結(jié)點(diǎn)?！繉?xiě)一個(gè)函數(shù)用來(lái)在給定鏈表中刪除一個(gè)結(jié)點(diǎn)。設(shè)結(jié)構(gòu)設(shè)結(jié)構(gòu)student的定義與前相同，根據(jù)在鏈表中刪除一個(gè)結(jié)點(diǎn)算法，的定義與前相同，根據(jù)在鏈表中刪除一個(gè)結(jié)點(diǎn)算法，函數(shù)設(shè)計(jì)如下：函數(shù)設(shè)計(jì)如下：struct student * del(struct student * head, int num) struct student *p1,*p2; if (head=null) printf(nlist null!n); else while(num!=p1-num & p1-next!=null) /*若若p1指向的不是要找的結(jié)點(diǎn)，且后面還有結(jié)點(diǎn)指向的不是要找的結(jié)點(diǎn)，且后面還有結(jié)點(diǎn)*/ p2=p1;p1=p1-next; /*找