用指針處理鏈表

鏈表是一種動態(tài)數(shù)據(jù)結(jié)構(gòu)，可根據(jù)需要動態(tài)地分配存儲單元。在數(shù)組中，插入或刪除一個元素都比較繁瑣，而用鏈表則相對容易。但是數(shù)組元素的引用比較簡單，對于鏈表中結(jié)點數(shù)據(jù)的存取操作則相對復雜。

11.7用指針處理鏈表①鏈表中每個元素稱為一個結(jié)點。②構(gòu)成鏈表的結(jié)點必須是結(jié)構(gòu)體類型數(shù)據(jù)。1.鏈表的基本結(jié)構(gòu)

head100010323284129613822008

動態(tài)單向鏈表示意圖C3284H1296A1382I2008NNULL1000A③相鄰結(jié)點的地址不一定是連續(xù)的，依靠指針將

它們連接起來。structnode{charc;

structnode*next;};10322023/2/51

C語言提供了相關(guān)的存儲管理庫函數(shù)。這里僅介紹其中三個，它們的原型說明在“stdlib.h”頭文件和“alloc.h”頭文件中，使用這三個函數(shù)時，應選擇其中一個頭文件包含到源程序中。⑴動態(tài)分配存儲區(qū)函數(shù)malloc()

函數(shù)原型：void

*malloc(unsignedsize);

調(diào)用格式：malloc(size)

功能：在內(nèi)存分配一個size字節(jié)的存儲區(qū)。調(diào)用

結(jié)果為新分配的存儲區(qū)的首地址，是一個void

類型指針。若分配失敗，則返回NULL（即0）。2.動態(tài)分配和釋放存儲單元

在ANSIC標準中，關(guān)鍵字void有兩種用法。第一種用法，可將無返回值的函數(shù)定義為void類型第二種用法，用void

*

定義指針，這是一個指向非具體數(shù)據(jù)類型的指針，稱為無類型指針。11.7用指針處理鏈表2023/2/52【例11.11】調(diào)用malloc函數(shù)分配所需存儲單元。#include<stdlib.h>main(){structst

{intn;

structst

*next;}*p;p=(structst

*)malloc(sizeof(structst));p->n=5;p->next=NULL;

printf("p->n=%d\tp->next=%x\n",p->n,p->next);}2.動態(tài)分配和釋放存儲單元

將函數(shù)返回值轉(zhuǎn)換成結(jié)構(gòu)體指針

11.7用指針處理鏈表2023/2/53⑵動態(tài)分配存儲區(qū)函數(shù)calloc()

函數(shù)原型：

void

*calloc(unsignedintn,unsignedintsize);

調(diào)用格式：calloc(n,size)

功能：在內(nèi)存分配一個n倍size字節(jié)的存儲區(qū)。

調(diào)用結(jié)果為新分配的存儲區(qū)的首地址，是一個void

類型指針。若分配失敗，則返回NULL（即0）。2.動態(tài)分配和釋放存儲單元

11.7用指針處理鏈表2023/2/54【例11.12】調(diào)用calloc函數(shù)分配所需存儲單元。#include<stdlib.h>main(){inti,*ip;

ip=(int*)calloc(10,2);for(i=0;i<10;i++)

scanf("%d",ip+i);for(i=0;i<10;i++)

printf("%d",*(ip+i));

printf("\n");}2.動態(tài)分配和釋放存儲單元

動態(tài)分配了10個存放整型數(shù)據(jù)的存儲單元

11.7用指針處理鏈表2023/2/55⑶釋放動態(tài)分配存儲區(qū)函數(shù)free()

函數(shù)原型：void

free(void

*p);2.動態(tài)分配和釋放存儲單元

此函數(shù)無返回值實參必須是一個指向動態(tài)分配存儲區(qū)

的指針，它可以是任何類型的指針變量。調(diào)用格式：free(p)功能：釋放p所指向的動態(tài)分配的存儲區(qū)。11.7用指針處理鏈表2023/2/56q

建立鏈表就是根據(jù)需要一個一個地開

辟新結(jié)點，在結(jié)點中存放數(shù)據(jù)并建立結(jié)點

之間的鏈接關(guān)系。

【例11.13】建立一個學生電話簿

的單向鏈表函數(shù)。3.建立單向鏈表頭指針h設為NULL讀入一個學生姓名當姓名長度不為0開辟新結(jié)點p=NEW

