C語言程序設(shè)計(jì)ppt-第10章-02

1、C語言程序設(shè)計(jì)The C Programming Language華中科技大學(xué)計(jì)算機(jī)學(xué)院曹計(jì)昌7/23/20221華中科技大學(xué)計(jì)算機(jī)學(xué)院*10.7 聯(lián) 合 10.7.1 聯(lián)合類型的定義 與結(jié)構(gòu)類似，聯(lián)合類型也是一種構(gòu)造類型。一個(gè)聯(lián)合類型中包含有多個(gè)成員，這些成員共享共同的存儲區(qū)域，但這些成員并不同時(shí)存在;聯(lián)合存儲區(qū)域的大小由各個(gè)成員中所占字節(jié)數(shù)最大的成員決定;在任何時(shí)刻，各個(gè)成員中只能有一個(gè)成員擁有該存儲。 除了用關(guān)鍵字union取代struct之外，聯(lián)合類型的定義、聯(lián)合變量的聲明、以及聯(lián)合成員的引用在語法上與結(jié)構(gòu)完全相同。 7/23/20222華中科技大學(xué)計(jì)算機(jī)學(xué)院如果有3個(gè)不同數(shù)據(jù)類型（c

2、har, short, long ）的變量要分時(shí)共用一個(gè)共同的存儲區(qū)域，則可以定義如下的聯(lián)合類型： union chlcharc;shorth;longl;這里chl是所定義的聯(lián)合類型的聯(lián)合名（tag） , 它與union一起形成一個(gè)union chl的聯(lián)合類型。c、h、l是聯(lián)合類型的成員。 7/23/20223華中科技大學(xué)計(jì)算機(jī)學(xué)院10.7.2 聯(lián)合變量的聲明、初始化及聯(lián)合成員的引用 定義了union chl的聯(lián)合類型后，可以通過：union chl u;來聲明一個(gè)union chl類型的變量。也可以在定義union chl聯(lián)合類型的同時(shí)來聲明相應(yīng)的聯(lián)合變量。如：union chlchar

3、c;short h;long l;v=9;它在定義union chl聯(lián)合類型的同時(shí)聲明了聯(lián)合類型的變量v，并且對其進(jìn)行了初始化。在不產(chǎn)生二義的情況下，往往簡稱聯(lián)合類型的變量為聯(lián)合。7/23/20224華中科技大學(xué)計(jì)算機(jī)學(xué)院聯(lián)合變量的聲明、初始化值得注意的是，聯(lián)合變量的初始化與結(jié)構(gòu)的初始化在形式上相同，都應(yīng)該用花括號界定初值，但聯(lián)合是一種特殊形式的構(gòu)造類型的數(shù)據(jù)，在同一時(shí)刻它只擁有其中的一個(gè)成員。因此，初始化時(shí)只能對聯(lián)合的第1個(gè)成員進(jìn)行初始化。換言之，初值表中只能包含與第1個(gè)成員數(shù)據(jù)類型相同的一個(gè)初值。如上面例子中的v=9。也可以：union chl v=9,w=a;7/23/20225華中科技

4、大學(xué)計(jì)算機(jī)學(xué)院例10.12 通過例子對聯(lián)合的特性進(jìn)行進(jìn)一步分析。#include stdio.hunion chl charc; shorth; longl;void show(union chl *pu);void show_memoy(union chl *pu); 7/23/20226華中科技大學(xué)計(jì)算機(jī)學(xué)院void main(void) union chl u; printf(size of u is %dn,sizeof(u); u.l=0 x31323334L; show(&u); show_memoy(&u); u.h=0 x3638; show(&u); show_memoy(&

5、u);7/23/20227華中科技大學(xué)計(jì)算機(jī)學(xué)院void show(union chl *pu) printf(char format: %cn,(*pu).c); printf(int format: %hxn,pu-h); printf(long format: %lxn,(*pu).l);void show_memoy(union chl *pu) char *p=(char *)pu; int i=0; while(i”操作符來引用聯(lián)合成員。從u.l，(*pu).c，pu-h三個(gè)表達(dá)式中可以歸納出對聯(lián)合成員的引用形式為：（1）聯(lián)合變量名.成員名。（2）(*指向聯(lián)合變量的指針).成員名。

6、（3）指向聯(lián)合變量的指針-成員名。例如：u.c 或(*pu).c 或pu-c 都表示引用聯(lián)合成員c，類型是char。u.h 或(*pu).h 或pu-h 都表示引用聯(lián)合成員h，類型是short。u.l 或(*pu).l 或pu-l 都表示引用聯(lián)合成員c，類型是long。而u.c=a，(*pu).h=0 x3839，以及pu-l=0 x31323334L分別表示對聯(lián)合u的成員c、h、l的賦值操作。 7/23/202212華中科技大學(xué)計(jì)算機(jī)學(xué)院4) 共享存儲的特點(diǎn)在main函數(shù)中，u.l=0 x31323334L;賦值語句產(chǎn)生的存儲可由表10-3描述，各字節(jié)的地址由高向低，依次存放0 x31、0

7、x32、0 x33、0 x34，聯(lián)合u由成員l使用。由show函數(shù)和相應(yīng)的運(yùn)行結(jié)果可以看出，此時(shí)如果按照(*pu).c解釋，輸出的只是共享存儲的低字節(jié)的內(nèi)容0 x34或字符4。如果按照,pu-h解釋，輸出的只是共享存儲的低端2個(gè)字節(jié)的內(nèi)容0 x33和0 x34。執(zhí)行u.h=0 x3638;語句之后，聯(lián)合u由成員h使用。該語句修改了共享存儲低端2個(gè)字節(jié)的內(nèi)容，但是高端2個(gè)字節(jié)的內(nèi)容沒有變化。 7/23/202213華中科技大學(xué)計(jì)算機(jī)學(xué)院5) 相容性操作聯(lián)合中允許存儲不同類型的數(shù)據(jù)，對某個(gè)時(shí)刻存儲的數(shù)據(jù)，其所允許的操作也有所不同，有些操作對該類型的數(shù)據(jù)是相容的，但有些操作卻不相容（得不到正確結(jié)果）

