c数据结构—————串

数据结构—————串"/>

c数据结构—————串

1.串相关知识

1.1串的定义：

由零个或多个字符组成的有序序列:’abcdef’

1. 2串的长度:串中字符的数目称为串的长度

1.3空串：’’ ‘ ’空格串

1.4子串：子串包含空串和串本身，

如 ab 的子串：a、b、ab 和一个空子串共 4 个

1.5子串在主串中的位置：

比如：a,b,c,d 为以下的 4 个串
a=‘yang’; b=‘chao’; c=‘yangchao’; d=‘yang caho’;首先他们的长度分别是
4，4，8，9；同时 a,b 都是 c 和 d 的子串。a 在 c 和 d 中的位置都为 0（第一个相同字符的位置）.而 b在 c 中的位置是4，在 d 中的位置是5.
对于串’abcd’来说，他的子串有’a’, ’b’, ’c’, ’d’, ‘ab’, ‘bc’, ‘cd’, ‘abc’, ’bcd’,
‘abcd’,‘’总共 11 个还有’’（空子串）
子串必须是连续的例如ad则不是

1.6、串相等：

只有当两个串的长度相等，并且各个对应位置的字符都相等时才相等。比如：串’abcdef’和’abcdef’就是相等。
但是上面的 4个串 a，b，c，d 彼此都不相等。

2.串的数据结构

2.1结构体的定义

#defineSIZE20
typedefstructStr
{
charelem[SIZE];
intlength;//在串里面没有'\0'一说当前有效数据个数
}Str;

2.2要实现的主要函数

voidStrAssign(Str*s,constchar*chars);//利用字符串初始化串
voidStrCpy(Str*s,Str*t);//将串 t 拷贝到 s
boolIsEmpty(Str*s);//判断串是否为空
intGetLength(Str*s);//求串的长度
voidClear(Str*s);//串清空
//从 s 里面的第 pos 位置提取长度为 len 的子串，放到 sub 里面
boolSubStr(Str*sub,Str*s,intpos,intlen);
boolInsert(Str*s,intpos,Str*t);//在 pos 位置插入 t
//在 s 里面查找子串 sub,从 pos 位置开始的第一个符合的，返回下标
intBF(Str*s,Str*sub,intpos);
boolDeletePos(Str*s,intpos,intlen);//从 pos 位置开始删除 len 个长度
boolDelete(Str*s,intpos,Str*t);//从 pos 位置开始删除子串 t;
boolReplace(Str*s,Str*t,Str*v,intpos);//用 v 替换从 pos 位置开始的第一个 t;
boolReplaceAll(Str*s,Str*t,Str*v);//将所有的 t 替换成 v
voidShow(Str*s);
voidDestroy(Str*s);

2.3实现

