第3章-线性表ppt课件

.,第三章线性表,3.1线性表的定义和基本操作3.2线性表的顺序存储结构3.3线性表的链式存储结构3.4线性表的应用举例,本章主要内容,3.1线性表的定义和基本操作,线性表的定义线性表是由n（n0）个类型相同的数据元素组成的有限序列。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)数据元素类型为下列所示的结构类型：structbookinfointNo;/图书编号char*name;/图书名称char*auther;/作者名称.;在现实中，这种类型的数据结构很多很多，如学生档案学籍系统、图书管理系统、仓库管理系统、设备管理系统等,线性表的基本操作,1.初始化线性表LvoidInitList()2.求线性表的长度：intLength()3.取表元：DataTypeGet(inti)4.按值查找：intLocate(DataTypex)5.插入操作：intInsert(DataTypex,inti)6.删除操作：intDeleted(inti),返回,2.2线性表的顺序存储结构,顺序存储结构指用一组连续的存储单元依次存储线性表中的每个数据元素。如右图所示：,说明：L为每个数据元素所占据的存储单元数目。,顺序表元素在内存的存储地址,相邻两个数据元素的存储位置计算公式LOC(ai+1)=LOC(ai)+L线性表中任意一个数据元素的存储位置的计算公式为：LOC(ai+1)=LOC(a1)+(i-1)*L,顺序存储结构的特点,逻辑与物理一致：逻辑上相邻，物理上也相邻利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系随机存取：可以利用上述给出的数学公式，快速地计算出任何一个数据元素的存储地址,顺序存储结构的类型定义,在C+中，线性表的顺序存储定义如下:,#defineMAXSIZE100typedefintDataType;classSequenListpublic:voidInitiate();intLength();intInsert(DataTypex,inti);intDeleted(inti);intLocate(DataTypex);DataTypeGet(inti);private:DataTypedataMAXSIZE;intlen;,典型操作的算法实现,1.顺序表的初始化顺序表的初始化即构造一个数据元素个数为0的空表，算法如下:算法3-1顺序表的初始化voidSequenList:Initiate()len=0;,典型操作的算法实现,2.插入运算插入运算是指在顺序表的第i个位置上插入一个值为x的新元素，插入后使原表为n的顺序表（a1，a2，ai-1，ai，ai+1，an）变为表长为n+1的顺序表（a1，a2，ai-1，x，ai，ai+1，an）其中，i的合理取值范围为1in+1。,intSequenList:Insert(DataTypex,inti)/在线性表的第i个数据元素之前插入一个新的数据元素xintj;if(len=MAXSIZE)coutlen+1)/如果插入位置不合法cout=i;j-)dataj=dataj-1;/元素后移datai-1=x;/插入元素len+;/表长度增加1return1;,插入算法的时间性能分析：时间主要消耗在数据元素的移动上。在第i个位置上插入x，从第i个到第n个元素都要向后移动一个位置，共需要移动n-(i-1)，即n-i1个数据元素。而i的取值范围为1in+1，即有n1个位置可以插入。设在第i个位置上做插入操作的概率为Pi，则平均移动数据元素的次数为：在等概率情况下，Pi=1/(n+1)，则,时间复杂度为O(n),典型操作的算法实现,3.删除运算线性表的删除运算是指将表中第i个元素从线性表中删除，使原表长为n的线性表（a1，a2，ai-1，ai，ai+1，an）变成表长为n-1的线性表（a1，a2，ai-1，ai+1，an）i的取值范围为1in。,在顺序表上完成删除运算的步骤如下:（1）将数据元素ai+1an依次向前移动一个位置。（2）修改len值，使之仍指向最后一个数据元素的下一个位置。,intSequenList:Deleted(inti)/删除顺序表的第i个数据元素intj;if(ilen)/若删除位置不合法coutpositionisnotcorrect!endl;return0;elsefor(j=i;jlen;j+)dataj-1=dataj;/元素前移len-;/表长度减1return1;,本算法应注意以下问题,（1）删除第i个数据元素，i的取值为1in（即len），否则第i个元素不存在。因此，要检查删除位置的有效性。（2）删除ai之后，该数据不再存在；如果需要，可先取出ai，再做删除。,删除算法的时间性能分析：,与插入运算相同，其时间主要消耗在移动表中元素上。删除第i个元素时，其后面的元素ai+1an都要向前移动一个位置，共移动n-i个元素，所以平均移动数据元素的次数为在等概率情况下，Pi=1/n，则这说明，在顺序表上做删除运算时大约需要移动表中一半元素。显然，该算法的时间复杂度为O(n)。,典型操作的算法实现,4.按值查找在线性表中查找与给定值相等的数据元素。方法是：从第一个元素a1起依次和比较，直到找到值相等的数据元素，返回它在顺序表中的位置值（下标+1）；或者查遍整个表都没有找到，返回0。,intSequenList:Locate(DataTypex)/返回值为x的数据元素的位序值intj=0;while(jlen),算法主要运算是比较。次数与x在表中的位置有关，也与表长有关。当a1=x时，比较一次成功；当an=x时，比较n次成功。在查找成功的情况下，平均比较次数为（n+1）/2，时间复杂度为O(n),返回,顺序表查询算法,intLocation_SeqList(PSeqListPL,DataTypex)/*顺序表检索，入口参数：为顺序表指针，检索元素，返回元素位置，-1表示表不存在，0表示查找失败*/inti=0;if(!PL)printf(表不存在);return(-1);/*表不存在，不能检索*/while(ilength,典型操作的算法实现,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：1in+1。,(1)检查待插入的表是否存在，若不存在退出；(2)判断顺序表是否满(即表长length是否大于等于MAXSIZE)？若满，退出；否则执行(3)；(3)检查插入位置的合法性(i满足1=MAXSIZE)printf(“表溢出”);return(-1);/*表空间已满，不能插入*/if(iPL-length+1)/*检查插入位置的合法性*/printf(“插入位置不合法”);return(0);for(j=PL-length-1;j=i-1;j-)PL-dataj+1=PL-dataj;/*移动元素*/PL-datai-1=x;/*新元素插入*/PL-length+;/*表长加1*/return(1);/*插入成功，返回*/,设插入的位置为i，则把ei到en元素向后移动一个位置共需要移动ni1个元素。设在第i个位置上作插入的概率为Pi，由于1in+1，共有n1个位置可以插入，即在情况下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：1in。,删除前,删除后,删除的操作步骤:,（1）检查表是否存在，若不存在退出（2）检查删除位置的合法性（i是否为1ilength）若不满足，退出（3）将ei+1en顺序向上移动一位，ei+1占据ei位置，（注意数据的移动方向）（4）修改表长,顺序表删除算法,intDelete_SeqList(PSeqListPL，inti)/*顺序表删除，入口参数：顺序表指针，删除元素位置，返回标志1表示成功，0表示删除位置不合法，-1表示表不存在*/intj;if(!PL)printf(表不存在);return(-1);/*表不存在，不能删除元素*/if(iPL-length)/*检查删除位置的合法性*/printf(删除位置不合法);return(0);for(j=i;jlength;j+)PL-dataj-1=PL-dataj;/*向上移动*/PL-length-;return(1);/*删除成功*/,删除算法的效率分析,在进行删除操作时，若假定删除每个元素的可能性均等，则平均移动元素的个数为：,结论,顺序存储结构表示的线性表，在做插入或删除操作时，平均需要移动大约一半的数据元素当线性表的数据元素量较大，并且经常要对其做插入或删除操作时，消耗的时间代价较大,返回,2.3线性表的链式存储结构,线性表顺序存储结构的优点：逻辑上相邻、物理上相邻，结构简单可以根据元素的下标存取，速度便捷线性表顺序存储结构的缺点：在做插入或删除元素的操作时，会产生大量的数据元素移动对于长度变化较大的线性表，要一次性地分配足够的存储空间，但这些空间常常又得不到充分的利用线性表的容量难以扩充,线性表的链式存储,逻辑上相邻的元素之间的物理位置是通过指针的指向来实现的，这种指向一般是通过的动态的地址指针来实现的（也可以通过静态的伪地址指针来实现）每个数据元素不仅要表示它的具体内容，还要附加一个表示它的直接后继元素存储位置的信息,线性表链式存储结构示意图,链式存储,表示每个数据元素的两部分信息组合在一起被称为结点,其中表示数据元素内容的部分被称为数据域data；表示直接后继元素存储地址的部分被称为指针或指针域next单链表中最后一个结点没有直接后继结点，它的指针域放入一个特殊的值NULL为了简化对链表的操作，人们经常在链表的第一个结点之前附加一个结点，并称为头结点,链式存储结构的特点线性表中的数据元素在存储单元中的存放顺序与逻辑顺序不一定一致通过头指针进入链表，通过结点的指针域访问后继结点，寻找第一个结点和寻找最后一个结点所花费的时间不等，存取方式被为顺序存取方式,对比顺序存储为随即存取方式,链式存储,链式存储的几种形式,单链表循环链表双向链表,typedefintDataType;classItempublic:DataTypedata;Item*next;Item()next=NULL;,单链表的定义,classLinkpublic:Item*head;Link()head=NULL;Link()DeleteAll();voidInitiate();voidDeleteAll();voidHeadCreate(intn);voidTailCreate(intn);voidHeadCreateWithHead(intn);voidTailCreateWithHead(intn);intLength();Item*Locatex(DataTypex);Item*Locatei(inti);DataTypeGet(inti);boolInsert(DataTypex,inti);boolDeleted(inti);voidPrint();,单链表的逻辑结构示意图,单链表的几种形态,单链表的基本操作,1.初始化,voidLink:Initiate()DeleteAll();head=NULL;,2.建立单链表,（1）从表尾到表头建立单链表（不带有空白头结点）,voidLink:HeadCreate(intn)DeleteAll();Item*s,*p;inti;p=NULL;for(i=1;is-data;s-next=p;p=s;head=p;,（2）从表头到表尾建立单链表（不带有空白头结点）,头,voidLink:TailCreate(intn)Item*s,*r,*p;inti;DeleteAll();p=NULL;for(i=1;is-data;s-next=NULL;if(p=NULL)p=r=s;elser-next=s;r=s;head=p;,（3）从表尾到表头建立单链表（带有空白头结点）,voidLink:HeadCreateWithHead(intn)Item*s,*p;inti;DeleteAll();p=newItem();p-next=NULL;for(i=1;is-data;s-next=p-next;p-next=s;head=p;,（4）从表头到表尾建立单链表（带有空白头结点）,voidLink:TailCreateWithHead(intn)Item*s,*r,*p;inti;DeleteAll();p=newItem();p-next=NULL;r=p;for(i=1;is-data;r-next=s;r=s;,r-next=NULL;head=p;,3求表长设定一个移动指针p和计数器j，初始化后，p所指结点后面若还有结点，p向后移动，计数器加1。,intLink:Length()intj;Item*p;j=1;p=head-next;while(p!=NULL)j+;p=p-next;return-j;,4查找操作,（1）按序号查找从单链表的第一个元素结点起，判断当前结点是否是第i个，若是，则返回该结点的指针；否则继续下一个结点的查找，直到表结束为止。若没有第i个结点，则返回空；如果i=0；则返回头指针。,Item*Link:Locatei(inti)intj=1;Item*p;if(i=0)returnhead;p=head-next;while(p!=NULL),（2）按值查找即定位从链表的第一个元素结点起，判断当前结点值是否等于，若是，返回该结点的指针，否则继续下一个结点的查找，直到表结束为止。若找不到，则返回空。,Item*Link:Locatex(DataTypex)Item*p;p=head-next;while(p!=NULL),（3）读取第i个位置上的元素值,DataTypeLink:Get(inti)intj;Item*p;j=1;p=head-next;while(jnext;,if(p=NULL)|(ji)coutdata;,5插入(前插),设p指向链表中某结点，s指向待插入的值为x的新结点，将*s插入*p的前面,插入算法找到第i-1个结点；若存在，继续步骤，否则结束。申请新结点，将数据填入新结点的数据域。将新结点插入。,boolLink:Insert(DataTypex,inti)Item*p,*s;p=Locatei(i-1);if(p=NULL)coutdata=x;s-next=p-next;p-next=s;returntrue;,返回,循环链表,循环链表为空的情形,特点：1.可以通过链表中任意节点遍历整个链表2.可以通过尾指针访问到头节点3.循环链表的操作基本上和单链表相同,返回,双向链表,双向链表的节点定义,typedefintDataType;classDualItempublic:DataTypedata;DualItem*next;DualItem*prior;DualItem()next=NULL;prior=NULL;,双向链表的节点插入,设p指向双向链表中某结点，s指向待插入的值为x的新结点，将*s插入到*p的前面，步骤如下：s-prior=p-prior;p-prior-next=s;s-next=p;p-prior=s;,双向链表的节点删除,设p指向双向链表中某结点，删除*p。操作示意图如图2-17所示。操作步骤如下：p-prior-next=p-next;p-next-prior=p-prior;free(p),1、2的顺序可以调换,返回,2.3线性表的应用举例,1.要求在时间复杂度为O(n)的条件下将顺序表（a1，a2,an）重新排列为以a1为界的两部分：a1前面的值都比a1小，a1后面的值都比a1大,定义i、j分别指向第一个元素和最后一个元素，从最后一个元素aj开始逐一向前扫描每一