单链表的基本概念_第1页
单链表的基本概念_第2页
单链表的基本概念_第3页
单链表的基本概念_第4页
单链表的基本概念_第5页
已阅读5页,还剩27页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

9.5单链表的基本概念

数组可以看成是一批有先后次序的元素构成的序列,其优点是能用下标随意访问元素,操作简便;不足之处在于元素个数有上限,插入或删除某个元素时需要移动其他元素。与数组一样,链表也是一种有先后次序的序列,但它的元素可以动态分配,插入或删除元素时不需要移动其他元素,因此常常被看作是与数组互为补充的一种重要的数据构成方式。

设计链表的原则是为了使问题的处理更好理解,更易实现。如果描述一个问题可以使用链表,也可以使用数组,而且使用数组可以更好地进行处理,那就应该选择数组。1.常见链表示意图

单链表8910189.589103908910785NULL8910189.589103908910785NULLNULL双链表8910189.589103908910785循环链表head100010323284129613822008图9.2动态单向链表示意图C3284H1296A1382I2008NNULL1000s1032①链表有一个“头指针”变量,用head表示,它存放一个地址。该地址指向一个元素。②链表中每个元素称为一个结点,每个结点包括两个部分:用户需要的普通数据、下一个结点的地址。可以看出head指向第一个元素,第一个元素又指向第二个元素……,直到最后一个元素,该元素不再指向其他元素,它称为“表尾”,它的地址部分放一个“NULL”(表示空地址),链表到此结束。③构成链表的结点必须是结构体类型数据。④相邻结点的地址不一定是连续的,依靠指针将它们连接起来。要找某一元素,必须先找到上一个元素,根据它提供的下一元素地址才能找到下一个元素。如果不提供“头指针”(head),则整个链表都无法访问。2.链表的基本结构

structnode{charc;

structnode*next;};next是structnode类型中的一个成员,它又指向structnode类型的数据(这就是next所在的结构体类型)

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

3.静态链表

【例1】建立一个如图所示的简单链表,它由3个学生数据的结点组成。输出各结点中的数据。

#defineNULL0

structstudent{longnum;floatscore;

structstudent*next;/*next指向structstudent类型数据*/};main(){structstudenta,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成员不存放其他结点地址*/p=head;/*使p指针指向a结点*/do{printf("%ld%5.1f\n",p->num,p->score);/*输出p指向的结点的数据*/p=p->next/*使p指向下一结点*/}while(p!=NULL);/*输出完c结点后p的值为NULL*/}本例比较简单,所有结点都是在程序中定义的,不是临时开辟的,也不能用完后释放,这种链表称为“静态链表”。

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

函数原型:void

*malloc(unsignedsize);

调用格式:malloc(size)

功能:在内存的动态存储区中分配一个长度为size的连续空间。调用结果为新分配的存储区的首地址,是一个void类型指针。若分配失败,则返回空指针(即NULL

)。4.动态分配和释放存储单元

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

*

定义指针,这是一个指向非具体数据类型的指针,称为无类型指针。【例2】调用malloc函数分配所需存储单元。

#include<stdlib.h>main(){struct

st{intn;

struct

st

*next;}*p;p=(struct

st

*)malloc(sizeof(struct

st));p->n=5;p->next=NULL;/*系独立结点*/

printf("p->n=%d\tp->next=%x\n",p->n,p->next);}4.动态分配和释放存储单元

将函数返回值转换成结构体指针。void*强制转换成struct

st*结果:p->n=5p->next=0⑵动态分配存储区函数calloc()

函数原型:

void

*calloc(unsigned

int

n,unsigned

intsize);

调用格式:calloc(n,size)

功能:在内存的动态区存储中分配n个长度为size的连续空间。函数返回一个指向分配域起始地址的指针;如果分配不成功,则返回NULL(即0)。

用calloc函数可以为一维数组开辟动态存储空间,n为数组元素个数,每个元素长度为size。4.动态分配和释放存储单元

【例3】调用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");}4.动态分配和释放存储单元

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

如:输入:1、2、3……10

输出:1、2、3……10⑶释放动态分配存储区函数free()

函数原型:void

free(void

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

此函数无返回值

实参必须是一个指向动态分配存储区

的指针,它可以是任何类型的指针变量。调用格式:free(p)功能:释放由p指向的内存区,使这部分内存区能被其他变量使用。p是最近一次调用malloc或calloc函数时返回的值。free函数无返回值。

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

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

之间的链接关系。

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

的单向链表函数。5.建立单向链表头指针h设为NULL读入一个学生姓名当姓名长度不为0

开辟新结点p=NEW

strcpy(p->name,name)

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

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

把p所指的结点作为第一个结点

把p所指的结点连接到表尾q移到表尾

strcpy(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);

}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();

……}【例5】输出学生电话簿链表函数。6.输出单向链表中各结点信息hpChang62783410Li68752341NULLWang63212986

p指向第一个结点

p=head

当p不为NULL

输出结点数据

p指向下一个结点

p=p->next图9.5输出链表的N-S图pppNULLvoidprlist(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);

……}

在链表中,如果要删除第i个结点,一般是将第(i-1)个结点直接与第(i+1)个结点相连接,然后再释放第i个结点的存储单元。7.删除单向链表中指定的结点hNULL第i-1个结点第i个结点第i+1个结点

【例6】删除学生电话簿链

表中指定学生的信息。

p=head

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

第一个结点

删除中间结点或尾结点

删除结点工

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

q【例6】删除学生电话簿链表中指定学生的信息。hpChang62783410Li68752341NULLWang63212986pp(c)未找到指定的结点(strcmp(x,p->name)!=0)

qq

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

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

8.在单向链表中插入结点hNULL第i个结点ppqqp0p新的第i个结点

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

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

插入

结点在表尾

追加结点

插入结点工

作分两步:查找插

入位置连接

新结点在表头

插入结点

在表中间

插入结点

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

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

qq

Zhao62758421p0Zhao62758421NULLif(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;};【例8】学生电话簿链表管理程序(演示)。

编制此程序可利用例4至例7的4个函数完成链表的建立、输出、删除和插入等功能,这里只需编制一个main函数完成对这4个函数的调用。

#include<stdlib.h>#defineNEW(structnode*)malloc(sizeof(structnode))

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

structnode*next;};main(){structnode*create(),*delnode(structnode*,char*);

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

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论