c语言程序设计与项目实践第11章课件.ppt

c语言程序设计与项目实践第11章课件.ppt

ID:57057122

大小:2.15 MB

页数:21页

时间:2020-07-30

c语言程序设计与项目实践第11章课件.ppt_第1页
c语言程序设计与项目实践第11章课件.ppt_第2页
c语言程序设计与项目实践第11章课件.ppt_第3页
c语言程序设计与项目实践第11章课件.ppt_第4页
c语言程序设计与项目实践第11章课件.ppt_第5页
资源描述:

《c语言程序设计与项目实践第11章课件.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、第11章链表本章的学习重点◆链表的定义◆结构体实现单链表◆结构体实现双向链表◆链表中插入结点◆链表中删除结点11.1什么是链表链表是物理上的一个个不连续的内存块按照一定的逻辑顺序连接而成的数据结构。每个数据块构成一个结点。结点是链表的基本元素,因此,也可以说链表由结点组合而成。1.链表的结点在存储每个结点数据元素时,除了存储结点本身要承载的数据信息外,还要存储与它相邻的结点的地址信息,这两部分的组合称为结点(Node)。数据域(DataDomain):存储数据信息的内存区域引用域(ReferenceDomain):存储与其相

2、邻结点地址的内存区域,又称为指针域(PointerDomain),如图所示为链表结点的逻辑结构示意图。11.1什么是链表2.单链表的逻辑结构将各个单链表结点按一定顺序连接起来,就构成了链表。表头结点(header):链表的开头,索引链表的起始位置,一般表头结点仅有引用域,而没有数据域,表尾结点:单链表中最后一个结点,通常表尾结点的引用域赋值为空,即为NULL。如图所示为单链表的逻辑结构示意图。11.1什么是链表3.双向链表的逻辑结构双向链表也叫双链表,是链表的一种,它每个数据结点中都有两个引用域,一个用于指向下一个结点,称为

3、直接后继或后继结点,另一个用于指向上一个结点,称为直接前驱或前驱结点。如图所示为双向链表的逻辑结构示意图。4.循环链表的逻辑结构循环链表是将单链表或双向链表的表尾指向表头,从而使链表构成一个环形结构,因此称为循环链表。11.2结构体实现单链表C语言中,可以使用结构体定义链表的结点。由于链表的结点需要包含引用域,用于指向下一个结点的位置,因此,结点中必须包含指针类型成员,用来存放下一个结点的地址。11.2.1单链表结点的结构体实现1.普通结点的定义使用结构体定义单链表结点的一般表达形式为:struct结点名{数据域引用域};例

4、如,要定义一个学生数学成绩的链表,可以使用下面的结点定义:01structStuNode//定义结构体StuNode02{03charName[32];04floatScore;05structStuNode*next;//引用域,以结构体指针表示06};11.2.1单链表结点的结构体实现2.头结点的定义单链表中,头结点仅含有引用域,通常使用header表示。因此,头结点可以使用一个结构体指针来表示。例如,可以使用下面的代码定义上述讨论的链表头结点:structStuNode*header;当链表没有普通结点是称为空结点,对

5、于空结点的链表表头结点,应该赋值为空,可以使用如下语句实现:header=NULL;11.2.2单链表的结构体实现1.结构体变量构成链表将几个具有结点属性的结构体变量连接起来,也可以构成链表。例如,设计一个简单链表。首先定义几个StuNode类型的结构体变量,用于表示链表结点:structStuNodeZhangsan,Lisi,Wangwu,Zhaoliu;structStuNode*header=NULL;01header=&Zhangsan;//表头结点指向结点Zhangsan02Zhangsan.next=&Lisi

6、;//Zhangsan的引用域指向结点Lisi03Lisi.next=&Wangwu;//Lisi的引用域指向结点Wangwu04Wangwu.next=&Zhaoliu;//Wangwu的引用域指向结点Zhaoliu05Zhaoliu.next=NULL;//Zhaoliu的引用域为NULL如图所示为该链表的逻辑结构示意图。11.2.2单链表的结构体实现2.结构体数组构成单链表将结构体数组中各个元素设置为链表结点的结构,并且将各元素按一定规则连接起来也可以构成单链表。范例11.1ListAndStructArray.c有一

7、个含有5个元素的结构体数组,用于存放学生的数学成绩,每个元素中含有成员姓名、学号和成绩。设计一个链表,将学生成绩由高到低排列,并输出排序后的学生信息。3.动态分配结点构成单链表可以动态分配结点构成单链表,例如:structStuNode*stupointer1,*stupointer2,*stupointer3;structStuNode*header=NULL;stupointer1=(structStuNode*)malloc(sizeof(structStuNode));stupointer2=(structStuNo

8、de*)malloc(sizeof(structStuNode));stupointer3=(structStuNode*)malloc(sizeof(structStuNode));将几个动态分配的内存区域连接构成链表:header=stupointer1;//表头指向第一个结点stup

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。