單鏈表基本概念

1、9.5 單鏈表的基本概念 數(shù)組可以看成是一批有先后次序的元素構(gòu)成的序列，其優(yōu)點是能用下標隨意訪問元素，操作簡便；不足之處在于元素個數(shù)有上限，插入或刪除某個元素時需要移動其他元素。 與數(shù)組一樣，鏈表也是一種有先后次序的序列，但它的元素可以動態(tài)分配，插入或刪除元素時不需要移動其他元素，因此常常被看作是與數(shù)組互為補充的一種重要的數(shù)據(jù)構(gòu)成方式。 設(shè)計鏈表的原則是為了使問題的處理更好理解，更易實現(xiàn)。如果描述一個問題可以使用鏈表，也可以使用數(shù)組，而且使用數(shù)組可以更好地進行處理，那就應(yīng)該選擇數(shù)組。1. 常見鏈表示意圖 單鏈表單鏈表8910189.589103908910785NULL8910189.5891

2、03908910785NULLNULL雙鏈表雙鏈表8910189.589103908910785循環(huán)鏈表循環(huán)鏈表head 1000 1032 3284 1296 1382 2008圖圖9.2 動態(tài)單向鏈表示意圖動態(tài)單向鏈表示意圖C3284H1296A1382I2008NNULLNULL1000s1032鏈表有一個鏈表有一個“頭指針頭指針”變量，用變量，用head表示，它存放一個地址。該地址指向一個元素。表示，它存放一個地址。該地址指向一個元素。鏈表中每個元素稱為一個結(jié)點，每個結(jié)點包括兩個部分：用戶需要的普通數(shù)據(jù)、下一鏈表中每個元素稱為一個結(jié)點，每個結(jié)點包括兩個部分：用戶需要的普通數(shù)據(jù)、下一個結(jié)

3、點的地址?？梢钥闯鰝€結(jié)點的地址?？梢钥闯鰄ead指向第一個元素，第一個元素又指向第二個元素指向第一個元素，第一個元素又指向第二個元素，直到直到最后一個元素，該元素不再指向其他元素，它稱為最后一個元素，該元素不再指向其他元素，它稱為“表尾表尾”，它的地址部分放一，它的地址部分放一個個“NULL”（表示空地址），鏈表到此結(jié)束。（表示空地址），鏈表到此結(jié)束。構(gòu)成鏈表的結(jié)點必須是結(jié)構(gòu)體類型數(shù)據(jù)。構(gòu)成鏈表的結(jié)點必須是結(jié)構(gòu)體類型數(shù)據(jù)。相鄰結(jié)點的地址不一定是連續(xù)的，依靠指針將它們連接起來。要找某一元素，必須先相鄰結(jié)點的地址不一定是連續(xù)的，依靠指針將它們連接起來。要找某一元素，必須先找到上一個元素，根據(jù)它提供

