第二章线性表 令线性表 冷顺序表 令链表 冷顺序表与链表的比较
第二章 线性表 ❖ 线性表 ❖ 顺序表 ❖ 链表 ❖ 顺序表与链表的比较
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> | 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