数据结构学习笔记（3）——串

刺骨的言语ヽ痛彻心扉 2022-10-13 15:58 191阅读 0赞

# 串数据类型的定义 #

## 串的定义 ##

1.  串是由0个或多个字符组成的有限序列。
2.  串中字符的个数称为串的长度，0个字符的串称为空串。
3.  串中任意连续的字符组成的子序列称为子串，包含子串的串称为主串。
4.  串是一种限定元素为字符的线性表。
5.  串与线性表最大的区别是操作集不同，线性表主要是针对某一元素操作，而串则主要针对子串操作。

## 串的存储结构 ##

*  定长顺序存储表示

typedef struct Str{
        
        char str[maxSize+1];	//maxSize为已定义的常量，表示串的最大长度。+1是以为多出一个结束标记`\0`
        int length;
    }Str;

虽然多了一个结束标记’\\0’，但是计算长度length时并不纳入计算范围。

*  变长分配存储表示（动态分配存储表示）

typedef struct Str{
        
        char *ch;	//指向动态分配存储空间首地址的字符指针
        int length;
    }Str;

使用动态分配时，需要使用malloc()函数来分配一个长度为length，类型为char的连续存储空间：`str.ch=(char*)malloc(sizeof(char)*(n+1))`作为串的基地址。

## 串的基本操作 ##

1.  赋值操作
    
    串是一个数组，这里的赋值操作不是指对某一位置处的赋值，而是将一个字符串（数组）的值赋给另一个数组。

//将ch赋值给str
    int strAssign(Str& str, char* ch) {
        
        //1.释放原串空间
    	if (str.ch) free(str.ch);
    	//2.求ch的长度
    	int len = 0;
    	char *c = ch;
    	while (*c) {
        	//c值为'\0'结束循环
    		++len;
    		++c;	//由于c一开始指向的是一片连续存储空间的首地址，那么相邻存储单元的地址就相差1，这里c++就相当于指针c指向ch中下一个字符
    	}
    	//3.如果ch的长度为0，那么直接返回空串即可
    	if (len == 0) {
        
    		str.ch = NULL;
    		str.length = 0;
    		return 1;
    	}
        //4.ch的长度不为0，开始赋值
    	else {
        
    		//先分配存储空间，返回申请到的连续存储空间的首地址，+1是为了存放'\0'
    		str.ch = (char*)malloc(sizeof(char)*(len + 1));
    		if (str.ch == NULL) return 0;	//申请存储空间失败
    		else {
        
    			c = ch;		//上面测量长度时，c已经指向了ch的最后一个字符，这里要将指针重新指向数组的头部
    			for (int i = 0;i <= len;i++, c++) {
        		//显然循环了len+1次，因为'\0'也要赋值过来
    				str.ch[i] = *c;
    			}
    			str.length = len;
    			return 1;
    		}
    	}
    }

函数`int strAssign(Str& str, char* ch){...}`的使用：

`strAssign(str,"abcde")`此句执行后，str.ch的值就是abcde，str.length的值就是5。

1.  获取字符串的长度

//如果串的定义中有定义length的话，直接返回length
    int getStrLen(Str str){
        
        return str.length;
    }
    //如果没有定义length，可以通过上面的方法计算长度
    int getStrLen(Str str){
        
        int len = 0;
    	char *c = str.char;
    	while (*c) {
        	
    		++len;
    		++c;	
    	}
    }

1.  串的比较

设两串 A和 B 中的待比较字符分别为 a 和 b：

如果 a 的 ASCII码小于 b 的 ASCII 码， 则返回 A 小于B 的标记（一个负数）；

如果 a 的 ASCII 码大于b 的 ASCII 码， 则返回 A 大于B 的标记（一个正数）；

如果 a 的 ASCII 码等于b 的 ASCII 码， 则继续下一对字符；

经过上述比较没有比较出A和B大小的情况下，规定先结束的字符串为较小串，两串同时结束则A与B相等（返回0）；

//用s1去和s2比较
    int strCompare(Str s1,Str s2) {
        
    	for (int i = 0; i < s1.length && i<s2.length; i++) 
    	{
        	
    		if (s1.ch[i] != s2.ch[i]) {
        		
    			return s1.ch[i] - s2.ch[i];		
    		}
    	}
        return s1.length - s2.length;
    
    	/*
    		1.字符的比较、加减都是在操作它们的ASCII码
    		
    		2.for循环里发现某一位置s1和s2对应的字符的ASCII码不相等，则返回s1.ch[i] - s2.ch[i]，有2种情况：
    		s1.ch[i] - s2.ch[i] < 0，则s1 < s2
    		s1.ch[i] - s2.ch[i] > 0，则s1 > s2
    
            3.for循环里面没有return,则在循环外返回s1.length - s2.length，有3种可能结果：
            s1.length - s2.length == 0,则二者同时结束循环且所有字符相等，s1 == s2
            s1.length - s2.length < 0,则s1先结束循环，s1 < s2
            s1.length - s2.length > 0,则s2先结束循环，s1 > s2
        */
    
    }

