数据结构线性表ppt

1、线性表线性表是一种最简单的是一种最简单的线性结构线性结构 线性结构的线性结构的基本特征基本特征: :1集合中必存在唯一的一个集合中必存在唯一的一个“第一元素第一元素”2集合中必存在唯一的一个集合中必存在唯一的一个 “最后元素最后元素”3除最后元素在外，均有除最后元素在外，均有 唯一的后继唯一的后继4除第一元素之外，均有除第一元素之外，均有 唯一的前驱唯一的前驱线性结构线性结构 是是 一个数据元素的一个数据元素的有序（次序）集合有序（次序）集合2.1 线性表的类型定义线性表的类型定义2.3 线性表类型的实现线性表类型的实现 链式映象链式映象2.4 一元多项式的表示一元多项式的表示2.2 线性表类

2、型的实现线性表类型的实现 顺序映象顺序映象抽象数据类型抽象数据类型线性表线性表的定义如下：的定义如下：ADT List 数据对象数据对象：D ai | ai ElemSet, i=1,2,.,n, n0 称称 n 为线性表的为线性表的表长表长; 称称 n=0 时的线性表为时的线性表为空表空表。数据关系数据关系：R1 |ai-1 ,aiD, i=2,.,n 设线性表为设线性表为 (a1，a2, . . . ，ai，. . . ，an), 称称 i 为为 ai 在线性表中的在线性表中的位序位序。 基本操作：基本操作： 结构初始化操作结构初始化操作结构销毁操作结构销毁操作 引用型操作引用型操作 加工

3、型操作加工型操作 ADT List InitList( &L )操作结果：操作结果：构造一个空的线性表构造一个空的线性表 L。初始化操作初始化操作 结构销毁操作结构销毁操作DestroyList( &L )初始条件：初始条件：操作结果：操作结果：线性表线性表 L 已存在。已存在。销毁线性表销毁线性表 L。ListEmpty( L )ListLength( L )PriorElem( L, cur_e, &pre_e )NextElem( L, cur_e, &next_e ) GetElem( L, i, &e )LocateElem( L, e, compare( ) )ListTraver

