[转]串

(C版之java线程例子)

串，即字符串。计算机上的非数值处理的对象基本上是字符串数据。但是，由于现在我们使用的计算机硬件结构主要是反映数值计算的需要的，在处理字符串数据时比处理整数和浮点数要复杂的多。而且，对于不同类型程序，所处理的字符串具有不同的特点，要有效地实现字符串的处理，就必须根据具体情况使用合适的存储结构。串的存储表示主要有：1.定长顺序存储表示； 2. 堆分配存储表示； 3.块链存储表示。

以下介绍比较简单的定长顺序存储表示。

串定长顺序存储表示，说白了，就是用以个固定长度字符数组来存放。

1.定义“头部”

#define MAXSTRLEN 255 //所能定义的最大串长
typedef unsigned char SString[MAXSTRLEN + 1]; //数组中下标0的位置，用来存放，当前串的长度

2.初始化

Status InitStr(SString &T)
{
T[0] = 0;//初始化唯一要做的事。定义串当前长度为0。
return OK;
}

3.把一个字符数组赋给SString。。

Status StrAssign(SString &T, char *chars)
{
int len = strlen(chars);
if (len > MAXSTRLEN)
return ERROR;
T[0] = len;
for (int i = 0; i < len; i++)
{
T[i + 1] = chars[i];
}
return OK;
}

也许看到在这，你会问，SString本身是一个字符数组，为什么又要用一个字符数组去赋给SString？

其实不然，SString相对与字符数组，已经有所不同了，它以数组中下标0的位置存放串当前的实际长度。PASCAL语言中就是使用这个串类型的表示方法。

而对于char *chars = "12345"，要像把它赋给另一个字符数组如char chars1[n]，那么这里的n值必须大于等于6。因为C语言在字符串末位加了''作为结束标志符。但是有的编译器如gcc不检测这错误。

4.串的比较

Status StrCompare(SString S, SString T)
{
for (int i = 1; i <= S[0] && i <= T[0]; i++)
{
if (S[i] != T[i])
{
return S[i] - T[i]; //返回第一组不同的字符间的差
}
}
return T[0] - S[0];//若其中一个字符串刚好是另一个的子串，返回两字符串之间的长度差。
}

5.从S下标为pos开始，取长度len的子串Sub。

Status SubString(SString S, SString &Sub, int pos, int len)
{
if (pos < 1 || pos > S[0] || len < 1 || len > S[0] - pos + 1)
return ERROR;
Sub[0] = len;
for (int i = 1; i <= len; i++)
{
Sub[i] = S[pos + i - 1];
}
return OK;
}

6.串的合并：S1，S2合并为S

Status Contact(SString &S, SString S1, SString S2)
{
int i = 0;
int j = 0;
if (S1[0] + S2[0] <= MAXSTRLEN) //第一种情况，两串长度的和小于所定义的串的最大存储长度
{
S[0] = S1[0] + S2[0];
for (i = 1; i <= S1[0]; ++i)
S[i] = S1[i];
for (j = 1; j <= S2[0]; ++i, ++j)
S[i] = S2[j];
return OK;
} else if (S1[0] < MAXSTRLEN) //第二种情况，S1能完全存入S，S2可能被截断或者一个都不存入
{
S[0] = MAXSTRLEN;
for (i = 1; i <= S1[0]; i++)
{
S[i] = S1[i];
}
for (j = 1; i <= MAXSTRLEN; ++i, ++j)
S[i] = S2[j];
return OK;
} else) //第三种情况，连S1也被截断
{
S[0] = MAXSTRLEN;
for (i = 1; i <= MAXSTRLEN; i++)
{
S[i] = S1[i];
}
return OK;
}
}

7.模式匹配的一种改进算法：KMP算法

void get_next(SString T, int next[])
{
int i = 1;
next[1] = 0;
int j = 0;
while (i < T[0])
{
if (j == 0 || T[i] == T[j])
{
++i; //执行先++j，再执行next[i] = j。
++j; //因为是在串中第j+1字符前有长度为j的最长子串，与从首字符起长度为j的子串相等。 next[i] = j; //注意其上的前提是已经T[i] == T[j]。
} else
j = next[j];
}
}

