Chapter01——线性表

1、第二章第二章线性表线性表+ -0= 2.1 线性表的类型定义线性表的类型定义2.3 线性表的链式表示和实现线性表的链式表示和实现2.4 一元多项式的表示一元多项式的表示2.2 线性表的顺序表示和实现线性表的顺序表示和实现2.1 线性表的类型定义线性表的类型定义一、线性表的逻辑结构一、线性表的逻辑结构 线性表是线性表是n个数据元素个数据元素a1,a2,an的有限序列，的有限序列，记为记为 (a1,a2,ai,an)其中，其中，ai可以是一个数、一个字母、一串字符、一可以是一个数、一个字母、一串字符、一页书，甚至更复杂的信息页书，甚至更复杂的信息例如：英文字母表（例如：英文字母表（A,B,C,Z）

2、 在校生人数变化情况表在校生人数变化情况表 （800，1500，2400，4100，20000） 在稍复杂的线性表中，一个数据元素可以由若干个数据在稍复杂的线性表中，一个数据元素可以由若干个数据项组成，如职工花名册表项组成，如职工花名册表编号姓名性别年龄月收入1王小林男5122002陈红女4718003孙丽丽女3517604赵京男271650在这种情况下，通常把数据元素称为记录，把含有大量在这种情况下，通常把数据元素称为记录，把含有大量记录的线性表称为文件。记录的线性表称为文件。 综上所述：综上所述：线性表中的数据元素可以是各种各样的，线性表中的数据元素可以是各种各样的，但同一线性表中的元素必

3、定具有相同的特性但同一线性表中的元素必定具有相同的特性,即属同一数即属同一数据对象，相邻数据元素之间存在着序偶关系。据对象，相邻数据元素之间存在着序偶关系。若将线性表记为若将线性表记为 （a1,ai-1,ai,ai+1,an），则），则 ai-1是是ai的的直接前趋元素直接前趋元素； ai+1是是ai的的直接后继元素直接后继元素； 当当i=1,2,n-1时，时，ai有且仅有一个直接后继；有且仅有一个直接后继； 当当i=2,3，,n时，时，ai有且仅有一个直接前趋；有且仅有一个直接前趋；即：第一个元素无前趋；最后一个元素无后继；即：第一个元素无前趋；最后一个元素无后继； 其它元素仅有一个直接前趋

4、和一个直接后继。其它元素仅有一个直接前趋和一个直接后继。 线性表中元素的个数线性表中元素的个数n（n0）定义为线性表的）定义为线性表的长度长度； n=0时，称为时，称为空表空表； 在非空表中的每个数据元素在非空表中的每个数据元素ai都有一个确定的位置，都有一个确定的位置，称称i为数据元素在线性表中的为数据元素在线性表中的位序位序。二、抽象数据类型线性表的定义二、抽象数据类型线性表的定义ADT List 数据对象数据对象：D ai | ai ElemSet, i=1,2,.,n, n0 数据关系：数据关系：R1 | ai-1,aiD, i=2,.,n 基本操作：基本操作： 结构初始化操作结构初始

5、化操作结构销毁操作结构销毁操作 引用型操作引用型操作 加工型操作加工型操作 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 )