8、。由于語法上合法，編譯器對這種情況不會報(bào)錯(cuò)，但運(yùn)算的結(jié)果卻不正確。假如在union chl中增加一個(gè)成員（其它都不變），如：float f;則在show函數(shù)中，如果執(zhí)行語句為：printf(float format: %fn,pu-f);則得到是不正確的結(jié)果0.00，而其他語句中操作卻是相容的。 7/23/202214華中科技大學(xué)計(jì)算機(jī)學(xué)院*10.8 字段結(jié)構(gòu)由多個(gè)相鄰的二進(jìn)制位可以組成結(jié)構(gòu)或者聯(lián)合中的整型或無符號整型成員，這些個(gè)相鄰的二進(jìn)制位被稱為字段（bit field），對應(yīng)的成員稱為結(jié)構(gòu)或聯(lián)合的字段成員，以字段為成員的結(jié)構(gòu)稱為字段結(jié)構(gòu)。組成字段的二進(jìn)制位的數(shù)目成為該字段的寬度，它是一個(gè)

9、非負(fù)的整型常量表達(dá)式。字段結(jié)構(gòu)在操作系統(tǒng)，編譯程序，嵌入式系統(tǒng)的C語言編程方面使用較多。例如，stdio.h中關(guān)于文件狀態(tài)成員flags的取值就規(guī)定了1為讀狀態(tài)，2為寫狀態(tài)，4為緩沖數(shù)據(jù)狀態(tài)等等。這些數(shù)據(jù)都是一些值很小的整數(shù)，沒有必要用int或char變量來存儲每一個(gè)值。通常對若干個(gè)特征中的每個(gè)特征按照取值的大小分配合適的二進(jìn)制位，然后將它們組織成為字段封裝到一個(gè)int或char變量中。這樣就可以通過字段名對相應(yīng)的二進(jìn)制位或位串進(jìn)行操作，而不必采用前面章節(jié)介紹的位運(yùn)算。 7/23/202215華中科技大學(xué)計(jì)算機(jī)學(xué)院10.8.1 字段結(jié)構(gòu)類型的定義字段結(jié)構(gòu)也屬于構(gòu)造類型，因此要先定義字段結(jié)構(gòu)類型

10、，再聲明字段結(jié)構(gòu)變量，然后再對字段結(jié)構(gòu)變量中的成員進(jìn)行操作?？紤]十字路口的交通燈 .顏色枚舉類型的聲明如下：enum color OFF=0,RED=1,YELLOW=2,GREEN=3; 7/23/202216華中科技大學(xué)計(jì)算機(jī)學(xué)院struct traffic_lightunsigned short int east:2;/* 東組燈狀態(tài)字段 */unsigned short int south:2;/* 南組燈狀態(tài)字段 */unsigned short int west:2;/* 西組燈狀態(tài)字段 */unsigned short int north:2;/* 北組燈狀態(tài)字段 */unsig

11、ned short int reserve:8; /* 保留字段 */unsigned short int east_on:4; /* 東組燈開通時(shí)間 */unsigned short int south_on:4;/* 南組燈開通時(shí)間 */unsigned short int west_on:4;/* 西組燈開通時(shí)間 */unsigned short int north_on:4;/* 北組燈開通時(shí)間 */; 4組交通燈的字段結(jié)構(gòu)類型的聲明7/23/202217華中科技大學(xué)計(jì)算機(jī)學(xué)院4組交通燈的字段結(jié)構(gòu)類型的簡略形式聲明 struct traffic_lightunsigned short

12、int east:2,south:2,west:2,north:2,reserve:8;unsigned short int east_on:4,south_on:4,west_on:4,north_on:4;上面聲明了一個(gè)struct traffic_light的字段結(jié)構(gòu)類型，east、south、north_on為它的字段成員，字段成員往往也簡稱為字段。冒號后面的整數(shù)說明了成員的字段寬度，字段寬度是一個(gè)非負(fù)的整型常量表達(dá)式。上面定義中，其中字段寬度為2的四個(gè)成員用unsigned char更加簡練，但Turbo C中不支持unsigned char，因此用unsigned short in

13、t。7/23/202218華中科技大學(xué)計(jì)算機(jī)學(xué)院10.8.2 字段結(jié)構(gòu)類型變量的聲明及成員的引用 可以先定義字段結(jié)構(gòu)類型，再聲明字段結(jié)構(gòu)類型的變量。如：struct traffic_light Jiedaokou;它聲明了struct traffic_light的字段結(jié)構(gòu)類型變量Jiedaokou。同時(shí)，還可以在聲明字段結(jié)構(gòu)類型的變量的同時(shí)對其進(jìn)行初始化。如：struct traffic_light Jiedaokou=0,0,0,0,0,0,0,0,0;它將east、north_on這9個(gè)字段成員都初始化為0。 7/23/202219華中科技大學(xué)計(jì)算機(jī)學(xué)院也可以在定義字段結(jié)構(gòu)類型的同時(shí)聲明字

14、段結(jié)構(gòu)變量并對其成員進(jìn)行初始化。如： struct traffic_lightunsigned short int east:2,south:2,west:2,north:2,reserve:8;unsigned short int east_on:4,south_on:4,west_on:4,north_on:4; Jiedaokou=0,0,0,0,0,0,0,0,0,*p=&Jiedaokou;字段就是一個(gè)小整數(shù)，它可以出現(xiàn)在其它整數(shù)可以出現(xiàn)的任何地方。字段在參與運(yùn)算時(shí)被自動轉(zhuǎn)換為int或unsigned int類型的整數(shù)。對一個(gè)字段結(jié)構(gòu)中成員的引用與對一般結(jié)構(gòu)變量中結(jié)構(gòu)成員的引用方法相

