数据结构笔记8串（《大话数据结构》学习笔记）
【1】串的定义
串(string)是由零个或多个字符组成的有限序列,又名叫字符串。
一般记为 s= " a1a2… … .an " ( n>0), 其中, s 是串的名称,用双引号(有些书中也用单引号)括起来的字符序列是串的值,注意单引号不属于串的内容 。 ai可以是字母 、 数字或其他字符 , i 就是该字符在串中的位置。 串中的字符数目 n 称为串的长度, 定义中谈到"有限"是指长度 n 是一个有限的数值 。 零个字符的审称为空串 ( null string) , 宫的长度为零,可以直接用两双引号 "…’ 表示。
【2】串的比较
事实上 , 串的比较是通过组成串的字符之间的编码来进行的 , 而字符的编码指的是字符在对应字符集中的序号。
如果我们要在 C 语言中比较两个串是否相等,必须是它们串的长度以及它们各个对应位置的字特都相等时,才算是相等。即给定两个串
s= “a1a2 … a n” ,t=“b 1 b2 … … bm” ,当且仅当 n=m ,且 al=bl , a2=切 ,…, an=bm 时 ,我们认为 s=t 。
【3】串的抽象数据类型
【4】串的存储结构
4.1串的顺序存储结构
串的顺序存储结构是用 一组地址连续的存储单元来存储串中的字符序列的。按照预定义的大小,为每个定义的感变量分配一个固定长度的存储区。一般是用定长数组来定义。既然是定长数组,就存在一个预定义的最大串长度, 一般可以将实际的串长度值保存在数组的0下标位置，有的书中也会定义存储在数组的最后一个下标位置。
对于串的顺序存储,有一些变化,串值的存储空间可在程序执行过程中动态分配而得。比如在计算机中存在一个自由存储区,叫做"堆"。这个堆可由 C 语言的动态分配函数 malloc()和 free ()来管理。
4.2串的链式存储结构
对于串的链式存储结构,与线性表是相似的,但由于串结构的特殊性,结构中的每个元素数据是一个字符,如果也简单的应用链表存储串值, 一 个结点对应 一个字符,就会存在很大的空间浪费 。 因此,一个结点可以存放一个字符,也可以考虑存放多个字符,最后一 个结点若是未被占满时,可以用" #" 或其他非率值字符补全
【5】朴素的模式匹配算法
假设我们要从下面的主串 S=“goodgoogle” 中,找到 T="google"这个子串的位置。我们通常需要下面的步骤 。
1.主串 S 第一位开始, S 与 T 前三个字母都匹配成功,但 S 第四个字母是 d 而 T的是 g 。第一位匹配失败。
- 主串 S 第二位开始,主审 S 首字母是 0 ,要匹配的 T 首字母是 g ,匹配失败。
3.主串 S 第 三位开始,主串 S 首字母是 0 ,要匹配的 T 首字母是 g ，匹配失败。
4 . 主串 S 第四位开始,主串 S 首字母是 d ,要匹配的 T 首字母是 g ,匹配失败。
- 主串 S 第五位开始, S 与 T , 6 个字母全匹配,匹配成功.
简单的说,就是对主串的每一个字符作为子串开头,与要匹配的字符串进行匹配。对主串做大循环,每个字符开头做 T 的长度的小循环,直到匹配成功或全部遍历完成为止。