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

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

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

4、大學計算機學院例10.12 通過例子對聯合的特性進行進一步分析。#include stdio.hunion chl charc; shorth; longl;void show(union chl *pu);void show_memoy(union chl *pu); 7/23/20226華中科技大學計算機學院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華中科技大學計算機學院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”操作符來引用聯合成員。從u.l，(*pu).c，pu-h三個表達式中可以歸納出對聯合成員的引用形式為：（1）聯合變量名.成員名。（2）(*指向聯合變量的指針).成員名。

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

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

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

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

10、，再聲明字段結構變量，然后再對字段結構變量中的成員進行操作。考慮十字路口的交通燈 .顏色枚舉類型的聲明如下：enum color OFF=0,RED=1,YELLOW=2,GREEN=3; 7/23/202216華中科技大學計算機學院struct traffic_lightunsigned short int east:2;/* 東組燈狀態字段 */unsigned short int south:2;/* 南組燈狀態字段 */unsigned short int west:2;/* 西組燈狀態字段 */unsigned short int north:2;/* 北組燈狀態字段 */unsig

11、ned short int reserve:8; /* 保留字段 */unsigned short int east_on:4; /* 東組燈開通時間 */unsigned short int south_on:4;/* 南組燈開通時間 */unsigned short int west_on:4;/* 西組燈開通時間 */unsigned short int north_on:4;/* 北組燈開通時間 */; 4組交通燈的字段結構類型的聲明7/23/202217華中科技大學計算機學院4組交通燈的字段結構類型的簡略形式聲明 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;上面聲明了一個struct traffic_light的字段結構類型，east、south、north_on為它的字段成員，字段成員往往也簡稱為字段。冒號后面的整數說明了成員的字段寬度，字段寬度是一個非負的整型常量表達式。上面定義中，其中字段寬度為2的四個成員用unsigned char更加簡練，但Turbo C中不支持unsigned char，因此用unsigned short in

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

14、段結構變量并對其成員進行初始化。如： 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;字段就是一個小整數，它可以出現在其它整數可以出現的任何地方。字段在參與運算時被自動轉換為int或unsigned int類型的整數。對一個字段結構中成員的引用與對一般結構變量中結構成員的引用方法相

15、同，有“.”和“-”兩種。如：Jiedaokou.west，Jiedaokou.west_on，p-north，p-north_on等。 7/23/202220華中科技大學計算機學院例10.13 字段結構變量的成員引用舉例。 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);程序的運行結果如下：Jiedaokou.west=3 Jiedaokou.west_on=5Jiedaokou.east=0 Jiedaokou.east_on=0 7/23/202221華中科技大學計算機學院字段成員的寬度問題由于字段成員表示整數的范圍有限，在對字段成員賦值時不要超出了它表示數的范圍。如果超出了它表示數的范圍，則數的高位部分將被丟棄。如Jiedaokou.west_on的寬度為4，它

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

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

19、節;將字段b0b15寬度定義為1，用以表示一個16位字中的各個二進制位。并且用聯合使一個短整型變量、2個字節字段與16個位字段共享共同的存儲。 7/23/202224華中科技大學計算機學院例10.14 用字段和聯合訪問一個16位字中的高低字節和各二進制位的應用舉例。#include stdio.h#define CHAR_BIT 8struct w16_bytes unsigned short byte0:8,byte1:8; /* byte0為低字節,byte1為高字節 */ ;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華中科技大學計算機學院union w16 /* 短整型變量、結構成員byte、結構成員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; /* 相當于byte1為2 */ w.

21、bit.b10=1; /* 相當于byte1為6 */ w.byte.byte0=b; printf(w.i=0 x%xn,w.i); /* 按整型解釋、輸出共享存儲的內容 */ bit_print(w.i); /* 從高到低，逐位輸出共享存儲的各bit值 */ 7/23/202226華中科技大學計算機學院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位；等價于：num = num1 */ if(i%CHAR_BIT=0 & ishift) /* 每輸出8位后，輸出空格 */ putchar( ); putchar(n); 7/23/202227華中科技大學計算機學院程序中mask最高位為1，其余15位為0，通常稱為掩碼，將它與短整型變量作按位與運算用以測試短整型變量的最高位是0還是1。在bit_print函數中的for循環中，每循環一次，通過num=1將次高位移至最高位。w.bit.b9=1和w.bit.b10=1將i的高字節設成6，w

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

