数据结构与算法分析 第2章.ppt





《数据结构与算法分析 第2章.ppt》由会员分享,可在线阅读,更多相关《数据结构与算法分析 第2章.ppt(32页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、第第2 2章章 线性表线性表2.1 线性表类型的定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式存储结构 2.3.1 单向链表单向链表 2.3.2 单链表的基本运算单链表的基本运算 2.3.3 循环链表循环链表 2.3.4 双链表双链表 2.4 链表应用举例 2.5 顺序表和链表的比较 2.1 2.1 线性表类型的定义线性表类型的定义 线性表是n个数据元素的有限序列。其一般描述为:A=(a1,a2,an)其中A称为线性表的名称,每个ai(ni1)称为线性表的数据元素,具体n的值含义则称为线性表中包含有数据元素的个数,也称为线性表的长度;当n的值等于0时,表示该线性表是空表。每个数据元
2、素的含义在不同情况下各不相同,它们可能是一个字母、一个数字、也可以是一条记录等。一般情况下,在线性表中每个ai的描述的是一组相同属性的数据。2.1 2.1 线性表类型的定义线性表类型的定义线性表的离散定义是:B=,其中A包含n个结点(a1,a2an),R只包含一个关系。R=(ai-1,ai)|I=1,2,n,线性表中包含的数据元素个数为线性表的长度。一个数据元素通常包含多个数据项,此时每个数据元素称为记录,含有大量的记录的线性表称为文件。在稍微复杂的线性表中,一个数据元素可以由若干个数据项组成。线性表是一个比较灵活的数据结构,它的长度根据需要增长或缩短,也可以对线性表的数据元素进行不同的操作(
3、如访问数据元素、插入、删除数据元素等)。2.1 2.1 线性表类型的定义线性表类型的定义使用抽象数据类型ADT定义线性表如下:ADT list数据对象:D=ai|ai元素集合,i=1,2,n,n0数据关系:R=ai-1,ai|ai-1,ai元素集合,i=1,2,n基本操作:将以上对线性表的操作搬下来,每个函数注明输入输出ADT list 2.2 2.2 线性表的顺序表示和实现线性表的顺序表示和实现 线性表的存储结构分为顺序存储和非顺序存储。其中顺序存储也称为向量存储或一维数组存储。(1)顺序表 线性表的顺序存储,也称为向量存储,又可以说是一维数组存储。线性表中结点存放的物理顺序与逻辑顺序完全一
4、致,它叫向量存储(一般指一维数组存储),与此同时对应A=(a1,a2,an)线性表而言。实际上,数据的存储逻辑位置由数组的下标决定。所以相邻的元素之间地址的计算公式为(假设每个数据元素占有c个存储单元):LOC(ai+1)=LOC(ai)+c2.2 2.2 线性表的顺序表示和实现线性表的顺序表示和实现(1)顺序表 对线性表的所有数据元素,假设已知第一个数据元素a1的地址为d1,每个结点占有c个存储单元,则第i个数据元素ai的地址为:di=d1+(i-1)*c线性表的第一个数据元素的位置通常称做起始位置或基地址。线性表的这种机内表示称做线性表的顺序存储结构或顺序映象(Sequential map
5、ping),使用这种存储结构存储的线性表又称做顺序表。其特点是,表中相邻的元素之间具有相邻的存储位置。在使用一维数组时,数组的下标起始位置根据给定的问题确定,或者根据实际的高级语言的规定确定。2.2 2.2 线性表的顺序表示和实现线性表的顺序表示和实现(1)顺序表 顺序分配的线性表的可以直接使用一维数组描述为:type arraylist;/type的类型根据实际需要确定/通常用在数组的元素个数不是很多且可以对数组元素“枚举”的情况下。也可以使用符合类型数组的动态进行动态定义。type arrayname;该代码只是对应用数组的声明,还没有对该数组分配空间,因此不能访问数组。只有对数组进行初始
6、化并申请内存资源后,才能够对数组中元素进行使用和访问。arrayname=new typearraysize;其作用是给名称为arrayname的数组分配arraysize个类型为type大小的空间;其中arraysize表示数组的长度,它可以是整型的常量和变量;如果arraysize是常量,则分配固定大小的空间,如果是变量,则表示根据参数动态分配数组的空间。2.2 2.2 线性表的顺序表示和实现线性表的顺序表示和实现(2)顺序表基本运算的实现 线性表的顺序存储的结构,容易实现线性表的某些操作,如随机存取第i个数据元素等,但是在插入或删除数据元素时则是比较烦琐,所以顺序存储结构比较适合存取数据
7、元素。应该注意java的数组下标从0开始。下面考虑线性表顺序存储的插入、删除和排序的实现方法。顺序表的“求表长”和取第i个数据元素的时间复杂度均为O(1),因为可以直接求出线性表的长度,顺序存储下可可以实现随机存取,可以直接取得数据元素,而不需要移动元素。2.3 2.3 线性表的链式存储结构线性表的链式存储结构 线性表的顺序存储结构的特点是逻辑关系上相邻的两个元素在物理位置上也相邻,因此随机存取元素时比较简单,但是这个特点也使得在插入和删除元素时,造成大量的数据元素移动,同时如果使用静态分配存储单元,还要预先占用连续的存储空间,可能造成空间的浪费或空间的溢出。如果采用链式存储,就不要求逻辑上相
8、邻的数据元素在物理位置上也相邻,因此它没有顺序存储结构所具有的弱点,但同时也失去了可随机存取的优点。2.3 2.3 线性表的链式存储结构线性表的链式存储结构2.3.1 单向链表任意存储单元存储线性表的数据元素,对于链式存储线性表时,其特点形式如图所示:DATANEXT其中data 是数据域,存放数据元素的值;next是指针域,存放相邻的下一个结点的地址,单向链表是指结点中的指针域只有一个的沿着同一个方向表示的链式存储结构。因为结点是一个独立的对象,所以能够实现独立的结点类。2.3 2.3 线性表的链式存储结构线性表的链式存储结构2.3.1 单向链表对于链式分配线性表,整个链表的存取必须是从头指
9、针开始,头指针指示链表中第一个结点的存储位置。同时由于最后一个数据元素,没有直接后继,则线性链表中最后一个结点的指针为“空”(null)。在使用单链表结点时,必须完成三步:首先创建一个新结点;为该结点赋一个新值;新结点的next域赋值个当前元素;当前结点的前驱的next域要指向新插入的结点。2.3 2.3 线性表的链式存储结构线性表的链式存储结构2.3.2 单链表的基本运算单链表的基本运算 建立链表建立链表 因为单向链表的长度不固定,所以应采用动态建立单向链表的方法。动态地建立单向链表的常用方法有如下两种:尾插入法尾插入法该方法是将新结点插到当前链表的表尾上,为此必须增加一个尾指针tail的开
10、销,使其始终指向当前链表的尾结点;或者增加一个循环用来查找链表的末尾结点,然后将新结点插入到链表的末尾。此方法的优点是,在固定head头指针后,该指针就不能再变了。不会因为不断修改头指针,造成头指针的丢失。实际上动态建立链表的过程,就是不断插入新结点的过程;2.3 2.3 线性表的链式存储结构线性表的链式存储结构2.3.2 单链表的基本运算单链表的基本运算头插入法头插入法如果我们在链表的开始结点之前附加一个结点,并称它为头结点,那么会带来以下两个优点:第一,由于开始结点的位置被存放在头结点的指针域中,所以在链表的第一个位置上的操作就和在表的其他位置上操作一致,无须进行特殊处理;第二,无论链表是
11、否为空,其头指针是指向头结点的非空指针(空表中头结点的指针域空),因此空表和非空表的处理也就统一了。2.3 2.3 线性表的链式存储结构线性表的链式存储结构 查找运算查找运算按序号查找:按序号查找:在链表中,即使知道被访问结点的序号i,也不能像顺序表中那样直接按序号i访问结点,而只能从链表的头指针出发,顺着链域next逐个结点往下搜索,直至搜索到第i个结点为止(一般采用计数器的方式)。链表不是随机存取结构,只能顺序存取。查找之前首先要做到从头(head)开始,然后再逐个向后查找,查找过程中,每向后移动依次,计数器增加1,直到找到第i个结点(查找成功)或找完整个链表,没有第i个结点(查找失败)。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构与算法分析 第2章 数据结构 算法 分析

限制150内