数据结构 线性表 第二章 线性表 主讲：张昱 重点：顺序表和链表上各种基本算 yuzhang@ustc.edu 法的实现及相关的时间性能分析 0551-3603804 难点：线性表应用的算法设计 13 273 第二章线性表 2.1线性表的类型定义 21线性表的类型定义 ·定义 2.2线性表的顺序表示和实现 n(>0)个戴摄元素的有限序列，记作(a,….n4,a) 2.3线性表的链式表示和实现 其中，4是表中数据元意，n是表长度(a-0时称为空表) 2.3.1线性链表 2.3.2循还链表 ■逻辑特征 2.3.3能态链表 n>0时 2.3.4动杰链表与静杰链袁 ·有且仅有一个“第一个"”戴排元素 2.3.5双向能意2.3.6其他袁示 。有且仅有一个“最后一个”数据元素 2.4基王链凌的算法设计 ,除第一个数据元素外，其它元素有且仅有一个直接前驱 2.5一元多项式的表示及相加 。除最后一个数据元素外，其它元素有且仅有一个直接后继 33 73 2.1线性表的类型定义-ADT List LocateElem(L,e.compare)) ,ADT Listy定义 PriorElem(L,cur_e &pre_e) 作 作结果，构地一十空的线性表虹 Des Listinsert(&L,i,e ClearList(&L) 代整壁为空味 : 装数装RuE,香F处3死 L帐 初己存在 去装无快 作铺果做衣对L的每外数描元求调用面敏vs训，一且v修出)失败，则量作失败 )ADT List 图 67 画1/73 数据结构——线性表 主讲：张昱 yuzhang@ustc.edu 0551-3603804 2/73 重点：顺序表和链表上各种基本算 法的实现及相关的时间性能分析 难点：线性表应用的算法设计 第二章 线性表 3/73 第二章 线性表 2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.3.1 线性链表 2.3.2 循环链表 2.3.3 静态链表 2.3.4 动态链表与静态链表 2.3.5 双向链表 2.3.6 其他表示 2.4 基于链表的算法设计 2.5 一元多项式的表示及相加 4/73 2.1 线性表的类型定义 „ 定义 n(≥0)个数据元素的有限序列,记作(a1, …ai-1, ai , ai+1,…, an) 其中，ai是表中数据元素，n 是表长度(n=0时称为空表) „ 逻辑特征 n>0时 „ 有且仅有一个“第一个”数据元素 „ 有且仅有一个“最后一个”数据元素 „ 除第一个数据元素外，其它元素有且仅有一个直接前驱 „ 除最后一个数据元素外，其它元素有且仅有一个直接后继 5/73 2.1 线性表的类型定义-ADT List „ ADT List定义 ADT List{ 数据对象：D={ai | ai∈ElemSet, i=1,2,…,n, n≥0} 数据关系：R={R1},R1={<ai-1,ai>|ai-1,ai∈D, i=2,3,…,n } 基本操作： InitList(&L) 操作结果：构造一个空的线性表L DestroyList(&L) 初始条件：线性表L已存在 操作结果：销毁线性表L ClearList(&L) 初始条件：线性表L已存在 操作结果：将线性表L重置为空表 ListEmpty(L) 初始条件：线性表L已存在 操作结果：若L为空表，则返回TRUE，否则返回FALSE ListLength(L) 初始条件：线性表L已存在 操作结果：返回线性表L中数据元素的个数 6/73 2.1 线性表的类型定义 „ ADT List定义 GetElem(L, i ,&e) 初始条件：线性表L已存在，1≤i≤ListLength(L) 操作结果：用e返回L中第i个数据元素的值 LocateElem(L, e, compare( )) 初始条件：线性表L已存在，compare( )是数据元素的判定函数 操作结果：返回L中第1个与e满足关系compare( )的数据元素的位序。 若这样的元素不存在，则返回值为0 PriorElem(L, cur_e ,&pre_e) 初始条件：线性表L已存在 操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱， 否则操作失败，pre_e无定义 NextElem(L, cur_e ,&next_e) 初始条件：线性表L已存在 操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继， 否则操作失败，next_e无定义 ListInsert(&L, i, e) 初始条件：线性表L已存在，1≤i≤ListLength(L)+1 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1 ListDelete(&L, i, &e) 初始条件：线性表L已存在，1≤i≤ListLength(L) 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1 ListTraverse(L, visit( )) 初始条件：线性表L已存在 操作结果：依次对L的每个数据元素调用函数visit( )。一旦visit( )失败，则操作失败 }ADT List