数据结构课件CD 第04章　串.ppt

《数据结构课件CD 第04章　串.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第4章　串数据结构主讲教师：周时阳本章主要介绍串，它属于线性结构，是数据元素的内部结构确定为符号的特殊线性表。讨论串的逻辑结构、逻辑结构上定义的运算、物理结构、逻辑结构与物理结构对应关系、运算的实现算法与效率分析。重点研究串的概念、基本运算、顺序结构和链式存储结构及其主要运算的实现算法及其效率分析。内容摘要2重点讲解4.1串类型的定义4.2串的表示和实现4.3串的模式匹配算法4.4串应用举例小结34.1.1串的逻辑结构定义及术语串（或字符串）是由零个或零个以上的字符组成的有限序列。一般记为S＝’a1a2…an’(n≥0)其中，S

2、为串名，a1a2…an称为栈串值；ai（1≤i≤n）属于某个字符表，通常字符表取为ASCII表。串中含有字符的个数称为串的长度（即串长）；含有零个字符的串称为空串，其长度为0。4.1串类型的定义实质上，串是限制数据元素取自于某个字符表的特殊线性表。S:(a1,a2,…,ai-1,ai,ai+1,…,an-1,an)4为了讨论的方便，约定空格符号采用符号⊔示意。下面给出基于ASCII表上的串的实例。’$abc123’’while’’3.1415’’x1’’123’’’’⊔⊔⊔’串长：7串长：5，字母串串长：6，数字串串长：2，字母

3、数字串串长：3，数字串串长：0，空串串长：3，空格串串值采用一对单引号括起来，其根本原因是为了避免与变量名、函数名和数据常量等的书写相互混淆而已！5字符a在串S中的序号称为字符a在串S中的位置。串S中任意个连续的字符组成的子序列S’称为串S的子串，串S也称为串S’的主串。字符串S=’LIST_SIZE’序号：123456789主串S=’LIST_SIZE’S的子串：’ST_S’’LIST’’SIZE’’LIST_SIZE’’S’…6子串S’的第一个字符在主串S中的位置称为子串S’串在主串S中的位置。子串的位置：31613主串S=

4、’LIST_SIZE’S的子串：’ST_S’’LIST’’SIZE’’LIST_SIZE’’S’123456789非子串：’STSI’0推论：串S’是串S的子串S’当且仅当S’串在主串S中的位置＞0。7两个串S1和S2相等当且仅当S1和S2串值相等。记为：S1＝S2。例如，假设S1＝’abc123’S2＝’abc123’则S1＝S2两个串S1和S2相等当且仅当S1和S2长度相等，且每个位置对应的字符相等。例如，假设S1＝’abc123’S2＝’abc123’则S1＝S2长度均为6注解：两个定义是等价的、第2个定义便于设计求子串位

5、置运算的算法。8讨论数据“大小”概念问题：1＞2吗？实质上，数据大小是数据排列后，确定的前后顺序关系。例如，我们可以实数顺序排列在数轴上，之后约定排在前面的“小于”后面的。这样，1＜2。0123……-1-2x反之，同样的排列，但约定排在后面的小于前面的。这样，1＞2。即日常的“第1”和“第2”的概念。对于字符串，是将串值按照“字典序”排列，约定排在前面的“小于”后面的，这样规定串的“大小”概念的。94.1.2基本运算定义（1）串赋值StrAssign(&S，chars)S←chars,S是串变量，chars是串常量（2）串复制S

6、trCopy(&S，T)S←T,S和T是串变量（3）判空串StrEmpty(S)（4）串比较StrCompare(S，T)＞0(S＞T)函数值＝0(S＝T)＜0(S＜T)（5）求串长StrLength(S)（6）置空串ClearString(&S)10（7）串连接Concat(&S，S1，S2)将S2串值连接S1串值之后的新串值，赋值于S。例如，假设S1＝’abc’S2＝’123’则Concat(&S，S1，S2)运算后,S＝’abc123’串连接运算－－S2串值连接S1串值之后的新串值！（8）取子串SubString(&Sub

7、，S，pos，len)在串S中从位置pos开始取出长度为len的子串，赋值于Sub。例如，假设S1＝’abc123’则SubString(&Sub，S，2，3)运算后，Sub＝’bc1’注：1≤pos≤Strlength(S),1≤len≤Strlength(S)-pos+1注：另外一种的定义SubString(&Sub，S，i，j)，其中，i和j分别表示“开始序号”和“截止序号”。11（9）求子串位置Index(S，T，pos)从串S的pos位置开始，求串T在S中的位置。如果不再S中，返回0。例如，假设S＝’abc123@23

8、ab%c23’T＝’23’则Index(S，T，2)运算后，返回值5；Index(S，T，6)运算后，返回值8；Index(S，T，9)运算后，返回值14；Index(S，T，15)运算后，返回值0；Index(S，’cb’，1)运算后，返回值0。注：1≤pos