《数据结构》线性表的定义顺序表示和实现.ppt

《《数据结构》线性表的定义顺序表示和实现.ppt》由会员分享，可在线阅读，更多相关《《数据结构》线性表的定义顺序表示和实现.ppt（34页珍藏版）》请在三一办公上搜索。

1、第1章 绪论第2章 线性表第3章 栈和队列 第4章 串第6章 树和二叉树 第7章 图第9章 查找第10章 排序,目 录,数据结构课程的起点：,什么是线性结构？,线性结构的基本特征:,1集合中必存在唯一的一个“第一元素”；,2集合中必存在唯一的一个“最后元素”,3除最后元素在外，均有 唯一的后继；,4除第一元素之外，均有 唯一的前驱。,线性结构 是一个数据元素的有序（次序）集,特点：一对一,第2章 线性表,2.1 线性表的逻辑结构 2.2 线性表的顺序表示和实现2.3 线性表的链式表示和实现2.4 应用举例,（a1,a2,ai-1，ai,ai1，,an）,2.1 线性表的逻辑结构,线性表的定义：

2、用数据元素的有限序列表示,n=0时称为,数据元素,线性起点,ai的直接前趋,ai的直接后继,下标，是元素的序号，表示元素在表中的位置,n为元素总个数，即表长。n0,空表,线性终点,（A,B,C,D,Z）,例2 分析学生情况登记表是什么结构。,分析:数据元素都是同类型（字母），元素间关系是线性的。,例1 分析26 个英文字母组成的英文表是什么结构。,“同一数据逻辑结构中的所有数据元素都具有相同的特性”是指数据元素所包含的数据项的个数都相等。,是指各元素具有相同的数据类型,试判断下列叙述的正误：,注意：同一线性表中的元素必定具有相同特性！,分析：数据元素都是同类型（记录），元素间关系是线性的。,抽

