资源描述：
《数据结构 C语言版 教学课件 作者 严蔚敏 李冬梅 吴伟民 第4章 串 数组和广义表.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、2021年10月6日北京林业大学信息学院李冬梅数据结构2021年10月6日北京林业大学信息学院可表示为：（a1,a2,……,an）线性结构第2章线性表第3章栈和队列第4章串、数组和广义表2021年10月6日北京林业大学信息学院串比较，strcmp(chars1,chars2)串复制，strcpy(charto,charfrom)串连接，strcat(charto,charfrom)求串长，strlen(chars)……调用标准库函数#include补充：C语言中常用的串运算2021
2、年10月6日北京林业大学信息学院第4章串、数组和广义表4.1串4.2数组4.3广义表教学内容2021年10月6日北京林业大学信息学院1.掌握串的存储方法，理解串的两种模式匹配算法；2.明确数组和广义表这两种数据结构的特点，掌握数组存储时地址计算方法，了解几种特殊矩阵的压缩存储方法。教学目标1.了解串的存储方法，理解串的两种模式匹配算法，重点掌握BF算法。2.明确数组和广义表这两种数据结构的特点，掌握数组地址计算方法，了解几种特殊矩阵的压缩存储方法。3.掌握广义表的定义、性质及其GetHead和GetT
3、ail的操作。2021年10月6日北京林业大学信息学院4.1串串(String)----零个或多个字符组成的有限序列串名串值串长n空串n=02021年10月6日北京林业大学信息学院a=‘BEI’,b=‘JING’c=‘BEIJING’d=‘BEIJING’子串字符位置主串子串位置串相等空格串2021年10月6日北京林业大学信息学院数据对象:数据关系:基本操作:(1)StrAssign(&T,chars)//串赋值(2)StrCompare(S,T)//串比较(3)StrLength(S)//求串长(4
4、)Concat(&T,S1,S2)//串联ADTString{串的抽象数据类型2021年10月6日北京林业大学信息学院(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,
5、len)//子串删除(13)DestroyString(&S)//串销毁}ADTString2021年10月6日北京林业大学信息学院顺序存储链式存储串的存储结构2021年10月6日北京林业大学信息学院typedefstruct{char*ch;//若串非空,则按串长分配存储区,//否则ch为NULLintlength;//串长度}HString;顺序存储表示2021年10月6日北京林业大学信息学院链式存储表示2021年10月6日北京林业大学信息学院#defineCHUNKSIZE80//可由用户定义的
6、块大小typedefstructChunk{charch[CHUNKSIZE];structChunk*next;}Chunk;typedefstruct{Chunk*head,*tail;//串的头指针和尾指针intcurlen;//串的当前长度}LString;链式存储表示2021年10月6日北京林业大学信息学院可将多个字符存放在一个结点中，以克服其缺点优点：操作方便缺点：存储密度较低实际分配的存储位串值所占的存储位存储密度=链式存储表示2021年10月6日北京林业大学信息学院算法目的：BF算法（
7、又称古典的、经典的、朴素的、穷举的）KMP算法（特点：速度快）算法种类：确定主串中所含子串第一次出现的位置（定位）即如何实现教材P72Index(S,T,pos)函数串的模式匹配算法2021年10月6日北京林业大学信息学院S:ababcabcacbabT:abcijS:ababcabcacbabT:abcS:ababcabcacbabT:abci指针回溯BF算法设计思想2021年10月6日北京林业大学信息学院将主串的第pos个字符和模式的第一个字符比较，若相等，继续逐个比较后续字符；若不等，从主串的下
8、一字符起，重新与模式的第一个字符比较。直到主串的一个连续子串字符序列与模式相等。返回值为S中与T匹配的子序列第一个字符的序号，即匹配成功。否则，匹配失败，返回值0BF算法设计思想Index(S,T,pos)2021年10月6日北京林业大学信息学院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
