一、实验目的
1.掌握串的特点、连接、插入、删除、显示、查找、取字串等操作；
2.掌握顺序定长存储的方式，以及模式匹配的基本思想。
二、实验原理
1.串是内容受限的线性表，是由零个或多个字符构成的有限序列。串有两种基本存储结构：顺序存储和链式存储，但多采用顺序存储结构。
2.串的常用算法有连接、插入、删除、查找、取子串、模式匹配等算法。模式匹配算法主要有BF算法和KMP算法。
三、实验内容及步骤
（一）实验内容
1.顺序串的连接、插入、删除、取子串；
2.BF模式匹配算法。
3.KMP模式匹配算法。
（二）实验步骤
1.顺序串的初始化
2.顺序串的连接
3.顺序串的插入
4.顺序串的删除
5.取子串
6.用BF模式匹配算法实现串的模式匹配操作
1. #include<cstring> 2. #include<iostream> 3. using namespace std; 4. 5. #define OK 1 6. #define ERROR 0 7. #define OVERFLOW -2 8. typedef int Status; 9. #define MAXSTRLEN 255 //用户可在255以内定义最长串长 10. typedef char SString[MAXSTRLEN+1]; //0号单元存放串的长度 11. 12. Status StrAssign(SString T, char *chars) 13. { //生成一个其值等于chars的串T 14. int i; 15. if (strlen(chars) > MAXSTRLEN) 16. return ERROR; 17. else { 18. T[0] = strlen(chars); 19. for (i = 1; i <= T[0]; i++) 20. T[i] = *(chars + i - 1); 21. return OK; 22. } 23. } 24. 25. //算法4.1 BF算法 26. int Index(SString S, SString T, int pos) 27. { 28. //返回模式T在主串S中第pos个字符之后第s一次出现的位置。若不存在，则返回值为0 29. //其中，T非空，1≤pos≤StrLength(S) 30. int i = pos; 31. int j = 1; 32. while(i <= S[0]&&j <= T[0]) 33. { 34. if(S[i]==T[j]) 35. { 36. ++i;++j; 37. } //继续比较后继字符 38. else 39. { 40. i=i-j+2;j=1; 41. } //指针后退重新开始匹配 42. } 43. if (j > T[0]) 44. return i - T[0]; 45. else 46. return 0; 47. return 0; 48. }//Index 49. 50. int main() 51. { 52. SString S; 53. StrAssign(S,"bbaaabbaba") ; 54. SString T; 55. StrAssign(T,"abb") ; 56. cout<<"主串和子串在第"<<Index(S,T,1)<<"个字符处首次匹配\n"; 57. return 0; 58. }
7.用KMP模式匹配算法实现串的模式匹配操作
1. #include<cstring> 2. #include<iostream> 3. using namespace std; 4. 5. #define OK 1 6. #define ERROR 0 7. #define OVERFLOW -2 8. typedef int Status; 9. #define MAXSTRLEN 255 //用户可在255以内定义最长串长 10. typedef char SString[MAXSTRLEN+1]; //0号单元存放串的长度 11. 12. Status StrAssign(SString T, char *chars) { //生成一个其值等于chars的串T 13. int i; 14. if (strlen(chars) > MAXSTRLEN) 15. return ERROR; 16. else { 17. T[0] = strlen(chars); 18. for (i = 1; i <= T[0]; i++) 19. T[i] = *(chars + i - 1); 20. return OK; 21. } 22. } 23. //算法4.3 计算next函数值 24. void get_next(SString T, int next[]) 25. { //求模式串T的next函数值并存入数组next 26. int i = 1, j = 0; 27. next[1] = 0; 28. while (i < T[0]) 29. if (j == 0 || T[i] == T[j]) 30. { 31. ++i; 32. ++j; 33. next[i] = j; 34. } 35. else 36. j = next[j]; 37. }//get_next 38. 39. //算法4.2 KMP算法 40. int Index_KMP(SString S, SString T, int pos, int next[]) 41. { // 利用模式串T的next函数求T在主串S中第pos个字符之后的位置的KMP算法 42. //其中，T非空，1≤pos≤StrLength(S) 43. int i = pos, j = 1; 44. while (i <= S[0] && j <= T[0]) 45. {if(j==0||S[i]==T[j]) 46. {++i;++j;} 47. else j=next[j];} 48. if (j > T[0]) // 匹配成功 49. return i - T[0]; 50. else 51. return 0; 52. }//Index_KMP 53. 54. int main() 55. { 56. SString S; 57. StrAssign(S,"aaabbaba") ; 58. SString T; 59. StrAssign(T,"abb") ; 60. int *p = new int[T[0]+1]; // 生成T的next数组 61. get_next(T,p); 62. cout<<"主串和子串在第"<<Index_KMP(S,T,1,p)<<"个字符处首次匹配\n"; 63. return 0; 64. }
