C语言-链表课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《C语言-链表课件.ppt》由用户(晟晟文业)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 语言 课件
- 资源描述:
-
1、第十一章 链表1ppt课件例:跳马。依下图将每一步跳马之后的位置例:跳马。依下图将每一步跳马之后的位置(x,y)(x,y)放放到一个到一个“结点结点”里,再用里,再用“链子穿起来链子穿起来”,形成,形成一条链,相邻两结点间用一个指针将两者连到一一条链,相邻两结点间用一个指针将两者连到一起。起。结构的概念与应用结构的概念与应用2ppt课件依上图有依上图有7个结点个结点(x1,y1)(x1,y1)(x2,y2)(x2,y2)(x6,y6)(x6,y6)(x7,y7)(x7,y7)为了表示这种既有数据又有指针的情况,为了表示这种既有数据又有指针的情况,引入结构这种数据类型。引入结构这种数据类型。3p
2、pt课件11.7 11.7 用指针处理链表用指针处理链表链表是程序设计中一种重要的动态数据结构,链表是程序设计中一种重要的动态数据结构,它是动态地进行存储分配的一种结构。它是动态地进行存储分配的一种结构。动态性体现为:动态性体现为:n链表中的元素个数可以根据需要增加和减少,不链表中的元素个数可以根据需要增加和减少,不像数组,在声明之后就固定不变;像数组,在声明之后就固定不变;n元素的位置可以变化,即可以从某个位置删除,元素的位置可以变化,即可以从某个位置删除,然后再插入到一个新的地方;然后再插入到一个新的地方;4ppt课件12491249 A A13561356 B B14751475 C C
3、10211021 D DNullNull1 1、链表中的元素称为、链表中的元素称为“结点结点”,每个结点包括两,每个结点包括两个域:个域:数据域和指针域;数据域和指针域;2 2、单向链表通常由一个头指针(、单向链表通常由一个头指针(head)head),用于指向,用于指向链表头;链表头;3 3、单向链表有一个尾结点,该结点的指针部分指、单向链表有一个尾结点,该结点的指针部分指向一个空结点向一个空结点(NULL)(NULL)。Head 1249 1356 1475 1021结点里的指针是存放下一个结点的地址5ppt课件链表中结点的定义链表中结点的定义q链表是由结点构成的,链表是由结点构成的,关键
4、是定义结点关键是定义结点;q链表的结点定义打破了先定义再使用的限制链表的结点定义打破了先定义再使用的限制,即可以用自己定义自己;即可以用自己定义自己;q递归函数的定义也违反了先定义再使用;递归函数的定义也违反了先定义再使用;这是这是C C语言程序设计上的两大特例语言程序设计上的两大特例6ppt课件链表的基本操作链表的基本操作对链表的基本操作有:对链表的基本操作有:(1 1)创建链表是创建链表是指,从无到有地建立起一个链表,指,从无到有地建立起一个链表,即往空链表中依次插入若干结点,并保持结点即往空链表中依次插入若干结点,并保持结点之间的前驱和后继关系。之间的前驱和后继关系。(2 2)检索操作检
5、索操作是指,按给定的结点索引号或检索是指,按给定的结点索引号或检索条件,查找某个结点。如果找到指定的结点,条件,查找某个结点。如果找到指定的结点,则称为检索成功;否则,称为检索失败。则称为检索成功;否则,称为检索失败。(3 3)插入操作插入操作是指,在结点是指,在结点k ki-1i-1与与k ki i之间插入一个之间插入一个新的结点新的结点k k,使线性表的长度增,使线性表的长度增1 1,且,且k ki-1i-1与与k ki i的的逻辑关系发生如下变化:逻辑关系发生如下变化:插入前,插入前,k ki-1i-1是是k ki i的前驱,的前驱,k ki i是是k ki-1i-1的后继;插入后,的后
6、继;插入后,新插入的结点新插入的结点k k成为成为k ki-1i-1的后继、的后继、k ki i的前驱的前驱.7ppt课件(4 4)删除操作删除操作是指,删除结点是指,删除结点k ki i,使线性表的长度,使线性表的长度减减1 1,且,且k ki-1i-1、k ki i和和k ki+1i+1之间的逻辑关系发生如下变之间的逻辑关系发生如下变化:化:删除前,删除前,k ki i是是k ki+1i+1的前驱、的前驱、k ki-1i-1的后继;删除后,的后继;删除后,k ki-1i-1成为成为k ki+1i+1的前驱,的前驱,k ki+1i+1成为成为k ki-1i-1的后继的后继.(5)(5)打印输
7、出打印输出8ppt课件一个指针类型的成员既可指向其它类型的结构体一个指针类型的成员既可指向其它类型的结构体数据,也可以指向自己所在的结构体类型的数据数据,也可以指向自己所在的结构体类型的数据991019910189.589.59910399103909099107991078585numScorenextnext是是struct student类型中的一个成员,类型中的一个成员,它又它又指向指向struct student类型类型的数据。的数据。换名话说:换名话说:next存放下一个结点的地址存放下一个结点的地址9ppt课件11.7.2 11.7.2 简单链表简单链表#define NULL
8、0struct student long num;float score;struct student *next;main()struct student a,b,c,*head,*p;a.num=99101;a.score=89.5;b.num=99103;b.score=90;c.num=99107;c.score=85;head=&a;a.next=&b;b.next=&c;c.next=NULL;p=head;do printf(%ld%5.1fn,p-num,p-score);p=p-next;while(p!=NULL);例例11.7建建立立和和输输出出一一个个简简单单链链表表各
9、结点在程序中定义,不是临时开辟的,各结点在程序中定义,不是临时开辟的,始终占有内容始终占有内容不放不放,这种链表称为,这种链表称为“静静态链表态链表”10ppt课件 11.7.3 11.7.3 处理动态链表所需的函数处理动态链表所需的函数C C 语言使用系统函数语言使用系统函数动态动态开辟和释放存储单元开辟和释放存储单元1.malloc 1.malloc 函数函数 函数原形:函数原形:void void*malloc(unsigned int size);malloc(unsigned int size);作用:作用:在内存的动态存储区中分配在内存的动态存储区中分配 一个一个 长度为长度为si
10、zesize的连续空间。的连续空间。返回值:返回值:是一个指向分配域起始地址的指针(基本是一个指向分配域起始地址的指针(基本类型类型voidvoid)。)。执行失败:执行失败:返回返回NULLNULL11ppt课件函数原形函数原形:void*calloc(unsigned n,unsigned size);作用:作用:在内存动态区中分配在内存动态区中分配 n n个个 长度为长度为sizesize的的连续空间。连续空间。函数返回值函数返回值:指向分配域起始地址的指针:指向分配域起始地址的指针执行失败:返回执行失败:返回nullnull主要用途主要用途:为一维数组开辟动态存储空间。:为一维数组开辟
11、动态存储空间。n n 为为数组元素个数,每个元素长度为数组元素个数,每个元素长度为sizesize2.calloc2.calloc 函数函数12ppt课件3.free 3.free 函数函数函数原形:函数原形:void free(void void free(void*p p););作用:作用:释放由释放由 p p 指向的内存区。指向的内存区。P:P:是最近一次调用是最近一次调用 calloc calloc 或或 malloc malloc 函数函数时返回的值。时返回的值。free free 函数无返回值函数无返回值动态分配的存储单元在用完后一定要释放,动态分配的存储单元在用完后一定要释放,否
12、则内存会因申请空间过多引起资源不足否则内存会因申请空间过多引起资源不足而出现故障。而出现故障。13ppt课件结点的动态分配结点的动态分配ANSI C ANSI C 的三个函数的三个函数(头文件头文件 malloc.h)void malloc.h)void*malloc(unsigned int size)malloc(unsigned int size)void void*calloc(unsigned n,unsigned size)calloc(unsigned n,unsigned size)void free(void void free(void*p)p)C+C+的两个函数的两个函数
13、new new 类型(初值)类型(初值)delete delete 指针变量指针变量 /*表示释放数组,可有可无)表示释放数组,可有可无)*/使用使用 new new 的优点:的优点:可以通过对象的大小直接分配,而不管对象可以通过对象的大小直接分配,而不管对象的具体长度是多少(的具体长度是多少(p340 p340 例例14.1014.10)14ppt课件11.7.4 11.7.4 建立动态链表建立动态链表基本方法基本方法:三个结点(头结点三个结点(头结点headhead、尾结点、尾结点 NULL NULL 和待插入结点和待插入结点 P P)第一步:定义头结点第一步:定义头结点headhead、
14、尾结点、尾结点 p2p2 和待插入结点和待插入结点p1p1,待插入的结点数据部分初始化;待插入的结点数据部分初始化;第二步:该结点被头结点、尾结点同时指向第二步:该结点被头结点、尾结点同时指向。P1=p2=(struct studentP1=p2=(struct student*)malloc(LEN);)malloc(LEN);头指针部分为头指针部分为空空,head=NULL;head=NULL;第三步:重复申请待插入结点空间,对该结点的数据部第三步:重复申请待插入结点空间,对该结点的数据部分赋值(或输入值),将该结点插入在最前面,或者最分赋值(或输入值),将该结点插入在最前面,或者最后面(
15、书上在尾部插入)后面(书上在尾部插入).P2-next=P1;P2=P1;P2-next=P1;P2=P1;最后最后:P2-next=NULL;:P2-next=NULL;*head,head,*p1,p1,*p2p2使用使用malloc(LEN)malloc(LEN)P2-next=NULL;15ppt课件11.7.4 11.7.4 建立动态链表建立动态链表991019910189.589.5headP1p21.任务是开辟结点和输入数据任务是开辟结点和输入数据2.2.并建立前后相链的关系并建立前后相链的关系待插入的结点待插入的结点p1p1数数据部分初始化据部分初始化,该结该结点被头结点点被头
16、结点head、尾结点尾结点p2同时指向同时指向.16ppt课件图图11.1411.14991019910189.589.5headp299103991039090p1991019910189.589.5headp299103991039090p1(a)(b)p1重复申请待插入重复申请待插入结点空间,对该结结点空间,对该结点的数据部分赋值点的数据部分赋值(或输入值)(或输入值)P2-next P2-next 指向指向p1p1新开辟的结点。新开辟的结点。17ppt课件图图11.1411.14head991019910189.589.5p1p299103991039090(c)P2P2指向新结指向新
17、结点点p2=p1p2=p118ppt课件图图11.1511.15991019910189.589.5991019910189.589.5p299107991078585p1head991019910189.589.5991019910189.589.5p299107991078585p1head(a)(b)19ppt课件 图图11.1611.169910399103909099107991078585p20 00 0p1head991019910189.589.59910399103909099107991078585NULLNULLp20 00 0p1head991019910189.589
18、.520ppt课件例例11.8 11.8 建立一个有建立一个有3 3名学生数据的单向动态链表名学生数据的单向动态链表#define NULL 0#define LEN sizeof(struct student)struct studentlong num;float score;struct student*next;int n;struct student*creat(void)struct student*head;struct student*p1,*p2;n=0;p1=p2=(struct student*)malloc(LEN);scanf(%1d,%f,&p1-num,&p1-s
19、core);head=NULL;结构体类型数据的长度,结构体类型数据的长度,sizeofsizeof是是“字节数运算字节数运算符符”定义指针类型的函数。带回链表的起始地址定义指针类型的函数。带回链表的起始地址开辟长度为开辟长度为LENLEN的内存区的内存区P1,p2P1,p2是指向结构体类型数据的指针变是指向结构体类型数据的指针变量,强行转换成结构体类型量,强行转换成结构体类型假设头指向空结点假设头指向空结点21ppt课件续续while(p1-num!=0)n=n+1;/*n 是结点的个数是结点的个数*/if(n=1)head=p1;else p2-next=p1;p2=p1;p1=(stru
20、ct student*)malloc(LEN);scanf(%1d,%f,&p1-num,&p1-score);p2-next=NULL;return(head);/返回链表的头返回链表的头指针指针算法:算法:p1指向新开的结点指向新开的结点:p1=(stuct student*)malloc(LEN);p1的所指向的结点连接在的所指向的结点连接在p2所指向结点后面,用所指向结点后面,用p2-next=p1来实现。来实现。p2 指向链表中最后建立的结点,指向链表中最后建立的结点,:p2=p1;头指针指向头指针指向p1结点结点P1开辟的新结点链到了开辟的新结点链到了p2的后面的后面P1继续开辟新
21、结点继续开辟新结点给新结点赋值此给新结点赋值此22ppt课件11.7.5 11.7.5 输出链表输出链表链表遍历链表遍历1.1.单向链表总是从头结点开始的;单向链表总是从头结点开始的;2.2.每访问一个结点,就将当前指针向该每访问一个结点,就将当前指针向该结点的下一个结点移动:结点的下一个结点移动:p=p-nextp=p-next;3.3.直至下一结点为空直至下一结点为空 P=NULLP=NULL23ppt课件图图 11.1811.18headp PPNULLNULL24ppt课件例题例题 9 9void print(struct student*head)struct student*p;p
22、rintf(nNow,These%d records are:n,n);p=head;if(head!=NULL)do printf(%ld%5.lfn,p-num,p-score);p=p-next;while(p!=NULL);25ppt课件11.7.6 11.7.6 对链表的删除操作对链表的删除操作删除结点原则:删除结点原则:不改变原来的排列顺序,只是从链表中分离开来,不改变原来的排列顺序,只是从链表中分离开来,撤消原来的链接关系。撤消原来的链接关系。两种情况:两种情况:1 1、要删的结点是头指针所指的结点则直接操作;、要删的结点是头指针所指的结点则直接操作;2 2、不是头结点,要依次往
23、下找。、不是头结点,要依次往下找。另外要考虑:空表和找不到要删除的结点另外要考虑:空表和找不到要删除的结点26ppt课件链表中结点删除链表中结点删除需要由两个临时指针:需要由两个临时指针:P1:P1:判断指向的结点是不是要删除的结点判断指向的结点是不是要删除的结点(用于寻找);(用于寻找);P2:P2:始终指向始终指向P1P1的前面一个结点;的前面一个结点;27ppt课件图图11.1911.19ABDECABDEC(a)(B)28ppt课件图图11.2011.209910199101headp199103991039910799107NULLNULL(a)(b)9910199101head99
24、103991039910799107NULLNULLp2p1原链表原链表P1指向指向头结点头结点P2指向指向p1指向的结指向的结点。点。P1指指向下移一向下移一个结点。个结点。29ppt课件图图11.2011.209910199101head99103991039910799107NULLNULLp19910199101head99103991039910799107NULLNULLp2p1(c)(d)经判断后,第经判断后,第1个结点是要删除个结点是要删除的结点,的结点,head指指向第向第2个结点,个结点,第第1个结点脱离。个结点脱离。经经P1P1找到要删找到要删除的结点后使除的结点后使之脱
25、离。之脱离。30ppt课件例例 题题 1010struct student*del(struct student*head,long num)struct student *p1,*p2;if(head=NULL)printf(nlist null!n);goto end;p1=head;while(num!=p1-num&p1-next!=NULL)p2=p1;p1=p1-next;if(num=p1-num)if(p1=head)head=p1-next;else p2-next=p1-next;printf(delete:%ldn,num);n=n-1;else printf(%ld n
展开阅读全文