第3章线性表剖析

《第3章线性表剖析》由会员分享，可在线阅读，更多相关《第3章线性表剖析（102页珍藏版）》请在金锄头文库上搜索。

1、2019年10月17日星期四,第1页,线性表,2019年10月17日星期四,第2页,【学习目标】,1. 了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。用前者表示的线性表简称为顺序表，用后者表示的线性表简称为链表。 2. 熟练掌握这两类存储结构的描述方法以及线性表的基本操作在这两种存储结构上的实现。 3. 能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。 4. 结合线性表类型的定义增强对抽象数据类型的理解。,2019年10月17日星期四,第3页,【重点和难点】,链表是本章的重点和难点。扎

2、实的指针操作和内存动态分配的编程技术是学好本章的基本要求，分清链表中指针 p 和结点 *p 之间的对应关系，区分链表中的头结点、头指针和首元结点的不同所指以及循环链表、双向链表的特点等。,【知识点】,线性表、顺序表、链表、有序表,2019年10月17日星期四,第4页,线性结构的基本特征为:,1集合中必存在唯一的一个“第一元素”；,2集合中必存在唯一的一个 “最后元素” ；,3除最后元素在外，均有 唯一的后继；,4除第一元素之外，均有 唯一的前驱。,线性结构 是 一个数据元素的有序（次序）集,线性表是一种最简单的线性结构,2019年10月17日星期四,第5页,1 线性表的类型定义,3 线性表类型

3、的实现 链式映象,4 一元多项式的表示,2 线性表类型的实现 顺序映象,2019年10月17日星期四,第6页,线性表的类型定义,2019年10月17日星期四,第7页,定义：一个线性表是具有相同类型的n（n0）个数据元素的有限序列，通常记为：,特征： i为元素的序号 元素个数n表长度，n=0空表 1in时 ai的直接前驱是ai-1，a1无直接前驱 ai的直接后继是ai+1，an无直接后继,1 线性表的定义,2019年10月17日星期四,第8页,数据对象：,D ai | ai D0, i=1,2,.,n, n0 称 n 为线性表的表长; 称 n=0 时的线性表为空表。,数据关系：,R |ai-1

4、,aiD, i=2,.,n ,设线性表为 (a1，a2, . . . ，ai，. . . ，an), 称 i 为 ai 在线性表中的位序。,2019年10月17日星期四,线性表的基本运算,置空表setnull(L)：将线性表L置为空表。 求长度length(L)：计算线性表L中数据元素的个数。 取元素get(L,i)：取出线性表L中第i个数据元素；要求ilength(L)。 取前趋prior(L,x)：取出线性表L中值为x的元素的前趋元素；要求x的位序大于1。 取后继next(L,x)：取出线性表L中值为x的元素的后继元素；要求x的位序小于length(L)。 定位序locate(L,x)：确

5、定元素x在线性表L中的位置，并给出位置序号；若L中无x返回0。,2019年10月17日星期四,线性表的基本运算（续）,插入insert(L,x,i)：在线性表L中第i个位置上插入值为x的新元素，使表长增1；要求1ilength(L)+1。 删除delete(L,i)：删除线性表L中的第i个元素，使表长减1；要求1ilength(L)。,2019年10月17日星期四,第11页,利用上述定义的线性表 可以实现其它更复杂的操作,例 2-2,例 2-1,2019年10月17日星期四,第12页,求两个集合的并，即A=AB,例 2-1,2019年10月17日星期四,第13页,要求对线性表作如下操作： 扩大

6、线性表 LA，将存在于线性表LB 中而不存在于线性表 LA 中的数据元素插入到线性表 LA 中去。,上述问题可演绎为：,2019年10月17日星期四,第14页,1从线性表LB中依次察看每个数据元素;,2依值在线性表LA中进行查访;,3若不存在，则插入之。,get (LB, i)e,locate (LA, e),insert(LA, n+1, e),操作步骤：,2019年10月17日星期四,第15页,e =get(Lb, i); / 取Lb中第i个数据元素赋给e if (!locate (La, e) ) insert(La, +La_len, e); / La中不存在和 e 相同的数据元素，则

7、插入之,void union(La, Lb) La_len = length(La); / 求线性表的长度 Lb_len = length(Lb);,for (i = 1; i = Lb_len; i+) , / union,2019年10月17日星期四,第16页,已知一个非纯集合 B，试构造一个纯集合 A，使 A中只包含 B 中所有值各不相 同的数据元素。,仍选用线性表表示集合。,例 2-2,2019年10月17日星期四,第17页,集合 B,集合 A,从集合 B 取出物件放入集合 A 要求集合A中同样物件不能有两件以上,因此，算法的策略应该和例2-1相同,2019年10月17日星期四,第18

