串的基本知识及操作

曾经终败给现在 2023-07-12 09:21 34阅读 0赞

一、  
串和线性表很相似，操作也基本相同  
区别  
①串的元素全为字符  
② 线性表的操作基本是单个元素；串的基本操作是“串的整体”  
ps:串加单引号 data=‘data’,第一个是标识符，第二个是串  
若串仅仅作为输入输出的常量，则仅需要储存字符序列；大多数非数值计算中，串也以变量形式存在

二、串的储存  
1.顺序映象  
①定长顺序储存  
用地址连续的内存单元依次存放字符序列  
用数组

#define MAZSTRLEN 255
    typedef unsigned char Sstring[MAXSTRLEN+1];

//0单元存放串的长度（某些高级语言中）；C语言中串的长度是隐含的，用某个特定字符表示的

ps：当串的实际长度超过定义的最大长度，则超过部分被舍去，称为“截断” （所以注意连接contact时候分情况）

②堆分配储存  
存储空间中只有串的起始地址和串长；  
使用mallco（）和free()函数动态管理，为新产生的串分配存储区，称这种串值共享的存储空间为“堆”；  
C语言中常以一个空字符为结束标志，串长为隐含值

typedef struct{
    	char *ch;
    	int length;
    }HString;

2.块链储存  
由于存储密度问题，一个结点最好存储不只一个字符，比如一个结点可以存一行；用链储存操作方便，可以直接删除一行，还不移动其他行的数据

#define CHUNKSIZE 80//可由客户定义的块大小
    typedef struct Chunk{
    	char ch[CUNKSIZE];//数据域 
        struct Chunk*next;//指针域 
    }Chunk;//结点
    typedef struct{
    	Chunk *head,*tail; 
    	int curlen;
    }L_String;//串的链表结构

三、C语言中串的基本操作（其它串操作都由基本操作构成）  
1.gets(str)  
2.puts(str)  
3.stract(str1,str2)连接  
4.strcpy(str1,str2)把串2赋值给串1  
5.strcmp(str1,str2)比较  
6.strlen(str)  
7.strlwr(str)全部转换为小写字母  
8.strupr(str)全部转换为大写字母

四、串的操作  
1.StrAssign(&T,chars)  
把串的常量（字符串）赋值给串的变量T  
2.StrCopy(&T,S)  
将串S赋值给串T  
3.StrLength(S)  
求串的长度（元素个数）  
4.StrEmpty(S)  
如果S是空串，返回TRUE;否则返回FALSE  
5.StrCompare(S,T)  
一位一位比较大小（如a>b），以第一次比较出来的结果为准 S>T,返回值>0;=、<  
6.Contact(&T,S1,S2)  
把s1和s2连接成T，返回T  
7.SubString(&Sub,S,pos,len)  
用子串sub返回字符串S从位置pos开始起长度为len的字符串  
8.Index(S,T,pos)  
定位，返回串T在串S的第pos个元素后第一次出现得位置的位序  
子串的定位成为模式匹配，其中T为模式串  
·利用基本操作  
总概括：StrCompare(SubString(S,i,StrLength(T)),T)?=0

Index(String S,String T,int pos){
    	if(pos>0){
    		n=StrLength(S);,=StrLength(T);
    		i=pos;
    		while(i<=n-m+1){ //画图更好理解 
    			SubString(sub,S,i,m);
    			if(StrCompare(sub,T)!=0) ++I;
    			else return i;
    		}//while
    	}//if
    	return 0;
    }

9.Replace(&S,T,V)  
将串s中的子串T全部替换为V  
10.StrInsert(&S,pos,T)  
在串S的第pos个位置前插入串T  
11.StrDelete(&S,pos,len)  
在串S中，从第pos个元素起，删除长度为len的串

五、求子串的模式匹配（定位index）  
“编辑”菜单的“查找”子菜单  
定长顺序储存时的算法：  
1.简单算法

int Index(SString S,SString T,int pos){//从第pos个位置开始查找 
    	i=pos;j=1;
    	while(i<=S[0]&&j<T[0]){ //S[0]和T[0]中储存的是串长 
        if(S[i] = =T[j]) {++i;++j;}
        else{i=i-j+2;j=1;}//指针后退，重新匹配 
    }//while
     if(j>T[0]) return i-T[0];
     else return 0;
    }

当二进制0、1查找时，由于只有0、1两种可能，可能前面的全匹配成功，最后一个字符不一样而匹配失败，时间复杂度会很大；所以这种简单算法不适用于字符可能性少得情况  
2.首尾匹配算法  
先比较模式串（T）的第一个→最后一个→顺序第二个到第n-1个

int Index_FL(SString S,SString T,int pos){
    	SLength=S[0];TLength=T[0];
    	while(i<=SLength-TLength+1){
    		if(S[i]!=T[1]) ++i;
    		else if(S[i]!=T[TLength]) ++i;
    		else{
    			……//跟上面简单算法就差不多了 
    		}//else 
    	}//while
    }

但是如果只有倒数第二个不相同，其他都相同的话，时间复杂度还是相当高  
3. KMP算法  
解决了指针回溯的问题，时间复杂度为O(S\[0\]+T\[0\]),变成线性的，而非前面两种的是乘积，则时间复杂度大大降低

int Index_KMP(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 j=next[j];
    	}
    	if(j>T[0]) return i-T[0]; //匹配成功 
    	else return 0;
    } //Index_KMP
    void get_next(SString T,int next[]){//求next值并存入数组
     j=1;next[1]=0;k=0;
     while(j<T[0]){
     	if(k= =0||T[j]]= =T[k]){++j;++k;next[j]=k;}
     	else k=next[k];
     }  
    }//get_next

4.KMP算法改进  
如果Si！=Tj,则比较Si和Tk(k=next\[j\]),但是如果Tj= =Tk,则不必比较了就

void get_nextval(SString T,int nextval[]){//求模式串T的next函数修正值并存入数组nextval 
    	j=1;next[1]=0;k=0;
    	while(j<T[0]){
    		if(k==0||T[j]==T[k]){++j;++k;
    		if(T[j]!=T[k]) nextval[j]=k;
    		else nextval[j]=nextval[k];
    		}
    		else k=nextval[k];
    	}
    }//get_nextval