《数据结构课件、代码》第2章线性表

第2章线性表(一),张成文北京邮电大学计算机学院,教学要求,1了解：线性表的定义和基本运算。2掌握：线性表的两种存储结构：顺序存储结构和链式存储结构的描述方式，以及这两种存储结构上的基本运算的实现算法。3掌握：线性表的两种存储结构的特点及其具体实现。,主要内容,2.1线性表引例2.2线性表的定义和逻辑结构2.3线性表的基本运算2.4线性表的顺序存储结构2.5顺序表应用2.6小结,线性表引例,例某大学欲进行一次数学竞赛，约有200名学生报名参赛。现将报名登记表(如下表所示)存入计算机以便完成如下工作：(1)能正确录入学生记录；(2)按成绩对该表进行重新排序；(3)按学号或姓名查询学生成绩。,报名登记表,线性表的定义和逻辑结构,线性表的概念线性表是指n(n0)个具有相同类型数据元素(或称结点)的有限序列，可表示为(a1,a2,.,ai,.,an)。其中，ai代表一个数据元素，a1称为表头(或头结点)，an称为表尾(或尾结点)，ai(0in)称为ai+1的直接前驱，ai+1称为ai的直接后继。线性表中数据元素的个数称为线性表的长度，长度为0的线性表称为空表，记为()。,线性表的定义和逻辑结构,（a1,a2,ai-1，ai,ai1，,an）,线性表用数据元素的有限序列表示,n=0时称为,数据元素,线性起点,ai的直接前趋,ai的直接后继,下标，是元素的序号，表示元素在表中的位置,n为元素总个数，即表长。n0,空表,线性终点,例1分析26个英文字母组成的英文表是什么结构。,（A,B,C,D,Z）,例2分析学生情况登记表是什么结构。,分析：数据元素都是同类型（记录），元素间关系是线性的。,分析：数据元素都是同类型（字母），元素间关系是线性的。,注意：同一线性表中的元素必定具有相同特性！,线性表的特征对于非空的线性表:有且仅有一个开始结点a1，没有直接前趋，有且仅有一个直接后继a2；有且仅有一个终结结点an，没有直接后继，有且仅有一个直接前趋an-1；其余的内部结点ai（2in-1）都有且仅有一个直接前趋ai-1和一个ai+1。,a1,a2,a3,a4,a5,a6,圆圈称为结点。一个结点代表一个数据元素，结点之间的连线代表逻辑关系，即相应数据元素之间的邻接关系。,线性表的特点同一性：线性表由同类数据元素组成，每一个ai必须属于同一数据对象。有穷性：线性表由有限个数据元素组成，表长度就是表中数据元素的个数。有序性：线性表中相邻数据元素之间存在着序偶关系。,在不同的问题中，数据元素代表的具体含义不同，它可以是一个数字一个字符，也可以是一句话，甚至其他更复杂的信息。例如:线性表L1:(12,58,45,2,45,46),其元素为数字；线性表L2:(a,g,r,d,s,t),其元素为字母。表1也是一个线性表，其数据元素较为复杂，每个学生的学号姓名性别成绩构成一个数据元素。这种由若干数据项构成的数据元素常称为记录，含有大量记录的线性表称为文件。,线性表的逻辑结构表示在任何问题中，数据元素之间可以存在多种关系。从数据结构的观点来看，重要的是数据元素之间的逻辑关系。所谓逻辑关系，是指数据元素之间的关联方式或称“邻接关系”。在数据的逻辑结构图中，圆圈称为结点。一个结点代表一个数据元素，结点之间的连线代表逻辑关系，即相应数据元素之间的邻接关系。,线性表是一种相当灵活的数据结构，对其数据元素可以进行各种运算(操作)。如对上表，应不仅能查询成绩，还能根据需要增加或删除学生记录。下面给出线性表一些基本运算的含义，这些运算的实现算法后面将具体讨论。(1)Initiate(L)：初始化运算。该函数用于设定一个空的线性表L。(2)Length(L)：求长度函数。该函数返回给定线性表L中数据元素的个数。(3)Get(L,i)：取元素操作。若1iLength(L)，则函数值为给定线性表中第i个数据元素，否则为空元素NULL。,线性表的基本运算,(4)Prior(L,x)：求前驱函数。当x在线性表L中，且其位序大于1，则函数值为x的直接前驱，否则为空元素。(5)Next(L,x)：求后继函数。当x在线性表L中，且其位序小于Length(L),则函数值为x的直接后继，否则为空元素。(6)Locate(L,x)：定位操作。如线性表中存在和x相等的数据元素，则返回该数据元素的位序。若满足条件的元素不惟一，则返回最小的位序。(7)Insert(L,i,x):前插操作。若1iLength(L)+1，则在线性表L中第i个元素之前插入新结点x。,(8)Delete(L,i):删除操作。若1iLength(L)，则删除线性表L中第i个元素。(9)Empty(L)：判空函数。若L为空表，则返回值为1(表示“真”)，否则返回值为0(表示“假”)。(10)Clear(L)：置空操作。将线性表L值为空表。利用这些基本运算还可实现对线性表的各种复杂操作。如将两个线性表进行合并，重新复制一个线性表，对线性表中的元素按某个数据项递增(或递减)的顺序进行重新排序等。可将以上基本运算应用于上表，理解在具体问题中各种运算的具体含义。,线性表的顺序存储结构,顺序表的存储特点顺序表的基本运算,线性表的顺序存储结构,用一组地址连续的存储单元依次存储线性表的元素。,把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。,线性表的顺序表示又称为顺序存储结构或顺序映像。,顺序存储定义：,顺序存储方法：,简言之：,逻辑上相邻的元素，物理上也相邻,可以利用数组Vn来实现。,注意：在C语言中数组的下标是从0开始，即：Vn的有效范围是从V0Vn-1,顺序表的存储特点,1).逻辑上相邻的数据元素，其物理上也相邻；2).若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出（利用数组Vn的下标）。,设首元素a1的存放地址为LOC(a1)（称为首地址），设每个元素占用存储空间（地址长度）为K字节，则表中任一数据元素的存放地址为：LOC(ai+1)=LOC(ai)+KLOC(ai)=LOC(a1)+K*（i-1）,对上述公式的解释如下图所示,a1a2ai-1aian,线性表的起始地址称作线性表的基地址,线性表的顺序存储结构示意图,设有一维数组，下标的范围是到，每个数组元素用相邻的个字节存储。存储器按字节编址，设存储数组元素的第一个字节的地址是，则的第一个字节的地址是多少？,113,例1,但此题要注意下标起点略有不同：LOC(M3)=98+5(3-0)=113,解：已知地址计算通式为：,LOC(ai)=LOC(a1)+L*（i-1）,用数组V来存放26个英文字母组成的线性表（a，b，c，z），写出在顺序结构上生成和显示该表的C语言程序。,charV30;voidbuild()/*字母线性表的生成，即建表操作*/inti;V0=a;for(i=1;ilast,线性表的删除,给出了在线性表中删除一个元素的框图，其中被删除元素所在的第i个位置已经给出。,下面给出线性表删除一个元素的算法，被删除的元素被保留在out中以防丢失。/*线性表元素的删除*/DELEGLIST(v,i,n)/*v是线性表，i是被删除元素的位置，n是线性表的长度*/intj;out=vi;for(j=i;j=n-1;j+)vj=vj+1;/*从i+1到n位置上的元素逐个上移*/n-;,3.线性表元素定位操作下图(a)所示的是无序线性表，其数据元素在线性表中的存放是任意的；图(b)所示的是有序线性表，其数据元素的排列按英文字母的字母顺序从小到大存放。有序线性表有如下特点，设V为有序线性表，数据元素ai值的相邻关系为ai-1aiai+1。,无序和有序线性表(a)无序线性表；(b)有序线性表,无序表查找操作:ESEARCH(v,n,t)算法分析:,t=,38,序号i,1,2,3,4,1,8,50,原操作是：将顺序表中的元素逐个和给定值t相比较。,无序线性表的查找算法框图,无序线性表的查找算法如下：/*无序线性表的查找算法*/ESEARCH(v,n,t)/*v是无序线性表，n是线性表的长度，t是被查找的记录*/inti;vn+1=t;/*建立无序查找的结束标志*/i=1;while(vi!=t)i+;,if(i=n)return(search,true);elsereturn(search,false);,有序线性表的查找算法框图,有序线性表的查找算法如下：/*有序线性表的查找算法*/EGSEARCH(v,n,t)/*v是有序线性表，n是线性表的长度，t是被查找的记录*/charsearch6;inti;vn+1=;/*设置查找的结束标志*/i=1;,while(vit)i+;if(vi=t)printf(search,true);elseprintf(search,false);,优点：1.无需为表示结点间的逻辑关系而增加额外的存储空间；2.可方