数据结构5

串的抽象数据类型定义

ADT String{

数据对象：D={a1|ai属于CharacterSet,i=1,2,.....n,n>=0}

数据关系：R1={<ai-1,ai>|ai-1,ai属于D,i=2........n}

}

 

串的基本操作

StrAssign(&T,chars)

初始条件：chars是字符串常量

操作结果：把chars赋为T的值

 

StrCopy(&T,s)

初始条件：串S存在

操作结果：由串S复制得串T

 

StrLength(S)

初始条件：串S存在。

操作结果：返回S的元素个数，称为串的长度

 

StrEmpty(S)

初始条件：串S存在。

操作结果：若S为空串，则返回TRUE,否则返回FALSE

 

StrCompare(S,T)

初始条件：串S和T存在。

操作结果：若S>T,则返回值>0

若S=T,咋返回值=0

若S<T,则返回值<0

 

Concat(&T,S1,S2)

初始条件：串S1和S2存在。

操作结果；用T返回由S1和S2连接而成的新串。

 

SubString(&Sub,S,pos,len)

初始条件：串S存在，1<=pos<=StrLength(S)且0<=len<=StrLength(S)-pos+1

操作结果：用Ssub返回串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的子串。

 

 

串的逻辑结构和线性表极为相似，区别仅在于串的数据对象约束为字符集，然而，串的基本操作和线性表有很大差别，在线性表的基本操作中，大多以

“单个元素”作为操作对象，如：线性表中查找某个元素，求某个元素，在某个位置上插入一个元素和删除一个元素灯。而在串的基本操作中，通常以

”串的整体“作为操作对象，如：在串中查找某个子串，求取一个子串，在串的某个为孩子插入一个子串以及删除一个子串等。

 

串的表示和实现

如果在程序设计语言中，串只是作为输入或输出常量出现，则只需存储此串的串值，即字符序列即可，但在大多数非数值处理的程序中，串也以变量的形

 

式出现。

 

串的三种存储表示

1、串的定长顺序存储表示

2、串的堆分配存储表示

3、串的块链存储表示

 

一、串的定长顺序存储表示

#define MAXSTRLEN 255

typedf unsigned char String

串的实际长度可在这个给予定义长度的范围内随意设定，超过了给予定长长度的串值则被舍去，称为”截断“

 

二、串的堆分配存储表示

typedef struct{

         char *ch;

         //若是非空串，则按串长度分配存储区，否则ch为NULL

         int length;//串长度

}

 

通常，C语言中提供的串类型就是以这种存储方式实现的，系统利用函数malloc()和free()进行串值空间的动态管理，为每一个新产生的串分配一个存储区

 

，称串值共享的存储空间为“堆”，C语言中的串以一个空字符为结束符，串长是一个隐含值。

 

这类串操作的实现算法为：

先为新生成的串分配一个存储空间，然后进行串值的复制。

 

三、串的块链存储表示

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

typedef struct Chunk{ //结点结构

         char ch[CHUNKSIZE];

         struct Chunk *netx;

}

typedef struct{//串的链表结构

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

int curlen; //串的当前长度

}

 

串值也可用链表来存储，由于串的数据元素是一个字符，它只有8位二进制数，因此用链表存储时，通常一个结点中存放的不是一个字符，而是一个子串，

 

例如：在编辑系统中，整个文本编辑区可用看成一个串，每一行是一个子串，构成一个结点，即：同一行的串用定长结构（80个字符），行和行之间用指

 

针相链接。

 

串的模式匹配算法

这是串的一种重要操作，很多软件，若有“编辑”菜单项的话，则其中必有“查找”子菜单项。

首先，回忆一下串匹配（查找）的定义：

INDEX(s,t,pos)

初始条件：串S和T存在，T是非空串,1<=pos<=StrLength(S)

操作结果：若主串S中存在和串T值相同的子串，则返回它在主串S中第pos个字符之后第一次出现的位置；否则函数值为0

 

下面讨论以定长顺序结构表示串时的几种算法

一、简单算法

二、首位匹配算法

三、KMP算法

简单算法：

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;

}

 

 

二、首位匹配算法

先比较模式串的第一个字符，

再比较模式串的最后一个字符，

最后比较模式串中从第二个到第n-1个字符。

 

int Index_FL(SString S,SString T,int pos){

         sLength=S[0],tLength=T[0];

         i = pos;

         patStartChar=T[1];

         patEndChar=T[tLength];

         while(i<=sLength=tLength+1){

                   if(S[i]!=patStartChar) i++;

                   else if(S[i+tLength-1]!=patEndChar)++i;

                   else{

                            k=1;j=2;

                            while(j<tLength&&S[i+k]=T[j]){

                                     ++k;++j;

                            }

                            if(j==tLength)   return i;

                            else ++i;

                   }

         }

}