用指针处理链表

链表是一种动态数据结构，可根据需要动态地分配存储单元。在数组中，插入或删除一个元素都比较繁琐，而用链表则相对容易。但是数组元素的引用比较简单，对于链表中结点数据的存取操作则相对复杂。

11.7用指针处理链表①链表中每个元素称为一个结点。②构成链表的结点必须是结构体类型数据。1.链表的基本结构

head100010323284129613822008

动态单向链表示意图C3284H1296A1382I2008NNULL1000A③相邻结点的地址不一定是连续的，依靠指针将

它们连接起来。structnode{charc;

structnode*next;};10322023/2/51

C语言提供了相关的存储管理库函数。这里仅介绍其中三个，它们的原型说明在“stdlib.h”头文件和“alloc.h”头文件中，使用这三个函数时，应选择其中一个头文件包含到源程序中。⑴动态分配存储区函数malloc()

函数原型：void

*malloc(unsignedsize);

调用格式：malloc(size)

功能：在内存分配一个size字节的存储区。调用

结果为新分配的存储区的首地址，是一个void

类型指针。若分配失败，则返回NULL（即0）。2.动态分配和释放存储单元

在ANSIC标准中，关键字void有两种用法。第一种用法，可将无返回值的函数定义为void类型第二种用法，用void

*

定义指针，这是一个指向非具体数据类型的指针，称为无类型指针。11.7用指针处理链表2023/2/52【例11.11】调用malloc函数分配所需存储单元。#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.动态分配和释放存储单元

将函数返回值转换成结构体指针

11.7用指针处理链表2023/2/53⑵动态分配存储区函数calloc()

函数原型：

void

*calloc(unsignedintn,unsignedintsize);

调用格式：calloc(n,size)

功能：在内存分配一个n倍size字节的存储区。

调用结果为新分配的存储区的首地址，是一个void

类型指针。若分配失败，则返回NULL（即0）。2.动态分配和释放存储单元

11.7用指针处理链表2023/2/54【例11.12】调用calloc函数分配所需存储单元。#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.动态分配和释放存储单元

动态分配了10个存放整型数据的存储单元

11.7用指针处理链表2023/2/55⑶释放动态分配存储区函数free()

函数原型：void

free(void

*p);2.动态分配和释放存储单元

此函数无返回值实参必须是一个指向动态分配存储区

的指针，它可以是任何类型的指针变量。调用格式：free(p)功能：释放p所指向的动态分配的存储区。11.7用指针处理链表2023/2/56q

建立链表就是根据需要一个一个地开

辟新结点，在结点中存放数据并建立结点

之间的链接关系。

【例11.13】建立一个学生电话簿

的单向链表函数。3.建立单向链表头指针h设为NULL读入一个学生姓名当姓名长度不为0开辟新结点p=NEW

strcpy(p->name,name)gets(p->tel)p->next=NULLh==NULLTFh指向第一个连接新结点结点h=pq->next=pq指向新的尾结点q=p

读入一个学生姓名建立单向链表NULLhpChang62783410NULLWang63212986NULLpq

11.7用指针处理链表2023/2/57

strcpy(p->name,name);/*为新结点中的成员赋值*/

printf("tel:");gets(p->tel);p->next=NULL;if(h==NULL)/*h为空，表示新结点为第一个结点*/

h=p;/*头指针指向第一个结点*/

else/*h不为空*/

q->next=p;/*新结点与尾结点相连接*/

q=p;/*使q指向新的尾结点*/

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

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

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

printf("name:");gets(name);while(strlen(name)!=0)/*当输入的姓名不是空串循环*/

{

p=NEW;/*开辟新结点*/

if(p==NULL)/*p为NULL，新结点分配失败*/{printf("Allocationfailure\n");exit(0);/*结束程序运行*/}#include<stdlib.h>#include<string.h>#defineNEW(structnode*)malloc(sizeof(structnode))structnode{charname[20],tel[9];

structnode*next;};main(){structnode*head;……head=create();……}11.7用指针处理链表2023/2/58【例11.14】输出学生电话簿链表函数。4.输出链表hpChang62783410Li68752341NULLWang63212986

