《线性表及其结构特点.ppt》由会员分享，可在线阅读，更多相关《线性表及其结构特点.ppt（42页珍藏版）》请在金锄头文库上搜索。
1、第二章 线性表,2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.3.1 线性链表 2.3.2 循环链表 2.3.3 双向链表 2.4 一元多项式的表示及相加,在数据元素的非空有限集中 存在唯一的一个被称作“第一个”的数据元素 存在唯一的一个被称作“最后一个”的数据元素 除第一个外，集合中的每个数据元素均只有一个前驱 除最后一个外，集合中的每个数据元素均只有一个后继,线性结构是一个数据元素的有序（次序）集,线性结构特点：,2.1 线性表的类型定义： 定义： 一个线性表是n个数据元素的有限序列,例 英文字母表（A,B,C,Z)是一个线性表,特征：,元素
2、个数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), 称i为ai在线性表中的位序。,基本操作：,结构初始化 InitList( &L ) 操作结果：构造一个空的线性表L。 销毁结构 Destroy
3、List( &L ) 初始条件：线性表L已存在。 操作结果：销毁线性表L。,引用型操作,ListEmpty( L ) 初始条件：线性表L已存在。 操作结果：若L为空表，则返回TRUE，否则FALSE。 ListLength( L ) 初始条件：线性表L已存在。 操作结果：返回L中元素个数。,PriorElem( L, cur_e, &pre_e ) 初始条件：线性表L已存在。 操作结果：若cur_e是L的元素，但不是第一个，则用pre_e 返回它的 前驱，否则操作失败，pre_e无定义。 NextElem( L, cur_e, &next_e ) 初始条件：线性表L已存在。 操作结果：若cur
4、_e是L的元素，但不是最后一个，则用next_e返回它 的后继，否则操作失败，next_e无定义。,GetElem( L, cur_e, &next_e ) 初始条件：线性表L已存在， 1iLengthList(L) 操作结果：用e返回L中第i个元素的值。 LocateElem( L, e, compare( ) ) 初始条件：线性表L已存在，compare( )是元素判定函数。 操作结果：返回L中第1个与e满足关系compare( )的元素的位序。 若这样的元素不存在，则返回值为0。,ListTraverse(L, visit( ) 初始条件：线性表L已存在。 操作结果：依次对L的每个元素调
5、用函数visit( )。一旦visit( )失败，则操 作失败。,加工型操作,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, &e) 初始条件：线性表L已存在且非空，1iLengthList(L) 操作结果：删除L的
6、第i个元素，并用e返回其值，L的长度减1。 ADT List,利用上述定义的线性表可以完成其它更复杂的操作,例2-1 假设有两个集合A和B分别用两个线性表LA和LB表示（即：线性表中的数据元素即为集合中的成员），现要求一个新的集合AAB。 上述问题可演绎为，要求对线性表作如下操作：扩大线性表LA，将存在于线性表LB中而不存在于线性表LA中的数据元素插入到线性表LA中去。,思路：,1从线性表LB中依次取得每个数据元素; GetElem(LB, i)e 2依次在线性表LA中进行查访; LocateElem(LA, e, equal( ) 3若不存在，则插入之。 ListInsert(LA, n+1
7、, e),void union(List / La中不存在和 e 相同的数据元素，则插入之 / union,例2-2 已知一个非纯集合B，试构造一个纯集合A，使A中只包含B中所有值各不相同的数据元素。 void purge(List &La, List Lb) / 已知线性表Lb中的数据元素依值非递减有序排列(Lb是有序表)， / 构造线性表La，使其只包含Lb中所有值不相同的数据元素,InitList(LA); La_len = ListLength(La); Lb_len =ListLength(Lb); / 求线性表的长度 for (i = 1; i = Lb_len; i+) GetE
8、lem(Lb, i, e); / 取Lb中第i个数据元素赋给e if(!equal (en, e) /en初始化为LB中没有的值 ListInsert(La, +La_len, e); en = e; / La中不存在和 e 相同的数据元素，则插入之 / purge,例2-3 归并两个“其数据元素按值非递减有序排列的”线性表LA和LB，求得线性表LC也具有同样特性 设 La = (a1, , ai, , an) Lb = (b1, , bj, , bm) Lc = (c1, , ck, , cm+n) 则 Ck = k = 1, 2, , m+n,思路：,1分别从LA和LB中取得当前元素ai和
9、bj； 2若aibj，则将ai插入到LC中，否则将bj插入到LC中。,void MergeList(List La, List Lb, List ,while (i = La_len) / merge_list,2.2 线性表的顺序存储结构,顺序表： 定义：用一组地址连续的存储单元存放一个线性表叫 元素地址计算方法： LOC(ai)=LOC(a1)+(i-1)*L LOC(ai+1)=LOC(ai)+L 其中： L一个元素占用的存储单元个数 LOC(ai)线性表第i个元素的地址,顺序表：,特点： 实现逻辑上相邻物理地址相邻 实现随机存取 实现：可用C语言的一维数组实现,typedef int
10、DATATYPE; #define M 1000 DATATYPE dataM;,例 typedef struct card int num; char name20; char author10; char publisher30; float price; DATATYPE; DATATYPE libraryM;,数据元素不是简单类型时,可定义结构体数组,动态申请和释放内存 DATATYPE *pData = (DATATYPE *)malloc(M*sizeof(DATATYPE); free(pData);,顺序映像的C语言描述,/- 线性表的动态分配顺序存储结构 - #define
11、LIST_INIT_SIZE 80 / 线性表存储空间的初始分配量 #define LISTINCREMENT 10 / 线性表存储空间的分配增量 typedef struct ElemType *elem; / 存储空间基址 int length; / 当前长度 int listsize; / 当前分配的存储容量(以sizeof(ElemType)为单位) SqList; / 俗称 顺序表,线性表的初始化在顺序映像中的实现,Status InitList_Sq(SqList / InitList_Sq,线性表操作LocateElem(L, e, compare( )的实现：,int Loca
12、teElem_Sq(SqList L, ElemType e, Status (*compare)(ElemType, ElemType) / 在顺序线性表L中查找第1个值与e满足compare()的元素的位序。 / 若找到，则返回其在L中的位序，否则返回0。,i = 1; / i的初值为第1元素的位序 p = L.elem; / p的初值为第1元素的存储位置 while (i = L.length / LocateElem_Sq,此算法的时间复杂度为: O( ListLength(L) ),线性表操作ListInsert(&L, i, e)的实现：,问：插入元素时，线性表的逻辑结构发生什么变
13、化？ (a1, , ai-1, ai, , an) 改变为 (a1, , ai-1, e, ai, , an),x,思路：,1、合法性检查 2、存储空间的处理（判断、申请） 3、元素的移动：从n号到pos号往后移动。 4、把e插入pos号位置，长度增1,Status ListInsert_Sq(SqList ,if (!newbase) exit(OVERFLOW); / 存储分配失败 L.elem = newbase; / 新基址 L.listsize += LISTINCREMENT; / 增加存储容量 q = / ListInsert_Sq,算法时间复杂度T(n) 设Pi是在第i个元素之
14、前插入一个元素的概率，则在长度为n的线性表中插入一个元素时，所需移动的元素次数的平均次数为：,线性表操作ListDelete(&L, i, &e)的实现：,问：删除元素时，线性表的逻辑结构发生什么变化？ (a1, , ai-1, ai, ai+1, , an) 改变为 (a1, , ai-1, ai+1, , an),思路：,1、删除位置的合法性检查 2、删除元素的提取 3、从pos+1号到n号元素前移 4、长度减1。,Status ListDelete_Sq(SqList / ListDelete_Sq,算法评价 设Qi是删除第i个元素的概率，则在长度为n的线性表中删除一个元素所需移动的元素次数的平均次数为：,故在顺序表中插入或删除一个元素时，平均移动表的一半元素，当n很大时，效率很低,顺序存储结构的优缺点：,优点 逻辑相邻，物理相邻 可随机存取任一元素 存储空间使用紧凑 缺点 插入、删除操作需要移动大量的元素 预先分配空间需按最大空间分配，利用不充分 表容量难以扩充,
