【数据结构】串详解（含统考真题）

存储结构定长顺序存储

#define MANLAN 255
typedef struct{
	char ch[MANLAN];	//存放字符
	int length;			//串长度
}SString;

堆分配存储

typedef struct{
	char *ch;	//指向基地址
	int length;	//串长度
}HString;	//按串长分配存储区
HString S;
S.ch=(char *)malloc(MANLAN*sizeof(char));
S.length=0;

块链式存储

typedef struct StringNode{
	char ch[4];	//一个结点(块)存放多个字符
	struct StringNode * next;
}StringNode * SString;

定长顺序存储定义方便、操作简单；堆分配存储长度可变，不会浪费空间；块链式存储每个结点(快)可以存储多个字符，可以提高存储密度。

操作集

void StrAssian(SString &T,char chars[]);//赋值
int StrCompare(SString S,SString T);//比较
int StrLength(SString S);//求串长
void Concat(SString &T,SString S1,SString S2);//串联接
void SubString(SString &Sub,SString S,int pos,int len);//求子串
bool StrEmpty(SString S);//判空
int Index(SString S,SString T);//定位

以下用常用的定长顺序存储实现

赋值

//赋值操作。把串T赋值为chars
void StrAssian(SString &T,char chars[]){
	T.length=0;
	while(chars[T.length]!='')
		T.ch[++T.length]=chars[T.length-1];
}

比较

//比较操作。若S>T，则返回值>0;若S=T，则返回值=0;若S T.ch[i]) return 1;
		else return -1;
	}
	if(S.length>T.length) return 1;
	else if(S.length 
求串长 
//求串长。返回串S的元素个数。
int StrLength(SString S){
	return S.length;
}
 
串联接 
//串联接。用T返回由S1和S2联接而成的新串。
void Concat(SString &T,SString S1,SString S2){
	T.length=S1.length+S2.length;
	int i=1;
	for(;i<=S1.length;i++) T.ch[i]=S1.ch[i];
	for(;i<= T.length;i++) T.ch[i]=S2.ch[i-S1.length];
}
 
求子串 
//求子串。用Sub返回串s的第pos个字符起长度为len的子串。
void SubString(SString &Sub,SString S,int pos,int len){
	if(pos+len>S.length) {
		Sub.length=0;
		return ;
	}
	Sub.length=len;
	for(int i=1;i<=len;i++) Sub.ch[i]=S.ch[i+pos-1];
}
 
判空 
//判空操作。若s为空串，则返回 TRUE，否则返回FALSE。
bool StrEmpty(SString S){
	return StrLength(S)==0;
}
 
定位 
//定位操作。若主串s中存在与串T值相同的子串，则返回它在主串s中第一次出现的位置;否则函数值为0。
int Index(SString S,SString T){
	int i=1,n=S.length,m=T.length;
	SString Sub;
	while(i<=n-m-1){
		SubString(Sub,S,i,m);
		if(StrCompare(Sub,T)!=0) i++;
		else return i;
	}
	return 0;
}
 
完整代码 
#include
using namespace std;

#define MANLAN 255
typedef struct{
	char ch[MANLAN];
	int length;
}SString;

void StrAssian(SString &T,char chars[]);//赋值
int StrCompare(SString S,SString T);//比较
int StrLength(SString S);//求串长
void Concat(SString &T,SString S1,SString S2);//串联接
void SubString(SString &Sub,SString S,int pos,int len);//求子串
bool StrEmpty(SString S);//判空
int Index(SString S,SString T);//定位

//不同的高级语言对串的基本操作集可以有不同的定义方法。在上述定义的操作中，
//串赋值StrAssian.电比较StrCompare、求串长StrLength、串联接Concat及求子串SubString
//五种操作构成串类型的最小操作子集，即这些操作不可能利用其他串操作来实现:
//反之，其他串操作（除串清除ClearString和串销毁 DestroyString外）均可在该最小操作子集上实现。

int main(){
	SString S,T,R;
	char chars1[]="bcbcdefaaa";
	char chars2[]="abcdefa";
	StrAssian(S,chars1);
	StrAssian(T,chars2);
	cout<<"S:";
	for(int i=1;i<=S.length;i++)cout<0) printf("S>Tn");
//	else if(StrCompare(S,T)<0) printf("ST，则返回值>0;若S=T，则返回值=0;若S T.ch[i]) return 1;
		else return -1;
	}
	if(S.length>T.length) return 1;
	else if(S.lengthS.length) {
		Sub.length=0;
		return ;
	}
	Sub.length=len;
	for(int i=1;i<=len;i++) Sub.ch[i]=S.ch[i+pos-1];
}

