- 算法1： 串采用定长顺序存储结构(由c4-1.h定义)的基本操作(12个)
#define DestroyString ClearString // DestroyString()与ClearString()作用相同 #define InitString ClearString // InitString()与ClearString()作用相同 Status StrAssign(SString T,char* chars) { // 生成一个其值等于chars的串T int i; if(strlen(chars)>MAX_STR_LEN) // chars的长度大于最大串长 return ERROR; else { T[0]=strlen(chars); // 0号单元存放串的长度 for(i=1;i<=T[0];i++) // 从1号单元起复制串的内容 T[i]=*(chars+i-1); return OK; } } void StrCopy(SString T,SString S) { // 由串S复制得串T int i; for(i=0;i<=S[0];i++) T[i]=S[i]; } Status StrEmpty(SString S) { // 若S为空串，则返回TRUE；否则返回FALSE if(S[0]==0) return TRUE; else return FALSE; } int StrCompare(SString S,SString T) { // 初始条件：串S和串T存在 // 操作结果：若S>T，则返回值>0；若S=T，则返回值=0；若S<T，则返回值<0 int i; for(i=1;i<=S[0]&&i<=T[0];++i) if(S[i]!=T[i]) return S[i]-T[i]; return S[0]-T[0]; } int StrLength(SString S) { // 返回串S的元素个数 return S[0]; } void ClearString(SString S) { // 初始条件：串S存在。操作结果：将S清为空串 S[0]=0; // 令串长为零 } Status Concat(SString T,SString S1,SString S2) // 算法4.2修改 { // 用T返回S1和S2连接而成的新串。若未截断，则返回TRUE；否则返回FALSE int i; if(S1[0]+S2[0]<=MAX_STR_LEN) // 未截断 { for(i=1;i<=S1[0];i++) T[i]=S1[i]; for(i=1;i<=S2[0];i++) T[S1[0]+i]=S2[i]; T[0]=S1[0]+S2[0]; return TRUE; } else // 截断S2 { for(i=1;i<=S1[0];i++) T[i]=S1[i]; for(i=1;i<=MAX_STR_LEN-S1[0];i++) // 到串长为止 T[S1[0]+i]=S2[i]; T[0]=MAX_STR_LEN; return FALSE; } } Status SubString(SString Sub,SString S,int pos,int len) { // 用Sub返回串S的自第pos个字符起长度为len的子串。算法4.3 int i; if(pos<1||pos>S[0]||len<0||len>S[0]-pos+1) // pos和len的值超出范围 return ERROR; for(i=1;i<=len;i++) Sub[i]=S[pos+i-1]; Sub[0]=len; return OK; } int Index1(SString S,SString T,int pos) { // 返回子串T在主串S中第pos个字符之后的位置。若不存在，则函数值为0。 // 其中，T非空，1≤pos≤StrLength(S)。算法4.5 int i,j; // 指示主串S和子串T的当前比较字符 if(1<=pos&&pos<=S[0]) // pos的范围合适 { i=pos; // 从主串S的第pos个字符开始和子串T的第1个字符比较 j=1; while(i<=S[0]&&j<=T[0]) if(S[i]==T[j]) // 当前两字符相等 { ++i; // 继续比较后继字符 ++j; } else // 当前两字符不相等 { i=i-j+2; // 两指针后退重新开始匹配 j=1; } if(j>T[0]) // 主串S中存在子串T return i-T[0]; else // 主串S中不存在子串T return 0; } else // pos的范围不合适 return 0; } Status StrInsert(SString S,int pos,SString T) { // 初始条件：串S和T存在，1≤pos≤StrLength(S)+1 // 操作结果：在串S的第pos个字符之前插入串T。完全插入返回TRUE，部分插入返回FALSE int i; if(pos<1||pos>S[0]+1) // pos超出范围 return ERROR; if(S[0]+T[0]<=MAX_STR_LEN) // 完全插入 { for(i=S[0];i>=pos;i--) // 移动串S中位于pos之后的字符 S[i+T[0]]=S[i]; // 串S向后移串T的长度，为插入串T准备空间 for(i=pos;i<pos+T[0];i++) // 在串S中插入串T S[i]=T[i-pos+1]; S[0]+=T[0]; // 更新串S的长度 return TRUE; // 完全插入的标记 } else // 部分插入 { for(i=MAX_STR_LEN;i>=pos+T[0];i--) // 移动串S中位于pos之后且移后仍在串内的字符 S[i]=S[i-T[0]]; for(i=pos;i<pos+T[0]&&i<=MAX_STR_LEN;i++) // 在串S中插入串T(也可能是部分插入) S[i]=T[i-pos+1]; S[0]=MAX_STR_LEN; // 串S的长度为串的最大长度 return FALSE; // 部分插入的标记 } } Status StrDelete(SString S,int pos,int len) { // 初始条件：串S存在，1≤pos≤StrLength(S)-len+1 // 操作结果：从串S中删除自第pos个字符起长度为len的子串 int i; if(pos<1||pos>S[0]-len+1||len<0) // pos和len的值超出范围 return ERROR; // 删除不成功的标记 for(i=pos+len;i<=S[0];i++) // 对于删除的子串之后的所有字符 S[i-len]=S[i]; // 向前移动删除子串的长度 S[0]-=len; // 更新串S的长度 return OK; // 删除成功的标记 } void StrPRint(SString S) { // 输出字符串S。新增 int i; for(i=1;i<=S[0];i++) printf("%c",S[i]); printf("/n"); }- 算法2： 串采用堆分配存储结构(由c4-2.h定义)的基本操作(12个)
#define DestroyString ClearString // DestroyString()与ClearString()作用相同 void InitString(HString &S) { // 初始化(产生空串)字符串S。新增 S.length=0; S.ch=NULL; } void ClearString(HString &S) { // 将S清为空串。在教科书第77页 free(S.ch); // 释放S.ch所指空间 InitString(S); // 初始化串S } void StrAssign(HString &T,char* chars) { // 生成一个其值等于串常量chars的串T。在教科书第76页 int i,j; if(T.ch) // T指向某存储单元 free(T.ch); // 释放T原有存储空间 i=strlen(chars); // 求chars的长度i if(!i) // chars的长度为0 InitString(T); // 生成空串 else // chars的长度不为0 { T.ch=(char*)malloc(i*sizeof(char)); // 分配串存储空间 if(!T.ch) // 分配串存储空间失败 exit(OVERFLOW); for(j=0;j<i;j++) // 分配串存储空间成功后，复制串chars[]到串T T.ch[j]=chars[j]; T.length=i; // 更新串T的长度 } } void StrCopy(HString &T,HString S) { // 初始条件：串S存在。操作结果：由串S复制得串T int i; if(T.ch) // 串T不空 free(T.ch); // 释放串T原有存储空间 T.ch=(char*)malloc(S.length*sizeof(char)); // 分配串存储空间 if(!T.ch) // 分配串存储空间失败 exit(OVERFLOW); for(i=0;i<S.length;i++) // 从第1个字符到最后一个字符 T.ch[i]=S.ch[i]; // 逐一复制字符 T.length=S.length; // 复制串长 } Status StrEmpty(HString S) { // 初始条件：串S存在。操作结果：若串S为空，则返回TRUE；否则返回FALSE if(S.length==0&&S.ch==NULL) // 空串标志 return TRUE; else return FALSE; } int StrCompare(HString S,HString T) { // 若串S>串T，则返回值>0；若S=T，则返回值=0；若S<T，则返回值<0。在教科书第77页 int i; for(i=0;i<S.length&&i<T.length;++i) // 在有效范围内 if(S.ch[i]!=T.ch[i]) // 逐一比较字符 return S.ch[i]-T.ch[i]; // 不相等，则返回2字符ASCII码之差 return S.length-T.length; // 在有效范围内，字符相等，但长度不等，返回长度之差 } int StrLength(HString S) { // 返回串S的元素个数，称为串的长度。在教科书第77页 return S.length; } void Concat(HString &T,HString S1,HString S2) { // 用串T返回由串S1和串S2连接而成的新串。在教科书第77页 int i; if(T.ch) // 串T不空 free(T.ch); // 释放串T原有存储空间 T.length=S1.length+S2.length; // 串T的长度=串S1的长度+串S2的长度 T.ch=(char*)malloc(T.length*sizeof(char)); // 分配串T的存储空间 if(!T.ch) // 分配串存储空间失败 exit(OVERFLOW); for(i=0;i<S1.length;i++) // 将串S1的字符逐一复制给串T T.ch[i]=S1.ch[i]; for(i=0;i<S2.length;i++) // 将串S2的字符逐一复制给串T(接在串S1的字符之后) T.ch[S1.length+i]=S2.ch[i]; } Status SubString(HString &Sub,HString S,int pos,int len) { // 用Sub返回串S的第pos个字符起长度为len的子串。 // 其中，1≤pos≤StrLength(S)且0≤len≤StrLength(S)-pos+1。在教科书第77页 int i; if(pos<1||pos>S.length||len<0||len>S.length-pos+1) // pos和len的值超出范围 return ERROR; // 无法用Sub返回子串 if(Sub.ch) // 串Sub不空 free(Sub.ch); // 释放串Sub原有存储空间 if(!len) // 空子串 InitString(Sub); // 初始化串Sub else // 完整子串 { Sub.ch=(char*)malloc(len*sizeof(char)); // 分配串Sub的存储空间 if(!Sub.ch) // 分配串存储空间失败 exit(OVERFLOW); for(i=0;i<=len-1;i++) // 将串S第pos个字符起长度为len的子串的字符逐一复制给串Sub Sub.ch[i]=S.ch[pos-1+i]; Sub.length=len; // 串Sub的长度 } return OK; } Status StrInsert(HString &S,int pos,HString T) // 算法4.4 { // 1≤pos≤StrLength(S)+1。在串S的第pos个字符之前插入串T int i; if(pos<1||pos>S.length+1) // pos不合法 return ERROR; if(T.length) // T非空 { S.ch=(char*)realloc(S.ch,(S.length+T.length)*sizeof(char)); // 重分S存储空间 if(!S.ch) // 重新分配串S的存储空间失败 exit(OVERFLOW); for(i=S.length-1;i>=pos-1;--i) // 为插入T而腾出位置 S.ch[i+T.length]=S.ch[i]; for(i=0;i<T.length;i++) // 插入T S.ch[pos-1+i]=T.ch[i]; S.length+=T.length; // 更新串S的长度 } return OK; } Status StrDelete(HString &S,int pos,int len) { // 从串S中删除第pos个字符起长度为len的子串 int i; if(S.length<pos+len-1) // pos和len的值超出范围 return ERROR; for(i=pos-1;i<=S.length-len;i++) // 将待删除子串之后的字符逐一前移 S.ch[i]=S.ch[i+len]; S.length-=len; // 更新串S的长度 S.ch=(char*)realloc(S.ch,S.length*sizeof(char)); // 重新分配串S的存储空间(减少) return OK; } void StrPrint(HString S) { // 输出字符串S。新增 int i; for(i=0;i<S.length;i++) printf("%c",S.ch[i]); printf("/n"); }- 算法3： 串的模式匹配算法——KMP算法。
#include"c1.h" #include"c4-1.h" // 串的定长顺序存储结构 #include"bo4-1.cpp" // 定长顺序存储结构的基本操作(12个) void get_next(SString T,int next[]) { // 求模式串T的next函数值并存入数组next。算法4.7 int i=1,j=0; next[1]=0; // T的第1个字符与主串“失配”时，主串的下一字符与T的第1个字符比较 while(i<T[0]) // 当T[0]>1时，next[2]=1 if(j==0||T[i]==T[j]) // 初态或两字符相等 { ++i; // 各+1继续向后比较 ++j; next[i]=j; // 主串和T在第i个字符不匹配时，前j-1个字符是匹配的，只须与第j个字符比较 } else // 两字符不等 j=next[j]; // j减小到前面字符相等之处 } void get_nextval(SString T,int nextval[]) { // 求模式串T的next函数修正值并存入数组nextval。算法4.8 int i=1,j=0; nextval[1]=0; // T的第1个字符与主串“失配”，主串的下一字符与T的第1个字符比较 while(i<T[0]) if(j==0||T[i]==T[j]) { ++i; ++j; if(T[i]!=T[j]) // 此处与算法4.7不同 nextval[i]=j; else nextval[i]=nextval[j]; } else j=nextval[j]; // j减小到前面字符相等之处 } int Index_KMP(SString S,SString T,int pos,int next[]) { // 利用模式串T的next数组求T在主串S中第pos个字符之后的位置的KMP算法。 // 其中，T非空，1≤pos≤StrLength(S)。算法4.6 int i=pos,j=1; // 初始位置 while(i<=S[0]&&j<=T[0]) // i和j分别都未超出主串S和模式串T的范围 if(j==0||S[i]==T[j]) // 继续比较后继字符 { ++i; ++j; } else // 模式串向右移动 j=next[j]; if(j>T[0]) // 匹配成功 return i-T[0]; else return 0; } void main() { int i,*p; SString s1,s2; // 以教科书算法4.8之上的数据为例 StrAssign(s1,"aaabaaaab"); // 由"aaabaaaab"生成主串s1 printf("主串为"); StrPrint(s1); // 输出串s1 StrAssign(s2,"aaaab"); // 由"aaaab"生成子串s2 printf("子串为"); StrPrint(s2); // 输出串s2 p=(int*)malloc((StrLength(s2)+1)*sizeof(int)); // 生成s2的next数组，[0]不用 get_next(s2,p); // 利用算法4.7，求得next数组，存于p中 printf("子串的next数组为"); for(i=1;i<=StrLength(s2);i++) printf("%d ",*(p+i)); printf("/n"); i=Index_KMP(s1,s2,1,p); // 利用算法4.6求得串s2在s1中首次匹配的位置i if(i) printf("主串和子串在第%d个字符处首次匹配/n",i); else printf("主串和子串匹配不成功/n"); get_nextval(s2,p); // 利用算法4.8，求得nextval数组，存于p中 printf("子串的nextval数组为"); for(i=1;i<=StrLength(s2);i++) printf("%d ",*(p+i)); printf("/n"); printf("主串和子串在第%d个字符处首次匹配/n",Index_KMP(s1,s2,1,p)); }算法4： 与存储结构无关的两个基本操作。
int Index(String S,String T,int pos) // 算法4.1 { // T为非空串。若主串S中第pos个字符之后存在与T相等的子串， // 则返回第一个这样的子串在S中的位置；否则返回0 int n,m,i; String sub; InitString(sub); // 新增 if(pos>0) { n=StrLength(S); // 主串S的长度 m=StrLength(T); // 模式串T的长度 i=pos; while(i<=n-m+1) // i从串S的pos到倒数第m个 { SubString(sub,S,i,m); // 子串sub是从主串S的第i个字符起，长度为m的子串 if(StrCompare(sub,T)!=0) // 子串sub不等于模式串T ++i; // 继续向后比较 else // 子串sub等于模式串T return i; // 返回模式串T的第1个字符在主串S中的位置 } } return 0; // 主串S中不存在与模式T相等的子串 } Status Replace(String &S,String T,String V) { // 初始条件：串S、T和V存在，串T是非空串 // 操作结果：用串V替换主串S中出现的所有与串T相等的不重叠的子串 int i=1; // 从串S的第一个字符起查找串T Status k; if(StrEmpty(T)) // T是空串 return ERROR; while(i) { i=Index(S,T,i); // 结果i为从上一个i之后找到的子串T的位置 if(i) // 串S中存在串T { StrDelete(S,i,StrLength(T)); // 删除串T k=StrInsert(S,i,V); // 在原串T的位置插入串V if(!k) // 不能完全插入(定长顺序存储结构有可能发生这种情况) return ERROR; i+=StrLength(V); // 在插入的串V后面继续查找串T } }; return OK; }新闻热点
疑难解答
