数据结构：第02章 线性表

1、2.1 线性线性表的定义运表的定义运算算2.2 线性线性表类型的实表类型的实现现-顺序映顺序映象象 顺序表的几顺序表的几种基本运算种基本运算 2.3 线性线性表类型的实表类型的实现现-链式映链式映象象单链表操作单链表操作的实现的实现 2.4 应用应用举例举例一元一元多项式的表多项式的表示及运算示及运算 2.5 其他其他形式的链表形式的链表静态链表静态链表 循环链表循环链表 双向链表双向链表1数据结构数据结构第二章第二章 线性表线性表20222022年年3 3月月2929日星期二日星期二2.1 线性线性表的定义运表的定义运算算2.2 线性线性表类型的实表类型的实现现-顺序映顺序映象象 顺序表的几

2、顺序表的几种基本运算种基本运算 2.3 线性线性表类型的实表类型的实现现-链式映链式映象象单链表操作单链表操作的实现的实现 2.4 应用应用举例举例一元一元多项式的表多项式的表示及运算示及运算 2.5 其他其他形式的链表形式的链表静态链表静态链表 循环链表循环链表 双向链表双向链表2本章内容本章内容2.1 2.1 线性表的定义运算线性表的定义运算2.2 2.2 线性表类型的实现线性表类型的实现-顺序映象顺序映象 顺序表的几种基本运算顺序表的几种基本运算 2.3 2.3 线性表类型的实现线性表类型的实现-链式映象链式映象 单链表操作的实现单链表操作的实现 2.4 2.4 应用举例应用举例一元多项

3、式的表示及运算一元多项式的表示及运算 2.5 2.5 其他形式的链表其他形式的链表静态链表静态链表 循环链表循环链表 双向链表双向链表2.1 线性线性表的定义运表的定义运算算2.2 线性线性表类型的实表类型的实现现-顺序映顺序映象象 顺序表的几顺序表的几种基本运算种基本运算 2.3 线性线性表类型的实表类型的实现现-链式映链式映象象单链表操作单链表操作的实现的实现 2.4 应用应用举例举例一元一元多项式的表多项式的表示及运算示及运算 2.5 其他其他形式的链表形式的链表静态链表静态链表 循环链表循环链表 双向链表双向链表32.1 2.1 线性表的定义运算线性表的定义运算 1.线性表的定义：线性

4、表的定义： 是由是由n(n=0)个数据元素（结点）个数据元素（结点）a1, a2, a3, an组成的有限序列。组成的有限序列。 其中：其中：n为数据元素的个数，也称为为数据元素的个数，也称为表的表的长度长度。 当当n=0 时，称为时，称为空表空表。 非空的线性表非空的线性表(n0) 记作：（记作：（ a1, a2, a3, an）表中的元素又称表中的元素又称“表目表目”。线性表中的数据元素在不同的情况下可以有不同线性表中的数据元素在不同的情况下可以有不同的具体含义，它可以是一个数、一个符号，也可是其的具体含义，它可以是一个数、一个符号，也可是其它更复杂的信息。它更复杂的信息。2.1 线性线性

5、表的定义运表的定义运算算2.2 线性线性表类型的实表类型的实现现-顺序映顺序映象象 顺序表的几顺序表的几种基本运算种基本运算 2.3 线性线性表类型的实表类型的实现现-链式映链式映象象单链表操作单链表操作的实现的实现 2.4 应用应用举例举例一元一元多项式的表多项式的表示及运算示及运算 2.5 其他其他形式的链表形式的链表静态链表静态链表 循环链表循环链表 双向链表双向链表42.2.线性表（线性表（a1,a2,a3, a1,a2,a3, anan）的）的逻辑特征：逻辑特征：线性结构是一个数据元素的线性结构是一个数据元素的有序（次序）集有序（次序）集 1)集合中必存在唯一的一个集合中必存在唯一的

6、一个“第一元素第一元素”；2)集合中必存在唯一的一个集合中必存在唯一的一个“最后元素最后元素”；3)除最后元素在外除最后元素在外ai(1i1)，均有，均有唯一的前驱唯一的前驱ai-1。5） ai是属于某个数据对象的元素，它可以是一个数字、是属于某个数据对象的元素，它可以是一个数字、一个字母或一个记录。一个字母或一个记录。3.线性表的线性表的特性特性 （1）线性表中的所有数据元素的数据类型是一致的。）线性表中的所有数据元素的数据类型是一致的。 （2）数据元素）数据元素 在线性表中的位置只取决于它的序号。在线性表中的位置只取决于它的序号。 （3）结点间的逻辑关系是线性的。）结点间的逻辑关系是线性的

7、。2.1 线性线性表的定义运表的定义运算算2.2 线性线性表类型的实表类型的实现现-顺序映顺序映象象 顺序表的几顺序表的几种基本运算种基本运算 2.3 线性线性表类型的实表类型的实现现-链式映链式映象象单链表操作单链表操作的实现的实现 2.4 应用应用举例举例一元一元多项式的表多项式的表示及运算示及运算 2.5 其他其他形式的链表形式的链表静态链表静态链表 循环链表循环链表 双向链表双向链表5线性表的类型定义线性表的类型定义抽象数据类型线性表的定义如下：抽象数据类型线性表的定义如下：ADT List 数据对象数据对象：D ai | ai ElemSet, i=1,2,.,n, n0 称称n为线

