[C] 纯文本查看 复制代码
/*字符串*/
#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[count++];
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;
}
发表于 2020-10-30 17:19
