[不指定 2005/12/05 03:15 | by turbozv ]
     感谢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的数组元素存储。

定位函数
int Index(SString S, SString T, int pos)
{
   //返回子串T在主串S中第pos个字符之后的位置。若不存在,则函数值为0。
   //其中,T非空,1<=pos<=Strlength(S).
   int i, j;
   i = pos;
   j = 1;
   while (i <= S[0] && j <= T[0]) {
       if (S[i] == T[j]) {
           ++i;
           ++j;
       } else {
           i = i - j + 2;
           j = 1;
       }
   }
   if (j > T[0])
       return i - T[0];
   else
       return 0;
}



串的置换操作
int Replace(SString & s1, SString s2, int i, int j)
{
   //将s1中从位置i开始,长度为j的子串替换为s2
   //替换成功则返回新的长度,否则返回-1
   //其中,1<=i<=Strlength(s1).0<=j<=Strlength(s1).
   int k;
   if (i + j - 1 > s1[0])
       return -1;
   if (j > s2[0])              //被替换的串长度大于子串长度
       for (k = i + j; k <= s1[0]; k++)
           s1[k + s2[0] - j] = s1[k];
   else if (j < s2[0])         //被替换的串长度小于子串长度
       for (k = s1[0]; k >= i + j; k--)
           s1[k + s2[0] - j] = s1[k];
   for (k = 1; k <= s2[0]; k++)
       s1[i + k - 1] = s2[k];
   s1[0] = s1[0] - j + s2[0];
   return s1[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++;
}
}
学习 | 评论(1) | 引用(0) | 阅读(13950)
过天
2006/07/06 18:27
上面那个求两个字符串中最大公共子串的题好象错了吧,我用Turbo c2.0运行有错,可能用其他的可以吧
分页: 1/1 第一页 1 最后页