8、性表的为线性表的表长表长; 称称n=0时的线性表为时的线性表为空表空表。数据关系数据关系：R1 |ai-1 ,aiD, i=2,.,n 设线性表为设线性表为 (a1，a2,.，ai，.，an), 称称i为为ai在线在线性表中的性表中的位序位序。2.1 线性线性表的定义运表的定义运算算2.2 线性线性表类型的实表类型的实现现-顺序映顺序映象象 顺序表的几顺序表的几种基本运算种基本运算 2.3 线性线性表类型的实表类型的实现现-链式映链式映象象单链表操作单链表操作的实现的实现 2.4 应用应用举例举例一元一元多项式的表多项式的表示及运算示及运算 2.5 其他其他形式的链表形式的链表静态链表静态链表

9、 循环链表循环链表 双向链表双向链表6线性表的类型定义线性表的类型定义基本操作：基本操作：结构初始化结构初始化InitList( &L )操作结果：操作结果：构造一个空的线性表构造一个空的线性表L。销毁结构销毁结构DestroyList( &L )初始条件：初始条件：线性表线性表L已存在。已存在。操作结果：操作结果：销毁线性表销毁线性表L。引用型操作引用型操作ListEmpty( L )初始条件：初始条件：线性表线性表L已存在。已存在。操作结果：操作结果：若若L为空表，则返回为空表，则返回TRUE，否则，否则FALSE。2.1 线性线性表的定义运表的定义运算算2.2 线性线性表

10、类型的实表类型的实现现-顺序映顺序映象象 顺序表的几顺序表的几种基本运算种基本运算 2.3 线性线性表类型的实表类型的实现现-链式映链式映象象单链表操作单链表操作的实现的实现 2.4 应用应用举例举例一元一元多项式的表多项式的表示及运算示及运算 2.5 其他其他形式的链表形式的链表静态链表静态链表 循环链表循环链表 双向链表双向链表7线性表的类型定义线性表的类型定义ListLength( L )初始条件：初始条件：线性表线性表L已存在。已存在。操作结果：操作结果：返回返回L中元素个数。中元素个数。PriorElem( L, cur_e, &pre_e )初始条件：初始条件：线性表线性表

11、L已存在。已存在。操作结果：操作结果：若若cur_e是是L的元素，但不是第一个，则用的元素，但不是第一个，则用pre_e 返回它的前驱，否则操作失败，返回它的前驱，否则操作失败，pre_e无定义。无定义。NextElem( L, cur_e, &next_e )初始条件：初始条件：线性表线性表L已存在。已存在。操作结果：操作结果：若若cur_e是是L的元素，但不是最后一个，则用的元素，但不是最后一个，则用next_e 返回它的后继，否则操作失败，返回它的后继，否则操作失败，next_e无定义。无定义。2.1 线性线性表的定义运表的定义运算算2.2 线性线性表类型的实表类型的实现现-顺序

12、映顺序映象象 顺序表的几顺序表的几种基本运算种基本运算 2.3 线性线性表类型的实表类型的实现现-链式映链式映象象单链表操作单链表操作的实现的实现 2.4 应用应用举例举例一元一元多项式的表多项式的表示及运算示及运算 2.5 其他其他形式的链表形式的链表静态链表静态链表 循环链表循环链表 双向链表双向链表8线性表的类型定义线性表的类型定义GetElem( L, i, &e )初始条件：初始条件：线性表线性表L已存在，已存在， 1iLengthList(L)操作结果：操作结果：用用e 返回返回L中第中第i个元素的值。个元素的值。LocateElem( L, e, compare( ) )

