HUBEI UNIVERSITY OF AUTOMOTIVE TECHNOLOGY
数据结构程序设计 实验报告03
实训题目: 串的构造与应用(自行编写) 专 业: 软件工程 班 级: 软件 161 姓 名: 王 洋 学 号: 201600819 完成日期: 2017年11月5日
2017年11月
目 录
一 实验前提 ....................................................... 3
一、1. 实验序言 ................................................ 3 一、2. 实验目的 ................................................ 3 一、3. 实验背景 ................................................ 3 一、4. 实验方式 ................................................ 4 二 程序原理 ....................................................... 4
二、1. 设计思路 ................................................ 4 二、2. 实验原理 ................................................ 4 三 程序设计 ....................................................... 6
三、1. 主要功能 ................................................ 6 三、2. 程序界面 ................................................ 6 四 功能实现 ....................................................... 7
四、1. 串的初始化 .............................................. 7 四、2. 串的插入和删除 .......................................... 8 四、3. 串的修改及提取子串 ...................................... 9 四、4. 程序调试 ............................................... 10 四、5. 程序细节 ............................................... 10 四、6. 要点函数功能源码 ....................................... 11 五 }程序总结 ..................................................... 12
五、1. 程序收获清单 ........................................... 12 五、2. 程序不足改进 ........................................... 12 六 实验总结 ...................................................... 12
第 2 页 /共 12 页
一 实验前提
一、1. 实验序言
每一次实验都是一种历练和进步,至少在每次进行序言的时候,都会去总结和想办法改进程序。即使能力有限,我也切身感受到了进步,以及进步后对程序的稍微深度地思考。
而这次对于串的实验,显然让我感受到了,这样的思考非常欠缺,我所需要完成的还有很多,尤其是随着功能的完善,和深入的编程,会发现其中有更多的地方需要我去改进,尤其是功能越多越深入,这种感觉就越明显
一、2. 实验目的
串的基本操作的编程实现(2学时,验证型),掌握串的建立、遍历、插入、删除等基本操作的编程实现,也可以进一步编程实现查找、合并、剪裁等操作,存储结构可以在顺序结构或链接结构、索引结构中任选,也可以全部实现。也鼓励学生利用基本操作进行一些应用的程序设计。
一、3. 实验背景
在较熟练的掌握关于对象的编程方法后,这次我就改用了C++进行编写,而且难度要比我预期的要低,效果反而更好了。同时,串基于字符数组实现要容易得多,而且对于一维数组的具体操作,已经相对较为熟练,而且也提供了很多关于字符串的相关函数,所以为了提高编程水平,这次对于串的操作,都不依赖系统函数和字符串函数,相反,深入初始化,插入,删除,遍历等功能的本质,对字符串的底层进行编程实现。同时也可以使用以前掌握的表格打印方法,让字符串的位置一目了然,同时也方便了字符串的删除和插入等操作。
第 3 页 /共 12 页
一、4. 实验方式
本次实验的插入和删除函数的对于长度的判断,我在自行编写的时候出现了错误,所以参阅了课本后对其进行了修改,再者就是如何定一个一个字符串类,其他的所有函数和表格打印输出,界面等都自行编写,而且较以往,有了明显的突破,此外,这次上机是利用类进行的对字符串的编写,以后也会多尝试使用C++进行编写。
二 程序原理
二、1. 设计思路
本次实验与以往有很多不同,首先就是在可以移植的界面和函数外,其他的都改用C++进行编程,并用类实现了字符串。其次,就是在编程过程中,随着功能和函数实现的深入,我发现了越来越多的问题,并对其进行了改正,而在改正过程中进行深入思考,又发现了更多的问题,这些问题本事不是程序的问题,也不是函数错误,而是功能上的缺陷和隐患。与以往的写完就没其他重大问题不同,这次的编写确实可以发现很多之前没有也无法注意到的问题,所以一直尽自己的努力在改进。以下是此次两个程序的设计图。
基于类进行功能实现 拷贝框架和界面
修改调试 改用C++实现 多次优化输出打印
图1 — 程序设计流程图
二、2. 实验原理
串的基本功能实现依旧是基于字符数组,且对串的操作也是对数组的操作,而对数组基本的操作,首先就需要对数组进行初始化。
而串的插入和删除等操作,因为用户的不可预见性,所以操作的长度需要提前进行处理,插入多少位置就需要把插入位置的右端所有的数据进行移动,而删
第 4 页 /共 12 页
除指定两端位置的字符串,与插入实现方法无异,这都会导致大量的移动,因此内部处理操作工程量巨大,而且效率不高,即使链表可以轻松处理这个问题,但对于串的特殊性,它在这里的作用反而是它最大的弊病,因此相比之下,数组在一定程度上反而要比链表容易设计和操作。
修改功能则需要考虑的更多,一般分为三种情况: 1.只修改一个字符,直接找到位置进行修改;
2.修改字符数短于指定位置长度,需要修改替换,然后把多余的位置进行整体向前移动,具体的操作示意图如下图2。
(1)获得修改位置长度 (2)修改指定长度字符 (3)多余位置进行移动
图2 — 修改字符数短于指定位置长度的操作示意图
A B C 1 2 3 D D 5 6 7 8 9 A B C 1 2 3 4 5 6 7 8 9 A B C 1 2 3 4 5 6 7 8 9 3.修改字符数长于指定位置长度,需要修改替换指定长度,然后移动指定右端位置的后面的数据,腾出剩下需要修改的字符空间,最后进行写入即可。具体的操作示意图如下图3。
(1)获得修改位置长度 (2)修改指定长度字符 (3)移动所需剩余长度 (4)写入剩余修改字符
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 5 8 9 A B C 1 2 3 4 5 6 7 8 9
图3 — 修改字符数长于指定位置长度的操作示意图
总体来看,数据的移动量太大,效率不高,但是可以保证操作的逻辑性和正确性,在编程实现方面也简单了许多。
第 5 页 /共 12 页
三 程序设计
三、1. 主要功能
串可以实现的功能很多,但是作为一个设计者,有时候可以优化一些方案,把功能结合起来,用一个部分实现一些功能,比如我把数据的打印显示做的人性化,在某些方面来说,简化了数据求长,子串的搜索,当然,这些考虑,只是基于较短的数据输入条件,并不可取。一般的功能即新串插入、旧串删除、当前串遍历、当前串求长度、求指定位置子串。但是将遍历和求数据长度单独提取出来作为一个功能觉得不合适,于是,程序整体是在每次操作前后,都进行一次遍历,在使用功能前后都可以让用户清楚地读取当前串情况。
(1)初始化串内容,并自动获得串长 (2)串插入、删除、修改 (3)获得子串 (4)串长度以及遍历
三、2. 程序界面
串的实现界面沿袭了之前的实验界面,并且将用户输入,和计算机提示都锁定在了两行之内,确保表格的正确打印。输入输出方格下面是数据和数据表格显示的区域,具体如下图。
图4 —串的简单操作程序界面图
第 6 页 /共 12 页
四 功能实现
四、1. 串的初始化
串的实现改用类进行实现,所以在构造函数内只对串就行动态内存获取,以及长度归零。同时为了能多次进行初始化,在每次确定长度以前,对长度进行归零操作。串内容的获取,采用getchar函数进行缓存区读取,保留回车,和空格在读取到“~”字符时,结束循环。
这个地方我当时有一个疑问就是,我在动态内存分配的时候,故意使用1长度,发现仍然可以进行任意长度的输入,而且操作去除长度判断,其他的函数都是可以运行的。这让我非常疑惑,疑惑在动态内存分配到底起到作用没有?之后和吴贝贝同学讨论发现,循环获取字符的操作中,我直接对内存进行了访问和操作,所以动态内存申请就显得没有作用了,而且也没有必要。但是仔细想后有发现,目前我们对操作系统如何分配内存的机制不是很了解,如果当我们在进行循环访问和操作内存的时候,一连串的内存的某个地方出现了其他程序使用的区域,那么循环到下一个正在使用的区域,就会打破另外一个程序的内存访问区,可能会导致其他程序的崩溃,但是后来查询资料发现,内存的分配,系统都会自动正确地选取一系列连续的可用内存给程序使用,所以不必要考虑到会破坏其他程序的内存区域。但是这只是小部分的获取字符串内容,如果遇到大量的字符需要输入,就必须要考虑到这个问题,毕竟对一个连续的内存区域进行操作,难免会出现错误……这些问题,不仅让我深入体会到编程中我们没有考虑过的问题,也让我意识到,我们思考的根本不够,今后的实验中,以后的编程里,还需要考虑更多更多,以下是初始化函数代码。
void string::strCreate()
{
}
int i=0; length = 0;//可多次进行输入 getchar();//吃掉选择功能的回车
while ((str[i] = getchar()) != '~' || str[i + 1] == NULL)
//不是~继续获得字符
因为对内存进行操作 需要保证下一个内存空
i++;//当然 str[i + 1] == NULL 这个我不能保证真正能用上或是本身就是个错误
length = i;
第 7 页 /共 12 页
四、2. 串的插入和删除
(1)插入
插入部分,获得插入位置,同时输入插入内容,通过插入的内容判断长度,并把这些参数传入设置好的成员函数,并给对象发消息,进行插入操作。本质上也就是通过插入内容的长度来进行原串的移动,然后进行数据写入。当然,因为我设置了可以保留空格和回车,特别是回车,而且将其遍历内容打印到表格中,在某些情况下会出错。比如如果字符串内有了回车,我的打印内容会在表格内也会换行,这样观察字符串长度就会出错(在表格上看)因为表格上的空位置,在串内是不存在的,如下图,这样就对复杂的插入操作,就需要更复杂的输出打印方式,所以程序需要考虑,可以进步的地方确实很多。
图5— 输入需要插入的位置
图6— 因为长度问题和表格会提示错误
(2)删除
删除功能同样是数据的移动,用户输入需要删除的左右位置,就可以通过字符的移动来实现。和插入功能有着相同的问题,就是带有回车的部分不好处理,主要是因为我加入了表格打印,这个打印限制了我不少发挥的地方,但是它确实又好用,所以目前的我不能两全其美,也需要反省和深入学习。对于普通的删除
第 8 页 /共 12 页
操作基本没有多大问题,如下图演示。
图7— 输入所需要删除的位置
图8— 成功删除指定位置内容
四、3. 串的修改及提取子串
(1)删除,如实验原理所述,这里不再具体阐述,主要存在一些仍因为打印表格出现的问题,就是修改带回车内容的字符串,修改后打印出来的内容会不好处理,不带回车的是没有问题的,因为变化性太大,所以不好把控,如下图,我在当前串内对4和5直接的位置进行修改,回车确认后如下显示。。
图9— 修改错误范例 第 9 页 /共 12 页
图10— 回车后显示错乱
(2)获得子串,原理与删除相同,函数内得到位置之后返回一个新的数组指针,然后对其输出显示即可,同时还有显示长度,当然因为回车和空格的存在,而且回车符号虽然可以用其他的符号显示出来,代替看不见的回车或者空格,但是这样的替代系统不认可,显示不出来,所以也移除了这个功能,导致如果串内有回车或者字符,字符长度和肉眼看到的不一样。
四、4. 程序调试
程序功能实现后,进行了大量的改进具体如下。 (1)该用表格打印,方便观看。
(2)加入初始化含回车,重新考虑输出打印。 (3)加入获得子串功能。
(4)在输出打印的部分,调试了很久,为了保证每一行被输满,而且要考虑到回车的效果,改进了很多,同时也加入了可以修改表格的长和宽的效果。。
四、5. 程序细节
(1)利用类实现串的操作。
(2)使用了制表符制作表格,让输入打印更美观。
(3)利用光标定位,让用户输入和输出提示被锁定在一个区域内,不仅方便观看和操作,也保证了表格的安全和完整。
(4)加入回车和空格输入,让输入变得灵活。
(5)将一些语句很短的判断性质的函数融合在一起,并使用了重载。
第 10 页 /共 12 页
四、6. 要点函数功能源码
打印输出串(遍历)源码。
void string::strTraverse() {
std::cout << std::endl; SetPos(1, 11);
if(str[length-1]=='~')//如果最后一行只有结束符 那么不让它显示 { }
SetPos(3 + 3 * item, 16 + j * 2); std::cout << str[i];
std::cout << std::endl;
else //如果不是就把它打印出来 }
SetPos(3 + 3 * item, 16 + j * 2); std::cout << str[i];
for (i = 0, j = 0, item = 0; i < length-1; i++, item++)//最后一个字符单独判断 {
if (i != 0 && i % column == 0 || str[i] == '\\n')//需要分情况 { }
if (str[i] == '\\n') { } j++;
item = 0; //当遇到整行,需要返回左边进行打印
i++;// 直接换行,跳过回车字符
item = 0;//当遇到回车,需要返回左边进行打印
int i, j;
int item;//增加中间变量,防止i被修改
第 11 页 /共 12 页
五 }程序总结
五、1. 程序收获清单
(1)改用类进行编写,效果和收益都不错。
(2)深入功能,考虑的多了,会发现更多的进步空间,会主要更多的程序细节,特别是在打印输出部分,我至少改进了六次(如要点功能代码)。
(3)精简功能函数,避免在函数中出现输入输出。
(4)函数多使用了返回值,增加可用性,精简了函数的外部。
五、2. 程序不足改进
(1)类的使用需要更加熟练。
(2)表格的使用仍然是一个弊端,需要考虑其他的美观界面。
(3)程序实现功能较少,增加功能因为打印表格而维护起来很麻烦,以后想办法学习更好的输入表格形式。
(4)因为加入了表格,打印起来非常复杂而且容易出错,主要原因是计算方法的问题。而且因为功能的增加,会越来越麻烦,而且增加出错概率(不是指程序本身出错,而是打印的时候会出错)。
(4)获得老师指导,点出我的函数内出现了常量,函数内仍然使用了常量,不方便修护,以后会多注意。
六 实验总结
实验用类很好的实现了很多功能,而且减少出错率,增加编写效率。但由于没有好的输出方式,让基于这些功能的输出打印,表现的非常脆弱,而且难以修复,当然这不影响本次实验的主要内容,只是我自己在扩展程序中发现的问题。同时随着问题的深入,会暴漏更多的问题。同样这也是一次次的成长。
最后与吴贝贝同学讨论了对内存的操作的利弊,并帮我解决了其中的部分疑惑,也感谢马老师给予程序中的一些建议。
第 12 页 /共 12 页
因篇幅问题不能全部显示,请点此查看更多更全内容