数据结构串实验报告

1、数据结构串实验报告 hubei university of automotive technology 数据结构程序设计 实验 报告 0 03 3 实训 题目： 串的构造与应用（自行编写） 专 业： 软件工程 班 级: : 软件 161 姓 名： 王 洋 学 号 ： 202100819 完成日期: : 7 2021 年 年 1 11 月 月 5 5 日 7 2021 年 年 1 11 月 目 录 一 实验前提 . . 4 4 一、 1. 实 验 序 言 4 4 一、 2. 实 验 目 的 4 4 一、 3. 实 验 背 景 4 4 一、 4. 实 验 方 式 5 5 二 程序原理 . . 5

2、5 二、 1. 设 计 思 路 5 5 二、 2. 实 验 原 理 6 6 三 程序设计 . . 8 8 三、 1. 主 要 功 能 8 8 三、 2. 程 序 界 面 8 8 四 功能实现 . . 9 9 四、 1. 串 的 初 始 化 9 9 四、 2. 串 的 插 入 和 删 除 11 四、 3. 串 的 修 改 及 提 取 子 串 12 四、 4. 程 序 调 试 14 四、 5. 程 序 细 节 14 四、 6. 要 点 函 数 功 能 源 码 14 五 程序总结 . . 16 五、 1. 程 序 收 获 清 单 16 五、 2. 程 序 不 足 改 进 17 六 实验总结 . .

3、17 一 实 验前提 一、 1. 实验序言 每一次实验都是一种历练和进步，至少在每次进行序言的时候，都会去总结和想办法改进程序。即使能力有限，我也切身感受到了进步，以及进步后对程序的稍微深度地思考。 而这次对于串的实验，显然让我感受到了，这样的思考非常欠缺，我所需要完成的还有很多，尤其是随着功能的完善，和深入的编程，会发现其中有更多的地方需要我去改进，尤其是功能越多越深入，这种感觉就越明显 一、 2. 实验目的 串的基本操作的编程实现（2 学时，验证型），掌握串的建立、遍历、插入、删除等基本操作的编程实现，也可以进一步编程实现查找、合并、剪裁等操作，存储结构可以在顺序结构或链接结构、索引结构中

4、任选，也可以全部实现。也鼓励学生利用基本操作进行一些应用的程序设计。 一、 3. 实验背景 在较熟练的掌握关于对象的编程方法后，这次我就改用了 c+进行编写，而且难度要比我预期的要低，效果反而更好了。同时，串基于字符数组实现要容易得多，而且对于一维数组的具体操作，已经相 对较为熟练，而且也提供了很多关于字符串的相关函数，所以为了提高编程水平，这次对于串的操作，都不依赖系统函数和字符串函数，相反，深入初始化，插入，删除，遍历等功能的本质，对字符串的底层进行编程实现。同时也可以使用以前掌握的表格打印方法，让字符串的位置一目了然，同时也方便了字符串的删除和插入等操作。 一、 4. 实验方式 本次实验

5、的插入和删除函数的对于长度的判断，我在自行编写的时候出现了错误，所以参阅了课本后对其进行了修改，再者就是如何定一个一个字符串类，其他的所有函数和表格打印输出，界面等都自行编写，而且较以往，有了明显的突破，此外，这次上机是利用类进行的对字符串的编写，以后也会多尝试使用 c+进行编写。 二 程序原理 二、 1. 设计思路 本次实验与以往有很多不同，首先就是在可以移植的界面和函数外，其他的都改用 c+进行编程，并用类实现了字符串。其次，就是在编程过程中，随着功能和函数实现的深入，我发现了越来越多的问题，并对其进行了改正，而在改正过程中进行深入思考，又发现了更多的问题，这些问题本事不是程序的问题，也不

6、是函数错误，而是功能上的缺陷和隐患。与以往的写完就没其他重大问题不同，这次的编写确实可以发现很多之前没有也无法注意到的问题，所以一直尽自己 的努力在改进。以下是此次两个程序的设计图。 图 1 程序设计流程图 二、 2. 实验原理 串的基本功能实现依旧是基于字符数组，且对串的操作也是对数组的操作，而对数组基本的操作，首先就需要对数组进行初始化。 而串的插入和删除等操作，因为用户的不可预见性，所以操作的长度需要提前进行处理，插入多少位置就需要把插入位置的右端所有的数据进行移动，而删除指定两端位置的字符串，与插入实现方法无异，这都会导致大量的移动，因此内部处理操作工程量巨大，而且效率不高，即使链表可

