数据结构之线性结构-串

迈不过友情╰ 2022-10-19 04:16 234阅读 0赞

### 文章目录 ###

*  串
 *   *  定义
     *  基本操作

# 串 #

## 定义 ##

串是由零个或多个字符组成的有限序列

## 基本操作 ##

StrAssign(&T,chars):赋值操作。把串T赋值为chars。  
StrCopy(&T,S):复制操作。由串S复制得到串T。  
StrEmpty(S):判空操作。若S为空串，则返回TRUE，否则返回FALSE。  
StrLength(S):求串长。返回串S的元素个数。  
ClearString(&S):清空操作。将S清为空串。  
DestroyString(&S):销毁串。将串S销毁(回收存储空间)。  
Concat(&T,S1,S2):串联接。用T返回由S1和S2联接而成的新串

#include<stdio.h>
    #include<stdlib.h>
    
    
    //定义堆分配串
    typedef struct {
        
    	char* ch;
    	int length;
    }HeapStr;
    
    
    //函数声明
    //初始化
    int InitiHeapStr(HeapStr& T);
    //赋值
    int HeapStrAssign(HeapStr& T, char* chars);
    //插入
    int HeapStrInsert(HeapStr& S, int pos, HeapStr T);
    //复制
    int HeapStrCopy(HeapStr& T, HeapStr S);
    //判空
    int HeapStrEmpty(HeapStr S);
    //比较
    int HeapStrCompare(HeapStr S, HeapStr T);
    //求串长
    int HeapStrLength(char s[]);
    //两个串连接
    int ConcatHeapStr(HeapStr& S, char* s1, char* s2);
    //求子串
    int SubHeapStr(HeapStr& Sub, HeapStr S, int pos, int len);
    //删除
    int HeapStrDelete(HeapStr& S, int pos, int len);
    //清空
    int ClearHeapStr(HeapStr& S);
    //销毁
    int DestroyHeapStr(HeapStr& S);
    //输出
    int StrPrin(char* s);
    //暴力匹配
    int HeapStrBFIndex1(HeapStr S, HeapStr T);
    int HeapStrBFIndex2(HeapStr S, HeapStr T);
    //克努特—莫里斯—普拉特操作（简称KMP算法）
    int HeapStrIndexKMP(HeapStr S, HeapStr T, int next[]);
    int get_next(HeapStr T, int next[]);
    
    //初始化
    int InitiHeapStr(HeapStr& T) {
        
    	T.ch = NULL; T.length = 0;
    	return 1;
    }
    
    //赋值
    int HeapStrAssign(HeapStr& T, char* chars) {
        
    	if (T.ch)
    		free(T.ch);//释放原来的内容
    	int len, i;
    	len = HeapStrLength(chars);
    	if (len) {
        
    		T.ch = NULL; T.length = 0;
    	}
    	else {
        
    		if (!(T.ch = (char*)malloc(len * sizeof(char)))) {
        //根据chars的长度为其分配空间
    			printf_s("溢出");
    			return 0;
    		}
    		for (i = 0; i < len; i++)
    			T.ch[i] = chars[i];
    		T.length = len;
    	}
    
    	return 1;
    }
    
    //插入
    int HeapStrInsert(HeapStr& S, int pos, HeapStr T) {
        
    	int i;
    	if (pos < 1 || pos > S.length + 1)//pos不合法
    		return 0;
    	if (T.ch==NULL)//如果T为空，直接返回
    		return 1;
    	if (T.length)
    	{
        
    		S.ch = (char*)realloc(S.ch, (S.length + T.length) * sizeof(char));
    		for (i = S.length - 1; i >= pos - 1; --i)//让串S腾出位置
    			S.ch[i + T.length] = S.ch[i];//在腾位置的时候一般都是从最后面开始往前
    		for (i = 0; i < T.length; i++)
    			S.ch[pos + i - 1] = T.ch[i];
    		S.length += T.length;
    	}
    	return 1;
    }
    
    //复制
    int HeapStrCopy(HeapStr& T, HeapStr S) {
        
    	int i;
    	if (T.ch)
    		free(T.ch);
    	if(!(T.ch = (char*)malloc(S.length * sizeof(char)))) {
        //分配空间
    		printf_s("溢出");
    		return 0;
    	}		
    	for (i = 0; i < S.length; i++)
    		T.ch[i] = S.ch[i];
    	T.length = S.length;
    	return 1;
    }
    
    //判空
    int HeapStrEmpty(HeapStr S) {
        
    	if (S.length)
    		return 0;
    	else
    		return 1;
    }
    
    
    //比较
    int HeapStrCompare(HeapStr S, HeapStr T) {
        
    	//若S>T，则返回值>0；若S=T，则返回值=0；若S<T，则返回值<0
    	int i;
    	for (i = 0; i < S.length && i < T.length; ++i)
    		if (S.ch[i] != T.ch[i])
    			return S.ch[i] - T.ch[i];
    	return S.length - T.length;//如果某一个串长度读完了，字符串还相等，返回两者的长度差。
    }
    
    //求串长
    int HeapStrLength(char s[]) {
        
    	int i;
    	for (i = 0; s[i] != '\0'; i++);
    	return i;
    }
    
    //两个串连接
    int ConcatHeapStr(HeapStr& S, char* s1, char* s2) {
        
    	int i = 0, len1, len2;
    	len1 = HeapStrLength(s1);
    	len2 = HeapStrLength(s2);
    	if (0 == len1 && 0 == len2) {
        //判空
    		printf_s("串空");
    		return 0;
    	}
    	if (S.ch)
    		S.ch = NULL;
    	S.length = len1 + len2;//串长
    	S.ch = (char*)malloc(S.length * sizeof(char));
    	for (i = 0; i < len1; i++)
    		S.ch[i] = s1[i];
    	for (i = 0; i < len2; i++)
    		S.ch[i + len1] = s2[i];//从第一个串长度之后开始，串长代表的位置正好是第一个串结束的下一个
    	
    	return 1;
    }
    
    //求子串
    int SubHeapStr(HeapStr& Sub, HeapStr S, int pos, int len) {
        
    	int i;
    	if (pos + len > S.length) {
        
    		printf_s("下标超出数组范围");
    		return 0;
    	}
    	if (pos + len < 0) {
        
    		printf_s("下标出错");
    		return 0;
    	}
    
    	if (!len)
    		InitiHeapStr(Sub);
    	else
    	{
        
    		Sub.ch = (char*)malloc(len * sizeof(char));
    		for (i = 0; i < len; i++)
    			Sub.ch[i] = S.ch[i+pos];
    		Sub.length = len;
    	}
    	return 1;
    }
    
    //删除
    int HeapStrDelete(HeapStr& S, int pos, int len) {
        
    	int i;
    	if (S.length <= pos + len)
    		return 0;
    	for (i = pos - 1; i <= S.length - len; i++)
    		S.ch[i] = S.ch[i + len];
    	S.length -= len;
    	S.ch = (char*)realloc(S.ch, S.length * sizeof(char));//先将pos+len后面的覆盖到pos后，然后在给串重新分空间
    	return 1;
    }
    
    //清空
    int ClearHeapStr(HeapStr& S) {
        
    	if (S.ch) {
        
    		free(S.ch);
    		S.ch = NULL;
    	}
    	S.length = 0;
    	return 1;
    }
    
    //销毁
    int DestroyHeapStr(HeapStr& S) {
        
    	return 1;
    }
    
    //输出
    int StrPrin(HeapStr S){
        
    	int i;
    	for (i = 0; i < S.length; i++)
    		printf("%c", S.ch[i]);
    	printf("\n");
    	return 1;
    }
    
    
    /*
    	模式匹配，定位操作
    	查找子串在主串中的位置
    	主串S长n，子串T长m
    	最好时间复杂度O(n)，最坏时间复杂度O(nm)，一般时间复杂度O(m+n)
    */
    //朴素匹配，暴力算法，Brute-Force
    int HeapStrBFIndex1(HeapStr S, HeapStr T) {
        
    	int i = 0, n = S.length, m = T.length;
    	HeapStr sub;
    	while (i < n - m + 1) {
        
    		SubHeapStr(sub, S, i, m);
    		if (HeapStrCompare(sub, T) != 0) {
        
    			++i;
    		}
    		else {
        
    			return i;//返回子串在主串的位置
    		}
    	}
    	return -1;
    }
    //S为主串，T为子串
    int HeapStrBFIndex2(HeapStr S, HeapStr T) {
        
    	int i = 0,j = 0;
    	while (i+j < S.length && j < T.length) {
        
    		if (S.ch[i+j] == T.ch[j]) {
        
    			j++;//继续比较后面的字符
    		}else {
        
    			i++; j = 0;
    		}
    	}
    	if (j == T.length)
    		return i;
    	else
    		return -1;
    }
    
    //改进的字符串匹配
    //克努特—莫里斯—普拉特操作（简称KMP算法）
    int HeapStrIndexKMP(HeapStr S, HeapStr T, int next[]) {
        
    	int i = 0, j = 0;
    	while (i<S.length&&j<T.length)	{
        
    		if (j >= 0 && S.ch[i] != T.ch[j]) {
        //如果不匹配，从next数组中获取下一个比较的值
    			j = next[j];
    
    		}
    		else {
        //如果匹配或者重新开始，即(j == -1 || S.ch[i] == T.ch[j])
    			 i++; j++;//继续比较后继字符
    		}
    	}
    	if (j == T.length)
    		return i - T.length;//返回首字符下标
    	else
    		return -1;
    }
    int get_next(HeapStr T,int next[]) {
        
    	int i = 0, j = -1;
    	next[0] = j;
    	while (i<T.length)	{
        
    		if (j >= 0 && T.ch[i] !=T.ch[j]) {
        
    			j = next[j];
    		}
    		else {
        
    			i++; j++;
    			next[i] = j;
    		}
    
    	}
    	return 1;
    }
    int get_nextval(HeapStr T, int next[]) {
        
    	int i = 0, j = -1;
    	next[0] = j;
    	while (i < T.length) {
        
    		if (j >= 0 && T.ch[i] != T.ch[j]) {
        
    			j = next[j];
    		}
    		else {
        
    			j++; i++;
    			if (T.ch[i] != T.ch[j])
    				next[i] = j;
    			else
    				next[i] = next[j];
    		}
    	}
    	return 1;
    }
    
    
    
    int main() {
        
    	HeapStr S,T;
    	InitiHeapStr(S);
    	InitiHeapStr(T);
    
    	int tmp;
    	int next[20];
    	char s1[] = "THIS IS ", s2[] = "A MATH BOOK ";
    	ConcatHeapStr(S, s1, s2);
    	StrPrin(S);
    	SubHeapStr(T, S, 3, 4);
    	StrPrin(T);
    
    	tmp=HeapStrBFIndex2(S,T);
    	if (tmp>=0) {
        
    		printf_s("匹配成功，下标：%d\n",tmp);
    	}
    	else {
        
    		printf_s("匹配失败\n");
    	}
    
    	get_next(T, next);
    
    	tmp = HeapStrIndexKMP(S, T,next);
    	if (tmp>=0) {
        
    		printf_s("匹配成功，下标：%d\n", tmp);
    	}
    	else {
        
    		printf_s("匹配失败\n");
    	}
    	ClearHeapStr(S);
    	ClearHeapStr(T);
    	system("pause");
    	return 0;
    }

![在这里插入图片描述][20210709112016369.png]

[20210709112016369.png]: /images/20221005/918dd99d103941199a7652293455dc35.png