第二章 线性表.ppt

2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.4 一元多项式的表示,第二章 线性表,主要内容：1.线性表的类型定义 2.线性表的顺序表示和实现 3.线性表的链式表示和实现 学习提要：1.了解线性表的逻辑结构和物理结构 2.掌握两种存储结构的描述方法以及在每种存储结构上的基本操作的实现 3.理解两种存储结构的特点及其使用场合 重难点内容：顺序表、链表及其操作实现,线性结构是一个数据元素的有序（次序）集。线性结构的基本特征:（1）存在惟一的一个被称作“第一个”的数据元素（2）存在惟一的一个被称作“最后一个”的数据元素（3）除第一个之外，集合中的每个数据元素均只有 一个直接前驱（4）除最后一个之外，集合中的每个数据元素均只有一个直接后继,线性表(linear_list)：n个数据元素的有限序列。表示为（a1，a2，ai，ai+1，an),例：英文字母表（A,B,C,.Z)是一个线性表,2.1 线性表的类型定义,2.1 线性表的类型定义,线性表的长度：表中元素的个数n(n=0)，n=0 空表。位序：元素ai在表中的位置数i。,逻辑特征：1in时ai的直接前驱是ai-1，a1无直接前驱ai的直接后继是ai+1，an无直接后继元素同构，且不能出现缺项,抽象数据类型线性表的定义如下：,ADT List 数据对象：D ai|ai ElemSet，i=1,2,.,n,n0 数据关系：R1|ai-1,aiD,i=2,.,n 基本操作：InitList(&L)操作结果：构造一个空的线性表L。,DestroyList(&L)初始条件：线性表L已存在。操作结果：销毁线性表L。ListEmpty(L)初始条件：线性表L已存在。操作结果：若L为空表，则返回TRUE，否则FALSE。ListLength(L)初始条件：线性表L已存在。操作结果：返回L中元素个数。,GetElem(L,i,&e)初始条件：线性表L已存在，1iListLength(L)操作结果：用e返回L中第i个元素的值。LocateElem(L,e,compare()初始条件：线性表L已存在，compare()是元素判定函数。操作结果：返回L中第i个与e满足关系compare()的元素的位序。若这样的元素不存在，则返回值为0。,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无定义。,引用型操作,ListTraverse(L,visit()初始条件：线性表L已存在。操作结果：依次对L的每个元素调用函数visit()。一旦visit()失败，则操作失败。ClearList(&L)初始条件：线性表L已存在。操作结果：将L重置为空表。PutElem(L,i,&e)初始条件：线性表L已存在，1i ListLength(L)操作结果：L中第i个元素赋值同e的值。,引用型操作,ListInsert(&L,i,e)初始条件：线性表L已存在，1i ListLength(L)+1 操作结果：在L的第i个元素之前插入新的元素e，L的长度增1。ListDelete(&L,i,&e)初始条件：线性表L已存在且非空，1i ListLength(L)操作结果：删除L的第i个元素，并用e 返 回其值，L的长度减1。ADT List,加工型操作,利用上述定义的线性表 可以实现其它更复杂的操作,例 2-2,例 2-3,例 2-1,假设:有两个集合 A 和 B 分别用两个线性表 LA 和 LB 表示，即：线性表中的数据元素即为集合中的成员。现要求一个新的集合AAB。,例 2-1,要求对线性表作如下操作：扩大线性表 LA，将存在于线性表LB 中而不存在于线性表 LA 中的数据元素插入到线性表 LA 中去。,上述问题可演绎为：,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 相同的数据元素，则插入之,void union(List,for(i=1;i=Lb_len;i+),/union,已知一个非纯集合 B，试构造一个纯集合 A，使 A中只包含 B 中所有值各不相 同的数据元素。,仍选用线性表表示集合。,例 2-2,集合 B,集合 A,从集合 B 取出物件放入集合 A要求集合A中同样物件不能有两件以上,因此，算法的策略应该和例2-1相同,void union(List/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+),InitList(La);/构造(空的)线性表LA,若线性表中的数据元素相互之间可以比较，并且数据元素在线性表中依值非递减或非递增有序排列，即 aiai-1 或 aiai-1(i=2,3,n)，则称该线性表为有序表(Ordered List)。,试改变结构，以有序表表示集合。,例如：（2，3，3，5，6，6，6，8，12）,对集合 B 而言，值相同的数据元素必定相邻；,对集合 A 而言，数据元素依值从小至大的顺序插入。,因此，数据结构改变了，解决问题的策略也相应要改变。,void purge(List i+)/purge,GetElem(Lb,i,e);/取Lb中第i个数据元素赋给 eif(ListEmpty(La)|!equal(en,e)ListInsert(La,+La_len,e);en=e;/La中不存在和 e 相同的数据元素，则插入之,已知有序表LA和LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的数据元素仍按值非递减有序排列,例 2-3,void MergeList(List La,List Lb,List&Lc)/本算法将非递减的有序表 La 和 Lb 归并为 Lc/merge_list,while(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);,/La 和 Lb 均非空，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不空时 GetElem(Lb,j+,bj);ListInsert(Lc,+k,bj);/插入 Lb 表中剩余元素,线性表的顺序表示：用一组地址连续的存储单元依次存储线性表的数据元素。,2.2 线性表的顺序表示和实现,a1,a2,ai,b,b+L,b+(i-1)L,1,2,i,内存状态,储存地址,位序,b+(listsize-1)L,b+(n-1)L,an,b+nL,n,空闲,顺序表：定义：顺序存储结构表示的线性表。元素地址计算方法：LOC(ai+1)=LOC(ai)+LLOC(ai)=LOC(a1)+(i-1)*L其中：L一个元素占用的存储单元个数LOC(ai)线性表第i个元素的地址,特点：实现逻辑上相邻物理位置相邻实现随机存取实现：可用C语言的一维数组实现,a1,a2,an,0,1,n-1,1,2,n,内存状态,数组下标,位序,listsize-1,备用空间,#define LIST_INIT_SIZE 100#define LISTINCREMENT 10 typedef struct ElemType*elem;/基址 int length;/当前长度 int listsize;/当前分配的存储容量(以 sizeof(ElemType)为单位 SqList;,顺序表类型定义：,定义一个顺序表：SqList L;则顺序表的各数据项的表示：L.length L.listsize L.elem0 L.elemL.length-1SqList*L;则顺序表的各数据项的表示：L-length L-listsizeL-elem0 L-elemL-length-1,线性表的基本操作在顺序表中的实现：,InitList(&L)/结构初始化,LocateElem(L,e,compare()/查找,ListInsert(&L,i,e)/插入元素,ListDelete(&L,i,&e)/删除元素,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;L.listsize=LIST_INIT_SIZEreturn OK;,例如：顺序表,e=,38,i,1,2,3,4,1,8,50,基本操作是：将顺序表中的元素逐个和给定值 e 相比较。,查找操作LocateElem(L,e,compare(),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 的初值为第 1 元素的存储位置,while(i=L.length,if(i=L.length)return i;else return 0;,(*compare)(*p+,e),例2-1 顺序表查找算法的实现,(a1,ai-1,ai,an)改变为(a1,ai-1,e,ai,an),插入操作ListInsert_Sq(&L,i,e),内存,a1,a2,ai,ai+1,an,e,q,p,For(p;p=q;-p),&(L.elemi-1),&(L.elemL.length-1),*(p+1)=*p,*q=e;+L.length;,Status ListInsert_Sq(SqList&L,int i,ElemType e)/在顺序表L的第 i 个元素之前插入新的元素e,/i 的合法范围为 1iL.length+1/ListInsert_Sq,