4、的下一元素地址才能找到下一個元素。如果不提供找到上一個元素，根據(jù)它提供的下一元素地址才能找到下一個元素。如果不提供“頭頭指針指針”（head），則整個鏈表都無法訪問。），則整個鏈表都無法訪問。2. 鏈表的基本結(jié)構(gòu) struct nodechar c; struct node *next; ;next是是struct node類型中的一個成員，類型中的一個成員，它又指向它又指向struct node 類型的數(shù)據(jù)類型的數(shù)據(jù)(這這就是就是next所在的結(jié)構(gòu)體類型）所在的結(jié)構(gòu)體類型） 鏈表是一種動態(tài)數(shù)據(jù)結(jié)構(gòu)，可根據(jù)需要鏈表是一種動態(tài)數(shù)據(jù)結(jié)構(gòu)，可根據(jù)需要動態(tài)地分配存儲單元。在數(shù)組中，插入或刪動態(tài)地分配存

5、儲單元。在數(shù)組中，插入或刪除一個元素都比較繁瑣，而用鏈表則相對容除一個元素都比較繁瑣，而用鏈表則相對容易。但是數(shù)組元素的引用比較簡單，對于鏈易。但是數(shù)組元素的引用比較簡單，對于鏈表中結(jié)點數(shù)據(jù)的存取操作則相對復雜。表中結(jié)點數(shù)據(jù)的存取操作則相對復雜。 3. 靜態(tài)鏈表 【例1】建立一個如圖所示的簡單鏈表，它由3個學生數(shù)據(jù)的結(jié)點組成。輸出各結(jié)點中的數(shù)據(jù)。 #define NULL 0 struct student long num; float score; struct student *next; /*next指向struct student 類型數(shù)據(jù)*/ ; main( ) struct stu

6、dent a,b,c, *head, *p; a.num=89101; a.score=89.5; b.num=89103; b.score=90; c.num=89107; c.score=85; /*對結(jié)點的num和score成員賦值*/ head=&a; /*將結(jié)點a的起始地址賦給頭指針head*/ 8910189.589103908910785numscorenext a.next=&b; /*將結(jié)點b的起始地址賦給a結(jié)點的next成員*/ b.next=&c; /*將結(jié)點c的起始地址賦給b結(jié)點的next成員*/ c.next=NULL; /*c結(jié)點的next成員不存放其他結(jié)點地址*/

7、 p=head; /*使p指針指向a結(jié)點*/do printf(%ld%5.1fn,p-num, p-score); /*輸出p指向的結(jié)點的數(shù)據(jù)*/ p= p- next /*使p指向下一結(jié)點*/ while(p!=NULL); /*輸出完c結(jié)點后p的值為NULL*/本例比較簡單，所有結(jié)點都是在程序中定義的，不是臨時開辟的，也不能用完后釋放，這種鏈表稱為“靜態(tài)鏈表”。 C語言提供了相關(guān)的存儲管理庫函數(shù)。這里語言提供了相關(guān)的存儲管理庫函數(shù)。這里僅介紹其中三個，它們的原型說明在僅介紹其中三個，它們的原型說明在“stdlib.h”頭文件和頭文件和“alloc.h”頭文件中，使用頭文件中，使用這三個函

8、數(shù)時，應(yīng)選擇其中一個頭文件包含到這三個函數(shù)時，應(yīng)選擇其中一個頭文件包含到源程序中。源程序中。 動態(tài)分配存儲區(qū)函數(shù)malloc( ) 函數(shù)原型：void *malloc(unsigned size); 調(diào)用格式：malloc(size) 功能：在內(nèi)存的動態(tài)存儲區(qū)中分配一個長度為size的連續(xù)空間。調(diào)用結(jié)果為新分配的存儲區(qū)的首地址，是一個void類型指針。若分配失敗，則返回空指針（即NULL ）。4. 動態(tài)分配和釋放存儲單元 在ANSI C標準中，關(guān)鍵字void有兩種用法。第一種用法，可將無返回值的函數(shù)定義為void類型第二種用法，用void * 定義指針，這是一個指向非具體數(shù)據(jù)類型的指針，稱為無

9、類型指針。 【例2】調(diào)用malloc函數(shù)分配所需存儲單元。 #include main( ) struct st int n; struct st *next; *p; p=(struct st *)malloc(sizeof(struct st); p-n=5; p-next=NULL; /*系獨立結(jié)點*/ printf(p-n=%dtp-next=%xn,p-n,p-next); 4. 動態(tài)分配和釋放存儲單元 將函數(shù)返回值轉(zhuǎn)換成結(jié)構(gòu)將函數(shù)返回值轉(zhuǎn)換成結(jié)構(gòu)體指針。體指針。void void * *強制轉(zhuǎn)換強制轉(zhuǎn)換成成struct st struct st * *結(jié)果：p-n=5 p-next

10、=0 動態(tài)分配存儲區(qū)函數(shù)calloc( ) 函數(shù)原型： void *calloc(unsigned int n,unsigned int size); 調(diào)用格式：calloc(n,size) 功能：在內(nèi)存的動態(tài)區(qū)存儲中分配n個長度為size的連續(xù)空間。函數(shù)返回一個指向分配域起始地址的指針；如果分配不成功，則返回NULL（即0）。 用calloc函數(shù)可以為一維數(shù)組開辟動態(tài)存儲空間，n為數(shù)組元素個數(shù)，每個元素長度為size。4. 動態(tài)分配和釋放存儲單元 【例3】調(diào)用calloc函數(shù)分配所需存儲單元。 #include main( ) int i,*ip; ip=(int *)calloc(10,2

11、); for (i=0; i10; i+) scanf(%d,ip+i); for (i=0; iname,name) gets(p-tel) p-next=NULL h=NULL T F h指向第一個指向第一個 連接新結(jié)點連接新結(jié)點 結(jié)點結(jié)點 h=p q-next=p q指向新的尾結(jié)點指向新的尾結(jié)點 q=p 讀入一個學生姓名讀入一個學生姓名圖圖9.3 建立單向鏈表建立單向鏈表NULLhpChang62783410NULLWang63212986NULLpq 把把p p所指的結(jié)點作為所指的結(jié)點作為第一個結(jié)點第一個結(jié)點 把把p p所指的結(jié)點連接到表尾所指的結(jié)點連接到表尾q q移到表尾移到表尾 s

