单链表基本概念

1、9.5 单链表的基本概念 数组可以看成是一批有先后次序的元素构成的序列，其优点是能用下标随意访问元素，操作简便；不足之处在于元素个数有上限，插入或删除某个元素时需要移动其他元素。 与数组一样，链表也是一种有先后次序的序列，但它的元素可以动态分配，插入或删除元素时不需要移动其他元素，因此常常被看作是与数组互为补充的一种重要的数据构成方式。 设计链表的原则是为了使问题的处理更好理解，更易实现。如果描述一个问题可以使用链表，也可以使用数组，而且使用数组可以更好地进行处理，那就应该选择数组。1. 常见链表示意图 单链表单链表8910189.589103908910785NULL8910189.5891

2、03908910785NULLNULL双链表双链表8910189.589103908910785循环链表循环链表head 1000 1032 3284 1296 1382 2008图图9.2 动态单向链表示意图动态单向链表示意图C3284H1296A1382I2008NNULLNULL1000s1032链表有一个链表有一个“头指针头指针”变量，用变量，用head表示，它存放一个地址。该地址指向一个元素。表示，它存放一个地址。该地址指向一个元素。链表中每个元素称为一个结点，每个结点包括两个部分：用户需要的普通数据、下一链表中每个元素称为一个结点，每个结点包括两个部分：用户需要的普通数据、下一个结

3、点的地址。可以看出个结点的地址。可以看出head指向第一个元素，第一个元素又指向第二个元素指向第一个元素，第一个元素又指向第二个元素，直到直到最后一个元素，该元素不再指向其他元素，它称为最后一个元素，该元素不再指向其他元素，它称为“表尾表尾”，它的地址部分放一，它的地址部分放一个个“NULL”（表示空地址），链表到此结束。（表示空地址），链表到此结束。构成链表的结点必须是结构体类型数据。构成链表的结点必须是结构体类型数据。相邻结点的地址不一定是连续的，依靠指针将它们连接起来。要找某一元素，必须先相邻结点的地址不一定是连续的，依靠指针将它们连接起来。要找某一元素，必须先找到上一个元素，根据它提供

4、的下一元素地址才能找到下一个元素。如果不提供找到上一个元素，根据它提供的下一元素地址才能找到下一个元素。如果不提供“头头指针指针”（head），则整个链表都无法访问。），则整个链表都无法访问。2. 链表的基本结构 struct nodechar c; struct node *next; ;next是是struct node类型中的一个成员，类型中的一个成员，它又指向它又指向struct node 类型的数据类型的数据(这这就是就是next所在的结构体类型）所在的结构体类型） 链表是一种动态数据结构，可根据需要链表是一种动态数据结构，可根据需要动态地分配存储单元。在数组中，插入或删动态地分配存

5、储单元。在数组中，插入或删除一个元素都比较繁琐，而用链表则相对容除一个元素都比较繁琐，而用链表则相对容易。但是数组元素的引用比较简单，对于链易。但是数组元素的引用比较简单，对于链表中结点数据的存取操作则相对复杂。表中结点数据的存取操作则相对复杂。 3. 静态链表 【例1】建立一个如图所示的简单链表，它由3个学生数据的结点组成。输出各结点中的数据。 #define NULL 0 struct student long num; float score; struct student *next; /*next指向struct student 类型数据*/ ; 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; /*对结点的num和score成员赋值*/ head=&a; /*将结点a的起始地址赋给头指针head*/ 8910189.589103908910785numscorenext a.next=&b; /*将结点b的起始地址赋给a结点的next成员*/ b.next=&c; /*将结点c的起始地址赋给b结点的next成员*/ c.next=NULL; /*c结点的next成员不存放其他结点地址*/

7、 p=head; /*使p指针指向a结点*/do printf(%ld%5.1fn,p-num, p-score); /*输出p指向的结点的数据*/ p= p- next /*使p指向下一结点*/ while(p!=NULL); /*输出完c结点后p的值为NULL*/本例比较简单，所有结点都是在程序中定义的，不是临时开辟的，也不能用完后释放，这种链表称为“静态链表”。 C语言提供了相关的存储管理库函数。这里语言提供了相关的存储管理库函数。这里仅介绍其中三个，它们的原型说明在仅介绍其中三个，它们的原型说明在“stdlib.h”头文件和头文件和“alloc.h”头文件中，使用头文件中，使用这三个函

8、数时，应选择其中一个头文件包含到这三个函数时，应选择其中一个头文件包含到源程序中。源程序中。 动态分配存储区函数malloc( ) 函数原型：void *malloc(unsigned size); 调用格式：malloc(size) 功能：在内存的动态存储区中分配一个长度为size的连续空间。调用结果为新分配的存储区的首地址，是一个void类型指针。若分配失败，则返回空指针（即NULL ）。4. 动态分配和释放存储单元 在ANSI C标准中，关键字void有两种用法。第一种用法，可将无返回值的函数定义为void类型第二种用法，用void * 定义指针，这是一个指向非具体数据类型的指针，称为无

9、类型指针。 【例2】调用malloc函数分配所需存储单元。 #include main( ) struct st int n; struct st *next; *p; p=(struct st *)malloc(sizeof(struct st); p-n=5; p-next=NULL; /*系独立结点*/ printf(p-n=%dtp-next=%xn,p-n,p-next); 4. 动态分配和释放存储单元 将函数返回值转换成结构将函数返回值转换成结构体指针。体指针。void void * *强制转换强制转换成成struct st struct st * *结果：p-n=5 p-next

10、=0 动态分配存储区函数calloc( ) 函数原型： void *calloc(unsigned int n,unsigned int size); 调用格式：calloc(n,size) 功能：在内存的动态区存储中分配n个长度为size的连续空间。函数返回一个指向分配域起始地址的指针；如果分配不成功，则返回NULL（即0）。 用calloc函数可以为一维数组开辟动态存储空间，n为数组元素个数，每个元素长度为size。4. 动态分配和释放存储单元 【例3】调用calloc函数分配所需存储单元。 #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指向第一个指向第一个 连接新结点连接新结点 结点结点 h=p q-next=p q指向新的尾结点指向新的尾结点 q=p 读入一个学生姓名读入一个学生姓名图图9.3 建立单向链表建立单向链表NULLhpChang62783410NULLWang63212986NULLpq 把把p p所指的结点作为所指的结点作为第一个结点第一个结点 把把p p所指的结点连接到表尾所指的结点连接到表尾q q移到表尾移到表尾 s

12、trcpy(p-name,name); /* 为新结点中的成员赋值 */ printf(tel: ); gets(p-tel); p-next=NULL; /*p所指的下一个结点的地址为NULL*/ if (h=NULL) /* h为空，表示新结点为第一个结点 */ h=p; /* 头指针指向第一个结点 */ else /* h不为空 */ q-next=p; /* 新结点与尾结点相连接 */ q=p; /* 使q指向新的尾结点 */ 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) /* 当输入的姓名不是空串循环 */ p=NEW; /* 开辟新结点 */ if (p=NULL) /* p为NULL，新结点分配失败 */ printf(Allocation failuren); exit(0); /* 结束程序运行 */ #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】输出学生电话簿链表函数。6. 输出单向链表中各结点信息 hpChang62783410Li68752341NULLWang63212986 p指向第一个结点指向第一个结点 p=head 当当p不为不为NULL 输出结点数据输出结点数据 p指向下一个结点指向下一个结点 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个结点，一般是将第（i-1）个结点直接与第（i+1）个结点相连接，然后再释放

