数据结构之线性表

第二章线性表,DATASTRUCTURE,数据结构,引言线性表是一种线性数据结构，其用途非常广泛，用于信息检索、存储管理、模拟技术、通信等领域。,内容提要1、定义线性表抽象数据类型；2、讨论线性表的顺序存储表示方法；3、讨论单链表、循环链表等链接存储表示方法；4、线性表的应用实例多项式的算术运算。,2.1线性表抽象数据类型,课堂提要第2章线性表2.1线性表ADT2.2线性表的顺序表示2.3线性表的链接表示2.4多项式的算术运算,1.线性表举例,线性表是n(0)个元素a0，a1，an-1的有序集合，记为（a0，a1，an-1）其中，n是线性表中元素的个数，称为线性表的长度，n=0时称为空表。,设ai是线性表（a0，a1，an-1）中第i个元素，i=0,1,n-1，则称ai是ai+1的直接前驱元素，ai+1是ai的直接后继元素。线性表是动态数据结构，它的表长可以改变。,2.线性表的定义,ADT2.1线性表抽象数据类型ADTLinearListData:零个或多个元素的有序集合。Operations:Create()：创建一个空线性表。Destroy()：撤消一个线性表。IsEmpty()：若线性表空，则返回true；否则返回false。Length()：返回表中元素个数。Find(i,x)：在x中返回表中下标为i的元素ai(即表中第i+1个元素)。如果不存在，则返回false，否则返回true。Search(x)：返回x在表中的下标；若x不在表中，则返回-1。Insert(i,x)：在元素ai之后插入x。若i=-1，则x插在第一个元素a0前。插入成功返回true，否则返回false。Delete(i)：删除元素ai。删除成功返回true，否则返回false。Update(i,x)：将元素ai的值修改为x。修改成功返回true，否则返回false。Output(out)：把表送至输出流。,3.线性表抽象数据类型,4.线性表的C+模板抽象类,程序2.1线性表的C+类templateclassLinearListpublic:virtualboolIsEmpty()const=0;virtualintLength()const=0;virtualboolFind(inti,T,2.2线性表的顺序表示,1.线性表的两种存储表示法(1)顺序表示法(2)链接表示法2.线性表的顺序表示法是用一组地址连续的存储单元依次存储线性表中元素。顺序表示的线性表程为顺序表。存储结构是逻辑结构在机内的映象，包括：元素和关系。,课堂提要第2章线性表2.1线性表ADT2.2线性表的顺序表示2.3线性表的链接表示2.4多项式的算术运算,（1）线性表的顺序表示法,若已知顺序表示的线性表中每个元素占k个存储单元，第一个元素a0在计算机内存中的地址是loc(a0)，则表中任意一个元素ai在内存中的存储地址loc(ai)为loc(ai)=loc(a0)+i*k只要给定loc(a0)和k，就可以确定线性表中任意一个元素的存储地址，换句话说，顺序表是一种随机存取结构。,（2）地址计算公式：,3.顺序表类,程序2.1线性表的C+类templateclassLinearListpublic:virtualboolIsEmpty()const=0;virtualintLength()const=0;virtualboolFind(inti,T,templateclassSeqList:publicLinearListpublic:SeqList(intmSize);SeqList()Deleteelements;boolIsEmpty()const;intLength()const;boolFind(inti,T,SeqListL(5);/定义了一个有5个整型值的顺序表对象,程序2.2线性表的顺序表实现,classSeqList:publicLinearListpublic:SeqList(intmSize);private:intmaxLength;T*elements;/动态一维数组的指针,4.动态一维数组描述顺序表,顺序表在一维数组中的存储,(1)构造函数/创建一个顺序表templateSeqList:SeqList(intmSize)maxLength=mSize;elements=newTmaxLength;n=0;(2)析构函数/撤消一个顺序表templateSeqList:SeqList()deleteelements;,（1）查找下标为i的元素aiFind(i,x):在x中返回表中下标为i的元素ai(即表中第i+1个元素)。如果不存在，则返回false，否则返回true。,x=elementsi;渐近时间复杂度：O(1),5.在顺序存储表示下实现线性表上定义的操作,templateboolSeqList:Find(inti,T渐近时间复杂度：O(1),（2）插入操作Insert(i,x)：在表中下标为i的元素ai后插入x。若i=-1，则将新元素x插在最前面。若插入成功，返回true；,后移n-i-1个元素,01ii+1i+2n-1maxLength-1,a0a1ai,插入操作,an-1,x,ai+1,插入操作算法：templateboolSeqList:Insert(inti,Tx)if(in-1)couti;j-)elementsj+1=elementsj;elementsi+1=x;n+;returntrue;,分析：设顺序表长度为n，则在位置i（i=-1,0,n-1）后插入一个元素要移动n-i-1个元素。设共有n+1个可插入元素的位置，并设在各位置处插入元素的概率是相等的，即Pi=1/(n+1)，则平均情况下在表中插入元素需要移动元素的个数为：,渐近时间复杂度：O(n),ai,a0ai-1,（3）删除操作Delete(i)：删除元素ai。,0i-1ii+1i+2n-1maxLength-1,删除操作,an-1,ai+1,删除操作算法：templateboolSeqList:Delete(inti)if(!n)coutn-1)coutOutOfBoundsendl;returnfalse;for(intj=i+1;jn;j+)elementsj-1=elementsj;n-;returntrue;,分析:设顺序表长度为n,则删除元素ai（i=0,n-1）,要移动n-i-1元素。若删除表中每个元素的概率是相等的，即Qi=1/n，则平均情况下从表中删除一个元素需要移动元素的个数为：,渐近时间复杂度：O(n),（4）顺序表的应用集合求“并”,求集合A和B的并,两集合求并的算法思想是：置i=0；若i小于集合LB的元素个数，则做，否则转；取出集合LB中i位置的元素x；若x不在集合LA中，则将其插入集合LA的最后位置；i+；转继续结束。,求集合A和B的并,求集合A和B的并,例2.1求集合A和B的并A,分析：集合可以看成是线性表，用顺序表LA和LB分别表示集合A和B，“并”的结果放在LA中。,用顺序表类SeqList实现集合“并”算法的程序，存入头文件seqlistu.h中。#includeseqlist.htemplatevoidUnion(SeqList/其插入集合LA中,#includeseqlistu.hconstintSIZE=20;voidmain()SeqListLA(SIZE);/定义顺序表对象LA，表示集合ASeqListLB(SIZE);/定义顺序表对象LB，表示集合Bfor(inti=0;ilink=p-linkp-link=q,能否对调上述2语句的执行顺序？,不能，会“断链”现象,ai,ai+1,x,p,将q插入p之后:,templateboolSingleList:Insert(inti,Tx)if(in-1)cout*q=newNode;q-element=x;/生成新结点qNode*p=first;for(intj=0;jlink;if(i-1)q-link=p-link；p-link=q;/在p之后插入qelseq-link=first；first=q;/插字第一个元素之前n+;returntrue;,渐近时间复杂度：O(n),（3）删除操作,删除元素ai。(a0,a1,.,ai.,an-1),即删除该元素,删除算法步骤为：从first开始找第i+1个结点，p指向该结点，q指向p之前驱结点;从单链表中删除p；释放p之空间；表长减1。,ai,ai+1,ai-1,q,p,删除时只要修改一个指针：q-link=p-link,删除p:,templateboolSingleList:Delete(inti)if(!n)coutn-1)cout*p=first,*q=first;for(intj=0;jlink;if(i=0)first=first-link;elsep=q-link;q-link=p-link;deletep;n-;returntrue;,渐近时间复杂度：O(n),5.单链表的应用集合求“交”,求集合A和B的并,两集合求交的算法思想是：置i=0；若i小于集合LA中当前元素的个数，则做，否则转；取出集合LA中i位置的元素x；若x不在集合LB中，则将其从集合LA中删除，否则i+；转继续;结束。,求集合A和B的并,例2.2求集合A和B的交A,分析：集合可以看成是线性表，用单链表LA和LB分别表示集合A和B，“交”的结果放在LA中。,#includesinglelist.htemplatevoidIntersection(SingleList/否则i+,2.3.2带表头结点的单链表,上一节介绍的单链表在做插入和删除运算时，要考虑一般情况和特殊情况，用带表头结点的单链表可以简化上述两种算法。,课堂提要第2章线性表2.1线性表ADT2.2线性表的顺序表示2.3线性表的链接表示2.3.1单链表2.3.2带表头结点的单链表2.3.3单循环链表2.3.4双向链表2.4多项式的算术运算,1.带表头结点的单链表,(a0,a1,.,ai.,an-1),在原单链表中增加一个结点，但它的element域中不存放线性表中的任何元素，称该结点为表头结点。,2.带表头结点单链表的构造、插入和删除,（1）构造函数,SingleList:SingleList()first=NULL;n=0;,HeaderList:HeaderList()Node*first=newNode;first-link=NULL;n=0;,（2）插入操作templateboolHeaderList:Insert(inti,Tx)if(in-1)cout*p=first;for(intj=0;jlink;Node*q=newNode;q-element=x;q-link=p-link;p-link=q;n+;returntrue;,（3）删除操作templateboolHeaderList:Delete(inti)if(!n)coutn-1)cout*q=first,*p;for(intj=0;jlink;p=q-link;q-link=p-link;deletep;n-;returntrue;,q,p,例如删除a2,2.3.3单循环链表,1.单循环链表,单循环链表可以从表中任一结点出发访问表中所有结点。,课堂提要第2章线性表2.1线性表ADT2.2线性表的顺序表示2.3线性表的链接表示2.3.1单链表2.3.2带表头结点的单链表2.3.3单循环链表2.3.4双向链表2.4多项式的算术运算,带表头结点的单循环链表,不带表头结点的单循环链表,非空表,a0,a1,a2,an-1,first,非空表,2.3.4双向链表,1.双向链表,(1)双向链表的结点结构,课堂提要第2章线性表2.1线性表ADT2.2线性表的顺序表示2.3线性表的链接表示2.3.1单链表2.3.2带表头结点的单链表2.3.3单循环链表2.3.4双向链表2.4多项式的算术运算,(2)带表头结点的双向循环链表,2.双向链表的插入,插入操作的核心步骤是：(1)DNode*q=newDNode;q-data=x;(2)q-llink=p-llink;q-rlink=p;p-llink-rlink=q;p-llink=q;llink-rlink=p-rlink;p-rlink-llink=p-llink;link的值填入新结点的相应域link=newTerm(c,e,link);returnlink;,关于项结点类的InsertAfter函数的执行过程,申请新项结点存储单元,新项结点,执行q1-InsertAfter(3,14),Term*Term:InsertAfter(intc,inte)link=;returnlink;,这里要搞清楚一个问题：上述函数中，link是指哪个结点的指针域？,314,new,Term(c,e,link),q1的指针域！也就是指向q1后继的q!,关于项结点类的InsertAfter函数的执行过程,q,210,-1,q1,qx,新项结点,执行q1-InsertAfter(3,14),Term*Term:InsertAfter(intc,inte)link=;returnli