3、象数据类型线性表的定义如下：,ADT List,数据对象：,D ai|ai ElemSet,i=1,2,.,n,n0,数据关系：,R1|ai-1,aiD,i=2,.,n,基本操作：,结构初始化操作,结构销毁操作,引用型操作,加工型操作,ADT List,InitList(&L),操作结果：构造一个空的线性表L,结构初始化操作,结构销毁操作,DestroyList(&L),初始条件：线性表L已存在操作结果：销毁线性表L,引用型操作:,ListEmpty(L)/判空 ListLength(L)/表长,PriorElem(L,cur_e,&pre_e)/前驱 NextElem(L,cur_e,&ne

4、xt_e)/后继,GetElem(L,i,&e)/读取 LocateElem(L,e,compare()/查找,ListTraverse(L,visit()/遍历,加工型操作,ClearList(&L)/清空,PutElem(&L,i,&e)/改写,ListInsert(&L,i,e)/插入,ListDelete(&L,i,&e)/删除,例1：假设:有两个集合 A 和 B 分别用两个线性表 LA 和 LB 表示，即：线性表中的数据元素即为集合中的成员。现要求一个新的集合AAB。,即扩大线性表 LA，将存在于线性表LB 中而不存在于线性表 LA 中的数据元素插入到线性表 LA 中去。,操作步骤：

5、,1从线性表LB中依次察看每个数据元素;,2依值在线性表LA中进行查访;,GetElem(LB,i)e,LocateElem(LA,e,equal(),3若不存在，则插入之。,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,从集合 B 取出物件放入集合 A要求集合A中不能有同样物件

6、,因此，算法的策略应该和例1相同,例2：已知一个非纯集合 B，试构造一个纯集合 A，使 A中只包含 B 中所有值各不相同的数据元素。,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

7、 或 aiai-1(i=2,3,n)，则称该线性表为有序表(Ordered List)。,试改变结构，以有序表表示集合。,例如：（2，3，3，5，6，6，6，8，12）,对集合 B 而言,值相同的数据元素必定相邻,对集合 A 而言,数据元素依值从小至大的顺序插入,因此，数据结构改变了，解决问题的策略也相应要改变。,则,例3：归并两个“其数据元素按值非递减有序排列”的有序表 LA 和 LB，求得有序表 LC 也具有同样特性。,设 La=(a1,ai,an),Lb=(b1,bj,bm)Lc=(c1,ck,cm+n)且已由(a1,ai-1)和(b1,bj-1)归并得(c1,ck-1),k=1,2,m

8、+n,1初始化 LC 为空表；,基本操作：,2分别从 LA和LB中取得当前元素 ai 和 bj；,3若 aibj，则将 ai 插入到 LC 中，否则将bj 插入到 LC 中；,4重复 2 和 3 两步，直至 LA 或 LB 中元素被取完为止；,5将 LA 表或 LB 表中剩余元素复制插入到LC 表中。,算法见教材 P21,返 回,2.2 线性表的顺序表示和实现,2.2.1 顺序表的表示2.2.2 顺序表的实现2.2.3 顺序表的运算效率分析,2.2.1 顺序表的表示,用一组地址连续的存储单元依次存储线性表的元素。,把逻辑上相邻的数据元素存储在物 理上相邻的存储单元中的存储结构。,线性表的顺序表

9、示又称为顺序存储结构或顺序映像。,顺序存储定义：,顺序存储方法：,特点：,逻辑上相邻的元素，物理上也相邻,可以利用数组Vn来实现,注意：在C语言中数组的下标是从0开始，即：Vn的有效范围是从 V0Vn-1,地址求解公式：若已知表中首元素在存储器中的位 置，则其他元素存放位置亦可求出（利用数组Vn的下标）。,设首元素a1的存放地址为LOC(a1)（称为首地址），设每个元素占用存储空间（地址长度）为L字节，则表中任一数据元素的存放地址为：LOC(ai+1)=LOC(ai)+L LOC(ai)=LOC(a1)+L*（i-1）,对上述公式的解释如图所示,地址 内容 元素在表中的位序,1,i,2,n,空

10、闲区,i+1,L,b=LOC(a1),b+L,b+(i-1)L,b+(n-1)L,b+(max-1)L,LOC(ai)=LOC(a1)+L*（i-1）,线性表的顺序存储结构示意图,下标起点是1,设有一维数组，下标的范围是到，每个数组元素用相邻的个字节存储。存储器按字节编址，设存储数组元素的第一个字节的地址是98，则的第一个字节的地址是多少？,答案：113,但此题要注意下标起点是从0开始：LOC(M3)=98+5(4-1)=113,解：已知地址计算通式为：,LOC(ai)=LOC(a1)+L*（i-1）,例,顺序映像的 C 语言描述,typedef struct SqList;/俗称 顺序表,#

11、define LIST_INIT_SIZE 100/线性表存储空间的初始分配量#define LISTINCREMENT 10/线性表存储空间的分配增量,ElemType*elem;/存储空间基址,int length;/当前长度,int listsize;/当前分配的存储容量/(以sizeof(ElemType)为单位),返 回,sizeof(x)算符的意思是：计算变量x的长度(字节数),malloc(m)函数的意思是：新开一片大小为m字节的连续空间，并把该区首址作为函数值。,Status InitList_Sq(SqList/InitList_Sq,2.2.2 顺序表的实现（或操作）,1）

12、初始化 动态创建一个空顺序表,在线性表的第i个位置前插入一个元素,2)插入,在线性表的第i个位置前插入一个元素的示意图如下：,插入26,实现步骤：将第n至第i 位的元素向后移动一个位置；将要插入的元素写到第i个位置；表长加1。,核心语句：,for(j=n;j=i;j-)aj+1=a j;a i=x;n+;,/后移一个位置/插入/表长加1,注意2：表是否已满？如表长超过表尺寸则要增加尺寸。,注意1：事先应判断:插入位置i 是否合法?应当符合条件：1in+1 或 i=1,n+1,使用realloc（*p，newsize）：新开一片大小为newsize的连续空间，并把以*p为首址的原空间数据都拷贝进

13、去，并把该区首址作为函数值。,动态数组的核心是realloc（void*p，newsize）函数,算法见教材 P24,Status ListInsert_Sq(SqList&L,int i,ElemType e)/在顺序表L的第 i 个元素之前插入新的元素e,/i 的合法范围为 1iL.length+1/ListInsert_Sq,q=,if(L.length=L.listsize)/当前存储空间已满，增加分配 newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType);if(!newbase)ex

14、it(OVERFLOW);/存储分配失败 L.elem=newbase;/新基址 L.listsize+=LISTINCREMENT;/增加存储容量,if(i L.length+1)return ERROR;/插入位置不合法,删除线性表的第i个位置上的元素,3)删除,删除顺序表中某个指定的元素的示意图如下：,算法见教材 P24,实现步骤：将第i+1 至第n 位的元素向前移动一个位置；表长减1。注意：事先需要判断，删除位置i 是否合法?应当符合条件：1in 或 i=1,n,核心语句：,for(j=i+1;j=n;j+)aj-1=aj;n-;,/前移一个位置/表长减1,Status ListDel

15、ete_Sq(SqList&L,int i,ElemType&e)/ListDelete_Sq,for(+p;p=q;+p)*(p-1)=*p;/被删除元素之后的元素左移-L.length;/表长减1return OK;,p=/表尾元素的位置,if(i L.length)return ERROR;/删除位置不合法,返 回,2.2.3 顺序表的运算效率分析,算法时间主要耗费在移动元素的操作上，因此计算时间复杂度的基本操作（最深层语句频度）T(n)=O(移动元素次数)而移动元素的个数取决于插入或删除元素的位置.,思考：若插入在尾结点之后，则根本无需移动（特别快）若插入在首结点之前，则表中元素全部要

16、后移（特别慢）应当考虑在各种位置插入（共n+1种可能）的平均移动次数才合理。,讨论1：若在长度为 n 的线性表的第 i 位前 插入一个元素，则向后移动元素的次数f(n)为:f(n)=,n i+1,时间效率分析:,插入时的平均移动次数为,同理可证：顺序表删除一元素的平均移动次数为,想一想：顺序表插入、删除算法的平均空间复杂度为多少？,O(1),因为没有占用辅助空间！,链式存储结构,2.2节小结,线性表顺序存储结构特点：逻辑关系上相邻的两个元素在物理存储位置上也相邻；优点：可以随机存取表中任一元素，方便快捷；缺点：在插入或删除某一元素时，需要移动大量元素。解决问题的思路：改用另一种线性存储方式：,