串
实验三 串
一、实验目的
熟悉串的顺序存储结构
掌握串的基本运算及应用
二、实验内容
串采用顺序存储结构，编写朴素模式匹配算法，查找在串中是否存在给定的子串。（3.1.1采用暴力匹配、KMP实现，3.1.2采用BM实现）
编写一个算法
void strDelete(seqstring*S,int pos,int len)，从串S中删除第pos个字符开始长度为len的子串。要求：1≤pos≤S->length-len+1
Tips
暴力匹配算法：i指向文本串，j指向模式串。当匹配成功，继续匹配下一个字符；当匹配失败，令
i = i - (j - 1); j = 0;。即失配，i 回溯，j 被置为0。（因gets()作为字符串输入函数不安全，故改用scanf()进行输入，字符串内不能有空格）KMP 算法：
BM 算法：
删除函数运用循环直到长度条件满足即可，注意长度的改变。
Answer
3.1.1
//模式匹配的程序代码#include#include //#include #include //顺序串的结构类型定义#define maxsize 100typedef struct{ char str[maxsize]; int len;}seqstring;int Index(seqstring*, seqstring*);int Index2(seqstring*, seqstring*);//void main()int main(){ seqstring*S,*subS; S=(seqstring*)malloc(sizeof(seqstring)); subS=(seqstring*)malloc(sizeof(seqstring)); printf("输入串："); //gets(S->str); scanf("%s",S->str); S->len=strlen(S->str); printf("输入子串："); //gets(subS->str); scanf("%s",subS->str); subS->len=strlen(subS->str); if(Index2(S,subS)>0) { printf("匹配成功！\n"); } else { printf("匹配失败！\n"); } return 0;}//顺序串的朴素模式匹配int Index(seqstring* s,seqstring* p){ int i = 0; int j = 0; while (i < s->len && j < p->len) { if (s->str[i] == p->str[j]) { //如果当前字符匹配成功（即S[i] == P[j]），则i++，j++ i++; j++; } else { //如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0 i = i - j + 1; j = 0; } } //返回匹配结果 if (j == p->len) { return 1 + i - j; } else { return 0; }}//顺序串的KMP匹配int Index2(seqstring* s,seqstring* p){ int i = 0; int j = 0; void GetNext(seqstring*,int*); int next[maxsize]; GetNext(p,next); while (i < s->len && j < p->len) { //如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++ if (j == -1 || s->str[i] == p->str[j]) { i++; j++; } else { //如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j] //next[j]即为j所对应的next值 j = next[j]; } } //返回匹配结果 if (j == p->len) { return 1 + i - j; } else { return 0; }}//顺序串的KMP匹配，求next数组函数void GetNext(seqstring* p,int* next){ next[0] = -1; int k = -1; int j = 0; while (j < p->len - 1) { //p[k]表示前缀，p[j]表示后缀 if (k == -1 || p->str[j] == p->str[k]) { ++k; ++j; if (p->str[j] != p->str[k]) { next[j] = k; } else //因为不能出现p[j] = p[next[j]]，所以当出现时需要继续递归，k = next[k] = next[next[k]] { next[j] = next[k]; } } else { k = next[k]; } }}
3.1.2
//模式匹配的程序代码#include#include //#include #include //顺序串的结构类型定义#define maxsize 100typedef struct{ char str[maxsize]; int len;}seqstring;int Index(seqstring*, seqstring*);//void main()int main(){ seqstring*S,*subS; S=(seqstring*)malloc(sizeof(seqstring)); subS=(seqstring*)malloc(sizeof(seqstring)); printf("输入串："); //gets(S->str); scanf("%s",S->str); S->len=strlen(S->str); printf("输入子串："); //gets(subS->str); scanf("%s",subS->str); subS->len=strlen(subS->str); if(Index(S,subS)>0) { printf("匹配成功！\n"); } else { printf("匹配失败！\n"); } return 0;}//顺序串的BM匹配int Index(seqstring* s,seqstring* p){ int* MakeSkip(char *ptrn, int pLen); int* MakeShift(char* ptrn,int pLen); int* skip=MakeSkip(p->str,p->len); int* shift=MakeShift(p->str,p->len); int s_idx = p->len; if (p->len == 0) { return 1; } while (s_idx <= s->len)//计算字符串是否匹配到了尽头 { int p_idx = p->len, skip_stride, shift_stride; while (s->str[--s_idx] == p->str[--p_idx])//开始匹配 { if (s_idx < 0) { return 0; } if (p_idx == 0) { return 1; } } skip_stride = skip[(unsigned char)s->str[s_idx]];//根据坏字符规则计算跳跃的距离 shift_stride = shift[p_idx];//根据好后缀规则计算跳跃的距离 s_idx += (skip_stride > shift_stride) ? skip_stride : shift_stride;//取大者 } return 0;}//根据坏字符规则做预处理，建立一张坏字符表int* MakeSkip(char *ptrn, int pLen){ int i; //为建立坏字符表，申请256个int的空间 //之所以要申请256个，是因为一个字符是8位，所以字符可能有2的8次方即256种不同情况 int *skip = (int*)malloc(256*sizeof(int)); if(skip == NULL) { fprintf(stderr, "malloc failed!"); return 0; } //初始化坏字符表，256个单元全部初始化为pLen，没有在模式串出现的字符距离为pLen。 for(i = 0; i < 256; i++) { *(skip+i) = pLen; } //给表中需要赋值的单元赋值，不在模式串中出现的字符就不用再赋值了 while(pLen != 0) { *(skip+(unsigned char)*ptrn++) = pLen--; } return skip;}//根据好后缀规则做预处理，建立一张好后缀表int* MakeShift(char* ptrn,int pLen){ //为好后缀表申请pLen个int的空间 int *shift = (int*)malloc(pLen*sizeof(int)); int *sptr = shift + pLen - 1;//方便给好后缀表进行赋值的指标 char *pptr = ptrn + pLen - 1;//记录好后缀表边界位置的指标 char c; if(shift == NULL) { fprintf(stderr,"malloc failed!"); return 0; } c = *(ptrn + pLen - 1);//保存模式串中最后一个字符，因为要反复用到它 *sptr = 1;//以最后一个字符为边界时，确定移动1的距离 pptr--;//边界移动到倒数第二个字符 while(sptr-- != shift)//该最外层循环完成给好后缀表中每一个单元进行赋值的工作 { char *p1 = ptrn + pLen - 2, *p2,*p3; //该do...while循环完成以当前pptr所指的字符为边界时，要移动的距离 do{ while(p1 >= ptrn && *p1-- != c);//该空循环，寻找与最后一个字符c匹配的字符所指向的位置 p2 = ptrn + pLen - 2; p3 = p1; while(p3 >= ptrn && *p3-- == *p2-- && p2 >= pptr);//该空循环，判断在边界内字符匹配到了什么位置 }while(p3 >= ptrn && p2 >= pptr); *sptr = shift + pLen - sptr + p2 - p3;//保存好后缀表中，以pptr所在字符为边界时，要移动的位置 pptr--;//边界继续向前移动 } return shift;}
3.2
//删除子串的程序代码#include#include //#include #include //顺序串的结构类型定义#define maxsize 256typedef struct{ char str[maxsize]; int length;}seqstring;void strPut(seqstring*);void strDelete(seqstring*,int,int);//void main()int main(){ seqstring*S; int pos,len; S=(seqstring*)malloc(sizeof(seqstring)); printf("输入串：");// gets(S->str); scanf("%s",S->str); S->length=strlen(S->str); strPut(S); printf("删除的开始位置:");scanf("%d",&pos); printf("删除的字符个数:");scanf("%d",&len); strDelete(S,pos,len); strPut(S); return 0;}//输出串void strPut(seqstring*S){ int i; for(i=0;i length;i++) printf("%c",S->str[i]); printf("\n"); printf("Length:%d\n",S->length);}//添加删除子串算法void strDelete(seqstring*S,int pos,int len){ int i; if(pos < 0 || len < 0 || pos+len-1 > S->length) { printf("删除位置不正确\n"); } else { for(i = pos+len;i <= S->length-1;i++) { S->str[i-len] = S->str[i]; } S->length = S->length -len;//修改串S的长度 }}