15、同，有“.”和“-”兩種。如：Jiedaokou.west，Jiedaokou.west_on，p-north，p-north_on等。 7/23/202220華中科技大學(xué)計(jì)算機(jī)學(xué)院例10.13 字段結(jié)構(gòu)變量的成員引用舉例。 void main(void)struct traffic_light Jiedaokou=0,0,0,0,0,0,0,0,0;Jiedaokou.west=GREEN;Jiedaokou.west_on=5;printf(Jiedaokou.west=%ut,Jiedaokou.west);printf(Jiedaokou.west_on=%un,Jiedaokou.w

16、est_on);printf(Jiedaokou.east=%ut,Jiedaokou.east);printf(Jiedaokou.east_on=%un,Jiedaokou.east_on);程序的運(yùn)行結(jié)果如下：Jiedaokou.west=3 Jiedaokou.west_on=5Jiedaokou.east=0 Jiedaokou.east_on=0 7/23/202221華中科技大學(xué)計(jì)算機(jī)學(xué)院字段成員的寬度問題由于字段成員表示整數(shù)的范圍有限，在對字段成員賦值時(shí)不要超出了它表示數(shù)的范圍。如果超出了它表示數(shù)的范圍，則數(shù)的高位部分將被丟棄。如Jiedaokou.west_on的寬度為4，它

17、能夠表示數(shù)的范圍是015。如果執(zhí)行Jiedaokou.west_on=17（即0 x11 或00010001B），編譯時(shí)不會報(bào)錯(cuò)，如果再執(zhí)行：printf(Jiedaokou.west_on=%un,Jiedaokou.west_on);其輸出為1。高位“1”被丟棄。 7/23/202222華中科技大學(xué)計(jì)算機(jī)學(xué)院可以通過指向字段結(jié)構(gòu)變量的指針來操縱字段結(jié)構(gòu)變量的成員。 如:struct traffic_light Jiedaokou=0,0,0,0,0,0,0,0,0,*p=&Jiedaokou;它聲明了一個(gè)struct traffic_light類型的字段結(jié)構(gòu)指針p，并且使p指向了字段結(jié)構(gòu)變

18、量Jiedaokou。而p-north=RED;p-north_on=6;分別表示通過指針p引用Jiedaokou的成員north和north_on，并通過賦值操作對這些成員進(jìn)行賦值。下面的語句則是輸出相應(yīng)的結(jié)果：printf(Jiedaokou.north=%ut,p-north);printf(Jiedaokou.north_on=%un,p-north_on);7/23/202223華中科技大學(xué)計(jì)算機(jī)學(xué)院10.8.3 字段結(jié)構(gòu)與聯(lián)合的應(yīng)用本節(jié)通過一個(gè)例子說明如何訪問一個(gè)16位字中的高低字節(jié)和各二進(jìn)制位。例子中將字段byte0和byte1的寬度定義為8，用以表示一個(gè)16位字中的高字節(jié)和低字

19、節(jié);將字段b0b15寬度定義為1，用以表示一個(gè)16位字中的各個(gè)二進(jìn)制位。并且用聯(lián)合使一個(gè)短整型變量、2個(gè)字節(jié)字段與16個(gè)位字段共享共同的存儲。 7/23/202224華中科技大學(xué)計(jì)算機(jī)學(xué)院例10.14 用字段和聯(lián)合訪問一個(gè)16位字中的高低字節(jié)和各二進(jìn)制位的應(yīng)用舉例。#include stdio.h#define CHAR_BIT 8struct w16_bytes unsigned short byte0:8,byte1:8; /* byte0為低字節(jié),byte1為高字節(jié) */ ;struct w16_bits unsigned short b0:1,b1:1,b2:1,b3:1,b4:1,b

20、5:1,b6:1,b7:1, b8:1,b9:1,b10:1,b11:1,b12:1,b13:1,b14:1,b15:1; ;7/23/202225華中科技大學(xué)計(jì)算機(jī)學(xué)院union w16 /* 短整型變量、結(jié)構(gòu)成員byte、結(jié)構(gòu)成員bit共享共同的存儲 */ shorti; struct w16_bytesbyte; struct w16_bitsbit; ;void main(void) union w16w=0;/* i為0；byte0和byte1也為0；b0至b15皆為0 */ void bit_print(short); w.bit.b9=1; /* 相當(dāng)于byte1為2 */ w.

21、bit.b10=1; /* 相當(dāng)于byte1為6 */ w.byte.byte0=b; printf(w.i=0 x%xn,w.i); /* 按整型解釋、輸出共享存儲的內(nèi)容 */ bit_print(w.i); /* 從高到低，逐位輸出共享存儲的各bit值 */ 7/23/202226華中科技大學(xué)計(jì)算機(jī)學(xué)院void bit_print(short num) int i,shift=sizeof(short)*CHAR_BIT; int mask=1(shift-1); /* 掩碼mask的最高位為1，其余15位為0* / for(i=1;i=shift;i+) putchar(num & ma

22、sk) = 0)? 0: 1); /* num最高位為1，輸出1 */ num=1; /* num左移1位；等價(jià)于：num = num1 */ if(i%CHAR_BIT=0 & ishift) /* 每輸出8位后，輸出空格 */ putchar( ); putchar(n); 7/23/202227華中科技大學(xué)計(jì)算機(jī)學(xué)院程序中mask最高位為1，其余15位為0，通常稱為掩碼，將它與短整型變量作按位與運(yùn)算用以測試短整型變量的最高位是0還是1。在bit_print函數(shù)中的for循環(huán)中，每循環(huán)一次，通過num=1將次高位移至最高位。w.bit.b9=1和w.bit.b10=1將i的高字節(jié)設(shè)成6，w

