串数组和广义表优秀课件.ppt

《串数组和广义表优秀课件.ppt》由会员分享，可在线阅读，更多相关《串数组和广义表优秀课件.ppt（59页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、串数组和广义表串数组和广义表第1页，本讲稿共59页 2022年9月23日 第第4 4章章串、数组和广义表串、数组和广义表 4.1 4.1 串串4.2 4.2 数组数组4.3 4.3 广义表广义表 教学内容教学内容第2页，本讲稿共59页 2022年9月23日 1.1.掌握串的存储方法，理解串的两种模式匹配掌握串的存储方法，理解串的两种模式匹配算法算法；2.2.明确数组和广义表这两种数据结构的特点，明确数组和广义表这两种数据结构的特点，掌握数组存储时地址计算方法，了解几种特掌握数组存储时地址计算方法，了解几种特殊矩阵的压缩存储方法。殊矩阵的压缩存储方法。教学目标教学目标1.了解串的存储方法，理解串

2、的两种模式匹配了解串的存储方法，理解串的两种模式匹配算法，重点掌握算法，重点掌握BF算法算法。2.明确数组和广义表这两种数据结构的特点，明确数组和广义表这两种数据结构的特点，掌握掌握数组地址计算方法数组地址计算方法，了解几种特殊矩阵，了解几种特殊矩阵的压缩存储方法。的压缩存储方法。3.掌握广义表的定义、性质及其掌握广义表的定义、性质及其GetHead和和GetTail的操作的操作。第3页，本讲稿共59页 2022年9月23日 4.1 4.1 串串串串(String)-(String)-零个或多个字符组成的有限序列零个或多个字符组成的有限序列串名串名串值串值串长串长n空串空串n=0第4页，本讲稿

3、共59页 2022年9月23日 a=a=BEIBEI,b=b=JINGJING c=c=BEIJINGBEIJING d=d=BEI JINGBEI JING子串子串字符位置字符位置主串主串子串位置子串位置串相等串相等空格串空格串第5页，本讲稿共59页 2022年9月23日 数据对象数据对象:数据关系数据关系:基本操作基本操作:(1)StrAssign(&T,chars)/串赋值串赋值(2)StrCompare(S,T)/串比较串比较(3)StrLength(S)/求串长求串长(4)Concat(&T,S1,S2)/串联串联ADT String 串的抽象数据类型串的抽象数据类型第6页，本讲稿共

4、59页 2022年9月23日 北京林业大学信息学院北京林业大学信息学院(5)SubString(&Sub,S,pos,len)/求子串求子串(6)StrCopy(&T,S)/串拷贝串拷贝(7)StrEmpty(S)/串判空串判空(8)ClearString(&S)/清空串清空串(9)Index(S,T,pos)/子串的位置子串的位置(11)Replace(&S,T,V)/串替换串替换(12)StrInsert(&S,pos,T)/子串插入子串插入(12)StrDelete(&S,pos,len)/子串删除子串删除(13)DestroyString(&S)/串销毁串销毁ADTString第7页，