8、页,void union(List / union,e=get(Lb, i); / 取Lb中第 i 个数据元素赋给 e if (!locate(La, e) ) insert(La, +La_len, e); / La中不存在和 e 相同的数据元素，则插入之,for (i = 1; i = Lb_len; i+) ,setnull(La); / 构造(空的)线性表LA,2019年10月17日星期四,第19页,若线性表中的数据元素相互之间可以比较，并且数据元素在线性表中依值非递减或非递增有序排列，即 aiai-1 或 aiai-1(i = 2,3, n)，则称该线性表为有序表(Ordered L

9、ist)。,我们再来看看有序表表示的集合。,2019年10月17日星期四,第20页,例如： LA=(3,5,8,11) LB=(2,6,8,9,11,15,20),对集合LA和LB 而言， 值相同的数据元素必定相邻。,要求生成一个新表LC，使LC中的数据元素仍按值非递减有有序排列。,2019年10月17日星期四,第21页,线性表类型 的实现-顺序映象,2019年10月17日星期四,第22页,用一组地址连续的存储单元 依次存放线性表中的数据元素,a1 a2 ai-1 ai an,线性表的起始地址 称作线性表的基地址,2019年10月17日星期四,第23页,元素地址计算方法： LOC(ai)=LO

10、C(a1)+(i-1)*d 1in 特点： 逻辑上相邻物理地址相邻 随机存取 实现：可用C语言的一维数组实现,LOC(a1)+(n-1)*d,LOC(a1),LOC(a1)+(i-1)*d,存储地址,LOC(a1)+d,2019年10月17日星期四,顺序表的类型描述,#define MAXSIZE 500 typedef struct elemtype dataMAXSIZE; int last; sequenlist,seqlist; 即把顺序表类型sequenlist描述为一个结构体，域data数组存放表中的数据元素，域last存放表长，datalast存放表中最后一个元素。,2019年1

11、0月17日星期四,库函数提供动态地开辟和释放存储单元的 有关函数： malloc函数 其函数原型为void *malloc(unsigned int size);其 作用是在内存的动态存储区中分配一个长度为 size的连续空间。此函数的值（即“返回值”） 是一个指向分配域起始地址的指针（类型为 void）。如果此函数未能成功地执行（例如内 存空间不足），则返回空指针(NULL)。,2019年10月17日星期四,(2) calloc函数 其函数原型为void *calloc（unsigned ， unsigned size）;其作用是在内存的动态存储区 中分配个长度为size的连续空间。函数返回

12、 一个指向分配域起始地址的指针；如果分配不 成功，返回NULL。 用calloc函数可以为一维数组开辟动态存 储空间，n为数组元素个数，每个元素长度为 size,2019年10月17日星期四,(3) free函数 其函数原型为void free（void *p）;其作用是释放由指向的内存区，使这部分内存区能被其他变量使用。是最近一次调用calloc或malloc函数时返回的值。free函数无返回值.,2019年10月17日星期四,第28页,void setnull( sequenlist *L) / 构造一个空的线性表 / InitList_Sq int length(sequenlist L

13、) return L.last; ,L-last = 0;,2019年10月17日星期四,第29页,线性表的基本操作在顺序表中的实现,Locate(L, x) / 查找,2019年10月17日星期四,第30页,例如：顺序表的查找操作,x =,38,i,1,2,3,4,1,8,50,可见，基本操作是： 将顺序表中的元素 逐个和给定值 x 相比较。,2019年10月17日星期四,第31页,int locate (sequenlist L, elemtype x) / 在顺序表中查询第一个满足判定条件的数据元素， / 若存在，则返回它的位序，否则返回 0 ,O( ListLength(L) ),算法

14、的时间复杂度为：,int i = 1; / i 的初值为第 1 元素的位序,while (i = L.last ,if (i = L.last) return i; else return 0;,2019年10月17日星期四,第32页,线性表操作 insert(L, i, x)的实现：,首先分析:,插入元素时， 线性表的逻辑结构发生什么变化？,2019年10月17日星期四,第33页,(a1, , ai-1, ai, , an) 改变为 (a1, , ai-1, x, ai, , an), ,2019年10月17日星期四,第34页,算法的思想,进行合法性检查（i） 检查线性表是否已满 讲第n个至

15、第i个元素逐一后移一个单位 在第i个位置上插入 表的长度+1,2019年10月17日星期四,插入运算的算法描述,void insert(sequenlist *L; elemtype x; int i) int j; if(i(L-last+1) printf(“插入位置不正确n”); else if(L-last=MAXSIZE) printf(“表已满，发生上溢n”); else for(j=L-last;j=i;j-) L-dataj+1=L-dataj; L-datai=x; L-last=L-last+1; /*insert*/,2019年10月17日星期四,第36页,考虑插入算法的

16、时间复杂度:,2019年10月17日星期四,第37页,线性表操作 delete(&L, i)的实现：,首先分析：,删除元素时， 线性表的逻辑结构发生什么变化？,2019年10月17日星期四,第38页,(a1, , ai-1, ai, ai+1, , an) 改变为 (a1, , ai-1, ai+1, , an),ai+1,an, ,表的长度减少,2019年10月17日星期四,第39页,算法的思想,进行合法性检查，i是否满足要求 判定线性表是否为空 将第i+1至第n个元素逐一往前移动一个位置 将表的长度减少1,2019年10月17日星期四,删除运算的算法描述,void delete(sequenlis