23、.byte.byte0=b將i的低字節(jié)設(shè)成62（b的ASCII碼）。bit_print函數(shù)將num在內(nèi)存中的值以二進(jìn)制位的方式輸出。程序的運(yùn)行結(jié)果如下：w.i=0 x66200000110 01100010 7/23/202228華中科技大學(xué)計(jì)算機(jī)學(xué)院*10.9 動態(tài)存儲分配 10.9.1 靜態(tài)數(shù)據(jù)結(jié)構(gòu)和動態(tài)數(shù)據(jù)結(jié)構(gòu)到目前為止，教材中介紹的各種基本類型和導(dǎo)出類型的數(shù)據(jù)結(jié)構(gòu)都是靜態(tài)數(shù)據(jù)結(jié)構(gòu)。靜態(tài)數(shù)據(jù)結(jié)構(gòu)指在變量聲明時(shí)建立的數(shù)據(jù)結(jié)構(gòu)。在變量聲明時(shí)變量的存儲分配也確定了，并且在程序的執(zhí)行過程中不能改變。動態(tài)數(shù)據(jù)結(jié)構(gòu)是在程序運(yùn)行過程中通過調(diào)用系統(tǒng)提供的動態(tài)存儲分配函數(shù)，向系統(tǒng)申請存儲而逐步建立起來的。

24、在程序運(yùn)行過程中，動態(tài)數(shù)據(jù)結(jié)構(gòu)所占存儲的大小可以根據(jù)需要調(diào)節(jié)，使用完畢時(shí)可以通過釋放操作將所獲得的存儲交還給系統(tǒng)供再次分配。由于系統(tǒng)提供的動態(tài)存儲分配函數(shù)的返回值是指向分配存儲的起始地址的指針，因此動態(tài)數(shù)據(jù)對象沒有名字，對動態(tài)數(shù)據(jù)對象的訪問只能通過指針進(jìn)行。 7/23/202229華中科技大學(xué)計(jì)算機(jī)學(xué)院10.9.2 C的動態(tài)存儲分配函數(shù)動態(tài)存儲分配函數(shù)是C的標(biāo)準(zhǔn)函數(shù)，函數(shù)的原型聲明在頭文件中給出。使用動態(tài)存儲分配函數(shù)必須先使用#include 編譯預(yù)處理命令。C提供下列與動態(tài)存儲分配相關(guān)的函數(shù)。void * malloc(size_t size);void * calloc(size_t n,

25、 size_t size);void * realloc(void * p_block, size_t size);void free(void * p_block);其中，size_t表示unsigned int，即無符號整型。它是在中通過typedef unsigned size_t;定義的。 7/23/202230華中科技大學(xué)計(jì)算機(jī)學(xué)院1) malloc函數(shù)的功能 malloc函數(shù)的原型為：void * malloc(size_t size);malloc函數(shù)的功能是向系統(tǒng)申請分配size個(gè)字節(jié)大小的存儲。如果分配成功，返回新分配存儲區(qū)域的首地址；如果分配失?。ㄈ鐑?nèi)存容量不夠），返回NU

