文本编辑程序是利用计算机进行文字加工的基本软件工具，实现对文本文件的插入、删除等修改操作。限制这些操作以行为单位进行的编辑程序称为行编辑程序。行编辑器只能从事最简单的输入输出。输入、编辑、文档显示并不能同步地进行。编辑的文本文件可能很大，全部读入内存的做法既不经济也不易实现。一种解决办法是逐行地编辑，任何时刻只把待编辑文件的一行放在内存，称为活区。允许输入出错时发现错误并及时更正。一般而言，用户无法直接输入文本，而只能在文本终端上通过简要的命令，对已有的文档进行添加或编写。现利用字符串来定义，设计并实现了一个简单行编辑程序，具备行编辑器的行插入，行删除等基本功能。通过该题目的设计过程，可以使我们加深理解数据结构中的线性表及栈的逻辑结构、存储结构，掌握线性表及栈上基本运算的实现，进一步理解和熟练掌握课本中所学的各种数据结构，学会如何把学到的知识用于解决实际问题，还可以培养我们的动手能力。 关键词:行编辑器；文本；字符串 注：目录只是一个参考（这个只是自己当时要求做的）

（1）用栈实现简单的行编辑程序，主要功能有：行插入（格式：i,即 将插入活区中的第行之后）；行删除（格式：d[ ]， 删除活区中第行（到第行），两种格式的例子是：“d10 ”和“d10 14 ”）；活页切换（格式：n， 将活区写入输出文件，并从输入文件中读入下一段，作为新的活区）； 活区显示（格式：p， 逐页地（每页20行）显示活区内容，每显示一页之后由用户决定是否继续显示以后各页（如果存在）。印出的每一行要前置行号和一个空格符，行号固定占4位，增量为1）； （2）设文件每行不超过320个字符，很少超过80个字符，由学生依据软件工程的测试技术自己确定，注意测试边界数据，如首行、尾行。算法对于合法的输入数据都能产生满足规格说明要求的结果； （3）算法对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得出满足规格说明要求的结果；对算法实现过程中的异常情况能给出出错信息； （4）较高要求：加入复杂操作，如对某行进行串替换等；

本课程设计主要解决在文本编辑中，对行编辑的问题，通过字符串完善对文本的编辑，实现对文本的查找、替换、和修改数据。在程序设计中采用了字符串的方法实现对简单的行编辑器。程序通过调试运行，初步实现了设计目标，并且经过适当完善后，将可以应用在实际中解决问题。用字符串实现一个简单的行编辑器，其中包括字符的按行录入、修改、替换、查询。用栈实现简单的行编辑程序，文本编辑程序是利用计算机进行文字加工的基本软件工具，实现对文本文件的插入、删除等修改操作。限制这些操作以行为单位进行的编辑程序称为行编辑程序。被编辑的文本文件可能很大，全部读入编辑程序的数据空间（内存）的做法即不经济，又不易实现。一种解决方法是逐段的编辑。任何时刻只把待编辑文件的一段放在内存，称为活区。 通过《简单行编辑程序》的设计过程，我们学会了分析研究数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构，存储结构及相应的算法，并初步掌握算法的时间分析和空间分析的技术。一方面，通过该题目设计工程，也是复杂程序设计的训练过程，要求我们编写程序设计结构清楚和正确易读，符合软件工程的规范。 该题目通过用规范的数学语言描述数据结构的定义，以突出其数学特性，同时，通过对若干数据结构实例的参考和学习，为今后学习面向对象的程序设计做了铺垫。

栈（stack）是一种特殊的线性表。作为一个简单的例子，可以把食堂里冼净的一摞碗看作一个栈。在通常情况下，最先冼净的碗总是放在最底下，后冼净的碗总是摞在最顶上。而在使用时，却是从顶上拿取，也就是说，后冼的先取用，后摞上的先取用。如果我们把冼净的碗“摞上”称为进栈（压栈），把“取用碗”称为出栈（弹出），那么上例的特点是：后进栈的先出栈。然而，摞起来的碗实际上是一个线性表，只不过“进栈”和“出栈”都在最顶上进行，或者说，元素的插入和删除操作都是在线性表的一端进行而已。 一般而言，栈是一个线性表，其所有的插入和删除操作均是限定在线性表的一端进行，允许插入和删除的一端称栈顶(Top)，不允许插入和删除的一端称栈底(Bottom)。若给定一个栈S=（a1, a2，a3，……，an），则称a1为栈底元素，an为栈顶元素，元素ai位于元素ai-1之上。栈中元素按a1, a2，a3，……，an 的次序进栈，如果从这个栈中取出所有的元素，则出栈次序为an, an-1，……，a1 。也就是说，栈中元素的进出是按后进先出的原则进行，这是栈结构的重要特征。因此栈又称为后进先出(LIFO—Last In First Out)表。 我们常用一个图来形象地表示栈，其形式如下图：

