数据结构第二章 线性表part2

1、 已知线性表已知线性表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-3 Void MergeList (List La , List Lb, List &Lc) INITIATE(Lc); i=j=1; k=0; /初始化初始

2、化 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 表中剩余元素表中剩余元素 GetElem(La, i+,ai); ListInsert(LC,+k,ai) ; while (j=Lb_len)

3、 / 插入插入 Lb 表中剩余元素表中剩余元素 GetElem(Lb, j+,bj); ListInsert(LC,+k,bj ; / MergeList2.2 线性表的顺序表示和实现线性表的顺序表示和实现一、线性表的顺序存储结构一、线性表的顺序存储结构顺序映象顺序映象二、顺序存储结构的特点二、顺序存储结构的特点三、线性表的顺序存贮结构示意图及描述三、线性表的顺序存贮结构示意图及描述四、线性表的基本操作在顺序表中的实现四、线性表的基本操作在顺序表中的实现五、顺序存储结构的优缺点五、顺序存储结构的优缺点一、线性表的顺序存储结构一、线性表的顺序存储结构 顺序映象顺序映象 最简单的一种顺序映象方法是

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

5、一个数据元素的存储位置，即数据元素的存储位置，即 LOC(ai)=LOC(a1)+(i-1)*c 起始地址（基地址）起始地址（基地址）以“存储位置相邻存储位置相邻”表示有序对二、顺序存储结构的特点二、顺序存储结构的特点 表中相邻的两个元素其物理存储位置也相邻。表中相邻的两个元素其物理存储位置也相邻。即以元素在计算机内物理位置上的相邻来表示线性即以元素在计算机内物理位置上的相邻来表示线性表中数据元素之间相邻的逻辑关系。每个数据元素表中数据元素之间相邻的逻辑关系。每个数据元素的存储位置和线性表的起始位置相差一个和数据元的存储位置和线性表的起始位置相差一个和数据元素在线性表中的序号成正比的常数；只要

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

7、t; /俗称顺序表俗称顺序表#define LIST_INIT_SIZE 80 / 线性表存储空间的初始分配量线性表存储空间的初始分配量#define LISTINCREMENT 10 / 线性表存储空间的分配增量线性表存储空间的分配增量ElemType *elem; / 存储空间基址存储空间基址int length; / 当前长度当前长度int listsize; / 当前分配的存储容量当前分配的存储容量 / ( (以以sizeof(ElemTypesizeof(ElemType) )为单位为单位) )四、线性表的基本操作在顺序表中的实现四、线性表的基本操作在顺序表中的实现InitList(

8、&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_ INIT_SIZE sizeof (ElemType);if (!L.elem) exit (OVERFLOW);

9、 / 存储分配失败存储分配失败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, ElemType e, Status (*compare)(ElemType, ElemType) /在顺序表中查询第一个满

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

11、 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 个元素之前插入新的元素e, / i 的合法范围为 1iL.length+1 / ListInsert_Sq 算法算法时

12、间复杂度时间复杂度为为: :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) / 当前存储空间已满，增加分配 newbase = (ElemType *)realloc(L.elem, (L.listsize+LISTINCR

13、EMENT)*sizeof (ElemType); if (!newbase) exit(OVERFLOW); / 存储分配失败 L.elem = newbase; / 新基址 L.listsize += LISTINCREMENT; / 增加存储容量if (i L.length+1) return ERROR; / 插入位置不合法 Status ListInsert_Sq(SqList &L, int i, ElemType e) / 在顺序表L的第 i 个元素之前插入新的元素e, / i 的合法范围为 1iL.length+1 / ListInsert_Sq 算法算法时间复杂度时间

14、复杂度为为: :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 的线性表中插入一个元素所需移插入一个元素所需移动元素次数的期望值动元素次数的期望值为：ip11) 1(ni

15、iisinpE11) 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线性表操作线性表操作 ListDelete(&L, i, &e)的实现的实现：

16、首先分析：首先分析：删除元素时，删除元素时，线性表的逻辑结构发生什么变化？线性表的逻辑结构发生什么变化？ (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; / 被删除元素之后的元素左移被删除元素之后的元素左移-L.length

17、; / 表长减表长减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 的线性表中删除一个元素所需移动元素次数的移动元素次数的期望值期

18、望值为：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 = q; +p) *(p-1) = *p; 例如：ListDelete_Sq(L, 5, e) p 在顺序存储结构的线性表中插入或删除一个数在顺序存储结构的线性表中插入或删除一个数据元素时，其时间主要耗费在移动元素上，移动次据元素时，其时间主要耗费在移动元素上，移动次数不仅依赖于线性表的长度数不仅依赖于线性表的长度L.length，还依赖于元，还依赖于元素插入或删除的位置