2010年計算機等級考試二級C語言教程：第八章

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

　　在圖7.3中，第0個結點稱為頭結點， 它存放有第一個結點的首地址，它沒有數(shù)據(jù)，只是一個指針變量。 以下的每個結點都分為兩個域，一個是數(shù)據(jù)域，存放各種實際的數(shù)據(jù)，如學號num，姓名name，性別sex和成績score等。另一個域為指針域， 存放下一結點的首地址。鏈表中的每一個結點都是同一種結構類型。例如， 一個存放學生學號和成績的結點應為以下結構：

　　struct stu

　　{ int num;

　　int score;

　　struct stu *next;

　　}

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

　　1.建立鏈表;

　　2.結構的查找與輸出;

　　3.插入一個結點;

　　4.刪除一個結點;

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