数据结构-串、数组和广义表课件.ppt

《数据结构-串、数组和广义表课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、可表示为：（a1,a2,……,an）线性结构第2章线性表第3章栈和队列第4章串、数组和广义表第4章串、数组和广义表串比较，strcmp(chars1,chars2)串复制，strcpy(charto,charfrom)串连接，strcat(charto,charfrom)求串长，strlen(chars)……调用标准库函数#include补充：C语言中常用的串运算第4章串、数组和广义表1.了解串的存储方法，理解串的两种模式匹配算法，重点掌握BF算法。2.明确数组和广义表这两种数据结构的特点，掌握数组地址计算方法，了解几种特殊矩阵的压缩存储方法。3.掌握广义表的定义、性质及

2、其GetHead和GetTail的操作。4.1串串(String)----零个或多个字符组成的有限序列串名串值串长n空串n=0a=‘BEI’,b=‘JING’c=‘BEIJING’d=‘BEIJING’子串字符位置主串子串位置串相等空格串数据对象:数据关系:基本操作:(1)StrAssign(&T,chars)//串赋值(2)StrCompare(S,T)//串比较(3)StrLength(S)//求串长(4)Concat(&T,S1,S2)//串联ADTString{串的抽象数据类型(5)SubString(&Sub,S,pos,len)//求子串(6)StrCopy(&T,S)//串拷贝

3、(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)DestroyString(&S)//串销毁}ADTString顺序存储链式存储串的存储结构typedefstruct{char*ch;//若串非空,则按串长分配存储区,//否则ch为NULLintlength;//串长度}HString;顺序存储表示链式存储表示#defineCHUNKS

4、IZE80//可由用户定义的块大小typedefstructChunk{charch[CHUNKSIZE];structChunk*next;}Chunk;typedefstruct{Chunk*head,*tail;//串的头指针和尾指针intcurlen;//串的当前长度}LString;链式存储表示可将多个字符存放在一个结点中，以克服其缺点优点：操作方便缺点：存储密度较低实际分配的存储位串值所占的存储位存储密度=链式存储表示算法目的：BF算法（又称古典的、经典的、朴素的、穷举的）KMP算法（特点：速度快）算法种类：确定主串中所含子串第一次出现的位置（定位）串的模式匹配算法S:ababc

5、abcacbabT:abcijS:ababcabcacbabT:abcS:ababcabcacbabT:abci指针回溯BF算法设计思想将主串的第pos个字符和模式的第一个字符比较，若相等，继续逐个比较后续字符；若不等，从主串的下一字符起，重新与模式的第一个字符比较。直到主串的一个连续子串字符序列与模式相等。返回值为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]

6、){++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位各比较了m次最后m位也各比较了1次总次数为：(n-m)*m+m＝(n-m+1)*m若m<

7、’S=‘ababcabcacbab’T=‘abcac’S=‘ababcabcacbab’T=‘abcac’iiikkabaabckiiKMP算法设计思想（了解）串操作应用举例－－文本编辑文本可被看作一个字符串，称为文本串页则是文本串的子串行又是页的子串。页号起始行号页表…………行号起始地址长度行表…………《数据结构》所讨论的数组与高级语言中的数组区别：高级语言中的数组是顺序结构；而本章的数组既可以是顺序的，也