p指向第一个结点

p=head

当p不为NULL

输出结点数据p指向下一个结点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;……head=create();

prlist(head);……}11.7用指针处理链表2023/2/510在链表中，如果要删除第i个结点，一般是将第（i-1）

个结点直接与第（i+1）个结点相连接，然后再释放第i个

结点的存储单元。5.删除单向链表中指定的结点hNULL第i-1个结点第i个结点第i+1个结点

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)删除链表中指定结点的N-S图删除

第一个结点

删除中间结点或尾结点

删除结点工

作分两步：查找结点删除结点学生姓名当姓名不同并且不是尾结点循环11.7用指针处理链表2023/2/512【例11.15】删除学生电话簿链表中指定学生的信息。hpChang62783410Li68752341NULLWang63212986(a)删除第一个结点(head=p->next)11.7用指针处理链表2023/2/513【例11.15】删除学生电话簿链表中指定学生的信息。hpChang62783410Li68752341NULLWang63212986(b)删除中间结点或尾结点(q->next=p->next)p

q11.7用指针处理链表2023/2/514【例11.15】删除学生电话簿链表中指定学生的信息。hpChang62783410Li68752341NULLWang63212986pp(c)未找到指定的结点(strcmp(x,p->name)!=0)

qq

11.7用指针处理链表2023/2/515

if(strcmp(x,p->name)==0){if(p==head)head=p->next;/*删除头结点*/

elseq->next=p->next;/*删除中间或尾结点*/

free(p);/*释放被删除的结点*/}

else

printf("Notfound.");/*未找到指定的结点*/

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指针向表尾移动*/查找结点

11.7用指针处理链表2023/2/516将一个新结点插入到链表中，首先要寻找插入的位置。如果要求在第i个结点前插入，可设置三个工作指针p0、p和q，p0是指向待插入结点的指针。利用p和q指针查找第i个结点，找到后再将新结点链接到链表上。

6.在单向链表中插入结点hNULL第i个结点ppqqp0p新的第i个结点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

在链表指定位置前插入结点的N-S图【例11.16】在学生电话簿链表中插入一个学生的信息。要求将新的信息插入在指定学生信息之前，如果未找到指定学生，则追加在链表尾部。

当姓名不同并且不是尾结点循环空表时

插入

结点在表尾

追加结点

插入结点工

作分两步：查找插

入位置连接

新结点在表头

插入结点

在表中间

插入结点

11.7用指针处理链表2023/2/518【例11.16】在学生电话簿链表中插入一个学生的信息。要求将新的信息插入在指定学生信息之前，如果未找到指定学生，则追加在链表尾部。hpChang62783410Li68752341NULLWang63212986(a)在表头插入结点(head=p0;p0->next=p)Zhao62758421p011.7用指针处理链表2023/2/519【例11.16】在学生电话簿链表中插入一个学生的信息。要求将新的信息插入在指定学生信息之前，如果未找到指

定学生，则追加在链表尾部。hChang62783410Li68752341NULLWang63212986(b)在表中间插入结点(q->next=p0;p0->next=p)pqZhao62758421p011.7用指针处理链表2023/2/520【例11.16】在学生电话簿链表中插入一个学生的信息。要求将新的信息插入在指定学生信息之前，如果未找到指定学生，则追加在链表尾部。hpChang62783410Li68752341NULLWang63212986pp(c)在表尾追加结点(p->next=p0;p0->next=NULL)

qq

Zhao62758421p0Zhao62758421NULL11.7用指针处理链表2023/2/521

if(strcmp(x,p->name)==0){if(p==head)head=p0;/*在表头插入结点*/

elseq->next=p0;/*在表中间插入结点*/

p0->next=p;}else{p->next=p0;/*在表尾插入结点*/

p0->next=NULL;}

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

char*x){structnode*p,*q;staticstructnode*h;if(head==NULL){head=p0;/*空表时，插入结点*/

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个函数完成链表的建立、输出、删除和插入等功能，这里只需编制一个main函数完成对这4个函数的调用。#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**