资源描述：
《数据结构课件(线性表).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数据结构第二章线性表7/30/2021本章内容§2.1线性表的定义运算§2.2线性表类型的实现--顺序映象顺序表的几种基本运算§2.3线性表类型的实现--链式映象单链表操作的实现§2.4应用举例—一元多项式的表示及运算§2.5其他形式的链表静态链表循环链表双向链表§2.1线性表的定义运算1.线性表的定义：是由n(n>=0)个数据元素（结点）a1,a2,a3,……an组成的有限序列。其中：n为数据元素的个数，也称为表的长度。当n=0时，称为空表。非空的线性表(n>0)记作：（a1,a2,a3,……an）表中的元素又称“表目”。线性表中的数据元素在不同的情况下可以有不同的具体含义，它可以是一个数、
2、一个符号，也可是其它更复杂的信息。2.线性表（a1,a2,a3,……an）的逻辑特征：线性结构是一个数据元素的有序（次序）集1)．集合中必存在唯一的一个“第一元素”；2)．集合中必存在唯一的一个“最后元素”；3)．除最后元素在外ai(1≤i1)，均有唯一的前驱ai-1。5）ai是属于某个数据对象的元素，它可以是一个数字、一个字母或一个记录。3.线性表的特性（1）线性表中的所有数据元素的数据类型是一致的。（2）数据元素在线性表中的位置只取决于它的序号。（3）结点间的逻辑关系是线性的。线性表的类型定义抽象数据类型线性表的定义如下：A
3、DTList{数据对象：D＝{ai
4、ai∈ElemSet,i=1,2,...,n,n≥0}{称n为线性表的表长;称n=0时的线性表为空表。}数据关系：R1＝{
5、ai-1,ai∈D,i=2,...,n}{设线性表为(a1，a2,...，ai，...，an),称i为ai在线性表中的位序。}线性表的类型定义基本操作：{结构初始化}InitList(&L)操作结果：构造一个空的线性表L。{销毁结构}DestroyList(&L)初始条件：线性表L已存在。操作结果：销毁线性表L。{引用型操作}ListEmpty(L)初始条件：线性表L已存在。操作结果：若L为空表，则返回TRUE，否则F
6、ALSE。线性表的类型定义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
7、返回L中第i个元素的值。LocateElem(L,e,compare())初始条件：线性表L已存在，compare()是元素判定函数。操作结果：返回L中第1个与e满足关系compare()的元素的位序。若这样的元素不存在，则返回值为0。ListTraverse(L,visit())初始条件：线性表L已存在。操作结果：依次对L的每个元素调用函数visit()。一旦visit()失败，则操作失败。(遍历）线性表的类型定义{加工型操作}ClearList(&L)初始条件：线性表L已存在。操作结果：将L重置为空表。PutElem(&L,i,e)初始条件：线性表L已存在，1≤i≤LengthList(L
8、)操作结果：L中第i个元素赋值同e的值。ListInsert(&L,i,e)初始条件：线性表L已存在，1≤i≤LengthList(L)+1操作结果：在L的第i个元素之前插入新的元素e，L的长度增1。ListDelete(&L,i,&e)初始条件：线性表L已存在且非空，1≤i≤LengthList(L)操作结果：删除L的第i个元素，并用e返回其值，L的长度减1。 }ADTList§2.1线性表的定义运算（续）利用上述定义的线性表可以完成其它更复杂的操作例2-1假设有两个集合A和B分别用两个线性表LA和LB表示（即：线性表中的数据元素即为集合中的成员），现要求一个新的集合A＝A∪B。上述问题可演
9、绎为，要求对线性表作如下操作：扩大线性表LA，将存在于线性表LB中而不存在于线性表LA中的数据元素插入到线性表LA中去。1．从线性表LB中依次取得每个数据元素;GetElem(LB,i,&e)2．依值在线性表LA中进行查访;LocateElem(LA,e,equal())3．若不存在，则插入之。ListInsert(LA,n+1,e)§2.1线性表的定义运算（续）voidunion(List&La
