新版数据结构课程设计.doc

数据结构课 程 设 计 报 告 书题 目： 文本文献单词的检索与计数 专 业： 网络工程 学 号： 学生姓名： 张钦昆 指导教师： 王初阳 完毕日期： 2023/6/7 目 录1 设计任务书21.1 题目与规定21.2 知识点21.3 输入输出分析21.4 测试数据分析22 概要设计32.1 结构体类型及函数声明32.2 主程序流程32.3 模块流程说明43 具体设计83.1 数据类型实现83.2 程序代码84 调试分析174.1 问题分析与回顾174.2 算法时空分析174.3 算法改善174.4 经验和体会175 测试结果18参考文献23评分标准.241 设计任务书1.1 题目与规定题目：文本文献单词的检索与计数。规定：编程建立一个文本文献，每个单词不包含空格且不跨行，单词由字符序列构成且区分大小写；记录给定单词在文本文献中出现的总次数；检索输出某个单词出现在文本中的行号、在该行中出现的次数以及位置。建立文本文献，文献名由用户用键盘输入；给定单词的计数，输入一个不含空格的单词，记录输出该单词在文本中的出现次数；检索给定单词，输入一个单词，检索并输出该单词所在的行号、该行中出现的次数以及在该行中的相应位置。1.2 知识点 串的应用、文献、结构体、指针、数组、函数、函数的调用、循环语句、选择语句、输入输出控制、自定义类型等。1.3 输入输出分析（1）普通输入在文本文献的建立中，需要先定义串变量和文本文献，从而建立文本文献；根据实际情况，将单词的长度定义为20，规定每行最多输入110个字符。（2）对话式输入为便于转换及比较，对话式输入采用字符数组进行存储.为保障程序的健壮性，同时限制对话式输入的格式，对于非法的会话式输入则提醒用户操作失败的因素。（3）程序输出为了能让程序输出时更加美观，程序输出重要以整齐为主，使得输出的程序结果均整齐输出。1.4 测试数据分析在建立文本文献名时，规定键盘输入所建立的文本文献的名称，假如所输入的文本文献名称超过所给定的字符，将提醒输入错误，请重新输入。在第二次输入文本文献名称以供在此文本文献中查找所给定的单词，假如用户输入的文本文献名称与第一次不符或输入为空，系统将提醒输入错误，请重新输入。在主控程序中，规定输入执行指令14，假如输入非14字符，系统将提醒输入错误，请重新选择2 概要设计2.1 结构体类型及函数声明（1）结构体1. typedef struct /* 定义顺序串类型 */ char chMaxStrSize; int length; string;2. typedef struct /*记录单词出现的次数*/ char wordWORD_LEN; int count; elem_type; 3. typedef structelem_type *elem; /*存储空间基址*/int length; /*当前长度*/int listsize; /*当前分派的存储容量*/ sqlist; 函数：1.建立文献：void creat_text_file()2.单词记录：void sqlist_add(sqlist *sq, elem_type *et, char *word)3.文本文献中单词的总汇：void substrsum()4.单词的定位：void substrcount()5.主函数：int main()2.2 主程序流程（1）主程序调用模块图主程序运用switch()语句实现各个模块的调用，主函数调用如图1所示。主程序根据不同数值调用函数1建立文本文献2给定单词计数3检索单词在文本中的位置图1 主程序调用模块图2.3 模块流程说明主函数对各重要模块进行调用，各个重要模块又分别调用其他子模块。下面用简要流程图对各重要模块进行说明。（1）建立文本文献主模块如图2所示，建立文本文献模块。一方面定义一个串变量，然后调用void creat_text_file()函数，定义文本文献，键盘输入文献名，打开该文献，循环读入文本行，写入文本文献，最后关闭文献。开始定义一个串变量调用void creat_text_file()函数，定义文本文献键盘输入文献名打开文献，循环读入文本行，写入文本文献关闭文献、图2 建立文本文献模块 （2）给定单词的计数主模块如图3所示为给定单词计数程图。 其实现过程如下；一方面输入要检索的文本文献名，打开相应的文献，然后输入要检索记录的单词，循环读文本文献，读入一行，将其送入定义好的串中，并求该串的实际长度，调用串匹配函数进行计数。数最后关闭文献，输出记录结果开始输入要检索的文本文献名，打开相应文献输入要检索记录的单词使用while循环语句，调用sqlist_add(&sq, et, word)函数，循环读文本文献，送入定义好的串中关闭文献求该串的实际长度，调用串匹配函数partposition(s,t,k)进行计数，输出记录结果 图3单词计数模块 （3）主控程序模块如图4为中控程序流程图。过程如下：输入头文献使用循环语句输出一下4个执行指令：1. 建立文本文档2. 文本单词汇总 3. 给定单词定位4. 退出 如输入非14的指令，系统将提醒，输入错误请重新输入。结束。开始输入头文献输入四个执行指令输入的是否为14的执行指令？ 否 是提醒：输入错误，请重新输入执行相应指令结束图4 主控程序模块3 具体设计3.1 数据类型实现 结构体：1. typedef struct /* 定义顺序串类型 */ char chMaxStrSize; int length; string;2. typedef struct /*记录单词出现的次数*/ char wordWORD_LEN; int count; elem_type; 3. typedef structelem_type *elem; /*存储空间基址*/int length; /*当前长度*/int listsize; /*当前分派的存储容量*/ sqlist; 函数：1. 建立文献：void creat_text_file()2. 单词记录：void sqlist_add(sqlist *sq, elem_type *et, char *word)3. 文本文献中单词的总汇：void substrsum()4. 单词的定位：void substrcount()5. 主函数：int main()3.2 程序代码 #include #include #include #define LIST_INIT_SIZE 500 /*线性表存储空间的初始分派量*/ #define LISTINCREMENT 10 /*线性表存储空间的分派增量*/ #define FILE_NAME_LEN 20 /*文献名长度*/ #define WORD_LEN 20 /*单词长度*/ #define MaxStrSize 256 #define llength 110 /*规定一行有110个字节*/ typedef struct char chMaxStrSize; /* ch是一个可容纳256个字符的字符数组 */ int length; string;/* 定义顺序串类型 */ typedef struct char wordWORD_LEN; /*存储单词，不超过20个字符*/int count; /*单词出现的次数*/ elem_type; typedef structelem_type *elem; /*存储空间基址*/int length; /*当前长度*/int listsize; /*当前分派的存储容量*/ sqlist; void sqlist_init(sqlist *sq, elem_type *et) sq-elem = et; sq-length = 0; void sqlist_add(sqlist *sq, elem_type *et, char *word) int i; int j; for (i = 0; i length; i+) /*当前单词与加入的单词相同，直接记录，不做插入 */ if (strcmp(eti.word, word) = 0) eti.count+; return; if (strcmp(eti.word, word) 0)break;if (sq-length = LIST_INIT_SIZE)printf(空间局限性，单词%s插入失败n, word);return;for (j = sq-length; j i; j-)memcpy(et+j, et+j-1, sizeof(elem_type);sq-length+;strcpy(eti.word, word);eti.count = 1; int sqlist_count(sqlist *sq, elem_type *et) int i; int j=0; for(i=0;ilength;i+) j=j+eti.count; return j; void creat_text_file() elem_type w; sqlist s; char file_nameFILE_NAME_LEN + 1,yn; FILE *fp; printf(输入要建立的文献名：); scanf(%s,file_name); fp=fopen(file_name,w); yn=n; /* 输入结束标志初值 */ while(yn=n|yn=N) printf(请输入一行文本：); gets(w.word); gets(w.word); s.length=strlen(w.word); fwrite(&w,s.length,1,fp); fprintf(fp,%c,10); /* 是输入换行 */ printf(结束输入吗？y or n ：);yn=getchar(); fclose(fp); /* 关闭文献 */ printf(建立文献结束!n); void substrsum()char file_nameFILE_NAME_LEN + 1;char wordWORD_LEN+1;FILE *fp;int i;int j,q=0;int w,x,y=0;elem_type etLIST_INIT_SIZE;sqlist sq;sqlist_init(&sq, et);printf(请输入文献名：);scanf(%s, file_name);fp = fopen(file_name, r);if (fp = NULL)printf(打开文献失败!n);return;while (fscanf(fp, %s, word) != EOF)sqlist_add(&sq, et, word);fclose(fp);printf( 单词 个数n);for (i = 0; i =0;w-)if(eti.wordw90&eti.wordw122)eti.wordw= ;for(w=0;wx;w+)if (eti.wordw= )y+;if(y=x)eti.count=0;y=0;else y=0;if(eti.count!=0)printf(%20s%10dn, eti.word, eti.count);else q+;j=sqlist_count(&sq, et); printf(n%s的单词总数为%d个n,file_name,j);printf(n%s的非单词个数为%d种n,file_name,q);printf(n); int partposition (string s1,string s2,int k)int i,j;i=k-1; /* 扫描s1的下标，由于c中数组下标是从0开始，串中序号相差1 */j=0; /* 扫描s2的开始下标 */while(is1.length & j=s2.length)return i-s2.length; /* 表达s1中存在s2，返回其起始位置 */elsereturn -1; /* 表达s1中不存在s2，返回-1 */ /* 函数结束 */ void substrcount()FILE *fp;string s,t; /* 定义两个串变量 */char fname10; int i=0,j,k;printf(输入文本文献名：);scanf(%s,fname);fp=fopen(fname,r);printf(输入要记录计数的单词：);scanf(%s,t.ch);t.length=strlen(t.ch);while(!feof(fp)memset(s.ch,0,110);fgets(s.ch,110,fp);s.length=strlen(s.ch);k=0; /* 初始化开始检索位置 */while(ks.length-1) /* 检索整个主串S */j=partposition(s,t,k); /* 调用串匹配函数 */if(j0 ) break;elsei+; /* 单词计数器加1 */ k=j+t.length; /* 继续下一字串的检索 */printf(n单词%s在文本文献%s中共出现%d次n,t.ch,fname,i);/* 记录单词出现的个数 */ void substrint()FILE *fp;string s,t; /* 定义两个串变量 */char fname10;int i,j,k,l,m;int wz20; /* 存放一行中字串匹配的多个位置 */printf(输入文本文献名：);scanf(%s,fname);fp=fopen(fname,r);printf(输入要检索的单词：);scanf(%s,t.ch);t.length=strlen(t.ch);l=0; /* 行计数器置0 */while(!feof(fp) /* 扫描整个文本文献 */ memset(s.ch,0,110);fgets(s.ch,110,fp);s.length=strlen(s.ch);l+; /* 行计数器自增1 */k=0; /* 初始化开始检索位置 */i=0; /* 初始化单词计数器 */while(ks.length-1) /* 检索整个主串S */j=partposition(s,t,k); /* 调用串匹配函数 */if(j0)printf(行号：%d,次数：%d,位置分别为：,l,i);for(m=1;m=i;m+)printf(第%4d个字符,wzm+1);printf(n);printf(n本软件自定义110个字节为一行nn); /* 检索单词出现在文本文献中的行号、次数及其位置 */void substrio()void substrcount(),substrint();char t;while(1)printf(=n);printf( 请输入:); printf(|文本文献单词字串的定位记录及定位|n);printf(|=|n);printf(| a. 单词出现次数 |n);printf(| |n);printf(| |n);printf(| b. 单词出现位置 |n);printf(| |n);printf(=n);scanf(%c,&t);switch(t) case a: substrcount();break;case b: substrint();break;default: return;int main()void creat_text_file(),substrsum(),substrio();int xz;while(1)printf(=n);printf(| 文本文献的检索、字串的记录及定位 |n);printf(|=|n);printf(| 1. 建立文本文献 |n);printf(| 2. 单词字串的计数 |n);printf(| 3. 单词字串的定位 |n);printf(| 4. 退出整个程序 |n);printf(=n);printf( 请选择(1-4)n );scanf(%d,&xz);switch(xz)case 1: creat_text_file();break;case 2: substrsum();break;case 3: substrio();break;case 4: return 0;default:printf(选择错误，重新选 n);return 0; 4 调试分析4.1 问题分析与回顾问题1：在语句“请输入一行文本”后边，只写一句接受语句，结果运营时，请输入文本和结束输入吗？演示在一起，并且不能接受文本输入。解决：和同学讨论后，加入了文本接受语句，成功运营。问题2：当要检索文本时，输入为空，或输入非建立的文本文献名，系统不能正常运营。分析：缺少判断语句。解决：当出现这种情况时，系统提醒输入错误，请重新输入。4.2 算法时空分析拟定给定单词出现的个数，需要记录文本文献中所有的单词，因此时间复杂度为O(n);拟定给定单词出现的位置，需要显示其所在的行和列，时间复杂度为O(i*l);4.3 算法改善此算法虽然基本实现了功能，但却仍存在许多局限性，例如当当前建立的文献名与之前相同时，没有错误提醒，另如在对单词的检索方面，时间复杂度及空间复杂度仍不尽如人意。仍需要改善代码，达成算法的高效性。4.4 经验和体会通过本次数据结构的课程设计，让我对数据结构这门课有了更加深刻的结识。数据结构这门课程的理论性只是较强，要学好这门课程，就必要在掌握好理论知识的同时，加强上机操作，碰到问题，解决问题，这样才会有更大的进步。 我课程设计的题目是文献文本的检索与计数，由于这个课题要用到串的知识。而我对之前对串的定义却不是很明确，于是我有具体的学习了课本上的知识并查阅了很多文献。在着手作程序的过程中，经常碰到程序运营不出来，运营达不到效果等问题，特别是接受文本，搜索时如何定位等方面碰到了很多问题。但我通过请教老师和同学，查阅文献，然后基本上解决了这些问题。在这个过程中我学到了很多，我结识到了坚持不懈的重要性，在我一遍一遍的调试下，终于成功的写出了程序。在编写本次程序时，我学会了先用流程图对进行算法分析，这样是自己的思绪更加清楚，而不是像之前那样对整个函数没有整体的认知，而导致经常无从下手。之前我对数据结构的各种算法都感到畏惧，感觉很抽象，而这次通过自己几周的努力，在老师和同学们的帮助下，终于完毕了本次课程设计，这对我来说无疑是极大的鼓舞，极大的增强了我学数据结构的自信心。并且我也充足结识到数据结构自身就是一门实践性很强的课程，只有加强实践，才干学得更好！5 测试结果（1） 输入建立文献名如图5所示为输入建立文献测试图5输入建立文献测试（2） 输入一行文本测试如图6所示建立一行文本，建立文献结束界面。 图6 建立文献结束测试（3）单词字串的计数测试如图7，单词字串的计数测试界面。图7 单词字串的计数测试（4）单词字串的定位测试如图8和图9所示。 图8单词字串的定位测试 图9 单词字串的定位测试（5）程序结束退出，如图10所示图10 程序结束退出 参考文献1 严蔚敏，吴伟民数据结构（C语言版）北京：清华大学出版社，20232 蒋清明，向德生 C语言程序设计 北京：人民邮电出版社，20233 尹德淳，龙脉工作室C函数速查手册 北京：人民邮电出版社，20234 闵敏，朱辉生数据结构高等教育出版社 编著 2023.45 张世和数据结构清华大学出版社 2023.116 李玲玲C程序设计清华大学出版社7 郑莉，董渊C+程序设计基础教程 清华大学出版社。8 社尹德淳C函数速查手册M北京：人民邮电出版，龙脉工作室20239 林小茶C语言程序设计10朱鸣华C语言程序设计教程11蒋文蓉数据结构高等教育出版社 2023.2 评分标准程序（80）对的性（50）完毕规定功能测试无错误（41-50）完毕所有重要功能但有少许错误（31-40）完毕一些功能但有错误（1-30）不能运营（0）创新性（10）比题目规定多完毕三个功能以上（7-10）（1）假如对的性不能达成40分，创新性不予考虑。（2）规定多完毕的功能必须能反映出工作量，否则不予以加分。比题目规定多完毕两个功能（4-6）比题目规定多完毕一个功能（1-3）仅完毕题目规定（0）注释丰富限度（20）注释清楚（11-20）较多（6-10）少许（0-5）报告（30）层次、结构、逻辑性（10）合理（5-10）不甚合理（0-4）语言表达能力（10）行文流畅且仅有不多于5个错别字（5-10）不太通顺且有多于5个错别字（0-4）版面（10）版面整洁，布局合理（5-10）版面混乱，布局不合理（0-4）总分由于有创新分，有也许超过100分，超过者按100分算五级制成绩教 师 签 名： 批 改 日 期： 年 月 日