16、第i个结点的存储单元 。7. 删除单向链表中指定的结点 hNULLNULL第第i-1个结点个结点 第第i个结点个结点 第第i+1个结点个结点 【例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 没找到没找到 free(p)图图9.9 删除链表中指定结点的删除链表中指定结点的N-S图图删除删除第一个第

17、一个结点结点 删除中间删除中间结点或尾结点或尾结点结点 删除结点工删除结点工作分两步：作分两步：查找结点查找结点删除结点删除结点学生姓名学生姓名当姓名不同并且当姓名不同并且不是尾结点循环不是尾结点循环【例6】删除学生电话簿链表中指定学生的信息。hpChang62783410Li68752341NULLWang63212986(a) 删除第一个结点 (head=p-next)【例6】删除学生电话簿链表中指定学生的信息。hpChang62783410Li68752341NULLWang63212986(b) 删除中间结点或尾结点 (q-next=p-next)p q【例6】删除学生电话簿链表中指定

18、学生的信息。hpChang62783410Li68752341NULLWang63212986pp(c) 未找到指定的结点 (strcmp(x,p-name)!=0) qq if (strcmp(x,p-name)=0) if (p=head) head=p-next; /* 删除头结点 */ else q-next=p-next; /* 删除中间或尾结点 */ free(p); /* 释放被删除的结点 */ else printf(Not found.); /* 未找到指定的结点 */ 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指针向表尾移动 */查找结点查找结点 将一个新结点插入到链表中，首先要寻找插入的位置。如果要求在第i个结点前插入，可设置三个工作指针p0、p和q，p0是指向待插入结点的指针。利用p和q指针查找第i个结点，找到后再将新结点链接到链表上。 8. 在单向链表中插入结点 hNULLNULL第第i个结点个结点ppqqp0p新的第新的第i个结点个结点 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 在链表指定位置前插入结点的在链表指定位置前插入结点的N-S图图【例7】在学生电话簿链表中插入一个学生的信息。要求将新的信息插入在指定学生信息之前，如果未找到指定学生，则追加在链表尾部。 当姓名不同并且当姓名不同并且不是尾结点循环不是尾结点循环空表时空表时插入插入结点结点在表尾在表尾追加结点追加结点 插入结点工插入结点工作分两步：作分两步：查找插查找插入位置入

22、位置连接连接新结点新结点在表头在表头插入结点插入结点 在表中间在表中间插入结点插入结点 【例7】在学生电话簿链表中插入一个学生的信息。要求将新的信息插入在指定学生信息之前，如果未找到指定学生，则追加在链表尾部。hpChang62783410Li68752341NULLWang63212986(a) 在表头插入结点 (head=p0; p0-next=p)Zhao62758421p0【例7】在学生电话簿链表中插入一个学生的信息。要求将新的信息插入在指定学生信息之前，如果未找到指定学生，则追加在链表尾部。hChang62783410Li68752341NULLWang63212986(b) 在表中

23、间插入结点 (q-next=p0; p0-next=p)pqZhao62758421p0【例7】在学生电话簿链表中插入一个学生的信息。要求将新的信息插入在指定学生信息之前，如果未找到指定学生，则追加在链表尾部。hpChang62783410Li68752341NULLWang63212986pp(c) 在表尾追加结点 (p-next=p0; p0-next=NULL) qq Zhao62758421p0Zhao62758421NULL if (strcmp(x,p-name)=0) if (p=head) head=p0; /* 在表头插入结点 */ else q-next=p0; /* 在表

24、中间插入结点 */ p0-next=p; else p-next=p0; /* 在表尾插入结点 */ 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; /* 空表时，插入结点 */ 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个函数完成链表的建立、输出、删除和插入等功能，这里只需编制一个main函数完成对这4个函数的调用。 #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