DataStructure_5.String

本文主要是介绍DataStructure_5.String，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

5.1

5.1.1 串即字符串，由零个或多个字符组成的有限(有限指串的长度n是有限数值)序列，一般记为s="a1a2a3…an"(n≥0)，注意引号不属于串的内容ai(1≤i≤n)可以是字母，数字或其他字符，i就是该字符在串中的位置。n称为串的长度。零个字符的串称为空串(null string)，长度为零，可以直接用双引号表示""""，也可以用空集符号Ф表示，串的相邻字符之间具有前驱与后继的关系。

5.1.2

主串中任意连续字符组成的子序列称为该串的子串，相应的，包含子串的串称为主串，

子串在主串中的位置就是子串的第一个字符在主串中的序号。比如lover和love，friend和end就是主串和子串的关系。

5.2串的比较

当两个串s="a1a2a3…an"和t="b1b2b3…bm"不相等时，规定s<t在满足

①n<m且ai=bi时，如s="hap",t="happy"时，有s<t，因为t比s多两个字母

②存在某个k≤min(m,n)，使得ai=bi，ak<bk，如s="happen",t="happy"时，两串前4个字母均相同，而两串第5个字母(k值)，字母e的ASCⅡ码101<字母y的ASCⅡ码121所以s<t

两个条件之一时成立

5.3串的存储结构

5.3.1 串的顺序存储结构

一般使用定长数组来定义，串的实际长度可以保存在数组下标0的位置也可以保存在最后一个下标位置，也可以像c/c++那样在串后面接一个"\0"来表示串的终结，这时串的长度跑一个遍历就知道了。

但定长数组不可避免的会遇到一个问题，在字符串的操作中(比如两串的连接，新串的插入，字符串的替换)，都有可能使得数组长度爆掉。所以可以使用一个叫做"堆"的动态存储区(可通过C中的malloc()和free()来管理)来创立动态数组，解决定长数组的弊端。

5.3.2 串的链式存储结构

本身与线性表是相似的，但由于串结构的特殊性，一个结点可以考虑存放多个字符，当最后一个结点若是未被占满，可以用"#"或其他非串值字符补全。至于一个结点存放多少字符合适，就需要根据实际情况来选择。</

这篇关于DataStructure_5.String的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---