//S为主串，T为要查找的模式串
Status Index_KMP(SString S, SString T, int pos)
{
int *next = new int();
get_next(T, next);
int i = pos, j = 1; //i为T开始匹配的位置 ,
while (i <= S[i] && j <= T[0])
{
if (j == 0 || S[i] == T[j])
{
++i;
++j;
} else
j = next[j]; //j != 0 且 S[i] != T[j]，S[i]与T[next[j]]比较
}
if (j > T[0])
return i - T[0]; //匹配成功
else
return 0;
}
=================================================
(C版)

/*
 2  * 七、数据结构基础之顺序串        
 3  * 顺序串与顺序表类似，用一组地址连续的存储单元来存储串中的字符序列
 4  * --- 2012年4月29日 ---by lee
 5  */ 
 6 
 7 #ifndef _SEQUENTIAL_STRING_H
 8 #define _SEQUENTIAL_STRING_H
 9 
10 #include "Utility.h"
11 
12 //宏定义顺序串的空间大小，最多存放20个字符
13 #define STRINGSIZE 21
14 
15 
16 //声明顺序表类型结构体
17 typedef struct _SqString
18 {
19     char str[STRINGSIZE];//存放数据元素的数组
20     int length;//记录串的实际长度
21 } SqString;
22 
23 /* 串匹配算法
24  * 目标串："t0 t1 t2 ... tn-1" (length=n)
25  * 模式串："p0 p1 p2 ... pm-1" (m>=1 && m<=n)
26  * 找出模式串P在目标串T中首次出现的有效位移i
27  */
28 
29 // 朴素的串匹配算法：
30 // 用一个循环来依次检查i(i>=0 && i<=n-m)是否为有效位移
31 // 匹配成功则返回目标串中的有效位移i，否则返回-1
32 int NaiveMatch(SqString *T, SqString *P)
33 {
34     int n=T->length;//目标串长度
35     int m=P->length;//模式串长度
36     int j,k;
37     //外层循环i控制位移
38     for(int i=0; i<=n-m; i++)
39     {
40         j=0;//j作为模式串P的计数器
41         k=i;//k作为目标串中匹配P的字符串的计数器
42         while((j<m) && (T->str[k]==P->str[j]))
43         {
44             k++;
45             j++;
46         }
47         //j移动到最后，则说明完全匹配
48         if(j==m)
49         {
50             return i;//返回有效位移i
51         }
52     }
53     return -1;
54 }
55 
56 
57 
58 
59 #endif

====================================================
(C版之堆分配实现串的基本操作)
用堆分配存储表示实现Hstring串类型的最小操作子集的基础上，实现串抽象数据类型的其余基本操作（不使用C语言本身提供的串函数）。

代码一如下：

#include<stdio.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
typedef struct{
char *ch;
int length;
}HString;
Status StrAssign(HString *t,char *chars){

    int i,j;
    char *c;
    if(t->ch) free(t->ch);
    for(i=0,c=chars;c[i]!='';i++);
    if(!i) {t->ch=NULL;t->length=0;}
    else {
      t->ch=(char *)malloc(i *sizeof(char));
      if(!(t->ch))
        exit(OVERFLOW);
      for(j=0;j<i;j++)
t->ch[j]=chars[j];
      t->length=i;
    }
    return OK;
}
Status DestroyString(HString *s)

{free(s->ch);
s->ch=NULL;
s->length=0;
return OK;
}
void print(HString T)

{int i;
for(i=0;i<T.length;i++)
   printf("%c",T.ch[i]);
printf(" ");
}
int StrLength(HString S){

    return S.length;
}
Status ClearString(HString *s){

    if(s->ch) {free(s->ch);s->ch=NULL;}
    s->length=0;
    return OK;
}
Status Concat(HString *t,HString S1,HString S2){

    int i;
    ClearString(t);
    t->ch=(char *)malloc((S1.length+S2.length) *sizeof(char));
    if(!(t->ch))
      exit(OVERFLOW);
    for(i=0;i<S1.length;i++)
    t->ch[i]=S1.ch[i];
    t->length=S1.length+S2.length;
    for(i=0;i<t->length;i++)
    t->ch[S1.length+i]=S2.ch[i];
    return OK;
}
Status SubString(HString *sub,HString S,int pos,int len){

   int i;
   if(pos<1||pos>S.length||len<0||len>S.length-pos+1)
     return ERROR;
   if(sub->ch) free (sub->ch);
   if(!len) {sub->ch=NULL;sub->length=0;}
   else{
     sub->ch=(char *)malloc(len *sizeof(char));
     for(i=0;i<len;i++)
       sub->ch[i]=S.ch[pos-1+i];
     sub->length=len;
   }
   return OK;
}
int StrCompare(HString S,HString T){

    int i;
    for(i=0;i<S.length&&i<T.length;++i)
      if(S.ch[i]!=T.ch[i])
        return S.ch[i]-T.ch[i];
    return S.length-T.length;
}