通常，对栈进行的操作主要有以下几种： ⑴在使用栈之前，首先需要建立一个空栈，称建栈（栈的初始化）； ⑵往栈顶加入一个新元素，称进栈（压栈、入栈）； ⑶删除栈顶元素，称出栈（退栈、弹出）； ⑷查看当前的栈顶元素，称读栈；{注意与⑶的区别} ⑸在使用栈的过程中，还要不断测试栈是否为空或已满，称为测试栈。

（1）顺序栈 栈是一种线性表，在计算机中用一维数组作为栈的存储结构最为简单，操作也最为方便。例如，设一维数组STACK[1…n] 表示一个栈，其中n为栈的容量，即可存放元素的最大个数。栈的第一个元素，或称栈底元素，是存放在STACK[1]处，第二个元素存放在STACK[2]处，第i个元素存放在STACK[i]处。另外，由于栈顶元素经常变动，需要设置一个指针变量top，用来指示栈顶当前位置，栈中没有元素即栈空时，令top=0；当top=n时，表示栈满。 如果一个栈已经为空，但用户还继续做出栈（读栈）操作，则会出现栈的“下溢”；如果一个栈已经满了，用户还继续做进栈操作，则会出现栈的“上溢”。这两种情况统称为栈的溢出。 建栈的操作很简单，只要建立一个一维数组，再把栈顶指针置为零即可。栈的容量根据具体的应用要求而定，一般要定义的足够大。比如：

（2）链式栈 当我们学可指针和链表后，也可以用链表来模拟栈（链式栈），这样可以提高空间利用率，但编程复杂度提高了。定义方法如下：

在这里插入图片描述

(3)记录型栈 由于栈本身和栈顶指针是密不可分的，所以有时我们把他们定义成一个记录来处理。如：

（1）建栈 只要把栈顶指针置为零。即在程序开始时，置top:=0； （2）测试栈 测试栈顶指针的值，若top=0，则栈空；若top=n，则栈满。 （3）读栈 若top=0，则栈空，无栈顶元素可读，显示出错信息，中止程序； 若top0，则回送栈顶元素的值STACK[top]给某个变量。 （4）进栈（push） 将栈顶指针加1后，再把新元素送到栈顶。注意进栈操作前必须保证栈不能 满，否则会溢出。假设新元素x为整型，栈的最大深度为n。 则，x和n设置为值型参，而栈和栈顶指针要设置成变量型参。

（5）出栈(pop) 取得栈顶元素的值给x后，再把栈顶指针top的值减1。注意出栈操作前必须保证栈非空。

栈是一种先进后出的线性表，为了能按照原来的输入顺序输出元素，我在程序中设计了两个栈，第一个栈用来存储输入的字符，然后把第一个栈的元素出栈，并且把出栈的元素放入第二个栈中，这样就实现了出栈是元素的顺序和最开始输入的顺序是一致的了。 首先，构造一个空栈函数Createlist()；然后设计输入函数push(SqStack &S,char e)和出栈函数pop(SqStack &S,char &e)；在这两个函数里，我们通过顶指针的增加（S.top++=e）和指针的减少来实现元素的进栈和出（e=–S.top）。 我们通过设计函数int insert()来进行行插入操作，通freemem()来清空栈中所有的元素，通过使用free()函数来释放top的地址。通过函int saveanddisplay(int hang)输出显示输入的所有元素。

1 实现流程 在函数的开始定义了三个指向struct text结构体的指针变量p1,p2,p3。输入要删除的两个行号（比如1 3），表示删除从第1行到第3行的数据。程序流程图如图3-2所示。 函数实现: 执行行删除功能时，由主函数调用删除函数删除所需删除行，再调用显示函数，显示执行行删除后的文本。 int del(textp head)//删除d命令对应的函数，用来删max－min中的行，用结构体中的flat表示是否被删除

2 伪代码实现

1 实现流程 行插入函数的开始定义了三个指向struct text结构体的指针变量p,p1,p2,在给hang赋初值后使p1指向头结点,利用for循环，找到要插入行的前一行hang-1，然后 给插入的行分配内存空间。输入文本内容并连入链表。程序流程图如3-3所示。

2 伪代码实现

