C語言程序設(shè)計(jì)

1、C語言程序設(shè)計(jì)語言程序設(shè)計(jì) 第10章 指針 v15.2 鏈表的相關(guān)概念 v15.2 鏈表的操作 C語言程序設(shè)計(jì)語言程序設(shè)計(jì) 15.2 鏈表的相關(guān)概念 v鏈表是由一個(gè)個(gè)結(jié)點(diǎn)順序連接起來構(gòu)成的表，稱為鏈表。 其中，結(jié)點(diǎn)用來存放元素信息和下一個(gè)元素的地址。鏈表 中的元素在邏輯上相鄰，在物理上不一定相鄰。而數(shù)組中 的元素邏輯上相鄰，在物理上也一定相鄰。本節(jié)主要講解 鏈表的基本概念和動(dòng)態(tài)內(nèi)存分配。 C語言程序設(shè)計(jì)語言程序設(shè)計(jì) 15.1 鏈表的相關(guān)概念 v15.1.1 鏈表鏈表 v1鏈表鏈表 v鏈表是由結(jié)點(diǎn)連接而成，結(jié)點(diǎn)就表示一個(gè)元素的信息。鏈表是由結(jié)點(diǎn)連接而成，結(jié)點(diǎn)就表示一個(gè)元素的信息。 鏈表就是通過地

2、址（指針）將每個(gè)結(jié)點(diǎn)（元素）連接起鏈表就是通過地址（指針）將每個(gè)結(jié)點(diǎn)（元素）連接起 來的表。例如，鏈表中的元素包括來的表。例如，鏈表中的元素包括A、B、C、D，如圖，如圖 15.1所示。所示。 C語言程序設(shè)計(jì)語言程序設(shè)計(jì) 15.1 鏈表的相關(guān)概念 v在圖15.1中，鏈表由4個(gè)結(jié)點(diǎn)構(gòu)成，每個(gè)結(jié)點(diǎn)包括兩個(gè)域： 數(shù)據(jù)域和指針域。數(shù)據(jù)域用來存放數(shù)據(jù)信息，指針域表示 地址信息，指向下一個(gè)結(jié)點(diǎn)的地址。數(shù)據(jù)域存放的 是A、B、C、D。在C語言中，通常用箭頭表 示結(jié)點(diǎn)之間的先后關(guān)系，一個(gè)結(jié)點(diǎn)的指針指向下一個(gè)相鄰 的元素。這樣利用指針將結(jié)點(diǎn)連接起來的表就構(gòu)成了鏈表。 C語言程序設(shè)計(jì)語言程序設(shè)計(jì) 15.1 鏈表的

3、相關(guān)概念 v如果要訪問鏈表中的元素，需要先找到第一個(gè)結(jié)點(diǎn)，為了 找到鏈表的第一個(gè)結(jié)點(diǎn)，還需要一個(gè)指針指向第一個(gè)結(jié)點(diǎn)， 我們稱這樣的指針為頭指針，記作head。另外，最后一個(gè) 元素D的結(jié)點(diǎn)沒有其它結(jié)點(diǎn)，將最后一個(gè)結(jié)點(diǎn)的指針域 置為NULL。如圖15.2所示。 C語言程序設(shè)計(jì)語言程序設(shè)計(jì) 15.1 鏈表的相關(guān)概念 v2定義鏈表的結(jié)點(diǎn) v鏈表是由結(jié)點(diǎn)構(gòu)成，結(jié)點(diǎn)包括數(shù)據(jù)域和指針域。一個(gè)結(jié) 點(diǎn)可以包括一個(gè)或多個(gè)數(shù)據(jù)域，因此，需要將結(jié)點(diǎn)定義 為結(jié)構(gòu)體類型。因?yàn)橹羔樣蚴侵赶蜃陨硪粯拥慕Y(jié)構(gòu)體類 型數(shù)據(jù)，如圖15.2中的元素A所在結(jié)點(diǎn)的指針域指向元 素B所在的結(jié)點(diǎn)，而A和B都是同一個(gè)類型。 C語言程序設(shè)計(jì)語言程

4、序設(shè)計(jì) 15.1 鏈表的相關(guān)概念 struct student/*定義結(jié)點(diǎn)類型*/ char data; /*數(shù)據(jù)域*/ struct student *next; /*next是指針域，指向結(jié) 構(gòu)體類型struct student*/ ; v其中，指針域是一個(gè)指向struct student的結(jié)構(gòu)體指針類 型。我們將這種存在指針指向自己的結(jié)構(gòu)體類型稱為自 引用類型。 C語言程序設(shè)計(jì)語言程序設(shè)計(jì) 15.1 鏈表的相關(guān)概念 v如果有如下的結(jié)構(gòu)體類型定義： struct student int no; /*學(xué)號*/ char name20; /*姓名*/ char addr30;/*地址*/ st

