C语言oj题求解

根据题意：不允许使用现成字符串函数，所以string.h头文件下的所有函数都没有使用。

程序支持任意长度字符串输入，第一个字符串有且只有一个*号。

第一个字符串格式可以是a*b，可以是*a，也可以是a*。

根据题目要求*号至少代表一个字符（不超过字符串2范围）

注意：如果最小匹配或贪婪匹配，匹配成功多个一样长度的字符串，只返回其中一条！

代码的逻辑：

1、将字符串1按*号拆分成2个字符。比如aa*bb，就会拆分才“aa”和“bb”

2、两个拆分的子串分别与字符串2匹配，返回所有满足的位置集合（用结构链表保存）

3、得到的2个位置集合，进行组合，找出满足条件的位置组合，输出对应字符串。

#include#include#includetypedefstructaddress//记录对应位置的结构体{char*sBen;//起始位置char*sEnd;//结束位置structaddress*next;}ASD;ASD*check(char*str1,char*str2);//检查字符是否在字符串中，是返回字符串中对应地址，否返回NULLintstrlenRW(char*str);//自定义计算字符串长度voidprintfASD(ASD*asdHead);voidmeError(void*p);//内存申请失败char**splitStr(char*str);//拆分子字符串，以*号分割，返回分割后的两个字符串组成的二维数组char*input();//输入任意长度字符串voidorderStr(ASD*asdHead,intflag);//将字符串链表，按结束地址大小，升序排列,冒泡排序char*getMinOrMax(ASD*asdHead1,ASD*asdHead2,intflag,char*str2);//获取最小匹配或贪婪匹配,flag=0:最小匹配，flag=1：贪婪匹配,str2:主字符串intmain(){intlen1=0,len2=0;char*str1=NULL,*str2=NULL,**spStrs=NULL;ASD*asdHead1=NULL,*asdHead2=NULL;printf(----用包含*号的字符串1在字符串2中找出最小匹配和贪婪匹配----\n);while(1){str1=NULL,str2=NULL,spStrs=NULL;asdHead1=NULL,asdHead2=NULL;printf(\n请分别输入字符串1及字符串2,每输入一个字符串回车确认：\n);str1=input();if(str1){len1=strlenRW(str1);spStrs=splitStr(str1);if(!spStrs)continue;}elseprintf(字符串1不能为空，本次匹配无效，重新输入\n\n);str2=input();if(str1){len2=strlenRW(str2);}if(len2next){asdHNext=asdHead->next;while(asdHNext->next){if(!flag)boolv=asdHead->next->sEnd>asdHNext->next->sEnd;elseboolv=asdHead->next->sEndnext->sEnd;if(boolv){cSave=asdHead->next->sBen;asdHead->next->sBen=asdHNext->next->sBen;asdHNext->next->sBen=cSave;cSave=asdHead->next->sEnd;asdHead->next->sEnd=asdHNext->next->sEnd;asdHNext->next->sEnd=cSave;}asdHNext=asdHNext->next;}asdHead=asdHead->next;}}char*getMinOrMax(ASD*asdHead1,ASD*asdHead2,intflag,char*str2)//获取最小匹配或贪婪匹配,flag=0:最小匹配，flag=1：贪婪匹配{intlen,i,boolv;char*pBen=NULL,*pEnd=NULL,*rStr=NULL;ASD*asdH2Save=asdHead2,*asdTempMin=NULL,*asdTempMax=NULL;if(!asdHead1)//首字符是*{asdHead1=(ASD*)malloc(sizeof(ASD));asdTempMin=(ASD*)malloc(sizeof(ASD));asdTempMax=(ASD*)malloc(sizeof(ASD));meError(asdHead1),meError(asdTempMin),meError(asdTempMax);asdHead1->next=asdTempMin;asdTempMin->next=asdTempMax;asdTempMax->next=NULL;if(asdHead2->next){orderStr(asdHead2,0);if(asdHead2->next->sBen-1>=str2)asdTempMin->sBen=asdHead2->next->sBen-1;elseasdTempMin->sBen=asdHead2->next->sBen;asdTempMin->sEnd=asdHead2->next->sBen-2;orderStr(asdHead2,1);asdTempMax->sBen=str2;asdTempMax->sEnd=asdHead2->next->sBen-strlenRW(str2);}elsereturnNULL;}if(!asdHead2)//最后一个字符是*{asdHead2=(ASD*)malloc(sizeof(ASD));asdTempMin=(ASD*)malloc(sizeof(ASD));asdTempMax=(ASD*)malloc(sizeof(ASD));meError(asdHead2),meError(asdTempMin),meError(asdTempMax);asdHead2->next=asdTempMin;asdTempMin->next=asdTempMax;asdTempMax->next=NULL;orderStr(asdHead1,1);asdTempMin->sBen=asdHead1->next->sEnd+2;if(*(asdHead1->next->sEnd+1)!=0)asdTempMin->sEnd=asdHead1->next->sEnd+1;elseasdTempMin->sEnd=asdHead1->next->sEnd;orderStr(asdHead1,0);asdTempMax->sBen=asdHead1->next->sEnd+strlenRW(str2);asdTempMax->sEnd=&str2[strlenRW(str2)-1];asdHead2->next=asdTempMin;asdTempMin->next=asdTempMax;}asdH2Save=asdHead2;if(!flag)//最小匹配，*号前数组取最大匹配地址，*号后数组取最小匹配地址orderStr(asdHead1,1),orderStr(asdHead2,0),boolv=strlenRW(str2);else//贪婪匹配，*号前数组取最小匹配地址，*号后数组取最大匹配地址orderStr(asdHead1,0),orderStr(asdHead2,1),boolv=0;while(asdHead1->next){asdHead2=asdH2Save;while(asdHead2->next){if(asdHead2->next->sBen-asdHead1->next->sEnd>=2)//前后之间至少间隔一个字符if((!flag&&asdHead2->next->sBen-asdHead1->next->sEndnext->sBen-asdHead1->next->sEnd>boolv))//间隔字符数满足条件{pBen=asdHead1->next->sBen;pEnd=asdHead2->next->sEnd;boolv=asdHead2->next->sBen-asdHead1->next->sEnd;}asdHead2=asdHead2->next;}asdHead1=asdHead1->next;}len=pEnd-pBen+1;rStr=(char*)malloc(sizeof(char)*(len+1));meError(rStr);i=0;while(pBennext){sBen=asdHead->next->sBen;sEnd=asdHead->next->sEnd;while(sBennext;}printf(\n);}intstrlenRW(char*str)//自定义计算字符串长度{intlen=0;while(*str){len++;str++;}returnlen;}ASD*check(char*str1,char*str2)//检查子字符str1在字符串str2中位置，返回所有位置的集合,集合中每个对应地址是按照升序排列的{ASD*asdHead=(ASD*)malloc(sizeof(ASD)),*asdTail=NULL,*asdNew=NULL;char*s1Save=str1,*s2Save=str2;meError(asdHead);asdHead->next=NULL;asdNew=(ASD*)malloc(sizeof(ASD));meError(asdNew);asdNew->next=NULL;asdNew->sBen=NULL;asdNew->sEnd=NULL;while(*str2){if(*s1Save==*s2Save&&*s1Save!=0)//str1当前位与str2当前位相等，记录起始位置{if(!asdNew->sBen)asdNew->sBen=s2Save;s1Save++;s2Save++;}elseif(*s1Save!=*s2Save&&*s1Save!=0)//str1当前位与str2当前位不相等，str1重头开始取位,继续往str2下一位匹配，清空起始和结束地址指针sBen、sEnd{s1Save=str1;s2Save=++str2;asdNew->sBen=NULL;asdNew->sEnd=NULL;}elseif(*s1Save==0)//一次匹配完成,str1重头开始取位,继续往下找匹配{asdNew->sEnd=s2Save-1;if(asdHead->next==NULL)asdHead->next=asdNew;elseasdTail->next=asdNew;asdTail=asdNew;asdNew=(ASD*)malloc(sizeof(ASD));meError(asdNew);asdNew->next=NULL;asdNew->sBen=NULL;asdNew->sEnd=NULL;s1Save=str1;s2Save=++str2;}}free(asdNew);returnasdHead;}voidmeError(void*p)//内存申请失败{if(p==NULL){printf(异常：内存申请失败！回车结束程序！\n);while(getch()!='\r');exit(0);}}