13、初始条件：初始条件：线性表线性表L已存在，已存在，compare( )是元素判定函是元素判定函数。数。操作结果：操作结果：返回返回L中第中第1个与个与e满足关系满足关系compare( )的元的元素的位序。若这样的元素不存在，则返回值为素的位序。若这样的元素不存在，则返回值为0。ListTraverse(L, visit( )初始条件：初始条件：线性表线性表L已存在。已存在。操作结果：操作结果：依次对依次对L的每个元素调用函数的每个元素调用函数visit( )。一旦。一旦visit( )失败，则操作失败。失败，则操作失败。(遍历遍历）2.1 线性线性表的定义运表的定义运算算2.2 线性线性表类

14、型的实表类型的实现现-顺序映顺序映象象 顺序表的几顺序表的几种基本运算种基本运算 2.3 线性线性表类型的实表类型的实现现-链式映链式映象象单链表操作单链表操作的实现的实现 2.4 应用应用举例举例一元一元多项式的表多项式的表示及运算示及运算 2.5 其他其他形式的链表形式的链表静态链表静态链表 循环链表循环链表 双向链表双向链表9线性表的类型定义线性表的类型定义加工型操作加工型操作ClearList( &L )初始条件：初始条件：线性表线性表L已存在。已存在。操作结果：操作结果：将将L重置为空表。重置为空表。PutElem(&L, i, e )初始条件：初始条件：线性表线性表

15、L已存在，已存在，1iLengthList(L)操作结果：操作结果：L中第中第i个元素赋值同个元素赋值同e的值。的值。ListInsert( &L, i, e )初始条件：初始条件：线性表线性表L已存在，已存在，1iLengthList(L)+1操作结果：操作结果：在在L的第的第i个元素之前插入新的元素个元素之前插入新的元素e，L的长的长度增度增1。ListDelete(&L, i, &e)初始条件：初始条件：线性表线性表L已存在且非空，已存在且非空，1iLengthList(L)操作结果：操作结果：删除删除L的第的第i个元素，并用个元素，并用e返回其值，返回其值，L的

16、长的长度减度减1。 ADT List2.1 线性线性表的定义运表的定义运算算2.2 线性线性表类型的实表类型的实现现-顺序映顺序映象象 顺序表的几顺序表的几种基本运算种基本运算 2.3 线性线性表类型的实表类型的实现现-链式映链式映象象单链表操作单链表操作的实现的实现 2.4 应用应用举例举例一元一元多项式的表多项式的表示及运算示及运算 2.5 其他其他形式的链表形式的链表静态链表静态链表 循环链表循环链表 双向链表双向链表102.1 2.1 线性表的定义运算（续）线性表的定义运算（续）利用上述定义的线性表可以完成其它更复杂的操作利用上述定义的线性表可以完成其它更复杂的操作例例2-1 假设有两

17、个集合假设有两个集合A和和B分别用两个线性表分别用两个线性表LA和和LB表示（即：线性表中的数据元素即为集合中的成员），表示（即：线性表中的数据元素即为集合中的成员），现要求一个新的集合现要求一个新的集合AAB。上述问题可演绎为，要求对线性表作如下操作：扩大上述问题可演绎为，要求对线性表作如下操作：扩大线性表线性表LA，将存在于线性表，将存在于线性表LB中而不存在于线性表中而不存在于线性表LA中中的数据元素插入到线性表的数据元素插入到线性表LA中去。中去。1从线性表从线性表LB中依次取得每个数据元素中依次取得每个数据元素; GetElem(LB, i ,&e )2依值在线性表依值在线性

18、表LA中进行查访中进行查访; LocateElem(LA, e, equal( )3若不存在，则插入之。若不存在，则插入之。 ListInsert(LA, n+1, e)2.1 线性线性表的定义运表的定义运算算2.2 线性线性表类型的实表类型的实现现-顺序映顺序映象象 顺序表的几顺序表的几种基本运算种基本运算 2.3 线性线性表类型的实表类型的实现现-链式映链式映象象单链表操作单链表操作的实现的实现 2.4 应用应用举例举例一元一元多项式的表多项式的表示及运算示及运算 2.5 其他其他形式的链表形式的链表静态链表静态链表 循环链表循环链表 双向链表双向链表112.1 2.1 线性表的定义运算（

19、续）线性表的定义运算（续）void union(List &La, List Lb) / 将所有在线性表将所有在线性表Lb中但不在中但不在La中的数据元素插入到中的数据元素插入到La中中La_len = ListLength(La);Lb_len =ListLength(Lb); / 求线性表的长度求线性表的长度for (i = 1; i = Lb_len; i+) GetElem(Lb, i, e); / 取取Lb中第中第i个数据元素赋给个数据元素赋给eif(!LocateElem(La, e, equal( )ListInsert(La, +La_len, e);/ La中不存在和

20、中不存在和 e 相同的数据元素，则插入之相同的数据元素，则插入之 / union2.1 线性线性表的定义运表的定义运算算2.2 线性线性表类型的实表类型的实现现-顺序映顺序映象象 顺序表的几顺序表的几种基本运算种基本运算 2.3 线性线性表类型的实表类型的实现现-链式映链式映象象单链表操作单链表操作的实现的实现 2.4 应用应用举例举例一元一元多项式的表多项式的表示及运算示及运算 2.5 其他其他形式的链表形式的链表静态链表静态链表 循环链表循环链表 双向链表双向链表122.2 2.2 线性表类型的实现线性表类型的实现-顺序映象顺序映象表示和实现表示和实现用一组地址连续的存储单元依次存放线性表

21、中的数据元素。用一组地址连续的存储单元依次存放线性表中的数据元素。逻辑地址逻辑地址数据元素数据元素存储地址存储地址 数据元素数据元素0 0k k0 0Loc(kLoc(k0 0) )k k0 01 1k k1 1Loc(kLoc(k0 0)+c)+ck k1 1i ik ki iLoc(kLoc(k0 0)+i)+i* *c ck ki in-1n-1k kn-1n-1Loc(kLoc(k0 0)+(n-1)+(n-1)* *c ck kn-1n-12.1 线性线性表的定义运表的定义运算算2.2 线性线性表类型的实表类型的实现现-顺序映顺序映象象 顺序表的几顺序表的几种基本运算种基本运算 2.

22、3 线性线性表类型的实表类型的实现现-链式映链式映象象单链表操作单链表操作的实现的实现 2.4 应用应用举例举例一元一元多项式的表多项式的表示及运算示及运算 2.5 其他其他形式的链表形式的链表静态链表静态链表 循环链表循环链表 双向链表双向链表13表示和实现表示和实现若一个数据元素仅占一个存储单元，则其存储方式见下图若一个数据元素仅占一个存储单元，则其存储方式见下图: 从图中可见，第从图中可见，第i个数据元素的地址为：个数据元素的地址为： LOC（a i）=loc(ai-1)+1= loc(a 1)+(i-1) 存储地址 内容元素序号12。I 。 n a 1 A 2 。 。A i 。 。LL

23、 + 1。L+（i - 1）。L+（n - 1） a n2.1 线性线性表的定义运表的定义运算算2.2 线性线性表类型的实表类型的实现现-顺序映顺序映象象 顺序表的几顺序表的几种基本运算种基本运算 2.3 线性线性表类型的实表类型的实现现-链式映链式映象象单链表操作单链表操作的实现的实现 2.4 应用应用举例举例一元一元多项式的表多项式的表示及运算示及运算 2.5 其他其他形式的链表形式的链表静态链表静态链表 循环链表循环链表 双向链表双向链表14表示和实现（续）表示和实现（续） 若每个数据元素占用若每个数据元素占用m个存储单元，则第个存储单元，则第m个数据元素个数据元素的存储位置为：的存储位

24、置为： LOC（a i）=loc(a i-1)+m LOC（a i）=loc(a 1)+(i-1)*m loc(a 1)称为称为基地址基地址（第一个数据元素的存储位置）。（第一个数据元素的存储位置）。 显然，数据元素在顺序表中位置取决于数据元素在线显然，数据元素在顺序表中位置取决于数据元素在线性表中的位置。性表中的位置。 顺序表的特点顺序表的特点 是：是：逻辑位置相邻，其物理位置也相邻。逻辑位置相邻，其物理位置也相邻。只要确定了首地址，线性表中任意数据元素都可以只要确定了首地址，线性表中任意数据元素都可以随随机存取机存取（访问）。（访问）。2.1 线性线性表的定义运表的定义运算算2.2 线性线

25、性表类型的实表类型的实现现-顺序映顺序映象象 顺序表的几顺序表的几种基本运算种基本运算 2.3 线性线性表类型的实表类型的实现现-链式映链式映象象单链表操作单链表操作的实现的实现 2.4 应用应用举例举例一元一元多项式的表多项式的表示及运算示及运算 2.5 其他其他形式的链表形式的链表静态链表静态链表 循环链表循环链表 双向链表双向链表15顺序映像的顺序映像的C C语言描述语言描述在在C语言中可以用以下方式定义一个顺序表：语言中可以用以下方式定义一个顺序表：struct SeqListDataType elementMAXNUM; int n;/* n MAXNUM */ ;2.1 线性线性表

26、的定义运表的定义运算算2.2 线性线性表类型的实表类型的实现现-顺序映顺序映象象 顺序表的几顺序表的几种基本运算种基本运算 2.3 线性线性表类型的实表类型的实现现-链式映链式映象象单链表操作单链表操作的实现的实现 2.4 应用应用举例举例一元一元多项式的表多项式的表示及运算示及运算 2.5 其他其他形式的链表形式的链表静态链表静态链表 循环链表循环链表 双向链表双向链表16顺序映像的顺序映像的C C语言描述语言描述在实际应用中，为了使用方便，通常定义一个在实际应用中，为了使用方便，通常定义一个struct SeqList类型的指针类型和别名：类型的指针类型和别名： #define LIST_

27、INIT_SIZE 80 / 线性表存储空间的初线性表存储空间的初始分配量始分配量#define LISTINCREMENT 10 / 线性表存储空间的分线性表存储空间的分配增量配增量typedef struct ElemType *elem; / 存储空间基址（表空间存储空间基址（表空间数组）数组） int length; / 当前长度当前长度 int listsize; / 当前分配的存储容量当前分配的存储容量(以以sizeof(ElemType)为单位为单位) SqList; / 俗称俗称 顺序表顺序表比较这两种定义顺序表的方法，后者概念较为清晰，比较这两种定义顺序表的方法，后者概念较为

28、清晰，符合数据抽象的原则，今后我们的定义一般采用后者。符合数据抽象的原则，今后我们的定义一般采用后者。2.1 线性线性表的定义运表的定义运算算2.2 线性线性表类型的实表类型的实现现-顺序映顺序映象象 顺序表的几顺序表的几种基本运算种基本运算 2.3 线性线性表类型的实表类型的实现现-链式映链式映象象单链表操作单链表操作的实现的实现 2.4 应用应用举例举例一元一元多项式的表多项式的表示及运算示及运算 2.5 其他其他形式的链表形式的链表静态链表静态链表 循环链表循环链表 双向链表双向链表17顺序表的几种基本运算顺序表的几种基本运算线性表的线性表的初始化初始化在顺序映像中的实现在顺序映像中的实

29、现Status InitList_Sq(SqList &L) / 构造一个空的线性表构造一个空的线性表L。L.elem = (ElemType*)malloc (LIST_INIT_SIZE * sizeof(ElemType); if (!L.elem) exit(OVERFLOW); / 存储分配失败存储分配失败L.length = 0; / 长度为长度为0L.listsize = LIST_INIT_SIZE ; / 初始存储容量初始存储容量return OK; / InitList_Sq2.1 线性线性表的定义运表的定义运算算2.2 线性线性表类型的实表类型的实现现-顺序映顺序

30、映象象 顺序表的几顺序表的几种基本运算种基本运算 2.3 线性线性表类型的实表类型的实现现-链式映链式映象象单链表操作单链表操作的实现的实现 2.4 应用应用举例举例一元一元多项式的表多项式的表示及运算示及运算 2.5 其他其他形式的链表形式的链表静态链表静态链表 循环链表循环链表 双向链表双向链表18顺序表的几种基本运算（续）顺序表的几种基本运算（续）线性表操作线性表操作LocateElem(LLocateElem(L, e, compare( ), e, compare( )的实现：的实现：int LocateElem_Sq(SqList L, ElemType e, Status (*c

31、ompare)(ElemType, ElemType) / 在顺序线性表在顺序线性表L中查中查找第找第1个值与个值与e满足满足compare( )的元素的位序。的元素的位序。 若找到，则若找到，则返回其在返回其在L中的位序，否则返回中的位序，否则返回0。i = 1; / i的初值为第的初值为第1元素的位序元素的位序p = L.elem; / p的初值为第的初值为第1元素的存储位置元素的存储位置while (i = L.length & !(*compare)(*p+, e) +i;if (i = L.length) return i;else return 0; / LocateEle

32、m_Sq此算法的时间复杂度为此算法的时间复杂度为: O( ListLength(L) )2.1 线性线性表的定义运表的定义运算算2.2 线性线性表类型的实表类型的实现现-顺序映顺序映象象 顺序表的几顺序表的几种基本运算种基本运算 2.3 线性线性表类型的实表类型的实现现-链式映链式映象象单链表操作单链表操作的实现的实现 2.4 应用应用举例举例一元一元多项式的表多项式的表示及运算示及运算 2.5 其他其他形式的链表形式的链表静态链表静态链表 循环链表循环链表 双向链表双向链表19顺序表的几种基本运算（续）顺序表的几种基本运算（续）线性表操作线性表操作ListInsert(&LListI

33、nsert(&L, i, e), i, e)的实现的实现：Status ListInsert_Sq(SqList &L, int pos, ElemType e) / 在顺序线性表在顺序线性表L的第的第pos个元素之前插入新的元素个元素之前插入新的元素e，pos的合法值为的合法值为1posListlength_Sq(L)+1if (pos L.length+1) return ERROR; / 插入插入位置不合法位置不合法if (L.length = L.listsize) / 当前存储空间已满，增加当前存储空间已满，增加分配分配newbase = (ElemType *)re

34、alloc(L.elem, (L.listsize+ LISTINCREMENT) *sizeof (ElemType);if (!newbase) exit(OVERFLOW); / 存储分配失败存储分配失败L.elem = newbase; / 新基址新基址L.listsize += LISTINCREMENT; / 增加存储容量增加存储容量2.1 线性线性表的定义运表的定义运算算2.2 线性线性表类型的实表类型的实现现-顺序映顺序映象象 顺序表的几顺序表的几种基本运算种基本运算 2.3 线性线性表类型的实表类型的实现现-链式映链式映象象单链表操作单链表操作的实现的实现 2.4 应用应用举

35、例举例一元一元多项式的表多项式的表示及运算示及运算 2.5 其他其他形式的链表形式的链表静态链表静态链表 循环链表循环链表 双向链表双向链表20顺序表的几种基本运算（续）顺序表的几种基本运算（续）线性表操作线性表操作ListInsert(&LListInsert(&L, i, e), i, e)的实现的实现：q = &(L.elempos-1); / q指示插入位置指示插入位置for (p = &(L.elemL.length-1); p = q; -p) *(p+1) = *p; / 插入位置及之后的元素右移插入位置及之后的元素右移*q = e; / 插入插入

36、e+L.length; / 表长增表长增1return OK; / ListInsert_Sq2.1 线性线性表的定义运表的定义运算算2.2 线性线性表类型的实表类型的实现现-顺序映顺序映象象 顺序表的几顺序表的几种基本运算种基本运算 2.3 线性线性表类型的实表类型的实现现-链式映链式映象象单链表操作单链表操作的实现的实现 2.4 应用应用举例举例一元一元多项式的表多项式的表示及运算示及运算 2.5 其他其他形式的链表形式的链表静态链表静态链表 循环链表循环链表 双向链表双向链表21顺序表的几种基本运算（续）顺序表的几种基本运算（续）插入算法分析：插入算法分析：上述算法上述算法for循环语句

37、的执行次数为循环语句的执行次数为n-i+1;若若i=1,需移动全部需移动全部n个结点（最坏：个结点（最坏：O(n)）若若i=n+1（在表尾插入）（在表尾插入）,无需用移动结点，直接插入即可。无需用移动结点，直接插入即可。（最好（最好O(1)）移动结点的平均次数：移动结点的平均次数：按等概率考虑：按等概率考虑： 可能的插入位置为可能的插入位置为i=1,2,n,n+1共共n+1个，则个，则pi=1/(n+1) 所以所以顺序表插入算法平均约需顺序表插入算法平均约需移动一半结点。移动一半结点。2) 1(2) 1) 1() 1111nnnnnn=+-+-+=（)1(11+-=+=inPEniii+=+=

38、+-+=+-=1111) 1(11) 1(niniiiinninPE2.1 线性线性表的定义运表的定义运算算2.2 线性线性表类型的实表类型的实现现-顺序映顺序映象象 顺序表的几顺序表的几种基本运算种基本运算 2.3 线性线性表类型的实表类型的实现现-链式映链式映象象单链表操作单链表操作的实现的实现 2.4 应用应用举例举例一元一元多项式的表多项式的表示及运算示及运算 2.5 其他其他形式的链表形式的链表静态链表静态链表 循环链表循环链表 双向链表双向链表22顺序表的几种基本运算（续）顺序表的几种基本运算（续）线性表操作线性表操作ListDelete(&LListDelete(&

39、;L, i, &e), i, &e)的实现的实现Status ListDelete_Sq(SqList &L, int pos, ElemType &e) / 在顺序线性表在顺序线性表L中删除第中删除第pos个元素，并用个元素，并用e返回其值。返回其值。pos的合法值为的合法值为1posListLength_Sq(L)if (pos L.length) return ERROR; / 删除位删除位置不合法置不合法p = &(L.elempos-1); / p为被删除元素的位置为被删除元素的位置e = *p; / 被删除元素的值赋给被删除元素的值赋给eq

40、= L.elem+L.length-1; / 表尾元素的位置表尾元素的位置for (+p; p data-表示由表示由p所指向结点的数据域。所指向结点的数据域。 (*p).next或或p-next-表示由表示由p所指向结点的指针域。所指向结点的指针域。Data next p 结点结点 (*p)2.1 线性线性表的定义运表的定义运算算2.2 线性线性表类型的实表类型的实现现-顺序映顺序映象象 顺序表的几顺序表的几种基本运算种基本运算 2.3 线性线性表类型的实表类型的实现现-链式映链式映象象单链表操作单链表操作的实现的实现 2.4 应用应用举例举例一元一元多项式的表多项式的表示及运算示及运算 2

41、.5 其他其他形式的链表形式的链表静态链表静态链表 循环链表循环链表 双向链表双向链表30结点和单链表的结点和单链表的C C语言描述语言描述typedef struct Lnode ElemType data; / 数据域数据域struct Lnode *next; / 指针域指针域 LNode, *LinkList;结点空间的申请结点空间的申请P=(LNode*)malloc(sizeof(LNode)-对指针对指针p赋值使其指向赋值使其指向某一结点（按需生成一个某一结点（按需生成一个LNode结点类型的新结点）。结点类型的新结点）。其中：其中：(LNode*)-进行类型转换。进行类型转换。

42、Sizeof(LNode)-求结点需用占用的字节数。求结点需用占用的字节数。malloc(size)-在内存中分配在内存中分配size个连续可用字节的空个连续可用字节的空间。间。free(p)-系统回收系统回收p结点。（动态）结点。（动态）2.1 线性线性表的定义运表的定义运算算2.2 线性线性表类型的实表类型的实现现-顺序映顺序映象象 顺序表的几顺序表的几种基本运算种基本运算 2.3 线性线性表类型的实表类型的实现现-链式映链式映象象单链表操作单链表操作的实现的实现 2.4 应用应用举例举例一元一元多项式的表多项式的表示及运算示及运算 2.5 其他其他形式的链表形式的链表静态链表静态链表 循

43、环链表循环链表 双向链表双向链表31单链表操作的实现单链表操作的实现（1 1）建立单链表之）建立单链表之-头插法建表：头插法建表： 思想：思想：从一个空表开始，重复读入数据，生成新结从一个空表开始，重复读入数据，生成新结点，将读入数据存放在新结点的数据域点，将读入数据存放在新结点的数据域 中，然后将新结中，然后将新结点插入到当前链表的表头上，直到读入结束标志为止。点插入到当前链表的表头上，直到读入结束标志为止。A D B C HeadHead S注：头插法生成的链注：头插法生成的链表中结点的次序和输表中结点的次序和输入的顺序相反。入的顺序相反。s = malloc (); / 生成新结点生成新

44、结点scanf(&s-data); / 输入元素值输入元素值snext = H; H = s; / 插入到表头插入到表头2.1 线性线性表的定义运表的定义运算算2.2 线性线性表类型的实表类型的实现现-顺序映顺序映象象 顺序表的几顺序表的几种基本运算种基本运算 2.3 线性线性表类型的实表类型的实现现-链式映链式映象象单链表操作单链表操作的实现的实现 2.4 应用应用举例举例一元一元多项式的表多项式的表示及运算示及运算 2.5 其他其他形式的链表形式的链表静态链表静态链表 循环链表循环链表 双向链表双向链表32单链表操作的实现（续）单链表操作的实现（续）（1 1）建立单链表之）建立单链

45、表之-头插法建表：头插法建表：void CreateList_L(LinkList &L, int n) / 逆位序输入逆位序输入n个元素的值，建立个元素的值，建立带表头结点带表头结点的单链线性的单链线性表表L。L = (LinkList) malloc (sizeof (LNode);L-next = NULL; / 先建立一个带头结点的单链表先建立一个带头结点的单链表for (i = n; i 0; -i) p = (LinkList) malloc (sizeof (LNode); / 生成新结生成新结点点scanf(&p-data); / 输入元素值输入元素值p-nex

46、t = L-next ; L-next = p; / 插入到表头插入到表头 / CreateList_L算法的时间复杂度为算法的时间复杂度为:O(Listlength(L)2.1 线性线性表的定义运表的定义运算算2.2 线性线性表类型的实表类型的实现现-顺序映顺序映象象 顺序表的几顺序表的几种基本运算种基本运算 2.3 线性线性表类型的实表类型的实现现-链式映链式映象象单链表操作单链表操作的实现的实现 2.4 应用应用举例举例一元一元多项式的表多项式的表示及运算示及运算 2.5 其他其他形式的链表形式的链表静态链表静态链表 循环链表循环链表 双向链表双向链表33单链表操作的实现（续）单链表操作

47、的实现（续）（1 1）建立单链表之）建立单链表之-尾插建表法尾插建表法：算法思想：将新结点插入到当前链表的表尾上，可增算法思想：将新结点插入到当前链表的表尾上，可增加一个尾指针加一个尾指针r，使其始终指向链表的尾结点。，使其始终指向链表的尾结点。A C B head r SD 尾插建表可使生尾插建表可使生成的结点次序和成的结点次序和输入的顺序相同输入的顺序相同 s = malloc (); / 生成新结点生成新结点scanf(&s-data); / 输入元素值输入元素值rnext = s; r= s; / 插入到表尾插入到表尾2.1 线性线性表的定义运表的定义运算算2.2 线性线性表类

48、型的实表类型的实现现-顺序映顺序映象象 顺序表的几顺序表的几种基本运算种基本运算 2.3 线性线性表类型的实表类型的实现现-链式映链式映象象单链表操作单链表操作的实现的实现 2.4 应用应用举例举例一元一元多项式的表多项式的表示及运算示及运算 2.5 其他其他形式的链表形式的链表静态链表静态链表 循环链表循环链表 双向链表双向链表34LNode *CREATLISTR( )Char ch; /*建立一建立一不带头结点不带头结点的单链表。逐个插入字符，以的单链表。逐个插入字符，以“$“为结束符，返回单链表头指针为结束符，返回单链表头指针*/ LNode *head,*s,*r; head=NUL

49、L; /*链表开始链表开始为空为空*/ r=NULL; /*尾指针初值为空尾指针初值为空*/ ch=getchar( ); /*读入第一读入第一个结点的值个结点的值*/ while(ch!=$) /*“$“为输入为输入结束符结束符*/ s=（LNode *）malloc(sizeof(LNode); /*生成新生成新结点结点*/s-data=ch;if(head=NULL)head=s;else r-next=s;r=sch=getchar( );If(r!=NULL) r-next=NULL; return head; /*CREATLISTR*/单链表操作的实现（续）单链表操作的实现（续）

50、尾插法建表尾插法建表: :2.1 线性线性表的定义运表的定义运算算2.2 线性线性表类型的实表类型的实现现-顺序映顺序映象象 顺序表的几顺序表的几种基本运算种基本运算 2.3 线性线性表类型的实表类型的实现现-链式映链式映象象单链表操作单链表操作的实现的实现 2.4 应用应用举例举例一元一元多项式的表多项式的表示及运算示及运算 2.5 其他其他形式的链表形式的链表静态链表静态链表 循环链表循环链表 双向链表双向链表35单链表操作的实现（续）单链表操作的实现（续）头、尾插法建表分析：头、尾插法建表分析：上述尾插法建表由于没有生成（附加）头结点，上述尾插法建表由于没有生成（附加）头结点，因此开始结

51、点和其它结点的插入处理并不一样，原因此开始结点和其它结点的插入处理并不一样，原因是开始结点的位置存放在头指针中，而其余结点因是开始结点的位置存放在头指针中，而其余结点的位置是在其前趋结点的指针域的位置是在其前趋结点的指针域 。 尾插法建表的改进算法尾插法建表的改进算法 思想：思想：设头结点，设头结点，使第一个结点和其余结点的使第一个结点和其余结点的插入操作一致。插入操作一致。（表）头结点（在第一个结点之前附设）（表）头结点（在第一个结点之前附设）-其指针域其指针域 存贮指向第一个结点的指针（即第一个结点的存贮位置）。存贮指向第一个结点的指针（即第一个结点的存贮位置）。 头结点的数据域：可有可无

52、头结点的数据域：可有可无 头结点的指针域：指向第一个结点的指针。头结点的指针域：指向第一个结点的指针。2.1 线性线性表的定义运表的定义运算算2.2 线性线性表类型的实表类型的实现现-顺序映顺序映象象 顺序表的几顺序表的几种基本运算种基本运算 2.3 线性线性表类型的实表类型的实现现-链式映链式映象象单链表操作单链表操作的实现的实现 2.4 应用应用举例举例一元一元多项式的表多项式的表示及运算示及运算 2.5 其他其他形式的链表形式的链表静态链表静态链表 循环链表循环链表 双向链表双向链表36单链表操作的实现（续）单链表操作的实现（续）头、尾插法建表分析：头、尾插法建表分析： 空表空表head

53、a1 an 头结点开始结点 非空表非空表无论链表是否为空，其头指针是指向头结点的非空指无论链表是否为空，其头指针是指向头结点的非空指针，所以表的第一个结点和其它结点的操作一致。针，所以表的第一个结点和其它结点的操作一致。2.1 线性线性表的定义运表的定义运算算2.2 线性线性表类型的实表类型的实现现-顺序映顺序映象象 顺序表的几顺序表的几种基本运算种基本运算 2.3 线性线性表类型的实表类型的实现现-链式映链式映象象单链表操作单链表操作的实现的实现 2.4 应用应用举例举例一元一元多项式的表多项式的表示及运算示及运算 2.5 其他其他形式的链表形式的链表静态链表静态链表 循环链表循环链表 双向

54、链表双向链表37单链表操作的实现（续）单链表操作的实现（续）-改进的尾插法建表算法改进的尾插法建表算法LNode *CREATLISTR1( )/*带头结点的尾插法带头结点的尾插法建立单链表，返回表建立单链表，返回表头指针头指针*/Char ch; LNode *head,*s,*r;head=malloc(sizeof(LNode); /*生成生成头结点头结点*/ r=head; /*尾指针初值指向头结点尾指针初值指向头结点*/ ch=getchar(); while(ch!=$) /*“$“为输入结束符为输入结束符*/ s=（LNode *）malloc(sizeof(LNode); /生

55、成新结点生成新结点*/ s-data=ch;r-next=s;/*新结点插新结点插入表尾入表尾*/r=s;/*尾指针尾指针r指向新的指向新的表尾表尾*/ch=getchar(); /*读下一结点读下一结点*/r-next=NULL; return head; /*CREATLISTR1*/2.1 线性线性表的定义运表的定义运算算2.2 线性线性表类型的实表类型的实现现-顺序映顺序映象象 顺序表的几顺序表的几种基本运算种基本运算 2.3 线性线性表类型的实表类型的实现现-链式映链式映象象单链表操作单链表操作的实现的实现 2.4 应用应用举例举例一元一元多项式的表多项式的表示及运算示及运算 2.5

56、 其他其他形式的链表形式的链表静态链表静态链表 循环链表循环链表 双向链表双向链表38单链表操作的实现（续）单链表操作的实现（续）（2 2）查找运算）查找运算按序号查找按序号查找 设单链表的长度为设单链表的长度为n，要查找表中第，要查找表中第i个结点，个结点，算法思想算法思想如下：如下： 从头结点开始顺链扫描，用指针从头结点开始顺链扫描，用指针p指向当前扫描指向当前扫描到的结点，用到的结点，用j作统计已扫描结点数的计数器，当作统计已扫描结点数的计数器，当p扫扫描下一个结点时，描下一个结点时，j自动加自动加1。 P的的初值指向头结点，初值指向头结点，j的初值为的初值为0。 当当j=i时，指针时，

57、指针p所指的结点就是第所指的结点就是第i个结点。个结点。 算法描述算法描述2.1 线性线性表的定义运表的定义运算算2.2 线性线性表类型的实表类型的实现现-顺序映顺序映象象 顺序表的几顺序表的几种基本运算种基本运算 2.3 线性线性表类型的实表类型的实现现-链式映链式映象象单链表操作单链表操作的实现的实现 2.4 应用应用举例举例一元一元多项式的表多项式的表示及运算示及运算 2.5 其他其他形式的链表形式的链表静态链表静态链表 循环链表循环链表 双向链表双向链表39单链表操作的实现（续）单链表操作的实现（续）(2) (2) 线性表的操作线性表的操作GetElem(LGetElem(L, i,

58、&e), i, &e)在链表中的实现在链表中的实现: :基本操作为基本操作为:使指针使指针p始终指向线性表中第始终指向线性表中第i个数据元素个数据元素Status GetElem_L(LinkList L, int pos , ElemType &e) / L为带头结点的单链表的头指针。当线性表中存在第为带头结点的单链表的头指针。当线性表中存在第pos个元素时，个元素时，则将第则将第pos个数据元素的值赋给个数据元素的值赋给e并返回并返回OK, 否则返回否则返回ERRORp = L-next ; j = 1; / 初始化，初始化，p指向第一个结点，指向第一个结点，j为计

59、数器为计数器while (p & jnext ; +j ; if ( ! p | jpos )return ERROR; / 第第pos个元素不存在个元素不存在e = p-data; / 取第取第pos个元素个元素return OK; / GetElem_L算法的时间复杂度为算法的时间复杂度为:O(ListLength(L)2.1 线性线性表的定义运表的定义运算算2.2 线性线性表类型的实表类型的实现现-顺序映顺序映象象 顺序表的几顺序表的几种基本运算种基本运算 2.3 线性线性表类型的实表类型的实现现-链式映链式映象象单链表操作单链表操作的实现的实现 2.4 应用应用举例举例一元一元

60、多项式的表多项式的表示及运算示及运算 2.5 其他其他形式的链表形式的链表静态链表静态链表 循环链表循环链表 双向链表双向链表40单链表操作的实现（续）单链表操作的实现（续）按值查找：按值查找：在链表中，查找是否有结点等于给定值在链表中，查找是否有结点等于给定值key的结的结点，若有的话，则返回首次找到的值为点，若有的话，则返回首次找到的值为key的结点的的结点的存储位置；否则返回存储位置；否则返回null. 算法思想：算法思想： 从开始结点出发，顺链逐个结点的值和给予定从开始结点出发，顺链逐个结点的值和给予定值值key作比较。作比较。 算法描述（略）算法描述（略）2.1 线性线性表的定义运表的定义运算算2.2 线性线性表类型的实表类型的实现现-顺序映顺序映象象 顺序表的几顺序表的几种基本运算种基本运算 2.3 线性线性表类型的实表类型的实现现-链式映链式映象象单链表操作单链表操作的实现的实现 2.4 应用应用举例举例一元一元多项式的表多项式的表示及运算示及运算 2.5