int Index(HString S,HString T,int pos)

{int i,m,n;
HString Sub,*sub=&Sub;
Sub.ch=NULL;
if(pos>0){
   n=StrLength(S);m=StrLength(T);i=pos;
   while(i<=n-m+1){
     SubString(sub,S,i,m);
     if(StrCompare(Sub,T)!=0) ++i;
     else return i;
   }
}
return 0;
}
Status StrInsert(HString *s,int pos,HString T)

{int i;
if(pos<1||pos>s->length+1) return ERROR;
if(T.length){
   s->ch=(char *)realloc(s->ch,(s->length+T.length) *sizeof(char));
   if(!s->ch) exit(OVERFLOW);
   for(i=s->length-1;i>=pos-1;--i)
     s->ch[i+T.length]=s->ch[i];
   for(i=0;i<=T.length-1;i++)
     s->ch[pos-1+i]=T.ch[i];
   s->length+=T.length;
}
return OK;
}
Status StrDelete(HString *s,int pos,int len)

{int i;
if(pos<1||pos>s->length) return ERROR;
for(i=pos+len-1;i<s->length;i++)
   s->ch[i-len]=s->ch[i];
s->length-=len;
return OK;
}
Status Replace(HString *s,HString T,HString V)

{int i,n,d;
n=StrLength(T);
do{d=Index(*s,T,1);
    StrDelete(s,d,n);
    StrInsert(s,d,V);
    }while(Index(*s,T,1));
return OK;
}

main()
{int i;
HString S,S1,S2,S3,T,U,V,W,*s;
clrscr();
S.ch=NULL;S1.ch=NULL;S2.ch=NULL;S3.ch=NULL;
T.ch=NULL;U.ch=NULL;V.ch=NULL;W.ch=NULL;
s=&S1;StrAssign(s,"THIS IS A BOOK");
s=&S2;StrAssign(s,"ESE ARE");
s=&U;StrAssign(s,"XYXYXYXYXYXY");
s=&S;StrAssign(s,"S");
s=&W;StrAssign(s,"W");
s=&S3;SubString(s,S1,3,7);
s=&V;SubString(s,U,6,3);
s=&T;Concat(s,S1,S);
Replace(s,S3,S2);
s=&U;Replace(s,V,W);
printf("S1=");print(S1);;
printf("T=");print(T);
printf("U=");print(U);
DestroyString(&S);
DestroyString(&S1);
DestroyString(&S2);
DestroyString(&S3);
DestroyString(&T);
DestroyString(&U);
DestroyString(&V);
DestroyString(&W);
getch();
}

代码段二用选择顺序实现用户的需要

#include<stdio.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
typedef struct{
char *ch;
int length;
}HString;
void menu()
{ clrscr();
  printf("* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * ");
  printf(" ***** StrAssign-1  Destroy-2  Print-3   Concat-4  Substring-5   Replace-6 Quit-7 ***** ");
  printf(" ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ");
  gotoxy(15,10);printf("Operation: ");
  gotoxy(1,20);
  printf(" *** *** *** *** *** *** *** *** *** *** *** *** *** *** *** *** *** *** *** ");
  printf(" * Enter a operation code:1,2,3,4,5,6,7                         * ");
  printf(" **** **** **** **** **** **** **** **** **** **** **** **** **** **** **** ");
  gotoxy(26,10);
}
Status StrAssign(HString *t,char *chars){

    int i,j;
    char *c;
    if((*t).ch) free((*t).ch);
    for(i=0,c=chars;c[i]!='';i++);
    if(!i) {(*t).ch=NULL;(*t).length=0;}
    else {
      (*t).ch=(char *)malloc(i*sizeof(char));
      if(!((*t).ch))
        exit(OVERFLOW);
      for(j=0;j<i;j++)
(*t).ch[j]=chars[j];
      (*t).length=i;
    }
    return OK;
}
Status DestroyString(HString *p)

