资源描述：
《数据结构串数组和广义表课件教学内容.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数据结构串数组和广义表课件第4章串、数组和广义表1.了解串的存储方法，理解串的两种模式匹配算法，重点掌握BF算法。2.明确数组和广义表这两种数据结构的特点，掌握数组地址计算方法，了解几种特殊矩阵的压缩存储方法。3.掌握广义表的定义、性质及其GetHead和GetTail的操作。4.1串串(String)----零个或多个字符组成的有限序列串名串值串长n空串n=0a=‘BEI’,b=‘JING’c=‘BEIJING’d=‘BEIJING’子串字符位置主串子串位置串相等空格串数据对象:数据关系:基本操作:(1)StrAssign(&T,chars)//串赋值(2)StrCompa
2、re(S,T)//串比较(3)StrLength(S)//求串长(4)Concat(&T,S1,S2)//串联ADTString{串的抽象数据类型(5)SubString(&Sub,S,pos,len)//求子串(6)StrCopy(&T,S)//串拷贝(7)StrEmpty(S)//串判空(8)ClearString(&S)//清空串(9)Index(S,T,pos)//子串的位置(10)Replace(&S,T,V)//串替换(11)StrInsert(&S,pos,T)//子串插入(12)StrDelete(&S,pos,len)//子串删除(13)DestroyStr
3、ing(&S)//串销毁}ADTString顺序存储链式存储串的存储结构typedefstruct{char*ch;//若串非空,则按串长分配存储区,//否则ch为NULLintlength;//串长度}HString;顺序存储表示链式存储表示#defineCHUNKSIZE80//可由用户定义的块大小typedefstructChunk{charch[CHUNKSIZE];structChunk*next;}Chunk;typedefstruct{Chunk*head,*tail;//串的头指针和尾指针intcurlen;//串的当前长度}LString;链式存储表示可将多
4、个字符存放在一个结点中，以克服其缺点优点：操作方便缺点：存储密度较低实际分配的存储位串值所占的存储位存储密度=链式存储表示算法目的：BF算法（又称古典的、经典的、朴素的、穷举的）KMP算法（特点：速度快）算法种类：确定主串中所含子串第一次出现的位置（定位）串的模式匹配算法S:ababcabcacbabT:abcijS:ababcabcacbabT:abcS:ababcabcacbabT:abci指针回溯BF算法设计思想将主串的第pos个字符和模式的第一个字符比较，若相等，继续逐个比较后续字符；若不等，从主串的下一字符起，重新与模式的第一个字符比较。直到主串的一个连续子串字符序
5、列与模式相等。返回值为S中与T匹配的子序列第一个字符的序号，即匹配成功。否则，匹配失败，返回值0BF算法设计思想Index(S,T,pos)intIndex(SstringS,SstringT,intpos){i=pos;j=1;while(i<=S[0]&&j<=T[0]){if(S[i]=T[j]){++i;++j;}else{i=i-j+2;j=1;}if(j>T[0])returni－T[0];elsereturn0;}BF算法描述（算法4.1）若n为主串长度，m为子串长度，最坏情况是BF算法时间复杂度主串前面n-m个位置都部分匹配到子串的最后一位，即这n-m位各比较
6、了m次最后m位也各比较了1次总次数为：(n-m)*m+m＝(n-m+1)*m若m<7、号页表…………行号起始地址长度行表…………《数据结构》所讨论的数组与高级语言中的数组区别：高级语言中的数组是顺序结构；而本章的数组既可以是顺序的，也可以是链式结构，用户可根据需要选择。4.2数组数组的抽象数据类型数据对象:数据关系:ADTArray{基本操作:(1)InitArray(&A,n,bound1,boundn)//构造数组A(2)DestroyArray(&A)//销毁数组A(3)Value(A,&e,index1,…,indexn)//取数组元素值(4)Assign(A,&e,index