4、se(L, visit( )引用型操作引用型操作: : ListEmpty( L )初始条件：初始条件：操作结果：操作结果：线性表线性表 L 已存在已存在。若若 L 为空表，则返回为空表，则返回TRUE，否则，否则FALSE。（线性表判空）ListLength( L )初始条件：初始条件：操作结果：操作结果：线性表线性表 L 已存在已存在。返回返回 L 中元素个数。中元素个数。（求线性表的长度） PriorElem( L, cur_e, &pre_e )初始条件：初始条件：操作结果：操作结果：线性表线性表 L 已存在。已存在。若若 cur_e 是是 L 的元素，则用的元素，则用pre_e 返回

5、它的前驱，否则返回它的前驱，否则操作失败，操作失败，pre_e无定义。无定义。（求数据元素的前驱）（求数据元素的前驱）NextElem( L, cur_e, &next_e )初始条件：初始条件：操作结果：操作结果：线性表线性表 L 已存在已存在。若若 cur_e 是是 L 的元素，则用的元素，则用next_e 返回它的后继，否则返回它的后继，否则操作失败，操作失败，next_e无定义。无定义。（求数据元素的后继）（求数据元素的后继）GetElem( L, i, &e ) 初始条件：初始条件： 操作结果：操作结果：线性表线性表 L 已存在，已存在，用用 e 返回返回L中第中第 i 个元素的值个

6、元素的值。（求线性表中某个数据元素）（求线性表中某个数据元素）且且 1iLengthList(L)LocateElem( L, e, compare( ) )初始条件：初始条件：操作结果：操作结果：线性表线性表 L 已存在，已存在，e e 为给定值，为给定值， compare( ) 是元素判定函数。是元素判定函数。返回返回 L 中第中第 1 个与个与 e 满足关系满足关系 compare( ) 的元素的的元素的位序位序。若这样的元素不存在，则返回值为若这样的元素不存在，则返回值为 0。（定位函数）（定位函数） ListTraverse(L, visit( )初始条件：初始条件：操作结果：操作结

7、果：线性表线性表 L 已存在。已存在。visit() 为某个访问函数为某个访问函数。依次依次对对 L 中中每个元素调用每个元素调用函数函数visit( )。一旦。一旦 visit( )失失败，则操作失败。败，则操作失败。（遍历线性表）（遍历线性表）加工型操作加工型操作 ClearList( &L )PutElem( &L, i, e )ListInsert( &L, i, e )ListDelete(&L, i, &e) ClearList( &L )初始条件：初始条件：操作结果：操作结果：线性表线性表 L 已存在。已存在。将将 L 重置为空表。重置为空表。（线性表置空）（线性表置空）PutE

8、lem( &L, i, e )初始条件：初始条件：操作结果：操作结果：线性表线性表 L 已存在，已存在，L 中第中第 i 个元素赋值个元素赋值 e e 。（改变数据元素的值）（改变数据元素的值）且且 1iLengthList(L) ListInsert( &L, i, e )初始条件：初始条件：操作结果：操作结果：线性表线性表 L 已存在已存在，在在 L 的第的第 i 个元素之前个元素之前插入插入新的元素新的元素 e，L 的长度增的长度增1。（插入数据元素）（插入数据元素）且且 1iLengthList(L)+1ListDelete(&L, i, &e)初始条件：初始条件：操作结果：操作结果：

9、线性表线性表 L 已存在且非空，已存在且非空，删除删除 L 的第的第 i 个元素，并用个元素，并用 e 返回其值，返回其值，L 的长度减的长度减1。（删除数据元素）（删除数据元素）1iLengthList(L)利用上述定义的利用上述定义的线性表类型线性表类型 可以实现其它更复杂的操作可以实现其它更复杂的操作例例 2-2例例 2-3例例 2-1 假设:有两个集合集合 A 和和 B 分别用两个线性表线性表 LA 和和 LB 表示，即：线性表中的数据元素即为集合中的成员。 现要求一个新的集合现要求一个新的集合AAB。例例 2-1 要求对线性表作如下操作：要求对线性表作如下操作：扩大线性表扩大线性表

10、LA，将，将存在于线性表存在于线性表LB 中中而而不存在于线性表不存在于线性表 LA 中中的的数据元素数据元素插入到线性表插入到线性表 LA 中中去。去。上述问题可演绎为：上述问题可演绎为：1从线性表从线性表 LB 中依次查看每个数据元素中依次查看每个数据元素;2依值在线性表依值在线性表 LA 中进行查访中进行查访; 3若不存在，则插入之若不存在，则插入之。GetElem(LB, i)e LocateElem(LA, e, equal( ) ListInsert(LA, n+1, e)( n 表示线性表表示线性表 LA 当前长度当前长度)操作步骤：操作步骤： GetElem(Lb, i, e)

11、; / 取取Lb中第中第i个数据元素赋给个数据元素赋给e if (!LocateElem(La, e, equal( ) ) ListInsert(La, +La_len, e); / La中不存在和中不存在和 e 相同的数据元素，则插入之相同的数据元素，则插入之 La_len = ListLength(La); / 求线性表的长度求线性表的长度 Lb_len = ListLength(Lb); for (i = 1; i = Lb_len; i+) /for / unionvoid union(List &La, List Lb) 已知一个已知一个非纯集合非纯集合 B，试构造一个，试构造一个

12、纯集合纯集合 A，使，使 A中只包含中只包含 B 中所有值各中所有值各不相同的数据元素。不相同的数据元素。仍选用仍选用线性表线性表表示集合表示集合例例 2-2集合集合 B集合集合 A从集合从集合 B 取出物件放入集合取出物件放入集合 A要求集合要求集合A中中同样物件不能有两件以上同样物件不能有两件以上因此，因此，算法的策略应该和例算法的策略应该和例2-1基本相同基本相同,差别仅在于集合差别仅在于集合 A 的初始状态是的初始状态是“空集空集”void union(List &La, List Lb) La_len=ListLength(La); Lb_len=ListLength(Lb); /

13、union GetElem(Lb, i, e); / 取取Lb中第中第 i 个数据元素赋给个数据元素赋给 e if (!LocateElem(La, e, equal( ) ) ListInsert(La, +La_len, e); / La中不存在和中不存在和 e 相同的数据元素，则插入之相同的数据元素，则插入之for (i = 1; i = Lb_len; i+) /forInitList(La); / 构造构造( (空的空的) )线性表线性表LA若线性表中的数据元素相互之间若线性表中的数据元素相互之间可以比较可以比较，并且数据元素在表中依值并且数据元素在表中依值非递减或非递增非递减或非递

14、增有序排列，即有序排列，即 a ai iaai-1i-1 或或 a ai iaai-1i-1(i = 2,3, n)(i = 2,3, n)，则，则称该表为称该表为有序表有序表(Ordered List)(Ordered List)。试改变结构，以试改变结构，以有序表有序表表示集合。表示集合。例如例如：下面是非递减线性表：下面是非递减线性表（2，3，3，5，6，6，6，8，12）对集合对集合 B 而言，而言， 值相同的数据元素必定相邻值相同的数据元素必定相邻对集合对集合 A 而言，而言， 数据元素依值从小至大的顺序插入数据元素依值从小至大的顺序插入因此，数据结构改变了，因此，数据结构改变了，

15、解决问题的策略也相应要改变。解决问题的策略也相应要改变。void purge(List &La, List Lb) InitList(LA); ; La_len = ListLength(La); Lb_len =ListLength(Lb); / 求线性表的长度求线性表的长度 for (i = 1; i = Lb_len; i+) /for / purge GetElem(Lb, i, e); / 取取Lb中第中第i个数据元素赋给个数据元素赋给 eif (ListEmpty(La) | !equal (en, e) ListInsert(La, +La_len, e); en = e;/en

16、是是La中的最后一个元素中的最后一个元素 / La中不存在和中不存在和 e 相同的数据元素，则插入之相同的数据元素，则插入之则则 归并两个归并两个“其数据元素按值非递减有序其数据元素按值非递减有序排列排列”的有序表的有序表 LA 和和 LB，求得有序表，求得有序表 LC 也具有同样特性。也具有同样特性。设设 La = (a1, , ai, , an), Lb = (b1, , bj, , bm) Lc = (c1, , ck, , cm+n)且由且由(a1, , ai-1)和和(b1, ,bj-1)归并得归并得 (c1, , ck-1)jijjiikbabbaac例例 2-3i=1,2,nj=

17、1,2,mk = 1, 2, , m+n1初始化初始化 LC 为空表；为空表；基本操作：基本操作：2分别从分别从 LA和和LB中取得当前元素中取得当前元素 ai 和和 bj；3若若 aibj，则将，则将 ai 插入到插入到 LC 中，否则将中，否则将 bj 插入到插入到 LC 中；中；4重复重复 2 和和 3 两步，直至两步，直至 LA 或或 LB 中元素中元素 被取完为止；被取完为止；5将将 LA 表或表或 LB 表中剩余元素复制插入到表中剩余元素复制插入到 LC 表中。表中。void MergeList(List La, List Lb, List &Lc) / 本算法将非递减的有序表本算

18、法将非递减的有序表 La 和和 Lb 归并为归并为 Lc / merge_listwhile (i = La_len) & (j = Lb_len) / La 和和 Lb 均不空均不空 while (i=La_len) / 若若 La 不空不空while (j=Lb_len) / 若若 Lb 不空不空InitList(Lc); / 构造空的线性表构造空的线性表 Lci = j = 1; k = 0;La_len = ListLength(La);Lb_len = ListLength(Lb);while (i = La_len) & (j = Lb_len) / La 和和 Lb 均非空，均非

19、空，i = j = 1, k = 0 GetElem(La, i, ai); GetElem(Lb, j, bj); if (ai = bj) / 将将 ai 插入到插入到 Lc 中中 ListInsert(Lc, +k, ai); +i; else / 将将 bj 插入到插入到 Lc 中中 ListInsert(Lc, +k, bj); +j; while (i = La_len) / 当当La不空时不空时 GetElem(La, i+, ai); ListInsert(Lc, +k, ai); / 插入插入 La 表中剩余元素表中剩余元素 while (j = Lb_len) / 当当Lb

20、不空时不空时 GetElem(Lb, j+, bj); ListInsert(Lc, +k, bj); / 插入插入 Lb 表中剩余元素表中剩余元素最简单的一种顺序映象方法是：最简单的一种顺序映象方法是： 令令 y y 的存储位置和的存储位置和 x x 的存储位置的存储位置相邻相邻( (用相邻的两个数组元素用相邻的两个数组元素) )。顺序映象顺序映象 以以 x 的存储位置和的存储位置和 y 的存储位置的存储位置之间某种关系表示逻辑关系之间某种关系表示逻辑关系 用一组用一组地址连续地址连续的存储单元的存储单元 依次存放依次存放线性表中的数据元素线性表中的数据元素 a1 a2 ai-1 ai an

21、线性表的线性表的起始地址起始地址，称作线性表的称作线性表的基地址基地址以“存储位置相邻存储位置相邻”表示有序对 即：LOC(ai) = LOC(ai-1) + C 一个数据元素所占存储量一个数据元素所占存储量所有数据元素的存储位置均取决于所有数据元素的存储位置均取决于 第一个数据元素的存储位置第一个数据元素的存储位置 LOC(ai) = LOC(a1) + (i-1)C 基地址基地址顺序映像的顺序映像的 C 语言描述语言描述分析分析：顺序存储的线性表的数据类型应包括：顺序存储的线性表的数据类型应包括：（1 1）一片连续的存储空间的起始地址）一片连续的存储空间的起始地址（2 2）线性表的长度）线

22、性表的长度( (已存储的数据个数已存储的数据个数) )（3 3）存储空间的大小）存储空间的大小（能够存储的数据总数）（能够存储的数据总数）即：即：顺序存储的线性表的数据类型是结构体类型顺序存储的线性表的数据类型是结构体类型一片连续的存储空间如何申请？一片连续的存储空间如何申请？顺序映像的顺序映像的 C 语言描述语言描述typedef struct SqList; / 俗称 顺序表顺序表ElemType *elem; / 存储空间基址int length; / 当前长度int listsize; / 当前分配的存储容量 / (以sizeof(ElemType)为单位)如： SqList La;

23、La.elem La. length La. listsize 存放一片连续存放一片连续空间的地址空间的地址存放线性表的存放线性表的长度长度存放线性表存放线性表的空间大小的空间大小连续空间的申请、连续空间的申请、lala各个成员的值由初始各个成员的值由初始化操作完成化操作完成线性表的基本操作在线性表的基本操作在顺序表顺序表中的实现中的实现InitList(&L) / 结构初始化结构初始化LocateElem(L, e, compare() / 查找查找ListInsert(&L, i, e) / 插入元素插入元素ListDelete(&L, i,&e) / 删除元素删除元素Status Ini

24、tList_Sq( SqList& L, int maxsize ) / 构造一个最大容量为 maxsize 的顺序表 / InitList_Sq算法时间复杂度时间复杂度：O(1)L.elem = new ElemTypemaxsize; / 为顺序表分配大小为 maxsize 的数组空间if (!L.elem) exit(OVERFLOW);L.length = 0;L.listsize = maxsize;return OK;初初始始化化操操作作例如：顺序表的查找e =38pppppi 1 2 3 4 1 850p可见，基本操作是，将顺序表中的元素逐个和给定值 e 相比较。L.length

25、L.listsizeL.elem 7 1023 75 41 38 54 62 17L.elem int LocateElem_Sq(SqList L, ElemType e, Status (*compare)(ElemType, ElemType) / 在顺序表中查询第一个满足判定条件的数据元素，在顺序表中查询第一个满足判定条件的数据元素， / 若存在，则返回它的位序，否则返回若存在，则返回它的位序，否则返回 0 0 / LocateElem_Sq O( ListLength(L) )if (i = L.length) return i; else return 0; 算法的算法的时间复杂度

26、时间复杂度为：为：i = 1; / i i 的初值为第的初值为第 1 1 个元素的位序个元素的位序p = L.elem; / p p 的初值为第的初值为第 1 1 个元素的存储位置个元素的存储位置while (i = L.length & !(*compare)(*p+, e) +i;(*compare)(*p+, e)/找到满足条件的元素找到满足条件的元素/ 没有找到满足条件的元素没有找到满足条件的元素查查找找线性表线性表操作操作 ListInsert(&L, i, e)的实现的实现：首先分析首先分析:插入元素时，插入元素时，线性表的逻辑结构线性表的逻辑结构发生什么变化发生什么变化？ (a1

27、, , ai-1, ai, , an) 改变为a1 a2 ai-1 ai ana1 a2 ai-1 ai ean, 表的长度增加1(a1, , ai-1, e, ai, , an) Status ListInsert_Sq(SqList &L, int i, ElemType e) / 在顺序表在顺序表L的第的第 i 个元素之前插入新的元素个元素之前插入新的元素e,e, / i 的合法范围为的合法范围为 1iL.length+1 / ListInsert_Sq 算法时间复杂度算法时间复杂度为为: :O( ListLength(L) )q = &(L.elemi-1); / q 指示插入位置指示

28、插入位置for (p = &(L.elemL.length-1); p = q; -p) *(p+1) = *p; / 插入位置及之后的元素右移插入位置及之后的元素右移*q = e; / 插入插入e+L.length; / 表长增表长增1return OK;元素右移元素右移if (L.length = L.listsize) return OVERFLOW; / 当前存储空间已满当前存储空间已满 if (i L.length+1) return ERROR; / 插入位置不合法插入位置不合法考虑移动元素的平均情况考虑移动元素的平均情况: : 假设在第假设在第 i 个元素之前插入的概率为个元素之

29、前插入的概率为 ， 则在长度为则在长度为n 的线性表中的线性表中插入一个元素所需插入一个元素所需移动元素次数的期望值移动元素次数的期望值为：为：ip11) 1(niiisinpE11) 1(11niisinnE2n 若假定在线性表中任何一个位置上进行若假定在线性表中任何一个位置上进行插入插入的概率的概率都是都是相等相等的，则的，则移动元素的期望值移动元素的期望值为为：O(n)21 18 30 75 42 56 8721 18 30 75例如：ListInsert_Sq(L, 5, 66) L.length-10pppq87564266q = &(L.elemi-1); / q 指示插入位置指示

30、插入位置for (p = &(L.elemL.length-1); p = q; -p) *(p+1) = *p;线性表操作线性表操作 ListDelete(&L, i, &e)的实现的实现：首先分析：首先分析：删除元素时，删除元素时，线性表的逻辑结构发生什么变化？线性表的逻辑结构发生什么变化？ (a1, , ai-1, ai, ai+1, , an) 改变为ai+1 an, 表的长度减少1a1 a2 ai-1 ai ai+1 ana1 a2 ai-1 (a1, , ai-1, ai+1, , an)Status ListDelete_Sq (SqList &L, int i, ElemTyp

31、e &e) / ListDelete_Sqfor (+p; p = q; +p) *(p-1) = *p; / 被删除元素之后的元素左移被删除元素之后的元素左移-L.length; / 表长减表长减1 1return OK;算法时间复杂度算法时间复杂度为为: : O( ListLength(L)p = &(L.elemi-1); / p 为被删除元素的位置为被删除元素的位置e = *p; / 被删除元素的值赋给被删除元素的值赋给 eq = L.elem+L.length-1; / 表尾元素的位置表尾元素的位置if (i L.length) return ERROR; / 删除位置不合法删除位置

32、不合法元素左移元素左移考虑移动元素的平均情况考虑移动元素的平均情况: : 假设删除第假设删除第 i 个元素的概率为个元素的概率为 , 则在长度为则在长度为n 的线性表中的线性表中删除一个元素删除一个元素所需所需移动元素次数的期望值移动元素次数的期望值为：为：iqniidlinqE1)(nidlinnE1)(121n若假定在线性表中任何一个位置上进行删除若假定在线性表中任何一个位置上进行删除的的概率概率都是都是相等相等的，则的，则移动元素的期望值移动元素的期望值为为：O(n)21 18 30 75 42 56 8721 18 30 75L.length-10pppq8756p = &(L.ele

33、mi-1);q = L.elem+L.length-1;for (+p; p next; j = 1; / p p指向第一个结点，指向第一个结点，j j为计数器为计数器while (p & jnext; +j; / 顺指针向后查找，直到顺指针向后查找，直到 p p 指向第指向第 i i 个元素个元素 / 或或 p p 为空为空if ( !p | ji ) return ERROR; / 第第 i i 个元素不存在个元素不存在e = p-data; / 取得第取得第 i i 个元素个元素return OK;ai-1 线性表的操作线性表的操作 ListInsert(&L, i, e) 在单链表中的

34、实现在单链表中的实现： 有序对有序对 改变为改变为 和和 eaiai-1 因此，在单链表中第因此，在单链表中第 i 个结点之前进个结点之前进行插入的基本操作为行插入的基本操作为: 找到线性表中第找到线性表中第i-1i-1个结点，然后修改个结点，然后修改其指向后继的指针。其指向后继的指针。可见，在链表中插入结点只需要修改指针。可见，在链表中插入结点只需要修改指针。但同时，但同时，若要在第若要在第 i 个结点之前插入元素，个结点之前插入元素，修改的是第修改的是第 i-1 个结点的指针个结点的指针(next)。 Status ListInsert_L(LinkList L, int i, ElemT

35、ype e) / L 为带头结点的单链表的头指针，本算法为带头结点的单链表的头指针，本算法 / 在链表中第在链表中第i 个结点之前插入新的元素个结点之前插入新的元素 e / ListInsert_L算法的算法的时间复杂度时间复杂度为为:O(ListLength(L)/插入插入p = L; j = 0;/p指向头结点指向头结点while (p & j next; +j; / 寻找第寻找第 i-1 个结点个结点if (!p | j i-1) return ERROR; / i 大于表长或者小于大于表长或者小于1 s = new LNode; / 生成新结点生成新结点if ( s = NULL) r

36、eturn ERROR;s-data = e; s-next = p-next; p-next = s; / 插入插入return OK; eai-1aiai-1sp线性表线性表的操作的操作ListDelete (&L, i, &e)在在链表中的实现链表中的实现:有序对有序对 和和 改变为改变为 ai-1aiai+1ai-1 在单链表中在单链表中删除删除第第 i i 个结点的基本个结点的基本操作为操作为: :找到线性表中第找到线性表中第i-1i-1个结点，修个结点，修改其指向后继的指针。改其指向后继的指针。ai-1aiai+1ai-1q = p-next; p-next = q-next; e

37、 = q-data; delete(q);pq Status ListDelete_L(LinkList L, int i, ElemType &e) / 删除以删除以 L 为头指针为头指针(带头结点带头结点)的单链表中第的单链表中第 i 个结点个结点 / ListDelete_L算法的算法的时间复杂度时间复杂度为为: O(ListLength(L)p = L; j = 0;while (p-next & j next; +j; / 寻找第寻找第 i -1个结点个结点q = p-next; p-next = q-next; / 删除并释放结点删除并释放结点e = q-data; delete(

38、q);return OK;if (!(p-next) | j i-1) return ERROR; / 删除位置不合理删除位置不合理清除操作清除操作 ClearList(&L) 在链表中的实现在链表中的实现:void ClearList(&L) / 将单链表重新置为一个空表将单链表重新置为一个空表 while (L-next) p=L-next; L-next=p-next; / ClearListdelete(p);算法时间复杂度：O(ListLength(L)如何从线性表得到单链表？如何从线性表得到单链表？链表是一个动态的结构，它不需要链表是一个动态的结构，它不需要予先分配空间，因此予先分

39、配空间，因此生成链表的过生成链表的过程程是一个结点是一个结点“逐个插入逐个插入” ” 的过程。的过程。例如：正位序例如：正位序( (尾插法尾插法) )输入输入 n n 个数据元个数据元素的值素的值(a(a1 1,a,a2 2,a,an n) )，建立带头结点的，建立带头结点的单链表。单链表。操作步骤操作步骤(必须用指针变量记住最后一个结点必须用指针变量记住最后一个结点)：一、建立一个一、建立一个“空表空表”；二、输入数据元素二、输入数据元素a1， 建立结点并插入；建立结点并插入；三、输入数据元素三、输入数据元素a2， 建立结点并插入；建立结点并插入；a1a1a2四、依次类推，直至输入四、依次类

40、推，直至输入a an n为止。为止。例如：逆位序（例如：逆位序（头插法头插法）输入）输入 n n 个数据个数据元素的值元素的值(a(an n,a,an-1n-1,a,a1 1) ) ，建立带头结，建立带头结点的单链表。点的单链表。操作步骤（操作步骤（新结点总是插在头结点之后新结点总是插在头结点之后）：）：一、建立一个一、建立一个“空表空表”；二、输入数据元素二、输入数据元素an， 建立结点并插入；建立结点并插入；三、输入数据元素三、输入数据元素an-1， 建立结点并插入；建立结点并插入；ananan-1四、依次类推，直至输入四、依次类推，直至输入a a1 1为止。为止。void CreateL

41、ist_L(LinkList &L, int n) / 逆序输入逆序输入 n n 个数据元素，建立带头结点的单链表个数据元素，建立带头结点的单链表 / CreateList_L算法的算法的时间复杂度时间复杂度为为:O(Listlength(L)L = new LNode; L-next = NULL; / 先建立一个带头结点的空单链表先建立一个带头结点的空单链表for (i = n; i 0; -i) /头插法头插法 p = new LNode; scanf(&p-data); / 输入元素值输入元素值 p-next = L-next; L-next = p; / 插入插入void Creat

42、eList_L(LinkList &L, int n) / 正序输入正序输入 n n 个数据元素，建立带头结点的单链表个数据元素，建立带头结点的单链表 / CreateList_L算法的算法的时间复杂度时间复杂度为为:O(Listlength(L)L = new LNode; L-next = NULL; / 先建立一个带头结点的空单链表先建立一个带头结点的空单链表q= L;/q q记住链表的最后一个结点记住链表的最后一个结点for (i = 1; i next=NULL; scanf(&p-data); / 输入元素值输入元素值 q-next = p; q = p; / 插入插入 单链表特点

43、单链表特点它是一种动态结构，需要时用它是一种动态结构，需要时用malloc()函数或运算符函数或运算符new申请申请不需预先分配空间不需预先分配空间指针占用额外存储空间指针占用额外存储空间不能随机存取，查找速度慢，适不能随机存取，查找速度慢，适合对线性表做插入与删除操作合对线性表做插入与删除操作回顾回顾 2.1 节中三个例子的算法，看节中三个例子的算法，看一下当线性表分别以顺序存储结构一下当线性表分别以顺序存储结构和链表存储结构实现时，它们的时和链表存储结构实现时，它们的时间复杂度为多少？间复杂度为多少？void union(List &La, List Lb) La_len = ListLe

44、ngth(La); Lb_len =ListLength(Lb); for (i = 1; i = Lb_len; i+) GetElem(Lb, i, e); if (!LocateElem(La, e, equal( ) ListInsert(La, +La_len, e); /for / union控制结构：控制结构：基本操作：基本操作：for 循环循环GetElem, LocateElem 和和 ListInsert当以当以顺序映像顺序映像实现抽象数据类型线性表时为实现抽象数据类型线性表时为: O( ListLength(La)ListLength(Lb) ) 当以当以链式映像链式映像

45、实现抽象数据类型线性表时为实现抽象数据类型线性表时为: O( ListLength(La)ListLength(Lb) )例例2-1算法时间复杂度算法时间复杂度 void purge(List &La, List Lb) InitList(La); ; La_len = ListLength(La); Lb_len =ListLength(Lb); for (i = 1; i = Lb_len; i+) GetElem(Lb, i, e); if (ListEmpty(La) | !equal (en, e) ListInsert(La, +La_len, e); en = e; /for /

46、 purge控制结构：控制结构：基本操作：基本操作：for 循环循环GetElem 和和 ListInsert当以当以顺序映像顺序映像实现抽象数据类型线性表时为实现抽象数据类型线性表时为: O( ListLength(Lb) )当以当以链式映像链式映像实现抽象数据类型线性表时为实现抽象数据类型线性表时为: O( Lb_len(Lb_len+La_len) )例例2-2算法时间复杂度算法时间复杂度void MergeList(List La, List Lb, List &Lc) InitList(Lc); i = j = 1; k = 0; La_len = ListLength(La); L

47、b_len = ListLength(Lb); while (i = La_len) & (j = Lb_len) GetElem(La, i, ai); GetElem(Lb, j, bj); if (ai next = p-next; p-next = s;s-next-prior = s; s-prior = p;psai-1ai插入插入ai-1删除删除aiai+1q=p-next；p-next = p-next-next;p-next-prior = p;delete(q);pai-1q实现方法：实现方法： 借助于结构体数组实现链表借助于结构体数组实现链表。静态链表的定义静态链表的定义

48、 # define MAXSIZE 链表可能的最大长度 typedef sturct ElemType data ； int next； StaticListTypeMAXSIZE StaticListType sa； 数据数据 指针指针sai.data sai.next线性表中第i+1个数据元素： 存储特点：存储特点：所有的结点所有的结点顺序存储顺序存储，但，但位置不表示位置不表示结点之间的结点之间的逻辑关系逻辑关系。好处好处 ：由用户自己来管理。所需整个空间的大小不变。但执行时，数据元素之间的关系变了，只修改指针即可。例例 头指针 f 0 1 2 3 4 5 6 7 8 9data 75

49、62 83 44 57 94 50 68next 4 3 8 6 7 2 -1 5 1 0 4 7 5 2 8 f 44 50 57 62 68 1 3 6 75 83 94 五、有序表类型五、有序表类型ADT Ordered_List 数据对象数据对象: S = xi|xi OrderedSet ， i=1,2,n, n0 集合中集合中任意两个任意两个元素之间元素之间均可以均可以进行比较进行比较数据关系数据关系: :R = | xi-1, xi S, xi-1 xi, i=2,3,n 线性表中的数据是从小到大线性表中的数据是从小到大排序的。排序的。 基本操作：基本操作： LocateElem

50、( L, e, &q, int(*compare)(ElemType,ElemType) )初始条件初始条件：有序表：有序表L已存在。已存在。操作结果操作结果：若有序表：若有序表L中存在元素中存在元素e e，则，则 q指示指示L中第一个值为中第一个值为 e 的元素的位置的元素的位置，并，并返回函数值返回函数值TRUE；否则；否则 q 指示第一个大指示第一个大于于 e 的元素的前驱的位置的元素的前驱的位置，并返回函数值，并返回函数值FALSE。Compare是一个是一个指向有序判定函指向有序判定函数的指针变量数的指针变量( 12, 23, 34, 45, 56, 67, 78, 89, 98,

51、145 )例如例如:若若 e = 45, 则则 q 指向指向 若若 e = 88, 则则 q 指向指向表示值为表示值为 88 的元素应插入的元素应插入在该指针所指结点之后。在该指针所指结点之后。由此得出：由此得出： 线性链表适用于插入、线性链表适用于插入、删除操作，查找操作要花删除操作，查找操作要花费较多的时间。费较多的时间。nnnxpxpxppxp.)(2210在计算机中，可以用一个线性表来表示在计算机中，可以用一个线性表来表示: : P = (p0, p1, ，pn)一元多项式一元多项式但是对于形如但是对于形如S(x) = 1 + 3x10000 2x20000的多项式，上述表示方法是否合

52、适？的多项式，上述表示方法是否合适？ 一般情况下的一般情况下的一元稀疏多项式一元稀疏多项式可写成可写成 Pn(x) = p1xe1 + p2xe2 + + pmxem其中其中：pi 是指数为是指数为ei 的项的非零系数的项的非零系数， 0 e1 e2 em = n可以下列线性表表示：可以下列线性表表示：（p1, e1）, (p2, e2), , (pm,em) ） P999(x) = 7x3 - 2x12 - 8x999例如例如:可用线性表可用线性表 ( (7, 3), (-2, 12), (-8, 999) )表示表示求两个一元多项式的和求两个一元多项式的和例 pa(x)=7+3x+9x8+

53、5x17 pb(x)=8x+22x7-9x8求：pa=pa+pb-1pa7 0 3 1 9 8 5 17 -1pb8 1 22 7 -9 8 -1pa7 0 11 1 22 7 5 17 pqADT Polynomial 数据对象数据对象： 数据关系数据关系：抽象数据类型一元多项式的定义如下：抽象数据类型一元多项式的定义如下：D ai | ai TermSet, i=1,2,.,m, m0 TermSet 中的中的每个元素包含一个每个元素包含一个 表示系数的实数和表示指数的整数表示系数的实数和表示指数的整数 R1 |ai-1 ,aiD, i=2,.,n 且且ai-1中的指数值中的指数值ai中的

54、指数值中的指数值 CreatPolyn ( &P, m ) DestroyPolyn ( &P ) PrintPolyn ( &P ) 基本操作基本操作：操作结果操作结果：输入输入 m 项的系数和指数，项的系数和指数， 建立一元多项式建立一元多项式 P。初始条件初始条件：一元多项式一元多项式 P 已存在已存在。操作结果操作结果：销毁一元多项式销毁一元多项式 P。初始条件初始条件：一元多项式一元多项式 P 已存在已存在。操作结果操作结果：打印输出一元多项式打印输出一元多项式 P。 PolynLength( P ) AddPolyn ( &Pa, &Pb ) SubtractPolyn ( &Pa

55、, &Pb ) ADT Polynomial初始条件初始条件：一元多项式一元多项式 P 已存在已存在。操作结果操作结果：返回一元多项式返回一元多项式 P 中的项数中的项数。初始条件初始条件：一元多项式一元多项式 Pa 和和 Pb 已存在已存在。操作结果操作结果：完成多项式相加运算，即：完成多项式相加运算，即： Pa = PaPb，并销毁一元多项式，并销毁一元多项式 Pb。一元多项式的数据类型描述：一元多项式的数据类型描述：typedef struct OrderList float coef; / 系数系数 int expn; / 指数指数 struct OrderList *next; El

56、emType， *polynomial; 用带表头结点的用带表头结点的有序链表有序链表表示多项式表示多项式Status CreatPolyn ( polynomail &P, int m ) / 输入输入m项的系数和指数，建立表示一元多项式的有序链表项的系数和指数，建立表示一元多项式的有序链表P / CreatPolynInitList (P); P -coef = 0.0; P - expn = -1; P - next=NULL; / 设置头结点的数据元素设置头结点的数据元素for ( i=1; i=m; +i ) / 依次输入依次输入 m 个非零项个非零项return OK;scanf

57、(e.coef, e.expn);if (!LocateElem ( P, e, q, (*cmp)() ) if ( !InsAfter ( P, q, e ) ) return ERROR; 注意注意: : 1. .输入次序不限输入次序不限; ;2. .指数相同的项只能输入一次指数相同的项只能输入一次例：例：（3+2x-5x2+7x4）+ （ 4x +x3-7x4）La=(3,0),(2,1),(-5,2),(7,4)Lb=( (4,1),(1,3),(-7,4)Lc= (3,0)Lc=(3,0),(6,1)Lc=(3,0),(6,1), (-5,2)Lc=(3,0),(6,1),(-5,2), (1,3)Lc=(3,0),(6,1),(-5,2), (1,3)Lc所对应的多项式为：所对应的多项式为：3+6x-5x2 +x3例：例：（3+2x-5x2+7x4）( 4x2 +x3-7x4）La=(3,0),(2,1),(-5,2),(7,4)Lb=( (4,2),(1,3),(-7,4)步骤一：步骤一： 4x2 (3+2x-5x2+7x4)Lc= (12,2)Lc= (12,2),(8,3)Lc= (12,2),(8,3),(-20,4)Lc= (12,2),(8,3),(-20,4),(28,6)步骤二：步骤二：