{if(p->ch==NULL)return ERROR;
free(p->ch);
p->ch=NULL;
p->length=0;
return OK;
}
int StrLength(HString S)
{
    return S.length;
}
void Print(HString T)
{int i;
if(T.length==0)printf("null string! ");
for(i=0;i<=T.length-1;i++)
   printf("%c",T.ch[i]);
printf(" ");
}

Status ClearString(HString *p){
    if(p->ch) {free(p->ch);p->ch=NULL;}
    p->length=0;
    return OK;
}
Status ConCat(HString *t,HString S1,HString S2){

    int i;
    ClearString(t);
    (*t).ch=(char *)malloc((S1.length+S2.length) *sizeof(char));
    if(!((*t).ch))
      exit(OVERFLOW);
    for(i=0;i<S1.length;i++)
    (*t).ch[i]=S1.ch[i];
    (*t).length=S1.length+S2.length;
    for(i=0;i<(*t).length;i++)
    (*t).ch[S1.length+i]=S2.ch[i];
    return OK;
}
Status SubString(HString *sub,HString S,int pos,int len){

   int i;
   if(pos<1||pos>S.length||len<0||len>S.length-pos+1)
     return ERROR;
   if((*sub).ch) free ((*sub).ch);
   if(!len) {(*sub).ch=NULL;(*sub).length=0;}
   else{
     (*sub).ch=(char *)malloc(len *sizeof(char));
     for(i=0;i<len;i++)
       (*sub).ch[i]=S.ch[pos-1+i];
     (*sub).length=len;
   }
   return OK;
}
int StrCompare(HString S,HString T)
{
    int i;
    for(i=0;i<S.length&&i<T.length;++i)
      if(S.ch[i]!=T.ch[i])
        return S.ch[i]-T.ch[i];
    return S.length-T.length;
}

int Index(HString S,HString T,int pos)
{int i,m,n;
HString Sub,*sub=&Sub;
Sub.ch=NULL;
if(pos>0){
   n=StrLength(S);m=StrLength(T);i=pos;
   while(i<=n-m+1){
     SubString(sub,S,i,m);
     if(StrCompare(Sub,T)!=0) ++i;
     else return i;
   }
}
return 0;
}
Status StrInsert(HString *p,int pos,HString T)
{int i;
if(pos<1||pos>p->length+1) return ERROR;
if(T.length){
   p->ch=(char *)realloc(p->ch,(p->length+T.length) *sizeof(char));
   if(!p->ch) exit(OVERFLOW);
   for(i=p->length-1;i>=pos-1;--i)
     p->ch[i+T.length]=p->ch[i];
   for(i=0;i<=T.length-1;i++)
     p->ch[pos-1+i]=T.ch[i];
   p->length+=T.length;
}
return OK;
}
Status StrDelete(HString *p,int pos,int len)
{int i;
if(pos<1||pos>p->length) return ERROR;
for(i=pos+len-1;i<p->length;i++)
   p->ch[i-len]=p->ch[i];
p->length-=len;
return OK;
}
Status Replace(HString *p,HString T,HString V)

{int i,n,d;
n=StrLength(T);
do{d=Index(*p,T,1);
    StrDelete(p,d,n);
    StrInsert(p,d,V);
    }while(Index(*p,T,1));
return OK;
}