#include"Str.h"
#include<stdio.h>
#include<assert.h>
#include<string.h>
void StrAssign(Str*s,const char*chars)//利用字符串初始化串
{assert(s!=NULL &&chars!=NULL );int len =strlen(chars);if(len>SIZE1 ){return;}int i=0;for(int i=0;i<len;i++){s->elem [i]=chars [i];s->length ++;}s->length =len;
}
void StrCpy(Str*s,Str*t)//将串 t 拷贝到 s   ?
{assert(s!=NULL &&t!=NULL );if(s->length <t->length  ){return;}for(int i=0;i<t->length ;i++){s->elem [i+s->length]=t->elem [i];}s->length +=t->length ;
}
bool IsEmpty(Str*s)
{return s->length ==0;
}
int GetLength(Str*s)//求串的长度
{return s->length ;
}
void Clear(Str*s)//串清空
{s->length =0;
}bool SubStr(Str*sub,Str*s,int pos,int len)//从 s 里面的第 pos 位置提取长度为 len 的子串，放到 sub 里面
{if(pos<0 || len<0 || pos+len > s->length  ){return false;}for(int i=0;i<len;i++){sub->elem [i]=s->elem [pos+i];}sub->length =len;return true;
}
bool Insert(Str*s,int pos,Str*t)//在 pos 位置插入 t
{int i=0;int lent=t->length ;int lens=s->length ;if(pos<0||lent+lens>SIZE1  ){return false;}for(int i = lens-1;i >= pos ;i--){s->elem[i+lent] = s->elem[i];}for(int i=0;i<lent;i++){s->elem [pos+i]=t->elem [i];}s->length +=t->length ;return true;
}
//在 s 里面查找子串 sub,从 pos 位置开始的第一个符合的，返回下标
int BF(Str*s,Str*sub,int pos)//朴素算法O(n*m)       n-主串长度m子串长度
{assert(s!=NULL && sub!=NULL );if(pos<0||pos>s->length ){return -1;}int i=pos;int j=0;int lenSub=GetLength (sub);int lens=s->length ;while(i<lens&&j<lenSub )//同时遍历两个串{if(s->elem [i]==sub->elem [j]){i++;j++;}else{i=i-j+1;j=0;}}if(j>=lenSub ){return  i-j ;}else{return -1;}
}bool DeletePos(Str*s,int pos,int len)//从 pos 位置开始删除 len 个长度
{assert(s!=NULL );if(pos<0||pos+len>s->length ){return false;}for(int i=0;i<s->length -len;i++){s->elem [i]=s->elem [i+len];}s->length -=len;return true;
}
bool Delete(Str*s,int pos,Str*t)//从 pos 位置开始删除子串 t;
{assert(s!=NULL );int index=BF (s,t,pos);if(index ==-1){return false;}return DeletePos (s,index ,t->length );
}
bool Replace(Str*s,Str*t,Str*v,int pos)//用 v 替换从 pos 位置开始的第一个 t;
{//查找t//删除t，//插入vint index=BF (s,t,pos);if(index ==-1){return false;}DeletePos(s,index,t->length );return Insert (s,index,v);
}
bool ReplaceAll(Str*s,Str*t,Str*v)//将所有的 t 替换成 v
{while(Replace (s,t,v,0));return true;
}
void Show(Str*s)
{for(int i=0;i<s->length ;i++){printf("%c",s->elem [i]);}printf("\n");
}
int main()
{Str s={{'a'},{0}};Str t={{'a','b','c','d'},{4}};const char *chars="hello";StrAssign(&s,chars);Show(&s);StrCpy(&s,&t);//将串 t 拷贝到 s  s:-===helloabcdShow(&s);SubStr(&t,&s,3,2);//从 s 里面的第 pos 位置提取长度为 len 的子串，放到 sub 里面   t:loShow(&t);Insert(&s,3,&t);//在 pos 位置插入 t   s:helloloabcdShow(&s);//Replace (&s,&t,&m,2);// v 替换从 pos 位置开始的第一个 t//Show(&s);ReplaceAll(&s,&t,&m,2);//int index=BF(&s,&sub,3);//printf("%d\n",index );//Str n;Str s;const char *chars="hello";StrAssign(&s,chars);Show(&s);return 0;}

2.3.1用字符串实现BF算法（朴素算法）

int Bf(char*str,char*sub,int pos)
{int i=pos;int j=0;int lenSub=strlen(sub);int lens=strlen(str) ;assert(str!=NULL && sub!=NULL );if(pos<0||pos>lens){return -1;}while(i<lens&&j<lenSub )//同时遍历两个串{if(str[i]==sub[j]){i++;j++;}else{i=i-j+1;j=0;}}if(j>=lenSub ){return  i-j ;}else{return -1;}
}

2.4 KMP算法

在 s 里面查找子串 sub,从 pos 位置开始的第一个符合的，返回下标。

2.4.1实现源码

void GetNext(char*sub,int *next)
{next[0]=-1;next[1]=0;int j=2;int k=0;int len =strlen(sub);while(j<len){if(k==-1||sub[k]==sub[j-1]){next[j]=k+1;j++;k=k+1;}else{k=next[k];//k连续回退；}}
}
int KMP(char*str,char*sub,int pos)
{int i=pos;int j=0;int lenSub=strlen(sub);int lens=strlen(str) ;int *next=(int*)malloc(lenSub *sizeof(int));GetNext (next,sub);assert(next!=NULL );//assert(str!=NULL && sub!=NULL );while(i<lens&&j<lenSub )//同时遍历两个串{if(j==-1 || str[i]==sub[j]){i++;j++;}else{j=next[j];}}if(j>=lenSub ){return  i-j ;}else{return -1;}
}

2.4.2kmp算法练习

//s1:abc s2:ababcdd 求s2里面有几个s1

void GetNext1(char *sub,int *next)
{int len = strlen(sub);int k = 0;next[0] = -1;next[1] = 0;int i = 2;while(i<=len){if(sub[k] == sub[i-1]|| k==-1){next[i] = k+1;k = k+1;i++;}else {k = next[k];}}
}int KmpCount1(char *str,char *sub,int pos)
{int lens = strlen(str);int lensub = strlen(sub);int i = pos;int j = 0;int count = 0;int *next = (int *)malloc(sizeof(int) *(lensub+1));GetNext1(sub,next);while(i < lens){//如果匹配到此时j处于next[]的下一个位置，//回归到next[j]if(j>=lensub){count++;j = next[j];}if(str[i] == sub[j]||(j==-1)){i++;j++;}else {j = next[j];}}//最后一个正好匹配到则count++if(j>=lensub){count++;}return count;
}

方法二

int KmpCount(char*str,char*sub,int pos)
{int count =0;int m=KMP(str,sub,0);int i=0;int lens=strlen(str);int lensub=strlen(sub);while(i<lens){if(m>=0){count++;m=KMP (str,sub,m+1);}else{i+=1;}}return count;
}
int main()
{char *str="123456abcdefgh";char*sub="abcd";char *str1="ababcabcdabcde";char*str2="abcabcdababcd";char* sub2="ab";printf("%d\n",Bf(str1,sub,3));printf("%d\n",KMP(str1,sub,3));printf("%d\n",KMP(str2,sub2,2));printf("\n");printf("%d\n",KmpCount("ababcabcd","ab",0));//3printf("%d\n",KmpCount("aaab","aa",0));//2printf("%d\n",KmpCount("acccacca","ac",0));//2printf("%d\n",KmpCount("ababcabcd","ab",0));//3printf("%d\n",KmpCount("aaab","aa",0));//2printf("%d\n",KmpCount("acccacca","ac",0));//2printf("\n");printf("%d\n",KmpCount1("ababcabcd","ab",0));//3printf("%d\n",KmpCount1("aaab","aa",0));//2printf("%d\n",KmpCount1("acccacca","ac",0));//2printf("%d\n",KmpCount1("ababcabcd","ab",0));//3printf("%d\n",KmpCount1("aaab","aa",0));//2printf("%d\n",KmpCount1("acccacca","ac",0));//2return 0;}