补充内容单向链表.pptx
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《补充内容单向链表.pptx》由会员分享,可在线阅读,更多相关《补充内容单向链表.pptx(57页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、链表的概述链表的概述链表的概念链表:(linked list)就是一些包含数据的独立数据结构(通常称为节点)的集合。也就是说链表就是一种数据结构,是一组结点(node)的集合序列。链表中的每个节点通过链或指针连接在一起。程序通过指针访问链表中的节点。通常节点是动态分配(内存单元)的。第1页/共57页链表概述(谭浩强)链表是一种常见的重要的数据结构。它是动态地进行存储分配的一种结构。第2页/共57页下图表示最简单的一种链表下图表示最简单的一种链表(单向链表单向链表)的结构。的结构。第3页/共57页链表的构成链表的构成 链表有一个“头指针”变量,图中以head表示,它存放一个地址。该地址指向一个元
2、素。链表中每一个元素称为“结点”,每个结点都应包括两个部分:一为用户需要用的实际数据,二为 下 一 个 结 点 的 地 址。可 以 看 出,head指向第一个元素;第一个元素又指向第二个元素直到最后一个元素,该元素不再指向其他元素,它称为“表尾”,它的地址部分放一个“NULL”(表示“空地址”),链表到此结束。第4页/共57页链表中的结点链表中的结点 前面介绍的结构体类型,用它作链表中的结点是最合适的。structstudent intnum;floatscore;structstudent *next;第5页/共57页第6页/共57页处理动态链表所需的函数处理动态链表所需的函数1malloc
3、函数其函数原型为void*malloc(unsigned int size);其作用是在内存的动态存储区中分配一个长度为size的连续空间。第7页/共57页mallocmalloc函数函数此函数的返回值是一个指向分配域起始地址的指针(基类型为void)。如果此函数未能成功地执行(例如内存空间不足),则其返回空指针(NULL)。第8页/共57页2 2 calloccalloc函数函数其函数原型为void*calloc(unsigned n,unsigned size);其作用是在内存的动态区存储中分配n个长度为size的连续空间。函数返回一个指向分配域起始地址的指针;如果分配不成功,返回NULL
4、。用calloc函数可以为一维数组开辟动态存储空间,n为数组元素个数,每个元素长度为size。第9页/共57页3 3 freefree函数函数其函数原型为void free(void*p);其作用是释放由p指向的内存区,使这部分内存区能被其他变量使用。p是调用calloc或malloc函数时返回的值。free函数无返回值。第10页/共57页建立动态链表建立动态链表 所谓建立动态链表是指在程序执行过程中从无到有地建立起一个链表,即一个一个地开辟结点和输入各结点数据,并建立起前后相链的关系。第11页/共57页例例 写一函数建立一个有写一函数建立一个有3 3名学名学生数据的单向动态链表。生数据的单向
5、动态链表。第12页/共57页谭浩强教材中的图谭浩强教材中的图10.13第13页/共57页谭浩强教材中的谭浩强教材中的图图10.14第14页/共57页谭浩强教材中的谭浩强教材中的图图10.15第15页/共57页谭浩强教材中的谭浩强教材中的图图10.16第16页/共57页建立链表的函数可以如下:建立链表的函数可以如下:#define NULL 0#define LEN sizeof(struct student)struct student long num;int score;struct student*next;int n;/*n为全局变量,本模块中各函数均可使用它*/第17页/共57页st
6、ruct student *creat(void)/*定义函数。此函数带回一个指向链表头的指针*/struct student *head;struct student *p1,*p2;n=0;p1=p2=(struct student*)malloc(LEN);/*开辟一个新单元*/scanf(%ld,%d,&p1-num,&p1-score);head=NULL;第18页/共57页while(p1-num!=0)n=n+1;if(n=1)head=p1;else p2-next=p1;p2=p1;p1=(struct student*)malloc(LEN);scanf(%ld,%d,&p
7、1-num,&p1-score);p2-next=NULL;return(head);第19页/共57页在在mainmain函数中调用函数中调用creatcreat函数:函数:main()struct student*head;head=creat();/*调用creat函数 后建立了一个单向动态链表*/第20页/共57页说明说明 (1)第1行为#define宏定义命令行,设置符号常量(或称宏名)NULL代表0,用它表示“空地 址”。第 2行 设 置 LEN代 表struct student类型数据的长度,sizeof是“求字节数运算符”。第21页/共57页说明说明 (2)第9行定义一个cre
8、at函数,即 struct student *creat(void)它是指针类型,即此函数返回一个指 针 值,它 指 向 一 个 struct student类型数据。实际上此creat函数带回一个链表起始地址。第22页/共57页说明说明 (3)malloc(LEN)的作用是开辟一个长度为LEN的内存区,LEN已定义为sizeof(struct student),即结构体struct student的长度。malloc带回的是不指向任何类型数据的指针(void*类型)。而p1、p2是指向struct student类型数据的指针变量,因此必须用强制类型转换的方法使指针的基类型改变为struct
9、 student类型,在malloc(LEN)之前加了“(struct student*)”,它的作用是使malloc返回的指针转换为指向struct student类型数据的指针。注意“*”号不可省略,否则变成转换成struct student类型了,而不是指针类型了。第23页/共57页说明说明 (4)最后一行return后面的参数是head(head已定义为指针变量,指向struct student类型数据)。因此函数返回的是head的值,也就是链表的头地址。(5)n是结点个数。第24页/共57页说明说明 (6)这个算法的思路是让p1指向新开的结点,p2指向链表中最后一个结点,把p1所指的
10、结点连接在p2所 指 的 结 点 后 面,用“p2-next=p1”来实现。第25页/共57页输出链表输出链表 将链表中各结点的数据依次输出。首先要知道链表第一个结点 的 地 址,也 就 是 要 知 道head的值。然后设一个指针变量p,先指向第一个结点,输出p所指的结点,然后使p后移一个结点,再输出。直到链表的尾结点。第26页/共57页例 编写一个输出链表的函数print。void print(struct student*head)struct student *p;printf(nNow,These%d records are:n,n);p=head;if(head!=NULL)第27页
11、/共57页do printf(%ld%dn,p-num,p-score);p=p-next;while(p!=NULL);第28页/共57页算法可用下图表示算法可用下图表示第29页/共57页谭浩强教材中的谭浩强教材中的图图10.18第30页/共57页在在mainmain函数中调用函数中调用print函数:函数:main()struct student*head;long num;head=creat();/*调用creat函数 后建立了一个单向动态链表*/print(head);printf(“input deldte num:”);scanf(“%ld”,&num);del(head,num
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 补充 内容 单向
![提示](https://www.deliwenku.com/images/bang_tan.gif)
限制150内