5、本讲稿共59页 2022年9月23日 顺序存储顺序存储链式存储链式存储串的存储结构串的存储结构第8页，本讲稿共59页 2022年9月23日 typedef structtypedef struct charchar*ch;/*ch;/若串非空若串非空,则按串长分配存储区则按串长分配存储区,/否则否则chch为为NULLNULL int length;/int length;/串长度串长度 HString;HString;顺序存储表示顺序存储表示第9页，本讲稿共59页 2022年9月23日 链式存储表示链式存储表示第10页，本讲稿共59页 2022年9月23日 可将多个字符存放在一个结点中，以克

6、服其缺点可将多个字符存放在一个结点中，以克服其缺点优点：操作方便优点：操作方便缺点：存储密度较低缺点：存储密度较低实际分配的存储位实际分配的存储位串值所占的存储位串值所占的存储位存储密度存储密度=链式存储表示链式存储表示第11页，本讲稿共59页 2022年9月23日#define CHUNKSIZE 80 /可由用户定义的块大小可由用户定义的块大小typedef struct Chunk char chCHUNKSIZE;struct Chunk*next;Chunk;typedef struct Chunk*head,*tail;/串的头指针和尾指针串的头指针和尾指针int curlen;/

7、串的当前长度串的当前长度LString;链式存储表示链式存储表示第12页，本讲稿共59页 2022年9月23日 算法目的：算法目的：BFBF算法算法（又称古典的、经典的、朴素的、穷举的）（又称古典的、经典的、朴素的、穷举的）KMPKMP算法（特点：速度快）算法（特点：速度快）算法种类：算法种类：确定主串中所含子串第一次出现的位置（定位）确定主串中所含子串第一次出现的位置（定位）即如何实现教材即如何实现教材P72 Index(S,T,pos)函数函数串的模式匹配算法串的模式匹配算法第13页，本讲稿共59页 2022年9月23日 S:ababcabcacbabT:abcijS:ababcabcac

8、babT:abcS:ababcabcacbabT:abci i i i指针回溯指针回溯指针回溯指针回溯BFBF算法设计思想算法设计思想第14页，本讲稿共59页 2022年9月23日 将主串的第将主串的第pospos个字符和模式的第一个字符比较，个字符和模式的第一个字符比较，若若相等相等，继续逐个比较后续字符；，继续逐个比较后续字符；若若不等不等，从主串的下一字符起，重新与模式的第一个字，从主串的下一字符起，重新与模式的第一个字符比较。符比较。直到主串的一个连续子串字符序列与模式相等直到主串的一个连续子串字符序列与模式相等 。返。返回值为回值为S S中与中与T T匹配的子序列匹配的子序列第一个字

9、符的序号第一个字符的序号，即匹配，即匹配成功。成功。否则，匹配失败，返回值否则，匹配失败，返回值 0 0BFBF算法设计思想算法设计思想Index(S,T,pos)第15页，本讲稿共59页 2022年9月23日 int Index(Sstring S,Sstring T,int pos)i=pos;j=1;while(i=S 0&j T 0)return iT0;else return 0;BFBF算法描述（算法算法描述（算法4.14.1）第16页，本讲稿共59页 2022年9月23日 若若n n为主串长度，为主串长度，m m为子串长度，最坏情况是为子串长度，最坏情况是BFBF算法时间复杂度算

10、法时间复杂度主串前面主串前面n-mn-m个位置都部分匹配到子串的最后一位，即个位置都部分匹配到子串的最后一位，即这这n-mn-m位各比较了位各比较了m m次次最后最后m m位也各比较了位也各比较了1 1次次总次数为：总次数为：(n-m)*m+m(n-m+1)*m若若mn，则算法复杂度，则算法复杂度O(n*m)例：例：S=S=00000000010000000001，T=T=00010001，pos=1pos=1第17页，本讲稿共59页 2022年9月23日 利用已经利用已经部分匹配部分匹配的结果而加快模式串的滑动速度，的结果而加快模式串的滑动速度，且主串且主串S S的指针的指针i i不必回溯不

11、必回溯！亲！可提速到！亲！可提速到O(n+m)O(n+m)哦！哦！S=ababcabcacbabT=T=abcacS=ababcabcacbabT=T=abcacS=ababcabcacbabT=T=abcaci ii ii ik kk kabaabck ki ii iKMPKMP算法设计思想（了解）算法设计思想（了解）第18页，本讲稿共59页KMP算法的算法的时间复杂度时间复杂度可以达到可以达到O(m+n)当当SiTj时，已经得到的结果时，已经得到的结果:Si-j+1.i-1=T1.j-1若已知若已知T1.k-1=Tj-k+1.j-1则有则有Si-k+1.i-1=T1.k-1三、三、KMP(

12、D.E.Knuth,V.R.Pratt,KMP(D.E.Knuth,V.R.Pratt,J.H.Morris)J.H.Morris)算法算法第19页，本讲稿共59页定义：模式串的定义：模式串的next函数函数第20页，本讲稿共59页intIndex_KMP(SStringS,SStringT,intpos)/1posStrLength(S)i=pos;j=1;while(i=S0&jT0)returni-T0;/匹配成功匹配成功elsereturn0;/Index_KMP第21页，本讲稿共59页这实际上也是一个匹配的过程，这实际上也是一个匹配的过程，不同在于：主串和模式串是同一个串不同在于：主

13、串和模式串是同一个串求求next函数值的过程是一个函数值的过程是一个递推过程，分析如下递推过程，分析如下:已知：已知：next1=0；假设：假设：nextj=k；又；又Tj=Tk则：则：nextj+1=k+1若：若：Tj Tk则则需往前回朔，检查需往前回朔，检查Tj=T？第22页，本讲稿共59页voidget_next(SString&T,int&next)/求模式串求模式串T的的next函数值并存入数组函数值并存入数组next。i=1;next1=0;j=0;while(iT0)if(j=0|Ti=Tj)+i;+j;nexti=j;elsej=nextj;/get_next第23页，本讲稿共

14、59页还有一种特殊情况需要考虑：还有一种特殊情况需要考虑：例如：例如：S=aaabaaabaaabaaabaaab T=aaaab nextj=01234nextvalj=00004第24页，本讲稿共59页voidget_nextval(SString&T,int&nextval)i=1;nextval1=0;j=0;while(i 0 a,i=0 a+i*la第34页，本讲稿共59页 2022年9月23日 二维数组二维数组第35页，本讲稿共59页 2022年9月23日 以行序为主序以行序为主序C,PASCAL数组的顺序存储数组的顺序存储第36页，本讲稿共59页 2022年9月23日 以列序为

15、主序FORTRAN第37页，本讲稿共59页 2022年9月23日 anm设数组开始存放位置设数组开始存放位置LOC(0,0)=aLOC(j,k)=a+j*m+k二维数组的行序优先表示二维数组的行序优先表示第38页，本讲稿共59页 2022年9月23日 设有二维数组设有二维数组A10,20A10,20，其每个元素占两个字节，其每个元素占两个字节，A A0000存储地址为存储地址为100100，若，若按行优先按行优先顺序存储，则元素顺序存储，则元素A6,6A6,6的存的存储地址为储地址为 ，按列优先按列优先顺序存储，元素顺序存储，元素A6,6A6,6的存的存储地址为储地址为 。课堂任务课堂任务（经

16、验值（经验值200）352352232232(6*20+6)*2+100=352(6*20+6)*2+100=352(6*10+6)*2+100=232(6*10+6)*2+100=232第39页，本讲稿共59页 2022年9月23日 设设有有一一个个二二维维数数组组A A m mn n 按按行行优优先先顺顺序序存存储储，假假设设A A0000存存放放位位置置在在644644(10)(10)，A A2222存存放放位位置置在在676676(10)(10)，每每个个元元素素占占一一个个空空间间，问问A A3333(10)(10)存存放放在在什什么位置？脚注么位置？脚注(10)(10)表示用表示用

17、1010进制表示。进制表示。设数组元素设数组元素Aij存放在起始地址为存放在起始地址为Loc(i,j)的存储单元中的存储单元中Loc(2,2)=Loc(0,0)+2*n+2=644+2*n+2=676.n=(676-2-644)/2=15Loc(3,3)=Loc(0,0)+3*15+3=644+45+3=692.课堂任务课堂任务（经验值（经验值200200）第40页，本讲稿共59页 2022年9月23日 1.什么是压缩存储？什么是压缩存储？若多个数据元素的若多个数据元素的值都相同值都相同，则只分配一个元素值的存，则只分配一个元素值的存储空间，且零元素不占存储空间。储空间，且零元素不占存储空间。

18、2.什么样的矩阵能够压缩？什么样的矩阵能够压缩？一些值相同的元素或零元素在矩阵中分布有规律的特殊矩阵，一些值相同的元素或零元素在矩阵中分布有规律的特殊矩阵，如：对称矩阵，对角矩阵，三角矩阵，稀疏矩阵等。如：对称矩阵，对角矩阵，三角矩阵，稀疏矩阵等。3.什么叫稀疏矩阵？什么叫稀疏矩阵？矩阵中非零元素的个数较少（一般小于矩阵中非零元素的个数较少（一般小于5%5%）特殊矩阵的压缩存储特殊矩阵的压缩存储(课堂自学，完成以下任务，每任务课堂自学，完成以下任务，每任务200200经验值经验值)第41页，本讲稿共59页 2022年9月23日 4.3 4.3 广义表广义表广义表（列表）：广义表（列表）：n(0

19、)个表元素组成的有限序列个表元素组成的有限序列，记作记作LS=(a0,a1,a2,an-1)LS是是表表名名，ai是是表表元元素素，它它可可以以是是表表(称称为为子子表表)，可可以以是是数数据据元元素素(称为称为原子原子)。n为表的长度。为表的长度。n=0的广义表为空表。的广义表为空表。第42页，本讲稿共59页 2022年9月23日 线性表的成分都是结构上不可分的单元素线性表的成分都是结构上不可分的单元素广义表的成分可以是单元素，也可以是有结构的表广义表的成分可以是单元素，也可以是有结构的表线性表是一种特殊的广义表线性表是一种特殊的广义表广义表不一定是线性表，也不一定是线性结构广义表不一定是线

20、性表，也不一定是线性结构广义表与线性表的区别？广义表与线性表的区别？（每答出一条区别加经验值（每答出一条区别加经验值100100）第43页，本讲稿共59页 2022年9月23日 广义表的基本运算广义表的基本运算（1）求表头求表头GetHead(L)：非空广义表的第一个元素，：非空广义表的第一个元素，可以是一个单元素，也可以是一个子表可以是一个单元素，也可以是一个子表（2）求表尾求表尾GetTail(L)：非空广义表除去表头元素以外：非空广义表除去表头元素以外其它元素所构成的表。其它元素所构成的表。表尾一定是一个表。表尾一定是一个表。第44页，本讲稿共59页 2022年9月23日 练习求表头表尾

21、练习求表头表尾（每题（每题100100经验值）经验值）A=()GetHead 和和GetTail均无定义均无定义A=(a,b)GetHead(A)=a GetTail(A)=(b)A=(a)GetHead(A)=a GetTail(A)=()A=(a)GetHead(A)=(a)GetTail(A)=()GetHead(GetTail(GetHead(GetTail(GetTail(A)=？A=(a,b,(c,d),(e,(f,g)d第45页，本讲稿共59页 2022年9月23日 有次序性有次序性有长度有长度有深度有深度可递归可递归可共享可共享一个直接前驱和一个直接后继一个直接前驱和一个直接后

22、继表中元素个数表中元素个数表中括号的重数表中括号的重数自己可以作为自己的子表自己可以作为自己的子表可以为其他广义表所共享可以为其他广义表所共享广义表的特点广义表的特点第46页，本讲稿共59页 2022年9月23日 E=(a,E)=(a,(a,E)=(a,(a,(a,.)，E为递归表为递归表1）A=()2）B=(e)3）C=(a,(b,c,d)4）D=(A,B,C)5）E=(a,E)n=0，因为因为A是空表是空表n=1，表中元素，表中元素e是原子是原子n=2，a为原子，为原子，(b,c,d)为子表为子表n=3，3个元素都是子表个元素都是子表n=2，a为原子，为原子，E为子表为子表D=(A,B,C

23、)=(),(e),(a,(b,c,d)，共享表共享表练习：求下列广义表的长度练习：求下列广义表的长度（每题经验值（每题经验值100100）第47页，本讲稿共59页 2022年9月23日 1.了解串的存储方法，理解串的两种模式匹配了解串的存储方法，理解串的两种模式匹配算法，重点掌握算法，重点掌握BF算法算法。2.明确数组和广义表这两种数据结构的特点，明确数组和广义表这两种数据结构的特点，掌握掌握数组地址计算方法数组地址计算方法，了解几种特殊矩阵，了解几种特殊矩阵的压缩存储方法。的压缩存储方法。3.掌握广义表的定义、性质及其掌握广义表的定义、性质及其GetHead和和GetTail的操作的操作。小

24、结小结第48页，本讲稿共59页进阶任务进阶任务（每任务（每任务100经验值）经验值）（1）串是一种特殊的线性表，其特殊性体现在（）串是一种特殊的线性表，其特殊性体现在（）。）。A可以顺序存储可以顺序存储B数据元素是一个字符数据元素是一个字符C可以链式存储可以链式存储D数据元素可以是多个字符若数据元素可以是多个字符若（2）串下面关于串的的叙述中，（）串下面关于串的的叙述中，（）是不正确的？）是不正确的？A串是字符的有限序列串是字符的有限序列B空串是由空格构成的串空串是由空格构成的串C模式匹配是串的一种重要运算模式匹配是串的一种重要运算D串既可以采用顺序存储，也可以采用链式存储串既可以采用顺序存储

25、，也可以采用链式存储（3）串）串“ababaaababaa”的的next数组为（数组为（）。）。A012345678999B012121111212C011234223456D0123012322345第49页，本讲稿共59页进阶任务进阶任务（每任务（每任务100经验值）经验值）（4）串）串“ababaabab”的的nextval为（为（）。）。A010104101B010102101C010100011D010101011（5）串的长度是指（）串的长度是指（）。）。A串中所含不同字母的个数串中所含不同字母的个数B串中所含字符的个数串中所含字符的个数C串中所含不同字符的个数串中所含不同字符的个

26、数D串中所含非空格字符的个数串中所含非空格字符的个数（6）假设以行序为主序存储数组）假设以行序为主序存储数组A=array1.100,1.100，设每个数，设每个数据元素占据元素占2个存储单元，基地址为个存储单元，基地址为10，则，则LOC5,5=（）。）。A808B818C1010D1020第50页，本讲稿共59页进阶任务进阶任务（每任务（每任务100经验值）经验值）（7）设有数组）设有数组Ai,j，数组的每个元素长度为，数组的每个元素长度为3字节，字节，i的值为的值为1到到8，j的值为的值为1到到10，数组从内存首地址，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素开始顺序存放

27、，当用以列为主存放时，元素A5,8的存储的存储首地址为（首地址为（）。）。ABA+141BBA+180CBA+222DBA+225（8）设有一个）设有一个10阶的对称矩阵阶的对称矩阵A，采用压缩存储方式，以行序为主存储，采用压缩存储方式，以行序为主存储，a11为第一为第一元素，其存储地址为元素，其存储地址为1，每个元素占一个地址空间，则，每个元素占一个地址空间，则a85的地址为（的地址为（）。）。A13B33C18D40（9）若对）若对n阶对称矩阵阶对称矩阵A以行序为主序方式将其下三角形的元素以行序为主序方式将其下三角形的元素(包括主对角线上所包括主对角线上所有元素有元素)依次存放于一维数组依

28、次存放于一维数组B1.(n(n+1)/2中，则在中，则在B中确定中确定aij（ij）的位置）的位置k的关系为（的关系为（）。）。Ai*(i-1)/2+jBj*(j-1)/2+iCi*(i+1)/2+jDj*(j+1)/2+i第51页，本讲稿共59页进阶任务进阶任务（每任务（每任务100经验值）经验值）（10）AN，N是对称矩阵，将下面三角（包括对角线）以行序存是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组储到一维数组TN(N+1)/2中，则对任一上三角元素中，则对任一上三角元素aij对应对应Tk的下标的下标k是（是（）。）。Ai(i-1)/2+jBj(j-1)/2+iCi(j-i)/

29、2+1Dj(i-1)/2+1（11）设二维数组）设二维数组A1.m，1.n（即（即m行行n列）按行存储在数组列）按行存储在数组B1.m*n中，则二维数组元素中，则二维数组元素Ai,j在一维数组在一维数组B中的下标中的下标为（为（）。）。A(i-1)*n+jB(i-1)*n+j-1Ci*(j-1)Dj*m+i-1（12）数组）数组A0.4,-1.-3,5.7中含有元素的个数（中含有元素的个数（）。）。A55B45C36D16第52页，本讲稿共59页进阶任务进阶任务（每任务（每任务100经验值）经验值）（13）广义表）广义表A=(a,b,(c,d),(e,(f,g)，则，则Head(Tail(He

30、ad(Tail(Tail(A)的值为（的值为（）。）。A(g)B(d)CcDd（14）广义表）广义表(a,b,c,d)的表头是（的表头是（），表尾是（），表尾是（）。）。AaB()C(a,b,c,d)D(b,c,d)（15）设广义表）设广义表L=(a,b,c)，则，则L的长度和深度分别为（的长度和深度分别为（）。）。A1和和1B1和和3C1和和2D2和和3 第53页，本讲稿共59页进阶任务进阶任务（每任务（每任务200经验值）经验值）（1）已已知知模模式式串串t=abcaabbabcab写写出出用用KMP法法求求得得的的每每个个字字符符对对应应的的next和和nextval函数值。函数值。模式

31、串模式串t t的的nextnext和和nextvalnextval值如下：值如下：j1 2 3 4 5 6 7 8 9 10 11 12 t串a b c a a b b a b c a bnextj0 1 1 1 2 2 3 1 2 3 4 5nextvalj0 1 1 0 2 1 3 0 1 1 0 5第54页，本讲稿共59页进阶任务进阶任务（每任务（每任务200经验值）经验值）（3）数组）数组A中，每个元素中，每个元素Ai,j的长度均为的长度均为32个二进位个二进位,行下标从行下标从-1到到9，列下标从，列下标从1到到11，从，从首地址首地址S开始连续存放主存储器中，主存储器字长为开始连续

32、存放主存储器中，主存储器字长为16位。求：位。求：存放该数组所需多少单元？存放该数组所需多少单元？存放数组第存放数组第4列所有元素至少需多少单元？列所有元素至少需多少单元？数组按行存放时，元素数组按行存放时，元素A7,4的起始地址是多少？的起始地址是多少？数组按列存放时，元素数组按列存放时，元素A4,7的起始地址是多少？的起始地址是多少？每个元素每个元素32个二进制位，主存字长个二进制位，主存字长16位，故每个元位，故每个元素占素占2个字长，行下标可平移至个字长，行下标可平移至1到到11(共共11行，行，11列列)。（1）11*11*2=242（2）11*2=22（3）s+(8*11+3)*2

33、=s+182（4）s+(6*11+5)*2=s+142第55页，本讲稿共59页进阶任务进阶任务（每任务（每任务200经验值）经验值）（4）请将香蕉）请将香蕉banana用工具用工具H()Head()，T()Tail()从从L中取出。中取出。L=(apple,(orange,(strawberry,(banana),peach),pear)H（H（T（H（T（H（T（L）第56页，本讲稿共59页进阶任务进阶任务（每任务（每任务200经验值）经验值）（5）写写一一个个算算法法统统计计在在输输入入字字符符串串中中各各个个不不同同字字符符出出现现的的频频度度并并将将结结果果存存入入文文件件（字字符符串

34、串中中的的合合法法字字符符为为A-Z这这26个个字母和字母和0-9这这10个数字）。个数字）。voidCount（）（）/统计输入字符串中数字字符和字母字符的个数。统计输入字符串中数字字符和字母字符的个数。inti，num36；charch；for（i0；i36；i+）numi；/初始化初始化while（chgetchar（）（）!=#）/#表示输入字符串结束。表示输入字符串结束。if（0=ch=9）i=ch48;numi+；/数字字符数字字符elseif（A=ch=Z）i=ch-65+10;numi+；/字母字符字母字符for（i=0；i10；i+）/输出数字字符的个数输出数字字符的个数pr

35、intf（“数字数字d的个数的个数dn”，i，numi）；）；for（i10；i36；i+）/求出字母字符的个数求出字母字符的个数printf（“字母字符字母字符c的个数的个数dn”，i55，numi）；）；/算法结束。算法结束。第57页，本讲稿共59页进阶任务进阶任务（每任务（每任务200经验值）经验值）1.树的逻辑特征是什么？树的逻辑特征是什么？2.二叉树的特征是什么？有什么性质？二叉树的特征是什么？有什么性质？只有一个根结点只有一个根结点(无前驱无前驱)，多个叶子结点，多个叶子结点(无后继无后继)，多个其，多个其它分支结点它分支结点(一个前驱、多个后继一个前驱、多个后继)二叉树二叉树或为

36、空树或为空树；或是由一个根结点加上两棵分别称为；或是由一个根结点加上两棵分别称为左子树左子树和和右子树右子树的、的、互不交的互不交的二叉树组成。二叉树组成。5个性质，见个性质，见P100101。第58页，本讲稿共59页实验三实验三 串及其应用（串及其应用（KMPKMP算法）算法）【实验目的实验目的】（1）掌握串的特点及顺序存储的方式。）掌握串的特点及顺序存储的方式。（2）掌握模式匹配的基本思想及其算法。）掌握模式匹配的基本思想及其算法。【实验内容实验内容】（1）由用户通过键盘输入建立一个主字符串和待匹配的子）由用户通过键盘输入建立一个主字符串和待匹配的子串；串；（2）由用户通过键盘输入子串匹配的起始位置；）由用户通过键盘输入子串匹配的起始位置；（3）由程序求出并输出子串在主串中的位置。）由程序求出并输出子串在主串中的位置。第59页，本讲稿共59页