第二章线性表 令线性表 冷顺序表 令链表 冷顺序表与链表的比较
第二章 线性表 ❖ 线性表 ❖ 顺序表 ❖ 链表 ❖ 顺序表与链表的比较
2.1线性表的概念及运算 线性表的逻辑结构 线性表的抽象数据类型定义
2.1 线性表的概念及运算 • 线性表的逻辑结构 • 线性表的抽象数据类型定义
2.1.1线性衰的逻辑结构 定义:n(≥0)个数据元素的有限序列,记作 ●●● ai-1, ais ai+1g..,an 其中;是表中数据元素,n是表长度。 特点: 同一线性表中元素具有相同特性。 相邻数据元素之间存在序偶关系。 除第一个元素外,其他每一个元素有一个且仅 有一个直接前驱。 除最后一个元素外,其他每一个元素有 个且仅有一个直接后继
2.1.1 线性表的逻辑结构 定义： n（0）个数据元素的有限序列，记作 （a1 , …ai-1 , ai , ai+1 ,…, an） 其中,ai 是表中数据元素，n 是表长度。 特点: ◼ 同一线性表中元素具有相同特性。 ◼ 相邻数据元素之间存在序偶关系。 ◼ 除第一个元素外，其他每一个元素有一个且仅 有一个直接前驱。 ◼ 除最后一个元素外，其他每一个元素有 一个且仅有一个直接后继
2.1.2线性表的抽隶数据类烈定义 ADT LinearList( 数据元素:D={a|a∈Do,i=1,2,,n,n≥0,D为某一数据对象} 关系:S={a1a11>|a,a11∈Do,i=-1,2,…,n1} 基本操作: (1 InitList (l) (2) Destroy List(L) (3)ClearList(L (4 Empty List (L) (5) ListLength(L) (6) Locate(L, e) (7) GetData( (8) InsList(, i, e) (9) DelList(L, i, &e) 3 ADT LinearList
2.1.2 线性表的抽象数据类型定义 ADT LinearList{ 数据元素：D={ai | ai∈D0 , i=1, 2, …，n, n≥0 ， D0为某一数据对象} 关系：Ｓ＝{ | ai , ai+1∈D0，i=1, 2, …, n-1} 基本操作： （1） InitList（L （2） DestroyList(L) （3） ClearList(L) （4） EmptyList（L （5） ListLength（L （6） Locate(L, e) （7） GetData(L, i) （8） InsList(L, i, e) （9） DelList(L, i, &e) } ADT LinearList
操作 操作前提 操作结果 InitList (L) L为未初始化线性表 将L初始化为空表 Destroylist()|线性表L已存在 将L销毁 ClearList(L 线性表L已存在 将表L置为空表 Emptylist(L)|线性表L已存在 如果L为空表则返回真,否则返 回假 Listlength(L)|线性表L已存在 如果L为空表则返回0,否则返 回表中的元素个数 如果L中存在元素e,则将“当前指 Locate( l e 表L已存在,e为合法元素值针”指向元素e所在位置并返回真, 否则返回假 表存在,且i值合法,即返回线性表L中第i个元素的值 GetData ( ly 1≤i≤ Listlength(L) Insist(,i,e)/表已存在,e为合法元素值在中第i个位置插入新的数据元 且1≤i≤ Listlength(L)+1素e,L的长度加1 Delist(,,e)表L已存在且非空, 删除L的第i个数据元素,并用e 1≤i≤ ListLength(L) 返回其值,L的长度减1
操作 操作前提 操作结果 InitList（L L为未初始化线性表 将L初始化为空表 DestroyList(L) 线性表L已存在 将L销毁 ClearList(L) 线性表L已存在 将表L置为空表 EmptyList（L） 线性表L已存在 如果L为空表则返回真， 否则返 回假 ListLength（L） 线性表L已存在 如果L为空表则返回0， 否则返 回表中的元素个数 Locate(L, e) 表L已存在， e为合法元素值 如果L中存在元素e， 则将“当前指 针”指向元素e所在位置并返回真， 否则返回假 GetData(L, i) 表L存在， 且i值合法，即 1≤i≤ListLength（L） 返回线性表L中第i个元素的值 InsList(L, i, e) 表L已存在，e为合法元素值 且1≤i≤ListLength(L)+1 在L中第i个位置插入新的数据元 素e，L的长度加1 DelList(L, i, &e) 表L已存在且非空， 1≤i≤ListLength(L) 删除L的第i个数据元素， 并用e 返回其值， L的长度减1
2.2线性表的顺序存储 线性表的顺序存储结构 线性表顺序存储结构上的基本运算
2.2 线性表的顺序存储 • 线性表的顺序存储结构 • 线性表顺序存储结构上的基本运算
2.2.1线性表的顺序存储结构 定义:用一组地址连续的存储单元依次存储 线性表中的各个元素。 顺序表 存储结构:数组。 特点:线性表的顺序存储方式。 存取方式:顺序存取 012345 458990674078 内存中连续分布相同大小 的存储单元,依靠存储位 顺序存储结构示意图 置的物理相邻来体现线性 表元素的逻辑关系
2.2.1 线性表的顺序存储结构 定义：用一组地址连续的存储单元依次存储 线性表中的各个元素。 存储结构：数组。 特点：线性表的顺序存储方式。 存取方式：顺序存取 45 89 90 67 40 78 0 1 2 3 4 5 顺序存储结构示意图 内存中连续分布相同大小 的存储单元，依靠存储位 置的物理相邻来体现线性 表元素的逻辑关系 顺序表
顺序表的存储方式: LOC(a1)=LOC(a1)+1为每个元素所占 存储空间大小 LOC(a =loC(a,+(i-1)*L 2 ●●● ●。● ●●● ●。●● a, a aa+ a+(i-1) a+(m-1)“ille
顺序表的存储方式： LOC(a i+1) = LOC( a i ) + l LOC(a i ) = LOC(a1 ) + (i-1) * l a1 a2 … a i … … … an 1 2 … i … … … n a a+l … a+(i-1)*l … … … a+(n-1)*l idle l 为每个元素所占 存储空间大小
顺序表( Seqlist)的类型定义 # define maXsize100/最大允许长度 typedef int Elem Type typedef struct t Elem Type elem [ MAXSIZE;存储空间 int last;∥/记录线性表中最后一个元素在数组 /elem中的位置(下标值),空表置为1 ISeqlist
顺序表（SeqList）的类型定义 #define MAXSIZE 100 //最大允许长度 typedef int ElemType; typedef struct { ElemType elem[MAXSIZE]; //存储空间 int last; //记录线性表中最后一个元素在数组 //elem[]中的位置（下标值），空表置为-1 }SeqList;
2.22线性衰顺序存储结构上的基本运算 初始化 查找 插入 删除 求长度
2.2.2 线性表顺序存储结构上的基本运算 • 初始化 • 查找 • 插入 • 删除 • 求长度