文章目录 前言一、实验目的二、实验内容三、实验环境1）使用的操作系统及版本2）使用的编译系统及版本 四、实验步骤及说明1、用c语言，设计出串的存储结构2、对应堆存储，设计出各功能算法。1）串赋值2）求串长3）串比较4）串连接5）求子串6）子串插入7）子串置换8）子串定位（BF算法） 五、实验总结总结
前言
计算机上非数值处理的对象大部分是字符串数据，字符串一般简称为串。串是一种特殊的线性表，其特殊性体现在数据元素是一个字符，也就是说，串是一种内容受限的线性表。
提示：以下是本篇文章正文内容，下面案例可供参考
一、实验目的掌握串类型的实现方法和文本模式匹配方法。
二、实验内容使用c语言编写顺序串的所有功能，包括串赋值、串比较、串连接、求串长、求子串、串删除、串置换、子串查找定位等。采用菜单调用的方式实现。
主菜单：
1：串赋值 2：求串长 3：串比较 4：串连接 5：求子串 6：子串插入 7：子串置换 8：子串定位 9：退出 三、实验环境 1）使用的操作系统及版本Windows10
2）使用的编译系统及版本Dev-C++ 5.11
四、实验步骤及说明 1、用c语言，设计出串的存储结构串是一种特殊的线性表，它的数据元素由一个字符组成。在计算机数据处理中，非数值处理的对象经常是字符串数据。串的存储有多种方法，包括定长顺序存储、堆存储及链式存储等，从存储利用上来说，堆存储最有效率，因此本实验以堆存储为基础来设计数据结构。
堆分配存储结构的特点是：仍以一组地址连续的存储单元存放串的字符序列，但其存储空间是在算法执行过程中动态分配得到的。在C语言中，存在一个称之为“堆”的自由存储区，并由C语言的动态分配函数malloc(?)和free(?)来管理。利用函数malloc(?)为每一个新产生的串分配一块实际需要的存储空间，若分配成功，则返回一个指针，指向串的起始地址。
串的堆分配存储结构如下：
typedef struct{char *ch;int length;}HString; 2、对应堆存储，设计出各功能算法。 1）串赋值 int StrAssign(HString *T,char *chars){//将字符串chars赋值给串Tint i,j;char *c;if(T->ch) free(T->ch); //释放原有的空间for(i=0, c=chars; *c; ++i, ++c); //求chars的长度if(!i) {T->ch=NULL;T->length=0;}else { if(!(T->ch=(char *)malloc((i+1)*sizeof(char)))) return ERROR; for(int n=0; n<(i+1); n++)*(T->ch+n)=0;//清空串Tfor (j=0;j<i;j++)T->ch[j]=chars[j];T->length=i;}return OK;} 2）求串长 int StrLength(HString S){//返回串S的长度 return S.length;} 3）串比较 Status StrCompare(HString S, HString T){//比较串S、T，若S>T返回正数，S=T返回0，S<T返回负数 char *SStr = S.ch, *TStr = T.ch;while(*SStr==*TStr && *SStr && *TStr){SStr++;TStr++; } if(*SStr == *TStr)return 0;else return (int)(*SStr-*TStr);} 4）串连接 Status Concat(HString *T, HString S){//将S连接于T，用T返回 char *TStr;if(!(TStr=(char *)malloc((T->length+S.length+1)*sizeof(char))))return ERROR;for(int i=0; i<(T->length+S.length+1); i++)*(TStr+i)=0;//清空串TStrint i=0;while(*(T->ch+i)) {//将指针指向pos位置 *(TStr+i) = *(T->ch+i);i++; }while(*(S.ch)){*(TStr+i) = *(S.ch++);T->length++;i++;}free(T->ch);T->ch = TStr;return OK; } 5）求子串 Status SubString(HString *SubS, HString S, int pos, int len){//用SubS返回串S的pos位置开始len长的子串 char *ch;int i=0, x=len;if(!(ch=(char*)malloc((len+1)*sizeof(char))))return ERROR;for(int i=0; i<(len+1); i++)*(ch+i)=0;//清空串ch if(S.length < (pos+len-1))return ERROR;for(; pos>1; pos--)S.ch++;for(; x>0; x--){*(ch+i) = *S.ch++;i++;}SubS->length = len;free(SubS->ch);SubS->ch = ch;return OK; } 6）子串插入 Status StrInsert(HString *S, HString SubS, int pos){//在串S的pos位置插入子串SunS HString H, X;//创建串H ,XH.ch = X.ch = NULL;H.length = X.length = 0; //初始化if(!(H.ch=(char*)malloc((S->length+SubS.length+1)*sizeof(char))))return ERROR;if(!(X.ch=(char*)malloc((S->length+SubS.length)*sizeof(char))))return ERROR;SubString(&X, *S, 1, pos-1);//取出S中pos位置前的串存放在X for(int i=0; i<(S->length+SubS.length+1); i++)*(H.ch+i)=0;//清空串H Concat(&H, X);//将X中字符串连接在空串H之后 Concat(&H, SubS);//将子串连接串H之后 SubString(&X, *S, pos, S->length-pos+1);//取出S中pos位置后的串存放在XConcat(&H, X);//将pos之后的串连接在串H之后 free(S->ch);S->ch = H.ch;free(X.ch);X.ch = NULL;return OK; } 7）子串置换 Status Replace(HString *S, HString T, HString V)/* 以串 v 置换串 s 中出现的所有和串 t 相同的非空串 */{ int s,t,v,i; HString sub,H;sub.length=H.length=0; s = StrLength(*S); t = StrLength(T); v = StrLength(V); i = 1; while(i <= s-t+1){ sub.ch=H.ch=NULL; SubString(&sub, *S, i, t);//将串S中的子串逐个提取出来与串T进行匹配 if(StrCompare(sub, T) == 0){//匹配相等时SubString(&H, *S, 1, i-1);//取出S中i位置前的串存放在H Concat(&H, V);//将替换串V连接到串H后 SubString(&sub, *S, i+t, s-(t+i)+1);//取出匹配相等的子串的后面的子串 Concat(&H, sub);//将sub连接到串H后 free((*S).ch);(*S).ch = H.ch;free(sub.ch); i += t; s = StrLength(*S);//操作完一次之后，串S已经改变，需要注意 } else{ ++i; } } } 8）子串定位（BF算法） int Index_BF(HString *S, HString SubS){//使用BF算法，返回子串SubS在主串中的位置 int i=0, j=0;while(S->ch[i] && SubS.ch[j]){if(S->ch[i]==SubS.ch[j]){i++;j++;}else{i=i-j+1;j=0;}}if(!SubS.ch[j])return i-j+1;else return 0;} 五、实验总结这次实验的重点在子串插入和子串置换，其中子串置换使用的模式匹配算法更是难点，开始自己依然没理解KMP算法原理，经过不断学习试错，也算大体明白其原理，但是使用时依然有较大问题，最后依然使用了BF算法来完成此次实验。
总结
提示：这里对文章进行总结：
本文是自己数据结构作业的一个记录，因为是假期整理的可能会有错误，欢迎告知。
代码全文以及实验报告原文下载链接
提取码：zryy。
