# 11.C語言鏈表的概念
在【例7-8】中采用了動態分配的辦法為一個結構分配內存空間。每一次分配一塊空間可用來存放一個學生的數據,我們可稱之為一個結點。有多少個學生就應該申請分配多少塊內存空間,也就是說要建立多少個結點。當然用結構數組也可以完成上述工作,但如果預先不能準確把握學生人數,也就無法確定數組大小。而且當學生留級、退學之后也不能把該元素占用的空間從數組中釋放出來。
用動態存儲的方法可以很好地解決這些問題。有一個學生就分配一個結點,無須預先確定學生的準確人數,某學生退學,可刪去該結點,并釋放該結點占用的存儲空間。從而節約了寶貴的內存資源。另一方面,用數組的方法必須占用一塊連續的內存區域。而使用動態分配時,每個結點之間可以是不連續的(結點內是連續的)。結點之間的聯系可以用指針實現。 即在結點結構中定義一個成員項用來存放下一結點的首地址,這個用于存放地址的成員,常把它稱為指針域。
可在第一個結點的指針域內存入第二個結點的首地址,在第二個結點的指針域內又存放第三個結點的首地址,如此串連下去直到最后一個結點。最后一個結點因無后續結點連接,其指針域可賦為0。這樣一種連接方式,在數據結構中稱為“鏈表”。
下圖為最一簡單鏈表的示意圖。

圖中,第0個結點稱為頭結點,它存放有第一個結點的首地址,它沒有數據,只是一個指針變量。以下的每個結點都分為兩個域,一個是數據域,存放各種實際的數據,如學號num,姓名name,性別sex和成績score等。另一個域為指針域,存放下一結點的首地址。鏈表中的每一個結點都是同一種結構類型。
例如,一個存放學生學號和成績的結點應為以下結構:
~~~
struct stu{
int num;
int score;
struct stu *next;
}
~~~
前兩個成員項組成數據域,后一個成員項next構成指針域,它是一個指向stu類型結構的指針變量。
鏈表的基本操作對鏈表的主要操作有以下幾種:
* 建立鏈表;
* 結構的查找與輸出;
* 插入一個結點;
* 刪除一個結點。
下面通過例題來說明這些操作。
【例11-9】建立一個三個結點的鏈表,存放學生數據。為簡單起見, 我們假定學生數據結構中只有學號和年齡兩項。可編寫一個建立鏈表的函數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<n;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);
}
~~~
在函數外首先用宏定義對三個符號常量作了定義。這里用 TYPE表示struct stu,用LEN表示sizeof(struct stu)主要的目的是為了在以下程序內減少書寫并使閱讀更加方便。結構stu定義為外部類型,程序中的各個函數均可使用該定義。
creat函數用于建立一個有n個結點的鏈表,它是一個指針函數,它返回的指針指向stu結構。在creat函數內定義了三個stu結構的指針變量。head為頭指針,pf為指向兩相鄰結點的前一結點的指針變量。pb為后一結點的指針變量。
- 前言
- 一. C語言概述
- 1.C語言的發展及其版本
- 2.C語言工作原理和運行機制
- 3.C語言編譯器(開發工具|IDE)推薦
- 4.C語言的特點
- 5.第一個C語言程序
- 6.C語言輸出函數(printf)和輸入函數(scanf)
- 7.C語言程序的結構特點
- 8.C語言字符集
- 9.C語言詞匯
- 二. C語言算法
- 1.什么是算法|算法的概念
- 2.簡單的C語言算法舉例
- 3.C語言算法的特性
- 4.用流程圖表示算法
- 5.三種基本結構的流程圖
- 6.用N-S流程圖表示算法
- 7.用計算機語言表示算法
- 三. 數據類型和運算符
- 1.C語言的數據類型
- 2.C語言常量與變量
- 3.C語言整型數據
- 4.C語言實型數據
- 5.C語言字符型數據
- 6.C語言變量賦初值
- 7.C語言數據類型轉換
- 8.C語言算術運算符和算術表達式
- 9.C語言賦值運算符和賦值表達式
- 10.C語言逗號運算符和逗號表達式
- 四. 順序程序設計
- 1.C語言語句概述
- 2.C語言賦值語句詳解
- 3.C語言數據的輸入輸出
- 4.C語言字符的輸入輸出
- 7.C語言順序結構程序設計舉例
- 五. 分支結構
- 1.C語言關系運算符和表達式
- 2.C語言邏輯運算符和表達式
- 3.C語言if語句詳解
- 4.C語言switch語句的用法詳解
- 5.C語言條件運算符和條件表達式
- 6.C語言分支結構程序舉例
- 六. 循環控制
- 1.C語言循環控制概述
- 2.C語言goto語句以及用goto語句構成循環
- 3.C語言while語句的用法
- 4.C語言do-while語句的用法
- 5.C語言for語句用法詳解
- 6.C語言幾種循環的比較
- 7.C語言break和continue語句的用法
- 8.C語言循環控制程序舉例
- 七. C語言數組
- 1.C語言一維數組的定義和引用
- 2.C語言二維數組的定義和引用
- 3.C語言字符數組及其應用
- 4.C語言常用字符串處理函數
- 5.C語言數組應用舉例
- 6.C語言數組小結
- 八. C語言函數
- 1.C語言函數概述
- 2.C語言函數的定義
- 3.C語言函數的參數和返回值
- 4.C語言函數的調用
- 5.C語言函數的嵌套調用
- 6.C語言函數的遞歸調用
- 7.C語言數組作為函數參數
- 8.C語言局部變量和全局變量
- 9.C語言變量的存儲類別
- 九. 預處理命令
- 1.C語言預處理概述
- 2.C語言無參數宏定義
- 3.C語言帶參數宏定義
- 4.C語言文件包含命令
- 5.C語言條件編譯詳解
- 6.C語言預處理指令總結
- 十. C語言指針
- 1.C語言指針的概念
- 2.C語言指針變量
- 3.C語言指針變量作為函數參數
- 4.C語言指針變量的運算
- 5.C語言數組指針
- 6.C語言通過指針引用數組
- 7.C語言數組名作函數參數
- 8.C語言指向多維數組的指針
- 9.C語言字符串指針
- 10.C語言字符串指針變量與字符數組的區別
- 11.C語言函數指針變量
- 12.C語言指針型函數
- 13.C語言指針數組的概念
- 14.C語言指向指針的指針
- 15.C語言main函數參數
- 16.關于指針的總結
- 十一. 結構體和共用體
- 1.C語言結構體的定義
- 2.C語言結構類型變量的說明
- 3.C語言結構變量成員的表示方法
- 4.C語言結構變量的賦值
- 5.C語言結構變量的初始化
- 6.C語言結構體數組的定義
- 7.C語言指向結構體變量的指針
- 8.C語言指向結構體數組的指針
- 9.C語言結構體指針變量作函數參數
- 10.C語言動態存儲分配
- 11.C語言鏈表的概念
- 12.C語言枚舉類型
- 13.C語言類型定義符typedef
- 十二. 位運算
- 1.C語言位運算符詳解
- 2.C語言位域(位段)
- 3.關于位運算的總結
- 十三. 文件操作
- 1.C語言文件概述
- 2.C語言文件指針
- 3.C語言文件的打開與關閉
- 4.C語言文件的讀寫
- 5.C語言文件的隨機讀寫
- 6.C語言文件檢測函數
- 7.C語言庫文件(頭文件)有哪些
- 8.文件操作小結