strcpy(p->name,name)gets(p->tel)p->next=NULLh==NULLTFh指向第一個連接新結(jié)點結(jié)點h=pq->next=pq指向新的尾結(jié)點q=p

讀入一個學生姓名建立單向鏈表NULLhpChang62783410NULLWang63212986NULLpq

11.7用指針處理鏈表2023/2/57

strcpy(p->name,name);/*為新結(jié)點中的成員賦值*/

printf("tel:");gets(p->tel);p->next=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);

}returnh;}structnode*create(){staticstructnode*h;

structnode*p,*q;charname[20];h=NULL;

printf("name:");gets(name);while(strlen(name)!=0)/*當輸入的姓名不是空串循環(huán)*/

{

p=NEW;/*開辟新結(jié)點*/

if(p==NULL)/*p為NULL，新結(jié)點分配失敗*/{printf("Allocationfailure\n");exit(0);/*結(jié)束程序運行*/}#include<stdlib.h>#include<string.h>#defineNEW(structnode*)malloc(sizeof(structnode))structnode{charname[20],tel[9];

structnode*next;};main(){structnode*head;……h(huán)ead=create();……}11.7用指針處理鏈表2023/2/58【例11.14】輸出學生電話簿鏈表函數(shù)。4.輸出鏈表hpChang62783410Li68752341NULLWang63212986

p指向第一個結(jié)點

p=head

當p不為NULL

輸出結(jié)點數(shù)據(jù)p指向下一個結(jié)點p=p->next輸出鏈表的N-S圖pppNULL11.7用指針處理鏈表2023/2/59voidprlist(structnode*head){structnode*p;p=head;while(p!=NULL){printf("%s\t%s\n",p->name,p->tel);p=p->next;}}#include<stdlib.h>#include<string.h>#defineNEW(structnode*)malloc(sizeof(structnode))structnode{charname[20],tel[9];

structnode*next;};main(){structnode*head;……h(huán)ead=create();

prlist(head);……}11.7用指針處理鏈表2023/2/510在鏈表中，如果要刪除第i個結(jié)點，一般是將第（i-1）

個結(jié)點直接與第（i+1）個結(jié)點相連接，然后再釋放第i個

結(jié)點的存儲單元。5.刪除單向鏈表中指定的結(jié)點hNULL第i-1個結(jié)點第i個結(jié)點第i+1個結(jié)點

11.7用指針處理鏈表2023/2/511【例11.15】刪除學生電話簿鏈

表中指定學生的信息。

p=headwhile(strcmp(x,p->name)!=0&&p->next!=NULL)q指針跟隨p指針后移查找(q=p;p=p->next;)

strcmp(x,p->name)==0TFp==headTFhead=p->nextq->next=p->next沒找到

free(p)刪除鏈表中指定結(jié)點的N-S圖刪除

第一個結(jié)點

刪除中間結(jié)點或尾結(jié)點

刪除結(jié)點工

作分兩步：查找結(jié)點刪除結(jié)點學生姓名當姓名不同并且不是尾結(jié)點循環(huán)11.7用指針處理鏈表2023/2/512【例11.15】刪除學生電話簿鏈表中指定學生的信息。hpChang62783410Li68752341NULLWang63212986(a)刪除第一個結(jié)點(head=p->next)11.7用指針處理鏈表2023/2/513【例11.15】刪除學生電話簿鏈表中指定學生的信息。hpChang62783410Li68752341NULLWang63212986(b)刪除中間結(jié)點或尾結(jié)點(q->next=p->next)p

q11.7用指針處理鏈表2023/2/514【例11.15】刪除學生電話簿鏈表中指定學生的信息。hpChang62783410Li68752341NULLWang63212986pp(c)未找到指定的結(jié)點(strcmp(x,p->name)!=0)

qq

11.7用指針處理鏈表2023/2/515

if(strcmp(x,p->name)==0){if(p==head)head=p->next;/*刪除頭結(jié)點*/

elseq->next=p->next;/*刪除中間或尾結(jié)點*/

free(p);/*釋放被刪除的結(jié)點*/}

else

printf("Notfound.");/*未找到指定的結(jié)點*/

h=head;returnh;}#include<stdlib.h>#include<string.h>#defineNEW(structnode*)malloc(sizeof(structnode))structnode{charname[20],tel[9];

