数据结构实践项目——串-阿里云开发者社区

开发者社区> 人工智能> 正文
登录阅读全文

数据结构实践项目——串

简介: 本文针对数据结构基础系列网络课程(4):串。 1. 串的基本概念及导学 2. 串的顺序存储及其基本操作实现 3. 串的顺序存储应用 4. 串的链式存储及其基本操作实现 5. 串的模式匹配(Brute-Force算法) 6. 串的模式匹配(KMP算法) 【项目1 - 建立顺序串的算法库】   定义顺序串的存储结构,实现其基本运算,并完成测试。   要求

本文针对数据结构基础系列网络课程(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后就退出了。解决这个问题,要查找完整个字符串,并将出现的次数记下来。改造这两个算法吧。

[参考解答]

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章
最新文章
相关文章