C语言入门之查找子串问题
Revival_S 人气:0C语言查找子串
查找子串
输入两个字符串s和t,在字符串s中查找子串t,输出起始位置,若不存在,则输出-1.要求自定义函数char* search(char * s,char * t)返回子串t的首地址,若未找到,则返回NULL。试编写相应程序。
#include <stdio.h> #include <stdlib.h> #include <string.h> char* search(char*s,char*t) { int size_t=strlen(t),size_s=strlen(s),T,i,j; char *p=NULL; for(i=0;i<=(size_s-size_t);i++) { p=s+i; T=1; for(j=0;j<size_t;j++) { if(*p!=*(t+j)) { T=0; break; } p++; } if(T==1) break; } if(T==0) return NULL; else return s+i; } int main() { char *s,*t,*p,ch; int count,i; while(1) { printf("请输入字符串s:(直接输入回车退出)\n"); s=(char *)malloc(sizeof(char)); //这里使用动态输入字符串 count=0; //内存足够下可以使字符串字符个数不受数组大小限制 while((ch=getchar())!='\n') { s[count]=ch; count++; s=(char *)realloc(s,(count+1)*sizeof(char)); } s[count]='\0'; if(count==0) //程序结束判断 { printf("程序运行结束!\n"); break; } while(1) //防止子串输入字符个数超过s的循环 { t=(char *)malloc((count+1)*sizeof(char)); printf("输入子串t:\n"); i=0; while((ch=getchar())!='\n') //循环输入字符来计数 { t[i]=ch; i++; } t[i]='\0'; if(i>count) { printf("子串t串长>s串长,请重新"); t=(char *)realloc(t,i*sizeof(char)); //保证内存成功释放,重新分配t内存 free(t); } else break; } if((p=search(s,t))!=NULL) { printf("起始位置:从第%d个字符开始\n",p-s+1); printf("%s\n\n",p); } else printf("-1\n\n"); //题目要求没有找到则输出-1 free(s); free(t); } return 0; }
用了malloc和realloc来实现动态内存分配从而实现输入字符个数不再受数组大小限制(内存足够的话),并且考虑到子串t可能因为超出s的个数而出错做了个容错判断,总体上加了循环实现循环输入并设置了一个退出程序出口。这里所有用动态分配的指针全部都及时释放了,不会因为循环次数的增多而导致内存占用增大。
由于realloc动态分配操作较慢,此程序还可以做优化,比如先开辟10字符的空间,每输入10个字符后再多开辟10字符空间,程序运行速度可以比此程序更快。(但对于这么一点可以忽略不计( ̄▽ ̄)~*)
自定义函数部分使用了从被查找串s第一个字符开始,与t串的字符逐个比较的方法来查找,目前也只能想到了这种查找方法。
结果:
C语言查找子串(采用两个循环查找)
题目来源:浙大PTA
本题要求实现一个字符串查找的简单函数。
函数接口定义
char *search( char *s, char *t );
函数search在字符串s中查找子串t,返回子串t在s中的首地址。若未找到,则返回NULL。
裁判测试程序样例
#include <stdio.h> #define MAXS 30 char *search(char *s, char *t); void ReadString( char s[] ); /* 裁判提供,细节不表 */ int main() { char s[MAXS], t[MAXS], *pos; ReadString(s); ReadString(t); pos = search(s, t); if ( pos != NULL ) printf("%d\n", pos - s); else printf("-1\n"); return 0; } /* 你的代码将被嵌在这里 */
输入样例1:
The C Programming Language
ram
输出样例1:
10
输入样例2:
The C Programming Language
bored
输出样例2:
-1
对于这道题的思路是,在一串
解答
加载全部内容