数据结构之线性表课件.ppt

单击此处编辑母版标题样式,*,*,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,数据结构,第,二,章 线性表,第,二,章 线性表,知 识 点,线性数据结构的基本特征和基本运算,线性表的存储结构,双向链表,循环链表,难 点,循环链表,利用本章的基本知识设计有效的算法解决与线性相关的应用问题,要 求,熟练掌握以下内容：,线性表的基本运算,线性表的特征、基本运算并能设计简单算法,了解以下内容：,线性表运算时间复杂性分析,第,二,章,目录,2.1 线性表的逻辑结构,2.2 线性表的顺序存储,2.3 线性表的链式存储,2.4 循环链表,2.5 双向链表,小 结,习题与练习,2,线性表,（,Linear List,）,线性表是由有限数目的相同类型元素组成的序列。,表中的数据元素,除了第一个和最后一个以外，都有一个且只有一个前驱元素，同时也都有一个且只有一个后继元素；,第一个元素只有一个后继元素而无前驱元素；最后一个元素只有一个前驱元素而无后继元素。,线性表的元素个数n称为这个表的长度，当n=0时，这个表叫做空表。,线性表在计算机内存中采用各元素顺序存储的方式，这种存储结构叫做向量。,每个线性表元素叫做这个向量的一个分量。,如果已知线性表第一个元素的地址和每个元素占用的存储单元数，由任一元素的序号就可以计算出该元素在内存中的地址。,在编程时以一维数组表示线性表最简单，用的也最普遍。,2.1线性表的逻辑结构,线性表的定义,例：Monday,Tuesday，Wednesday，,Thursday，Friday，Saturday，,Sunday,又 Score=sdudent1，50，student2，60，student3，70 注意线性表和集合的区别。,线性表元素之间是有序的，而集合元素,之间是无序的。,2.1线性表的逻辑结构,线性表的基本运算：,1.求线性表的长度n；,2.在第i个数据元素前面插入一个新的数据元素；,3.删除第i个数据元素；,4.存取或更新线性表第i个元素；,5.将两个或两个以上的线性表合并成一个线性表；,6.将一个线性表拆成多个线性表；,7.将线性表中各数据元素按某个域值（如关键字）递增或递减的顺序重新排列；,8.在线性表中查找满足某种条件的数据元素；,2.2 线性表的顺序存储,线性表的顺序存储结构(顺序表）,例：一顺序表 A=（3，6，8，9，2）,顺序存放在一维数组中,顺序存储的特点：,逻辑顺序与物理顺序一致，,元素之间的关系由物理位置的相邻关系体现,3,6,8,9,2,2.2 线性表的顺序存储,地址计算,设顺序表的每个元素占c个存储单元，并且元素所占的第一个单元的存储地址作为顺序表的存储位置，则顺序表中第I个元素的存储位置,Loc（ai）满足,Loc（ai）=Loc（ai-1）+c,Loc（ai）=Loc（a1）+（i-1）*c,2.2 线性表的顺序存储,结点描述,#define Maxlen,typedef struct seqenlist,elementtype elements maxlen;,int lenth;,list;,顺序存储下线性表的运算,1.,数据元素的插入,(insert),在顺序表L=（a1,a2,ai,an）中第i个元素前插入元素b，使成为,L=（a1,a2,b,ai,an）,基本思想,：把顺序表表中第I个元素至第n个元素后移一个位置，把元素b插入到第i个位置上，线性表的长度加1。,插入函数,int insert(list L,int i,elementtype x),int k;,if(iL.lenth+1),printf(“i值错！n”);,else,for(k=L.lenth;k=i-1;k-),L.elementsk=L.elementsk-1;,/*将第i个元素及其后面的元素后移*/,L.elementsi-1=x;,L.length+;/*顺序表长度加1*/,return(0);,插入函数分析,在循环语句中，当i=1时，须循环n次，表示元素插入线性表头的前面，则原线性表中n个元素均须向后移动一个单元，这是最不利的情况。,当i=n+1时，则循环一次也不进行，这时元素直接插入到线性表尾的后面，所以线性表的所有n个元素均不移动，这是最好的情况。,2.,元素的删除(Delete),在顺序表L=（a1,a2,ai,an）中删除第i个结点，使成为,L=（a1,a2,ai-1,ai+1,an）,基本思想,：要求删除第i个数据元素，由于线性表元素在数组中必须连续排列，中间不能有空单元，,故将此元素删除后，它后面的所有元素都需要向前移动一个单元，且数据元素总数由原来的n减少到n-1.,删除,函数,Int delete(list L,int i)/*删除顺序表中第I个结点,int k；,if(iL.lenth),printf(“i值错！n”);,else,for(k=i;kL.lenth；k+),L.elementsk-1=L.elementsk;/*I以后的元,L.lenth-;/*素前移,return(0),删除,函数分析,在循环语句中，当i=1时，需循环(n-1)次，这是要删除线性表表头元素，是最不利的情况；,当i=n时，则循环一次也不执行，只是将元素数目n比原来减少一个，而第n个数据元素不必再考虑，其余的各单元的元素均维持不变，这是最好的情况。,算法的时间复杂性,可以用数据元素的移动次数来度量这两个算法的时间复杂性。,插入时，最少循环0次，最多循环n次，如i的各种取值概率相同，则平均循环次数为n/2；,删除时最少的循环次数为0次，最多为n-1次，当i取值概率相同时，平均循环次数为(n-1)/2。,用数量级的形式表示线性表插入、删除运算的时间复杂性均为O(n)。,3.查找定位删除操作,删除一个值为X的元素,基本思想,：在线性表中，查找到值为X的元素ai，将 i 之后的元素前移一个位置，且线性表的长度减1。,Int LocateDeleteSeqlist(list sl;elementtype：x),Int I=0,j;/*删除值为X的元素,IF（sl.lenth=0)printf(“空表！n”);,While(Isl.lenth),If(sl.elementsI!=x),I+;,else for(j=I+1;j=L.lenth),printf(“i值错！n”);,return(0);,顺序表的应用举例,2.3,线性表的链式存储,2.1 单链表,结点,:在链式存储结构中，结点不仅存放数据元素的值，还附加一个指针（链），用来指向该结点的直接后继结点。,其中，data部分称为数据域，用于存储线性表的一个元素，next部分称为指针域或链域，用于存放一个指针，即存放该结点的直接后继结点的地址。,所有结点通过指针的链接而构成的线性表称为单链表。线性表（a,1,，a,2,，a,n,，）的单链表可直观地画成：,head是单链表的头指针，指向开始结点a,1,a,n,是终端结点，其指针域为空，不指向任何结点。,一个单链表由头指针head唯一标识和确定，因此，可用头指针来命名单链表。,单链表的类型定义,单链表的的结点类型定义如下：,typedef struct Lnode,elementtype data;,struct lnode*next；,linklist,一个结点是由两个域data和next组成的记录,data是结点的数据域，next是结点的链域。,链表举例,空表,H,a1,an,为了编程方便，一般在单链表的第一个结点之前加一个“头结点”，如：,当为空表时，即head-next=null,如下图。,a1,an,head,head,指针的概念,假设p是一个pointer类型，应正确区分指针型变量、指针、指针所指的结点和结点的内容这四个密切相关的不同概念：,p的值（如果有的话）是一个指针，即是一个所指结点的地址。,该指针（若不是NULL）指向的某个node型结点用*p来标识。,结点*p是由两个域组成的记录，这两个域分别用p,data域和p,next域来标识，它们各有自己的值，p,data的值是一个数据元素，p,next的值是一个指针。,2.3.2,单链表的基本运算,1.遍历(Traversal)：根据已给的表头指针，按由前向后的次序访问单链表的各个结点。,在实际应用中遍历是对单链表的最基本运算，例如，当要打印或显示出各个结点的数值域值、计算单链表的长度(即结点数目)或寻找某一个结点时都需要遍历单链表。,假设head是单链表的头指针，计算一个已建立好的单链表的结点个数的算法如下：,计算结点个数算法,int length(head)/*求表head的长度*/,int count=0;/*计数器置初值*/,p=head;/*p指向头结点*/,while(p!=NULL),p=p,-,next;,count+;,return(count);/*返回表长值*/,算法分析,此算法的关键是while循环语句，开始时p指针指向头结点，每一循环都修改指针值，让它指向下一个结点，同时将计数链表长度的变量count加1。,这样每循环一次就向后推移一个结点，直到p所指结点*p的链域值为NULL为止。,空指针NULL起标志的作用，若无此标志，尾结点链域的值为“无定义”，上述算法中的while语句在做最后一次判断时将出现“运行错”，这是应予避免的。,2.插入,所谓插入是指在单链表中第i个结点(i0)之后插入一个元素为x的结点。,实现插入算法主要完成三个基本操作：,1)在单链表上找到插入位置，即找到第i个结点。,可以用遍历的方法，即从表头起顺次访问单链表的结点，直至找到第i个结点。,2)生成一个以x为值的新结点。,可通过C的库函数malloc(size)来产生。,3)将新结点链入单链表中。,需要改变相关结点的指针，如下面的图所示。,假设指针p指向单链表中的第i个结点，指针s指向已生成的新结点，链入新结点的操作如下：,将新结点*s的链域指向结点*p的后继结点,(即s-next=p-next)；,将结点*p的链域指向新结点(即p-next=s)。,insert(head)/*在第i个结点,后,插入结点S,linklist*p=head;int k=0;,while(p!=null)$(knext;,k=k+1;,s=(linklist*)malloc(sizeof(linklist),if(s=null),printf(“没有足够的空间”),Return(null),s-next=p-next;,p-next=s;,return(head),插入算法,Linklist*insertllist(head,x,k)/在头指针为 linklist*head;head的单链表的第K个,elementtype x;结点之,前,插入X,int k;,linklist*p,*pre,*s;,int j=1;p=head；pre=null;,while(p!=null)$(jnext;/*结点pre,j+,插入算法续,if(j!=k),printf(“k超出链表的长度”);,return(null);,s=(linklist*)malloc(sizeof(listlist),if(s=null),printf(“没有足够的空间”),Return(null),插入算法续,s-data=x;,If(pre=null)/*插入的结点位于链,s-next=head;/*表的头部，即k=1,head=s;,else s-next=p;,pre-next=s;,return(head),3.删除,假设单链表,带有头结点,，头指针为head，删除单链表上一个,其值为x的结点,。主要操作,是：,1)用遍历的方法在单链表上找到该结点；,2)从单链表上删除该结点。,欲从单链表上删除一个结点，需修改该结点的前一个结点的指针，如下面的图所示。,假设指针q指向待删除结点的前一个结点，指针p指向要删除的结点，删除该结点的操作如下：将该结点的前一个结点*q的链域指向*p的后继结点（即q-next=p-next）。,删除算法,Linklist*Delete(head,x),linklist*head;elementtype x;,linklist*q,*p;,q=head;,p=head-next;,while(p!=null)&(p-data!=x),q=p;,p=p-next;,删除算法续,if,(p=NULL),printf(“x不存在”),return(null);,else,q-next=p-next;/*修改指针,free(p);,return(head);,返回,2.3.3 静态链表,在某些语言中，没有指针类型，就不能实现链表，可用一数组来模拟链表，这就是静态链表。,静态链表的定义,#define maxsize,typedef struct,elementtype data;,int next;,slinklist;,如：slinklist slmaxsize;,定义了一个有maxsize个元素的数组，每个元素由信息域和指针域组成。,例：L=（a，b，c，d，e，f），,0 0,1 1,2 2,3 3,4 4,5 5,6 6 插入h之后,0,1,a,2,b,3,c,4,d,5,e,6,f,0,0,1,a,2,b,7,c,4,d,5,e,6,f,0,h,3,2.3.4 线性表实现方法比较,链表：在已知元素个数的情况下，浪费空间；,在未知元素个数的情况下，节约空间；,速度快。,顺序表：在已知元素个数的情况下，空间利用率,高；,在未知元素个数的情况下，可能浪费空,间，利用率低；,速度慢。,2.4,循环链表,循环链表（circular linked list）是一种首尾相接的链表，将单链表表尾结点原来的空指针改为指向表头结点，就成为循环链表。,循环链表并不多占存储单元，但从循环链表的任一个结点出发都可以访问到此链表的每一个结点，因为当访问到表尾结点后又能返回到头结点。,1.,带头结点的循环链表,通常在循环链表的表头结点前面再加一个空结点,也叫空表头结点。,表空时空表头结点的指针指向其本身，如下面的图所示为空循环链表。,空表头结点除指针以外的数据域是没有用的，但为了将此结点与一般结点相区别，常常是将其赋以一个特别的数据，以与一般结点相区别。,若p-next=head，则p就是指向最后一个结点；,若head-next=head，则为空表。,例：约瑟夫（Josephus）问题。设编号为1,2,n(n0)个人，按顺时针围坐一圈，每人有一正整数密码m。,首先给定一正整数m，从第1个人开始(顺时针），枪毙第m个人，之后，以该人的密码作为m的新值，继续下去,基本思想：,首先建立一个带头结点，有n个结点的循环链表，头指针为head;,对给定的m（第1次给定m，以后即为结点的pwd），从第一个结点开始，寻找第m个结点，将其输出，并取出该结点的pwd，执行m=pwd；从下一个结点继续寻找第m个结点,直到表空为止。,结点定义为：,Typedef struct Jnode,int no;,int pwd;,struct Jnode*next;,clinklist;,Int josephus_seqlist(pseqlist josephus_sq,int s,m),/*顺序存储在josephus_sq中，从第s个元素开始,s1=s-1;,for(i=josephus_seq-length;i0;i-),s1=(s1+m-1)%i;,w=josephus_seq-datas1;,printf(“”,w);,delete_seqlist(josephus_seq,s1+1),2.,带尾指针的循环链表,另一种方法是不设头指针而改设尾指针，这样无论是找头结点还是尾结点都很方便。因为尾结点由尾指针rear来指示，则头结点的位置是rear-next-next。,2.5,双向链表,双向链表中每个结点除了有向后指针外，还有指向其前一个结点的指针，这样形成的链表中有两条不同方向的链，因此从某一结点均可向两个方向访问。,双链表的结点形式为：,其中链域prior和next分别指向本结点的直接前趋和直接后继结点。,如果循环链表的结点再采用双向指针，就成为,双向循环链表,。,双向链表为空链表时，,head,即 head-next=null,双链表较单链表虽然要多占用一些存储单元，但对其插入和删除操作以及查找结点的前趋和后继都非常方便。,双链表结构是一种对称结构，设指针p指向双链表的某一结点，则双链表的对称性可用下式来表示：,p=(p-prior)-next=(p-next)-prior,即结点*p的地址存放在其前趋结点,*(p-prior)的后继指针域中，又存放在它的后继结点*(p-next)的前趋指针域中。,结点定义为：,Typedef struct dbnode,elementtype data;,struct dbnode*prior;,struct dbnode*next;,Dblinklist;,1.,双链表的插入,设要在p所指结点的,前面,插入一个新结点*q，则需要修改4个指针：,q-prior=p-prior;,q-next=p;,(p-prior)-next=q;,p-prior=q;,2.,双链表的删除,设p指向待删除的结点，则删除该结点步骤为：,(p-prior)-next=p-next;,(p-next)-prior=p-prior;,这两个语句的执行顺序可以颠倒，执行这两个语句之后，可调用free(p),将*p结点释放。,2.6 多项式的加法,运算规则,将二个一元多项式中所有指数相同项的系数相加，相加后，若和不为零，则构造“和多项式”中的一项；,若和为零，则“和多项式”中无此项；,所有指数不相同的项均考贝到“和多项式”中。,1,.,如果用,数组来表示一元多项式,，以各项的指数作为下标，将各个系数存入一维数组中。,设一个一元多项式为,2.用,单链表表,示一元多项式,将单链表的每个结点对应着一元多项式中的一个非零项，它由三个域组成，分别表示非零项的系数、指数和指向下一个结点的指针。,求此两多项式之和C(x)=A(x)+B(x)。,结点的定义如下：typedef struct pnode,real coef;,Int exp;,Struct pnode*next;,polyn;,把多项式B(x)加到A(x)中。,基本思想,：设A和B为多项式A和B的搜索指针，比较其指数项，,若A-expexp,则A结点应是和多项式中的一项，A后移；,若A-expB-exp,将B结点插入到A结点之前，B后移；,若A-exp=B-exp,则两结点的系数相加，若和不为0，修改A结点的系数，A,B后移；若为0，删除两结点。A,B后移。,例,3.1,一个单链表L(至少有一个结点)，其头结点指针为head，编写一个函数将L倒置。,基本思想：从头到尾遍历单链表L，并设置3个附加指针p、q、r,p指向当前处理的结点，q指向p的后继，r指向q的后继，q、r的作用是为了防止倒置指针时，下一个结点丢失而设置的。,最后将第一个结点的next域置为NULL，并将头指针指向最后一个结点。,例,3.1算法,void invert(node*head),node*p,*q,*r;,p=head;,q=p-next;,while(q!=NULL)/*没有后继时停止*/,r=q-next;,q-next=p;,p=q;,q=r;,head-next=NULL;,head=p;,例,3.2,有两个循环单链表，头指针分为head,1,和head,2,，编写函数将链表head,2,链接到链表head,1,之后，链接后的链表仍保持是循环链表的形式。,解：先找到两个表的表尾，将head,2,放入链表head,1,的表尾，然后将head,1,放入原head,2,链表的表尾。,例,3.2算法,link(node*head1,*head2),node*p,*q;,p=head1;,while(p-next!=head1),p=p-next;,q=head2;,while(q-next!=head2),q=q-next;,p-next=head2;,q-next=head1;,例,3.3,给出在双链表中第i个结点(i0)之后插入一个元素为x的结点的函数。,解：在前面双链表一节中，已经给出了在一个结点之前插入一个新结点的方法，在一个结点之后插入一个新结点的思想与前面是一样的。,例,3.3算法,void insert(dnode*head,int i,x),dnode*s,*p;,int j;,s=(dnode*)malloc(sizeof(dnode);,/*建立一个待插入的结点，由s指向*/,s-data=x;,if(i=0),/*如i=0,将s所指结点插入到表头后返回*/,s-next=head;,head-prior=s;,head=s;,例,3.3算法续,else,p=head;,/*查找第i个结点，由p指向*/,j=1;,while(p!=NULL&jnext;,if(p!=NULL),/*若查找成功，把s插入到p之后*/,if(p-next=NULL),/*若p是最后一个结点，则直接把s结点链入*/,例,3.3算法续,p-next=s;,s-next=NULL;,s-prior=p;,else,s-next=p-next;,p-next-prior=s;,p-next=s;,s-prior=p;,else,printf(“未找到!n”);,返回,小结,单链表,循环链表,双向链表,双向循环链表,十字链表,返回,习题与练习,一、基础知识题,1.试比较顺序表与链表的优缺点。,2.试分析单链表与双链表的优缺点。,3.为什么在单循环链表中设置尾指针比设置头指针更好？,4.写出在循环双链表中的p所指结点之后插入一个s所指结点的操作。,5.写出在单链表中的p所指结点之前插入一个s所指结点的操作。,6.请利用链表来表示下面一元多项式,二、算法设计题,1.有一个有n个结点的单链表，设计一个函数将第i-1个结点与第i个结点互换，但指针不变。,2.设计一个函数，查找单链表中数值为x的结点。,3.已知一个单链表，编写一个删除其值为x的结点的前趋结点的算法。,4.已知一个单链表，编写一个函数从此单链表中删除自第i个元素起的length个元素。,5.,已知一个递增有序的单链表，编写一个函数向该单链表中插入一个元素为x的结点，使插入后该链表仍然递增有序。,6.已知一个单链表，编写一个函数将此单链表复制一个拷贝。,7.有一个共10个结点的单链表，试设计一个函数将此单链表分为两个结点数相等的单链表。,8.与上题相同的单链表，设计一个函数，将此单链表分成两个单链表，要求其中一个仍以原表头指针head,1,作表头指针，表中顺序包括原线性表的第一、三等奇数号结点；另一个链表以head,2,为表头指针，表中顺序包括原单链表第二、四等号结点。,9.已知一个指针p指向单循环链表中的一个结点，编写一个对此单循环链表进行遍历的算法。,10.已知一个单循环链表，编写一个函数，将所有箭头方向取反。,11.在双链表中，若仅知道指针p指向某个结点，不知头指针，能否根据p遍历整个链表？若能，试设计算法实现。,12.试编写一个在循环双向链表中进行删除操作的算法，要求删除的结点是指定结点p的前趋结点。,