C语言 在链式结构体的字符串中使用KMP算法
/*字符串*/#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
typedef char DataType;
typedef struct Char
{
DataType data;
struct Char *prior, *next;
}Char;
typedef struct Str
{
struct Char *C;
}Str;
void StrInit(Str *S);
void StrCreate(Str *S, char* CH, int len);
Str StrAssign(Str *S, Str *T);
int StrLength(Str *S);
Str StrCat (Str *S, Str *T);
Str StrSub (Str *S, int i, int len);
int StrCmp (Str *S, Str *T);
Str *GetNext(Str *T);
int StrIndex(Str *S, Str *T);
Str StrInsert(Str *S, Str *T, int i);
Str StrDelete (Str *S, int i, int len);
int StrPrint(Str *S);
int main()
{
Str S, T;
char A[] = "ababccca", B[] = "abc";
int i, lenA, lenB;
lenA = sizeof(A)-1;
lenB = sizeof(B)-1;
StrInit(&S);
StrInit(&T);
StrCreate(&S, A, lenA);
if(StrPrint(&S))
printf("打印完毕！\n");
else
printf("字符串为空！\n");
printf("Length of S: %d\n",StrLength(&S));
printf("Length of T: %d\n",StrLength(&T));
StrCreate(&T, B, lenB);
S = StrAssign(&S, &T);
if(StrPrint(&S))
printf("打印完毕！\n");
else
printf("字符串为空！\n");
printf("Length of S: %d\n",StrLength(&S));
printf("Length of T: %d\n",StrLength(&T));
StrCreate(&S, A, lenA);
if(StrPrint(&S))
printf("打印完毕！\n");
else
printf("字符串为空！\n");
printf("Length of S: %d\n",StrLength(&S));
printf("Length of T: %d\n",StrLength(&T));
S = StrCat(&S,&T);
if(StrPrint(&S))
printf("打印完毕！\n");
else
printf("字符串为空！\n");
printf("Length of S: %d\n",StrLength(&S));
printf("Length of T: %d\n",StrLength(&T));
T = StrSub(&S, 2, 11);
printf("从主串S第二个字符开始截取到结束后的子串T：\n");
if(StrPrint(&T))
printf("打印完毕！\n");
else
printf("字符串为空！\n");
printf("Length of S: %d\n",StrLength(&S));
printf("Length of T: %d\n",StrLength(&T));
printf("主串S与子串T比较：\n");
if(StrCmp(&S, &T) == -1)
printf("S < T ! \n");
else if(StrCmp(&S, &T))
printf("S > T ! \n");
else
printf("S = T ! \n");
T = StrSub(&S, 9, 3);
printf("截取主串S后三个字符后的子串T\n");
if(StrPrint(&T))
printf("打印完毕！\n");
else
printf("字符串为空！\n");
if(i = StrIndex(&S, &T))
printf("子串T在主串S中首次出现的位置为： %d\n", i+1);
else
printf("主串S中无子串T\n");
S = StrInsert(&S, &T, i);
printf("主串S在第 3 个位置插入子串T后的数据为：\n");
if(StrPrint(&S))
printf("打印完毕！\n");
else
printf("字符串为空！\n");
S = StrDelete(&S, 8, 3);
printf("主串S第 8 个位置往后删除 3 个数据后为：\n");
if(StrPrint(&S))
printf("打印完毕！\n");
else
printf("字符串为空！\n");
return 0;
}
void StrInit(Str *S) //字符串头初始化
{
Char *SC = (Char *)malloc(sizeof(Char));
SC->next = SC->prior = NULL;
S->C = SC;
}
void StrCreate(Str *S, char* CH, int len) //生成字符串
{
if(len == 0)
{
printf("error! the length is 0!");
return;
}
int count = 0;
Char *p = NULL, *q = NULL;
p = S->C->next;
while(p != NULL)
{
q = p;
p = p->next;
free(q);
}
p = S->C;
while(count < len)
{
Char *s = (Char *)malloc(sizeof(Char));
s->data = CH;
p->next = s;
s->next = NULL;
s->prior = p;
p = p->next;
}
}
Str StrAssign(Str *S, Str *T) // make S to T.
{
Char *p, *p2, *q;
p = S->C;
p2 = p->next;
q = T->C->next;
while(q != NULL)
{
Char *s = (Char *)malloc(sizeof(Char));
s->data = q->data;
s->next = NULL;
s->prior = p;
p->next = s;
p = p->next;
q = q->next;
}
while(p2 != NULL)
{
p = p2;
p2 = p2->next;
free(p);
}
return *S;
}
int StrLength(Str *S) //get length of String.
{
int i = 0;
Char *p = NULL;
p = S->C; //point at the first data area.
while(p->next != NULL)
{
p = p->next;
i++;
}
return i;
}
Str StrCat (Str *S, Str *T)//catch T to S;
{
Char *p = NULL, *q = NULL;
p = S->C;
q = T->C;
while(p->next != NULL)
p = p->next;
p->next = q->next;
if(q->next != NULL)
q->next->prior = p;
return *S;
}
Str StrSub (Str *S, int i, int len)
{
int count = 0;
Str ST, *T;
StrInit(&ST);
Char *p = NULL, *q = NULL;
T = &ST;
p = S->C;
q = T->C;
while(count < i && p->next != NULL)
{
count++;
p = p->next;
}
count = 0;
while(count < len && p != NULL)
{
count++;
Char *s = (Char *)malloc(sizeof(Char));
s->data = p->data;
s->next = NULL;
s->prior = q;
q->next = s;
q = q->next;
p = p->next;
}
return ST;
}
int StrCmp (Str *S, Str *T)
{
Char *p = NULL, *q = NULL;
p = S->C->next;
q = T->C->next;
while(p != NULL && q != NULL)
{
if(p->data > q->data) return 1;
else if (p->data < q->data) return -1;
p = p->next;
q = q->next;
}
if(p != NULL && q == NULL) return 1;
else if(p == NULL && q != NULL) return -1;
return 0;
}
Str *GetNext(Str *T) //方法①：将T赋值给字符数组 其余代码照原 方法② 找到取代利用next[]记录位置的方法
{
Str *Next, Next1;//记录： 将匹配到的结点 的下一结点 通过next连接起来， 再取的该结点，即存储结点的前驱。
StrInit(&Next1);//结点数为T的结点数-1
Next = &Next1;
Char *p, *q, *kp, *kq;
p = T->C;
q = p->next;
kp = Next->C;
kp->prior = T->C;
while(q != NULL)
{
if(p == T->C || p->data == q->data)
{
p = p->next;
q = q->next;
Char *s = (Char *)malloc(sizeof(Char));
s->prior = p;
s->next = NULL;
kp->next = s;
kp = kp->next;
}
else
{
if(p->prior != NULL)
p = p->prior;
}
}
return Next;
}
int StrIndex(Str *S, Str *T) //基于KMP算法的子串查找
{
if(StrLength(S)<StrLength(T))
{
printf("主串长度小于子串长度！");
return 0;
}
Str *Next;
Next = GetNext(T);
Char *p, *q, *Np, *Nq, *lastp1, *lastp2; //lastp1 p2,p1 用于记录最后一次不同的主串结点， p2 用于记录最后一次因不同而跳语句跳到相同的结点。
int count = 1, i = 0, k = 0, op = 0;;
p = S->C;
q = T->C;
lastp1 = p;
lastp2 = p->next;
Np = Next->C;
Nq = Next->C;
while(q != NULL)
{
if(q == T->C || p->data == q->data)
{
p = p->next;
q = q->next;
if(i++)
{
Nq = Np;
if(Np->next != NULL)
Np = Np->next;
}
k++;
}
else
{
q = Np->prior;
if(Np != Nq)
Np = Nq;
lastp1 = p;
if(q == T->C->next && p->data != q->data)
{
Np = Nq = Next->C;
q = T->C;
i = 0;
}
if(p->data == q->data)
lastp2 = p;
count = k;
}
if(p == NULL && q != NULL)
return 0;
}
if(lastp1 == lastp2)
count--;
return count;
}
Str StrInsert(Str *S, Str *T, int i)
{
if(StrLength(S) < i)
{
printf("下溢错误！\n");
return *S;
}
Char *ps, *qs, *pt, *qt;
int count = 0;
ps = S->C;
pt = T->C->next;
while(count < i && ps != NULL)
{
count++;
ps = ps->next;
}
qs = ps->next;
while(pt != NULL)
{
Char *s = (Char *)malloc(sizeof(Char));
s->data = pt->data;
s->next = NULL;
s->prior = ps;
ps->next = s;
ps = ps->next;
pt = pt->next;
}
ps->next = qs;
if(qs != NULL)
qs->prior = ps;
return *S;
}
Str StrDelete (Str *S, int i, int len)
{
if(StrLength(S)<i)
{
printf("下溢错误! \n");
return *S;
}
Char *p, *q;
int count = 0;
p = S->C;
while(count < i && p != NULL)
{
p = p->next;
count++;
}
q = p;
count = 1;
while(count < len && p != NULL)
{
p = p->next;
count++;
}
if(p->next != NULL)
p->next->prior = q->prior;
q->prior->next = p->next;
q->prior = NULL;
p->next = NULL;
while(q != NULL)
{
p = q;
q = q->next;
free(p);
}
return *S;
}
int StrPrint(Str *S)
{
Char *p;
p = S->C->next;
if(p == NULL)
return 0;
while(p != NULL)
{
printf(" %c \n",p->data);
p = p->next;
}
return 1;
}
看到没多少关于KMP算法相关的帖子，相关的也只是直接字符数组。但是在我C语言数据结构的课本里似乎要求的是要将字符存进链式结构体的字符串。然后就自己学习套用下该算法，用于我自己敲的这个字符串里面，目前还没发现什么毛病。 其实今天已经在其他的论坛发过了，不过没什么阅读量，没大佬指出问题。发这希望有大佬帮我看看
页:
[1]