structnode*next;};structnode*delnode(structnode*head,char*x){structnode*p,*q;staticstructnode*h;if(head==NULL){printf("Thisisaemptylist.");/*空鏈表情況*/

returnhead;}p=head;while(strcmp(x,p->name)!=0&&p->next!=NULL)

{q=p;p=p->next;}/*q指針尾隨p指針向表尾移動*/查找結(jié)點

11.7用指針處理鏈表2023/2/516將一個新結(jié)點插入到鏈表中，首先要尋找插入的位置。如果要求在第i個結(jié)點前插入，可設置三個工作指針p0、p和q，p0是指向待插入結(jié)點的指針。利用p和q指針查找第i個結(jié)點，找到后再將新結(jié)點鏈接到鏈表上。

6.在單向鏈表中插入結(jié)點hNULL第i個結(jié)點ppqqp0p新的第i個結(jié)點11.7用指針處理鏈表2023/2/517

head==NULLTFp=headhead=p0while(strcmp(x,p->name)!=0&&p->next!=NULL)p0->nextq指針跟隨p指針后移查找(q=p;p=p->next;)=NULL

strcmp(x,p->name)==0TFp==headTFp->next=p0head=p0q->next=p0p0->next=NULLp0->next=p

在鏈表指定位置前插入結(jié)點的N-S圖【例11.16】在學生電話簿鏈表中插入一個學生的信息。要求將新的信息插入在指定學生信息之前，如果未找到指定學生，則追加在鏈表尾部。

當姓名不同并且不是尾結(jié)點循環(huán)空表時

插入

結(jié)點在表尾

追加結(jié)點

插入結(jié)點工

作分兩步：查找插

入位置連接

新結(jié)點在表頭

插入結(jié)點

在表中間

插入結(jié)點

11.7用指針處理鏈表2023/2/518【例11.16】在學生電話簿鏈表中插入一個學生的信息。要求將新的信息插入在指定學生信息之前，如果未找到指定學生，則追加在鏈表尾部。hpChang62783410Li68752341NULLWang63212986(a)在表頭插入結(jié)點(head=p0;p0->next=p)Zhao62758421p011.7用指針處理鏈表2023/2/519【例11.16】在學生電話簿鏈表中插入一個學生的信息。要求將新的信息插入在指定學生信息之前，如果未找到指

定學生，則追加在鏈表尾部。hChang62783410Li68752341NULLWang63212986(b)在表中間插入結(jié)點(q->next=p0;p0->next=p)pqZhao62758421p011.7用指針處理鏈表2023/2/520【例11.16】在學生電話簿鏈表中插入一個學生的信息。要求將新的信息插入在指定學生信息之前，如果未找到指定學生，則追加在鏈表尾部。hpChang62783410Li68752341NULLWang63212986pp(c)在表尾追加結(jié)點(p->next=p0;p0->next=NULL)

qq

Zhao62758421p0Zhao62758421NULL11.7用指針處理鏈表2023/2/521

if(strcmp(x,p->name)==0){if(p==head)head=p0;/*在表頭插入結(jié)點*/

elseq->next=p0;/*在表中間插入結(jié)點*/

p0->next=p;}else{p->next=p0;/*在表尾插入結(jié)點*/

p0->next=NULL;}

}h=head;returnh;}structnode*insert(structnode*head,structnode*p0,

char*x){structnode*p,*q;staticstructnode*h;if(head==NULL){head=p0;/*空表時，插入結(jié)點*/

p0->next=NULL;}else

{p=head;while(strcmp(x,p->name)!=0&&p->next!=NULL){q=p;p=q->next;}查找插入點

#include<stdlib.h>#include<string.h>#defineNEW(structnode*)malloc(sizeof(structnode))structnode{charname[20],tel[9];

structnode*next;};11.7用指針處理鏈表2023/2/522【例11.17】學生電話簿鏈表管理程序。編制此程序可利用例11.13至例11.16的4個函數(shù)完成鏈表的建立、輸出、刪除和插入等功能，這里只需編制一個main函數(shù)完成對這4個函數(shù)的調(diào)用。#include<stdlib.h>#defineNEW(structnode*)malloc(sizeof(structnode))

structnode{charname[20],tel[9];

structnode*next;};11.7用指針處理鏈表2023/2/523main(){structnode*create(),*delnode(structnode*,char*);

structnode*insert(structnode*,structnode*,char*);voidprlist(structnode*);

structnode*head=NULL,*stu;chars[80],name[20];

intc;11.7用指針處理鏈表2023/2/524do

{do

{

printf("\n****MENU**