首页 > 代码库 > 数据结构与算法---字符串(下)
数据结构与算法---字符串(下)
前面两篇文章，分别介绍了字符串的概念、抽象数据类型、KMP模式匹配算法。这篇文章，我们来学习字符串的一些常用算法。
字符串的相关操作算法
StrAssign：
/*功能:生成一个其值等于Chars的串T*/Status StrAssign(String T, char *chars){ int i; if (chars[0] > MAXSIZE) return ERROR; T[0] = chars[0]; //chars[0]存放的是字符chars的长度 T[0]存放着的是串T的长度 for (i = 1; i <= chars[0]; i++) T[i] = *(chars + i - 1); //将chars的字符依次存入T中 return OK;}
这个算法的功能是创建字符串，没什么复杂的地方。
StrCopy:
/*功能:由串S复制得串T*/Status StrCopy(String S, String T){ int i; for (i = 0; i <= S[0]; i++) T[i] = S[i]; //将S串的字符依次赋给T串 return OK;}
我们在C#中，需要复制某个字符串给另一个字符串，只需调用String类的Copy()方法即可。Copy()方法的具体算法，其实就是上面的代码所演示的。古语有云:”知其然，知其所以然”，编程需要锻炼，不仅仅是锻炼我们的编码速度，而是要从编程中领悟编程的思想。学习经典算法，就是领悟编程思想。
StrEmpty：
/*功能:判断字符串是否为空串，是返回True，否则返回False*/Status StrEmpty(String S){ if (S[0] == 0) //字符长度为0，则为空串 return TRUE; else return FALSE;}
判断字符串是否为空的算法，是不是感觉算法其实也挺简单的？简单的需求就用简单的算法，其实算法还是有难度的，特别是一些经典的算法。但是不要气馁，人生的乐趣就是在不断克服苦难中得到的。只做简单的事情，人生多无趣？
StrCompare:
/*功能:比较两个字符串操作:如果两个串S>T,则返回值>0;若S=T，则返回值=0；若S<T,则返回值<0*/int StrCompare(String S, String T){ int i; for (i = 1; i <= S[0] && i <= T[0]; ++i) { if (S[i != T[i]]) //判断两个字符串中的字符是否相等 return S[i] - T[i]; //根据返回值是否大于零，来判断两个串的大小 else return S[0] - T[0]; //如果两个字符串相等，返回0 }}
这个算法，是判断两个字符串是否相等。
ClearString：
/*功能:将串S清空为空串*/Status ClearString(String S){ S[0] = 0; //将字符长度设置为0，串变为空串。 return OK;}
这个算法，是清空字符串。
StrConcat:
/*功能:用T返回S1和S2联接而成的新串。若未截断，返回True,否则返回FALSE*/Status Concat(String T, String S1, String S2){ int i; if (S1[0] + S2[0] <= MAXSIZE) //未截断 { 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 //截断 { for (i = 1; i <= S1[0]; i++) T[i] = S1[i]; for (i = 1; i <= MAXSIZE - S1[0]; i++) T[S1[0] + 1] = S2[i]; S1[0] = MAXSIZE; return FALSE; }}
这个算法的功能是实现，两个字符串的拼接。需要注意的是，拼接时可能出现空间不足，截断字符串的可能。所以，算法中要分情况来操作。
我们来看看SubString方法的实现，这个方法一定不陌生吧。
/*功能:用Sub返回S串中Pos位置起len个长度的字串初始条件:串S存在，1<=pos<=StrLength(S) 0<=len<=StrLength(S)-Pos+1*/Status SubString(String Sub, String S, int pos, int len){ int i; if (pos<1 || pos>S[0] || len<0 || len>S[0] - pos + 1) return FALSE; for ( i = 1; i <= len; i++) Sub[i] = S[pos + i - 1]; Sub[0] = len; return OK;}
Index:
/*功能:返回字串T在主串S的pos位置之后的位置，若不存在，返回值为0；初始条件:串S、T存在，1<=Pos<=StrLength(S)*/int Index(String S, String T, int pos){ int i = pos; //i的当前位置 int j = 1; //子串T的当前位置 while (i <= S[0]) { if (S[i] == T[j]) //当前位置字符相等，继续匹配 { ++i; ++j; } else //当前位置匹配不相等 { j = 1; // j回溯到字串的第一个位置 i = i - j + 2; //主串位置回溯到上次匹配成功位置的下个位置， } } if (j > T[0]) return i - T[0]; else return 0;}
其实这个方法就是我在数据结构与算法---字符串(中)文章中，讲到的朴素模式匹配的算法。
我们再看一个通过调用其它字符串方法来完成匹配的算法:
/*功能:返回子串T在主串S中pos位置之后出现的位置，如不存在返回0初始条件:1<=pos<=StrLength(S) */int Index2(String S, String T, int pos){ int i = pos; int n, m; //n表示主串S的长度，m表示子串T的长度 if (i > 0) { n = strLength(S); //通过调用Strlength()来获取主串S的长度 m = strLength(T); //通过调用Strlength()来获取子串T的长度 while (i <= n - m + 1) { SubString( sub, S, i，n); //通过调用SubString()来获取从i位置起n个长度的子串sub if (StrCompare(T, sub) == 0) //通过调用StrCompare方法，来判断获取的Sub子串是否已字串T相等 return i; //相等则返回i位 else i++; //不相等，则i回溯到下个位置 } } return 0;}
通过观察这个算法，调用了之前讲到的一些算法。其实，字符串的基本操作也就是那么几个算法。复杂的操作，就需要方法之间互相配合。
好了， 字符串这章已经讲完了。
数据结构与算法---字符串(下)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。