7、以轻松处理这个问题，但对于串的特殊性，它在这里的作用反而是它最大的弊病，因此相比之下，数组在一定程度上反而要比链表容易设计和操作。 修改功能则需要考虑的更多，一般分为三种情况： 1.只修改一个字符，直接找到位置进行修改； 2.修改字符数短于指定位置长度，需要修改替换，然后把多余的位置进行整体向前移动，具体的操作示意图如下图 2。 a b c 1 2 3 d d 5 6 7 8 9 拷贝框架和界面 改用 c+实现 基于类进行功能实现 多次优化输出打印 修改调试 （1）获得修改位置长度 （2）修改指定长度字符 （3）多余位置进行移动 图 2 修改字符数短于指定位置长度的操作示意图 3.修改字符数长

8、于指定位置长度，需要修改替换指定长度，然后移动指定右端位置的后面的数据，腾出剩下需要修改的字符空间，最后进行写入即可。具体的操作示意图如下图 3。 （1）获得修改位置 长度 （2）修改指定长度 字符 （3）移动所需剩余长度 （4）写入剩余修改字符 图 3 修改字符数长于指定位置长度的操作示意图 总体来看，数据的移动量太大，效率不高，但是可以保证操作的逻辑性和正确性，在编程实现方面也简单了许多。 a b c 1 2 3 4 5 6 7 8 9 a b c 1 2 3 4 5 6 7 8 9 a b c 1 2 3 d d 7 8 a b c 1 2 3 4 5 7 8 a b c 1 2 3 4

9、 5 8 9 a b c 1 2 3 4 5 6 7 8 9 三 程序设计 三、 1. 主要功能 串可以实现的功能很多，但是作为一个设计者，有时候可以优化一些方案，把功能结合起来，用一个部分实现一些功能，比如我把数据的打印显示做的人性化，在某些方面来说，简化了数据求长，子串的搜索，当然，这些考虑，只是基于较短的数据输入条件，并不可取。一般的功能即新串插入、旧串删除、当前串遍历、当前串求长度、求指定位置子串。但是将遍历和求数据长度单独提取出来作为一个功能觉得不合适，于是，程序整体是在每次操作前后，都进行一次遍历，在使用功能前后都可以让用户清楚地读取当前串情况。 (1)初始化串内容，并自动获得串长

10、 ( (2 2) ) 串 插 入、 删除、 修改 ( (3 3) ) 获得子串 (4)串长度以及遍历 三、 2. 程序界面 串的实现界面沿袭了之前的实验界面，并且将用户输入，和计算机提示都锁定在了两行之内，确保表格的正确打印。输入输出方格下面是数据和 数据表格显示的区域，具 体如下图。 图 4 串的简单操作程序界面图 四 功能实现 四、 1. 串的初始化 串的实现改用类进行实现，所以在构造函数内只对串就行动态内存获取，以及长度归零。同时为了能多次进行初始化，在每次确定长度以前，对长度进行归零操作。串内容的获取，采用 getchar 函数进行缓存区读取，保留回车，和空格在读取到字符时，结束循环。

11、 这个地方我当时有一个疑问就是，我在动态内存分配的时候，故意使用 1 长度，发现仍然可以进行任意长度的输入，而且操作去除长度判断，其他的函数都是可以运行的。这让我非常疑惑，疑惑在动态内存分配到底起到作用没有？之后和吴贝贝同学讨论发现，循环获取字符的操作中，我直接对内存进行了访问和操作，所以动态内存申请就显得没有作用了，而且也没有必要。但是仔细想后有发现，目前我们对操作系统如何分配内存的机制不是很了解，如果当我们在进行循环访问和操作内存的时候，一连串的内存的某个地方 出现了其他程序使用的区域，那么循环到下一个正在使用的区域，就会打破另外一个程序的内存访问区，可能会导致其他程序的崩溃，但是后来查询

12、资料发现，内存的分配，系统都会自动正确地选取一系列连续的可用内存给程序使用，所以不必要考虑到会破坏其他程序的内存区域。但是这只是小部分的获取字符串内容，如果遇到大量的字符需要输入，就必须要考虑到这个问题，毕竟对一个连续的内存区域进行操作，难免会出现错误这些问题，不仅让我深入体会到编程中我们没有考虑过的问题，也让我意识到，我们思考的根本不够，今后的实验中，以后的编程里，还需要考虑更多更多，以下是初始化函数代码。 void string:strcreate() int i=0; length = 0;/可多次进行输入 getchar();/吃掉选择功能的回车 while (stri = getch

13、ar() != | stri + 1 = null) /不是继续获得字符 因为对内存进行操作 需要保证下一个内存空 i+;/当然 stri + 1 = null 这个我不能保证真正能用上或是本身就是个错误 length = i; 四、 2. 串的插入和删除 （1）插入 插入部分，获得插入位置，同时输入插入内容，通过插入的内容判断长度，并把这些参数传入设置好的成员函数，并给对象发消息，进行插入操作。本质上也就是通过插入内容的长度来进行原串的移动，然后进行数据写入。当然，因为我设置了可以保留空格和回车，特别是回车，而且将其遍历内容打印到表格中，在某些情况下会出错。比如如果字符串内有了回车，我的打印

