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

1、BUPT课堂练习for(i=2;i=n;+i) for(j=2;j=i-1;+j) ai，j=1; i = 2，3 n执行次数 = 0，1, n-2频度 =0+1+n-2 =(n-2)(n-2+1)/2=n2/2-3n/2+1T(n)=O(n2)BUPTfor(i=3;i=n;+i) for(j=2;j=0)个数据元素的有限序列，通常记为： (a1，a2， ai-1，ai，ai+1，an) 其中n为表长， n0 时称为空表。BUPT . . . 86 84 70李四880004 99 90 95张三880003 90 85 80马二880002 95 85 90丁一880001 英语物理数学姓

2、名学号BUPT线性表的类型定义BUPT抽象数据类型线性表的定义o ADT List o 数据对象： n Dai | ai ElemSet, i=1,2,.,n, n0 o 数据关系：n R1 | ai D, i=2,.,n n 序偶，即有序对，可以看作是具有两个元素的集合。但它与一般集合不同的是序偶具有确定的次序。 BUPT抽象数据类型线性表的定义o 基本操作：n 结构初始化InitList(*L)操作结果：构造一个空的线性表 Ln 销毁结构DestroyList(*L)初始条件：线性表 L 已存在操作结果：销毁线性表 L可分为四类可分为四类结构初始化、销毁结构结构初始化、销毁结构引用型操作、

3、加工型操作引用型操作、加工型操作BUPT参数传递o 值传递o 指针传递o 引用传递BUPTSwap(int a, int b)int temp;temp =a;a=b;b=temp;Main()int x,y;Swap(x,y);BUPTSwap(int *a, int *b)int temp;temp =*a;*a=*b;*b=temp;Main()int x,y;Swap(&x,&y);BUPTSwap(int *a, int *b)int *temp;temp =a;a=b;b=temp;Main()int x,y;Swap(&x,&y);BUPTSwap

4、(int &a, int &b)int temp;temp =a;a=b;b=temp;Main()int x,y;Swap(x,y);BUPTSwap(const int &a, const int &b)int temp;temp =a;a=b;b=temp;Main()int x,y;Swap(x,y);BUPT抽象数据类型线性表的定义n 引用型操作（6个）ListEmpty( L )初始条件：线性表L已存在操作结果：若 L 为空表，则返回 TRUE，否则返回 FALSEListLength( L )初始条件：线性表 L 已存在操作结果：返回 L 中元素个

5、数BUPT抽象数据类型线性表的定义n 引用型操作（续）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 无定义BUPT抽象数据类型线性表的定义n 引用型操作（续）GetElem( L, i, *e )初始条件：线性表 L 已存在1iLengthList(L

6、)。操作结果：用 e 返回 L 中第 i 个元素的值。LocateElem( L, e)初始条件：线性表 L 已存在。操作结果：返回 L 中与 e 相等的元素的序号。若这样的元素不存在，则返回值为0。BUPT抽象数据类型线性表的定义n 加工型操作加工型操作ClearList( *L )初始条件：线性表 L 已存在。操作结果：将 L 重置为空表。BUPT抽象数据类型线性表的定义n加工型操作加工型操作ListInsert( *L, i, e )初始条件：线性表 L 已存在，1iLengthList(L)+1。操作结果：在 L 的第 i 个元素之前插入新的元素 e，L 的长度增1。ListDelet

7、e( *L, i, *e )初始条件：线性表 L 已存在且非空，1iLengthList(L)。操作结果：删除删除 L 的第 i 个元素，并用 e 返回其值，L 的长度减长度减1。 ADT ListBUPT抽象数据类型线性表的定义o例例2-1 已知集合 A 和 B，求两个集合的并集，使 AAB，且 B 不再单独存在。思路：对集合 B 中的所有元素一一检查，看看在集合 A 中是否存在相同元素，若不存在，则将该元素插入到集合 A，否则舍弃之。要在计算机中求解，首先要确定要在计算机中求解，首先要确定“如何表示集合如何表示集合”。集合。集合可以有多种表示方法，对上述集合求并的问题可以用线性表表可以有多

