字符串与数组课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《字符串与数组课件.ppt》由用户(晟晟文业)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 字符串 数组 课件
- 资源描述:
-
1、第第4章章 字符串和数组字符串和数组一、字符串一、字符串存储方式(存储方式(1)一个由多个字符构成以零(0)结尾的线性表就是字符串。C语言中没有字符串数据类型。C语言中字符串被存储在字符型数组中,这个数组可以静态定义,也可动态分配。2 堆存储:利用一块连续的内存来存放字符串的存储结构堆存储:利用一块连续的内存来存放字符串的存储结构define MAXSIZE 100char str1MAXSIZE+1;/*静态定义的字符数组,可容纳最大字符串长度是MAXSIZE*/char*pstr=NULL;/*字符指针,将指向存放字符串的内存*/int len;scanf(“%d”,&len);/*获得字
2、符串的长度*/pstr=(char*)malloc(len+1);/*根据字符串的长度分配一块内存*/一、字符串一、字符串存储方式(存储方式(2)块链存储块链存储typedef struct strnode char*block;/*根据需要动态分配的内存,存放一段字符串*/int size;/*block所指内存的大小*/struct strnode*next;/*指向下一段字符串*/STRNODE,*STRNODEPTR,*BLOCKLINKSTR;My name is Yang Kaichengblock next3一、字符串一、字符串简单模式匹配简单模式匹配(1)【任务描述任务描述】已
3、知一字符串已知一字符串S S和字符串和字符串T T,请确定字符串,请确定字符串T T在在S S中的位置,即字符串中的位置,即字符串T T的首字母在字符串的首字母在字符串S S中的下标值。中的下标值。这里字符串这里字符串S S被称为主串,被称为主串,T T被称为子串,又称为模式串。被称为子串,又称为模式串。通常情况下,通常情况下,S S串的长度比串的长度比T T大。大。【算法思想算法思想】以以pospos作为作为S S串的下标。设串的下标。设T T串的长度是串的长度是lentlent。pospos从从0 0开始从左向右扫描字符串开始从左向右扫描字符串S S,检查以,检查以SposSpos为起点为
4、起点的长度为的长度为lentlent的子串是否与的子串是否与T T串完全相同。串完全相同。如果完全相同,则意味着匹配成功,返回如果完全相同,则意味着匹配成功,返回pospos值;值;如果不同,说明匹配失败,需要将如果不同,说明匹配失败,需要将pospos向后移动一个单元,继续向后移动一个单元,继续检查以检查以SposSpos为起点的长度为为起点的长度为lentlent的子串是否与的子串是否与T T串完全相同。串完全相同。这样循环反复,直到匹配成功或者以这样循环反复,直到匹配成功或者以SposSpos为起点的子串长度不够为起点的子串长度不够为止。为止。4一、字符串一、字符串简单模式匹配简单模式匹
5、配(2)int StrIndex(char*s,char*t)/*返回t在s中的位置,找不到t,则返回-1*/int i,j;int pos=0;/*匹配的起点*/while(1)i=pos;j=0;while(si&tj&si=tj)/*匹配循环*/i+;j+;if(tj=0)return pos;/*匹配成功*/else if(si=0)return-1;/*匹配到了主串的末尾还没有成功*/else pos+;/*匹配的起点向后移动一个单元,重新匹配*/while(1)时间复杂度:时间复杂度:)(mnO)(mnO5一、字符串一、字符串*模式匹配的模式匹配的KMP算法算法(1)简单匹配算法的
6、最大问题是:简单匹配算法的最大问题是:每次匹配失败时,每次匹配失败时,S串要回到串要回到Spos+1处,而处,而T串要回到串要回到T0处,从头开处,从头开始比较。始比较。下面的例子蕴含着改进的空间下面的例子蕴含着改进的空间已知主串是:已知主串是:aabcdabcdabceab模式串是:模式串是:abcdabce“KMP算法的基本思想:算法的基本思想:只要发现只要发现SiTjSiTj时,时,i i保持不动,保持不动,j j跳到跳到k k处处(滑动滑动T T串串),直到,直到k k是是-1-1时,时,i i才向右移动才向右移动1 1位。位。k k被称为被称为j j的的nextnext值,即值,即k
7、=next(j)k=next(j)。j跳到跳到k处的条件是:处的条件是:k是是T串在串在j处的自身最大重复子串的长度。处的自身最大重复子串的长度。SaabcdabcdabceababcdabceTposijk jkjk i 大的重复子串大的重复子串6K值的真正含义:是子串T0.j-1自身重复子串T0.k-1的长度特点:有重复子串一、字符串一、字符串*模式匹配的模式匹配的KMP算法算法(2)关键是关键是next(j)如何求解如何求解 next(j)表达的是表达的是T串自身的特征,与串自身的特征,与S串无关串无关 next函数的数学定义函数的数学定义 next(j)函数值的求解算法函数值的求解算法
8、已知已知k=next(j),说明,说明T0.j-1之间最大重复子串的长度是之间最大重复子串的长度是k。下面的循环。下面的循环可以求出可以求出next(j+1)的值:的值:比较比较TjTj和和TkTk,如果,如果Tj=TkTj=Tk,那么,那么T0.jT0.j之间最大重复子串的之间最大重复子串的长度就是长度就是k+1k+1,也就是说,也就是说next(j+1)=k+1next(j+1)=k+1,求值完毕;,求值完毕;如果如果Tj TkTj Tk,我们只能在,我们只能在T0.k-1T0.k-1内寻找最大重复子串。内寻找最大重复子串。T0.k-1T0.k-1最大重复子串长度是最大重复子串长度是nex
9、t(k)next(k),这时设定,这时设定k=next(k)k=next(k),也就是说,也就是说,k k回退到自己的回退到自己的nextnext值处。我们再次比较值处。我们再次比较TjTj和和TkTk,即转到步骤。,即转到步骤。其他情况当此集合不空时且01.1.01|01)(jkjTkTjkkMaxjjnext7因为因为next值只和值只和T串内容有关,串内容有关,一旦一旦T串确定,就可以计算出所有串确定,就可以计算出所有next值,值,并用一个数组保存,以供字符串匹配时使用。并用一个数组保存,以供字符串匹配时使用。一、字符串一、字符串*模式匹配的模式匹配的KMP算法算法(2)关键是关键是n
10、ext(j)如何求解如何求解 next(j)表达的是表达的是T串自身的特征,与串自身的特征,与S串无关串无关 next函数的数学定义函数的数学定义 next(j)函数值的求解算法函数值的求解算法已知已知k=next(j),说明,说明T0.j-1之间最大重复子串的长度是之间最大重复子串的长度是k。下面的循环。下面的循环可以求出可以求出next(j+1)的值:的值:比较比较TjTj和和TkTk,如果,如果Tj=TkTj=Tk,那么,那么T0.jT0.j之间最大重复子串的之间最大重复子串的长度就是长度就是k+1k+1,也就是说,也就是说next(j+1)=k+1next(j+1)=k+1,求值完毕;
11、,求值完毕;如果如果Tj TkTj Tk,我们只能在,我们只能在T0.k-1T0.k-1内寻找最大重复子串。内寻找最大重复子串。T0.k-1T0.k-1最大重复子串长度是最大重复子串长度是next(k)next(k),这时设定,这时设定k=next(k)k=next(k),也就是说,也就是说,k k回退到自己的回退到自己的nextnext值处。我们再次比较值处。我们再次比较TjTj和和TkTk,即转到步骤。,即转到步骤。其他情况当此集合不空时且01.1.01|01)(jkjTkTjkkMaxjjnext8一、字符串一、字符串*模式匹配的模式匹配的KMP算法算法(3)void NextVal(c
12、har*T,int*next)/*求模式串T各单元的next值*/int j,k,len;next0=-1;j=0;len=strlen(T);while(j=0&Tj!=Tk)k=nextk;/*k回退到自己的next值处,重复子串的长度变小*/nextj+1=k+1;/*无论是k=-1,还是Tj=Tk,nextj+1的值都是k+1*/j+;/*准备推算下一个next值*/9一、字符串一、字符串*模式匹配的模式匹配的KMP算法算法(4)#define MAXSIZE 50int nextMAXSIZE;int StrIndexKMP(char*S,char*T)/*返回T在S中的位置,查找失
13、败,返回-1*/int i=0,j=0;NextVal(T,next);/*计算T串的next值*/while(Si!=0&Tj!=0)/*如果没到字符串末尾,就循环继续匹配*/if(Si=Tj)/*i和j都向后移动一个单元*/i+;j+;else j=nextj;/*匹配失败,j滑动到自己的next值处*/if(j=-1)/*说明滑动之前j已经是0,需要将i向后移动,同时置j为0*/i+;j=0;/else /*属于while语句*/if(Tj=0)return i-j;/*匹配成功,返回位置*/else return-1;/*查找失败*/10解疑解疑11Saabcdabcdabceabab
14、cdabceTposijk01234567next-10000123012345678910二、数组与矩阵二、数组与矩阵数组的定义数组的定义#define N 10#define M 20#define P 10elemtype aN;/*定义了一个N个单元的一维数组*/假设假设a0的地址是的地址是Loc,elemtype数据类型的大小是数据类型的大小是S(字节字节),那么数组单元,那么数组单元ai的地址就是的地址就是:Loc+iS。elemtype bMN;/*定义了一个MN个单元的二维数组*/假设假设b00的地址是的地址是Loc,那么数组单元,那么数组单元bij的前面一共有的前面一共有i行
15、(行(iN个)单个)单元,外加元,外加j个单元,它的地址就是:个单元,它的地址就是:Loc+(iN+j)S12二、数组与矩阵二、数组与矩阵矩阵的压缩存储矩阵的压缩存储(1)1特殊矩阵之特殊矩阵之三角矩阵三角矩阵的压缩存储的压缩存储111222111211100201000nnnnnAAAAAAAAAA111211102221201110000nnnnnAAAAAAAAAAn(n+1)/2-1An-1n-1A11A12A02A00A01A0n-1A13012上三角矩阵的压缩存储上三角矩阵的压缩存储下三角矩阵的压缩存储下三角矩阵的压缩存储An-1n-1A30A22A11A00A10A20A3101
16、23n(n+1)/2-1A21BB13三角矩阵三角矩阵Aij和数组和数组Bk的关系:的关系:u上三角矩阵:上三角矩阵:k=(N+(N-1)+(N-(i-1)+(j-i)=i(2N-i+1)/2+j-I (ji)u下三角矩阵:下三角矩阵:k=(1+2+3+i)+j=i(i+1)/2+j (ij)二、数组与矩阵二、数组与矩阵矩阵的压缩存储矩阵的压缩存储(2)2特殊矩阵之特殊矩阵之对称矩阵对称矩阵的压缩存储,按照三角矩阵的方式的压缩存储,按照三角矩阵的方式 N阶矩阵,存在阶矩阵,存在Aij=Aji3特殊矩阵之特殊矩阵之带状矩阵带状矩阵的压缩存储的压缩存储N阶矩阵,只有主对角线和它的上下两条对角线上有
17、数据,其他位置都是阶矩阵,只有主对角线和它的上下两条对角线上有数据,其他位置都是0或或者某个固定常量。者某个固定常量。k=(i3-1)+(j-(i-1)=2i+j1121343332232221121110010000nnnnAAAAAAAAAAAAA14二、数组与矩阵二、数组与矩阵矩阵的压缩存储矩阵的压缩存储(3)4特殊矩阵之特殊矩阵之稀疏矩阵稀疏矩阵的压缩存储的压缩存储在一个在一个MN的矩阵中,非零元素的个数是的矩阵中,非零元素的个数是T,我们将,我们将 称为稀疏因子。通常称为稀疏因子。通常认为,当稀疏因子小于等于认为,当稀疏因子小于等于0.05时,这个矩阵就称为稀疏矩阵。时,这个矩阵就称
18、为稀疏矩阵。稀疏矩阵的稀疏矩阵的顺序存储顺序存储#define MAXSIZE 500typedef struct int i,j;/*在矩阵中的位置下标*/elemtype v;/*非零元素*/TRIPLE;/*三元组*/typedef struct TRIPLE dataMAXSIZE;/*三元组数组*/int rnum,cnum,sum;/*行数、列数、非零元素的个数*/TRIPLEMATRIX;15二、数组与矩阵二、数组与矩阵矩阵的压缩存储矩阵的压缩存储(4)下面的算法创建一个顺序存储结构的稀疏矩阵:下面的算法创建一个顺序存储结构的稀疏矩阵:void InputData(TRIPLEM
19、ATRIX*m)int count;TRIPLE t;/*开始输入稀疏矩阵的行数、列数和非零元素的个数*/scanf(%d,%d,%d,&m-rnum,&m-cnum,&m-sum);count=0;while(1)scanf(%d,%d,%d,&t.i,&t.j,&t.v);/*获取三元组数据,要求按行序输入*/if(t.i=0&t.irnum&t.j=0&t.jcnum)/*三元组数据合法*/m-datacount=t;count+;/*计数器增1*/if(count=m-sum)break;/*所有数据都输入完毕*/else break;/*遇到非法输入*/16二、数组与矩阵二、数组与矩
20、阵矩阵的压缩存储矩阵的压缩存储(5)4特殊矩阵之特殊矩阵之稀疏矩阵稀疏矩阵的压缩存储的压缩存储稀疏矩阵的稀疏矩阵的十字链表存储十字链表存储将所有同一行的非零元素按列序链接,所有同一列的非零元素按行序链接。将所有同一行的非零元素按列序链接,所有同一列的非零元素按行序链接。这样,同一个三元组单元同时存在于行链和列链两个链表中。这样,同一个三元组单元同时存在于行链和列链两个链表中。typedef struct crsnode_tag int i,j;elemtype v;/*三元组数据*/struct crsnode_tag*right,*down;/*行链指针和列链指针,right指向同一行下一列
展开阅读全文