数据结构（C语言版）-第4章串、数组和广义表

2021-10-24 21:47:33

补充：C语言中常用的串运算

调用标准库函数 #include<string.h>

串比较，strcmp(char s1,char s2)
串复制，strcpy(char to,char from)
串连接，strcat(char to,char from)
求串长，strlen(char s)

4.1 串

串(String)----零个或多个字符组成的有限序列

串的存储结构:顺序存储、链式存储

顺序存储表示

typedef struct{

   char *ch;      //若串非空,则按串长分配存储区,

                  //否则ch为NULL

   int  length;   //串长度

}HString;

链式存储表示

#define CHUNKSIZE 80       //可由用户定义的块大小

typedef struct Chunk{

   char  ch[CHUNKSIZE];

   struct Chunk *next;

}Chunk;

typedef struct{

   Chunk *head,*tail;      //串的头指针和尾指针

   int curlen;             //串的当前长度

}LString;

串的模式匹配算法:

BF算法设计思想:

Index(S,T,pos)

将主串的第pos个字符和模式的第一个字符比较，
若相等，继续逐个比较后续字符；
若不等，从主串的下一字符起，重新与模式的第一个字符比较。

直到主串的一个连续子串字符序列与模式相等。返回值为S中与T匹配的子序列第一个字符的序号，即匹配成功。
否则，匹配失败，返回值 0

int  Index(Sstring S,Sstring T,int pos){

    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;

}