本文共 6994 字，大约阅读时间需要 23 分钟。

串的存储结构(堆串)

一、堆串简介

        串的堆存储结构，与定长顺序串的存储结构类似，都是用一维数组地址连续的存储单元存储串的字符序列，不同的是堆串的存储空间是在程序执行过程中动态分配的。

二、堆串存储结构

typedef struct {
   	char *ch;//若是非空串，则是指向串的起始地址；否则为空	int len;//字符串的长度}HString;

为了便于理解和讨论，这里在给串分配存储空间时，在实际串长的基础上多分配一个存储空间，且连续空间的第0号单元不使用。

三、堆串基本操作的实现(VS2017开发环境)

这里也包含了KMP和BF模式匹配部分的代码，头文件如下:

#pragma once#include
   
    typedef struct {
   	char *ch;//若是非空串，则是指向串的起始地址；否则为空	int len;//字符串的长度}HString;//串初始化函数void HStrInit(HString *S) {
   	S->ch = NULL;	S->len = 0;}//串赋值函数int HStrAssign(HString *S, const char *chars) {
   	int i = 0;	if (NULL == chars || NULL == S) {
   		return 0;	}	else {
   		while (chars[i] != '\0') {
   			i++;		}		S->len = i;//串S的长度等于串chars的长度		if (0 != S->len) {
   			if (S->ch != NULL) {
   				free(S->ch);			}			S->ch = (char *)malloc(sizeof(char)*(S->len + 1));//0号单元不用，故比实际需求多开辟一个空间			if (NULL == S->ch) {
   //空间开辟失败				return 0;			}			for (i = 1; i <= S->len; i++) {
   //将chars的内容逐一赋值给S->ch				S->ch[i] = chars[i - 1];			}		}		else {
   			S->ch = NULL;//当chars的长度为0时，则置S为空串。		}		return 1;	}}//串插入函数(在第pos个位置之前插入T,)int HStrInsert(HString *S, int pos, const HString T) {
   	int i;	char *temp;	if (NULL == S || NULL == S->ch || NULL == T.ch || pos > S->len || pos < 1) {
   		return 0;//插入位置不合法	}	else {
   		temp = (char *)malloc(sizeof(char)*(S->len + T.len + 1));		if (NULL == temp) {
   			return 0;		}		else {
   			for (i = 1; i < pos; i++) {
   //把S串pos（不含S->ch[pos]）之前的字符赋值给temp				temp[i] = S->ch[i];			}			for (i = pos; i < pos + T.len; i++) {
   //把串T赋给temp[pos]到temp[pos+T.len]				temp[i] = T.ch[i - pos + 1];			}			for (i = pos + T.len; i <= S->len + T.len; i++) {
   //把原来S串中pos之后的内容链接到temp尾部				temp[i] = S->ch[i - T.len];			}			free(S->ch);			S->ch = temp;			S->len = S->len + T.len;//更新S串的长度			return 1;		}	}}//串删除函数int HStrDelete(HString *S, int pos, int len) {
   	int i;	char *temp;	if (NULL == S || NULL == S->ch || len < 0 || pos<1 || pos>S->len - len + 1) {
   		return 0;	}	else {
   		temp = (char *)malloc(sizeof(char)*(S->len - len + 1));		if (NULL == temp) {
   			return 0;		}		else {
   			for (i = 1; i < pos; i++) {
   //把S串pos（不含S->ch[pos]）之前的字符复制给temp				temp[i] = S->ch[i];			}			for (i = pos; i <= S->len - len; i++) {
   //把temp[pos]之后的部分改写为				temp[i] = S->ch[i + len];          //S[pos+len:S->len]的内容			}			free(S->ch);			S->ch = temp;			S->len = S->len - len;   //更新串S的长度			return 1;		}	}}//打印void print(HString *S) {
   	for (int i = 1; i <= S->len; i++) {
   		printf("%c", S->ch[i]);	}	printf("\n");}//BF模式匹配算法int Index(HString S, int pos, HString T) {
   	int i = pos;//主串从pos开始	int j = 1;//模式串从头开始	while (i <= S.len&&j <= T.len) {
   		if (S.ch[i] == T.ch[j]) {
   //当对应字符相等时，比较后续字符			i++;			j++;		}		else {
   //当对应字符不相等时			i = i - j + 2;//主串回溯到i-j+2的位置重新比较			j = 1;//模式串从头开始重新比较		}	}	if (j > T.len) {
   //匹配成功时，返回匹配起始位置		return i - T.len;	}	else {
   //匹配失败，返回0		return 0;	}}//统计BF模式匹配算法的比较次数int IndexCount(HString S, int pos, HString T) {
   	int i = pos;//主串从pos开始	int j = 1;//模式串从头开始	int count = 0;	while (i <= S.len&&j <= T.len) {
   		if (S.ch[i] == T.ch[j]) {
   //当对应字符相等时，比较后续字符			i++;			j++;		}		else {
   //当对应字符不相等时			i = i - j + 2;//主串回溯到i-j+2的位置重新比较			j = 1;//模式串从头开始重新比较		}		count++;	}	return count;	}//KMP模式匹配算法void Get_Next(HString T, int next[]) {
   	int j = 1, k = 0;	next[1] = 0;	while (j < T.len) {
   		if (k == 0 || T.ch[j] == T.ch[k]) {
   			++j;			++k;			next[j] = k;		}		else {
   			k = next[k];		}	}}void Get_NextVal(HString T, int next[], int nextval[]) {
   	int j = 2, k = 0;	Get_Next(T, next);	nextval[1] = 0;	while (j <= T.len) {
   		k = next[j];		if (T.ch[j] == T.ch[k]) {
   			nextval[j] = nextval[k];		}		else {
   			nextval[j] = next[j];		}		j++;	}}int Index_KMP(HString S, int pos, HString T,int nextval[]) {
   	int i = pos;//主串从第pos开始	int j = 1;//模式串从头开始	while (i <= S.len&&j <= T.len) {
   		if (j == 0 || S.ch[i] == T.ch[j]) {
   //继续比较后继字符			++i;			++j;		}		else {
   			j = nextval[j];		}	}	if (j > T.len) {
   //匹配成功		return i - T.len;//返回匹配的起始位置	}	else {
   		return 0;	}}//统计KMP算法的比较次数int Index_KMPCount(HString S, int pos, HString T, int nextval[]) {
   	int i = pos;//主串从第pos开始	int j = 1;//模式串从头开始	int count = 0;	while (i <= S.len&&j <= T.len) {
   		if (j == 0 || S.ch[i] == T.ch[j]) {
   //继续比较后继字符			++i;			++j;		}		else {
   			j = nextval[j];		}		count++;	}	return count;}//比较两个串大小int StrCompare(HString S, HString T) {
   	int min = S.len < T.len ? S.len : T.len;	int flag;	for (int i = 1; i <=min; i++) {
   		if (S.ch[i] == T.ch[i]) {
   			flag = 0;		}		else if (S.ch[i] > T.ch[i]) {
   			flag = 1;			break;		}		else {
   			flag = -1;			break;		}	}	if (S.len > T.len&&(flag==0)) {
   		flag = 1;	}	else if (T.len > S.len && (flag == 0)) {
   		flag = -1;	}	return flag;}//用串V替换串S中出现的所有与串T相等的不重叠的子串int StrReplace(HString *S, HString T, HString V,int nextval[]) {
   	int i = 1;	int index;	while(i<=S->len){
   		 index = Index_KMP(*S, i, T, nextval);		if (index == 0) {
   		//	printf("替换失败!\n");			return 0;		}		else {
   //这里目前找到后的办法是先插后删，如果先删后插，那如果是在最后匹配到是不能插的，			//除非将插入函数修改为后插函数，上面的HStrInsert()是前插函数			printf("index=%d", index);			HStrInsert(S, index, V);			HStrDelete(S,index+V.len, T.len);			print(S);			i = index + V.len;		}	}	return 1;}//堆串求逆操作,求逆的结果赋值给T串带回int StrReverse(HString *S, HString *T) {
   	char *temp;	temp = (char *)malloc(sizeof(char)*(S->len + 1));	for (int i = S->len; i >= 1; i--) {
   		temp[S->len-i+1] = S->ch[i];	}	free(T->ch);	T->ch = temp;	T->len = S->len;	return 1;}
   

源文件：

#include
   
    #include
    
     #include
     
      #include"DString.h"int main() {
   	HString S;	HString T;	HString V;	HStrInit(&S);	HStrInit(&T);	HStrInit(&V);	char a[] = "adabbbab";	char b[] = "ab";	char c[] = "kkk";	HStrAssign(&S, a);	HStrAssign(&T, b);	HStrAssign(&V, c);	printf("主串:");	print(&S);	printf("模式串:");	print(&T);	printf("要替换的串:");	print(&V);	printf("BF模式匹配:\n");	int index = Index(S, 1, T);	int count1 = IndexCount(S, 1, T);	printf("index=%d\n", index);	printf("比较次数:%d\n", count1);	printf("KMP模式匹配:\n");	int *next,*nextval;	next = (int *)malloc(sizeof(int)*(T.len + 1));	nextval = (int *)malloc(sizeof(int)*(T.len + 1));	Get_NextVal(T,next,nextval);	printf("next[]数组如下\n");	for (int i = 1; i < (T.len + 1); i++) {
   		printf("%d ", next[i]);	}	printf("\nnextval[]数组如下:\n");	for (int i = 1; i < (T.len + 1); i++) {
   		printf("%d ", nextval[i]);	}	printf("\n");	int index1 = Index_KMP(S, 1, T, nextval);	int count2 = Index_KMPCount(S, 1, T, nextval);	printf("index1=%d\n", index1);	printf("比较次数:%d\n",count2);	printf("-------------用串V替换串S中出现的所有与串T相等的不重叠的子串-------------------\n");	/*int test = StrCompare(S, T);	printf("test=%d\n", test);*/	int index2 = StrReplace(&S, T, V, nextval);	printf("-----------逆置S串，结果由T带回---------------------\n");	StrReverse(&S, &T);	printf("逆置前:");	print(&S);	printf("逆置后:");	print(&T);	system("pause");	return 0;}
     
    
   

四、测试(这里并没有每个函数都测试，用哪个就调用哪个就行)

转载地址：http://bnzzi.baihongyu.com/