HUBEI UNIVERSITY OF AUTOMOTIVE TECHNOLOGY
数据结构程序设计
实验报告03
实训题目：串的构造与应用（自行编写）
专业：软件工程
班级: 软件161
姓名：王洋
学号：201600819
完成日期: 2017年11月5日
2017年11月
目录
一实验前提 (3)
一、1. 实验序言 (3)
一、2. 实验目的 (3)
一、3. 实验背景 (3)
一、4. 实验方式 (3)
二程序原理 (3)
二、1. 设计思路 (3)
二、2. 实验原理 (3)
三程序设计 (3)
三、1. 主要功能 (3)
三、2. 程序界面 (3)
四功能实现 (3)
四、1. 串的初始化 (3)
四、2. 串的插入和删除 (3)
四、3. 串的修改及提取子串 (3)
四、4. 程序调试 (3)
四、5. 程序细节 (3)
四、6. 要点函数功能源码 (3)
五}程序总结 (3)
五、1. 程序收获清单 (3)
五、2. 程序不足改进 (3)
六实验总结 (3)
一实验前提
一、1. 实验序言
每一次实验都是一种历练和进步，至少在每次进行序言的时候，都会去总结和想办法改进程序。即使能力有限，我也切身感受到了进步，以及进步后对程序的稍微深度地思考。
而这次对于串的实验，显然让我感受到了，这样的思考非常欠缺，我所需要完成的还有很多，尤其是随着功能的完善，和深入的编程，会发现其中有更多的地方需要我去改进，尤其是功能越多越深入，这种感觉就越明显
一、2. 实验目的
串的基本操作的编程实现（2学时，验证型），掌握串的建立、遍历、插入、删除等基本操作的编程实现，也可以进一步编程实现查找、合并、剪裁等操作，存储结构可以在顺序结构或结构、索引结构中任选，也可以全部实现。也鼓励学生利用基本操作进行一些应用的程序设计。
一、3. 实验背景
在较熟练的掌握关于对象的编程方法后，这次我就改用了C++进行编写，而且难度要比我预期的要低，效果反而更好了。同时，串基于字符数组实现要容易得多，而且对于一维数组的具体操作，已经相对较为熟练，而且也提供了很多关于字符串的相关函数，所以为了提高编程水平，这次对于串的操作，都不依赖系统函数和字符串函数，相反，深入初始化，插入，删除，遍历等功能的本质，
对字符串的底层进行编程实现。同时也可以使用以前掌握的表格打印方法，让字符串的位置一目了然，同时也方便了字符串的删除和插入等操作。
一、4. 实验方式
本次实验的插入和删除函数的对于长度的判断，我在自行编写的时候出现了错误，所以参阅了课本后对其进行了修改，再者就是如何定一个一个字符串类，其他的所有函数和表格打印输出，界面等都自行编写，而且较以往，有了明显的突破，此外，这次上机是利用类进行的对字符串的编写，以后也会多尝试使用C++进行编写。
二程序原理
二、1. 设计思路
本次实验与以往有很多不同，首先就是在可以移植的界面和函数外，其他的都改用C++进行编程，并用类实现了字符串。其次，就是在编程过程中，随着功能和函数实现的深入，我发现了越来越多的问题，并对其进行了改正，而在改正过程中进行深入思考，又发现了更多的问题，这些问题本事不是程序的问题，也不是函数错误，而是功能上的缺陷和隐患。与以往的写完就没其他重大问题不同，这次的编写确实可以发现很多之前没有也无法注意到的问题，所以一直尽自己的努力在改进。以下是此次两个程序的设计图。
图1 — 程序设计流程图
二、2. 实验原理
串的基本功能实现依旧是基于字符数组，且对串的操作也是对数组的操作，而对数组基本的操作，首先就需要对数组进行初始化。
而串的插入和删除等操作，因为用户的不可预见性，所以操作的长度需要提前进行处理，插入多少位置就需要把插入位置的右端所有的数据进行移动，而删除指定两端位置的字符串，与插入实现方法无异，这都会导致大量的移动，因此部处理操作工程量巨大，而且效率不高，即使链表可以轻松处理这个问题，但对于串的特殊性，它在这里的作用反而是它最大的弊病，因此相比之下，数组在一定程度上反而要比链表容易设计和操作。
修改功能则需要考虑的更多，一般分为三种情况：
1.只修改一个字符，直接找到位置进行修改；
2.修改字符数短于指定位置长度，需要修改替换，然后把多余的位置进行整体向前移动，具体的操作示意图如下图2。
（1）获得修改位置长度
（2）修改指定长度字符
（3）多余位置进行移动
图2 — 修改字符数短于指
定位置长度的操作示意图 3.修改字符数长于指定位置长度，需要修改替换指定长度，然后移动指定右
端位置的后面的数据，腾出剩下需要修改的字符空间，最后进行写入即可。具体的操作示意图如下图3。
（2）修改指定长度字符
（3）移动所需剩余长度
（4）写入剩余修改字符
图3 —修改字符数长于指定位置长度的操作示意图
总体来看，数据的移动量太大，效率不高，但是可以保证操作的逻辑性和正确性，在编程实现方面也简单了许多。
三程序设计
三、1. 主要功能
串可以实现的功能很多，但是作为一个设计者，有时候可以优化一些方案，把功能结合起来，用一个部分实现一些功能，比如我把数据的打印显示做的人性化，在某些方面来说，简化了数据求长，子串的搜索，当然，这些考虑，只是基于较短的数据输入条件，并不可取。一般的功能即新串插入、旧串删除、当前串遍历、当前串求长度、求指定位置子串。但是将遍历和求数据长度单独提取出来作为一个功能觉得不合适，于是，程序整体是在每次操作前后，都进行一次遍历，在使用功能前后都可以让用户清楚地读取当前串情况。
(1)初始化串容，并自动获得串长
(2)串插入、删除、修改
(3)获得子串
(4)串长度以及遍历
三、2. 程序界面
串的实现界面沿袭了之前的实验界面，并且将用户输入，和计算机提示都锁定在了两行之，确保表格的正确打印。输入输出方格下面是数据和数据表格显示的区域，具体如下图。
图4 —串的简单操作程序界面图
四功能实现
四、1. 串的初始化
串的实现改用类进行实现，所以在构造函数只对串就行动态存获取，以及长度归零。同时为了能多次进行初始化，在每次确定长度以前，对长度进行归零操作。串容的获取，采用getchar函数进行缓存区读取，保留回车，和空格在读取到“~”字符时，结束循环。