‘壹’ 利用c语言中提供的串的基本操作编写从S串中删除所有和串T相同的字串的算法。先谢过啦！
#include<stdio.h>
#include<string.h>
int main()
{
char s[100];
char t[100];
int i=0, j=0, m=0,n=0,k;
gets(s);
gets(t);
m=strlen(s);
n=strlen(t);
for (i=0;i<m;i++)
{
for(j=0;j<n;j++)
if(s[i]==t[j])
for(k=i;k<=m;k++)
s[k]=s[k+1];
}
puts(s);
return 0;
}
已运行过……通过！
‘贰’ 串模式匹配算法
# include <string.h> # include <stdio.h> # include <stdlib.h> # define OK 1 # define ERROR 0 typedef int Status; //串的定长顺序存储结构 # define MAX_STR_LEN 40 typedef char SString[MAX_STR_LEN + 1];//0号单元存放串的长度 Status StrAssign(SString T,char * chars)//生成一个其值等于chars的串T { int i; if (strlen(chars) > MAX_STR_LEN) { return ERROR; } else { T[0] = strlen(chars); for (i=1; i<=T[0]; ++i) { T[i] = * (chars + i - 1); } return OK; } } //返回串S的元素的个数 int StrLength(SString S) { return S[0]; } //用Sub返回串S的自第pos个字符起长度为len的子串 Status SubString(SString Sub,SString S,int pos,int len) { int i; if (pos<1 || pos>S[0] || len<0 || len>S[0]-pos+1) { return ERROR; } for (i=1; i<=len; ++i) { Sub[i] = S[pos+i-1]; } Sub[0] = len; return OK; } //输出字符串T void StrPrint(SString T) { int i; for (i=1; i<=T[0]; ++i) { printf("%c ",T[i]); } printf("\n"); } //求模式串T的next函数值并存入数组next void get_next(SString T,int next[]) { int i = 1,j = 0; next[1] = 0; while (i < T[0]) { if (j==0 || T[i]==T[j]) { ++i; ++j; next[i] = j; } else { j = next[j]; } } } //求模式串T的next函数修正值并存入数组nextval void get_nextval(SString T,int nextval[]) { int i = 1,j = 0; nextval[1] = 0; while (i < T[0]) { if (j==0 || T[i]==T[j]) { ++i; ++j; if (T[i] != T[j]) { nextval[i] = j; } else { nextval[i] = nextval[j]; } } else { j = nextval[j]; } } } //利用模式串T的next函数求T在主串S中第pos字符之后的位置的KMP算法 //1=<pos=<StrLength(S) int Index_KMP(SString S,SString T,int pos,int next[]) { int i = pos,j = 1; while (i<=S[0] && j<=T[0]) { if (j==0 || S[i]==T[j]) { ++i; ++j; } else { j = next[j]; } } if (j > T[0]) { return i - T[0]; } else { return 0; } } int main(void) { int i,* p; SString s1,s2; StrAssign(s1,"aaabaaaab"); printf("主串为："); StrPrint(s1); StrAssign(s2,"aaaab"); printf("子串为："); StrPrint(s2); p = (int *)malloc((StrLength(s2) + 1) * sizeof(int)); get_next(s2,p); printf("子串的next的数组为："); for (i=1; i<=StrLength(s2); ++i) { printf("%d ",* (p+i)); } printf("\n"); i = Index_KMP(s1,s2,1,p); if (i) { printf("主串和子串在第%d个字符处首次匹配\n",i); } else { printf("主串和子串匹配不成功\n"); } get_nextval(s2,p); printf("子串的nextval数组为："); for (i=1; i<=StrLength(s2); ++i) { printf("%d ",* (p+i)); } printf("\n"); printf("主串和子串在第%d个字符处首次匹配\n",Index_KMP(s1,s2,1,p)); printf("求串s1的从第5个字符起长度为5的子串s2:\n"); SubString(s2,s1,5,5); printf("串s2为:"); StrPrint(s2); return 0; } /* 在vc++6.0中的输出结果： ------------------------ 主串为：a a a b a a a a b 子串为：a a a a b 子串的next的数组为：0 1 2 3 4 主串和子串在第5个字符处首次匹配 子串的nextval数组为：0 0 0 0 4 主串和子串在第5个字符处首次匹配 求串s1的从第5个字符起长度为5的子串s2: 串s2为:a a a a b Press any key to continue ------------------------------ */
‘叁’ 关于数据结构串的简单操作
这是串的定义而不是使用。系统（比如C/C++）在对定义的String类型进行实例化或者说定义时候，其最大长度是maxlen，这是系统已定义的，意思是长度不能超过maxlen，超过则丢弃（或其他处理），而len则是当前穿的长度，就是第一个字符到最后字符（\0之前的字符）的长度；
比如说string s=“123456”；这里系统在定义是就把len=6；使用到串的长度时就是len=6
‘肆’ 数据结构串的基本操作及算法
乃说的是字符串吧？
简单的字符串的操作一般都是用暴力算法的
剪切，粘贴，替换什么的都是开个新的缓冲区往里写
查找可以用KMP算法
高级点的么，字符串用块状链表来存
对应的剪切，粘贴，替换的性能能够有所提升
查找依然推荐KMP算法。。。
‘伍’ 数据结构关于串的KMP算法的理解高手请进
KMP 算法是一种字符串的模式匹配算法，参看严蔚敏数据结构一书，里面讲的很清楚。
基本的字符串匹配算法是将被匹配的字符串S和模式串T 逐个字符进行比较。例如:S中有10个字符，T中有5个字符。S串初始的匹配位置为3.则从S中的第3个字符与T中的第一个字符匹配，若相同则S的第4个字符与T中的第2个字符匹配。直到匹配成功或者出现失配字符。当出现失配情况下，移动标识S中当前进行比较的字符指针，会退到第4个字符处。然后，重复这一过程。简单说，基本的字符匹配算法是通过移动被匹配的字符串S，进行比较字符的指针位置来完成字符匹配的。
而KMP算法刚好相反，在整个匹配过程中S中当前比较字符的指针并不发生回退现象，当出现S中的字符与T中的字符失配的时候。通过改变T的当前比较字符位置的指针来确定当前S中的字符该与T中哪个字符进行比较。简单说，通过模式字符串T的当前比较字符的指针的回退来完成字符匹配。
当理解了KMP算法通过改变T的当前比较字符位置的指针来完成匹配时，接下来要理清的是模式字符串T中的字符指针在失配的情况下是如何移动的。
以严蔚敏数据结构一书中KMP为例，对于模式字符串T，KMP维护了一个对应于T中每个字符弱发生失配情况下，指针回退到哪一位置的数组。当被匹配串S与模式串T发生失配的情况下，T读取数组中相应记录的位置，讲指针回退。如果回退后仍然失配则S的当前比较字符位置指针+1，T串指针回到第一个字符处。
由此可见获取数组中存储的数据是KMP算法的关键，书中的公式看起来有点抽象。数组中的存储指针的位置是根据，模式串T与自身的匹配过程获取的。
实际上是说，模式串T的第一个字符，如果出现失配则不会回退；当前比较位置的字符向前N-1位的子串恰好与T中从第一个字符起止N-1个字符形成的子串相等，且N小于当前位置，满足这些条件的N的最大值即为T当前位置指针回退的位置，然后迭代此过程，直到T本身匹配或回退到第一个字符位置仍不匹配，则当前位置的对应的回退位置指针指向T中的第一个字符所在位置。
讲的还不是很清楚，主要是对比一下基本的字符匹配算法和KMP的不同。一个是通过移动被匹配字符串比较字符的指针来实现匹配，一个是移动模式字符串的当前比较字符的位置指针来实现匹配。对于匹配串字符回退位置这个计算书中已经很清楚，根据算法单步调试一次自然就理解了。
‘陆’ 如何编写实现串的置换操作Replace（&S,T,V)的算法
解：
int Replace(Stringtype &S,Stringtype T,Stringtype V);//将串S中所有子串T替换为
V,并返回置换次数
{
for(n=0,i=1;i<=Strlen(S)-Strlen(T)+1;i++) //注意i的取值范围
if(!StrCompare(SubString(S,i,Strlen(T)),T)) //找到了与T匹配的子串
{ //分别把T的前面和后面部分保存为head和tail
StrAssign(head,SubString(S,1,i-1));
StrAssign(tail,SubString(S,i+Strlen(T),Strlen(S)-i-Strlen(T)+1));
StrAssign(S,Concat(head,V));
StrAssign(S,Concat(S,tail)); //把head,V,tail连接为新串
i+=Strlen(V); //当前指针跳到插入串以后
n++;
n++;
}//if
return n;
}//Replace
分析:i+=Strlen(V);这一句是必需的,也是容易忽略的.如省掉这一句,则在某些情况下, 会引起不希望的后果,虽然在大多数情况下没有影响.请思考:设S='place', T='ace', V='face',则省掉i+=Strlen(V);运行时会出现什么结果?
‘柒’ 数据结构中关于串的操作
子串定位--朴素算法：
#include <stdio.h>
#define N 9
typedef struct node
{ int i,j,v;
}JD;
int trans_sparmat(JD ma[],JD mb[])
{ int col,p,n,t,k;
if(ma[0].v==0)
return(0);
n=ma[0].j;
t=ma[0].v;
mb[0].i=n; mb[0].j=ma[0].i; mb[0].v=t;
k=1;
for(col=1;col<=n;col++)
for(p=1;p<=t;p++)
if(ma[p].j==col)
{ mb[k].i=ma[p].j;
mb[k].j=ma[p].i;
mb[k].v=ma[p].v;
k++;
}
return(1);
}
void main()
{ JD ma[N]={{6,7,8},{1,2,12},{1,3,9},{3,1,-3},
{3,6,14},{4,3,24},{5,2,18},{6,1,15},{6,4,-7}};
JD mb[N];
int i;
trans_sparmat(ma,mb);
for(i=0;i<N;i++)
printf("%d,%d,%d\n",mb[i].i,mb[i].j,mb[i].v);
}
快速算法：
#include <stdio.h>
#define N 9
#define M 8
typedef struct node
{ int i,j,v;
}JD;
int fast_transpos(JD ma[],JD mb[])
{ int n,col,p,k,t;
int num[M],cpot[M];
n=ma[0].j;
t=ma[0].v;
mb[0].i=n; mb[0].j=ma[0].i; mb[0].v=t;
if(t<=0)
return(0);
for(col=0;col<=n;col++)
num[col]=0;
for(p=1;p<=t;p++)
{ k=ma[p].j;
num[k]++;
}
cpot[0]=0; cpot[1]=1;
for(col=2;col<=n;col++)
cpot[col]=cpot[col-1]+num[col-1];
for(p=1;p<=t;p++)
{ col=ma[p].j;
k=cpot[col];
mb[k].i=ma[p].j;
mb[k].j=ma[p].i;
mb[k].v=ma[p].v;
cpot[col]++;
}
return(1);
}
void main()
{ JD ma[N]={{6,7,8},{1,2,12},{1,3,9},{3,1,-3},
{3,6,14},{4,3,24},{5,2,18},{6,1,15},{6,4,-7}};
JD mb[N];
int i;
fast_transpos(ma,mb);
for(i=0;i<N;i++)
printf("%d,%d,%d\n",mb[i].i,mb[i].j,mb[i].v);
}
‘捌’ 数据结构（c语言）一个关于串的算法
帮顶！不好意思语言不同
‘玖’ 编写算法，实现串的基本操作Replace(&S,T,V)。
int Replace(Stringtype &S,Stringtype T,Stringtype V);//将串S中所有子串T替换为V,并返回置换次数 { for(n=0,i=1;i<=Strlen(S)-Strlen(T)+1;i++) //注意i的取值范围 if(!StrCompare(SubString(S,i,Strlen(T)),T)) //找到了与T匹配的子串 { //分别把T的前面和后面部分保存为head和tail StrAssign(head,SubString(S,1,i-1)); StrAssign(tail,SubString(S,i+Strlen(T),Strlen(S)-i-Strlen(T)+1)); StrAssign(S,Concat(head,V)); StrAssign(S,Concat(S,tail)); //把head,V,tail连接为新串 i+=Strlen(V); //当前指针跳到插入串以后 n++; }//if return n; }//Replace
‘拾’ 数据结构串匹配十大经典算法
1。
int Index(SString S,SString T,int pos)
{
//返回子串T在主串S中第pos个字符之后的位置。若不存在，则函数值为0。
//其中，T非空，1〈=pos<=Stringlength(S).
i=pos;j=1;
while(i<=S[0] && j<=T[0])
{
if (S[i]== T[i]) {++i;++j;}
else { i=i-j+2;j=1;}
}
if(j>T[0]) return i-T[0];
else return 0;
}//Index
2。
int Index-KMP(SString S,SString T,int pos)
{
//利用模式串T的next函数值求T在主串S中第pos 个字符之后的位置的KMP算法。其中，T非空，1<=pos<=Stringlength(S)
i=pos;
j=1;
while(i<=S[0] && j<=T[0])
{
if (j==0 || S[i]==T[j]) {++i; ++j;}
else j=next[j];
}
if (j>T[0]) return i-T[0];
else return 0;
//Index}
下面是next函数：
void next(SString S,ing next[])
{
i=1;
next[1]=0;
j=0;
while (i<T[0])
{
if (j==0 || T[i]==T[j]){ ++i; ++j;
next[j]=i;}
else j=next[j];
}
}//next
我现在只有这两个答案。