1.  串的拼接

int concat(Str& str, Str& str1, Str& str2) {
        
    	//如果str.ch非NULL，就把原有的空间释放，并给ch赋NULL
    	if (str.ch) {
        
    		free(str.ch);
    		str.ch = NULL;
    	}
    	//申请一片足以放下str1、str2两个字符串的空间,+1是为了放结束符'\0'
    	str.ch = (char*)malloc(sizeof(char)*(str1.length + str2.length + 1));
    	if (!str.ch)
    		return 0;	//申请空间失败
    	//申请成功，开始拼接s1
    	int i = 0;
    	while (i < str1.length) {
        
    		str.ch[i] = str1.ch[i];
    		++i;
    	}
        //拼接s2
    	int j = 0;
    	while (j <= str2.length) {
        	//<=legth循环了length+1次，把'\0'也赋值过来
    		str.ch[i + j] == str2.ch[j];
    		++j;
    	}
        //修改str的参数值length
    	str.length = str1.length + str2.length;
    	return 1;
    }

1.  获取子串

//截取字符串
    //从字符串str的pos位置开始，截取长度为len的字符串赋值给sbustr，成功返回1，失败返回0
    int subString(Str& substr, Str str, int pos, int len) {
        
    	//校验输入值
    	if (pos < 0 || len >= str.length || len<0 || len>str.length - pos) {
        
    		return 0;
    	}
    	//释放掉ch的空间
    	if (substr.ch) {
        
    		free(substr.ch);
    		substr.ch = NULL;
    	}
    	//开始截取
    	//case1——len==0
    	if (len == 0) {
        
    		substr.ch = NULL;
    		substr.length = 0;
    		return 1;
    	}
    	//case2——len!=0
    	else {
        
    		//申请空间
    		substr.ch = (char*)malloc(sizeof(char)*len + 1);
    		if (substr.ch == NULL) return 0;
    		//核心，截取字符串
    		for (int i = pos, j = 0;i < pos + len;i++, j++) {
        
    			substr.ch[j] = str.ch[i];
    		}
    	}
    	substr.ch[len] = '\0';
    	substr.length = len;
    	return 1;
    }

1.  串清空

//串清空
    int clearString(Str &str) {
        
    	if (str.ch) {
        
    		free(str.ch);
    		str.ch = NULL;
    	}
    	str.length = 0;
    	retrn 1;
    }

# KMP算法 #

## 简单模式匹配 ##

用两个指针i和j分别表示主串和模式串中的将要进行比较的字符下标，指针k用来记录上一趟匹配主串的开始位置；

从主串和模式串的第一个字符开始开始匹配，如果相等，继续比较下一个字符，直到匹配成功，或某一位置字符不匹配；

如果中途某一位置字符不匹配，i 回溯到这一趟比较最开始的位置（k），从这个位置的下一个位置和模式串第一个字符（j回溯到1）比较。

//简单模式匹配，要求返回模式串在主串中的位置（首个字符的位置）
    int index(Str str, Str substr) {
        
    	int i = 1, j = 1;	
    	int k = i;	
    	while (i <= str.length && j <= substr.length) {
        
    		if (str.ch[i] == substr.ch[j]) {
        
    			++i;
    			++j;
    		}
    		else {
        
    			j = 1;
    			i = k++; 
    		}
    	}
    	if (i > substr.length) //匹配成功时，j=substr.length+1
    		return k;
    	else 
    		return 0;
    }
    //算法的时间复杂度：O(mn),m和n分别表示主串和模式串的长度

## KMP算法匹配 ##

### next\[\]数组的获取 ###

KMP算法的关键就是next\[\]的获取：