8、种表示方法，对上述集合求并的问题可以用线性表表示集合。示集合。现假设以线性表 LA 和 LB 分别表示集合 A 和 B，即构造两个线性表 LA 和 LB，它们的数据元素分别为集合 A 和 B 中的成员。上述集合求并的问题演绎为：要求对线性表作如下操作：扩大线性表 LA，将存在于线性表存在于线性表 LB 中中而不存在于线性表不存在于线性表 LA 中中的数据元素插入到线性表插入到线性表 LA 中中去。BUPT抽象数据类型线性表的定义具体操作步骤为：1从线性表 LB 中取出一个数据元素；2依值在线性表 LA 中进行查询；3若不存在，则将它插入到 LA 中。重复上述三步直至 LB 为空表止。对应四个基

9、本操作对应四个基本操作1. ListDelete( LB, 1, e );2. LocateElem( LA, e);3. ListInsert( LA, n+1,e )4. DestroyList( LB )BUPT抽象数据类型线性表的定义void union(List *LA, List *LB)/ 将所有在线性表将所有在线性表LB中但不在中但不在LA中的数据元素插入到中的数据元素插入到 LA 中中,/ 算法执行之后，线性表算法执行之后，线性表 LB 不再存在。不再存在。 La_len = ListLength(LA);/ 求得线性表 LA 的长度while (!ListEmpty(LB)

10、 / 依次处理 LB 中元素直至 LB 为空表止 ListDelete(LB,1,e);/ LB 删除第1个数据元素并赋给 e if (!LocateElem(LA,e) ListInsert(LA,+La_len,e);/ 当LA中不存在和 e 值相同的数据元素时进行插入 / whileDestroyList(LB);/ 销毁线性表 LB / unionBUPTMain()List a1,a2;/初始化a1，a2；Union(a1,a2);BUPT线性表的顺序存储表示和实现o 顺序表：顺序表： “用一组地址连续地址连续的存储单元依依次存放次存放线性表中的数据元素”，即以“存储存储位置相邻位置

11、相邻”表示“位序相继的两个数据元素之间的前驱和后继的关系(有序对)”，并以表中第一个元素的存储位置作为线性表的起始地址，称作线性表的基地址线性表的基地址。BUPTABCD0 x00010 x00020 x00030 x00040 x0005(A, B, C, D,)BUPT线性表的顺序存储表示和实现o LOC(ai ) = LOC(ai-1 ) + Cn 其中，C是一个数据元素所占存储量o LOC(ai ) = LOC(a1 ) + (i-1)C 基地址基地址BUPT线性表的顺序存储表示和实现o 用C语言描述的顺序表类型顺序表类型如下所示：o/ 存储结构存储结构const int MAXLIS

12、TSIZE=80; / 预设的存储 空间最大容量typedef struct ElemType *elem;/ 存储空间基址 int length; / 当前长度 int listsize;/ 允许的最大存储容量 SqList; / 俗称 顺序表顺序表BUPT线性表的顺序存储表示和实现o 五个操作的实现n 一、初始化操作一、初始化操作n 二、元素定位操作二、元素定位操作n 三、插入元素操作三、插入元素操作n 四、删除元素操作四、删除元素操作n 五、销毁结构操作五、销毁结构操作BUPT线性表的顺序存储表示和实现o 初始化操作n 对顺序表而言，“初始化”的实质是为它分配一个“足够应用”的元素存储空

13、间。BUPT线性表的顺序存储表示和实现void InitList(SqList *L, int maxsize) / 构造一个空的线性表构造一个空的线性表 Lif ( maxsize = 0 ) maxsize = MAXLISTSIZE; L.elem = (ElemType*)malloc(maxsize*sizeof(ElemType); if (!L.elem) exit(1); / 存储分配失败L.length = 0;/ 顺序表的初始长度为0L.listsize = maxsize; / 该顺序表可以存储元素的最大容量 / InitList此算法的时间复杂度为O (1)。BUPT线

14、性表的顺序存储表示和实现o 元素定位操作n 在顺序表中“查询”是否存在一个和给定值满足判定条件的元素的最简单的办法是，依次取依次取出结构中的每个元素和给定值进行比较出结构中的每个元素和给定值进行比较。BUPT线性表的顺序存储表示和实现oint LocateElem(SqList L, ElemType e)/ 在顺序表在顺序表L中查找第中查找第1个值与个值与 e 满足相等条件的元素满足相等条件的元素/ 若找到，则返回其在若找到，则返回其在 L 中的位序，否则返回中的位序，否则返回0。i = 1;/ i 的初值为第1元素的位序p = L.elem; / p 的初值为第1元素的存储位置while

15、(i = L.length & !equal(*p+,e)+i; / 依次进行判定if (i = L.length) return i; / 找到满足判定条件的数据元素为第 i 个元素else return 0;/ 该线性表中不存在满足判定的数据元素 / LocateElem BUPT线性表的顺序存储表示和实现o 插入元素操作n “插入元素”使线性表的逻辑结构发生什么变化？n 假设在线性表的第i个元素之前插入一个元素e，使得线性表( a1, , ai-1 , ai , , an ) 改变为 (a1, , ai-1 , e, ai , , )o (1) 改变了表中元素之间的关系,使 改变

16、为和 o (2) 表长增1.BUPT线性表的顺序存储表示和实现obool ListInsert(SqList *L, int pos, ElemType e)/ 若存储空间不满且若存储空间不满且1posListlength(L)+1，则在顺序表，则在顺序表 L / 第第 pos 个元素之前插入个元素之前插入e 且返回且返回TRUE，否则返回，否则返回FALSEif (pos L.length+1) return FALSE ; / 插入位置不合法if (L.length = L.listsize) return FALSE;/ 当前存储空间已满，无法插入for (j=L.length-1; j

17、=pos-1; -j)L.elemj+1 = L.elemj; / 插入位置及之后元素右移L.elempos-1 = e; / 插入 e+L.length; / 表长增1return TRUE; / ListInserto时间复杂度为：O (ListLength(L)BUPTa1a2ai-1aiai+1ana1a2ai-1xaiai+1an01i-2i-1in-1n插入前插入后BUPT线性表的顺序存储表示和实现o 删除元素操作n “删除元素”使线性表的逻辑结构发生什么变化？n 假设删除线性表中第i个元素，使得线性表(a1, , ai-1 , ai , ai+1 , an ) 改变为 (a1,

18、, ai-1 , ai+1 , , an )o (1) 改变了表中元素之间的关系，使和 改变为o (2) 表长减1BUPT线性表的顺序存储表示和实现obool ListDelete(SqList *L, int pos, ElemType *e)/ 若若1posListlength(L)，以，以 e 带回从带回从L 中删除的中删除的/ 第第 pos 个元素且返回个元素且返回 TRUE，否则返回，否则返回 FALSEif (pos L.length)return FALSE ; / 删除位置不合法for (j = pos; jL.length; +j) L.elemj-1 = L.elemj;

19、/ 被删除元素之后的元素左移 -L.length; / 表长减1return TRUE; / ListDelete o时间复杂度为：O (ListLength(L)BUPT线性表的顺序存储表示和实现o 销毁结构操作o void DestroyList( SqList *L )/ 释放顺序表释放顺序表 L 所占存储空间所占存储空间free(L.elem);L.listsize = 0;L.length = 0; / DestroyList_Sqo 时间复杂度为：O (1)BUPT线性表的顺序存储表示和实现o 插入和删除操作的性能分析n 在顺序表中任何一个合法位置上进行一次插入或删除操作时，需要移

20、动的元素个数的平均值是多少？BUPT线性表的顺序存储表示和实现o 插入操作插入操作o Ein(n)表示在长度为 n 的顺序表中进行一次插入操作时所需进行“移动”元素个数的期望值（即平均移动个数平均移动个数），o 顺序表上的插入运算，时间主要消耗在了数据的移动上，在第i个位置上插入 x ，从 ai 到 an 都要向下移动一个位置，共需要移动 ni1个元素，而 i 的取值范围为 ：1= idata = p-next = p = p-next;p-data = p-next = p = p-next;p-data = p-next =A0 x0255B0 x0283C0 x03110 x02010

21、x02550 x0283A;0 x0255; =0 x0255B;0 x0283; =0 x0283C;0 x0311;BUPT线性表的链式存储表示和实现o 五个基本操作n 初始化操作 n 销毁结构操作 n 存取元素操作 n 插入元素操作 n 删除元素操作BUPTtypedef LNode * Linklist;BUPT线性表的链式存储表示和实现o 初始化操作初始化操作n 空链表的头指针是否为NULL?o 若链表不带头结点，则以头指针L=NULL表示空表。o 在带头结点的情况下，则需建立一个其指针域的指针为NULL的头结点，并令头指针指向该结点。 BUPT线性表的链式存储表示和实现void I

22、nitList(Linklist L)/ 创建带头结点的空链表创建带头结点的空链表,L 为指向头结点的指针为指向头结点的指针L = LNode* malloc(sizeof(LNode);if (!L) exit(1); / 存储空间分配失败L-next = NULL; / InitList o 时间复杂度为O (1)BUPT线性表的链式存储表示和实现o销毁结构操作 ovoid DestroyList(Linklist L)/ 销毁以销毁以L为头指针的单链表，释放链表中所有结点空间为头指针的单链表，释放链表中所有结点空间while (L) p = L; L = L-next; free(p);

23、 / whileL = NULL; / DestroyListo算法的时间复杂度为O (Listlength(L)BUPT链表的遍历：status roam( Linklist L ) LNode *p = L; while( p ) p = p-next; return OK;typedef LNode * Linklist; a1anLa2.BUPT求表长int Length( Linklist L ) LNode * p = L; count=0; while (p ) count+; p = p-next; return count;a1anLa2pBUPT按值查找：LNode * L

24、ocateElem( Linklist L, Elemtype e ) /*在单链表L中查找值为e的结点，找到后返回其指针*/ LNode * p=L; while ( p-data != e ) p=p-next; return p; a1anLa2pBUPT线性表的链式存储表示和实现o 存取元素操作n 为取第 i 元素，首先必须先找到第 i-1 个元素。因此不论 i 值为多少，都必须从头结点开始起从头结点开始起“点数点数”，直数到第 i 个为止。BUPT线性表的链式存储表示和实现obool GetElem ( Linklist L, int pos, ElemType *e )/ 若若1p

25、osLengthList(L)，则用，则用 e 带回指针带回指针L指向头结点指向头结点的单链表中第的单链表中第 pos 个元素的值且返回函数值为个元素的值且返回函数值为TRUE,否则返回否则返回函数值为函数值为FALSEp = L-next; j =1; / 变量初始化，p 指向第一个结点while ( p & jnext; +j; / whileif ( !p) return FALSE; o / 链表中不存在第 pos 个结点e = p-data; / 取到第 pos 个元素return TRUE; / GetElem o算法的时间复杂度为O (ListLength(L)。BUPT

26、线性表的链式存储表示和实现o 插入元素操作n 在线性表中“插入”一个元素e时，使元素之间的关系改变为和。n 当用指针指示后继元素时，实现这种关系的改变就很容易了，只要修改相应指针即可只要修改相应指针即可。n 基本思想：找到第i-1个结点，然后修改指针: S-nextp-next；p-next=s； xypbs插入前xbysp插入后BUPTps在*p之后插入*sBUPT在*p之后插入*ss-next=p-next;psBUPT在*p之后插入*ss-next=p-next;p-next=s;psBUPT线性表的链式存储表示和实现bool ListInsert (Linklist L, int po

27、s, ElemType e )/ 若若1posLengthList(L)+1，则指针，则指针L指向头结点的单链指向头结点的单链的第的第 pos 个元素之前插入新的元素个元素之前插入新的元素 e，且返回函数值为，且返回函数值为 TRUE,否则不进行插入且返回函数值为否则不进行插入且返回函数值为 FALSEp=L; j=0;while(p & jnext; +j; / whileif(!p|jpos-1)return FALSE; / 参数不合法，pos 表长+1s=LNode* malloc(sizeof(LNode);if (!s) exit(1); / 存储空间分配失败s-data=

28、e; / 创建新元素的结点s-next=p- next; p-next=s; / 修改指针return TRUE; / ListInsert BUPT线性表的链式存储表示和实现o 删除元素操作n 和插入类似，由于删除元素ai改变了元素之间的关系，使ai+1不再是ai的后继，而是ai-1的后继.n 因此需要修改ai-1元素所在结点的指针。n 算法基本思想：首先找到第 i-1 个结点，然后修改相应指针。修改指针：修改指针：p-nextp-next -next ；pp删除前删除后BUPT删除*qqpBUPT删除*qqp p-next=q-next;BUPT删除*qqp p-next=q-next;

29、free(q);BUPT删除*qp p-next=q-next; free(q);BUPT线性表的链式存储表示和实现obool ListDelete (Linklist *L, int pos, ElemType *e)/ 若若1posLengthList(L)，则删除指针，则删除指针L指向头结点的单链表指向头结点的单链表中第中第 pos 个元素并以个元素并以 e 带回其值，返回函数值为带回其值，返回函数值为 TRUE，否则，否则不进行删除操作且返回函数值为不进行删除操作且返回函数值为 FALSEp = L; j = 0;while (p-next & j next; +j;if (!

30、(p-next) | j pos-1)return FALSE; / 删除位置不合理q = p-next; p-next = q-next;/ 修改指针e = q-data; free(q);/ 释放结点空间 return TRUE; / ListDelete_LBUPT线性表的链式存储表示和实现o 例例 逆序创建链表n假设线性表( a1 ，a2 ， an )的数据元素存储在一维数组 An中，则从数组的最后一个分量起，依次生成结点，并逐个插入到一个初始为“空”的链表中。n解题分析：解题分析：由于链表是一种动态存储管理的结构，链表中每个结点占用的存储空间不需预先分配划定，而是在运行时刻由系统应需

31、求即时生成，因此，建立链表的过程是一个动态生成的过程。即从即从 “空表空表”起，依次建立起，依次建立结点，并逐个插入链表。所谓结点，并逐个插入链表。所谓“逆序逆序”创建链表指的是，创建链表指的是，依和线性表的逻辑顺序相依和线性表的逻辑顺序相“逆逆”的次序输入元素的次序输入元素BUPT线性表的链式存储表示和实现ovoid CreateList_L(Linklist L, int n, ElemType A) / 已知数组已知数组 A 中存有线性表的中存有线性表的 n 个数据元素，个数据元素，/ 逆序建立带头结点的单链表。逆序建立带头结点的单链表。L =Linklist malloc(sizeof

32、(LNode);if (!L) exit(1); / 存储空间分配失败L-next = NULL;/ 先建立带头结点的空的单链表for (i = n; i 0; -i) p = Linklist malloc(sizeof(LNode);if (!p) exit(1); / 存储空间分配失败 p-data = Ai-1; / 赋元素值 p-next = L-next; L-next = p; / 插入在头结点之后 / for / CreateList_L o算法的时间复杂度为O (ListLength(L)。BUPT线性表的链式存储表示和实现o 例例 以链表作存储结构将线性表 ( a1 , a

33、2, am , b1 , b2 , bn ) 改变成 (b1,b2, bn , a1 , a2 , am ) 。n解题分析：解题分析：因为对链表来说，“插入”和“删除”仅需修改指针即可完成，且由于前 m 个元素之间和后 n 个元素之间的链接关系分别都不需要改变，则算法的实际操作为： (1) 从链表中删除从链表中删除(a1 , a2, am )；(2) 将将(b1 , b2 , bn )链接到头结点之后；链接到头结点之后；(3) 将将(a1 , a2, am )链接到链接到bn之后。之后。BUPTo 删除单链表删除单链表L中的冗余元素，即使操作之后的中的冗余元素，即使操作之后的单链表中只保留操作

34、之前表中所有值都不相同单链表中只保留操作之前表中所有值都不相同的元素的元素BUPT线性表的链式存储表示和实现ovoid purge_L(Linklist L )/ 删除单链表删除单链表L中的冗余元素，即使操作之后的单链表中只保留操中的冗余元素，即使操作之后的单链表中只保留操作之前表中所有值都不相同的元素作之前表中所有值都不相同的元素 p = L-next;L-next = NULL;/ 设新表为空表while ( p ) / 顺序考察原表中每个元素succ = p-next;/ 记下结点 *p 的后继q = L-next; / q 指向新表的第一个结点while( q & p-data

35、!=q-data ) q = q-next; / 在新表中查询是否存在和p-data相同的元素if ( !q ) / 将结点 *p 插入到新的表中p-next = L-next;L-next = p;else free(p);/ 释放结点 *pp = succ; / for / purge_LBUPT线性表的链式存储表示和实现o 单链表的优势n (1) 能有效利用存储空间；逻辑上相邻的元素，逻辑上相邻的元素，物理位置不一定需要相邻；物理位置不一定需要相邻； 元素之间的邻接关元素之间的邻接关系由指针域指示。链表是一种动态存储结构；系由指针域指示。链表是一种动态存储结构； 链表的结点可调用链表的结

36、点可调用malloc()申请申请和和free()释放。释放。n (2) 用“指针”指示数据元素之间的后继关系，便于进行“插入”、“删除”等操作；BUPT线性表的链式存储表示和实现o 单链表的劣势n 不能随机存取数据元素n 线性表的“表长”和数据元素在线性表中的“位序”，在单链表中都看不见了。n 不便于在表尾插入元素，需遍历整个表才能找到插入的位置。BUPT双向链表o 双向链表由指向头结点的头指针唯一确定，若将头尾结点链接起来则构成双向循环链表。o p-prior-next = p p-next-prior = pBUPT双向链表o 双向链表双向链表：其结点结构中含有两个两个指针域，其一指向数据

37、元素的其一指向数据元素的直接后继直接后继，另一指向，另一指向数据元素的数据元素的直接前驱直接前驱“o typedef struct DuLNode ElemType data;struct DuLNode *prior;struct DuLNode *next; DuLNode, *DuLink;BUPT双向链表o 在双向链表上进行操作基本上和单向链表相同，例如，查找结点也是要从头指针指示的头结点开始。o 插入和删除时必须同时修改两个方向上的指插入和删除时必须同时修改两个方向上的指针。针。BUPT双向链表o 插入操作void ListInsert_DuL(DuLink &L, DuLNode* p, DuLNode* s ) / 在带头结点的双向循环链表在带头结点的双向循环链表 L 中结点中结点 *p 之后插入结点之后插入结点 *ss-next = p-next; p-next = s;s-next-prior = s; s-prior = p;/ ListInsert_DuLbxas插入前bxas插入后ppBUPT双向链表o 删除操作void ListDelete_D