26、LL。新分配存儲區(qū)域未被初始化。例如，下面的代碼片斷就利用了malloc函數(shù)動態(tài)創(chuàng)建一個(gè)有6個(gè)元素的整型數(shù)組。int i,*p;p=(int *)malloc(6*sizeof(int);if(p) for(i=0;inum時(shí)，s2指向字符指針(p+i)-num。因此，(*s2)就是(p+i)-num。(*s2)=(char *)malloc(len*sizeof(char)+1);等價(jià)于：(p+i)-num =(char *)malloc(len*sizeof(char)+1);只有將s2聲明為雙重字符針，才能夠使主函數(shù)中的(p+i)-num和(p+i)-name指向在dynamic_inp

27、ut函數(shù)中動態(tài)分配的存儲區(qū)域。7/23/202238華中科技大學(xué)計(jì)算機(jī)學(xué)院void main(void)int n,i;struct c_score_tab *p;printf(input the number of students please!n);scanf(%d,&n);getchar(); /* getchar用于讀結(jié)束scanf輸入的回車符 */p=(struct c_score_tab *)malloc(n*sizeof(struct c_score_tab);assert(p);for(i=0;inumdynamic_input(input name!n,&(p+i)-nam

28、e); printf(input score!n);scanf(%d,&(*(p+i).c); /* 輸入C語言課程成績 */getchar();printf(n);for(i=0;inum,(p+i)-name,(p+i)-c);printf(n);free(p); /* 釋放成績單占據(jù)的存儲 */7/23/202239華中科技大學(xué)計(jì)算機(jī)學(xué)院*10.11 鏈 表鏈表是一種常用的動態(tài)數(shù)據(jù)結(jié)構(gòu)，它由一系列包含數(shù)據(jù)域和指針域的結(jié)點(diǎn)組成。如果結(jié)點(diǎn)的指針域中只包含一個(gè)指向后一個(gè)結(jié)點(diǎn)指針，這種鏈表稱為單向鏈表。如果結(jié)點(diǎn)的指針域包含兩個(gè)指針，且一個(gè)指向前一個(gè)結(jié)點(diǎn)，另一個(gè)指向后一個(gè)結(jié)點(diǎn)，這種鏈表稱為雙向鏈表

29、。如果結(jié)點(diǎn)的指針域包含兩個(gè)指針，且一個(gè)指向后一個(gè)結(jié)點(diǎn)，另一個(gè)指向另外一個(gè)鏈表，這種鏈表稱為十字交叉鏈表。 7/23/202240華中科技大學(xué)計(jì)算機(jī)學(xué)院10.11.1 自引用結(jié)構(gòu)如果一個(gè)結(jié)構(gòu)類型中包含一個(gè)該結(jié)構(gòu)類型的指針，稱該結(jié)構(gòu)類型為自引用結(jié)構(gòu)類型，對應(yīng)的結(jié)構(gòu)變量稱為自引用結(jié)構(gòu)變量，自引用結(jié)構(gòu)變量常常簡稱為自引用結(jié)構(gòu)。自引用結(jié)構(gòu)的指針成員是一個(gè)指向該自引用結(jié)構(gòu)的指針。因此，關(guān)于自引用結(jié)構(gòu)的定義也可以表示為：如果一個(gè)結(jié)構(gòu)中包含一個(gè)指向該結(jié)構(gòu)自身的指針，該結(jié)構(gòu)稱為自引用結(jié)構(gòu)。 7/23/202241華中科技大學(xué)計(jì)算機(jī)學(xué)院自引用結(jié)構(gòu)struct s_list int data; struct s_l

30、ist *next; node1=1,NULL;由于struct s_list結(jié)構(gòu)類型中，next是指向struct s_list結(jié)構(gòu)類型變量的指針（稱為指向自身的指針），因此struct s_list結(jié)構(gòu)類型是自引用結(jié)構(gòu)類型。而node1是自引用結(jié)構(gòu)變量（自引用結(jié)構(gòu)）。 7/23/202242華中科技大學(xué)計(jì)算機(jī)學(xué)院自引用結(jié)構(gòu)變量（自引用結(jié)構(gòu)）執(zhí)行下面語句：struct s_list node2,node3;node2.data=2;node3.data=3;node2.next=node3.next=NULL;則node1,node2,node3的存儲結(jié)構(gòu)如圖所示。 node1 node2

31、node37/23/202243華中科技大學(xué)計(jì)算機(jī)學(xué)院例10.16 以自引用結(jié)構(gòu)node1、node2和node3為“結(jié)點(diǎn)”構(gòu)建“鏈表”。 #include stdio.hstruct s_listint data;struct s_list *next; node1=1,NULL;void main(void)struct s_list node2,node3;struct s_list *head=NULL,*p;node2.data=2;node3.data=3;node2.next=node3.next= NULL;head=&node1; node1.next=&node2; nod

32、e2.next=&node3; p=head; printf(%pt%pn,&head, head);while(p) printf(%pt%dt%pn, p,p-data,p-nextp=p-next; 7/23/202244華中科技大學(xué)計(jì)算機(jī)學(xué)院程序中head稱為頭指針，head=&node1使head指向了node1；node1.next=&node2使node1指向了node2；node2.next=&node3使node2指向了node3。p稱為遍歷指針, p=p-next使p指向了下一個(gè)自引用結(jié)構(gòu)。對“結(jié)點(diǎn)”和“鏈表”加一個(gè)引號，表明上面程序創(chuàng)建的各個(gè)自引用結(jié)構(gòu)之間的指向關(guān)系與實(shí)際

33、鏈表一致，但存儲分配是靜態(tài)而不是動態(tài)的。程序的運(yùn)行結(jié)果如下：FFD4 01940194 1 FFCCFFCC 2 FFD0FFD0 3 00007/23/202245華中科技大學(xué)計(jì)算機(jī)學(xué)院10.11.2 動態(tài)創(chuàng)建結(jié)點(diǎn)可以通過（結(jié)點(diǎn)指針類型）malloc(sizeof(結(jié)點(diǎn)類型)的方式來動態(tài)創(chuàng)建結(jié)點(diǎn)。如：p=(struct s_list *)malloc(sizeof(struct s_list)它通過動態(tài)存儲分配創(chuàng)建一個(gè)struct s_list的自引用結(jié)構(gòu)變量作為結(jié)點(diǎn)，并將返回值的類型強(qiáng)制轉(zhuǎn)換為自引用結(jié)構(gòu)類型的指針并賦給指針p。 7/23/202246華中科技大學(xué)計(jì)算機(jī)學(xué)院例1017 從頭指

34、針開始,動態(tài)創(chuàng)建三個(gè)結(jié)點(diǎn)，并使用頭指針head訪問后繼三個(gè)結(jié)點(diǎn)。相關(guān)解釋以注釋的方式給出。 struct s_listint data;struct s_list *next; ;void main(void)struct s_list *head=NULL,*p;head=(struct s_list *) malloc(sizeof(struct s_list);head-data=1;head-next=(struct s_list *) malloc(sizeof(struct s_list);head-next-data=2;head-next-next=(struct s_list

35、 *) malloc(sizeof(struct s_list);head-next-next-data=3;head-next-next-next=NULL;p=head;while(p)printf(%pt%dt%pn, p,p-data,p-next);p=p-next; 7/23/202247華中科技大學(xué)計(jì)算機(jī)學(xué)院10.11.3 單向鏈表在單向鏈表中，結(jié)點(diǎn)的指針域中只包含一個(gè)指向其自身的指針，用于指向后繼結(jié)點(diǎn)。頭指針指向鏈表中稱為鏈頭的第一個(gè)結(jié)點(diǎn)，從第一個(gè)結(jié)點(diǎn)開始，每個(gè)結(jié)點(diǎn)的指針成員都指向其后繼結(jié)點(diǎn)，最后一個(gè)稱為鏈尾的結(jié)點(diǎn)的指針域?yàn)榭罩羔楴ULL。struct s_list結(jié)構(gòu)中由于數(shù)

36、據(jù)域內(nèi)只有一個(gè)整型數(shù)據(jù)，以此為結(jié)點(diǎn)構(gòu)成的鏈表一般都稱為整數(shù)鏈表。設(shè)所討論的結(jié)點(diǎn)為當(dāng)前結(jié)點(diǎn)，則它前面的一個(gè)結(jié)點(diǎn)稱為直接前驅(qū)結(jié)點(diǎn)（簡稱前驅(qū)）；它后面的一個(gè)結(jié)點(diǎn)稱為直接后繼結(jié)點(diǎn)（簡稱后繼）。 7/23/202248華中科技大學(xué)計(jì)算機(jī)學(xué)院例10.18 給定一批整數(shù)，以0作為結(jié)束標(biāo)志且不作為結(jié)點(diǎn)，將其建成一個(gè)先進(jìn)先出的鏈表，先進(jìn)先出鏈表的指頭指針始終指向最先創(chuàng)建的結(jié)點(diǎn)（鏈頭），先建結(jié)點(diǎn)指向后建結(jié)點(diǎn)，后建結(jié)點(diǎn)始終是尾結(jié)點(diǎn)。結(jié)點(diǎn)自引用結(jié)構(gòu)類型的聲明和創(chuàng)建鏈表函數(shù)原型的聲明如下：#include stdio.h#include stdlib.h“struct s_list int data; /* 數(shù)據(jù)域 *

37、/struct s_list *next; /* 指針域 */ ;void create_list_v1(struct s_list *headp,int *p); 7/23/202249華中科技大學(xué)計(jì)算機(jī)學(xué)院1用循環(huán)方式建立先進(jìn)先出鏈表建立一個(gè)非空先進(jìn)先出鏈表相關(guān)算法步驟如下：（1）聲明頭指針，尾指針。struct s_list * loc_head=NULL,*tail; （2）創(chuàng)建第一個(gè)結(jié)點(diǎn)。包括：（2-1）給第一個(gè)結(jié)點(diǎn)動態(tài)分配存儲并使頭指針指向第一個(gè)結(jié)點(diǎn)。loc_head=(struct s_list *)malloc(sizeof(struct s_list);（2-2）給第一個(gè)結(jié)點(diǎn)

38、的數(shù)據(jù)域中成員賦值。loc_head-data=*p+;（2-3）使尾指針也指向第一個(gè)結(jié)點(diǎn)。tail=loc_head;（3）循環(huán)建立后續(xù)結(jié)點(diǎn)（3-1）如果沒遇到結(jié)束標(biāo)志0，進(jìn)行下列操作：（3-1-1）給后繼結(jié)點(diǎn)動態(tài)分配存儲并使前驅(qū)結(jié)點(diǎn)的指針指向后繼結(jié)點(diǎn)。tail-next=(struct s_list *)malloc(sizeof(struct s_list);（3-1-2）使尾指針指向新建立的后繼結(jié)點(diǎn)tail=tail-next;（3-1-3）給后繼結(jié)點(diǎn)的數(shù)據(jù)域中成員賦值。tail-data=*p+;（3-1-4）轉(zhuǎn)（3-1）（4）給尾結(jié)點(diǎn)（最后一個(gè)結(jié)點(diǎn)）的指針賦NULL值。tail-n

39、ext=NULL;7/23/202250華中科技大學(xué)計(jì)算機(jī)學(xué)院根據(jù)算法步驟設(shè)計(jì)的創(chuàng)建鏈表函數(shù)的如下:void create_list_v1(struct s_list *headp,int *p)struct s_list * loc_head=NULL,*tail;if(p0=0) /* 相當(dāng)于*p=0 */;else /* loc_head指向動態(tài)分配的第一個(gè)結(jié)點(diǎn) */loc_head=(struct s_list *)malloc(sizeof(struct s_list);loc_head-data=*p+; /* 對數(shù)據(jù)域賦值 */tail=loc_head; /* tail指向第一

40、個(gè)結(jié)點(diǎn) */while(*p) /* tail所指結(jié)點(diǎn)的指針域指向動態(tài)創(chuàng)建的結(jié)點(diǎn) */tail-next=(struct s_list *)malloc(sizeof(struct s_list);tail=tail-next; /* tail指向新創(chuàng)建的結(jié)點(diǎn) */tail-data=*p+; /* 向新創(chuàng)建的結(jié)點(diǎn)的數(shù)據(jù)域賦值 */tail-next=NULL; /* 對指針域賦NULL值 */*headp=loc_head; /* 使頭指針headp指向新創(chuàng)建的鏈表 */ 其中，headp是指向鏈表頭指針的指針，類型是struct s_list *headp，為雙重指針，它指向的是main函

41、數(shù)中的head。*headp即main函數(shù)中的head，*headp=loc_head使main函數(shù)中的頭指針head指向新創(chuàng)建的鏈表。7/23/202251華中科技大學(xué)計(jì)算機(jī)學(xué)院在main函數(shù)中調(diào)用create_list_v1 void main(void)struct s_list *head=NULL,*p;int s=1,2,3,4,5,6,7,8,0; /* 0為結(jié)束標(biāo)記 */create_list_v1(&head,s); /* 創(chuàng)建新鏈表 */p=head; /*遍歷指針p指向鏈頭 */while(p)printf(%dt,p-data); p=p-next; /*遍歷指針p指向

42、下一結(jié)點(diǎn) */printf(n); 7/23/202252華中科技大學(xué)計(jì)算機(jī)學(xué)院遍歷鏈表的算法步驟 （1）初始化，使遍歷指針p指向頭結(jié)點(diǎn)。 p=head;（2）如果鏈表非空（即遍歷指針p非空，p！=NULL）（2-1）輸出結(jié)點(diǎn)數(shù)據(jù)域中成員的值。printf(%dt,p-data);（2-2）使遍歷指針p指向下一個(gè)結(jié)點(diǎn)。p=p-next;（2-3）轉(zhuǎn)（2）main函數(shù)中給出了根據(jù)算法步驟設(shè)計(jì)的程序。 7/23/202253華中科技大學(xué)計(jì)算機(jī)學(xué)院2用遞歸方式建立先進(jìn)先出鏈表struct s_list *create_list_v2(int *);struct s_list *create_list

43、_v2(int *p)struct s_list * loc_head=NULL;if(p0=0) /* 遇到結(jié)束標(biāo)記，返回NULL */return NULL;else /* loc_head指向新創(chuàng)建的結(jié)點(diǎn) */loc_head=(struct s_list *)malloc(sizeof(struct s_list);loc_head-data=*p; /* 對新創(chuàng)建結(jié)點(diǎn)的數(shù)據(jù)域賦值 */ loc_head-next=create_list_v2(p+1); /* 遞歸創(chuàng)建下一結(jié)點(diǎn) */return loc_head; /* 返回鏈頭地址 */ 7/23/202254華中科技大學(xué)計(jì)算機(jī)學(xué)

44、院create_list_v2是一個(gè)struct s_list類型的指針函數(shù)，即，它返回值的類型是struct s_list *。它遞歸的建立鏈表中的各個(gè)結(jié)點(diǎn)，當(dāng)遇到結(jié)束標(biāo)志時(shí)（p0=0），該次調(diào)用返回NULL值，而NULL值將作為前一次調(diào)用中所建立結(jié)點(diǎn)指針域的值.注意：由于遞歸調(diào)用時(shí)用p+1做實(shí)參，p0即*p，最后一次必然引用s8，即0。如果p0不為0，則建立結(jié)點(diǎn)，給結(jié)點(diǎn)的數(shù)據(jù)域中成員賦值，遞歸調(diào)用建立下一個(gè)結(jié)點(diǎn)，并將建立下一個(gè)結(jié)點(diǎn)操作的地址返回賦給結(jié)點(diǎn)的指針域。遞歸調(diào)用將后繼結(jié)點(diǎn)的地址返回并賦給前驅(qū)結(jié)點(diǎn)的指針域。另外，只要將前面main函數(shù)進(jìn)行修改，將create_list_v1(&hea

45、d,s);語句改為：head=create_list_v2(s);則main函數(shù)就可以完成對create_list_v2的調(diào)用，得到與1中完全相同的結(jié)果。 7/23/202255華中科技大學(xué)計(jì)算機(jī)學(xué)院10.11.4 鏈表的相關(guān)操作鏈表的相關(guān)操作包括：創(chuàng)建鏈表;遍歷鏈表;在鏈表中插入一個(gè)結(jié)點(diǎn);刪除鏈表中的一個(gè)結(jié)點(diǎn);同類型鏈表的歸并;鏈表的排序等。 7/23/202256華中科技大學(xué)計(jì)算機(jī)學(xué)院1遍歷鏈表遍歷鏈表可以進(jìn)一步分為遍歷鏈表，輸出鏈表中各個(gè)結(jié)點(diǎn)的數(shù)據(jù)域成員；遍歷鏈表，統(tǒng)計(jì)鏈表中結(jié)點(diǎn)的數(shù)目；遍歷鏈表，查找鏈表中符合條件的某個(gè)結(jié)點(diǎn)等。其中輸出鏈表中各個(gè)結(jié)點(diǎn)的數(shù)據(jù)域成員已經(jīng)介紹。7/23/202

46、257華中科技大學(xué)計(jì)算機(jī)學(xué)院例10.19 用循環(huán)遍歷的方式統(tǒng)計(jì)鏈表中結(jié)點(diǎn)的數(shù)目（即鏈表的長度）。int count_nodes(struct s_list * head)struct s_list * p=head;int num=0;while(p)num+;p=p-next;return num; 7/23/202258華中科技大學(xué)計(jì)算機(jī)學(xué)院例10.20 用遞歸遍歷的方式統(tǒng)計(jì)鏈表中結(jié)點(diǎn)的數(shù)目。int count_nodes_recursive(struct s_list * head)struct s_list * p=head;if(p) return (1+count_nodes_re

47、cursive(p-next);elsereturn 0;7/23/202259華中科技大學(xué)計(jì)算機(jī)學(xué)院例10.21 用遞歸方式查找鏈表中數(shù)據(jù)成員值與形參n相同的結(jié)點(diǎn)。如果有，返回該結(jié)點(diǎn)的地址，如果沒有，返回NULL。 struct s_list * find_nodes_recursive(struct s_list * head,int n)struct s_list * p=head;if(p) /* 鏈表非空，查找 */if(p-data=n &p!=NULL)return p; /* 找到，返回該結(jié)點(diǎn)的地址 */elsefind_nodes_recursive(p-next,n);/*

48、 遞歸查找 */else return NULL; 7/23/202260華中科技大學(xué)計(jì)算機(jī)學(xué)院2插入結(jié)點(diǎn)在鏈表中插入一個(gè)結(jié)點(diǎn)的操作是指在鏈中滿足給定條件結(jié)點(diǎn)（即插入點(diǎn)）的前或后加入一個(gè)新的結(jié)點(diǎn)。 因此，首先要根據(jù)給定條件遍歷鏈表，確定插入點(diǎn)的位置.插入點(diǎn)的位置可能是鏈頭、鏈尾、或者鏈中。插入方式有將加入結(jié)點(diǎn)作為插入點(diǎn)的新后繼結(jié)點(diǎn)和插入點(diǎn)的新前驅(qū)結(jié)點(diǎn)兩種。本節(jié)按照先進(jìn)先出鏈的規(guī)定，將加入結(jié)點(diǎn)作為插入點(diǎn)的新后繼結(jié)點(diǎn)。至于將加入結(jié)點(diǎn)作為插入點(diǎn)的新前驅(qū)結(jié)點(diǎn)的插入方法請讀者自行考慮。如果插入點(diǎn)是鏈尾，插入方法與建立先進(jìn)先出鏈的方法相同。如果插入點(diǎn)是鏈頭或鏈中，則需要兩個(gè)遍歷指針，一個(gè)是指向插入點(diǎn)的遍歷

49、指針current，另一個(gè)是指向插入點(diǎn)后繼結(jié)點(diǎn)的遍歷指針after。設(shè)新結(jié)點(diǎn)由other指針?biāo)?，它將插入在current和after所指結(jié)點(diǎn)之間。插入前結(jié)點(diǎn)間的指向關(guān)系如圖10.3所示。7/23/202261華中科技大學(xué)計(jì)算機(jī)學(xué)院插入前結(jié)點(diǎn)間的指向關(guān)系如圖10.3所示則 操作為： other-next=after; 操作為： current-next=other;插入后結(jié)點(diǎn)間的指向關(guān)系如圖10.4所示。7/23/202262華中科技大學(xué)計(jì)算機(jī)學(xué)院例10.22 在鏈表中數(shù)據(jù)成員的值與形參n相等的結(jié)點(diǎn)后面插入一個(gè)新的結(jié)點(diǎn)，給結(jié)點(diǎn)的數(shù)據(jù)成員賦值，并返回插入點(diǎn)的地址。struct s_list *

50、insert_nodes(struct s_list * head,int n)struct s_list * current=head,*after,*other;while(current-data!=n¤t!=NULL)current=current-next;if(!current) return NULL;after=current-next; other = (struct s_list *) malloc(sizeof(struct s_list);scanf(%d,&other-data); if(after)other-next=after; current-ne

51、xt=other; elseother-next=NULL; current-next=other; return current; 7/23/202263華中科技大學(xué)計(jì)算機(jī)學(xué)院3刪除結(jié)點(diǎn)刪除結(jié)點(diǎn)的操作是插入結(jié)點(diǎn)操作的逆操作。假設(shè)鏈表如圖10.5，且要?jiǎng)h除current指針指向的結(jié)點(diǎn)，則刪除該結(jié)點(diǎn)就是要將該結(jié)點(diǎn)從鏈表中孤立出來，形成圖10.6的鏈表。同時(shí)要釋放被刪除結(jié)點(diǎn)的存儲。圖中after指針僅為示意用，程序中不必用after指針。7/23/202264華中科技大學(xué)計(jì)算機(jī)學(xué)院刪除結(jié)點(diǎn)示意圖 7/23/202265華中科技大學(xué)計(jì)算機(jī)學(xué)院刪除結(jié)點(diǎn)算法描述刪除結(jié)點(diǎn)就是使該結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)指向其后繼結(jié)

52、點(diǎn)。為此需要指向被刪除結(jié)點(diǎn)的遍歷指針current和指向被刪除結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)的遍歷指針prior。結(jié)點(diǎn)間的指向關(guān)系為：刪除前：prior-next=current; 即:prior-next指向被刪結(jié)點(diǎn)。刪除后：prior-next=after;或 prior-next= current-next; 或 prior-next= prior-next-next;即:prior-next指向被刪結(jié)點(diǎn)的后繼結(jié)點(diǎn)。 7/23/202266華中科技大學(xué)計(jì)算機(jī)學(xué)院例10.23 寫一個(gè)函數(shù)，查找鏈表中數(shù)據(jù)成員的值與形參n相等的結(jié)點(diǎn)，如果找到，刪除該結(jié)點(diǎn)，并返回插入點(diǎn)的地址；如果沒有找到，返回NULL。 st

53、ruct s_list * delete_nodes(struct s_list *headp,int n)struct s_list * current=*headp,*prior=*headp;while(current-data!=n ¤t)/* 查找數(shù)據(jù)成員值與形參n相等的結(jié)點(diǎn) */prior=current; /* prior指向當(dāng)前結(jié)點(diǎn) */current=current-next; /* current指向下一結(jié)點(diǎn) */if(!current) /* 沒有符合條件的結(jié)點(diǎn) */return NULL;if(current=*headp) /* 被刪結(jié)點(diǎn)是鏈頭*/*hea

54、dp=current-next;else /* 被刪結(jié)點(diǎn)不是鏈頭 */prior-next= current-next;free(current); /* 釋放被刪結(jié)點(diǎn)的存儲 */return current; 7/23/202267華中科技大學(xué)計(jì)算機(jī)學(xué)院4歸并鏈表對于非空鏈表A、B,將鏈表B歸并到鏈表A指將鏈表A的鏈尾指向鏈表B的鏈頭所形成的一個(gè)新的鏈表。因此，首先要遍歷鏈表A找到其鏈尾，然后將鏈表B的頭指針值賦給鏈表A鏈尾的指針域即可。具體編程實(shí)現(xiàn)時(shí)，仍然要聲明兩個(gè)遍歷指針current和prior，prior仍然是指向current指針?biāo)附Y(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)。這樣，在遍歷鏈表的過程中，當(dāng)cu

55、rrent為空時(shí)，prior則指向的是鏈尾。 7/23/202268華中科技大學(xué)計(jì)算機(jī)學(xué)院例10.24 寫一個(gè)函數(shù)，對兩個(gè)鏈表進(jìn)行歸并。void concatenate_lists(struct s_list *headA,struct s_list *headB)struct s_list * current=headA,*prior;while(current)prior=current;current=current-next;prior-next=headB;調(diào)用concatenate_lists函數(shù)做歸并操作時(shí)，必須用兩個(gè)鏈表的頭指針作為實(shí)參。 7/23/202269華中科技大學(xué)計(jì)算

56、機(jī)學(xué)院5鏈表排序鏈表排序是指將鏈表的結(jié)點(diǎn)按某個(gè)數(shù)據(jù)域從小到大（升序）或從大到小（降序）的順序連接。鏈表排序算法的思路與數(shù)組排序類似，鏈表中的結(jié)點(diǎn)類似于數(shù)組中的元素，但數(shù)組中元素的存儲是連續(xù)的，可以用下標(biāo)索引，而鏈表中各結(jié)點(diǎn)在存儲方面并不連續(xù)，因此鏈表的結(jié)點(diǎn)只能用指針引用。排序中對鏈表結(jié)點(diǎn)的交換有兩種方法，一種是交換結(jié)點(diǎn)的數(shù)據(jù)域，不改變結(jié)點(diǎn)間的指向關(guān)系。另一種是改變結(jié)點(diǎn)的連接實(shí)現(xiàn)結(jié)點(diǎn)的交換，操作較為復(fù)雜。在數(shù)據(jù)域較為簡單的情況下，多采用交換結(jié)點(diǎn)的數(shù)據(jù)域的方法進(jìn)行鏈表排序。7/23/202270華中科技大學(xué)計(jì)算機(jī)學(xué)院例10.25 寫一個(gè)函數(shù)，采用交換結(jié)點(diǎn)數(shù)據(jù)域的方法實(shí)現(xiàn)對鏈表的升序排序。 void sort_lists(struct s_list *head);void sort_lists(struct s_list *head)struct s_list *p1=head,*p2;int len=0,i,j,t;while(p1) /* 計(jì)算鏈表的長度 */len+;p1=p1-next;for(i=0,p1=head;inext)for(j=i+1,p2=p1-next;jnext)if(p1-data p2-data)t=p1-data; /* 交換數(shù)據(jù)域 */p1-data=p2-data;p2-data=t; 7/23/202271華中科技大學(xué)計(jì)算機(jī)學(xué)院如果采用冒泡