5、ruct student *next;/*next是指向struct student的指針*/ ; C語言程序設(shè)計(jì)語言程序設(shè)計(jì) 15.1 鏈表的相關(guān)概念 v這種結(jié)點(diǎn)構(gòu)成的鏈表如圖15.3所示。 C語言程序設(shè)計(jì)語言程序設(shè)計(jì) 15.1 鏈表的相關(guān)概念 v15.1.2 動(dòng)態(tài)存儲(chǔ)分配 v鏈表中的結(jié)點(diǎn)是動(dòng)態(tài)存儲(chǔ)分配的，而不是由系統(tǒng)自動(dòng)分配 的。動(dòng)態(tài)存儲(chǔ)分配是在使用前才進(jìn)行分配內(nèi)存空間，使用 完畢就可以釋放內(nèi)存空間。內(nèi)存空間的分配和釋放由用戶 自己決定。 v1。malloc函數(shù)函數(shù)動(dòng)態(tài)內(nèi)存分配函數(shù)動(dòng)態(tài)內(nèi)存分配函數(shù) v函數(shù)malloc的主要作用是分配一塊長度為size的內(nèi)存空間。 函數(shù)原型如下： vvoid

6、 *malloc(unsigned int size); C語言程序設(shè)計(jì)語言程序設(shè)計(jì) 15.1 鏈表的相關(guān)概念 v函數(shù)malloc常常與運(yùn)算符sizeof配合使用。例如，要分配 一個(gè)大小為40的int型的內(nèi)存空間，代碼如下： vint *p; vp=(int*)malloc(sizeof(int)*40); C語言程序設(shè)計(jì)語言程序設(shè)計(jì) 15.1 鏈表的相關(guān)概念 v2。free函數(shù)動(dòng)態(tài)內(nèi)存釋放函數(shù) v函數(shù)free的主要作用是將動(dòng)態(tài)分配的內(nèi)存空間釋放。它的 函數(shù)原型如下： void free(void *p); v其中，參數(shù)p指向要釋放的內(nèi)存空間。函數(shù)free沒有返回值。 函數(shù)原型malloc和f

7、ree都在頭文件stdlib.h和alloc.h中定義。 C語言程序設(shè)計(jì)語言程序設(shè)計(jì) 15.2 鏈表的操作 v鏈表的主要操作包括：創(chuàng)建鏈表、輸出鏈表、鏈表的查 找、鏈表的插入和鏈表的刪除。 15.2.1 鏈表的創(chuàng)建 v鏈表的創(chuàng)建就是將一個(gè)個(gè)結(jié)點(diǎn)連接在一起。創(chuàng)建鏈表的 步驟如下： v 動(dòng)態(tài)生成結(jié)點(diǎn)。 v 輸入結(jié)點(diǎn)的數(shù)據(jù)。 v 將結(jié)點(diǎn)連接在一起。 C語言程序設(shè)計(jì)語言程序設(shè)計(jì) 15.2 鏈表的操作 v例如，要將3個(gè)字符X、Y和Z依次存放到結(jié)點(diǎn)中， 構(gòu)成一般鏈表。需要先定義一個(gè)結(jié)點(diǎn)類型，代碼如下： struct node char ch; struct node *next; ListNode; C語