12、trcpy(p-name,name); /* 為新結(jié)點中的成員賦值 */ printf(tel: ); gets(p-tel); p-next=NULL; /*p所指的下一個結(jié)點的地址為NULL*/ if (h=NULL) /* h為空，表示新結(jié)點為第一個結(jié)點 */ h=p; /* 頭指針指向第一個結(jié)點 */ else /* h不為空 */ q-next=p; /* 新結(jié)點與尾結(jié)點相連接 */ q=p; /* 使q指向新的尾結(jié)點 */ printf(name: ); gets(name); return h; struct node *create( ) static struct node

13、*h; struct node *p,*q; char name20; h=NULL; printf(name: ); gets(name); while (strlen(name)!=0) /* 當輸入的姓名不是空串循環(huán) */ p=NEW; /* 開辟新結(jié)點 */ if (p=NULL) /* p為NULL，新結(jié)點分配失敗 */ printf(Allocation failuren); exit(0); /* 結(jié)束程序運行 */ #include #include #define NEW (struct node *)malloc(sizeof(struct node)struct node

14、 char name20,tel9; struct node *next; ;main( ) struct node *head; head=create( ); 【例5】輸出學生電話簿鏈表函數(shù)。6. 輸出單向鏈表中各結(jié)點信息 hpChang62783410Li68752341NULLWang63212986 p指向第一個結(jié)點指向第一個結(jié)點 p=head 當當p不為不為NULL 輸出結(jié)點數(shù)據(jù)輸出結(jié)點數(shù)據(jù) p指向下一個結(jié)點指向下一個結(jié)點 p=p- -next圖圖9.5 輸出鏈表的輸出鏈表的N-S圖圖pppNULLNULLvoid prlist(struct node *head) struct

15、node *p; p=head; while (p!=NULL) printf(%st%sn,p-name,p-tel); p=p-next; #include #include #define NEW (struct node *)malloc(sizeof(struct node)struct node char name20,tel9; struct node *next; ;main( ) struct node *head; head=create( ); prlist(head); 在鏈表中，如果要刪除第i個結(jié)點，一般是將第（i-1）個結(jié)點直接與第（i+1）個結(jié)點相連接，然后再釋放

16、第i個結(jié)點的存儲單元 。7. 刪除單向鏈表中指定的結(jié)點 hNULLNULL第第i-1個結(jié)點個結(jié)點 第第i個結(jié)點個結(jié)點 第第i+1個結(jié)點個結(jié)點 【例6】刪除學生電話簿鏈 表中指定學生的信息。 p=head while(strcmp(x,p-name)!=0 & p-next!=NULLNULL) q指針跟隨指針跟隨p指針后移查找指針后移查找 (q=p;p=p-next;) strcmp(x,p-name)=0 T F p=head T F head=p-next q-next=p-next 沒找到?jīng)]找到 free(p)圖圖9.9 刪除鏈表中指定結(jié)點的刪除鏈表中指定結(jié)點的N-S圖圖刪除刪除第一個第

17、一個結(jié)點結(jié)點 刪除中間刪除中間結(jié)點或尾結(jié)點或尾結(jié)點結(jié)點 刪除結(jié)點工刪除結(jié)點工作分兩步：作分兩步：查找結(jié)點查找結(jié)點刪除結(jié)點刪除結(jié)點學生姓名學生姓名當姓名不同并且當姓名不同并且不是尾結(jié)點循環(huán)不是尾結(jié)點循環(huán)【例6】刪除學生電話簿鏈表中指定學生的信息。hpChang62783410Li68752341NULLWang63212986(a) 刪除第一個結(jié)點 (head=p-next)【例6】刪除學生電話簿鏈表中指定學生的信息。hpChang62783410Li68752341NULLWang63212986(b) 刪除中間結(jié)點或尾結(jié)點 (q-next=p-next)p q【例6】刪除學生電話簿鏈表中指定

18、學生的信息。hpChang62783410Li68752341NULLWang63212986pp(c) 未找到指定的結(jié)點 (strcmp(x,p-name)!=0) qq if (strcmp(x,p-name)=0) if (p=head) head=p-next; /* 刪除頭結(jié)點 */ else q-next=p-next; /* 刪除中間或尾結(jié)點 */ free(p); /* 釋放被刪除的結(jié)點 */ else printf(Not found.); /* 未找到指定的結(jié)點 */ h=head; return h;#include #include #define NEW (struc

