用指針處理鏈表

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

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

head100010323284129613822008

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

它們連接起來。structnode{charc;

structnode*next;};10322023/2/51

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

函數(shù)原型：void

*malloc(unsignedsize);

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

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

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

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

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

*

定義指針，這是一個(gè)指向非具體數(shù)據(jù)類型的指針，稱為無類型指針。11.7用指針處理鏈表2023/2/52【例11.11】調(diào)用malloc函數(shù)分配所需存儲(chǔ)單元。#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.動(dòng)態(tài)分配和釋放存儲(chǔ)單元

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

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

函數(shù)原型：

void

*calloc(unsignedintn,unsignedintsize);

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

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

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

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

11.7用指針處理鏈表2023/2/54【例11.12】調(diào)用calloc函數(shù)分配所需存儲(chǔ)單元。#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.動(dòng)態(tài)分配和釋放存儲(chǔ)單元

動(dòng)態(tài)分配了10個(gè)存放整型數(shù)據(jù)的存儲(chǔ)單元

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

函數(shù)原型：void

free(void

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

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

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

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

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

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

【例11.13】建立一個(gè)學(xué)生電話簿

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

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

讀入一個(gè)學(xué)生姓名建立單向鏈表NULLhpChang62783410NULLWang63212986NULLpq

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

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

printf("tel:");gets(p->tel);p->next=NULL;if(h==NULL)/*h為空，表示新結(jié)點(diǎn)為第一個(gè)結(jié)點(diǎn)*/

h=p;/*頭指針指向第一個(gè)結(jié)點(diǎn)*/

else/*h不為空*/

q->next=p;/*新結(jié)點(diǎn)與尾結(jié)點(diǎn)相連接*/

q=p;/*使q指向新的尾結(jié)點(diǎn)*/

printf("name:");gets(name);

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

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

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

{

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

if(p==NULL)/*p為NULL，新結(jié)點(diǎn)分配失敗*/{printf("Allocationfailure\n");exit(0);/*結(jié)束程序運(yùn)行*/}#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】輸出學(xué)生電話簿鏈表函數(shù)。4.輸出鏈表hpChang62783410Li68752341NULLWang63212986

p指向第一個(gè)結(jié)點(diǎn)

p=head

當(dāng)p不為NULL

輸出結(jié)點(diǎn)數(shù)據(jù)p指向下一個(gè)結(jié)點(diǎn)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在鏈表中，如果要?jiǎng)h除第i個(gè)結(jié)點(diǎn)，一般是將第（i-1）

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

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

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

表中指定學(xué)生的信息。

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é)點(diǎn)的N-S圖刪除

第一個(gè)結(jié)點(diǎn)

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

刪除結(jié)點(diǎn)工

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

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

qq

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

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

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

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

else

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

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指針向表尾移動(dòng)*/查找結(jié)點(diǎn)

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

6.在單向鏈表中插入結(jié)點(diǎn)hNULL第i個(gè)結(jié)點(diǎn)ppqqp0p新的第i個(gè)結(jié)點(diǎn)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é)點(diǎn)的N-S圖【例11.16】在學(xué)生電話簿鏈表中插入一個(gè)學(xué)生的信息。要求將新的信息插入在指定學(xué)生信息之前，如果未找到指定學(xué)生，則追加在鏈表尾部。

當(dāng)姓名不同并且不是尾結(jié)點(diǎn)循環(huán)空表時(shí)

插入

結(jié)點(diǎn)在表尾

追加結(jié)點(diǎn)

插入結(jié)點(diǎn)工

作分兩步：查找插

入位置連接

新結(jié)點(diǎn)在表頭

插入結(jié)點(diǎn)

在表中間

插入結(jié)點(diǎn)

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

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

qq

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

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

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

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

p0->next=NULL;}

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

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

p0->next=NULL;}else

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

#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】學(xué)生電話簿鏈表管理程序。編制此程序可利用例11.13至例11.16的4個(gè)函數(shù)完成鏈表的建立、輸出、刪除和插入等功能，這里只需編制一個(gè)main函數(shù)完成對這4個(gè)函數(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**