第二章线性表讲义——数据结构.ppt

课堂练习 for(i=2;i=n;++i) { for(j=2;j=i-1;++j) { a[i，j]=1; } } for(i=3;i=n;++i) { for(j=2;j=i+1;++j) { a[i，j]=1; } } 3+4+…+n=(n+3)(n-2)/2= 线性表 何谓线性结构? 线性结构是一个数据元素的有序（次序）集合。 四个特征： 集合中必存在唯一的一个第一元素“ 集合中必存在唯一的一个最后元素“ 除最后元素之外，其它数据元素均有唯一的后继“ 除第一元素之外，其它数据元素均有唯一的前驱 提纲 线性表的定义 线性表类型的实现（顺序映象） 线性表类型的实现（链式映象） 例1、26个英文字母组成的字母表 （A，B，C、…、Z） 例2、一副扑克的点数 （2，3，4，…，J，Q，K，A） 线性表定义： 是具有相同数据类型的n(n=0)个数据元素的有限序列，通常记为： (a1，a2，… ai-1，ai，ai+1，…an) 其中n为表长， n＝0 时称为空表。 线性表的类型定义 抽象数据类型线性表的定义 ADT List { 数据对象： D＝{ai | ai ∈ ElemSet, i=1,2,...,n, n≥0 } 数据关系： R1＝{ ai－1 , ai | ai ∈D, i=2,...,n }? 序偶，即有序对，可以看作是具有两个元素的集合。但它与一般集合不同的是序偶具有确定的次序。 抽象数据类型线性表的定义 基本操作： 结构初始化 InitList(*L) 操作结果：构造一个空的线性表 L 销毁结构 DestroyList(*L) 初始条件：线性表 L 已存在 操作结果：销毁线性表 L 参数传递 值传递 指针传递 引用传递 Swap(int a, int b){ int temp; temp =a; a=b; b=temp; } Main(){ int x,y; Swap(x,y); } Swap(int *a, int *b){ int temp; temp =*a; *a=*b; *b=temp; } Main(){ int x,y; Swap(x,y); } Swap(int *a, int *b){ int *temp; temp =a; a=b; b=temp; } Main(){ int x,y; Swap(x,y); } Swap(int a, int b){ int temp; temp =a; a=b; b=temp; } Main(){ int x,y; Swap(x,y); } Swap(const int a, const int b){ int temp; temp =a; a=b; b=temp; } Main(){ int x,y; Swap(x,y); } 抽象数据类型线性表的定义 引用型操作（6个） ListEmpty( L ) 初始条件：线性表L已存在 操作结果：若 L 为空表，则返回 TRUE，否则返回 FALSE ListLength( L ) 初始条件：线性表 L 已存在 操作结果：返回 L 中元素个数 抽象数据类型线性表的定义 引用型操作（续） 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 无定义 抽象数据类型线性表的定义 引用型操作（续） GetElem( L, i, *e )　　　 初始条件：线性表 L 已存在1≤i≤LengthList(L)。 操作结果：用 e 返回 L 中第 i 个元素的值。 LocateElem( L, e) 初始条件：线性表 L 已存在。 操作结果：返回 L 中与 e 相等的元素的序号。若这样的元素不存在，则返回值为0。 抽象数据类型线性表的定义 加工型操作 ClearList( *L ) 初始条件：线性表 L 已存在。 操作结果：将 L 重置为空表。 抽象数据类型线性表的定义 加工型操作 ListInsert( *L, i, e ) 初始条件：线性表 L 已存在，1≤i≤LengthList(L)+1。 操作结果：在 L