19、t node *)malloc(sizeof(struct node)struct node char name20,tel9; struct node *next; ;struct node *delnode(struct node *head, char *x) struct node *p,*q; static struct node *h; if (head=NULL) printf(This is a empty list.); /* 空鏈表情況 */ return head; p=head; while (strcmp(x,p-name)!=0 & p-next!=NULL) q=

20、p;p=p-next; /* q指針尾隨p指針向表尾移動 */查找結(jié)點查找結(jié)點 將一個新結(jié)點插入到鏈表中，首先要尋找插入的位置。如果要求在第i個結(jié)點前插入，可設(shè)置三個工作指針p0、p和q，p0是指向待插入結(jié)點的指針。利用p和q指針查找第i個結(jié)點，找到后再將新結(jié)點鏈接到鏈表上。 8. 在單向鏈表中插入結(jié)點 hNULLNULL第第i個結(jié)點個結(jié)點ppqqp0p新的第新的第i個結(jié)點個結(jié)點 head=NULL T F p=head head=p0 while(strcmp(x,p-name)!=0 & p-next!=NULLNULL) p0-next q指針跟隨指針跟隨p指針后移查找指針后移查找 (q

21、=p;p=p-next;) =NULL NULL strcmp(x,p-name)=0 T F p=head T F p-next=p0 head=p0 q-next=p0 p0-next=NULLNULL p0-next=p圖圖9.11 在鏈表指定位置前插入結(jié)點的在鏈表指定位置前插入結(jié)點的N-S圖圖【例7】在學生電話簿鏈表中插入一個學生的信息。要求將新的信息插入在指定學生信息之前，如果未找到指定學生，則追加在鏈表尾部。 當姓名不同并且當姓名不同并且不是尾結(jié)點循環(huán)不是尾結(jié)點循環(huán)空表時空表時插入插入結(jié)點結(jié)點在表尾在表尾追加結(jié)點追加結(jié)點 插入結(jié)點工插入結(jié)點工作分兩步：作分兩步：查找插查找插入位置入

22、位置連接連接新結(jié)點新結(jié)點在表頭在表頭插入結(jié)點插入結(jié)點 在表中間在表中間插入結(jié)點插入結(jié)點 【例7】在學生電話簿鏈表中插入一個學生的信息。要求將新的信息插入在指定學生信息之前，如果未找到指定學生，則追加在鏈表尾部。hpChang62783410Li68752341NULLWang63212986(a) 在表頭插入結(jié)點 (head=p0; p0-next=p)Zhao62758421p0【例7】在學生電話簿鏈表中插入一個學生的信息。要求將新的信息插入在指定學生信息之前，如果未找到指定學生，則追加在鏈表尾部。hChang62783410Li68752341NULLWang63212986(b) 在表中

23、間插入結(jié)點 (q-next=p0; p0-next=p)pqZhao62758421p0【例7】在學生電話簿鏈表中插入一個學生的信息。要求將新的信息插入在指定學生信息之前，如果未找到指定學生，則追加在鏈表尾部。hpChang62783410Li68752341NULLWang63212986pp(c) 在表尾追加結(jié)點 (p-next=p0; p0-next=NULL) qq Zhao62758421p0Zhao62758421NULL if (strcmp(x,p-name)=0) if (p=head) head=p0; /* 在表頭插入結(jié)點 */ else q-next=p0; /* 在表

24、中間插入結(jié)點 */ p0-next=p; else p-next=p0; /* 在表尾插入結(jié)點 */ p0-next=NULL; h=head; return h; struct node *insert(struct node *head, struct node *p0, char *x) struct node *p,*q; static struct node *h; if (head=NULL) head=p0; /* 空表時，插入結(jié)點 */ p0-next=NULL; else p=head; while (strcmp(x,p-name)!=0 & p-next!=NULL) q

25、=p;p=q-next; 查找插入點查找插入點 #include #include #define NEW (struct node *)malloc(sizeof(struct node)struct node char name20,tel9; struct node *next; ;【例8】學生電話簿鏈表管理程序（演示）。 編制此程序可利用例4至例7的4個函數(shù)完成鏈表的建立、輸出、刪除和插入等功能，這里只需編制一個main函數(shù)完成對這4個函數(shù)的調(diào)用。 #include #define NEW (struct node *)malloc(sizeof(struct node) struct node char name20,tel9; struct node *next; ;main( ) struct node *create( ),*delnode(struct node *, char *); struct node *insert(stru