数据结构 串(顺序存储)的基本操作
【摘要】 #include <stdio.h> #define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#define MAXSTRLEN 255 typedef unsigned char String[MAXSTRLEN+1]; int StrAssign(String &S, char *str){ i...
-
#include <stdio.h>
-
-
#define OK 1
-
#define ERROR 0
-
#define TRUE 1
-
#define FALSE 0
-
#define MAXSTRLEN 255
-
-
typedef unsigned char String[MAXSTRLEN+1];
-
-
-
int StrAssign(String &S, char *str)
-
{
-
int i,len;
-
char *p;
-
for (len = 0, p = str; *p != '\0'; len++,p++);
-
if (len == 0)
-
{
-
S[0] = 0;
-
}
-
else
-
{
-
for (i=0; i<len;i++)
-
{
-
S[i+1] = str[i];
-
}
-
S[0] = len;
-
}
-
return OK;
-
}
-
-
void StrCopy(String &S,String T)
-
{
-
if (T[0] == 0)
-
{
-
S[0] = 0;
-
}
-
else
-
{
-
int i;
-
for (i=1;i<=T[0]; i++)
-
{
-
S[i] = T[i];
-
}
-
S[0] = T[0];
-
}
-
}
-
-
int StrEmpty(String T)
-
{
-
if (T[0] == 0)
-
{
-
return OK;
-
}
-
return ERROR;
-
}
-
-
int StrLength(String T)
-
{
-
return T[0];
-
}
-
-
void ClearString(String &T)
-
{
-
T[0] = 0;
-
}
-
-
int StrCompare(String S,String T)
-
{
-
int i;
-
for (i=1; i<=S[0] && i<=T[0]; ++i)
-
{
-
if (S[i] != T[i])
-
{
-
return S[i] - T[i];
-
}
-
}
-
return S[0] - T[0];
-
}
-
-
int Concat(String &T,String S1,String S2)
-
{
-
int uncut;
-
int i,j;
-
if (S1[0] + S2[0] <= MAXSTRLEN)
-
{
-
for (i=1; i<=S1[0]; i++)
-
{
-
T[i] = S1[i];
-
}
-
for (j=1;j<=S2[0];j++)
-
{
-
T[i+j-1] = S2[j];
-
}
-
T[0] = S1[0] + S2[0];
-
uncut = TRUE;
-
}
-
else if (S1[0] < MAXSTRLEN)
-
{
-
for (i=1; i<=S1[0]; i++)
-
{
-
T[i] = S1[i];
-
}
-
for (j=1; j<=MAXSTRLEN - S1[0]; j++)
-
{
-
T[i+j-1] = S2[j];
-
}
-
T[0] = MAXSTRLEN;
-
uncut = FALSE;
-
}
-
else
-
{
-
for (i=0; i<=MAXSTRLEN; i++)
-
{
-
T[i] = S1[i];
-
}
-
uncut = FALSE;
-
}
-
return uncut;
-
}
-
-
-
-
-
-
-
void Print_String(String S)
-
{
-
if (S[0] == 0)
-
{
-
return;
-
}
-
else
-
{
-
int i;
-
for (i=1; i<=S[0]; i++)
-
{
-
printf("%c",S[i]);
-
}
-
printf("\n");
-
}
-
}
-
-
int SubString(String &Sub, String S, int pos, int len)
-
{
-
int i;
-
if (pos < 1 || pos > S[0] || len < 0 || len > S[0] - pos + 1)
-
{
-
return ERROR;
-
}
-
if (!len)
-
{
-
Sub[0] = 0;
-
}
-
else
-
{
-
for (i=1; i<=len;i++)
-
{
-
Sub[i] = S[pos+i-1];
-
}
-
Sub[0] = len;
-
}
-
return OK;
-
}
-
-
-
int Index(String S,String T, int pos)
-
{
-
-
if (pos > 0 && pos <= S[0] - T[0] + 1)
-
{
-
int n = S[0];
-
int m = T[0];
-
int i = pos;
-
String sub;
-
while (i<= n-m+1)
-
{
-
SubString(sub,S, i,m);
-
if (StrCompare(sub, T) != 0)
-
{
-
++i;
-
}
-
else
-
{
-
return i;
-
}
-
}
-
}
-
return 0;
-
}
-
-
void get_next(String T, int next[])
-
{
-
int i = 1;
-
int 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];
-
}
-
}
-
}
-
-
void get_nextval(String T, int nextval[])
-
{
-
int i = 1;
-
int 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];
-
}
-
}
-
}
-
-
int Index_KMP(String S, String T, int pos)
-
{
-
int i = pos;
-
int j = 1;
-
int next[255];
-
get_next(T,next);
-
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 Index_KMP2(String S, String T, int pos)
-
{
-
int i = pos;
-
int j = 1;
-
int nextval[255];
-
get_nextval(T,nextval);
-
while (i<=S[0] && j <= T[0])
-
{
-
if (j == 0 || S[i] == T[j])
-
{
-
++i;
-
++j;
-
}
-
else
-
{
-
j = nextval[j];
-
}
-
}
-
if (j>T[0])
-
{
-
return i-T[0];
-
}
-
else
-
return 0;
-
}
-
-
int main()
-
{
-
String T,S,H;
-
char str[1000];
-
gets(str);
-
StrAssign(T,str);
-
Print_String(T);
-
gets(str);
-
StrAssign(S,str);
-
Print_String(S);
-
StrCopy(T,S);
-
Print_String(T);
-
Concat(H,S,T);
-
Print_String(H);
-
SubString(S,T,5,3);
-
Print_String(S);
-
printf("%d\n",Index(T,S,1));
-
printf("%d\n",Index_KMP(T,S,1));
-
printf("%d\n",Index_KMP2(T,S,1));
-
-
-
return 0;
-
}
文章来源: blog.csdn.net，作者：悦来客栈的老板，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/qq523176585/article/details/17249169
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）