数据结构C语言串的基本操作
文档供参考,可复制、编制,期待您的好评与关注! 串的基本操作#include<stdio.h>#include<stdlib.h>#include<conio.h>#define m 100typedef structchar chm;int length;Hstr;void main()Hstr *l,*p,*r;char c,w;int h,j,k;int i=0;l=(Hstr *)malloc(sizeof(Hstr);p=(Hstr *)malloc(sizeof(Hstr);r=(Hstr *)malloc(sizeof(Hstr);l->length=0; p->length=0;r->length=0;printf("请选择相关操作(数字15控制,输入0结束)n");printf("-1.建立串-n");printf("-2.显示串长度-n");printf("-3.生成与原来相同的串-n");printf("-4.串比较-n");printf("-5.串连接-n");printf("-6.返回值-n");scanf("%c",&w);getchar();while(w)switch(w)case '1':printf("请输入字符(#结束):n");scanf("%c",&c);while(c!='#') l->length+;l->chi=c;i+;scanf("%c",&c);printf("串中字符为n");for(i=0;i<l->length;i+)printf("%c",l->chi); printf("n");break;case '2': printf("串长度为%dn",l->length);break;case '3': for(i=0;i<l->length;i+) p->chi=l->chi; p->length=l->length; printf("复制的串中字符为n");for(i=0;i<p->length;i+)printf("%c",p->chi); printf("n"); break;case '4':i=0;printf("请输入要与原串比较的字符串(#结束):n");scanf("%c",&c);while(c!='#') r->length+;r->chi=c;i+;scanf("%c",&c);printf("第二个串中字符为n");for(i=0;i<r->length;i+)printf("%c",r->chi); printf("n"); for(i=0;i<r->length&&i<l->length;i+)if(l->chi!=r->chi)if(l->chi-r->chi)<0)printf("第二个串大"); printf("n");if(l->chi-r->chi)>0)printf("第一个串大"); printf("n");break;if(i=r->length|i=l->length)printf("两个串一样大n"); break;case'5':i=0;printf("请输入要与原串连接的串(#结束)n"); scanf("%c",&c);while(c!='#')r->length+;r->chi=c;i+;scanf("%c",&c);printf("第二个串中字符为n");for(i=0;i<r->length;i+)printf("%c",r->chi); printf("n");for(i=0,j=0;i<r->length;i+,j+)l->chl->length+i=r->chj;l->length=l->length+r->length;printf("连接后第一个串中字符为n");for(i=0;i<l->length;i+)printf("%c",l->chi); printf("n");break;case '6':i=0;printf("请输入要找串的起始位置(第几个字符?)n"); scanf("%d",&h); printf("请输入要找的字符个数n"); scanf("%d",&k); printf("内容为:n"); for(i=0;i<k;i+) printf("%c",l->chh-1); h+; printf("n"); break;getchar();printf("请选择相关操作(数字16控制,输入0结束)n");printf("-1.建立串-n");printf("-2.显示串长度-n");printf("-3.生成与原来相同的串-n");printf("-4.串比较-n");printf("-5.串连接-n");printf("-6.返回值-n"); scanf("%c",&w);getchar();模式匹配#include<stdio.h>#include<stdlib.h>#include<string.h>#define bool int#define true 1#define false 0typedef structchar *ch;int length;HString;bool assign(HString *t,char *chs)int i=0;char *c=chs,*d=chs;while(ci)/c不为空时进入循环i+;/计算字符串常量chs的长度if(!i)t->ch=NULL;t->length=0;elset->ch=(char*)malloc(i*sizeof(char);c=t->ch;if(!t->ch)/如果没有申请到空间return -1;while(*chs)/chs不为空时进入循环*c+=*chs+;t->length=i;return true;bool insert(HString *s,int pos,HString *t)if(pos<0|pos>s->length)return false;if(t->length)/t非空int i=0;if(!(s->ch=(char*)realloc(s->ch,(s->length+t->length)*sizeof(char)exit(-1);for(i=s->length-1;i>=pos;i-)s->chi+t->length=s->chi;for(i=0;i<t->length;i+)s->chpos+i=t->chi;s->length+=t->length;return true;int strLength(HString *s)return s->length;int strCompare(HString *s,HString *t)int i;for(i=0;i<s->length&&i<t->length;i+)if(s->chi!=t->chi)return s->chi - t->chi;return s->length - t->length;bool subString(HString *sub,HString *s,int pos,int len)if(pos<0|pos>=s->length|len<0|len+pos > s->length)return false;if(sub->ch)free(sub->ch);if(!len)sub->ch=NULL;sub->length=0;elseint i=0;sub->ch=(char*)malloc(len*sizeof(char);for(;i<len;i+)sub->chi=s->chpos+i;sub->length=len;return true;void printStr(HString *t)int i=0;while(i+<t->length)putchar(t->chi-1);/printf("第%d个:%cn",i-1,t->chi-1);putchar('n');int indexBF(HString *s,HString *t,int pos)int i=pos,j=0;if(pos<0) return -1;while(i < s->length && j < t->length)if(s->chi=t->chj)i+;j+;elsei=i-j+1;j=0;if(j=t->length)return i-t->length;return -1;int findNext(HString *p,int *next)int i=0,j=-1;next0=-1;while(i<p->length)while(j=-1|i < p->length && p->chi=p->chj)i+;j+;if(p->chi!=p->chj)nexti=j;elsenexti=nextj;j=nextj;return -1;void findNextString(char *p,int *next)int len=strlen(p);int i=0,j=-1;next0=-1;while(i<len)if(j=-1 | pi=pj)i+;j+;if(pi!=pj)nexti=j;elsenexti=nextj;elsej=nextj;void findNext2(HString *p,int *next)int len=p->length;char *c=p->ch;int i=0,j=-1;next0=-1;while(i<p->length)if(j=-1|ci=cj)i+,j+;if(ci!=cj)nexti=j;elsenexti=nextj;elsej=nextj;int kmpString(char *t,char *p,int pos)int i=pos,j=0,plen=strlen(p),tlen=strlen(t);int *next=(int*)malloc(plen*sizeof(int);findNextString(p,next);while(i<tlen && j<plen)if(j=-1 | pj=ti)i+;j+;elsej=nextj;if(j=plen)return i-plen;return -1;int kmp2(HString *t,HString *p,int pos)int *next=(int*)malloc(p->length*sizeof(int);int i=pos,j=0;findNext2(p,next);while(i<t->length&&j<p->length)if(j=-1|p->chj=t->chi)i+,j+;elsej=nextj;if(j=p->length)return i-j;return -1;int kmp(HString *t,HString *p,int pos)int *next=(int*)malloc(p->length*sizeof(int);int i=pos,j=0;findNext(p,next);while(i<=t->length-p->length)while(j=-1|j<p->length && p->chj=t->chi)i+;j+;if(j=p->length)return i-p->length;j=nextj;return -1;int main()HString s1,s2;char a100,b100;int pos;puts("输入主串");gets(a);puts("输入模式串");gets(b);assign(&s1,a);assign(&s2,b);puts("输入匹配起始下标");scanf("%d",&pos);printf("%dn",kmp2(&s1,&s2,pos);system("pause");return 0;13 / 13