24、在程序運行過程中，動態數據結構所占存儲的大小可以根據需要調節，使用完畢時可以通過釋放操作將所獲得的存儲交還給系統供再次分配。由于系統提供的動態存儲分配函數的返回值是指向分配存儲的起始地址的指針，因此動態數據對象沒有名字，對動態數據對象的訪問只能通過指針進行。 7/23/202229華中科技大學計算機學院10.9.2 C的動態存儲分配函數動態存儲分配函數是C的標準函數，函數的原型聲明在頭文件中給出。使用動態存儲分配函數必須先使用#include 編譯預處理命令。C提供下列與動態存儲分配相關的函數。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華中科技大學計算機學院1) malloc函數的功能 malloc函數的原型為：void * malloc(size_t size);malloc函數的功能是向系統申請分配size個字節大小的存儲。如果分配成功，返回新分配存儲區域的首地址；如果分配失敗（如內存容量不夠），返回NU

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

27、ut函數中動態分配的存儲區域。7/23/202238華中科技大學計算機學院void main(void)int n,i;struct c_score_tab *p;printf(input the number of students please!n);scanf(%d,&n);getchar(); /* getchar用于讀結束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); /* 釋放成績單占據的存儲 */7/23/202239華中科技大學計算機學院*10.11 鏈 表鏈表是一種常用的動態數據結構，它由一系列包含數據域和指針域的結點組成。如果結點的指針域中只包含一個指向后一個結點指針，這種鏈表稱為單向鏈表。如果結點的指針域包含兩個指針，且一個指向前一個結點，另一個指向后一個結點，這種鏈表稱為雙向鏈表

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

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

31、node37/23/202243華中科技大學計算機學院例10.16 以自引用結構node1、node2和node3為“結點”構建“鏈表”。 #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華中科技大學計算機學院程序中head稱為頭指針，head=&node1使head指向了node1；node1.next=&node2使node1指向了node2；node2.next=&node3使node2指向了node3。p稱為遍歷指針, p=p-next使p指向了下一個自引用結構。對“結點”和“鏈表”加一個引號，表明上面程序創建的各個自引用結構之間的指向關系與實際

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

34、針開始,動態創建三個結點，并使用頭指針head訪問后繼三個結點。相關解釋以注釋的方式給出。 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華中科技大學計算機學院10.11.3 單向鏈表在單向鏈表中，結點的指針域中只包含一個指向其自身的指針，用于指向后繼結點。頭指針指向鏈表中稱為鏈頭的第一個結點，從第一個結點開始，每個結點的指針成員都指向其后繼結點，最后一個稱為鏈尾的結點的指針域為空指針NULL。struct s_list結構中由于數

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

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

