缥缈峰

     感谢Knife撰写串，Knife是我教研室的同学，签华为成研所。
大家有任何问题可以联系他：knife028_AT_126_DOT_com

---

作者：Knife(knife028_AT_126_DOT_com)


     有关串的定义和操作是大家在找工作时被问及较多的咚咚，在此和大家一起回顾和总结一下，达到共同学习的目的哈

一、串的基本概念
     串（或字符串），是由零个或多个字符组成的有限序列。串中字符的数目称为串的长度。零个字符的串称为空串，它的长度为零。
     串中任意个连续的字符组成的子序列称为该串的子串。包含子串的串相应地称为主串。通常称字符在序列中的序号称为该字符在串中的位置。子串在主串中的位置则以子串的第一个字符在主串中的位置来表示。
串相等的充要条件：长度相等，且各个对应位置上的字符都相等。
     空格串是指由一个或多个空格字符组成的串，其长度等于它包含的空格个数；空串是零个字符的串，其长度为零。


S1和S2为串，给出使S1||S2=S2||S1成立的所有可能条件如下：(||为连接符号)
1、S1和S2都为空串；
2、S1或S2其中之一为空串；
3、S1和S2为相同的串；
4、若两串长度不等，则长串由整数个短串组成。


串有三种机内表示方法
1、定长顺序存储表示；
2、堆分配存储表示；
3、块链存储表示。


随便提醒一下笔试者：C规定以字符'\0'作为字符串结束标志(考点哦)。


二、重要的串操作
     以下函数中串采用定长顺序存储结构（类似于线性表的顺序存储结构）,用一组地址连续的存储单元存储串值的字符序列.
#define MAXSTRLEN 255
typedef unsigned char SString[MAXSTRLEN+1]  //0号单元存放串长

     串的实际长度可在这予定义长度的范围内随意,超过予定义长度的串值则被舍去
     串长用下标为0的数组元素存储。

定位函数



串的置换操作


     
模式匹配的改进算法（KMP）

三、有关串的函数（C实现）

字符串逆序存储的递归算法
void InvertStore(char A[])
//字符串逆序存储的递归算法。
{ char ch;
static int i = 0;//需要使用静态变量
scanf ("%c",&ch);
if (ch!= '.')    //规定'.'是字符串输入结束标志
   {InvertStore(A);
    A[i++] = ch;//字符串逆序存储
   }
A[i] = '';  //字符串结尾标记
}//结束算法InvertStore。


long atoi(char X[])
//一数字字符串存于字符数组X中，本算法将其转换成数
{long num=0;
long htemp=1;
int j,i=1; //i 为数组下标
while (X[i]!= '') num=10*num+(X[i++]-'0');//当字符串未到尾，进行数的转换
if(X[0]=='-') return (-num);     //返回负数
else
{ for (j=1;j    htemp*=10;
 return ((X[0]-'0')*htemp+num); //返回正数，第一位若不是负号，则是数字
}
}//算法atoi结束



实现字符串拷贝的函数 strcpy为：

void strcpy(char *s , char *t) /*copy t to s*/

{ while  (*s++=*t++);

}


求两字符串中最大公共子串
// index存放子串在串s中的位置，length存放子串的长度
void  maxcomstr(orderstring *s,*t; int index, length)
{int i,j,k,length1,con;
 index=0;length=0;i=0;
 while (i {j=0;
 while(j   { if (s[i]= =t[j])
    { k=1;length1=1;con=1;
         while(con)
            if (i+k<=s.len && j+k<=t.len && s[i+k]==t[j+k] ) { length1=length1+1;k=k+1; }  else con=0;
         if (length1>length) { index=i;  length=length1; }
         j+=k;
    }
    else j++;
  }
 i++;
}
}