1 实现流程 打开文件函数定义了两个字符串 name[30],outname[30]，用来存储输入的文件名，然后用if语句判断文件是否存在，如果存在，则打开该文件，如果不存在，则显示打开文件失败，然后再判断要写入的文件是否存在，如果不存在，就新建一个要写入的文件，并要求用户输入文件名。流程如图3-4 所示。

2 伪代码实现

1 实现流程 活区切换函数实现活区之间的切换，把文本的每一页（20行）作为一个活区，可以逐页的把活区内容显示出来。在活区切换函数中定义了一个指向struct text结构体的指针变量p赋初值*p=NULL,当i小于20时，如果行没有被删除（flag=1）就通过fputs函数把活区内容写入到文件（out）流程图如3-5 所示。

显示函数display()在程序运行过程中经常得以调用，是行编辑程序中极其重要的一个函数。行编辑程序通过对显示函数display()的调用，在程序执行行插入、行删除等编辑功能后，输出编辑后的文本。 在活区显示中首先把文本内容链入链表，函数中用page来实现页码的自增。函数种定义了一个指向struct text结构体的指针变量p ,在文件fp非空和行号小于20的情况下，利用fgets函数使p->string从打开的文件fp中得到字符的值，然后输出每一行的行号和每一行的内容。其程序流程图如图3-6所示。

2 伪代码实现

1 在程序当中有中文字符 在开始调试时，出现以下所示的错误提示：

经过查找，发现错误字符并及时改正后就该提示就没有了。 2 在调试过程当中还出现了如下所示的错误提示：

通过网上查找错误提示，知道了原因，是因为主函数中调用的子函数没有原型声明，所以导致了该问题。修改方案：将主函数放到程序的最后面，让子函数在前面，这样就可以不用声明函数原型。 3 功能实现不健全： 在程序编写好之后，便开始在Visual C++ 6.0中编译执行程序，虽然程序没有错误，但是执行过程中插入可以实现，删除却实现不了，在仔细检验程序后，发现在执行过程中没有先打开文件，因此无法继续执行。再改正之后便可以得到正确的运行结果了。

1.时间复杂度O(n^3) 一个算法的时间复杂度，是指执行算法所需要的计算工作量。通常，对于一个给定的算法，我们要做两项分析。第一是从数学上证明算法的正确性，这一步主要用到形式化证明的方法及相关推理模式，如循环不变式、数学归纳法等。而在证明算法是正确的基础上，第二步就是分析算法的时间复杂度。算法的时间复杂度反映了程序执行时间随输入规模增长而增长的量级，在很大的程度上能很好的反映出算法的优劣与否。 一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行才能知道。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数越多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。n称为问题的规模，当n不断变化时，时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此，我们引入时间复杂度概念。一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n)，使得n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n))，称O（f(n)）为算法的渐进时间复杂度，简称时间复杂度。 在本次数据结构与算法的课程设计中，迪杰斯特拉算法花了比较多的时间。 Dijkstra 算法最简单的实现方法是用一个链表或者数组来存储所有顶点的集合 Q，所以搜索 Q 中最小元素的运算（Extract-Min(Q)）只需要线性搜索 Q 中的所有元素。这样的话算法的运行时间是 O(n2)。第一个FOR循环的时间复杂度是O（n），第二个FOR循环共进行一次n-1次，每次执行的时间是O(n)。所以总的时间复杂度是O(n2).由于本程序执行次数为n次，故该程序的时间复杂度为O(n^3)。 2.空间复杂度O(1) 一个程序的空间复杂度是指运行完一个程序所需内存的大小。利用程序的空间复杂度，可以对程序的运行所需要的内存多少有个预先估计。一个程序执行时除了需要存储空间和存储本身所使用的指令、常数、变量和输入 数据外，还需要一些对数据进行操作的工作单元和存储一些为现实计算所需信息的辅助空间。

测试数据：任意的TXT文件，只要每行不超过80个字符。进入程序的界面，出现命令的帮助信息，按任意键开始程序编辑。输入INPUT文件与OUTPUT文件的名字打开相应的文件 。输入P命令显示活区的内容。 其它的命令操作如下： 行插入格式： i 行删除格式： d[] 活区切换格式： n 清屏格式： c 帮助格式： h 最后输入e命令退出程序。 在程序运行初始状态，界面显示如下。提示用户输入任意键进行其他功能。

输入任意键后，用户可根据自己的要求，在输入文件名的情况下输入其他命令。下图是显示文件函数display()执行后的界面。

行插入执行过程。在键盘上输入i回车i1i2后，在文本第二行插入i1i2字符串。