8、言程序設(shè)計(jì)語言程序設(shè)計(jì) 15.2 鏈表的操作 v1將第一個(gè)字符X插入到鏈表中 v先動(dòng)態(tài)生成一個(gè)結(jié)點(diǎn)，用p指向該結(jié)點(diǎn)。代碼如下： vp=(ListNode*)malloc(sizeof(ListNode); v然后將X存放到結(jié)點(diǎn)的數(shù)據(jù)域ch中，代碼如下： vp-ch=X; v讓頭指針head指向第一個(gè)結(jié)點(diǎn)，代碼如下： vhead=p; v這樣就將第一個(gè)結(jié)點(diǎn)的插入到鏈表中。 C語言程序設(shè)計(jì)語言程序設(shè)計(jì) 15.2 鏈表的操作 v插入第一個(gè)結(jié)點(diǎn)的過程如圖插入第一個(gè)結(jié)點(diǎn)的過程如圖15.4所示。所示。 C語言程序設(shè)計(jì)語言程序設(shè)計(jì) 15.2 鏈表的操作 v2將第二個(gè)字符將第二個(gè)字符Y插入到鏈表中插入到鏈表中

9、 v動(dòng)態(tài)生成一個(gè)結(jié)點(diǎn)，將字符Y存放到該結(jié)點(diǎn)中，代碼如 下： p=(ListNode*)malloc(sizeof(ListNode); p-ch=Y; v將第2個(gè)結(jié)點(diǎn)連接在第1個(gè)結(jié)點(diǎn)之后。代碼如下： q-next=p; v讓q指向第二個(gè)結(jié)點(diǎn)，即當(dāng)前鏈表的最后一個(gè)結(jié)點(diǎn)。代碼 如下： q=p; C語言程序設(shè)計(jì)語言程序設(shè)計(jì) 15.2 鏈表的操作 v插入第二個(gè)結(jié)點(diǎn)的過程如圖15.5所示。 C語言程序設(shè)計(jì)語言程序設(shè)計(jì) 15.2 鏈表的操作 v3將第三個(gè)字符將第三個(gè)字符Z插入到鏈表中插入到鏈表中 v與前兩步類似，先動(dòng)態(tài)生成一個(gè)結(jié)點(diǎn)，并將字符C 存放到該結(jié)點(diǎn)，代碼如下： p=(ListNode*)mallo

10、c(sizeof(ListNode); p-ch=Z; v然后將q指向結(jié)點(diǎn)*p，代碼如下： q-next=p; v因?yàn)閜指向的結(jié)點(diǎn)是最后一個(gè)結(jié)點(diǎn)，所以將該結(jié)點(diǎn)的 指針域置為NULL。代碼如下： p-next=NULL; C語言程序設(shè)計(jì)語言程序設(shè)計(jì) 15.2 鏈表的操作 v插入最后一個(gè)結(jié)點(diǎn)的過程如圖插入最后一個(gè)結(jié)點(diǎn)的過程如圖15.6所示。所示。 C語言程序設(shè)計(jì)語言程序設(shè)計(jì) 15.2 鏈表的操作 v15.2.2 鏈表的輸出 v鏈表的輸出就是將鏈表中的各個(gè)結(jié)點(diǎn)的數(shù)據(jù)依次輸出。輸 出鏈表的操作非常簡單，定義一個(gè)指針變量p，使其指向 鏈表的第一個(gè)結(jié)點(diǎn)。然后輸出p指向的結(jié)點(diǎn)，并讓p指向下 一個(gè)結(jié)點(diǎn)。依次類

11、推，直到輸出所有結(jié)點(diǎn)的元素。 C語言程序設(shè)計(jì)語言程序設(shè)計(jì) 15.2 鏈表的操作 v輸出鏈表的函數(shù)如下：輸出鏈表的函數(shù)如下： void displist(struct node *h) struct node *p=h; while(p!=NULL) printf(%4c,p-ch); p=p-next; C語言程序設(shè)計(jì)語言程序設(shè)計(jì) 15.2 鏈表的操作 15.2.3 鏈表的查找 v鏈表的查找操作就是在鏈表中查找指定值的元素，如果找 到，返回該結(jié)點(diǎn)的指針，否則返回NULL。鏈表的查找操 作必須從鏈表的頭指針開始，依次與結(jié)點(diǎn)的值進(jìn)行比較。 直到找到結(jié)點(diǎn)或到達(dá)鏈表的末尾，查找操作結(jié)束。 C語言程序設(shè)

12、計(jì)語言程序設(shè)計(jì) 15.2 鏈表的操作 v鏈表的查找操作與鏈表的輸出操作是類似的，只是多鏈表的查找操作與鏈表的輸出操作是類似的，只是多 了一個(gè)比較的過程。鏈表的查找操作實(shí)現(xiàn)如下：了一個(gè)比較的過程。鏈表的查找操作實(shí)現(xiàn)如下： struct node *findnode(struct node *h,char x) struct node *p=h; while(p!=NULL return p; C語言程序設(shè)計(jì)語言程序設(shè)計(jì) 15.2 鏈表的操作 v15.2.4 鏈表的插入操作 v鏈表的插入操作是在鏈表中指定位置插入一個(gè)新結(jié)點(diǎn)。要將 一個(gè)結(jié)點(diǎn)插入到鏈表中，需要解決以下兩個(gè)問題： v（1）查找插入點(diǎn)。

13、v（2）將新結(jié)點(diǎn)插入到鏈表中。 C語言程序設(shè)計(jì)語言程序設(shè)計(jì) 15.2 鏈表的操作 v插入過程如圖插入過程如圖15.7所示。所示。 C語言程序設(shè)計(jì)語言程序設(shè)計(jì) 15.2 鏈表的操作 v將新結(jié)點(diǎn)插入到*r之后需要兩步操作，代碼如下： p-next=r-next;/*將*p的指針域指向*r的下一個(gè)結(jié) 點(diǎn)*/ r-next=p; /*將*r的指針域指向*p*/ v說明：在鏈表中插入新結(jié)點(diǎn)并不需要移動(dòng)鏈表中的元素， 只需要修改指針的指向即可。 C語言程序設(shè)計(jì)語言程序設(shè)計(jì) 15.2 鏈表的操作 15.2.5 鏈表的刪除操作 v刪除鏈表中元素值為刪除鏈表中元素值為a的結(jié)點(diǎn)，操作過程如圖的結(jié)點(diǎn)，操作過程如圖15.8所示。所示。 C語言程序設(shè)計(jì)語言程序設(shè)計(jì) 15.2 鏈表的操作 v刪除元素值為a的結(jié)點(diǎn)的關(guān)鍵代碼如下： r=findnode2(h,a);/*查找要?jiǎng)h除的結(jié)點(diǎn)，返回 值r指向要?jiǎng)h除結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)*/ p=r-next; /*p指向要?jiǎng)h除的結(jié)點(diǎn)*/ r-next=p-next; /*刪除p指向的結(jié)點(diǎn)，使*p脫鏈*/ free(p); /*釋放p指向的結(jié)點(diǎn)的內(nèi)存空間*/ C語言程序設(shè)計(jì)語