第2章线性表1(顺序表)

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,线性结构的定义：,若结构是非空有限集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。 ,可表示为：（,a,1, a,2, , a,n,）,简言之，线性结构反映结点间的逻辑关系是,的。,特点 只有一个首结点和尾结点；,特点 除首尾结点外，其他结点只有一个直接前驱和一个直接后继。,线性结构包括：,线性表、堆栈、队列、字符串、数组,等，其中最典型、最常用的是,-,线性表,一对一,(1:1),1,第,2,章 线性表,2.1,线性表的基本概念,2.2,线性表的顺序表示和实现,2.3,线性表的链式表示和实现,2.4,应用举例,2,2.1,线性表的基本概念,、线性表,它是一种最简单的线性结构。是一种可以在任意位置进行插入和删除数据元素操作的，由,n,（,n,0),个相同类型数据元素,a,0, a,1, , a,n-1,组成的线性结构。,3,（,a,0, a,1, ,a,i-1,，,a,i,a,i,1,，,a,n-1,）,线性表的逻辑结构：,n=0,时称为,数据元素,线性起点,a,i,的直接前趋,a,i,的直接后继,下标，,是元素的序号，表示元素在表中的位置,n,为元素总个数，即表长。,n0,空表,线性终点,4,（,A, B, C, D, , Z,）,学号,姓名,性别,年龄,班级,012003010622,陈建武,男,19,2003,级电信,0301,班,012003010704,赵玉凤,女,18,2003,级电信,0302,班,012003010813,王 泽,男,19,2003,级电信,0303,班,012003010906,薛 荃,男,19,2003,级电信,0304,班,012003011018,王 春,男,19,2003,级电信,0305,班,：,：,：,：,：,例,2,分析学生情况登记表是什么结构。,分析：数据元素都是同类型（记录），元素间关系是线性的。,分析：,数据元素都是同类型（,字母,）， 元素间关系是线性的。,注意：同一线性表中的元素必定具有相同特性 ！,例,1,分析,26,个英文字母组成的英文表是什么结构。,5,.,线性表抽象数据类型,它包括两个方面：,数据集合：,a,0, a,1, , a,n-1,a,i,的,数据类型为,DataType,操作集合,：,(1)ListInitiate(L),初始化线性表,(2)ListInsert(L,i,x),插入数据元素,(3)ListLength(L),求当前数据元素个数,(4)ListDelete(L,i,x),删除数据元素,(5)ListGet(L,i,x),取数据元素等,6,3.,线性表的存储结构,(1),顺序存储结构,:,它是使用一片,地址连续,的有限内存单元空间存储数据元素的一种计算机存储数据方法。,特点：,(,任意两个在逻辑上相邻的数据元素在物理位置上也必然相邻,),逻辑上相邻的元素，物理上也相邻。,(2),链式存储结构,:,它是把数据元素和指针定义成一个存储体，使用指针把发生联系的数据元素链接起来的一种计算机存储数据方法。,特点：,任意两个在,逻辑上相邻,的数据元素在,物理上不一定相邻,，数据元素的逻辑次序是通过链中的指针链接实现的。,7,2.2,线性表的顺序表示和实现,一,、,顺序表的存储结构,二、,顺序表的实现,三、,顺序表的运算效率分析,8,一、 顺序表的存储结构表示,1,、,顺序表,：,用一组,地址连续,的存储单元依次存储线性表的各个数据元素。即采用顺序存储结构的线性表。它通常采用静态数组实现数据元素的存储。,可以利用,数组,Vn,来实现,注意：在,C,语言中数组的下标是从,0,开始，即：,Vn,的有效范围是从,V0,Vn-1,9,(1),逻辑上相邻的数据元素，其物理上也相邻；,(2),若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出,（,利用数组,Vn,的,下标,）,。,设首元素,a,0,的存放地址为,LOC(a,0,),（,称为,首地址,），,设每个元素占用存储空间（地址长度）为,L,字节，,则表中任一数据元素的,存放地址,为：,LOC (,a,i+1,) = LOC(,a,i,) + L,LOC (,a,i,) = LOC(,a,0,) + L *i,对上述公式的解释如图所示,2,、线性表顺序存储特点：,10,a,0,a,1,a,i,a,i+1,a,n-1,地址 内容 元素在表中的位序,0,i,1,n-1,空闲区,i+1,L,b=LOC(a,0,),b,+,L,b,+,i,L,b,+(n-1),L,b,+(MaxSize-1),L,LOC (,a,i,) = LOC( a,0,) + L *i,3,、线性表的顺序存储结构示意图,11,4,、用,C,语言描述,typedef,struct,DateType,listMaxSize,;,int,size;,SeqList,;,/*,MaxSize,表示数组的最大元素个数，,list,表示顺序表的数组名，,size,表示顺序表中当前存储的数据元素个数，它必须满足,size,MaxSize,，,SeqList,是该结构体的名字。*,/,12,设有一维数组,，下标的范围是,到,，每个数组元素用相邻的,个字节,存储。存储器按字节编址，设存储数组元素,的第一个字节的地址是,，则,的第一个字节的地址是多少？,113,LOC( M,3,) = 98 + 5 3 =,113,解：,已知地址计算通式为：,LOC(a,i,) = LOC(a,0,) + L *i,例,1,13,二、,顺序表的实现（或操作）,数据结构的基本运算：,修改、插入、删除、,查找、排序,1),修改,通过数组的下标便可访问某个特定元素并修改之。,核心语句,:,Vi=x;,显然，顺序表修改操作的时间效率是,O(1),14,在线性表（,n,个元素）的第,i,个位置,前,插入,一个元素,实现步骤：,将第,n,至第,i,位的元素向后移动一个位置；,将要插入的元素写到第,i,个位置；,表长加,1,。,注意：,事先应判断,:,插入位置,i,是否合法,?,表是否已满,?,2),插入,15,int,ListInsert(SeqList,*,L,int,i,DataType,x),int,j;,if(L,-size=,MaxSize,) ,printf,(“,顺序表已满无法插入,!n”);,return 0;,else,if(,i,L-size,) ,printf,(“,参数,i,不合法,!n”);,return 0;,else ,for (j=L-size; ji; j,-,) L-,listj,=L-listj-1 ;,L-,listi,=x;,L-size+;,return 1;,插入数据元素,16,在线性表的第,i,个位置前插入一个元素的示意图如下：,12,13,21,24,28,30,42,77,12,13,21,24,25,28,30,42,77,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,8,9,插入,25,17,实现步骤：,将第,i+1,至第,n,位的元素向前移动一个位置；,表长减,1,。,注意：事先需要判断，,删除位置,i,是否合法,?,删除,线性表的第,i,个位置上的元素,for ( j=i+1; jsize-1; j+ ),L-listj-1= L-,listj, ;,L-size-;,return 1;,/,元素前移一个位置,/,表长减,1,核心语句：,3),删除,18,1,2,3,4,5,6,7,8,9,12,13,21,24,25,28,30,42,77,1,2,3,4,5,6,7,8,12,13,21,24,28,30,42,77,删除顺序表中某个指定的元素的示意图如下：,19,例：建立一个线性表，先依次输入数据元素,1,，,2,，,3,，,4,，,，,10,，然后删除，最后依次显示当前线性表中的数据元素。假设该线性的数据元素个数最坏情况下不会超过,100,个。实现方法：,1,、采用直接编写,一个主函数,实现。,2,、利用已设计实现的,抽象数据类型模块,。（存放在头文件名为,SeqList.h,中，通过,#include “,SeqList.h,”,）,20,三、,顺序表操作的效率分析,算法时间主要耗费在,移动元素,的操作上，因此,计算时间复杂度的基本操作（最深层语句频度）,T(n)= O,(,移动,元素次数,),而移动元素的个数取决于插入或删除元素的位置,.,思考：,若插入在尾结点之后，则根本无需移动（特别快）；,若插入在首结点之前，则表中元素全部要后移（特别慢）；,应当考虑在各种位置插入（共,n+1,种可能）的,平均,移动次数才合理。,时间效率,分析,:,21,推导：,假定在每个元素位置上插入,x,的可能性都一样（即概率,P,相同），则应当这样来计算平均执行时间：,将所有位置的执行时间相加，然后取平均。,若在首结点前插入，需要移动的元素最多，后移,n,次；,若在,a,1,后面插入，要后移,n-1,个元素，后移次数为,n-1,;,若在,a,n-1,后面插入，要后移,1,个元素；,若在尾结点,a,n,之后插入，则后移,0,个元素；,所有可能的元素移动次数合计,：,0+1+n,= n(n+1)/2,故插入时的平均移动次数为：,n(n+1)/2,（,n+1,）,n/2,O(n),共有多少种插入形式,?,连头带尾有,n+1,种,!,22,同理可证：,顺序表删除一元素的时间效率为,:,T,（,n)=(n-1)/2 ,O(n),插入效率：,删除效率：,教材,有对执行效率的推导：,即插入、删除算法的平均时间复杂度为,O(n),23,链式存储结构,本节小结,线性表,顺序存储结构特点,：逻辑关系上相邻的两个元素在物理存储位置上也相邻；,优点：,可以随机存取表中任一元素，方便快捷；,缺点：,在插入或删除某一元素时，需要移动大量元素。,解决问题的思路：,改用另一种线性存储方式：,24,作业：,参考教材课后习题,(,严蔚敏、吴伟民 著,),2.10,2.12,25,