《线性表与字符串.ppt》由会员分享，可在线阅读，更多相关《线性表与字符串.ppt（57页珍藏版）》请在三一办公上搜索。
1、数组线性表字符串,第二章 线性表和字符串,数组,二元组的一个集合。存储于一个连续存储空间中的相同数据类型的数据元素的集合；通过数组元素的下标，可以得到存放该数组元素的存储地址，从而可以访问该数组元素的值。,一维数组向量具有相同类型的n(n0)个元素的有限序列。n为数组长度或数组大小；n=0为空数组。各数组元素处于一个线性聚集或线性表中。每个元素的数据类型相同；占有相同的存储空间；每个元素的开始位置到相邻元素的开始位置的距离相等。,一维数组的特点数组中的每一个元素在数组中的位置由下标唯一确定；除第一个元素外，其它元素有且仅有一个直接前驱，第一个元素没有前驱。除最后一个元素外，其它元素有且仅有一个
2、直接后继，最后一个元素没有后继。示例长度为10，每个元素占l个存储字，起始地址为a。,数组的定义和初始化,创建数组静态数组在声明数组对象时显式地定义了数组长度；定义了数组的下标范围；对数组各元素赋值；存储空间不随程序的执行而改变。动态数组用指针声明数组；在指针中只存放数组第一个元素的地址，所以仅占用一个存储空间；用+和-可访问数组下一个元素或前一个元素。,数组的标准操作存储抽取示例Positioni=Positioni-1+Numberi-1赋值符号右边表示按下标i-1直接提取相应数组元素的值；赋值符号左边表示按下标i把右边的计算结果直接存储到相应数组元素中。,二维数组矩阵由n个行向量m个列向
3、量所组成的向量。共有n*m个数组元素；元素 jk处于第j个行向量的第k个列向量；在行和列方向上各有一个直接前驱和直接后继。某一个数组元素在数组中的位置需由下标的二元组jk唯一确定。三维数组共有m1*m2*m3个数组元素；每个数组元素同时处于三个向量之中；最多有三个直接前驱和直接后继。某一个数组元素在数组中的位置需由下标的三元组ijk唯一确定。,二维数组 三维数组,行向量 下标 i 页向量 下标 i列向量 下标 j 行向量 下标 j 列向量 下标 k,n维数组am1m2.mn 总共有m1*m2*mn个数组元素；每一个数组元素ai1i2.in处于n个向量之中；每一个数组元素的位置由下标的n元组i1
4、i2.in 唯一确定。,数组连续存储方式,在实现数组存储时，通常是按各个数组元素的排列顺序，顺次存放在一个连续的存储区域内，得到一个所有数组元素的线性序列。,一维数组第一个元素的起始位置为，每一个数组元素的存储大小为l。任一数组元素的存储地址LOC(i)：,LOC(1)=LOC(0)+l=+lLOC(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
5、*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,设二维数组anm第一个元素a00在相应的一维数组中存放于第一个位置，其地址为，每个元素占l个元素的空间。则任一数组元素ajk在相应一维数组中的存放地址利用递推公式计算：,设三维数组am1m2m3中，对于任一数组元素a ijk在一维数组中存放的位置为：,页优先 LOC(i,j,k)=LOC(i,0,0)+j*m3*l+k*l=LOC(i-1,0,0)
6、+m2*m3*l+j*m3*l+k*l=LOC(i-2,0,0)+2*m2*m3*l+j*m3*l+k*l=LOC(0,0,0)+i*m2*m3*l+j*m3*l+k*l=+(i*m2*m3+j*m3+k)*l,三维数组,线性表,线性聚集，一个存储n(n0)个表项的序列。n是表的长度，可以是任意整数。n=0为空表。表的长度随增加或删除某些表项而发生改变。每个表项都是单个对象，其数据类型相同。各个表项通过其位置来访问；第一个表项位于表的头部，最后一个表项位于表的尾部。除最后一个表项之外，其它每个表项有且仅有一个直接后继。,线性表的特点特点 顺序存取为了得到顺序表中所要求的项，必须从表的第一个表项
7、开始，逐个访问表项，直到找到满足要求的表项为止。遍历 逐项访问 从前向后 从后向前 从两端向中间,线性表上的基本运算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（ai）为存储ai的开始地址，则 LOC
8、（ai）=LOC(a0)+i*sizeof(a0),顺序存储线性表的数据类型#define MaxSize 100typedef int DataTypetypedef 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*
9、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-dataj=l-dataj-1;l-datai=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-dataj=l-dataj+1;l-len-;return
10、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指向第一个表元，第一个表元又指向第二个表元，直到最后一个表元，该表元不再指向其他表元，习惯称链表的最后一个表元为“表尾”。,一
11、个非空链表,一个空链表,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)
12、。,遍历链表的函数：void travelLink(LinkList*L)ListNode*p=L-head;while(p!=NULL)printf(”%4c”,p-data);/*输出表元的值*/p=p-next;/*准备访问下一个表元*/printf(”n”);,2.在链表中查找指定值的表元在链表中查找指定值表元有不同目的获取该表元的详细信息，称为简单查找。对链表的修改，或将查到的表元删除，或在查到的表元之前插入一个新表元等，称为动态查找。另外，查找过程的实现又可分两种情况，一是无序链表上的查找，二是有序链表上的查找。,（1）无序链表上的简单查找简单查找过程:从链表头指针所指的第一个表元
13、出发，顺序查找。或发现有指定值的表元，以指向该表元的指针值为查找结果；或查找至链表末尾，未发现有指定值的表元，查找结果为NULL，表示链表中没有指定值的表元。ListNode*searchSLink(LinkList*L,DataType key)ListNode*v=L-head;while(v!=NULL),（2）有序链表上的简单查找如链表的表元是按值从小到大有序的，在顺序考察链表表元的查找循环中，当发现还有表元，并且该表元的值比key小时，应继续查找。反之，若不再有表元，或当前表元值不比key值小，则应结束查找。查找循环结束后，仅当还有表元，且表元的值与key值相同情况下，才找到，函数返
14、回当前表元的指针。否则，链表中没有值为key的表元，函数返回NULL值。,ListNode*searchSOLink(LinkList*L,DataType key)ListNode*v=L-head;while(v!=NULL),（3）无序链表上的动态查找动态查找应为插入或删除做好必要的准备工作。由于是单向链表，函数除要回答查找结束时的当前表元的指针外，还应回答该表元的前驱表元指针。令函数返回值是查找结束时当前表元的指针，函数另设一个指针形参，将找到的前驱表元的指针存于环境中的某指针变量中。,ListNode*searchDSLink(LinkList*L,DataType key，List
15、Node*pp)ListNode*v=L-head,*u=NULL;while(v!=NULL),(4)有序链表上的动态查找表元按值从小到大顺序链接，与无序链表上的动态查找类似，但查找循环当发现查找值不比链表当前表元的值小时，就应提早结束查找循环。ListNode*searchDOLink(LinkList*L,DataType key，ListNode*pp)ListNode*v=L-head,*u=NULL;while(v!=NULL),3.从链表删除指定值的表元为删除首先要查找指定值的表元。若未找到，则不做删除工作；若找到，则将它从链表中删除。删除时要考虑两种不同情况，如删的是首表元，要
16、更改链表头指针；否则更改前驱表元的后继指针。在无序整数链表上删除指定值表元的函数中。因函数在删除链表首表元时，要修改链表头指针。函数返回删除表元的指针。,ListNode*sDelete(LinkList*L,DataType key)ListNode*u,*w;u=L-head;/*让 u 指向链表的首表元*/while(u!=NULL),4.在有序链表中插入指定值的表元寻找插入位置，生成新表元并插入之。void rInserte(LinkList*L,DataType key)ListNode*u,*w,*p;u=searchDOLink(L,key,5.建立单链表(1)头插法建表Link
17、List 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(ListNo
18、de);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)，而是指向了表的前端。为简化操作，在循环链表中往往加入表头结点。特点：只要知道表中某一结点的地址，就可搜寻到所有其他结点。,循环链
19、表的示例带表头结点的循环链表,字符串(String),字符串是n(0)个字符的有限序列，记作 S:“c0c1c2cn-1”其中，S是串名字“c0c1c2cn-1”是串值 ci是串中字符 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,提取子串运算,串的模式匹配,定义 在串中寻找子串（第一个字符）在串中的位置
20、词汇 在模式匹配中，子串称为模式，串称为目标。示例 目标 T:“Beijing”模式 P:“jin”匹配结果=3,第1趟 T a b b a b a 穷举的模式 P a b a 匹配过程第2趟 T a b b a b a P a b a第3趟 T a b b a b a P a b a第4趟 T a b b a b a P a b a,int Find(char*s,char*pat)/穷举的模式匹配 char*p=pat,*ss=s;int i=0;if(*pat,穷举的模式匹配算法时间代价：最坏情况比较n-m+1趟，每趟比较m次，总比较次数达(n-m+1)*m 原因在于每趟重新比较时，目标
21、串的检 测指针要回退。改进的模式匹配算法可 使目标串的检测指针每趟不回退。改进的模式匹配(KMP)算法的时间代价：若每趟第一个不匹配，比较n-m+1趟，总比较次数最坏达(n-m)+m=n 若每趟第m个不匹配，总比较次数最坏亦达到 n,目标 TS T U D E N S T U D E N T 模式 patS T U D E N T 目标 TS T U D E N S T U D E N T 模式 pat S T U D E N T 目标 TS T U D E N S T U D E N T 模式 pat S T U D E N T,穷举模式匹配的缺点:无谓比较,目标 TF I F I F I
22、Y U D E N T 模式 patF I F I Y 目标 TF I F I F I Y U D E N T 模式 pat F I F I Y 直接跳过错过成功比较 目标 TF I F I F I Y U D E N T 模式 pat F I F I Y,直接跳过子串可能错过成功比较,目标 Tt0 t1 t2 tj-1 tj tn-1 X 模式 patp0 p1 p2 pj-1 pj pm-1 目标 T t0 t1 tk tn-1 模式 pat p0 p1 pm-2 pm-1,改进的模式匹配（KMP）算法 寻找最大“跳跃”,T t0 ts-1 ts ts+1 ts+2 ts+j-1 ts+j
23、 ts+j+1 tn-1 P p0 p1 p2 pj-1 pj pj+1 则有 ts ts+1 ts+2 ts+j=p0 p1 p2 pj(1)为使模式 P 与目标 T 匹配，必须满足 p0 p1 p2 pj-1 pm-1=ts+1 ts+2 ts+3 ts+j ts+m 如果 p0 p1 pj-1 p1 p2 pj(2)则立刻可以断定 p0 p1 pj-1 ts+1 ts+2 ts+j下一趟必不匹配,同样，若 p0 p1 pj-2 p2 p3 pj则再下一趟也不匹配，因为有 p0 p1 pj-2 ts+2 ts+3 ts+j直到对于某一个“k”值，使得 p0 p1 pk+1 pj-k-1 p
24、j-k pj 且 p0 p1 pk=pj-k pj-k+1 pj则 p0 p1 pk=ts+j-k ts+j-k+1 ts+j pj-k pj-k+1 pj,k 的确定方法 当比较到模式第 j 个字符失配时，k 的值与模式的前 j 个字符有关，与目标无关。目标 TF I F I F I Y U D E N T 模式 patF I F I Y失效函数 可以利用失效函数 f(j)描述。失效函数又名失败链接值。在当前位置遇到失败后，在目标不回溯的情况下，模式的 重新开始位置。,若设 模式 P=p0 p1pm-2 pm-1,示例：确定失效函数 f(j),利用失效函数 f(j)的匹配处理 如果 j=0，
25、则目标指针加 1，模式指针回到 p0。如果 j 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
26、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不回溯,计算失效函数 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,p0 p1,f 1=-1;j=2时,f 1+1=0,p0=p2,f 2=f 1+1=0;j=3时,f 2+1=1,p1 p3,f 1+1=0,p0=p3,f 3=f 1+1=0;j=4时,f 3+1=1,p1=p4,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;,第二章结束,
