『壹』 利用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
我現在只有這兩個答案。