6、LocateElem( L, e, compare( ) )ListTraverse(L, visit( ) ListEmpty( L )初始条件：初始条件：操作结果：操作结果：线性表L已存在。若L为空表，则返回TRUE，否则FALSE。（线性表判空）ListLength( L )初始条件：初始条件：操作结果：操作结果：线性表L已存在。返回L中元素个数。（求线性表的长度） PriorElem( L, cur_e, &pre_e )初始条件：初始条件：操作结果：操作结果：线性表L已存在。若cur_e是L的元素，但不是第一个，则用pre_e 返回它的前驱，否则操作失败，pre_e无定义。（

7、求数据元素的前驱）NextElem( L, cur_e, &next_e )初始条件：初始条件：操作结果：操作结果：线性表L已存在。若cur_e是L的元素，但不是最后一个，则用next_e返回它的后继，否则操作失败，next_e无定义。（求数据元素的后继）GetElem( L, i, &e ) 初始条件：初始条件： 操作结果：操作结果：线性表L已存在，且 1iLengthList(L)。用 e 返回L中第 i 个元素的值。（求线性表中某个数据元素）LocateElem( L, e, compare( ) )初始条件：初始条件：操作结果：操作结果：线性表L已存在，e为给定值， c

8、ompare( )是元素判定函数。返回L中第中第1个个与e满足满足关系compare( )的元素的位序。若这样的元素不存在，则返回值为0。（定位函数） ListTraverse(L, visit( )初始条件：初始条件：操作结果：操作结果：线性表L已存在，Visit() 为某个访问函数。依次依次对L的每个元素调用函数visit( )。一旦visit( )失败，则操作失败。（遍历线性表）加工型操作加工型操作 ClearList( &L )PutElem( &L, i, &e )ListInsert( &L, i, e )ListDelete(&L, i,

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

10、, &e )初始条件：初始条件：操作结果：操作结果：线性表L已存在且非空， 1iLengthList(L) 。删除L的第i个元素，并用e返回其值，L的长度减1。（删除数据元素） 对上述定义的抽象数据类型线性表，还可以进对上述定义的抽象数据类型线性表，还可以进行一些更复杂的运算，如：行一些更复杂的运算，如： 将两个或两个以上的线性表合并成一个线性表；将两个或两个以上的线性表合并成一个线性表； 把一个线性表拆成两个或两个以上的线性表；把一个线性表拆成两个或两个以上的线性表； 重新复制一个线性表；重新复制一个线性表； 对线性表中的数据元素按某个数据项递增或递减的顺对线性表中的数据元素按某个数

11、据项递增或递减的顺 序进行重新排列，从而得到有序表。序进行重新排列，从而得到有序表。这些运算均可利用上述基本运算来实现。这些运算均可利用上述基本运算来实现。 线性表是一个相当灵活的数据结构，它的长线性表是一个相当灵活的数据结构，它的长度可依据需要进行增减，对数据元素不仅可以访度可依据需要进行增减，对数据元素不仅可以访问，还可以进行插入和删除等操作。运算的具体问，还可以进行插入和删除等操作。运算的具体实现一般依赖所采用的存储结构，所以，这里给实现一般依赖所采用的存储结构，所以，这里给出的只是定义在逻辑结构上的抽象运算，即只关出的只是定义在逻辑结构上的抽象运算，即只关心这些运算是心这些运算是“做什

12、么做什么”的，至于的，至于“怎样实现怎样实现”则依赖于所选定的存储结构。则依赖于所选定的存储结构。利用上述定义的线性表线性表 可以实现其它更复杂的操作例例 2-2例例 2-1 假设:有两个集合集合 A 和和 B 分别用两个线线性表性表 LA 和和 LB 表示，即：线性表中的数据元素即为集合中的成员。 现要求一个新的集合现要求一个新的集合AAB。例例 2-1 要求对线性表作如下操作： 扩大线性表 LA，将存在于线性表存在于线性表LB 中中而不存在于线性表不存在于线性表 LA 中中的数据元素插插入到线性表入到线性表 LA 中中去。上述问题可演绎为：上述问题可演绎为： LA： (c,p,t,a,q,

13、d) LB: (a,d,b,e,p,r) 结果结果LA: (c,p,t,a,q,d,b,e,r)1.从线性表LB中依次察看每个数据元素;2.依值在线性表LA中进行查访; 3.若不存在，则插入之。GetElem(LB, i)e LocateElem(LA, e, equal( ) ListInsert(LA, n+1, e)操作步骤：操作步骤： GetElem(Lb, i, e); / 取取Lb中第中第i个数据元素赋给个数据元素赋给e if (!LocateElem(La, e, equal( ) ) ListInsert(La, +La_len, e); / La中不存在和中不存在和 e 相同

14、的数据元素，则插入之相同的数据元素，则插入之void union(List &La, List Lb) La_len = ListLength(La); Lb_len = ListLength(Lb); / 求线性表的长度求线性表的长度for (i = 1; i = Lb_len; i+) / union 已知已知一个非纯集合非纯集合 B，试构造构造一个纯纯集合集合 A，使使 A中只包含中只包含 B 中所有值各不中所有值各不相相 同的数据元素同的数据元素。仍选用线性表线性表表示集合。补充：例补充：例 LA： () LB: (d,d, c, a,b,b, e) 结果结果LA: (d, c

15、, a,b, e)集合集合 B集合集合 A从集合 B 取出物件放入集合 A要求集合A中同样物件不能有两件以上同样物件不能有两件以上因此，算法的策略应该和例算法的策略应该和例2-1相同相同void union(List &La, List Lb) La_len=ListLength(La); Lb_len=ListLength(Lb); / union GetElem(Lb, i, e); / 取取Lb中第中第 i 个数据元素赋给个数据元素赋给 e if (!LocateElem(La, e, equal( ) ) ListInsert(La, +La_len, e); / La中不存在

16、和中不存在和 e 相同的数据元素，则插入之相同的数据元素，则插入之for (i = 1; i = Lb_len; i+) InitList(La); / 构造构造(空的空的)线性表线性表LA 若线性表中的数据元素相互之间可以比较比较，并且数据元素在线性表中依值非递减或非递增有依值非递减或非递增有序序排列，即 aiai-1 或 aiai-1(i = 2,3, n) 则称该线性表为有序表有序表(Ordered List)(Ordered List)。上例中，以有序表有序表表示集合，然后进行同样的操作。补充：例补充：例例如例如：LA=(2，3，3，5，6，6，6，8，12)LB=()结果：结果：LA

17、=(2，3，5，6，8，12)对集合对集合 B 而言，而言， 值相同的数据元素必定相邻；值相同的数据元素必定相邻；对集合对集合 A 而言，而言， 数据元素依值从小至大的顺序插入。数据元素依值从小至大的顺序插入。void purge(List &La, List Lb) InitList(LA); La_len = ListLength(La);Lb_len =ListLength(Lb); for (i = 1; i = Lb_len; i+) / purge GetElem(Lb, i, e); / 取取Lb中第中第i个数据元素赋给个数据元素赋给 eif (ListEmpty(La)

18、 | !equal (en, e) / en为表为表La中当前最后一个元素中当前最后一个元素 ListInsert(La, +La_len, e); en = e; / La中不存在和中不存在和 e 相同的数据元素，则插入之相同的数据元素，则插入之 在用无序的线性表表示集合时，在用无序的线性表表示集合时，A A中中每插入一个元素，要从头到尾检索一遍，每插入一个元素，要从头到尾检索一遍，看是否已存在相同元素。看是否已存在相同元素。 在用有序表表示集合时，在用有序表表示集合时， A A中每插入中每插入一个元素，只需要比较要插入的值是否等一个元素，只需要比较要插入的值是否等于于A A中的最后一个元素

19、。中的最后一个元素。 因此，数据结构改变了数据结构改变了 -解决问题的策略也相应要改变。解决问题的策略也相应要改变。 已知线性表已知线性表LA和和LB中的数据元素按值非递减有序排中的数据元素按值非递减有序排列，现要求将列，现要求将LA和和LB归并为一个新的线性表归并为一个新的线性表LC，且，且LC中的数据元素仍按值非递减有序排列。中的数据元素仍按值非递减有序排列。例如，设例如，设 LA=(3,5,8,11) i LB=(2,6,8,9,11,15,20) j 则则 LC=(2, 3, 5,6,8,8,9,11,11,15,20) k 例例 2-2 Void MergeList (List La

20、 , List Lb, List &Lc) INITIATE(Lc); i=j=1; k=0; /初始化初始化 La_len= LENGTH (La) ; Lb_len= LENGTH (Lb) ; while (i=La_len)& (j=Lb_len) /La和和Lb均非空均非空 GetElem(La,i,ai); GetElem (Lb,j,bj); if (ai=bj) ListInsert(LC, +k,ai); + i else ListInsert(LC,+k,bj); + j ; while (i=La_len) / 插入插入 La 表中剩余元素表中剩余元素 G

21、etElem(La, i+,ai); ListInsert(LC,+k,ai) ; while (j=Lb_len) / 插入插入 Lb 表中剩余元素表中剩余元素 GetElem(Lb, j+,bj); ListInsert(LC,+k,bj ; / MergeList2.2 线性表的顺序表示和实现线性表的顺序表示和实现一、线性表的顺序存储结构一、线性表的顺序存储结构顺序映象顺序映象二、顺序存储结构的特点二、顺序存储结构的特点三、线性表的顺序存贮结构示意图及描述三、线性表的顺序存贮结构示意图及描述四、线性表的基本操作在顺序表中的实现四、线性表的基本操作在顺序表中的实现五、顺序存储结构的优缺点五

22、、顺序存储结构的优缺点一、线性表的顺序存储结构一、线性表的顺序存储结构 顺序映象顺序映象 最简单的一种顺序映象方法是：最简单的一种顺序映象方法是： 令令y y的存储位置和的存储位置和x x的存储位置相邻的存储位置相邻。 以以 x 的存储位置和的存储位置和 y 的存储位置之间的存储位置之间某种关系表示逻辑关系某种关系表示逻辑关系。顺序存储结构：顺序存储结构： 用一组地址连续地址连续的存储单元依次存放依次存放线性表中的数据元素。 a1 a2 ai-1 ai an线性表的线性表的起始地址起始地址称作线性表的基地址基地址 假设线性表的每个数据元素要占假设线性表的每个数据元素要占c个存储单个存储单元，则

23、元，则 LOC(ai+1)=LOC(ai)+c 所有数据元素的存储位置均取决于第一个所有数据元素的存储位置均取决于第一个数据元素的存储位置，即数据元素的存储位置，即 LOC(ai)=LOC(a1)+(i-1)*c 起始地址（基地址）起始地址（基地址）以“存储位置相邻存储位置相邻”表示有序对二、顺序存储结构的特点二、顺序存储结构的特点 表中相邻的两个元素其物理存储位置也相邻。表中相邻的两个元素其物理存储位置也相邻。即以元素在计算机内物理位置上的相邻来表示线性即以元素在计算机内物理位置上的相邻来表示线性表中数据元素之间相邻的逻辑关系。每个数据元素表中数据元素之间相邻的逻辑关系。每个数据元素的存储位

24、置和线性表的起始位置相差一个和数据元的存储位置和线性表的起始位置相差一个和数据元素在线性表中的序号成正比的常数；只要确定了起素在线性表中的序号成正比的常数；只要确定了起始位置，线性表中任一数据元素都可随机存取。始位置，线性表中任一数据元素都可随机存取。顺顺序存储结构是一种随机存取的存储结构。序存储结构是一种随机存取的存储结构。 三、线性表的顺序存贮结构示意图及描述三、线性表的顺序存贮结构示意图及描述aia2a1内存状态内存状态序号序号存储地址存储地址Loc(a1)Loc(a1) + CLoc(a1) + C * (i-1)12iannLoc(a1) + C * (n-1)空闲空闲Loc(a1)

25、 + (maxlen-1)*c顺序映像的顺序映像的 C C 语言描述语言描述typedef struct SqList; /俗称顺序表俗称顺序表#define LIST_INIT_SIZE 80 / 线性表存储空间的初始分配量线性表存储空间的初始分配量#define LISTINCREMENT 10 / 线性表存储空间的分配增量线性表存储空间的分配增量ElemType *elem; / 存储空间基址存储空间基址int length; / 当前长度当前长度int listsize; / 当前分配的存储容量当前分配的存储容量 / ( (以以sizeof(ElemTypesizeof(ElemTyp

26、e) )为单位为单位) )四、线性表的基本操作在顺序表中的实现四、线性表的基本操作在顺序表中的实现InitList(&L) / 结构初始化结构初始化LocateElem(L, e, compare() / 查找查找ListInsert(&L, i, e) / 插入元素插入元素ListDelete(&L, i) / 删除元素删除元素Status InitList_Sq( SqList& L ) / 构造一个空的线性表构造一个空的线性表 / InitList_Sq算法时间复杂度时间复杂度： O(1)L.elem = (ElemType*) malloc (LIST_

27、 INIT_SIZE sizeof (ElemType);if (!L.elem) exit (OVERFLOW); / 存储分配失败存储分配失败L.length = 0; / 空表长度为零空表长度为零L.listsize = LIST_INIT_SIZE / 初始存储容量初始存储容量return OK;例如：查找顺序表例如：查找顺序表23 75 41 38 54 62 17L.elemL.lengthL.listsizee =38pppppi 1 2 3 4 1 850p可见，基本操作是：将顺序表中的元素逐个和给定值e相比较。 int LocateElem_Sq(SqList L, Elem

28、Type e, Status (*compare)(ElemType, ElemType) /在顺序表中查询第一个满足判定条件的数据元素，在顺序表中查询第一个满足判定条件的数据元素， / 若存在，则返回它的位序，否则返回若存在，则返回它的位序，否则返回 0 0 / LocateElem_Sq O( ListLength(L) )算法的算法的时间复杂度时间复杂度为：为：i = 1; / i i 的初值为第的初值为第 1 1 元素的位序元素的位序p = L.elem; / p p 的初值为第的初值为第 1 1 元素的存储位置元素的存储位置while (i = L.length & !(*c

29、ompare)(*p+, e) +i;if (i = L.length) return i; else return 0;线性表操作 ListInsert(&L, i, e)的实现：首先分析首先分析:插入元素时，线性表的逻辑结构逻辑结构发生什么变化发生什么变化？ (a1, , ai-1, ai, , an) 改变为 (a1, , ai-1, e, ai , , an)a1 a2 ai-1 ai an a1 a2 ai-1 ai ean, 表的长度增加 Status ListInsert_Sq(SqList &L, int i, ElemType e) / 在顺序表L的第 i 个

30、元素之前插入新的元素e, / i 的合法范围为 1iL.length+1 / ListInsert_Sq 算法算法时间复杂度时间复杂度为为: :O( ListLength(L) )q = &(L.elemi-1); / q 指示插入位置指示插入位置for (p = &(L.elemL.length-1); p = q; -p) *(p+1) = *p; / 插入位置及之后的元素右移插入位置及之后的元素右移*q = e; / 插入插入e+L.length; / 表长增表长增1return OK;if (L.length = L.listsize) / 当前存储空间已满，增加分配

31、newbase = (ElemType *)realloc(L.elem, (L.listsize+LISTINCREMENT)*sizeof (ElemType); if (!newbase) exit(OVERFLOW); / 存储分配失败 L.elem = newbase; / 新基址 L.listsize += LISTINCREMENT; / 增加存储容量if (i L.length+1) return ERROR; / 插入位置不合法考虑移动元素的平均情况考虑移动元素的平均情况: : 假设在第 i 个元素之前插入的概率为 ， 则在长度为n 的线性表中插入一个元素所需移插入一个元素所

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

33、Delete(&L, i, &e)的实现的实现：首先分析：首先分析：删除元素时，删除元素时，线性表的逻辑结构发生什么变化？线性表的逻辑结构发生什么变化？ (a1, , ai-1, ai, ai+1, , an) 改变为 (a1, , ai-1, ai+1, , an)ai+1an, 表的长度减少a1 a2 ai-1 ai ai+1 ana1 a2 ai-1 Status ListDelete_Sq (SqList &L, int i, ElemType &e) / ListDelete_Sqfor (+p; p = q; +p) *(p-1) = *p; / 被

34、删除元素之后的元素左移被删除元素之后的元素左移-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; / 删除位置不合法删除位置不合法考虑移动元素的平均情况考虑移动元素的平均情况: : 假设删除第 i 个元素的概率为 , 则在长度为n

35、 的线性表中删除一个元素所需移动元素次数的移动元素次数的期望值期望值为：iqniidlinqE1)(nidlinnE1)(121n 若假定在线性表中任何一个位置上进行删除的概率都是相等的，则移动元素的期望值移动元素的期望值为：21 18 30 75 42 56 8721 18 30 75L.length-10pppq8756p = &(L.elemi-1);q = L.elem+L.length-1;for (+p; p data; ai+1 =p -next -dataaiai+1ai+2P三、单链表操作的实现三、单链表操作的实现GetElem(L, i, &e) / 取第取

36、第i i个数据元素个数据元素ListInsert(&L, i, e) /插入数据元素插入数据元素ListDelete(&L, i, e) /删除数据元素删除数据元素ClearList(&L) /重置线性表为空表重置线性表为空表CreateList(&L, n) /生成含生成含n n个数据元素的链表个数据元素的链表L线性表的操作线性表的操作 GetElem(L, i, &e)在单链表中的实现在单链表中的实现:211830754256pppj1 2 3 在单链表中，任何两个元素的存储位置之间没在单链表中，任何两个元素的存储位置之间没有固定的联系，然而每个元素

37、的存储位置都包含在有固定的联系，然而每个元素的存储位置都包含在其直接前趋结点的信息中。在单链表中，取得第其直接前趋结点的信息中。在单链表中，取得第i i个个数据元素必须从头指针出发寻找。数据元素必须从头指针出发寻找。 因此，查找第因此，查找第 i i 个数据元素的基本操个数据元素的基本操作为：作为：移动指针，比较移动指针，比较 j j 和和 i i 。 单链表是一种顺序存取的结构，为找第单链表是一种顺序存取的结构，为找第 i 个数据元素，必须先找到第个数据元素，必须先找到第 i-1 个数据元素。个数据元素。 令指针令指针 p p 始终始终指向指向线性表中第线性表中第 j j 个数个数据元素。据

38、元素。 Status GetElem_L(LinkList L, int i, ElemType &e) / L是带头结点的链表的头指针，以是带头结点的链表的头指针，以 e 返回第返回第 i 个元素个元素 / GetElem_L算法算法时间复杂度时间复杂度为为:O(ListLength(L)p = L-next; j = 1; / p指向第一个结点，指向第一个结点，j为计数器为计数器while (p & jnext; +j; / 顺指针向后查找，直到顺指针向后查找，直到 p 指向第指向第 i 个元素或个元素或 p 为空为空 if ( !p | ji ) return ERROR

39、; / 第第 i 个元素不存在个元素不存在e = p-data; / 取得第取得第 i 个元素个元素return OK;ai-1 线性表的操作线性表的操作 ListInsert(&L, i, e) 在单链表中的实现：在单链表中的实现： 有序对有序对 改变为改变为 和和 eaiai-1 因此，在单链表中第因此，在单链表中第 i 个结点之前进行插个结点之前进行插入的基本操作为入的基本操作为: 找到线性表中第找到线性表中第i-1i-1个结点，然后修改其个结点，然后修改其指向后继的指针。指向后继的指针。 可见，在链表中插入结点只需要修改指可见，在链表中插入结点只需要修改指针。但同时，若要在第针

40、。但同时，若要在第 i 个结点之前插入元个结点之前插入元素，修改的是第素，修改的是第 i-1 个结点的指针。个结点的指针。 Status ListInsert_L(LinkList L, int i, ElemType e) / L 为带头结点的单链表的头指针，本算法为带头结点的单链表的头指针，本算法 / 在链表中第在链表中第i 个结点之前插入新的元素个结点之前插入新的元素 e / LinstInsert_L算法的算法的时间复杂度时间复杂度为为:O(ListLength(L)p = L; j = 0;while (p & j next; +j; / 寻找第寻找第 i-1 个结点个结点i

41、f (!p | j i-1) return ERROR; / i 大于表长或者小于大于表长或者小于1 s = (LinkList) malloc ( sizeof (LNode); / 生成新结点生成新结点s-data = e; s-next = p-next; p-next = s; /插入插入return OK; eai-1aiai-1spC C语言中的两个标准函数：语言中的两个标准函数：mallocmalloc和和freefree 假设假设p p和和q q是是linklistlinklist型的变量，则执行型的变量，则执行p=(linklist)malloc(sizeof(nodep=(

42、linklist)malloc(sizeof(node)的作用是：由的作用是：由系统生成一个系统生成一个nodenode型的结点，同时将该结点的起始型的结点，同时将该结点的起始位置赋给指针变量位置赋给指针变量p;p;执行执行free(q)free(q)的作用是由系统的作用是由系统回收一个回收一个nodenode型的结点，回收后的结点可以备作再型的结点，回收后的结点可以备作再次生成结点时用次生成结点时用。 因此，单链表是一种动态结构，整个可用存储因此，单链表是一种动态结构，整个可用存储空间可为多个链表共同享用，每个链表占用的空间空间可为多个链表共同享用，每个链表占用的空间不需预先分配划定，而是可

43、以由系统应需求即时生不需预先分配划定，而是可以由系统应需求即时生成。建立线性表的链式存储结构的过程就是一个动成。建立线性表的链式存储结构的过程就是一个动态生成链表的过程。即从空表的初始状态起，依次态生成链表的过程。即从空表的初始状态起，依次建立各元素结点，并逐个插入链表。建立各元素结点，并逐个插入链表。线性表的操作线性表的操作 ListDelete (&L, i, &e)在链表中的实现在链表中的实现:有序对有序对 和和 改变为改变为 ai-1aiai+1ai-1 在单链表中删除第删除第 i i 个结点个结点的基本基本操作操作为:找到线性表中第找到线性表中第i-1i-1个结点，修

44、个结点，修改其指向后继的指针。改其指向后继的指针。ai-1aiai+1ai-1q = p-next; p-next = q-next; e = q-data; free(q);pq Status ListDelete_L(LinkList L, int i, ElemType &e) / 删除以删除以 L L 为头指针为头指针( (带头结点带头结点) )的单链表中第的单链表中第 i i 个结点个结点 / ListDelete_L算法的算法的时间复杂度时间复杂度为为:O(ListLength(L)p = L; j = 0;while (p-next & j next; +j; /

45、寻找第寻找第 i i 个结点，并令个结点，并令 p p 指向其前趋指向其前趋if (!(p-next) | j i-1) return ERROR; / 删除位置不合理删除位置不合理q = p-next; p-next = q-next; / 删除并释放结点删除并释放结点e = q-data; free(q);return OK;操作操作 ClearList(&L) 在链表中的实现在链表中的实现:void ClearList(&L) / 将单链表重新置为一个空表将单链表重新置为一个空表 while (L-next) p=L-next; L-next=p-next; / Clea

46、rListfree(p);算法算法时间复杂度时间复杂度：O(ListLength(L)头结点头结点 a1 a2 . an Lp如何构造单链表？如何构造单链表？ 链表是一个动态的结构，它不需要预分链表是一个动态的结构，它不需要预分配空间，因此配空间，因此生成链表的过程生成链表的过程是一个结点是一个结点“逐个插入逐个插入” ” 的过程。的过程。例如：逆位序输入例如：逆位序输入 n n 个数据元素的值，建立个数据元素的值，建立 带头结点的单链表。带头结点的单链表。操作步骤：操作步骤：一、建立一个一、建立一个“空表空表”；二、输入数据元素二、输入数据元素an，建立，建立 结点并插入；结点并插入；三、输

47、入数据元素三、输入数据元素an-1，建立，建立 结点并插入；结点并插入；ananan-1四、依次类推，直至输入四、依次类推，直至输入a a1 1为止。为止。void CreateList_L(LinkList &L, int n) / 逆序输入逆序输入 n n 个数据元素，建立带头结点的单链表个数据元素，建立带头结点的单链表 / CreateList_L算法的算法的时间复杂度时间复杂度为为:O(Listlength(L)L = (LinkList) malloc (sizeof (LNode);L-next = NULL; /先建立一个带头结点的单链表先建立一个带头结点的单链表for

48、(i = n; i 0; -i) p = (LinkList) malloc (sizeof (LNode); scanf(&p-data); /输入元素值输入元素值 p-next = L-next; L-next = p; /插入插入 回顾回顾 2.1 节中几个例子的算节中几个例子的算法，看一下当线性表分别以链表法，看一下当线性表分别以链表存储结构表示时，它们的实现算存储结构表示时，它们的实现算法的时间复杂度为多少？法的时间复杂度为多少？void union(List &La, List Lb) La_len = ListLength(La); Lb_len =ListLen

49、gth(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) ) 当以链式映像实现抽象数据类型线性表时为: O( ListLength(La)ListLength(Lb) )例例2

50、-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 / purge控制结构：控制结构：基本操作：基本操作：for 循环循环GetElem 和 ListInsert当以顺序映像实现抽

51、象数据类型线性表时为: O( ListLength(Lb) )当以链式映像实现抽象数据类型线性表时为: O( ListLength2(Lb) )例例2-2算法时间复杂度算法时间复杂度void MergeList(List La, List Lb, List &Lc) InitList(Lc); i = j = 1; k = 0; La_len = ListLength(La); Lb_len = ListLength(Lb); while (i = La_len) & (j = Lb_len) GetElem(La, i, ai); GetElem(Lb, j, bj); if

52、 (ai next = L.current-next; L.current-next = s; if (L.tail = L.current) L.tail = s; L.current = s; return OK;Status DelAfter( LinkList& L, ElemType& e ) /若当前指针及其后继在链表中，则删除线性链表若当前指针及其后继在链表中，则删除线性链表L L中当前中当前 /指针所指结点之后的结点，并返回指针所指结点之后的结点，并返回OK; OK; 否则返回否则返回ERRORERROR。 /DelAfterif ( !(L.current &

53、amp; L.current-next ) ) return ERROR;q = L.current-next;L.current-next = q-next;if (L.tail = q) L.tail = L.current; /被删结点恰为尾结点被删结点恰为尾结点e=q-data; FreeNode(q);return OK;例一例一Status ListInsert_L(LinkList L, int i, ElemType e) /在带头结点的单链线性表在带头结点的单链线性表L L的第的第i i个元素之前插入元素个元素之前插入元素e e / ListInsert_L 利用上述定义的线

54、性链表如何完利用上述定义的线性链表如何完成线性表的其它操作成线性表的其它操作 ？if (!LocatePos (L, i-1) return ERROR; /i i值不合法，第值不合法，第i-1i-1个结点不存在个结点不存在if (InsAfter (L, e) return OK; /完成插入完成插入else return ERROR;Status MergeList_L(LinkList &Lc, LinkList &La, LinkList &Lb ， int (*compare) (ElemType,ElemType) /归并有序表归并有序表 La La 和和

55、Lb ,Lb ,生成新的有序表生成新的有序表 LcLc, , /并在归并之后销毁并在归并之后销毁La La 和和 Lb,Lb, /compare compare 为指定的元素大小判定函数为指定的元素大小判定函数 / MergeList_L例二例二if ( !InitList(Lc) return ERROR; /存储空间分配失败存储空间分配失败while (!( a=MAXC & b=MAXC) / LaLa或或LbLb非空非空 LocatePos (La, 0); LocatePos (Lb, 0 ) ; /当前指针指向头结点当前指针指向头结点if ( DelAfter( La, e

56、) a = e; / 取得取得LaLa表中第一个元素表中第一个元素a a else a = MAXC; / MAXCMAXC为常量最大值为常量最大值if ( DelAfter( Lb, e) b = e; / 取得取得LbLb表中第一个元素表中第一个元素b b else b = MAXC; / a a和和b b为两表中当前比较元素为两表中当前比较元素DestroyList(La); DestroyList(Lb); / 销毁链表销毁链表 La La 和和 LbLbreturn OK; if (*compare)(a, b) next = p-next; p-next = s;s-next-pr

57、ior = s; s-prior = p;psai-1ai插入插入ai-1删除删除aiai+1p-next = p-next-next;p-next-prior = p;pai-1这里有什么问题吗？q=p-next;free(q);3.双向循环链表双向循环链表空表空表非空表非空表 a1 a2 . an六、有序表类型六、有序表类型ADT Ordered_List 数据对象数据对象: S = xi|xi OrderedSet ， i=1,2,n, n0 集合中集合中任意两个任意两个元素之间元素之间均可以均可以进行比较进行比较数据关系数据关系: :R = | xi-1, xi S, xi-1 xi,

58、 i=2,3,n 回顾例回顾例2-2的两个算法的两个算法 LocateElem( L, e, &q, int(*compare)(ElemType,ElemType) ) 初始条件初始条件：有序表有序表L已存在。已存在。 操作结果操作结果：若有序表若有序表L中存在元素中存在元素e e，则，则q指示指示L中中 第一个值为第一个值为e 的元素的位置的元素的位置，并返回函，并返回函 数值数值TRUE；否则；否则q 指示第一个大于指示第一个大于e 的元素的前驱的位置的元素的前驱的位置，并返回函数值，并返回函数值 FALSE。 基本操作：基本操作： Compare是一个是一个有序判定函数有序判定

59、函数( 12, 23, 34, 45, 56, 67, 78, 89, 98, 45 )例如例如:若若 e = 45, 则则 q 指向指向 若若 e = 88, 则则 q 指向指向表示值为表示值为 88 的元素应插入的元素应插入在该指针所指结点之后。在该指针所指结点之后。void union(List &La, List Lb) / Lb 为线性表为线性表 InitList(La); / 构造构造(空的空的)线性表线性表LA La_len=ListLength(La); Lb_len=ListLength(Lb); for (i = 1; i = Lb_len; i+) GetElem

60、(Lb, i, e); / 取取Lb中第中第 i 个数据元素赋给个数据元素赋给 e if (!LocateElem(La, e, equal( ) ) ListInsert(La, +La_len, e); / La中不存在和中不存在和 e 相同的数据元素，则插入之相同的数据元素，则插入之 / for / union算法时间复杂度：算法时间复杂度：O(n2)void purge(List &La, List Lb) / Lb为有序表为有序表 InitList(LA); La_len = ListLength(La); Lb_len =ListLength(Lb); / 求线性表的长度求线性表的长度 for (i = 1; i = Lb_len; i+) / purge GetElem(Lb, i, e); / 取取Lb中第中第i个数据元素赋给个数据元素赋给 eif (ListEmpty(La) | !equal (en, e) ListInsert(La, +La_len, e); en = e; / La中不存在和中不存在和 e 相同的数据元素，则插入之相同的数据元素，则插入之算法时间复杂度：算法时间复杂度：O(n)小结小结: 链式存储结构的优缺点链式存储结构的优缺点 插入和删除运算时，无须移动表中元素的位