首页 > 代码库 > 数据结构与算法---字符串（上）
数据结构与算法---字符串（上）
好郁闷的事情，发生在了我的身上。昨天使用Live Writer写了<<数据结构与算法---字符串(上)>>，明明已经发布成功，本人亲自查看过。当我写完<<数据结构与算法---字符串(中)>>，发布成功后。我的博客，只有新发布的数据串(中)，数据串(上)不翼而飞了。真的好郁闷阿，备份也找不到了。看来古人的话还是有道理的:”工欲善其事，必先利其器”。要怪只能怪自己不会使用Live Writer这个工具，好在知识都储备在了脑子中。书归正传，让我们来学习字符串的数据结构吧。
字符串概念
电脑的产生，是为满足人们对数值计算的需求。早期的电脑，除了体格大一些，计算的速度快一些，与计算器没有什么大的区别。但是随着人们的需求不断提高，电脑的数值计算已然不可以满足人们的需求了。所以，电脑开始引入了字符的计算，这才有了字符串的概念。
字符串：由零个或多个字符组成的有限序列。
字符串中的字符个数可以为零，此时字符串称为空串(Null String)，长度为0。大家要注意，空串与空格串是不一样的两种概念。空串是由零个字符组成，字符长度为0。空格串是由n个空格字符组成，字符长度为n。请看下面代码:
static void Main(string[] args) { String sentence1 = ""; //sentence1为空串，长度为0 String sentence2 = " ";//sentence2为空格串，长度为3 }
如果T串存在于S串中，我们就称T串为S串的字串，相对应地，S串称为T串的主串。例如:
static void Main(string[] args) { String sentence1 = "believe in yourself"; //sentence1为sentence2的主串，因为自身包含setence2的字符 String sentence2 = "yourself";//sentence2为sentence1的子串，因为sentence2存在于sentence1中 }
字符串的存储结构
字符串的存储结构，跟线性表的很相似。字符串也分为两种存储结构，顺序存储、线性存储。
顺序存储:用一组地址连续的存储单元来存储字符串中的字符序列，我们一般使用数组来定义。我们习惯于将数组下标为零的位置，存入字符串的长度。
链式存储:对于字符串的链式存储，与线性表的链式存储很相似，但是由于字符串结构的特殊性，结构中的每个元素为字符。如果也按照线性表的链式存储，每个结点存放一个字符，那就会造成很大的空间浪费。一个结点可以存放一个字符，也可以考虑存放多个字符。
字符串的抽象数据类型
我们平时在项目开发中，会经常用到字符串类型的对象。我们使用字符串类型对象可以解决很多需求，例如，通过String类的Index(S,T)方法，可以判断S串中是否包含T串。我们通过String类的Compare()方法，可以检查用户输入的密码、用户名是否正确。我们看看串的抽象数据类型定义:
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串种pos位置之后，第一次出现串T的位置，如果没有，则返回0。 Repalce(S,T,V):串S,T和V存在，T是非空串。用V替换主串S中出现的所有与T相等的不重叠的字串。 StrInsert(S,pos,T)//1<=pos<=Strlength(S)+1在主串中pos位置之前插入字串T StrDelete(S,pos,len)// 1<=pos<=Strlength(S),0<len<=Strlength(S)-pos+1 删除主串中pos位置起长度为len的字串 endADT
这些是串的抽象数据类型，有些操作，可以配合使用。在数据结构与算法---字符串(下)中，我会详细讲解上面那些操作的实现算法。算法+数据结构=编程，合格的程序员，一定要多学习算法，要掌握它的原理，这样学习来就很easy。我在数据结构预算法---字符串(中)，讲解了KMP匹配算法，大家可以看一下。
数据结构与算法---字符串（上）