14、内容会在表格内也会换行，这样观察字符串长度就会出错（在表格上看）因为表格上的空位置，在串内是不存在的，如下图，这样就对复杂的插入操作，就需要更复杂的输出打印方式，所以程序需要考虑，可以进步的地方确实很多。 图 5 输入需要插入的位置 图 6 因为长度问题和表格会提示错误 （2）删除 删除功能同样是数据的移动，用户输入需要删除的左右位置，就可以通过字符的移动来实现。和插入功能有着相同的问题，就是带有回车的部分不好处理，主要是因为我加入了表格打印，这个打印限制了我不少发挥的地方，但是它确实又好用，所以目前的我不能两全其美，也需要反省和深入学习。对于普通的删除操作基本没有多大问题，如下图演示。 图

15、7 输入所需要删除的位置 图 8 成功删除指定位置内容 四、 3. 串的修改及提取子串 (1)删除，如实验原理所述，这里不再具体阐述，主要存在一些 仍因为打印表格出现的问题，就是修改带回车内容的字符串，修改后打印出来的内容会不好处理，不带回车的是没有问题的，因为变化性太大，所以不好把控，如下图，我在当前串内对 4 和 5 直接的位置进行修改，回车确认后如下显示。 图 9 修改错误范例 图 10 回车后显示错乱 (2)获得子串，原理与删除相同，函数内得到位置之后返回一个新的数组指针，然后对其输出显示即可，同时还有显示长度，当然因为回车和空格的存在，而且回车符号虽然可以用其他的符号显示出来，代替看

16、不见的回车或者空格，但是这样的替代系统不认可，显示不出来，所以也移除了这个功能，导致如果串内有回车或者字符，字符长度和肉眼看到的不一样。 四、 4. 程序调试 程序功能实现后，进行了大量的改进具体如下。 （1）该用表格打印，方便观看。 （2）加入初始化含回车，重新考虑输出打印。 （3）加入获得子串功能。 （4）在输出打印的部分，调试了很久，为了保证每一行被输满，而且要考虑到回车的效果，改进了很多，同时也加入了可以修改表格的长和宽的效果。 四、 5. 程序细节 （1）利用类实现串的操作。 （2）使用了制表符制作表格，让输入打印更美观。 （3）利用光标定位，让用户输入和输出提示被锁定在一个区域内，

17、不仅方便观看和操作，也保证了表格的安全和完整。 （4）加入回车和空格输入，让输入变得灵活。 （5）将一些语句很短的判断性质的函数融合在一起，并使用了重载。 四、 6. 要点函数功能源码 打印输出串（遍历）源码。 void string:strtraverse() int i, j; int item;/增加中间变量,防止i被修改 for (i = 0, j = 0, item = 0; i length-1; i+, item+)/最后一个字符单独判断 if (i != 0 i % column = 0 | stri = n)/需要分情况 if (stri = n) i+;/ 直接换行，跳过回

18、车字符 item = 0;/当遇到回车，需要返回左边进行打印 j+; item = 0; /当遇到整行，需要返回左边进行打印 setpos(3 + 3 * item, 16 + j * 2); std:cout stri; if(strlength-1=)/如果最后一行只有结束符 那么不让它显示 std:cout std:endl; else /如果不是就把它打印出来 setpos(3 + 3 * item, 16 + j * 2); std:cout stri; std:cout std:endl; setpos(1, 11); 五 程序总结 五、 1. 程序收获清单 (1)改用类进行编写，效果和收益都不错。 (2)深入功能，考虑的多了，会发现更多的进步空间，会主要更多的程序细节，特别是在打印输出部分，我至少改进了六次（如要点功能代码）。 (3)精简功能函数，避免在函数中出现输入输出。 (4)函数多使用了返回值，增加可用性，精简了函数的外部。 五、 2. 程序不足改进 (1)类的使用需要更加熟练。 (2)表格的使用仍然是一个弊端，需要考虑其他的美观界面。 (3)程序实现功能较少，增加功能因为打印表格而维护起来很麻烦，以后想办法学习更好的输入表格形式。 (4)因为加入了表格，打印起来非常复杂而且容易出错，主要原因是计