main()
{int i,ch; int pos,len;
HString T,M1,M2,M3,M4,*p;
T.ch=NULL;M1.ch=NULL;M2.ch=NULL;M3.ch=NULL;M4.ch=NULL;p=NULL;
ch=1;
clrscr();
while(ch)
{ menu();
   scanf("%d",&ch);
   switch(ch)
   {
    case 1:clrscr();
    printf("input the mather string(press 'Enter' to shou the end) : ");
    scanf("%s",p);
    if(StrAssign(&M1,p)) printf("Assign string mather success! ");
    else printf("Assign string mather fail! ");
    printf("input the chile string(press 'Enter' to shou the end) : ");
    scanf("%s",p);
    if(StrAssign(&M2,p)) printf("Assign string child success! ");
    else printf("Assign string child fail! ");
    printf("press any key to continue ! ");
    getch();
           break;
    case 2:clrscr();
    p=&M1;
    if(DestroyString(p))printf("destroy mather string success! ");
           else printf("null pointer,can't destroy! ");
    p=&M2;
    if(DestroyString(p))printf("destroy child string success! ");
    else printf("null pointer,can't destroy! ");
    p=&M3;
    if(DestroyString(p))printf("destroy small string success! ");
    else printf("null pointer,can't destroy! ");
    p=&M4;
    if(DestroyString(p))printf("destroy replaced string success! ");
           else printf("null pointer,can't destroy! ");
    printf("press any key to continue ! ");
           getch();
           break;
    case 3:clrscr();
    p=&M1;
    printf("mather string is : ");
    Print(*p);
    p=&M2;
    printf("child string is: ");
    Print(*p);
    p=NULL;
    printf("press any key to continue ! ");
    getch();
           break;
    case 4:clrscr();
    ConCat(&T,M1,M2);
    printf("the concat string is : ");
    Print(T);
    M1=T;

    printf("press any key to continue: ");
    getch();
    break;
    case 5:clrscr();
    printf("input the pos and the len: ");
    scanf("%d%d",&pos,&len);
    SubString(p,M1,pos,len);
    printf("the sub string is: ");
    Print(*p);
    T.ch=NULL;
    printf("press any key to continue: ");
    getch();
    break;
    case 6:clrscr();
    printf("input the string need to replace: ");
           scanf("%s",&M3);
    printf("input the new string you want to change to: ");
    scanf("%s",&M4);

    Replace(&M1,M3,M4);
    printf("the replaced string is : ");
    Print(M1);
    DestroyString(&T);
    printf("press any key to continue: ");
    getch();
    break;
   case 7:exit(0);

  }
}

}
===============================
(C之堆分配之二)

/***********************************************/
/* 该算法虽然是使用动态内存分配的方法实现
但因其存储单元的地址是连续的
所以本质上还是属于顺序存储
*/
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
/***********************************************/
#define MaxSize 256
typedef struct {
char *ch;
int length;
}HString, *pHString;
/***********************************************/
//函数声明
void InitString(pHString ch); //创建用户所输入的串
void DispString(pHString ch); //输出字符串
int GetLenString(pHString ch); //获得字符串的长度
int EmptyString(pHString ch); //字符串判空
int StrCompare(pHString T, pHString S); //字符串的比较
int ClearStr(pHString S); //将S清空，并释放S所占的内存
int Concat(pHString T, pHString S1, pHString S2); //字符串连接
int SubString(pHString Sub, pHString S, int pos, int len); //在Sub中返回S中第pos位开始的len个字符组成的子串
int Index(pHString T, pHString S, int pos); //串的模式匹配（简单算法的实现）
/***********************************************/
int main(void)
{
HString T;
InitString(&T);
HString S;
InitString(&S);
int k = Index(&T, &S, 2);
printf(" %d", k);
return 0;
}
/***********************************************/
//创建用户所输入的串
void InitString(pHString ch)
{
char str[MaxSize];
gets(str);
int i;
for (i=0; str[i]!=''; ++i) ;
ch->ch = (char *)malloc(sizeof(char) * i);
if (NULL == ch->ch)
{
printf("内存分配失败!程序终止....");
exit(-1);
}
int j;
for (j=0; j<i; ++j)
ch->ch[j] = str[j];
ch->length = j;
}
/***********************************************/
//输出字符串
void DispString(pHString ch)
{
int i;
for (i=0; i<ch->length; ++i)
putchar(ch->ch[i]);
putchar(' ');
}
/***********************************************/
//获得字符串的长度
//前提是ch串存在并且已被初始化
int GetLenString(pHString ch)
{
return ch->length;
}
/***********************************************/
//字符串判空
//前提是ch串存在并且已被初始化
int EmptyString(pHString ch)
{
if (0 == ch->length)
return 1;
else
return 0;
}
/***********************************************/
//若S大于T 返回值>0 若S等于T 返回值=0 若S小于T 返回值<0
int StrCompare(pHString T, pHString S)
{
int i;
for (i=0; i<S->length && i<T->length; ++i)
{
if (S->ch[i] != T->ch[i])
return S->ch[i] - T->ch[i];
}
return S->length - T->length;
}
/***********************************************/
//将S清空，并释放S所占的内存
int ClearStr(pHString S)
{
S->length = 0;
free(S->ch);
S->ch = NULL;
return 1;
}
/***********************************************/
//字符串连接
int Concat(pHString T, pHString S1, pHString S2)
{
int Tlen = S1->length + S2->length;
T->ch = (char *)malloc(sizeof(char)*Tlen);
if (NULL == T->ch)
{
printf("内存分配失败!程序终止....");
exit(-1);
}
int i;
for (i=0; i<S1->length; ++i)
T->ch[i] = S1->ch[i];
int j;
for (j=0; j+i<Tlen; ++j)
T->ch[i+j] = S2->ch[j];
T->length = Tlen;
return 1;
}
/***********************************************/
//在Sub中返回S中第pos位开始的len个字符组成的子串
int SubString(pHString Sub, pHString S, int pos, int len)
{
if (pos<=0 || pos >S->length || len<0 || len>S->length-pos+1)
return 0;
Sub->ch = (char *)malloc(sizeof(char) * len);
int i;
for (i=0; i<len; ++i)
Sub->ch[i] = S->ch[pos+i-1];
Sub->length = len;
return 1;
}
/***********************************************/
//串的模式匹配简单算法的实现
int Index(pHString T, pHString S, int pos)
{
if (pos<1 || pos >T->length)
return 0;
int Tlen = T->length;
int Slen = S->length;
int i = pos-1, j = 0;
while (i<Tlen && j<Slen)
{
if (T->ch[i] == S->ch[j])
{
++i;
++j;
}
else
{
i = i-j+1;
j = 0;
}
}
if (j>=Slen)
return i-Slen;
else
return -1;
}
/***********************************************/

