版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、数 据 结 构,第七课 线性表的链式表示与实现,第八课:线性表的链式表示与实现,本课主题: 线性表的链式表示与实现 教学目的: 掌握线性链表、单链表、静态链表的概 念、表示及实现方法 教学重点: 线性链表之单链表的表示及实现方法。 教学难点: 线性链表的概念。 复 习:顺序表的定义。,二、线性链表的概念:,1.线性链表:以链式结构存储的线性表称之为线性链表。 特点是该线性表中的数据元素可以用任意的存储单元来存储。线性表中逻辑相邻的两元素的存储空间可以是不连续的。 插入、删除操作是不再需要移动大量的元素,但失去了顺序表的可随机存取特点。,2.结点(Node):数据元素的映象用一个结点来表示。结点
2、的一个域表示元素本身,称为数据域, 另一个域是能指示其后继的指针 ,称为指针域, 用来表示线性表数据元素的逻辑关系。 3用线性链表表示线性表时,数据元素之间的逻辑关系是由结点中的指针指示的,链式结构存储的线性表实例,链表的种类,链表可分为单链表、循环链表和双向链表。 单链表:链表中的每一个结点中只包含一个指针域的称为单链表或线性链表。,二、线性链表(单链表)的存储实现,struct LNODE ElemType data; struct LNODE *next; ; typedef struct LNODE LNode; typedef struct LNODE * LinkList;,头指针
3、与头结点的区别: 头指针只相当于结点的指针域,头结点即整个线性链表的第一个结点,它的数据域可以放数据元素,也可以放线性表的长度等附加信息,也可以不存储任何信息。,三、线性表(单链表)的操作实现(类C语言)(1),1. 初始化操作 Status Init_L(LinkList L) if (L=(LinkList *)malloc(sizeof(LNode) L-next=NULL;return 1; else return 0; ,三、线性表(单链表)的操作实现(类C语言)(2),2. 插入操作:要在数据元素a和b 之间插入元素x。 算法思想:决定a和b之间的相邻关系是由a 的指针决定的。若要
4、实现插入,生成x结点,然后让a 的指针指向x 且x 的指针指向b。实现三个元a、x和b的逻辑关系。 设p为指向结点a 的指针,s为指向结点x的指针,则修改s、a的指针: snext=pnext;pnext=s;,插入操作 Status ListInsert_L(LinkList /ListInsert_L,三、线性表(单链表)的操作实现(类C语言)(3),3. 删除操作:在单链表数据元素a、b、c三个相邻的元素中删除b, 算法思想:就是要让a 的指针直接指向c,使b从链表中脱离。 即,pnext=pnextnext Status ListDelete_L(LinkList /ListDelet
5、e_L,三、线性表(单链表)的操作实现(类C语言)(4),4.取某序号元素的操作 算法思想:单链表是非随机存取结构。每个元素的位置信息都包含在前驱结点的信息中,所以取得第i个元素必须从头指针出发寻找。设置一个指针变量指向第一个结点,然后,让该指针变量逐一向后指向,直到第i个元素。,取某序号元素的操作 Status GetElem_L(LinkList /GetElem_L,三、线性表(单链表)的操作实现(类C语言)(5),5.归并两个单链表的操作例:将两个有序链表合并为一个有序链表。 算法思想:设立三个指针pa、pb和pc 分别用来指向两个有序链表和合并表的当前元素。比较两个表的当前元素的大小
6、,将小的元素链接到合并表中,即,让合并表的当前指针指向该元素,然后,修改指针。在归并两个链表为一个链表时,不需要另建新表的结点空间,而只需将原来两个链表中结点之间的关系解除,重新建立关系。,归并两个单链表的操作void MergeList_L(LinkList pb=Lb-next; Lc=pc=La; while(pa /MergeList_L C语言实现的例子。,四、 静态单链表有些高级语言没有指针,我们可以用数组来表示单链表,在数组中,以整型游标来代替指针。这种用数组描述的链表称为静态链表。,静态单链表存储结构,#define MAXSIZE 1000 typedef struct El
7、emType data; Int cur; component, SLinklistMAXSIZE; Si.cur 指示第i+1个结点的位置。 静态链表的操作和动态链表相似。以整型游标代替动态 指针。,在静态链表中的查找算法,int LocateElem_SL(SLinkList L, ElemType) /在静态链表L中查找值为e的元素。 /若找到,则返回它在L中的位序,否则返回0。 i=S0.cur; while(i /LocateElem_SL,五 双向链表的存储结构(1),1. 类型定义 typedef struct DuLNode ElemType data; struct DuLN
8、ode *prior; struct DuLNode *next; DuLNode, *DuLinklist; DuLinklist L;,五 双向链表的存储结构(2),2. 双向链表的操作 双指针使得链表的双向查找更为方便、快捷。NextElem和PriorElem的执行时间为O(1)。 仅需涉及一个方向的指针的操作和线性链表的操作相同。 插入和删除需同时修改两个方向的指针。,六、带头结点的线性链表类型(1),1. 类型定义 typedef struc LNode ElemType data; struct LNode *next *Link, *Position; typedef struc /链表类型
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2027年初中九年级英语Unit 1-4写作教学设计与实施策略研究
- 初中生物七年级教学设计:绿色植物光合作用与有机物制造专题复习
- 高一地理教学设计:地球圈层结构的整体性认知与默写小纸条实施策略研究
- 高中英语必修三Unit 6 Writing-撰写安全指南教学设计
- 初中心理健康八年级教学设计:我是最棒的 自信与我同行
- 高中三年级地理产业转移对区域发展的影响复习课教学设计
- 初中七年级美术《画自己》教学设计
- 小学六年级数学教学设计:集合问题核心逻辑与建模策略深度解析
- 初中英语八年级下册Unit 1 Spring is coming 速记与默写教学设计
- 小学二年级生命生态安全《看谁记得快又牢》(记忆有妙法)教学设计
- 2025年(完整版)三级安全教育真题及答案(2025年)
- 中国鼻炎诊疗指南(2026版)
- 2026年译林版九年级英语上册 Unit5 Music speaks单元测试卷(含答案)
- 2026年数据文员笔模拟题目及答案详解
- T/COSHA 48-2024医疗机构安全生产资料管理规范
- GB 48145-2026井工煤矿机电设备完好性要求
- IEC 61000-4-2-2025 中文版(静电放电抗扰度试验 2025 年 3 月发布)
- 2026年党员发展对象培训结业试题及答案
- 2026年邮储银行山西分行秋招无领导小组面试仿真题解析
- 入团考试时事试题及答案解析
- 高中英语北师大版必修第一册全册单词表(按单元编排)
评论
0/150
提交评论