本文针对数据结构基础系列网络课程(4)：串。 1. 串的基本概念及导学 2. 串的顺序存储及其基本操作实现 3. 串的顺序存储应用 4. 串的链式存储及其基本操作实现 5. 串的模式匹配（Brute-Force算法） 6. 串的模式匹配（KMP算法）
【项目1 - 建立顺序串的算法库】 定义顺序串的存储结构，实现其基本运算，并完成测试。 要求： 1、头文件sqString.h中定义数据结构并声明用于完成基本运算的函数。对应基本运算的函数包括：
void StrAssign(SqString &s,char cstr[]); //字符串常量cstr赋给串s void StrCopy(SqString &s,SqString t); //串t复制给串s bool StrEqual(SqString s,SqString t); //判串相等 int StrLength(SqString s); //求串长 SqString Concat(SqString s,SqString t); //串连接 SqString SubStr(SqString s,int i,int j); //求子串 SqString InsStr(SqString s1,int i,SqString s2); //串插入 SqString DelStr(SqString s,int i,int j) ; //串删去 SqString RepStr(SqString s,int i,int j,SqString t); //串替换 void DispStr(SqString s); //输出串2、在sqString.cpp中实现这些函数 3、在main函数中完成测试，包括如下内容： (1)建立串s:abcdefghijklmn和串s1:123 (2)输出串s和s1 (3)输出串s的长度 (4)在串s的第9个字符位置插入串s1而产生串s2 (5)输出串s2 (6)删除串s第2个字符开始的5个字符而产生串s2 (7)输出串s2 (8)将串s第2个字符开始的5个字符替换成串s1而产生串s2 (9)输出串s2 (10)提取串s的第2个字符开始的10个字符而产生串s3 (11)输出串s3 (12)将串s1和串s2连接起来而产生串s4 (13)输出串s4 [参考解答]
【项目2 - 建立链串的算法库】 定义链串的存储结构，实现串的基本运算，并完成测试。 具体要求参照项目1。 [参考解答]
【项目3-顺序串算法】 采用顺序存储方式存储串，实现下列算法并测试： （1）试编写算法实现将字符串S中所有值为c1的字符换成值为c2的字符： void Trans(SqString *&s, char c1, char c2); （2）试编写算法，实现将已知字符串所有字符倒过来重新排列。如ABCDEF改为FEDCBA。 void Invert(SqString &s) （3）从串s中删除其值等于c的所有字符。如从message中删除’e’，得到的是mssag。 void DellChar(SqString &s, char c) （4）有两个串s1和s2，设计一个算法求一个这样的串，该串中的字符是s1和s2中公共字符。所谓公共子串，是由在s1中有，且在s2中也有的字符构成的字符。例s1为”message”，s2为”agent”，得到的公共子串是”eage”。 SqString CommChar(SqString s1,SqString s2); ［参考解答］
【项目4-字符串加密】 一个文本串可用事先编制好的字符映射表进行加密。例如，设字符映射表为：
abcdefghijklmnopqrstuvwxyz ngzqtcobmuhelkpdawxfyivrsj则字符串“lao he jiao shu ju jie gou”被加密为“enp bt umnp xby uy umt opy”。 设计一个程序，实现加密、解密算法，将输入的文本进行加密后输出，然后进行解密并输出。 ［参考解答］
【项目5 - 计数的模式匹配】 采用顺序结构存储串，编写一个算法计算指定子串在一个字符串中出现的次数，如果该子串不出现则为0。
提示：无论BF模式匹配算法，还是KMP算法，都是在找到子串substr后就退出了。解决这个问题，要查找完整个字符串，并将出现的次数记下来。改造这两个算法吧。
[参考解答]
相关资源：用定长顺序存储结构表示串，求两个串的全部最长公共子串