课 程 设 计
（数据结构）
| 班 级 | 计科0901班 |
| 姓 名 | 许山蒙 |
| 学 号 | 0911051002 |
| 指导教师 | 张先伟 |
课程设计任务书及成绩评定
| 课题名称 | 文章编辑 |
1、设计目的
巩固和加深对数据结构的理解，通过上机实验、调试程序，加深对课本知识的理解，最终使学生能够熟练应用数据结构的知识写程序。
（1）通过本课程的学习，能熟练掌握几种基本数据结构的基本操作。
（2）能针对给定题目，选择相应的数据结构，分析并设计算法，进而给出问题的正确求解过程并编写代码实现。
2、设计题目要求：
功能：输入一页文字，程序可以统计出文字、数字、空格的个数。
静态存储一页文章，每行最多不超过80个字符，共N行；要求（1）分别统计出其中英文字母数和空格数及整篇文章总字数；（2）统计某一字符串在文章中出现的次数，并输出该次数；（3）删除某一子串，并将后面的字符前移。
存储结构使用线性表，分别用几个子函数实现相应的功能；
输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。
输出形式：（1）分行输出用户输入的各行字符；（2）分4行输出"全部字母数"、"数字个数"、
"空格个数"、"文章总字数"（3）输出删除某一字符串后的文章
Ⅱ、设计进度及完成情况
| 日 期 | 内 容 |
| 1.10-1.11 | 选取参考书，查阅有关文献资料，完成资料搜集和系统分析工作。 |
| 1.12~1.14 | 创建相关数据结构,录入源程序。 |
| 1.17~1.19 | 调试程序并记录调试中的问题，初步完成课程设计报告。 |
| 1.20~1.21 | 上交课程设计报告打印版并进行课程设计答辩，要求每个同学针对自己的设计回答指导教师3-4个问题。 |
| 考核结束后将课程设计报告和源程序的电子版长统一刻光盘上交。 |
[1] 严蔚敏 数据结构（C语言版）清华大学出版社 1999
[2] 严蔚敏 数据结构题集（C语言版）清华大学出版社 1999
[3] 谭浩强 C语言程序设计 清华大学出版社
[4] 与所用编程环境相配套的C语言或C++相关的资料
Ⅳ、成绩评定：
设计成绩： （教师填写）
指导老师： （签字）
二○一一 年 一 月 二 十一 日
第一章 概述……………………………………………………………… 1
第二章 系统分析………………………………………………………… 2
第三章 概要设计………………………………………………………… 3
第四章 详细设计………………………………………………………… 5
第五章 运行与测试…………………………………………………… 14
第六章 总结与心得…………………………………………………… 18
参考文献……………………………………………………………… 19
第一章概述
课程设计是实践性教学中的一个重要环节，它以某一课程为基础，可以涉及和课程相关的各个方面，是一门于课程之外的特殊课程。课程设计是让同学们对所学的课程更全面的学习和应用，理解和掌握课程的相关知识。《数据结构》是一门重要的专业基础课，是计算机理论和应用的核心基础课程。
数据结构课程设计，要求学生在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。
在这次的课程设计中我选择的题目是文章编辑。文章编辑主要包括文章进行修改，删除，统计文章字数信息等操作，但是人工的文章编辑操作起来效率相对来说很低，也比较容易出错。但是借助计算机系统来进行文章编辑后，效率可以得到很大提升，也能降低出错率，可以使文章编辑更方便、更高效。
第二章 系统分析
1．文章编辑的基本功能包括：统计文章中的字数信息；查询某一个词在文章中出现的次数；删除文章中出现的某一个词。要实现上述功能，需要建立基于顺序储存结构的线性表，来存储文章的内容。
2．演示程序是以用户与计算机的对话方式执行，这需要一个模块来完成使用者与计算机语言是转化，这一模块是直接写在主程序里面的。
3.程序执行时的命令：本程序为了使用时的方便，采用菜单式的方式来完成程序的演示，几乎不用输入什么特殊的命令，只需按提示输入选择即可。
4. 测试数据:分别对不同功能测试几组不同的数据。具体内容见运行测试。
5. 程序流程图：
第三章 概要设计
本章主要介绍
1、数据结构的设计
实验主要采用基于顺序储存结构的线性表，用一维数组表示。
2、算法的设计
void count(char str[])
统计文章全部字母数、数字个数、空格个数、文章字符总数，并输出到屏幕上。
void strcount(char str[], char temp[])
统计字符串temp[]在文章中出现的次数。
void strdelete(char str[],char temp[])
删除文章中的字符串temp[]。
int KMP(int k,char str[],char temp[])
查找模式串在主串中第k个字符后的第一个位置，若模式串不在主串中，返回-1。
3、抽象数据类型的 设计
ADT Article{
数据对象：D = { ai|ai∈ElemSet,i=1,2,…,n,n≥0 }
数据关系：R1 = { 基本操作： init( &Arti ) 操作结果：构造一篇空文章 input(&Arti) 初始条件：文章Arti已存在 操作结果：输入文章 continue_input(&Arti) 初始条件：文章Arti已存在 操作结果：继续输入文章 del(&Arti , pos, k) 初始条件：文章Arti已存在 操作结果：删除文章中pos位置后的k个字符 count(&Arti) 初始条件：文章Arti已存在 操作结果：统计文章全部字母数、数字个数、空格个数、文章字符总数 strcount(&Arti ,temp) 初始条件：文章Arti已存在 操作结果：统计模式串在主串中出现的次数 strdelete(&Arti temp,t) 初始条件：文章Arti已存在 操作结果：在主串中删除第t个模式串相应字符，若t为0，则全删除 empty(&Arti) 初始条件：文章Arti已存在 操作结果：判断文章是否为空 lengh(&Arti) 初始条件：文章Arti已存在 操作结果：文章长度 clear(&Arti) 初始条件：文章Arti已存在 操作结果：清空文章 output(&Arti) 初始条件：文章Arti已存在 操作结果：输出文章 } ADT Article 第四章 详细设计 1、抽象数据类型对应的类定义。 class Article //文章 { private: char str[1000]; public: Article() { str[0]='\\0'; } void input(); //输入文章 void continue_input(); //继续输入文章 void del(int pos,int k); //删除文章中pos位置后的k个字符 void count();//统计文章全部字母数、数字个数、空格个数、文章字符总数 int strcount(char temp[]);//统计模式串在主串中出现的次数 int strdelete(char temp[],int t);//在主串中删除第t个模式串相应字符，若t为0，则全删除 bool empty(); //判断文章是否为空 int lengh() //文章长度 { return strlen(str); } void clear() //清空文章 { str[0]='\\0'; } void output() //输出文章 { printf("%s\\n",str); } }; Article arti; 2、成员函数及其他子函数。 //输入新文章 void Article::input() { int i=0; char c; printf("请输入文章，以'#'结束：\n"); getchar(); while(1) { c=getchar(); if(c=='#') break; str[i]=c; i++; } if(i==0) printf("您没有输入文章！\n"); else { str[i]='\\0'; printf("文章输入成功！\n"); } } //继续输入文章 void Article::continue_input() { int i,j; char c; i=strlen(str); j=i; if(i==0) printf("提示：原文章为空！请输入文章，以'#'结束：\n"); else printf("请继续输入文章，以'#'结束：\n"); getchar(); while(1) { c=getchar(); if(c=='#') break; str[i]=c; i++; } if(i==j) printf("您没有继续输入文章！\n"); else { str[i]='\\0'; printf("文章输入成功！\n"); } } //删除pos位置之后的k个字符 void Article::del(int pos,int k) { int i; for(i=pos+k-1;str[i]!='\\0';i++) { str[i-k]=str[i]; } str[i-k]='\\0'; } //统计文章全部字母数、数字个数、空格个数、文章字符总数 void Article::count() { int letter=0,number=0,blank=0,all=0; int i=0; while(str[i]!='\\0') { if(isalpha(str[i])) letter++; else if(isdigit(str[i])) number++; else if(str[i]==' ') blank++; if(str[i]!='\\n') all++; i++; } printf("文章字符统计信息如下：\n"); printf("字母个数：%d\\n",letter); printf("数字个数：%d\\n",number); printf("空格个数：%d\\n",blank); printf("字符总数：%d\\n",all); } //取得模式串的next值 void get_next(char temp[],int next[]) { int i=0,j=-1; int len=strlen(temp); next[0]=-1; while(i while(j>-1||temp[i]==temp[j]) j=next[j]; i++; j++; if(temp[i]==temp[j]) next[i]=next[j]; else next[i]=j; } } //KMP算法，返回模式串在主串中第k个字符后的第一个位置，若模式串不在主串中，返回-1 int KMP(int k,char str[],char temp[]) { int pos=-1;//模式串在主串中的位置 int i,j; int len1,len2;//主串与模式串的长度 int next[81];//KMP算法中模式串的next值 len1=strlen(str); len2=strlen(temp); get_next(temp,next); i=k;j=0; while(i while(j>-1&&str[i]!=temp[j]) j=next[j]; i++; j++; if(j>=len2) { pos=i-j+1; break; } } return pos; } //统计模式串在主串中出现的次数 int Article::strcount(char temp[]) { int num=0,len=strlen(temp); int pos=0; while(1) { pos=KMP(pos,str,temp); if(pos>=0) num++; else break; } return num; } //在主串中删除第t个模式串相应字符，若t为0，则全删除 int Article::strdelete(char temp[],int t) { int num=0,len=strlen(temp); int pos=0; while(1) { pos=KMP(pos,str,temp); if(pos>=0) { num++; if(t==0) arti.del(pos,len); else if(num==t) arti.del(pos,len); } else break; } return num; } //判断文章是否为空 bool Article::empty() { if(str[0]=='\\0') return true; else return false; } //显示菜单 void order() { printf("\\n →[菜单]←\n"); printf(" 1、输入新文章 || 6、统计字符串出现次数\n"); printf(" 2、继续输入文章 || 7、删除字符串\n"); printf(" 3、清空当前文章 || 8、查看菜单\n"); printf(" 4、输出当前文章 || 9、查看学生信息\n"); printf(" 5、统计文章字符信息 || 0、退出\n\\n"); } //输入模式串 void input_temp(char temp[],int t) { int i=0; char c; if(t==0) printf("请输入要查询的字符串，以'#'结束：\n"); else printf("请输入要删除的字符串，以'#'结束：\n"); getchar(); while(1) { c=getchar(); if(c=='#') break; temp[i]=c; i++; } if(i==0) printf("您没有输入字符串！\n"); else { temp[i]='\\0'; printf("字符串输入成功！\n"); } } 3、主函数。 int main() { int num; char com[81]="\\0";//命令 char temp[81]="\\0";//模式串 printf(" -====文章编辑====-\\n\\n"); order(); while(1) { printf("\\n请输入命令编号："); scanf("%s",com); if(strcmp(com,"1")==0) { arti.input(); } else if(strcmp(com,"2")==0) { arti.continue_input(); } else if(strcmp(com,"3")==0) { if(arti.empty()) printf("您还未输入文章或文章内容已为空,请先输入文章！\n"); else { arti.clear(); printf("文章清除成功！\n"); } } else if(strcmp(com,"4")==0) { if(arti.empty()) printf("您还未输入文章或文章内容已为空,请先输入文章！\n"); else arti.output(); } else if(strcmp(com,"5")==0) { if(arti.empty()) printf("您还未输入文章或文章内容已为空,请先输入文章\n"); else arti.count(); } else if(strcmp(com,"6")==0) { if(arti.empty()) printf("您还未输入文章或文章内容已为空,请先输入文章\n"); else { input_temp(temp,0); if(strlen(temp)>0) { printf("该字符串在文章出现了%d次！\n",arti.strcount(temp)); } } } else if(strcmp(com,"7")==0) { if(arti.empty()) printf("您还未输入文章或文章内容已为空,请先输入文章\n"); else { input_temp(temp,1); if(strlen(temp)>0) { num=arti.strcount(temp); if(num==0) printf("该字符串在文章中没有出现！\n"); else if(num==1) { arti.strdelete(temp,0); printf("该字符串在文章出现了1次！已成功删除！\n"); } else { int t; printf("该字符串在文章出现了%d次！若要删除单一字符串，请输入字符串序号1-%d，若要全部删去，请输入0 : ",num,num); while(1) { scanf("%d",&t); if(t<0||t>num) printf("您输入的编号超出范围!请重新输入："); else { arti.strdelete(temp,t); printf("删除成功！\n"); break; } } } } } } else if(strcmp(com,"8")==0) { order(); } else if(strcmp(com,"9")==0) { printf("\\n"); printf("姓 名：许山蒙\n"); printf("班 级：计科0901班\n"); printf("学 号：0911051002\\n"); printf("课 程：《数据结构》\n"); printf("指导教师：张先伟\n\\n"); } else if(strcmp(com,"0")==0) { printf("\\n确认退出y/n:? "); scanf("%s",com); if (strcmp(com,"y")==0) { printf("\\n感谢使用，再见！\n\\n"); break; } } else { printf("\\n命令输入错误，请重新输入，或者输入8查看菜单。\n"); } } return 0; } 第五章 运行与测试 1、在调试程序的过程中遇到的问题及解决办法： 开始的时候当有异常输入时便无法执行程序。现加入异常处理环节，可以判断输入数据是否合法，这一问题得到解决。 2、测试数据及测试结果： （1）程序开始运行界面，如下图： （2）输入下面的测试文章： Yesterday is history, tomorrow is mystery, but today is a gift, that is why it is called Present. 3.14159265357932384623388279502 然后以“#”结束。 若输入成功，系统会给予提示。如下图： （3）统计文章字符信息，如下图： （4）查询字符串“is”在文章中出现的次数，如下图： （5）删除字符串“is”,并输出删除“is”后的文章，如下图： （6）当命令输入错误时会有提示，输入“8”可以查看菜单如下图： （7）退出，如下图： 第六章 总结与心得 本程序相对来说很简单，思路和算法都比较清晰，难度也不算大，只有KMP算法交较复杂一下。不过程序还有一些不足之处：本程序只能对即时输入的文章进行编辑，而不能对存储在磁盘里的文章进行编辑，如果能从文件输入数据，就可以打开磁盘文件，对其进行编辑，这还有待改进。 通过做课程设计我再一次熟悉了线性表的基本知识和操作，特别是仔细研究了一下KMP算法，对KMP算法的原理和过程有了更深的理解。这次的课程设计收获了很多，也感谢各位老师的指导。 参考文献: [1] 严蔚敏、吴伟民主编 《数据结构》（C语言版） 清华大学出版社 2002 [2] 殷人昆等著 《数据结构》（C++版） 清华大学出版社 2001 [3] 金远平著 《数据结构》（C++描述） 清华大学出版社 2005 [4] 许卓群等著 《数据结构与算法》 高等教育出版社 2004 [5] Frank M.Carrano 等著 《数据结构与Ｃ++高级教程》清华大学出版社 2004 [6] 严蔚敏、吴伟民 《数据结构习题集》（C语言版）清华大学出版社 下载本文