//判空操作。若s为空串，则返回 TRUE，否则返回FALSE。
bool StrEmpty(SString S){
	return StrLength(S)==0;
}

//定位操作。若主串s中存在与串T值相同的子串，则返回它在主串s中第一次出现的位置;否则函数值为0。
int Index(SString S,SString T){
	int i=1,n=S.length,m=T.length;
	SString Sub;
	while(i<=n-m-1){
		SubString(Sub,S,i,m);
		if(StrCompare(Sub,T)!=0) i++;
		else return i;
	}
	return 0;
}
 
模式串匹配 
模式串匹配详解 
精选习题 
单项选择题 
1、KMP算法的特点是在模式匹配时指示主串的指针(B).
 A.不会变大 B.不会变小 C.都有可能 D.无法判断 
2、设主串的长度为n,子串的长度为m，则简单的模式匹配算法时间复杂度为（C）KMP算法时间复杂度为（D）.
 A.O(m) B.O(n) C.O(mn) D.O(m+n) 
3、已知串S=‘aaab’，其next数组值为(A)
 A. 0123 B. 0112 C. 0231 D. 1211 
4、串’ ababaaababaa '的 next数组值为（C) 
A. 01234567899 B. 012121111212
 C. 011234223456 D. 0123012322345 
5、串’ ababaaababaa’的next数组为©
 A. 1,0,1,2,3,4,5,6,7,8,8,8 B. -1,0,1,0,1,0,0,0,0,1,0,1
 C. 1,0,0,1,2,3,1,1,2,3,4,5 D. -1,0,1,2,-1,0,1,2,1,1,2,3 
6、串’ababaaababaa’的nextval数组为（C).
 A. 0,1,0,1,1,2,0,1,0,1,0,2 B. 0,1,0,1,1,4,1,1,0,1,0,2
 C. 0,1,0,1,0,4,2,1,0,1,0,4 D. 0,1,1,1,0,2,1,1,0,1,0,4 
7、【2015统考真题】已知字符串S为’ abaabaabacacaabaabcc’,模式串t为’abaabc’.采用KMP算法进行匹配,第一次出现“失配”(s[i]≠t[j])时,i=j=5，则下次开始匹配时,i和j的值分别是（C).
 A. i=1,j=0 B. i=5,j=0 C . i=5,j=2 D. i=6,j=2
 8、【2019统考真题】设主串T=‘abaabaabcabaabc’，模式串S = ‘abaabc’，采用 KMP算法进行模式匹配,到匹配成功时为止,在匹配过程中进行的单个字符间的比较次数是(B).
 A. 9 B. 10 C. 12 D. 15 
综合应用题 
1.在字符串模式匹配的KMP算法中，求模式的next 数组值的定义如下:
 
     
      
       
        
         n
        
        
         e
        
        
         x
        
        
         t
        
        
         [
        
        
         j
        
        
         ]
        
        
         =
        
        
         
          {
         
         
          
           
            
             
              
               0
              
              
               ,
              
             
            
           
           
            
             
              
               j
              
              
               =
              
              
               1
              
             
            
           
          
          
           
            
             
              
               m
              
              
               a
              
              
               x
              
              
               {
              
              
               k
              
              
               ∣
              
              
               <
              
              
               1
              
              
               k
              
              
               <
              
              
               j
              
              
               
                且
               
               
                ′
               
              
              
               
                p
               
               
                1
               
              
              
               …
              
              
               
                p
               
               
                
                 k
                
                
                 −
                
                
                 1
                
               
               
                ′
               
              
              
               
                =
               
               
                ′
               
              
              
               
                p
               
               
                
                 j
                
                
                 −
                
                
                 k
                
                
                 +
                
                
                 1
                
               
              
              
               …
              
              
               
                p
               
               
                
                 j
                
                
                 −
                
                
                 1
                
               
               
                ′
               
              
              
               }
              
              
               ,
              
             
            
           
           
            
             
              
               此
              
              
               集
              
              
               合
              
              
               不
              
              
               为
              
              
               空
              
              
               时
              
             
            
           
          
          
           
            
             
              
               1
              
              
               ,
              
             
            
           
           
            
             
              
               其
              
              
               他
              
              
               情
              
              
               况
              
             
            
           
          
         
        
       
       
         next[j]=left{begin{matrix}0,&j=1 \max{k|<1k 
1)当1j=1时,为什么要取next[1J=0?
 2)为什么要取max{k},k最大是多少?
 3)其他情况是什么情况，为什么取next[j]=1? 
2.设有字符串S=‘aabaabaabaac’,P-’ aabaac’. 
1)求出P的 next数组.
 2）若S作主串，P作模式串，试给出KMP算法的匹配过程

【数据结构】串详解（含统考真题）

C/C++/C#相关栏目本月热门文章