线性表的逻辑结构 ◆若线性表中的结点是按值或按关键字值)由小到 大或由大到小)排列的，称线性表是有序的。 ◆线性表是一种相当灵活的数据结构，其长度可根 据需要增长或缩短。 ◆对线性表的数据元素不仅可以访问，还可以进行 插入和删除等操作
线性表的逻辑结构 ◆若线性表中的结点是按值(或按关键字值)由小到 大(或由大到小)排列的，称线性表是有序的。 ◆线性表是一种相当灵活的数据结构，其长度可根 据需要增长或缩短。 ◆ 对线性表的数据元素不仅可以访问，还可以进行 插入和删除等操作
线性表的抽象数据类型定义（1) ADT List 数据对象：D={a|a:∈ElemSet,=1,2,,n,n≥0} 数据关系：R={a1,a>|a1,a:∈D,i=2,3,,n} 基本操作： InitList(&L) 操作结果：构造一个空的线性表L; ListLength(L) 初始条件：线性表L已存在； 操作结果：返回L中数据元素个数；
线性表的抽象数据类型定义（1） ADT List{ 数据对象：D = { ai | ai∈ElemSet, i=1,2,…,n, n≧0 } 数据关系：R = {<ai-1 , ai> | ai-1 , ai∈D, i=2,3,…,n } 基本操作： InitList( &L ) 操作结果：构造一个空的线性表L； ListLength( L ) 初始条件：线性表L已存在； 操作结果：返回L中数据元素个数；
线性表的抽象数据类型定义(2) GetElem(L,i,&e) 初始条件：线性表L已存在，I≤i≤ListLength(L); 操作结果：用e返回L中第个数据元素的值； ListInsert (L,i,&e) 初始条件：线性表L已存在，1≤i≤ListLength(); 操作结果：在线性表L中的第个位置插入元素e; }ADT List
线性表的抽象数据类型定义（2） … GetElem( L, i, &e ) 初始条件：线性表L已存在，1≦i≦ListLength(L)； 操作结果：用e返回L中第i个数据元素的值； ListInsert ( L, i, &e ) 初始条件：线性表L已存在，1≦i≦ListLength(L) ； 操作结果：在线性表L中的第i个位置插入元素e； … } ADT List
线性表的基本操作(1) (1)初始化线性表InitList(&L):构造一个空的线性表L。 (2)销毁线性表DestroyList(&L):释放线性表L占用的内 存空间。 ●(3)清空线性表C1 earList(&L):将线性表重置为空表。 。(4)判线性表是否为空表ListEmpty(L):若L为空表，则返 回真，否则返回假。 ●(5)求线性表的长度ListLength(L):返回L中元素个数
线性表的基本操作（1） ⚫ (1)初始化线性表InitList(&L):构造一个空的线性表L。 ⚫ (2)销毁线性表DestroyList(&L):释放线性表L占用的内 存空间。 ⚫ (3)清空线性表ClearList(&L):将线性表重置为空表。 ⚫ (4)判线性表是否为空表ListEmpty(L):若L为空表,则返 回真,否则返回假。 ⚫ (5)求线性表的长度ListLength(L):返回L中元素个数
线性表的基本操作(2) (6)求线性表L中指定位置的某个数据元素GetElem(亿，i,&e): 用e返回L中第i(1≤i≤ListLength(L))个元素的值。 (7)定位查找LocateElem(L,e):返回L中第1个值域与e相等 的位序。若这样的元素不存在，则返回值为0。 (8)插入数据元素ListInsert(&L,i,e):在L的第i (1≤i≤ListLength(L)+1)个元素之前插入新的元素e,L的 长度增1。 (9)删除数据元素ListDelete(&L,i,&e):删除L的第i (I≤i≤ListLength(L))个元素，并用e返回其值，L的长度减 1
线性表的基本操作（2） ⚫ (6)求线性表L中指定位置的某个数据元素GetElem(L,i,&e): 用e返回L中第 i(1≤i≤ListLength(L))个元素的值。 ⚫ (7)定位查找LocateElem(L,e):返回L中第1个值域与e相等 的位序。若这样的元素不存在,则返回值为0。 ⚫ (8)插入数据元素ListInsert(&L,i,e):在L的第i (1≤i≤ListLength(L)+1) 个元素之前插入新的元素e,L的 长度增1。 ⚫ (9)删除数据元素ListDelete(&L,i,&e):删除L的第i (1≤i≤ListLength(L))个元素,并用e返回其值,L的长度减 1