6. =============================================
7. (C版之串的实现)
8. #include <stdio.h>
  #include <malloc.h>
  #define OVERFLOW -1
  #define OK 1
  #define ERROR 0
  typedef int status;
  typedef struct
  {
  char *ch;//按串长分配存储空间
  int length;//存放串长
  }sstring;
  status initstring(sstring &s)
  {//初始化串，堆存储方式
  s.ch=(char*)malloc(sizeof(char));
  if(!s.ch) return ERROR;//分配存储空间失败
  s.ch=NULL;
  s.length=0;//串长为0
  return OK;
  }
  status strassign(sstring &s,char *chars)
  {//串赋值
  int i=0,j;
  if(s.ch) free(s.ch);
  while(chars[i]!='')
  {
    i++;
  }//求串的长度
  s.ch=(char*)malloc(i*sizeof(char));
  if(!s.ch) return ERROR;
  for(j=0;j<i;j++)
  {
    s.ch[j]=chars[j];
  }
  s.length=i;
  return OK;
  }
  status getlength(sstring s,int &len)
  {//求串长
  len=s.length;
  return len;
  }
  status insert (sstring &s1,sstring s2,int pos)
  {//在字符串s1的第pos个字符之前插入字符串s2，并显示
  int j,k;
  if(pos<1||pos>s1.length+1)
  {//pos不合法
    printf("the pos is a wrong value ");
    return ERROR;
  }
  s1.ch=(char*)realloc(s1.ch,(s1.length+s2.length)*sizeof(char));
  if(!s1.ch)
    return ERROR;//空间分配失败
  for(j=s1.length-1,k=s1.length+s2.length-1;j>=pos-1;j--)
  {//字符串后移
    s1.ch[k]=s1.ch[j];
    k--;
  }
  for(j=s2.length-1;j>=0;j--)
  {
    s1.ch[k]=s2.ch[j];
    k--;
  }
  s1.length+=s2.length;
  printf("the new string s1 is %s ",s1.ch);
  return OK;
  }
  status delstr(sstring &s,int pos,int j)
  {//在串s中删除从第pos个字符起长度为j的字串（此处不显示删除的字串）
  int i,k=pos,m=pos-1;
  if(pos<1||pos+j-1>s.length)
  {
    printf("参数不合法 ");
    return ERROR;
  }
  for(i=k+j-1;i<=s.length-1;i++)
  {
    s.ch[m]=s.ch[i];
    m++;
  }
  s.ch[m]='';
  printf("the new string s is %s ",s.ch);
  return OK;
  }
  int strcompare(sstring s,sstring s1)
  {//比较串s和s1的大小，如果s>s1，则返回正数；如果s=s1，则返回0；如果s<s1，则返回复数
  int i;
  for(i=0;i<s.length&&i<s1.length;i++)
  {
    if(s.ch[i]!=s1.ch[i])
     return s.ch[i]-s1.ch[i];
  }
  return s.length-s1.length;
  }
  status concat(sstring &t,sstring s,sstring s1)
  {//由串t返回串s和s1联接而成的新串,并显示
  int i,j;
  t.ch=(char*)malloc((s.length+s1.length)*sizeof(char));
  if(!t.ch) return ERROR;
  for(i=0;i<s.length;i++)
  {
    t.ch[i]=s.ch[i];
  }
  for(i=s.length,j=0;j<s1.length;j++,i++)
  {
    t.ch[i]=s1.ch[j];
  }
  t.ch[i]='';
  t.length=s.length+s1.length;
  printf("the string t is %s ",t.ch);
  return OK;
  }
  status substr(sstring &sub,sstring s,int pos,int l)
  {//求出串s第pos个字符起长为l的字串，并用sub返回
  int i,j=0;
  if(pos<1||pos>s.length||l<1||pos+l-1>s.length)
  {
    printf("参数不合法 ");
    return ERROR;
  }
  sub.ch=(char*)malloc(l*sizeof(char));
  if(!sub.ch) return ERROR;
  for(i=pos;i<=pos+l-1;i++,j++)
    sub.ch[j]=s.ch[i-1];
  sub.length=l;
  printf("the string sub is %s ",sub.ch);
  return OK;
  }
  void getnext(sstring t,int next[])
  {//求串t的next函数，并存入数组next
  int i=0,j=-1;
  next[0]=-1;
  while(i<t.length)
  {
    if(j==-1||t.ch[i]==t.ch[j])
    {
     ++i;++j;next[i]=j;
    }
    else j=next[j];
  }
  }
  int KMPindex(sstring s,sstring t)
  {//KMP算法，其中s为主串，t为子串
  int next[50],i=0,j=0,v;
  getnext(t,next);
  while(i<s.length&&j<t.length)
  {
    if(j==-1||s.ch[i]==t.ch[j])
    {
     i++;j++;
    }
    else j=next[j];
  }
  if(j>=t.length)
    v=i-t.length;
  else
    v=-1;
  return v;
  }
  void main()
  {
  sstring s1,s2,t,sub;
  char str[50];
  int pos,len,next[50],j,v,l;
  initstring(s1);
  printf("**************初始化完毕************** ");
  printf("*************字符串s1赋初值************* ");
  printf("please input the chars ");
  scanf("%s",str);
  strassign(s1,str); //字符串赋初值
  printf("*************输出字符串s1************* ");
  printf("the string s1 is %s ",s1.ch);//输出字符串
  printf("************字符串s1的长度为************ ");
  len=getlength(s1,len);
  printf("the length of the string s1 is %d ",len);
  printf("*************字符串s2赋初值************* ");
  initstring(s2);
  printf("please input the chars ");
  scanf("%s",str);
  strassign(s2,str);//字符串赋初值
  printf("*************输出字符串s2************* ");
  printf("the string s2 is %s ",s2.ch);//输出字符串
  printf("*************字符串的插入************** ");
  printf("在字符串s1的第pos个位置之前插入字符串s2,pos=");scanf("%d",&pos);
  printf(" ");
  insert(s1,s2,pos);
  printf("*************字符串的删除************* ");
  printf("删除字符串s2第pos个字符起长为j的字符串 ");
  printf("      pos=");scanf("%d",&pos);printf("      j=");scanf("%d",&j);
  delstr(s2,pos,j);//串删除
  printf("***************串比较****************** ");
  if(strcompare(s1,s2)>0) //串比较
    printf("s1>s2 ");
  else
    if(strcompare(s1,s2)==0)
     printf("s1=s2 ");
    else
     printf("s1<s2 ");
  printf("***************串的合并****************** ");
  printf("将串s1，s2合并于串t后 ");
  initstring(t);
  concat(t,s1,s2);
  printf("***************取子串****************** ");
  printf("取出字符串s1第pos个字符起长为l的子串 ");
  printf("     pos=");scanf("%d",&pos);
  printf("     l=");scanf("%d",&l);
  substr(sub,s1,pos,l);
  printf("***************求模式串的next****************** ");
  printf("the next of the string is ");
  getnext(s1,next);
  for(j=0;j<s1.length;j++)
  {
       printf(" %d",next[j]);
  }
  printf(" ");
  printf("***************串的模式匹配****************** ");
  v=KMPindex(s1,s2);
  if(v!=-1)
       printf("从主串的第%d个字符起，匹配成功! ",v+1);
  else
    printf("匹配失败!主串中没有与模式串匹配的子串 ");
  
  }