数据结构2:线性表
1.线性表的定义及基本操作
1.1什么是线性表?
有若干个同类型元素组成的序列(0个或多个)。
定义:线性表
L = (a0, … , ai-1, ai , ai+1 , … , an-1)
其中:L为表名,ai (0≤i≤n-1)为数据元素;n为表长。n>0时,L为非空表;否则为空表,记为Φ 。
1.2线性表的逻辑结构和特征
形式化描述:线性表
L= (D, R)
D:数据元素集合,R:D上的关系集合,其中:
D={ai | ai∈datatype, i = 0, 1 , … , n-1, n≥0}
R={<ai, ai+1> | ai, ai+1∈D, 0≤i≤n-2}
关系符<ai, ai+1>:有序对,表示任意相邻的两个元素之间的一种先后次序关系
ai是ai+1的直接前驱,ai+1是ai的直接后继。
线性表的特征:对非空表, a0是表头,无前驱;an-1是表尾,无后继;其它的每个元素ai有且仅有一个直接前驱(ai-1)和一个直接后继(ai+1)。
1.3线性表的抽象数据类型表示
ADT List {
数据元素集:D={ai|ai∈datatype, i = 0, 1, 2, …… , n-1, n≥0}
数据关系集:R={<ai, ai+1>|ai, ai+1∈D, 0≤i≤n-2}
基本操作集:P
ListInit(&L)
操作结果:构造一个空的线性表L。
ListDestroy(&L)
初始条件:线性表L存在。
操作结果:撤销线性表L。
ListClear(&L)
初始条件:线性表L存在。
操作结果:将L置为一张空表。
ListLength(L)
初始条件:线性表L存在。
操作结果:返回L中元素个数(即表长n)。
ListEmpty(L)
初始条件:线性表L存在。
操作结果:L为空表时返回TRUE,否则返回FALSE。
GetElem(L, i)
初始条件:线性表L存在,且0≤i≤n1。
操作结果:返回L中第i个元素的值(或指针)。
LocateElem(L, e)
初始条件:线性表L存在,且e∈datatype。
操作结果:若e在L中,返回e的序号(或指针);否则返回e不在表中的信息(实际应用中如-1或NULL)。
PreElem(L, cur)
初始条件:线性表L存在,且cur∈datatype。
操作结果:若cur在L中且不是表头,返回cur的直接前驱,否则返回NULL。
SuccElem(L, cur)
初始条件:线性表L存在,且cur∈datatype。
操作结果:若cur在L中且不是表尾元素,返回cur的直接后继的值,否则返回NULL。
2.线性表的顺序存储结构
2.1顺序表
线性表L=(a0, a1, …, an-1)中的各元素依次存储于一片连续的存储空间
顺序存储结构的特点:
逻辑上相邻的元素 ai, ai+1,其存储位置也是相邻的。
对数据元素ai的存取为随机存取或按地址存取。
存储密度高。
存储密度D=(数据结构中元素所占存储空间)/(整个数据结构所占空间)。
不足:对表的插入和删除等操作的时间复杂度较差。
2.2顺序表的基本操作
置空表:ListClear (L), 令L->last = -1;
取ai: GetElem(L, i), 取L->data[i]之值;
求表长:ListLength(L), 取L->last之值加1即可。
3.线性表的链式存储结构
3.1指针变量的物理意义
计算机的内存空间是由连续编号的内存单元构成,每个内存单元具有唯一的地址(编号)。在以字节编址的计算机系统中,每个内存单元存放1个字节。
变量的2个要素:地址,值
地址由系统自动分配,所占空间的大小由类型决定
指针变量与其它变量一样,在定义之后,系统自动分配相应的内存空间以存放其值。
指针变量的值是指针,即地址。
3.2单链表
约定两种提法:
节点X:数据元素为X的节点。
P节点:指针P所指向的节点。
3.3单链表的基本操作
(1)创建
算法思路:依次读入表L=(a0, ..., an-1)中每一元素ai(设为整型),若ai≠结束符(-1),则将ai形成一新节点,链入表尾,最后返回链表的头指针。
设L=(2,4,8,-1),则建表过程如下:
设表长为n,显然此算法的时间复杂度为T(n)=O(n)。
从此算法可以看到,链表的结构是动态形成的,即算法运行前,表结构是不存在的,而通过算法的运行,得到一个如上图所示的单链表。
(2)查找
①按序号查找:GetElem(L, i)
算法思路:从链表的a0起,判断是否为第i个节点,若是则返回该节点的指针,否则查找下()一节点,依此类推。
②按值查找:LocateElem(L, e)
算法思路:从节点a0起,依次判断某节点是否等于e。若是,则返回该节点的地址,若不是,则查找下一节点a1,依此类推。若表中不存在e, 则返回NULL。
(3) ListInsert(L, i, e):将一给定值e插在元素ai之前
算法思路:调用算法GetElem(H, i-1),获取节点ai-1的指针p(ai 之前驱),然后申请一个q节点,存入e,并将其插入p节点之后。
指针变化如下:
(4)删除:ListDel(L, i)
算法思路:同插入法,先调用函数GetElem(H, i-1),找到节点ai的前驱,然后将节点ai删除之。
3.4单向循环链表
3.5双向链表
3.6双向循环链表
3.7静态链表
用数组模拟链表,以数组下标模拟指针
4.数组与链表方法比较
(1)若用数组实现线性表,则必须在编译前知道表的最大长度。
(2)对于数组,随机访问效率高。
(3)数组的存储密度高;
链表需在每个节点附加指针,即存在结构性开销;
但元素较少时,数组填不满,浪费空间。
一般来说,
当线性表元素个数未知或变化较大时,最好用链表;
若事先知道最大长度,可用数组;
若频繁插入/删除用链表较好