2010年計(jì)算機(jī)等級考試二級C語言教程：第七章

　　本例中，定義了結(jié)構(gòu)stu，定義了stu類型指針變量ps。 然后分配一塊stu大內(nèi)存區(qū)，并把首地址賦予ps，使ps指向該區(qū)域。再以ps為指向結(jié)構(gòu)的指針變量對各成員賦值，并用printf 輸出各成員值。最后用free函數(shù)釋放ps指向的內(nèi)存空間。 整個(gè)程序包含了申請內(nèi)存空間、使用內(nèi)存空間、釋放內(nèi)存空間三個(gè)步驟， 實(shí)現(xiàn)存儲(chǔ)空間的動(dòng)態(tài)分配。鏈表的概念在例7.9中采用了動(dòng)態(tài)分配的辦法為一個(gè)結(jié)構(gòu)分配內(nèi)存空間。每一次分配一塊空間可用來存放一個(gè)學(xué)生的數(shù)據(jù)， 我們可稱之為一個(gè)結(jié)點(diǎn)。有多少個(gè)學(xué)生就應(yīng)該申請分配多少塊內(nèi)存空間， 也就是說要建立多少個(gè)結(jié)點(diǎn)。當(dāng)然用結(jié)構(gòu)數(shù)組也可以完成上述工作， 但如果預(yù)先不能準(zhǔn)確把握學(xué)生人數(shù)，也就無法確定數(shù)組大小。 而且當(dāng)學(xué)生留級、退學(xué)之后也不能把該元素占用的空間從數(shù)組中釋放出來。 用動(dòng)態(tài)存儲(chǔ)的方法可以很好地解決這些問題。 有一個(gè)學(xué)生就分配一個(gè)結(jié)點(diǎn)，無須預(yù)先確定學(xué)生的準(zhǔn)確人數(shù)，某學(xué)生退學(xué)， 可刪去該結(jié)點(diǎn)，并釋放該結(jié)點(diǎn)占用的存儲(chǔ)空間。從而節(jié)約了寶貴的內(nèi)存資源。 另一方面，用數(shù)組的方法必須占用一塊連續(xù)的內(nèi)存區(qū)域。 而使用動(dòng)態(tài)分配時(shí)，每個(gè)結(jié)點(diǎn)之間可以是不連續(xù)的(結(jié)點(diǎn)內(nèi)是連續(xù)的)。 結(jié)點(diǎn)之間的聯(lián)系可以用指針實(shí)現(xiàn)。 即在結(jié)點(diǎn)結(jié)構(gòu)中定義一個(gè)成員項(xiàng)用來存放下一結(jié)點(diǎn)的首地址，這個(gè)用于存放地址的成員，常把它稱為指針域�？稍诘谝粋�(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)因無后續(xù)結(jié)點(diǎn)連接，其指針域可賦為0。這樣一種連接方式，在數(shù)據(jù)結(jié)構(gòu)中稱為“鏈表”。圖7.3為鏈表的示意圖。

　　在圖7.3中，第0個(gè)結(jié)點(diǎn)稱為頭結(jié)點(diǎn)， 它存放有第一個(gè)結(jié)點(diǎn)的首地址，它沒有數(shù)據(jù)，只是一個(gè)指針變量。 以下的每個(gè)結(jié)點(diǎn)都分為兩個(gè)域，一個(gè)是數(shù)據(jù)域，存放各種實(shí)際的數(shù)據(jù)，如學(xué)號(hào)num，姓名name，性別sex和成績score等。另一個(gè)域?yàn)橹羔樣颍?存放下一結(jié)點(diǎn)的首地址。鏈表中的每一個(gè)結(jié)點(diǎn)都是同一種結(jié)構(gòu)類型。例如， 一個(gè)存放學(xué)生學(xué)號(hào)和成績的結(jié)點(diǎn)應(yīng)為以下結(jié)構(gòu)：

　　struct stu

　　{ int num;

　　int score;

　　struct stu *next;

　　}

　　前兩個(gè)成員項(xiàng)組成數(shù)據(jù)域，后一個(gè)成員項(xiàng)next構(gòu)成指針域， 它是一個(gè)指向stu類型結(jié)構(gòu)的指針變量。鏈表的基本操作對鏈表的主要操作有以下幾種：

　　1.建立鏈表;

　　2.結(jié)構(gòu)的查找與輸出;

　　3.插入一個(gè)結(jié)點(diǎn);

　　4.刪除一個(gè)結(jié)點(diǎn);

　　下面通過例題來說明這些操作。

　　[例7.10]建立一個(gè)三個(gè)結(jié)點(diǎn)的鏈表，存放學(xué)生數(shù)據(jù)。 為簡單起見， 我們假定學(xué)生數(shù)據(jù)結(jié)構(gòu)中只有學(xué)號(hào)和年齡兩項(xiàng)。

　　可編寫一個(gè)建立鏈表的函數(shù)creat。程序如下：

　　#define NULL 0

　　#define TYPE struct stu

　　#define LEN sizeof (struct stu)

　　struct stu

　　{

　　int num;

　　int age;

　　struct stu *next;

　　};

　　TYPE *creat(int n)

　　{

　　struct stu *head,*pf,*pb;

　　int i;

　　for(i=0;i

　　{

　　pb=(TYPE*) malloc(LEN);

　　printf("input Number and Age\n");

　　scanf("%d%d",&pb->num,&pb->age);

　　if(i==0)

　　pf=head=pb;

　　else pf->next=pb;

　　pb->next=NULL;

　　pf=pb;

　　}

　　return(head);

　　}