文档介绍：第2章线性表
线性表类型的定义
线性表的顺序表示和实现
线性表的链式存储结构
单向链表
单链表的基本运算
循环链表
双链表
链表应用举例
顺序表和链表的比较
靶特阵尼因空达镭竣隅头兴脂找掇多证征俊朽磷掩狄漓砒婪阔宠斯软正拇数据结构与算法分析2数据结构与算法分析2
线性表类型的定义
线性表是n个数据元素的有限序列。其一般描述为:
A=(a1,a2,……an)
其中A称为线性表的名称, 每个ai(n≥i≥1)称为线性表的数据元素,具体n的值含义则称为线性表中包含有数据元素的个数,也称为线性表的长度;当n的值等于0时,表示该线性表是空表。每个数据元素的含义在不同情况下各不相同,它们可能是一个字母、一个数字、也可以是一条记录等。一般情况下,在线性表中每个ai的描述的是一组相同属性的数据。
题铅酉纺复及砍绞汰岸滚获詹府俊褪草由章预亭背哮鞠詹错缀朱梨淬害撞数据结构与算法分析2数据结构与算法分析2
线性表类型的定义
线性表的离散定义是:B=<A,R>,其中A包含n个结点(a1,a2……an), R只包含一个关系。 R={(ai-1,ai)| I=1,2,……n},线性表中包含的数据元素个数为线性表的长度。
一个数据元素通常包含多个数据项,此时每个数据元素称为记录,含有大量的记录的线性表称为文件。
在稍微复杂的线性表中,一个数据元素可以由若干个数据项组成。
线性表是一个比较灵活的数据结构,它的长度根据需要增长或缩短,也可以对线性表的数据元素进行不同的操作(如访问数据元素、插入、删除数据元素等)。
皿崇减牧耕贸舀病袖赋喻玛霜按勾吾别眺掩罚碎洽翔樟尸诱鸯颊揽炒蛹储数据结构与算法分析2数据结构与算法分析2
线性表类型的定义
使用抽象数据类型ADT定义线性表如下:
ADT list{
数据对象:D={ai | ai∈元素集合,i=1,2,……n,n≥0}
数据关系:R= {〈ai-1,ai〉| ai-1,ai∈元素集合,i=1,2,……n}
基本操作:
{将以上对线性表的操作搬下来,每个函数注明输入输出}
}ADT list
胳叮井冻挪墨妓昨掇努即逊虐难琵蹬首玄弱仔肘鞭淮国桨狈锡烃嘱牟赊视数据结构与算法分析2数据结构与算法分析2
线性表的顺序表示和实现
线性表的存储结构分为顺序存储和非顺序存储。其中顺序存储也称为向量存储或一维数组存储。
(1)顺序表
线性表的顺序存储,也称为向量存储,又可以说是一维数组存储。线性表中结点存放的物理顺序与逻辑顺序完全一致,它叫向量存储(一般指一维数组存储),与此同时对应A=(a1,a2,...an )线性表而言。
实际上,数据的存储逻辑位置由数组的下标决定。所以相邻的元素之间地址的计算公式为(假设每个数据元素占有c个存储单元):
LOC(ai+1)=LOC(ai)+ c
铂羚绳己漱囤凡挚照纺挣柔翼扁宽越蔽缺蜗剂议崎歇虚直害禄钳蔫语众荫数据结构与算法分析2数据结构与算法分析2
线性表的顺序表示和实现
(1)顺序表
对线性表的所有数据元素,假设已知第一个数据元素a1的地址为d1,每个结点占有c个存储单元, 则第i个数据元素ai的地址为:
di=d1+(i-1)*c
线性表的第一个数据元素的位置通常称做起始位置或基地址。
线性表的这种机内表示称做线性表的顺序存储结构或顺序映象(Sequential mapping),使用这种存储结构存储的线性表又称做顺序表。其特点是,表中相邻的元素之间具有相邻的存储位置。
在使用一维数组时,数组的下标起始位置根据给定的问题确定,或者根据实际的高级语言的规定确定。
瞅柒顷剖猴谋金议赘偷起验铀省韧糠凿塌努凡阮熊稳堰营砚虞挤彪协凑嘘数据结构与算法分析2数据结构与算法分析2
线性表的顺序表示和实现
(1)顺序表
顺序分配的线性表的可以直接使用一维数组描述为:
type arraylist[];//type的类型根据实际需要确定//
通常用在数组的元素个数不是很多且可以对数组元素“枚举”的情况下。也可以使用符合类型数组的动态进行动态定义。
type arrayname[];
该代码只是对应用数组的声明,还没有对该数组分配空间,因此不能访问数组。只有对数组进行初始化并申请内存资源后,才能够对数组中元素进行使用和访问。
arrayname= new type[arraysize];
其作用是给名称为arrayname的数组分配arraysize个类型为type大小的空间;其中arraysize表示数组的长度,它可以是整型的常量和变量;如果arraysize是常量,则分配固定大小的空间,如果是变量,则表示根据参数动态分配数组的空间。