《数据结构》课件第2章 线性表

1、第2章 线性表学习要点: 了解线性表的逻辑结构特性熟练掌握线性表的顺序存储结构和链式存储结构的描述方法熟练掌握线性表在这两种存储结构上实现的基本操作查找、插入和删除能够从时间和空间复杂度的角度综合比较线性表的两种存储结构的不同特点及其适用场合线性表是一种最简单的线性结构。 线性结构 是 一个数据元素的有序(次序)关系存在唯一的一个“第一个”的数据元素；存在唯一的一个“最后一个”的数据元素；除第一个数据元素外，均有唯一的前驱；除最后一个数据元素外，均有唯一的后继。2.1 线性表的类型定义线性表是最常用而且最简单的一种数据结构。定义：线性表是n个数据元素的有限序列。记为：(a1, ., ai-1,

2、 ai, ai+1, ., an)26个字母表：(A，B，C，Z)是一个线性表例如：某校近4年计算机拥有量：(120，340，510，720)记录文件特征：元素个数n表长度；n=0空表1in时ai的直接前驱是ai-1，a1无直接前驱ai的直接后继是ai+1，an无直接后继元素同构，且不能出现缺项抽象数据类型线性表的定义如下：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)

3、, 称 i 为 ai 在线性表中的位序。 基本操作： 结构初始化操作结构销毁操作 引用型操作 加工型操作 ADT List初始化操作： InitList( &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( ) )ListTraverse(L, visit( )DestroyList( &L )初始条件：操作结果：线

4、性表 L 已存在。销毁线性表 L。加工型操作：ClearList( &L )PutElem( &L, i, e )改变数据元素的值初始条件：线性表 L 已存在，且 1iLengthList(L)操作结果：L 中第 i 个元素赋值为 e 。ListInsert( &L, i, e )ListDelete(&L, i, &e)例2-1:假设:有两个集合A 和 B 分别用两个线性表 LA 和 LB 表示，即：线性表中的数据元素即为集合中的成员。现要求一个新的集合A=AB。 GetElem(Lb, i, e); / 取Lb中第i个数据元素赋给e if (!LocateElem(La, e, equal

5、( ) ) 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) 分析：操作步骤：从线性表 LB 中依次取出每个数据元素;依值在线性表 LA 中进行查访;若不存在，则插入之。GetElem(LB, i)e LocateElem(LA, e, equal( ) ListInsert(LA,

6、 n+1, e)( n 表示线性表 LA 当前长度)例2-2:已知一个非纯集合B，试构造一个纯集合 A，使A中只包含B中所有值各不相同的数据元素。分析：算法的策略应该和例2-1基本相同,差别仅在于集合 A 的初始状态是“空集”。集合 B集合 Avoid 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_le

7、n, e); / La中不存在和 e 相同的数据元素，则插入之for (i = 1; i = Lb_len; i+) InitList(La); / 构造(空的)线性表LA思考：改变结构，以有序表表示集合。则算法有什么不同？例如：集合B: (2，3，3，5，6，6，6，8，12)对构造集合 A 而言，数据元素两两不同，且依值从小至大的顺序插入。void purge(List &La, List Lb) InitList(LA); La_len = ListLength(La); Lb_len =ListLength(Lb); / 求线性表的长度 for (i = 1; i = Lb_len;

8、i+) / purgeGetElem(Lb, i, e); / 取Lb中第i个数据元素赋给 eif ( ) ListInsert(La, +La_len, e); en = e; /记录刚插入的元素 / La中不存在和 e 相同的数据元素，则插入之ListEmpty(La)|!equal(en, e)例2-3:（P20，例2-2）归并两个“数据元素按值非递减有序排列”的有序表 La 和 Lb，求得有序表 Lc 也具有同样特性。设 La = (a1, , ai, , an), Lb = (b1, , bj, , bm) Lc = (c1, , ck, , cm+n)且已由(a1, , ai-1)

9、和(b1, ,bj-1)归并得 (c1, , ck-1)则k = 1, 2, , m+n基本操作：初始化 Lc 为空表；分别从 La和Lb中取得当前元素 ai 和 bj；若 aibj，则将 ai 插入到 Lc中，否则将bj 插入到 Lc 中；重复2和3两步,直至 La 或 Lb 中元素被取完为止；将 La表或 Lb 表中剩余元素复制插入到Lc表中。/ La 和 Lb 均不空，i = j = 1, k = 0 GetElem(La, i, ai); GetElem(Lb, j, bj); if (ai = bj) / 将 ai 插入到 Lc 中 ListInsert(Lc, +k, ai); +

10、i; else / 将 bj 插入到 Lc 中 ListInsert(Lc, +k, bj); +j; void MergeList(List La, List Lb, List &Lc) / 本算法将非递减的有序表 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(L

11、a);Lb_len = ListLength(Lb); while (i = La_len) / 当La不空时 GetElem(La, i+, ai); ListInsert(Lc, +k, ai); / 插入 La 表中剩余元素 while (j = Lb_len) / 当Lb不空时 GetElem(Lb, j+, bj); ListInsert(Lc, +k, bj); / 插入 Lb 表中剩余元素定义：用一组地址连续的存储单元依次存放线性表中的数据元素。以“存储位置相邻”表示有序对，则有：LOC(ai) = LOC(ai-1) + l 2.2 线性表类型的实现顺序映像 a1 a2 ai-

12、1 ai an线性表的起始地址称作线性表的基地址 LOC(ai) = LOC(a1) + (i-1)l 基地址一个数据元素所占存储量特点：实现逻辑上相邻物理地址相邻实现随机存取实现：可用C语言的一维数组实现typedef struct SqList; / 顺序表#define LIST_INIT_SIZE 80 / 线性表存储空间的初始分配量#define LISTINCREMENT 10 / 线性表存储空间的分配增量ElemType *elem; / 存储空间基址int length; / 当前长度int listsize; / 当前分配的存储容量 / (以sizeof(ElemType)为

13、单位)数组指针线性表的基本操作在顺序表中的实现结构初始化：Status InitList_Sq( SqList& L ) / 构造一个空的线性表 / InitList_Sq算法时间复杂度：O(1)线性阶L.elem = (ElemType*) malloc (LIST_ INIT_SIZEsizeof (ElemType);if (!L.elem) exit(OVERFLOW); /存储分配失败L.length = 0; /空表长度为0L.listsize = LIST_INIT_SIZE; /初始存储容量return OK;查找：例如：有一个顺序表如下23 75 41 38 54 62 17

14、L.elemL.lengthL.listsizee =38pppppi12341850p可见，基本操作是：将顺序表中的元素逐个和给定值 e 相比较。 int LocateElem_Sq(SqList L, ElemType e, Status (*compare)(ElemType, ElemType) / 在顺序表中查询第一个满足判定条件的数据元素， / 若存在，则返回它的位序，否则返回 0 / LocateElem_Sq O( ListLength(L) )算法的时间复杂度为：i = 1; / i 的初值为第 1 元素的位序(注意：不是数组下标值！)p = L.elem; / p 的初值为

15、第 1 元素的存储位置while (i = L.length & !(*compare)(*p+, e) +i;if (i = L.length) return i;else return 0;(*compare)(*p+, e)插入元素：分析：插入元素时，线性表的逻辑结构发生什么变化？ (a1, , ai-1, ai, , an) 改变为 (a1, , ai-1, e, ai, , an)a1 a2 ai-1 ai ana1 a2 ai-1 ai ean, 表的长度增加 Status ListInsert_Sq(SqList &L, int i, ElemType e) / 在顺序表L的第

16、i 个元素之前插入新的元素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;元素右移插入元素算法时间复杂度的进一步讨论：考虑移动元素的平均情况: 假设在第i个元素之前插入的概率为 ，则在长度为n的线性表中插入一个元素所需移动元素次数的期望

17、值为： 若假定在线性表中任何一个位置上进行插入的概率pi都是相等的，则移动元素的期望值为：T(n)=O(n)O( ListLength(L) )if (L.length = L.listsize) / 当前存储空间已满，增加分配 newbase = (ElemType *)realloc(L.elem, (L.listsize+LISTINCREMENT)*sizeof (ElemType); if (!newbase) exit(OVERFLOW); / 存储分配失败 L.elem = newbase; / 新基址 L.listsize += LISTINCREMENT; / 增加存储容量i

18、f (i L.length+1) return ERROR; / 插入位置不合法例如： ListInsert_Sq(L, 5, 66) 21 18 30 75 42 56 8721 18 30 75L.length-10pppq87564266q = &(L.elemi-1); / q 指示插入位置for (p = &(L.elemL.length-1); p = q; -p) *(p+1) = *p;p删除元素：分析：删除元素时，线性表的逻辑结构发生什么变化？ (a1, , ai-1, ai, ai+1, , an) 改变为 (a1, , ai-1, ai+1, , an)ai+1an, 表

19、的长度减少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; / 被删除元素之后的元素左移-L.length; / 表长减1return OK;算法时间复杂度为: O( ListLength(L)p = &(L.elemi-1); / p 为被删除元素的位置e = *p; / 被删除元素的值赋给 eq = L.elem+L.length-1; / 表尾元素的位置if (i L.len

20、gth) return ERROR; / 删除位置不合法元素左移删除元素算法时间复杂度的进一步讨论：考虑移动元素的平均情况: 假设删除第i个元素的概率为 ，则在长度为n的线性表中删除一个元素所需移动元素次数的期望值为： 若假定在线性表中任何一个位置上进行删除的概率都是相等的，则移动元素的期望值为：T(n)=O(n)例如： ListDelete_Sq(L, 5, e) 21 18 30 75 42 56 8721 18 30 75L.length-10pppq8756p = &(L.elemi-1);q = L.elem+L.length-1;for (+p; p next; j = 1; /

21、p指向第一个结点，j为计数器while (p & jnext; +j; / 顺指针向后查找，直到p指向第i个元素 /或p为空if ( !p | ji ) return ERROR; / 第 i 个元素不存在e = p-data; / 取得第 i 个元素return OK;插入数据元素ListInsert(&L, i, e)：将有序对 改变为 和可见，在链表中插入结点只需要修改指针。但同时，若要在第i个结点之前插入元素，修改的是第i-1个结点的指针。因此，在单链表中第i个结点之前进行插入的基本操作为：找到线性表中第i-1个结点，然后修改其指向后继的指针。ai-1 eaiai-1? Status

22、ListInsert_L(LinkList L, int i, ElemType e) / L 为带头结点的单链表的头指针，本算法 / 在链表中第i 个结点之前插入新的元素 e / LinstInsert_L算法的时间复杂度为:O(n) /修改指针p = L; j = 0;while (p & j next; +j; / 寻找第 i-1 个结点if (!p | j i-1) return ERROR; / i 大于表长或者小于1 s = (LinkList) malloc ( sizeof (LNode); / 生成新结点s-data = e; s-next = p-next; p-next

23、= s; / 插入return OK; eai-1aiai-1sp删除数据元素ListDelete(&L, i, e)：将有序对 和 改变为 在单链表中删除第i个结点的基本操作为:找到链表中第i-1个结点，修改其指向后继的指针。ai-1aiai+1ai-1ai-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 为头指针(带头结点)的单链表中第 i 个结点 / ListDelete_L算法的时间复杂度

24、为:O(n)p = L; j = 0;while (p-next & j next; +j; / 寻找第 i 个结点，并令 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; / ClearListfree(p);算法

25、时间复杂度：O(n)注意：操作结束后，只剩一个头结点，且它的指针域为空！生成含 n 个数据元素的链表CreateList(&L, n)：例如：逆位序输入 n 个数据元素的值，建立带头结点的单链表。操作步骤：1.建立一个“空表”； 2.输入数据元素an，建立结点并插入； 3.输入数据元素an-1，建立结点并插入； 4.依次类推，直至输入a1为止。ananan-1anan-1an-2.void CreateList_L(LinkList &L, int n) / 逆序输入 n 个数据元素，建立带头结点的单链表 / CreateList_L算法的时间复杂度为:O(n)L = (LinkList) m

26、alloc (sizeof (LNode);L-next = NULL; / 先建立一个带头结点的单链表for (i = n; i 0; -i) p = (LinkList) malloc (sizeof (LNode); scanf(&p-data); / 输入元素值 p-next = L-next; L-next = p; / 插入比较：例2-1、2-2、2-3中的算法，当线性表分别以顺序存储结构和链表存储结构实现时，它们的时间复杂度为多少？void union(List &La, List Lb) La_len = ListLength(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(