顺序表

数据结构第二章－－线性表安工大计算机学院第2章线性表本章主要介绍下列内容线性表的定义和基本操作线性表的顺序存储结构线性表的链式存储结构线性表的应用举例数据结构第二章－－线性表安工大计算机学院本章学习要求了解：线性表的基本概念和基本运算。掌握：顺序表的存储结构和查找、插入、删除等基本运算。掌握：单链表的存储结构以及单链表的建立、查找、插入、删除等操作。掌握：双向链表的存储结构以及插入、删除操作。了解：静态链表的存储结构和基本运算。掌握：利用线性表的基本运算解决复杂问题。数据结构第二章－－线性表安工大计算机学院2.1线性表的逻辑结构2.1.1线性表的定义线性表是由n（n≥0）个类型相同的数据元素组成的有限序列。通常表示成下列形式：L=(a1,a2,...,ai-1,ai,ai+1,...,an)其中：L为线性表名称，习惯用大写书写；ai为组成该线性表的数据元素，习惯用小写书写；线性表中数据元素的个数被称为线性表的长度，当n=0时，线性表为空，又称为空线性表。数据结构第二章－－线性表安工大计算机学院举例La=（34，89，765，12，90，-34，22）数据元素类型为int。Ls=(Hello,World,China,Welcome)数据元素类型为string。Lb=(book1,book2,...,book100)数据元素类型为下列所示的结构类型：structbookinfo{intNo;//图书编号char*name;//图书名称char*auther;//作者名称...;}数据结构第二章－－线性表安工大计算机学院2.1.2线性表的基本操作1.初始化线性表LInitList(L)2.销毁线性表LDestoryList(L)3.清空线性表LClearList(L)4.求线性表L的长度ListLength(L)5.判断线性表L是否为空IsEmpty(L)6.获取线性表L中的某个数据元素内容GetElem(L,i,e)7.检索值为e的数据元素LocateELem(L,e)8.返回线性表L中e的直接前驱元素PriorElem(L,e)9.返回线性表L中e的直接后继元素NextElem(L,e)10.在线性表L中插入一个数据元素ListInsert(L,i,e)11.删除线性表L中第i个数据元素ListDelete(L,i,e)数据结构第二章－－线性表安工大计算机学院2.2线性表的顺序存储结构2.2.1顺序表线性表的顺序存储结构是指用一组连续的存储单元依次存储线性表中的每个数据元素。如下图2-1所示：数据结构第二章－－线性表安工大计算机学院存储地址内存单元...da1d+La2d+2La3...d+(i-1)Lai...d+(n-1)Lan......图2-1线性表顺序存储结构示意图数据结构第二章－－线性表安工大计算机学院其中，L为每个数据元素所占据的存储单元数目。相邻两个数据元素的存储位置计算公式LOC(ai+1)=LOC(ai)+L线性表中任意一个数据元素的存储位置的计算公式为：LOC(ai)=LOC(a1)+(i-1)*L顺序存储结构的特点（1）利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系，即线性表的逻辑结构与存储结构（物理结构）一致；数据结构第二章－－线性表安工大计算机学院（2）在访问线性表时，可以利用上述给出的数学公式，快速地计算出任何一个数据元素的存储地址。因此，我们可以粗略地认为，访问每个数据元素所花费的时间相等。这种存取元素的方法被称为随机存取法，使用这种存取方法的存储结构被称为随机存储结构。在C语言中，实现线性表的顺序存储结构的类型定义#defineMAXSIZE100//线性表的最大长度DataTypedata[MAXSIZE];intlength;通常将data和length封装成一个结构作为顺序表的类型：typedefstruct{DataTypedata[MAXSIZE];//指向存放线性表中数据元素的基地址intlength;//线性表的当前长度}SeqList；数据结构第二章－－线性表安工大计算机学院定义一个顺序表：SeqListL；根据C语言中函数参数的传递采用值传送的规则，有时定义一个指向SeqList类型的指针更为方便，能够实现信息的回送，因此我们定义一个指针类型：typedefSeqList*PSeqList；PSeqList是一个能够指向SeqList类型变量的指针类型；如SeqListPoint是一个指针变量，线性表的存储空间可通过SeqListPoint=(PSeqList)malloc(sizeof(SeqList))操作来获得，也可以通过SeqListPoint=&L来实现。数据结构第二章－－线性表安工大计算机学院SeqListPoint是顺序表的指针，这样表示的线性表在内存中的表示如图2-2所示。表长为(*SeqListPoint).length或SeqListPoint-length，线性表的存储区域为SeqListPoint-data数组。数据结构第二章－－线性表安工大计算机学院2.2.2顺序表上基本运算的实现1.初始化顺序表PSeqListInit_SeqList(void){/*创建一顺序表，入口参数无，返回一个指向顺序表的指针，指针值为零表示分配空间失败*/PSeqListSeqListPoint;SeqListPoint=(PSeqList)malloc(sizeof(SeqList));if(SeqListPoint==NULL)/*若SeqListPoint=NULL表示分配失败*/returnNULL;elseSeqListPoint-length=0;return(SeqListPoint);}注：malloc函数包含在stdlib.h头文件中数据结构第二章－－线性表安工大计算机学院2.销毁线性表LvoidDestroy_SeqList(PSeqListSeqListPoint){/*销毁顺序表，入口参数：为要销毁的顺序表指针地址，无返回值*/if(SeqListPoint)free(SeqListPoint);//SeqListPoint=NULL;return;}设调用函数为主函数，主函数对初始化函数和销毁函数的调用如下：main(){PSeqListSeqListPoint;SeqListPoint=Init_SeqList();……Destroy_SeqList(SeqListPoint);}数据结构第二章－－线性表安工大计算机学院3.求线性表L的长度intLength_SeqList(PSeqListSeqListPoint){/*求顺序表的长度，入口参数：为顺序表指针，返回表长，-1表示表不存在*/if(SeqListPoint)return(SeqListPoint-length);return(-1);}数据结构第二章－－线性表安工大计算机学院4.顺序表的检索操作顺序表的检索是在表存在的情况下，查找值为x的数据元素，若成功，返回在表中首次出现的值为x的那个元素的序号(不是下标)；未找到值为x的数据元素，返回0表示查找失败。在顺序表中完成该运算最简单的方法是：从第一个元素e1起依次和x比较，直到找到一个与x相等的数据元素，返回它在顺序表中的data数组的下标＋1（第一个元素存放在data[0]）；或者查遍整个表都没有找到与x相等的元素，返回0。具体算法描述如下：数据结构第二章－－线性表安工大计算机学院intLocation_SeqList(PSeqListSeqListPoint,ElementTypex){/*顺序表检索，入口参数：为顺序表指针，检索元素，返回元素位置，-1表示表不存在，0表示查找失败*/inti=0;if(!SeqListPoint){printf(＂表不存在＂);return(-1);/*表不存在，不能检索*/}while(iSeqListPoint-length&&SeqListPoint-data[i]!=x)i++;if(i=SeqListPoint-length)return0;elsereturn(i+1);}本算法的主要运算是比较。显然比较的次数与x在表中的位置有关，也与表长有关。当e1=x时，比较一次成功，当en=x时比较n次成功，平均比较次数为(n+1)/2；检索不成功时须循环n+1次。时间复杂度为O(n)。数据结构第二章－－线性表安工大计算机学院5.顺序表的插入运算顺序表的插入是指在表的第i个位置上插入一个值为x的新元素，即在第i元素之前插入x，使原表长为n的表：(e1，e2，...，ei-1，ei，ei+1，...，en)变为表长为n+1表：(e1，e2，...，ei-1，x，ei，ei+1，...，en)。其中i：1≤i≤n+1。顺序表插入运算的操作步骤如下：(1)检查待插入的表是否存在，若不存在退出；(2)判断顺序表是否满(即表长length是否大于等于MAXSIZE)？若满，退出；否则执行(3)；(3)检查插入位置的合法性(i满足1=i=length+1)。若不满足，退出；否则执行(4)；(4)将ei～en顺序向下移动一位，为新元素的插入腾出位置(注意数据的移动方向)；(5)将x置入腾出位置；(6)修改表长；数据结构第二章－－线性表安工大计算机学院顺序表插入运算主要步骤：for(j=SeqListPoint-length-1;j=i-1;j--)SeqListPoint-data[j+1]=SeqListPoint-data[j];/*移动元素*/SeqListPoint-data[i-1]=x;/*新元素插入*/SeqListPoint-length++;/*表长加1*/数据结构第二章－－线性表安工大计算机学院顺序表的插入运算，时间主要消耗在了数据的移动上，在第i个位置上插入x，从ei到en都要向下移动一个位置，共需要移动n－i＋1个元素。设在第i个位置上作插入的概率为Pi，则平均移动数据元素的次数：由于1≤i≤n+1，共有n＋1个位置可以插入，即在等概率情况下pi=1/(n+1)，则：因此在顺序表上作插入运算，该算法的时间复杂度为Ｏ(n)。数据结构第二章－－线性表安工大计算机学院6.顺序表的删除运算顺序表的删除运算是指将表中第i个元素从线性表中去掉，删除后使原表长为n的线性表：(e1，e2，...，ei-1，ei，ei+1，...，en)变为表长为n-1的线性表：(e1，e2，...，ei-1，ei+1，...，en)其中i：1≤i≤n。在顺序表上完成删除操作的算法步骤如下：（1）检查表是否存在，若不存在退出；（2）检查删除位置的合法性（i是否为1≤i≤length）若不满足，退出；（3）将ei+1～en顺序向上移动一位，ei+1占据ei位置，……（注意数据的移动方向）；（4）修改表长；数据结构第二章－－线性表安工大计算机学院intDelete_SeqList(PSeqListSeqListPoint，inti){/*顺序表删除，入口参数：顺序表指针，删除元素位置，返回标志1表示成功，0表示删除位置不合法，-1表示表不存在*/intj;if(!SeqListPoint){printf(＂表不存在＂);return(-1);/*表不存在，不能删除元素*/}if(i1||iSeqListPoint-length)/*检查删除位置的合法性*/{printf(＂删除位置不合法＂);return(0);}for(j=i;jSeqListPoint-length;j++)SeqListPoint-data[j-1]=SeqListPoint-data[j];/*向上移动*/SeqListPoint-length--;return(1);/*删除成功*/}数据结构第二章－－线性表安工大计算机学院删除算法的分析在进行删除操作时，若假定删除每个元素的可能性均等，则平均移动元素的个数为：分析结论顺序存储结构表示的线性