收藏 分销(赏)

线性表与字符串-2.ppt

上传人:仙人****88 文档编号:14747334 上传时间:2026-11-13 格式:PPT 页数:57 大小:566KB 下载积分:10 金币
下载 相关
线性表与字符串-2.ppt_第1页
第1页 / 共57页
线性表与字符串-2.ppt_第2页
第2页 / 共57页


点击查看更多>>
资源描述
,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数组,线性表,字符串,第二章 线性表和字符串,数组,二元组,的一个集合。,存储于一个连续存储空间中的相同数据类型的数据元素的集合;,通过数组元素的下标,可以得到存放该数组元素的存储地址,从而可以访问该数组元素的值。,一维数组,向量,具有相同类型的,n,(,n,0),个元素的有限序列。,n,为数组长度或数组大小;,n,=0,为空数组。,各数组元素处于一个线性聚集或线性表中。,每个元素的数据类型相同;,占有相同的存储空间;,每个元素的开始位置到相邻元素的开始位置的距离相等。,一维数组的特点,数组中的每一个元素在数组中的位置由下标唯一确定;,除第一个元素外,其它元素有且仅有一个直接前驱,第一个元素没有前驱。,除最后一个元素外,其它元素有且仅有一个直接后继,最后一个元素没有后继。,示例,长度为,10,,每个元素占,l,个存储字,起始地址为,a,。,数组的定义和初始化,创建数组,静态数组,在声明数组对象时显式地定义了数组长度;,定义了数组的下标范围;,对数组各元素赋值;,存储空间不随程序的执行而改变。,动态数组,用指针声明数组;,在指针中只存放数组第一个元素的地址,所以仅占用一个存储空间;,用,+,和,-,可访问数组下一个元素或前一个元素。,数组的标准操作,存储,抽取,示例,Position,i,=,Position,i,-1+,Number,i,-1,赋值符号右边表示按下标,i,-1,直接提取相应数组元素的值;,赋值符号左边表示按下标,i,把右边的计算结果直接存储到相应数组元素中。,二维数组,矩阵,由,n,个行向量,m,个列向量所组成的向量。,共有,n,*,m,个数组元素;,元素,j,k,处于第,j,个行向量的第,k,个列向量;,在行和列方向上各有一个直接前驱和直接后继。,某一个数组元素在数组中的位置需由下标的二元组,j,k,唯一确定。,三维数组,共有,m,1,*,m,2,*,m,3,个数组元素;,每个数组元素同时处于三个向量之中;,最多有三个直接前驱和直接后继。,某一个数组元素在数组中的位置需由下标的三元组,i,j,k,唯一确定。,二维数组 三维数组,行向量 下标,i,页向量 下标,i,列向量 下标,j,行向量 下标,j,列向量 下标,k,n,维数组,a,m,1,m,2,.,m,n,总共有,m,1,*,m,2,*,m,n,个数组元素;,每一个数组元素,a,i,1,i,2,.,i,n,处于,n,个向量之中;,每一个数组元素的位置由下标的,n,元组,i,1,i,2,.,i,n,唯一确定。,数组连续存储方式,在实现数组存储时,通常是按各个数组元素的排列顺序,顺次存放在一个连续的存储区域内,得到一个所有数组元素的线性序列。,一维数组,第一个元素的起始位置为,,每一个数组元素的存储大小为,l,。,任一数组元素的存储地址,LOC,(,i,),:,LOC,(1)=,LOC,(0)+,l,=,+,l,LOC,(2)=,LOC,(1)+,l,=,+2*,l,,,LOC,(,i,)=,LOC,(,i,-,1)+,l,=,+,i*l,行优先顺序,所有数组元素按行向量依次排列,第,i,+1,个行向量紧跟在第,i,个行向量后面。,列优先顺序,所有数组元素按列向量依次排列,第,j,+1,个列向量紧跟在第,j,个列向量后面。,二维数组,行优先,LOC,(,j,k,),=,LOC,(,j,0,)+,k,*,l,/,第,j,行开始位置加,k,*,l,=LOC,(,j,-1,0,)+,m,*,l,+,k,*,l,/,第,j,-1,行开始位置加该行元素个数,m,*,l,加,k,*,l,=LOC,(,j,-2,0,)+2*,m,*,l,+,k,*,l,/,前推到第,j,-2,行,=,=LOC,(0,0,)+,j,*,m,*,l,+,k,*,l,/,前推到第,0,行,=,+(,j*m+k,)*,l,设二维数组,a,n,m,第一个元素,a,00,在相应的一维数组中存放于第一个位置,其地址为,,每个元素占,l,个元素的空间。,则任一数组元素,a,j,k,在相应一维数组中的存放地址利用递推公式计算:,设三维数组,a,m,1,m,2,m,3,中,对于任一数组元素,a,i,j,k,在一维数组中存放的位置为:,页优先,LOC,(,i,j,k,),=,LOC,(,i,0,0,)+,j,*,m,3,*,l,+,k,*,l,=LOC,(,i,-1,0,0,)+,m,2,*,m,3,*,l,+,j,*,m,3,*,l,+,k,*,l,=LOC,(,i,-2,0,0,)+2*,m,2,*,m,3,*,l,+,j,*,m,3,*,l,+,k,*,l,=,=LOC,(0,0,0,)+,i,*,m,2,*,m,3,*,l,+,j,*,m,3,*,l,+,k,*,l,=,+(,i,*,m,2,*,m,3,+,j,*,m,3,+,k,)*,l,三维数组,线性表,线性聚集,一个存储,n,(,n,0,),个表项的序列。,n,是表的长度,可以是任意整数。,n,=0,为空表。,表的长度随增加或删除某些表项而发生改变。,每个表项都是单个对象,其数据类型相同。,各个表项通过其位置来访问;,第一个表项位于表的头部,最后一个表项位于表的尾部。,除最后一个表项之外,其它每个表项有且仅有一个直接后继。,线性表的特点,特点,顺序存取,为了得到顺序表中所要求的项,必须从表的第一个表项开始,逐个访问表项,直到找到满足要求的表项为止。,遍历,逐项访问,从前向后 从后向前 从两端向中间,线性表上的基本运算,InitList(L),构造,一,个空的顺序表,Length(L),求顺序表,L,中的表元个数,GetNode(L,i),取顺序表,L,中的第,i,个表元,LocateNode(L,x),在顺序表中找值为,x,的结点,返回该结点在,L,中的位置。,InsertList(L,x,i),在,L,的第,i,个位置插入一个,值为,x,的新表元。,DeleteList(L,i),删除,L,的第,i,个表元。,线性表 的存储结构,常用的存储结构:,顺序存储,链接存储,顺序存储(顺序表),设顺序表的每个表元的结构都相同,记,LOC,(,a,i,),为存储,ai,的开始地址,则,LOC,(,a,i,),=LOC(a,0,)+i*sizeof(a,0,),顺序存储线性表的数据类型,#define MaxSize 100,typedef int DataType,typedef struct,DataType dataMaxSize;,int len;,SeqList;,顺序搜索图示,x,=48,x,=50,int LocateNode(SeqList*l,DataType key),int i;,for(i=0;i len;i+),if(l-datai=key),return i;,return-1;,搜索成功 若搜索概率相等,则,搜索不成功 数据比较,n,次,表项的插入,int,InsertList,(,SeqList*l,DataType,x,int,i,),int j;,/,在表中第,i,个位置插入新元素,x,if,(,i,l,-len,|,l,-len,=MaxSize,),return,0,;,/,插入不成功,else,for,(,j=l-len,;,ji,;,j,-,),l,-,data,j,=l-data,j,-,1,;,l,-,data,i,=x,;,l-len,+;,return,1,;,/,插入成功,表项的删除,int,DeleteList,(,SeqList*l,int,x,),int i,j;,/,在表中删除已有元素,x,i=LocateNode,(l,x,),;,/,在表中搜索,x,if,(,i=,0,),for,(,j=i,;,jlen-1,;,j+,),l-data,j,=l-data,j+,1,;,l-len,-,;,return,1,;,/,成功删除,return,0,;,/,表中没有,x,线性表的应用:,集合的“并”运算,void,Union,(,SeqList*LA,SeqList*LB,),int,i,k,;DAtaType,x,;,for,(,i=,0,;,ilen,;,i+,),x=LBi,;,/,在,LB,中取一元素,k=LocateNode,(,LA,x,),;,/,在,LA,中搜索它,if,(,k=,-,1),/,若未找到插入它,InsertList,(,LA,x,LA-len,),;,有一个指针指向链表的第一个表元,习惯称该指针为,“,头指针,”,或,“,链表头,”,。头指针,head,指向第一个表元,第一个表元又指向第二个表元,,,直到,最后一个表元,该表元不再指向其他表元,习惯称链表的最后一个表元为,“,表尾,”,。,一个非空链表,一个空链表,first=NULL,链接存储线性表,-,单链表结构,单链表的存储映像,单链表的数据类型,typedef char DataType;,typedef struct node,DataType data;,struct node*next;,ListNode;,typedef struct,ListNode*head;,LinkList;,1.,遍历链表,从链表的首表元开始,沿着链表表元的链接顺序逐一考察各表元,直至链表结束。,用指针,p,遍历整个链表,访问表元只做输出表元值的工作。,p,的初值为链表头指针,在,p,不等于,NULL,值时循环,输出,p,所指表元的值,并准备考察下一个表元,(,即,p=p-next),。,遍历链表的函数:,void travelLink(LinkList*L),ListNode*p=L-head;,while(p!=NULL),printf(,”,%4c,”,p-data);,/*,输出表元的值*,/,p=p-next;,/*,准备访问下一个表元*,/,printf(,”,n,”,);,2.,在链表中查找指定值的表元,在链表中查找指定值表元有不同目的,获取该表元的详细信息,称为简单查找。,对链表的修改,或将查到的表元删除,或在查到的表元之前插入一个新表元等,称为动态查找。,另外,,查找过程的实现又可分两种情况,一是无序链表上的查找,二是有序链表上的查找。,(,1,)无序链表上的简单查找,简单查找过程,:,从链表头指针所指的第一个表元出发,顺序查找。或发现有指定值的表元,以指向该表元的指针值为查找结果;或查找至链表末尾,未发现有指定值的表元,查找结果为,NULL,,表示链表中没有指定值的表元,。,ListNode*searchSLink(LinkList*L,DataType key),ListNode*v=L-head;,while(v!=NULL)&(v-data!=key),v=v-next;,return v;,(,2,)有序链表上的简单查找,如链表的表元是按值从小到大有序的,在顺序考察链表表元的查找循环中,当发现还有表元,并且该表元的值比,key,小时,应继续查找。反之,若不再有表元,或当前表元值不比,key,值小,则应结束查找。,查找循环结束后,仅当还有表元,且表元的值与,key,值相同情况下,才找到,函数返回当前表元的指针。否则,链表中没有值为,key,的表元,函数返回,NULL,值。,ListNode*searchSOLink(LinkList*L,DataType key),ListNode*v=L-head;,while(v!=NULL)&(v-datanext;,return v!=NULL&,v-data=key?v:NULL;,(,3,)无序链表上的动态查找,动态查找,应为插入或删除做好必要的准备工作。,由于是单向链表,函数除要回答查找结束时的当前表元的指针外,还应回答该表元的前驱表元指针。,令函数返回值是查找结束时当前表元的指针,函数另设一个指针形参,将找到的前驱表元的指针存于环境中的某指针变量中。,ListNode*searchDSLink(LinkList*L,DataType key,,,ListNode*pp),ListNode*v=L-head,*u=NULL;,while(v!=NULL)&(v-data!=key),u=v;,v=v-next;/*,后继表元成为当前表元*,/,*pp=u;,return v;,(4),有序链表上的动态查找,表元按值从小到大顺序链接,,与无序链表上的动态查找类似,但查找循环当发现查找值不比链表当前表元的值小时,就应提早结束查找循环。,ListNode*searchDOLink(LinkList*L,DataType key,,,ListNode*pp),ListNode*v=L-head,*u=NULL;,while(v!=NULL)&(v-data next;,*pp=u;return v;,3.,从链表删除指定值的表元,为删除首先要查找指定值的表元。,若未找到,则不做删除工作;,若找到,则将它从链表中删除。,删除时要考虑两种不同情况,如删的是首表元,要更改链表头指针;否则更改前驱表元的后继指针。,在无序整数链表上删除指定值表元的函数中。,因函数在删除链表首表元时,要修改链表头指针。,函数返回删除表元的指针。,ListNode*sDelete(LinkList*L,DataType key),ListNode *u,*w;,u=L-head;/*,让,u,指向链表的首表元*,/,while(u!=NULL)&(u-data!=key),w=u;u=u-next;,if(u!=NULL)/*,链表中有值为,key,的表元*,/,if(u=L-head),L-head=u-next;/*,修改链表头指针*,/,else w-next=u-next;,u-next=NULL;,return u;,4.,在有序链表中插入指定值的表元,寻找插入位置,生成新表元并插入之。,void rInserte(LinkList*L,DataType key),ListNode *u,*w,*p;,u=searchDOLink(L,key,p=(ListNode*)malloc(sizeof(ListNode);,p-data=key;,p-next=u;,if(w=NULL),L-head=p;/*,修改链表头指针*,/,else w-next=p;,5.,建立单链表,(1),头插法建表,LinkList CreatListF(void),char ch;LinkList L;,ListNode*p;,L.head=NULL;,while(ch=getchar()!=n),p=(ListNode*)malloc(sizeof(ListNode);,p-data=ch;,p-next=L.head;,L.head=p;,return L;,(2),尾插法建表,LinkList CreatListR(void),char ch;LinkList L;ListNode*p,*r;,L.head=r=NULL;,while(ch=getchar()!=n),p=(ListNode*)malloc(sizeof(ListNode);,p-data=ch;,if(r=NULL)L.head=p;,else r-next=p,r=p;,if(r!=NULL)r-next=NULL;,return L;,带表头结点的单链表,表头结点位于表的最前端,本身不带数据,仅标志表头。,设置表头结点的目的是统一空表与非空表的操作,简化链表操作的实现。,非空表 空表,循环链表,(,Circular List,),循环链表是单链表的变形。,相同点:两者结点结构相同。,不同点:循环链表最后一个结点的,link,指针不为,0,(,NULL,),,而是指向了表的前端。,为简化操作,在循环链表中往往加入表头结点。,特点:只要知道表中某一结点的地址,就可搜寻到所有其他结点。,循环链表的示例,带表头结点的循环链表,字符串,(,String,),字符串是,n(,0),个字符的有限序列,记作,S:“,c,0,c,1,c,2,c,n-1,”,其中,,S,是串名字,“,c,0,c,1,c,2,c,n-1,”,是串值,c,i,是串中字符,n,是串的长度。,如:“,Welcome to Shanghai!”,char*subStr,(char*s,int,pos,int,len,char*ss,),/,从串中第,pos,个位置起连续提取,len,个字符,/,形成子串返回,int i,j;,if,(,pos,0,|,len,0),*ss=,0,;,/,返回空串,else,/,提取子串,for,(,i=,0,j=pos,;,sj!=0&,i 0,,则目标指针不变,,模式指针回到,p,f,(,j,-1)+1,。,运用,KMP,算法的匹配过程,第,1,趟 目标,a,c,a b a a b a a b c a c a a b c,模式,a,b,a a b c a c,j,=1,j,=,f,(,j,-,1)+1=0,第,2,趟 目标,a,c,a b a a b a a b c a c a a b c,模式,a,b a a b c a c,j,=0,目标指针加,1,第,3,趟 目标,a c a b a a b,a,a b c a c a a b c,模式,a b a a b,c,a c,j,=5,j,=,f,(,j,-,1)+1=2,第,4,趟 目标,a c a b a a b,a,a b c a c a a b c,模式,(,a b,),a,a b c a c,int,fastFind,(char*s,char*,pat,),/,带失效函数的,KMP,匹配算法,int,posP=,0,posT=,0,;,int,lengthP=strlen(pat),lengthT=strlen(s);,while,(,posP lengthP,&,posT lengthT,),if,(,pat,posP,=s,posT,),posP+,;,posT+,;,/,相等继续比较,else if,(,posP=,0),posT+,;,/,不相等,else,posP=f,posP,-,1+1,;,if,(,posP lengthP,),return,-,1,;,else,return,posT,-,lengthP,;,比较过程中,posT不回溯,计算失效函数,f,j,的方法,首先确定,f,0,=,-,1,再利用,f,j,求,f,j+,1,。,其中,f,(1),j,=,f,j,f,(,m,),j,=,f,f,(,m,-1),j,f,0,=,-,1;,j,=1,时,f,0+1=0,p,0,p,1,f,1=,-,1;,j,=2,时,f,1+1=0,p,0,=,p,2,f,2=,f,1+1=0;,j,=3,时,f,2+1=1,p,1,p,3,f,1+1=0,p,0,=,p,3,f,3=,f,1+1=0;,j,=4,时,f,3+1=1,p,1,=,p,4,f,4=,f,3+1=1;,void,fail,(char*s),/,计算失效函数,int,lengthP=strlen(s),j,i,;,f,0,=,-,1,;,/,直接赋值,for,(,j=,1,;,j=,0),i=f,i,;,/,递推,if,(*(,s+j,),=*,(,s+i+,1),f,j,=i+,1,;,else,f,j,=,-,1,;,第二章结束,
展开阅读全文

开通  VIP、SVIP  下载更划算
下载10份以上建议开通 VIP 会员
下载20份以上建议开通SVIP会员


开通VIP      成为共赢上传

当前位置:首页 > 教育专区 > 其他

移动网页_全站_页脚广告1

关于我们      便捷服务       自信AI       AI导航        关注我们

©2010-2026 宁波自信网络信息技术有限公司  版权所有

客服电话:0574-28810668  投诉电话:18658249818

gongan.png浙公网安备33021202000488号   

icp.png浙ICP备2021020529号-1  |  浙B2-20240490  

关注我们 :微信公众号    抖音    微博    LOFTER 

客服