输入行删除命令d后，用d1 1便可删除第一行。而原来状态下的第二行变为第一行显示。

图5-6 执行行删除

输入活动区切换等指令后，便会出现以下界面。

此文本为该程序的输入文件a.txt，储存文本文档于计算机D盘，将其用于程序执行

计算机中存储的文本b.txt本是一个空文本文档，但在执行完程序后，文本中出现了程序运行的最终结果。这是在退出后的最终结果。在文本每行中添加了标号。

程序调试总结： 通过对该题目的编写调试以及结果显示可以看出，本程序可以满足任务书的要求，实现了对行的插入、删除、活区显示、活区 切换等各项要求。在执行插入命令的过程中，要检验活区的大小，如果插入这一行之后，仍保持不超的话，就将其插入。在输入未读完时，可将未读完的内容保持在活区的顶部。此外，也实现了一些简单的操作，例如，创建了一个链表，实现文本文件的打开，实现以行为单位是很合理的。通过这次课设，了解简单行编辑程序应用的广泛性。本课程设计的简单行编辑程序各功能的运行操作十分快捷，能满足用户的需要。

本次课程设计的内容是简单行编辑程序。经过一个周，我完成了本次课程设计，过程可谓曲折。在此过程中，构思，编写程序代码的过程是最花费时间的，对于我而言，编写一个简单行编辑程序有些困难，每天对着电脑，查阅各种资料。在程序的调试中,经常会遇到这样那样的错误，有的是因为对基本知识点不熟悉，造成的语法错误，有的是由于粗心，造成的错误，所以导致了程序的不能正常运行。每个实验通常都要花很长时间才能够理清一个程序的思路，而且要不断地调试程序，同时还要做到界面的美化。在此期间，整个课程设计的过程中让我严肃认真的对待本次课程设计，所以让我很回味这整个过程，最终，在我们一起的努力下，最终完成了本次任务。 在这次课程设计中，使我懂得了理论与实际相结合是非常重要的。只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，才能提高自己的思考和解决问题以及实际动手能力。同时也巩固和加深了我对数据结构的进一步掌握， 提高综合运用本课程所学知识的能力，培养了我运用参考书，查阅手册及文献资料的能力，培养独立思考，深入研究，分析问题，解决问题的能力。通过实际对编译系统的分析设计，编程调试，掌握应用软件的分析方法和设计方法。而且，在做课程设计的同时也是对课本知识的巩固和加强，平时看课本时，有些问题就不是很理解，做完课程设计，这些问题就迎刃而解了,还可以记住很多东西。 认识来源于实践，实践是认识的最终目的，所以这个学期期末的数据结构课程设计对我来所作用非常大，让我更加了解数据结构的重要性，它将会在我的专业发展中发挥重要的作用。有了这次课程设计，我相信在以后的课程设计制作中，能够轻松并高质量的完成。

[1]谭浩强.C语言程序设计(第2版)学习指导.北京：清华大学出版社,2009. [2]杨莉,龚义建.C语言程序设计实训指导教程.武汉：华中科技大学出版社,2009. [3]张小东,郑宏珍.C语言程序设计与应用.北京：人民邮电出版社，2009. [4]郭翠英.C语言课程设计案例精编.北京：中国水利水电出版社，2004. [5]伍一,孔凡辉,孙柏祥.数据结构应用教程(第二版).清华大学出版社，2012. [6]胡学刚.数据结构(c语言版).北京：高等教育出版社，2007.

在拿到课题之初，说实话有些迷茫。不知道这次的课程设计该从何入手，通过老师讲解后，才对本次任务的流程有了大致的了解，至少知道了该去找哪方面的资料。在热心的学长学姐的帮助下，我们找到了最适合于本次课程设计的参考资料。经过认真编写，仔细审查，反复修改多次后，终于完成了本次课程设计。 在此，向指导我们完成本次课程设计的两位老师——X老师和S老师致以衷心的感谢，感谢两位老师在百忙之中抽出时间解答我们的困惑，感谢两位老师认真细致得检查我们的程序和文档，这对于我们完成本次课程设计任务起到了极大的帮助，是最关键的一部分，若是缺少了老师的帮助，本次课程设计仅凭我们自己的能力是极其困难的。再次表示感谢！ 另外，对在本次课程设计中，热心得把自己的经验倾囊相授的学长学姐们表示感谢，你们的成功经验给予了我们极大的启迪，使我们少走了很多弯路，才能更有效率得完成本次课程设计任务。 最后，向在我们完成课程设计过程中给予我们支持与鼓励的同班同学表示感谢。