首页 > 代码库 > 数据结构与算法---字符串（上）
数据结构与算法---字符串（上）
hey,you guys.
好久没有继续我们的数据结构学习了，今天让我们一起来学习，开发中非常重要的一种数据类型--字符串。关于字符串，大家应该不会陌生。例如，我们做web开发，需要校验用户输入的注册信息是否合法，或者判断用户输入的账户、密码、是否正确等等。我们通过调用字符串的相关函数，就可以解决我们的需求。古语有云:”知其然，知其所以然”。我们要做的，不仅仅是会调用字符串的方法，更要明白这些方法的原理。例如，在没有学习字符串之前，我认为要比较两个字符串是否相等，只需这样：
string sentence = "im a chinese"; string sentence2 = "im a brazilian"; int result = String.Compare(sentence, sentence2); if (result > 0) Console.Write("sentence>sentence2"); if (result == 0) Console.Write("sentence==sentence2"); if (result < 0) Console.Write("sentence<sentence2");
是的,通过调用String类的Compare()方法，可以判断出sentence与sentence2是否相等。但是，Compare()方法，是如何比较两个字符串的呢？不要小看字符串比较这个简单的操作，其中用到了一个很强大的算法---KMP模式匹配算法(下文，会专门讲解)。如果，我们能掌握理解这些字符串的基础算法，那么对我们将来使用字符串类会有很大的帮助。这也是，为什么要强调数据结构与算法的重要性。程序员，不懂数据结构，不懂算法，那永远都称不上是合格的程序员。好了，书归正传，让我们来一起学习字符串吧。
字符串概念:
电脑诞生的理由，是因为人们需要利用它来进行数值计算。说白了，最初的电脑相当于我们平时使用的计算器。不同的是，电脑比计算器体格大一些，计算时间快一些。慢慢的，只能计算数值的电脑，不能满足人们日益增长的需求。这时，电脑开始引入对字符串的处理，于是就有了字符串的概念。
串(String): 是由零个或多个字符组成的有限序列，又称字符串。
首先，字符串一定是有限的，也就是一定是有长度的。长度为零的字符串，称为空串(Null String)。大家要注意，字符为空格的字符串与空串是不同的.看代码:
string sentence = ""; //空串sentence，长度为0 string sentence2 = " "; //字符为空格的字符串sentence2，长度为3
子串:串中任意个数的连续字符组成的子序列称为该串的子串，相应地，包含子串的串称为主串。
string sentence = "beautiful";//主串 string subsentence = "ful";//字串
上面的subsentence串可以称为sentence串的子串，相应地，sentence串可以称为subsentence串的主串。
串的比较
int numberA = 12; int numberB = 10; // numberA>numberB string sentenceA = "stupid"; string sentenceB = "silly"; //sentenceA>sentenceB? sentenceA<sentenceB? ??????
就像上面的代码所展示的一样，因为12大于10，所以numberA>numberB。stupid，silly,都是愚蠢的意思，那么sentenceA==sentenceB?stupid,是六个字符，silly，是五个字符，所以sentenceA>sentenceB?两个数值类型可以比较大小，那么两个串类型如何比较大小呢？原来计算机处理字符时，需要先对字符进行字符编码。所谓的字符编码，就是字符在对应字符集中的下标。所以，字符之间的比较，说白了，也是值比较。就是将字符所在字符集中的下标拿来比较。常用的字符集有ASCII、Unicode等。
串的抽象数据类型
ADT串(string) Data 串中元素仅由一个字符组成，相邻元素具有前驱和后继关系。 Operation StrAssign(T,*chars):生成一个其值等于字符串常量chars的串T StrCopy(T,S)：串S存在，由串S复制得到串T ClearString(S):串S存在，将串清空 StringEmpty(S):若串S为空，则返回True,否则返回FALSE StrLength(S):返回S的元素个数，即串的长度 StrCompare(S,T):若S>T，返回值>0，若S<T,返回值<0,若S==T，返回0 Concat(T,S1,S2):用T返回S1和S2联接而成的新串 SubString(sub,S,pos,len):串S存在，1<=pos<=StrLength(S)并且0<=len<=StrLength(S)-pos+1,用Sub返回S串中pos位置起向后截取len长度的字串 Index(S,T,pos):串S、T存在，1<=pos<=StrLength(S),若S串中存在T串，则在S串pos位置之后中第一次出现T串的位置。如果S串中不存在T串，则返回0 Replace(S,T,V):串S、T、V存在，T是非空串。用V替换主串S中出现的所有与T相等的不重叠的字串。 StrInsert(S,pos,T):串S、T存在，1<=pos<=StrLength(S)+1。在串S的第pos个字符之前插入串T。 StrDelete(S,pos,len):串S存在，1<=pos<=StrLength(S)-len+1.从串S中删除第pos个字符起长度为len的字串。 endADT
串的抽象数据类型中的操作，是不是很熟悉？我们项目中是不是用过这些方法，例如截取字符串的SubString()、替换子串的Replace().之前我们只会调用，今天我们会学习如何来实现这些功能。
串的存储结构
串的存储结构与线性表很相似，也分为顺序存储，链式存储两种方式.
顺序存储:用内存中地址连续的存储空间来存放串的有限序列。按照预定义的大小，为每个定义的串变量分配一个固定长度的存储区。一般用定长数组来定义。
链式存储:与线性表链式存储不同的是，如果串的链式存储也像线性表那样每个结点存放一个字符，那么会造成很大的浪费。所以，串的链式存储，每个结点存放多个字符。
朴素的模式匹配算法
什么叫做模式匹配呢？例如，我们在一篇英文文章中，检索某个单词。说白了，就是字串在主串中定位。模式匹配是字符串中最重要的操作之一。假设，现有主串S=”goodgoogle“,找到T=”google“这个子串的位置。我们需要如下几步:
主串的字符依次与子串的字符匹配，当主串中第四个位置d与字串中第四个位置g不同时。主串的第二个位置o开始第二轮的与子串匹配的操作：
主串的第二位o与字串的第一位g不匹配，那就拿o的下一个字符重新来匹配子串：
配对不成功，就拿主串中的上次匹配的字符的下一位，与子串重新匹配:
配对不成功，继续拿主串的字符匹配字串:
最终匹配成功.
通过以上的步骤，其实就可以想到朴素的模式匹配算法的原理了。就是对主串从第一个字符开始循环，依次对子串的字符进行匹配。主串进行大循环，子串进行小循环。我们来看一下算法:
Status Index(String S, String T, int pos) { int i = pos;//主串开始循环的位置 int j = 1;//字串开始循环的位置 while (i <= S[0] && j <= T[0]) //S[0]存放的是串S的长度，T[0]存放的是串T的长度 { if (S[i == T[j]]) { i++; j++; } else { j = 1; //当字符匹配不对时，j指向T串的第一个字符 i = i - j + 2; //i指向S串上次匹配成功的字符的下一个字符 } } if (j > T[0]) return i - T[0]; else return 0;}
这个算法不难理解，i控制的是主串的循环，j控制的是子串的循环。如果模式匹配成功，就返回主串pos位置之后首次出现T串的位置。模式匹配不成功，就返回0.
我们来分析一下这个算法，最好的情况是，在主串第一个字符去匹配时，就成功，不需要主串中其他字符去匹配。例如,S=”Googlegood”,T=”Google”.稍差一点的，就像:
一开始就匹配不成功。
最差的情况，每次匹配不成功都发生在子串T的最后一位。例如,主串S=”00000000000000000000000001” 子串T=”0000001”.这样一分析，这个朴素的模式匹配效率也太低了。低就低在，判断过的字符，还在继续判断。
数据结构与算法---字符串（上）