[工学]数据结构第04次课线性表B课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《[工学]数据结构第04次课线性表B课件.ppt》由用户(晟晟文业)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 工学 数据结构 04 线性 课件
- 资源描述:
-
1、数据结构计算机与信息学院 刘勇第1页每课一贴每课一贴:原来很简单原来很简单 有个小弟在脚踏车店当学徒,有人送来一部故障的脚踏车,有个小弟在脚踏车店当学徒,有人送来一部故障的脚踏车,小弟除了将车修好,还把车子整理的漂亮如新,其它学徒笑他多小弟除了将车修好,还把车子整理的漂亮如新,其它学徒笑他多此一举,后来雇主将脚踏车领回去的第二天,小弟被挖角到那位此一举,后来雇主将脚踏车领回去的第二天,小弟被挖角到那位雇主的公司上班。雇主的公司上班。原来出人头地很简单,吃点亏就可以了。原来出人头地很简单,吃点亏就可以了。有一个网球教练对学生说:如果一个网球掉进草堆里,应有一个网球教练对学生说:如果一个网球掉进草
2、堆里,应该如何找?该如何找?有人答:从草堆中心线开始找。有人答:从草堆中心线开始找。有人答:从草堆的最凹处开始找。有人答:从草堆的最凹处开始找。有人答:从草最长的地方开始找。有人答:从草最长的地方开始找。教练宣布正确答案:按部就班的从草地的一头,搜寻到草教练宣布正确答案:按部就班的从草地的一头,搜寻到草地的另一头。地的另一头。原来寻找成功的方法很简单,从一数到十不要跳过原来寻找成功的方法很简单,从一数到十不要跳过就可以了就可以了。数据结构计算机与信息学院 刘勇第2页上堂课要点回顾上堂课要点回顾1.1.线性结构线性结构(包括表、栈、队、数组)的定义和特点:包括表、栈、队、数组)的定义和特点:仅一
3、个首、尾结点,其余元素仅一个直接前驱和一仅一个首、尾结点,其余元素仅一个直接前驱和一个直接后继。个直接后继。2.2.线性表线性表逻辑结构逻辑结构:“一对一一对一”或或 1:11:1存储结构存储结构:顺序、链式:顺序、链式运运 算算:修改、插入、删除:修改、插入、删除3.3.顺序存储顺序存储特征特征:逻辑上相邻,物理上也相邻;逻辑上相邻,物理上也相邻;优点:优点:随机查找快随机查找快 O(1)O(1)缺点:缺点:插入、删除慢插入、删除慢 O(n)O(n)数据结构计算机与信息学院 刘勇第3页2.3 线性表的链式表示和实现线性表的链式表示和实现2.3.1 链表的表示链表的表示2.3.2 链链表的实现
4、表的实现2.3.3 链链表的运算效率分析表的运算效率分析链表小结链表小结数据结构计算机与信息学院 刘勇第4页2.3.1 链表的表示链表的表示1536元素元素2 21400元素元素1 11346元素元素3 3 元素元素4 41345h存储地址存储地址 存储内容存储内容 指针指针 13451345 元素元素1 1 14001400 13461346 元素元素4 4 .14001400 元素元素2 2 15361536 .15361536 元素元素3 3 13461346h数据结构计算机与信息学院 刘勇第5页链式存储结构特点:链式存储结构特点:其结点在存储器中的其结点在存储器中的位置是位置是随意随意
5、的,的,即逻辑上相邻的数据元素逻辑上相邻的数据元素在物理上在物理上不一定不一定相邻相邻。如何实现?通过来实现注意:注意:每个存储结点都包含两部分:每个存储结点都包含两部分:数据域数据域和和指针域指针域2.3.1 链表的表示链表的表示数据结构计算机与信息学院 刘勇第6页例例1 画出画出26 个英文字母表的链式存储结构个英文字母表的链式存储结构。该字母表在内存的链式存放示意图如下:该字母表在内存的链式存放示意图如下:解:该字母表的逻辑结构为:解:该字母表的逻辑结构为:(a,b,y,z)aheadb/z各结点由两个域组成:各结点由两个域组成:数据域:数据域:存储元素数值数据;存储元素数值数据;指针域
6、:指针域:存储直接后继或者直接前驱的存储位置。存储直接后继或者直接前驱的存储位置。指针数据指针数据指针或或样式:样式:数据结构计算机与信息学院 刘勇第7页与链式存储有关的术语:与链式存储有关的术语:1、结点:、结点:数据元素的存储映像。由数据域和指针域两部分组成;数据元素的存储映像。由数据域和指针域两部分组成;2、链表:、链表:n 个结点由个结点由指针链指针链组成一个链表。它是线性表的链式组成一个链表。它是线性表的链式存储映像存储映像,称为线性表的链式存储结构称为线性表的链式存储结构。3、单链表、双链表、多链表、循环链表、单链表、双链表、多链表、循环链表:结点只有一个指针域的链表,称为结点只有
7、一个指针域的链表,称为单链表单链表或或线性链表线性链表;有两个指针域的链表,称为有两个指针域的链表,称为双链表双链表;有多个指针域的链表,称为有多个指针域的链表,称为多链表多链表;首尾相接的链表称为首尾相接的链表称为循环链表循环链表。a1heada2anhead循环链表示意图:循环链表示意图:数据结构计算机与信息学院 刘勇第8页4、头指针、头结点和首元结点、头指针、头结点和首元结点 示意图如下:示意图如下:头指针头指针头结点头结点首元结点首元结点a1heada2infoan头指针头指针是指向链表中是指向链表中第一个结点第一个结点(或为头结点或为首元结点)(或为头结点或为首元结点)的指针;的指针
8、;头结点头结点是在链表的是在链表的首元结点之前附设的一个结点首元结点之前附设的一个结点;数据域内;数据域内只放空表标志和表长等信息只放空表标志和表长等信息;首元结点首元结点是指链表中存储线性表是指链表中存储线性表第一个数据元素第一个数据元素a a1 1的结点。的结点。数据结构计算机与信息学院 刘勇第9页一个线性表的逻辑结构为:一个线性表的逻辑结构为:(ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANGZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG),其存),其存储结构用单链表表示如下,储结构用单链表表示如下,请问其请问其头指针头指针的的值值是多少?是
9、多少?存储地址存储地址数据域数据域指针域指针域1LI437QIAN1313SUN119WANGNULL25WU3731ZHAO737ZHENG1943ZHOU25例例:答:答:头指针头指针是指向是指向链表中第一个结点链表中第一个结点的指针,因此关键的指针,因此关键是要寻找是要寻找第一个结第一个结点的地址点的地址。7ZHAOH31头指针的值是头指针的值是31数据结构计算机与信息学院 刘勇第10页上例链表的逻辑结构示意图有以下上例链表的逻辑结构示意图有以下两种形式两种形式:ZHAOQIANLISUNZHOUWUZHENG/WANGHZHAOQIANLISUNZHOUWUZHENG/WANGH区别:
10、区别:无头结点无头结点 有头结点有头结点数据结构计算机与信息学院 刘勇第11页讨论1.在链表中设置头结点有什么好处?头结点头结点即在链表的首元结点之前附设的一个结点,该结即在链表的首元结点之前附设的一个结点,该结点的数据域中点的数据域中不存储线性表的数据元素不存储线性表的数据元素,其作用是为了对链表,其作用是为了对链表进行操作时,可以对进行操作时,可以对空表、非空表空表、非空表的情况以及对的情况以及对首元结点首元结点进行进行统一处理,编程更方便。统一处理,编程更方便。答:答:讨论2.头结点的数据域内装的是什么?头结点的头结点的数据域数据域可以为空,也可存放线性表可以为空,也可存放线性表长度长度
11、等附加信息,但此结点不能计入链表长度值。等附加信息,但此结点不能计入链表长度值。答:答:头结点的数据域头结点的数据域H数据结构计算机与信息学院 刘勇第12页讨论4.链表的数据元素有两个域,不再是简单数据类型,编程时该如何表示?因每个结点至少有两个分量,所以要采用因每个结点至少有两个分量,所以要采用结构结构数数据类型。据类型。答:答:什么是结构类型?如何书写表达?什么是结构类型?如何书写表达?答:答:讨论3.如何表示空表空表?无头结点时,无头结点时,当头指针的值为空当头指针的值为空时表示空表;时表示空表;有头结点时,有头结点时,当头结点的指针域为空当头结点的指针域为空时表示空表。时表示空表。头指
12、针头指针头指针头指针头结点头结点无头结点无头结点有头结点有头结点数据结构计算机与信息学院 刘勇第13页 实现实现typedef struct node Elemtype data;struct node *link;LNode,*LinkList;linklist *h,*p;datalinkp结点(结点(*p)(*p)表示表示p所指向的结点所指向的结点(*p).datap-data表示表示p指向结点的数据域指向结点的数据域(*p).linkp-link表示表示p指向结点的指针域指向结点的指针域生成一个生成一个LNode型型新结点:新结点:p=(linklist)malloc(sizeof(L
13、Node);系统回收系统回收p结点:结点:free(p)3.线性链表的实现线性链表的实现 定义:结点中只含一个指针域的链表叫定义:结点中只含一个指针域的链表叫,也叫,也叫单链表单链表数据结构计算机与信息学院 刘勇第14页 用一组用一组任意任意的存储单元存储线性表的数据元素的存储单元存储线性表的数据元素 利用利用指针指针实现了用不相邻的存储单元存放逻辑上实现了用不相邻的存储单元存放逻辑上相邻的元素相邻的元素 每个数据元素每个数据元素ai,除存储,除存储本身信息本身信息外,还需存储其外,还需存储其直接后继直接后继的的地址地址 结点结点 数据域:元素本身信息数据域:元素本身信息 指针域:指示直接后继
14、的存储位置指针域:指示直接后继的存储位置数据域数据域 指针域指针域结点结点简单总结:线性表的链式表示的基本特征:简单总结:线性表的链式表示的基本特征:数据结构计算机与信息学院 刘勇第15页4.单链表的基本运算单链表的基本运算Ch2_3.txtWhile循环中语句频度为循环中语句频度为若找到结点若找到结点X,为结点,为结点X在表中的序号在表中的序号否则,为否则,为n nOnT 算法评价算法评价v 查找:查找单链表中是否存在结点查找:查找单链表中是否存在结点X,若有则返,若有则返回指向回指向X结点的指针;否则返回结点的指针;否则返回NULL查找、插入、删除、查找、插入、删除、创建、原地逆序创建、原
15、地逆序 算法描述算法描述类似算法:求长度等,类似算法:求长度等,举一反三举一反三P36查找查找数据结构计算机与信息学院 刘勇第16页pabxs 插入插入:在线性表在线性表两个数据元素两个数据元素a和和b间间插入插入x,已知已知p指向指向as-link=p-link;p-link=s;1OnT 算法描述算法描述 算法评价算法评价注意注意前插和前插和后插后插的区别的区别数据结构计算机与信息学院 刘勇第17页算法描述算法描述pabc 1OnT算法评价算法评价删除删除:单链表中删除:单链表中删除b,设,设p指向指向ap-link=p-link-link;数据结构计算机与信息学院 刘勇第18页 nOnT
16、 动态建立单链表算法动态建立单链表算法:设线性表设线性表n个元素已存个元素已存放在数组放在数组a中,建立一个单链表,中,建立一个单链表,h为头指针为头指针 算法描述算法描述 算法评价算法评价h头结点头结点an 0h头结点头结点an-10an a2.h头结点头结点an-10an ha1a2头结点头结点an .0h头结点头结点0注意注意前插和前插和后插后插的区别的区别 P35/36数据结构计算机与信息学院 刘勇第19页 nOnT单链表单链表原地逆序原地逆序算法算法:设线性表设线性表n个元素已存放个元素已存放在链表在链表a中,要求在不改变其元素位置的条件下中,要求在不改变其元素位置的条件下将链表逆序
17、排列,将链表逆序排列,h为头为头指针指针 算法描述算法描述 算法评价算法评价ha1a2头结点头结点an .0hanan-1头结点头结点a1 .0数据结构计算机与信息学院 刘勇第20页5.5.应用举例:两个链表的归并应用举例:两个链表的归并(教材(教材P41P41)算法要求:算法要求:已知:已知:线性表线性表 A、B,分别由,分别由单链表单链表 LA,LB 存储,存储,其中数据元素按值其中数据元素按值非递减有序非递减有序排列,排列,要求:要求:将将 A,B 归并归并为一个新的线性表为一个新的线性表C,C 的数据的数据元素仍按值元素仍按值非递减排列非递减排列 。设线性表。设线性表 C 由由单链表单
展开阅读全文