//getNext：给定字符串s,求s的next[]数组。这里默认串从s.ch[]的1位置开始存储,同样的，next[]也是从1开始。
    
    void getNext(Str s, int next[]) {
        
        
    	int i = 1;
    	int j = 0;	
    	next[1] = 0;	//规定next[1]=0	
        
    	while (i < s.length) {
        		
    		if (j == 0 || s.ch[i] == s.ch[j]) {
        	
    			++i;
    			++j;
    			next[i] = j;
    		}
    		else {
        
    			j = next[j];
    		}
    	}
    }
    
    /* while循环表示即从1开始求模式串的next数组：
    	首次进入循环，此时i==1,j==0，且next[1]=0已知，不需要比较，直接令next[2]=1；
    	...
    	假设现在s的next数组已经求到了i位置，next[i]==j已知（i前面每一个位置的next值都可知），怎么求next[i+1]？
    	分析：next[i+1]等于s.ch[1]~s.ch[i]的最大公共前后缀长度+1；
    		 next[i]==j已知，即s.ch[1]~s.ch[i-1]的最大公共前后缀长度=j-1；
    	那么此时只要看s.ch[i]和s.ch[j]的值就可以判断：
    		1.如果s.ch[i]==s.ch[j]，那么自然next[i+1]=j+1;
    		2.如果s.ch[i]!=s.ch[j]，此时将求next[i+1]的问题视为模式匹配问题，
    		即前缀s.ch[1]...s.ch[j]去和后缀s.ch[i-j+1]...s.ch[i]匹配，
    		那么此时应将j指针回溯到j=next[j],再令s.ch[j]去和s.ch[i]比较，
    		重复上述的比较过程，直到出j==0或者二者相等。
    		（记住这个处理过程即可，原理网上找图片更好理解）
    	...
    	j==0说明：
    		1.如果是首次进入循环，此时i==1,j==0，规定next[1]=0。此时直接令next[2]=1
    		（实际上不管任何字符串，它的第一个字符和第二个字符的next值都应该是1，
    		因为它们的公共前后缀都是0，只不过这里为了方便运算，规定第一个字符的next为0）；
    		2.非首次进入循环，则说明此时前缀s.ch[1]...s.ch[j]去和后缀s.ch[i-j+1]...s.ch[i]
    		没有公共前后缀，那么next[i+1]=j+1=0+1=1；
    		则此时next[i+1]已知，再接着去求next[i+1+1]。
    */

### KMP算法 ###

i和j表示主串和模式串上字符下标；

取主串和模式串的字符从位置1开始挨个进行比较，如果相等，就接着比较下一个字符；

如果不相等，i不变，取模式串此位置j上的next\[j\]，用模式串next\[j\]位置上的字符去和主串上的字符i接着比较。

特殊的，这里的j=0只针对next\[1\]，实际上，在next数组中，只有next\[1\]是等于0的。j=0时，指针i和j都往后挪一位，即若主串i位置和模

式串第一个字符不相等，就从主串中的i+1位置继续与模式串第一个字符比较。

//KMP，substr是模式串，next[]是它的next数组，str是主串,字符串数组和next数组均是从1开始存储
    int KMP(Str str, Str substr, int next[]) {
        
        
    	int i = 1;
        int j = 1;
        
    	while (i <= str.length && j <= substr.length) {
        		
    		if (j == 0 || str.ch[i] == substr.ch[j]) {
        		
    			++i;
    			++j;
    		}
    		else {
        
    			j = next[j]; //与简单匹配求解最大的不同之处，i不回溯，只回溯j
    		}
    	}
        
    	if (j > substr.length) 	
    		return i - substr.length;
    	else 
    		return 0;
    }
    //KMP算法的时间复杂度（包含求next数组的过程）：O(m+n)，m和n分别表示主串和模式串的长度

1.  KMP算法的关键就在于求取模式串的next\[\]，手动计算时，next\[i\]等于模式串的子串（位置1到位置i-1）的最大公共前后缀长度+1；
2.  KMP的匹配算法和简单匹配算法形式上很相似，KMP算法的优势是建立在模式串中存在大量”部分匹配“基础上，如果模式串每个字符都和其他字符不同（每个字符的next值都为1），那么KMP算法和简单匹配（暴力匹配）的时间复杂度没有区别。
3.  KMP算法的特点是主串中的i不需要回溯，这意味着对于规模大的外存中字符串的匹配操作可以分段进行，每次可以读取部分进入内存比较，完成后写回外存，且不需要在后续比较中再读入，减少了I/O操作，提高了效率。这是KMP算法的优势之一。

### KMP算法的改进 ###

求nextval\[\]的一般步骤：

1.  当i=1时，next\[i\]=0，作为特殊标记，这一点与next数组没有区别
2.  从左往右，当i不为1时（next\[i\]=j），如果 c h i ch\_i chi 不等于 c h j ch\_j chj ，则nextval\[i\]=j=next\[i\]
3.  从左往右，当i不为1时（next\[i\]=j），如果 c h i ch\_i chi 等于 c h j ch\_j chj ，则nextval\[i\]=next\[j\]=next\[next\[j\]\]

void getNextval(Str s, int nextval[]) {
        
    	int i = 1;
    	int j = 0;
    	nextval[1] = 0;			
    	while (i < s.length) {
        
    		if (j == 0 || s.ch[i] == s.ch[j]) {
        
    			++i;
    			++j;
    			//nextval与next不同之处,这一块原本是next的赋值区域，所以只需要改动这里
    			if (s.ch[i] != s.ch[j]) 
    				nextval[i] = j;
    			else 
    				nextval[i] = nextval[j];
    			
    		}
    		else {
        
    			j = nextval[j];
    		}
    	}
    }