38、的數據域中成員賦值。loc_head-data=*p+;（2-3）使尾指針也指向第一個結點。tail=loc_head;（3）循環建立后續結點（3-1）如果沒遇到結束標志0，進行下列操作：（3-1-1）給后繼結點動態分配存儲并使前驅結點的指針指向后繼結點。tail-next=(struct s_list *)malloc(sizeof(struct s_list);（3-1-2）使尾指針指向新建立的后繼結點tail=tail-next;（3-1-3）給后繼結點的數據域中成員賦值。tail-data=*p+;（3-1-4）轉（3-1）（4）給尾結點（最后一個結點）的指針賦NULL值。tail-n

39、ext=NULL;7/23/202250華中科技大學計算機學院根據算法步驟設計的創建鏈表函數的如下:void create_list_v1(struct s_list *headp,int *p)struct s_list * loc_head=NULL,*tail;if(p0=0) /* 相當于*p=0 */;else /* loc_head指向動態分配的第一個結點 */loc_head=(struct s_list *)malloc(sizeof(struct s_list);loc_head-data=*p+; /* 對數據域賦值 */tail=loc_head; /* tail指向第一

40、個結點 */while(*p) /* tail所指結點的指針域指向動態創建的結點 */tail-next=(struct s_list *)malloc(sizeof(struct s_list);tail=tail-next; /* tail指向新創建的結點 */tail-data=*p+; /* 向新創建的結點的數據域賦值 */tail-next=NULL; /* 對指針域賦NULL值 */*headp=loc_head; /* 使頭指針headp指向新創建的鏈表 */ 其中，headp是指向鏈表頭指針的指針，類型是struct s_list *headp，為雙重指針，它指向的是main函

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

42、下一結點 */printf(n); 7/23/202252華中科技大學計算機學院遍歷鏈表的算法步驟 （1）初始化，使遍歷指針p指向頭結點。 p=head;（2）如果鏈表非空（即遍歷指針p非空，p！=NULL）（2-1）輸出結點數據域中成員的值。printf(%dt,p-data);（2-2）使遍歷指針p指向下一個結點。p=p-next;（2-3）轉（2）main函數中給出了根據算法步驟設計的程序。 7/23/202253華中科技大學計算機學院2用遞歸方式建立先進先出鏈表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) /* 遇到結束標記，返回NULL */return NULL;else /* loc_head指向新創建的結點 */loc_head=(struct s_list *)malloc(sizeof(struct s_list);loc_head-data=*p; /* 對新創建結點的數據域賦值 */ loc_head-next=create_list_v2(p+1); /* 遞歸創建下一結點 */return loc_head; /* 返回鏈頭地址 */ 7/23/202254華中科技大學計算機學

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

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

46、257華中科技大學計算機學院例10.19 用循環遍歷的方式統計鏈表中結點的數目（即鏈表的長度）。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華中科技大學計算機學院例10.20 用遞歸遍歷的方式統計鏈表中結點的數目。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華中科技大學計算機學院例10.21 用遞歸方式查找鏈表中數據成員值與形參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; /* 找到，返回該結點的地址 */elsefind_nodes_recursive(p-next,n);/*

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

49、指針current，另一個是指向插入點后繼結點的遍歷指針after。設新結點由other指針所指，它將插入在current和after所指結點之間。插入前結點間的指向關系如圖10.3所示。7/23/202261華中科技大學計算機學院插入前結點間的指向關系如圖10.3所示則 操作為： other-next=after; 操作為： current-next=other;插入后結點間的指向關系如圖10.4所示。7/23/202262華中科技大學計算機學院例10.22 在鏈表中數據成員的值與形參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華中科技大學計算機學院3刪除結點刪除結點的操作是插入結點操作的逆操作。假設鏈表如圖10.5，且要刪除current指針指向的結點，則刪除該結點就是要將該結點從鏈表中孤立出來，形成圖10.6的鏈表。同時要釋放被刪除結點的存儲。圖中after指針僅為示意用，程序中不必用after指針。7/23/202264華中科技大學計算機學院刪除結點示意圖 7/23/202265華中科技大學計算機學院刪除結點算法描述刪除結點就是使該結點的前驅結點指向其后繼結

52、點。為此需要指向被刪除結點的遍歷指針current和指向被刪除結點的前驅結點的遍歷指針prior。結點間的指向關系為：刪除前：prior-next=current; 即:prior-next指向被刪結點。刪除后：prior-next=after;或 prior-next= current-next; 或 prior-next= prior-next-next;即:prior-next指向被刪結點的后繼結點。 7/23/202266華中科技大學計算機學院例10.23 寫一個函數，查找鏈表中數據成員的值與形參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)/* 查找數據成員值與形參n相等的結點 */prior=current; /* prior指向當前結點 */current=current-next; /* current指向下一結點 */if(!current) /* 沒有符合條件的結點 */return NULL;if(current=*headp) /* 被刪結點是鏈頭*/*hea

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

55、rrent為空時，prior則指向的是鏈尾。 7/23/202268華中科技大學計算機學院例10.24 寫一個函數，對兩個鏈表進行歸并。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;調用concatenate_lists函數做歸并操作時，必須用兩個鏈表的頭指針作為實參。 7/23/202269華中科技大學計算

56、機學院5鏈表排序鏈表排序是指將鏈表的結點按某個數據域從小到大（升序）或從大到小（降序）的順序連接。鏈表排序算法的思路與數組排序類似，鏈表中的結點類似于數組中的元素，但數組中元素的存儲是連續的，可以用下標索引，而鏈表中各結點在存儲方面并不連續，因此鏈表的結點只能用指針引用。排序中對鏈表結點的交換有兩種方法，一種是交換結點的數據域，不改變結點間的指向關系。另一種是改變結點的連接實現結點的交換，操作較為復雜。在數據域較為簡單的情況下，多采用交換結點的數據域的方法進行鏈表排序。7/23/202270華中科技大學計算機學院例10.25 寫一個函數，采用交換結點數據域的方法實現對鏈表的升序排序。 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) /* 計算鏈表的長度 */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; /* 交換數據域 */p1-data=p2-data;p2-data=t; 7/23/202271華中科技大學計算機學院如果采用冒泡