数据结构-串(1)

串(string)是由零个或多个字符组成的有限序列，又叫字符串。

 一般记做s =”a1a2….an” （n>=0），s是串的名字，用双引号括起来的

字符串是串的值。

串中的字符数目n称为串的长度。n是一个有限的数值。

零个字符的串称为空串(null string),长度为零。可以直接用双引号””表示。

空格串是只包含空格的串。是与空串有区别的，空格串是有内容有长度的，而且可以不止一个空格。

串的比较

串的比较是通过组成串的字符之间的编码来进行的，而字符的编码指的是字符在对应字符集中的序号。

给定两个字符串: s=”a1a2…..an”, t=”b1b2…bm”,

仅当n=m，并且a1=b1,a2=b2,…,an=bm时，s=t。

当满足以下条件之一时，s<t。

1. n<m, 且ai=bi(i=1,2,…,n)。

例如：s = “hap”, t=”happy” s的长度< t的长度

1. 存在某个k<=min(m,n),使得ai=bi(i=1,2,…,k-1), ak<bk;

例如：s =”happen”, t=”happey”， e的ASCII码是101 ，y的ASCII码是121, e < y。

串的抽象数据类型

串比较关心查找子串位置，得到指定位值子串，替换子串等操作。

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存在，T是非空串，1<=pos<=StrLength(S)。若主串S中存在和T值相同的子串，
                  则返回它在主串S中第pos个字符之后第一次出现的位置，否则返回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