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

《数据构造》

课 程 设 计 报 告 书

题 目： 文本文献单词检索与计数
专 业： 网络工程
学 号：
学生姓名： 张钦昆
指引教师： 王初阳
完毕日期： /6/7

目 录
1 设计任务书 2
1.1 题目与规定 2
1.2 知识点 2
1.3 输入输出分析 2
1.4 测试数据分析 2
2 概要设计 3
2.1 构造体类型及函数声明 3
2.2 主程序流程 3
2.3 模块流程阐明 4
3 详细设计 8
3.1 数据类型实现 8
3.2 程序代码 8
4 调试分析 17
4.1 问题分析与回顾 17
4.2 算法时空分析 17
4.3 算法改进 17
4.4 经验和体会 17
5 测试成果 18
参照文献 23
评分原则..............................................................................24

1 设计任务书
1.1 题目与规定
题目：文本文献单词检索与计数。
规定：编程建立一种文本文献，每个单词不包括空格且不跨行，单词由字符序列构成且区别大小写；记录给定单词在文本文献中浮现总次数；检索输出某个单词出当前文本中行号、在该行中浮现次数以及位置。建立文本文献，文献名由顾客用键盘输入；给定单词计数，输入一种不含空格单词，记录输出该单词在文本中浮现次数；检索给定单词，输入一种单词，检索并输出该单词所在行号、该行中浮现次数以及在该行中相应位置。
1.2 知识点
串应用、文献、构造体、指针、数组、函数、函数调用、循环语句、选取语句、输入输出控制、自定义类型等。
1.3 输入输出分析
（1）普通输入
在文本文献建立中，需要先定义串变量和文本文献，从而建立文本文献；依照实际状况，将单词长度定义为20，规定每行最多输入110个字符。
（2）对话式输入
为便于转换及比较，对话式输入采用字符数组进行存储.为保障程序健壮性，同步限制对话式输入格式，对于非法会话式输入则提示顾客操作失败因素。
（3）程序输出
为了能让程序输出时更加美观，程序输出重要以整洁为主，使得输出程序成果均整洁输出。
1.4 测试数据分析
在建立文本文献名时，规定键盘输入所建立文本文献名称，如果所输入文本文献名称超过所给定字符，将提示输入错误，请重新输入。
在第二次输入文本文献名称以供在此文本文献中查找所给定单词，如果顾客输入文本文献名称与第一次不符或输入为空，系统将提示输入错误，请重新输入。
在主控程序中，规定输入执行指令1——4，如果输入非1——4字符，系统将提示输入错误，请重新选取

2 概要设计
2.1 构造体类型及函数声明
（1）构造体
1. typedef struct /* 定义顺序串类型 */
{
char ch[MaxStrSize]；
int length；
} string;
2. typedef struct /*记录单词浮现次数*/
{
char word[WORD_LEN]；
int count；
} elem_type；

3. typedef struct{
elem_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. 退出
如输入非1——4指令，系统将提示，输入错误请重新输入。
结束。

开始

输入头文献

输入四个执行指令

输入与否为1——4执行指令？

否
是
提示：输入错误，请重新输入
执行相应指令

结束

图4 主控程序模块

3 详细设计
3.1 数据类型实现

构造体：

1. typedef struct /* 定义顺序串类型 */
{
char ch[MaxStrSize]；
int length；
} string;

2. typedef struct /*记录单词浮现次数*/
{
char word[WORD_LEN]；
int count；
} elem_type；

3. typedef struct{
elem_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 <stdio.h>
#include <stdlib.h>
#include <string.h>
#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 ch[MaxStrSize]；/* ch是一种可容纳256个字符字符数组 */
int length；
} string;/* 定义顺序串类型 */
typedef struct
{
char word[WORD_LEN]； /*存储单词，不超过20个字符*/
int count； /*单词浮现次数*/
} elem_type；
typedef struct{
elem_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 < sq->length；i++)
{
/*当前单词与加入单词相似，直接记录，不做插入 */
if (strcmp(et[i].word，word) == 0)
{
et[i].count++;
return;
}
if (strcmp(et[i].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(et[i].word，word);
et[i].count = 1;
}
int sqlist_count(sqlist *sq，elem_type *et)
{
int i;
int j=0;
for(i=0;i<sq->length;i++)
j=j+et[i].count;
return j;
}
void creat_text_file()
{
elem_type w;
sqlist s;
char file_name[FILE_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_name[FILE_NAME_LEN + 1];
char word[WORD_LEN+1];
FILE *fp;
int i;
int j,q=0;
int w,x,y=0;
elem_type et[LIST_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 < sq.length；i++)
{
x=strlen(et[i].word);
for(w=x-1;w>=0;w--)
if(et[i].word[w]<65||(et[i].word[w]>90&&et[i].word[w]<97)||et[i].word[w]>122)
{
et[i].word[w]=' ';
}
for(w=0;w<x;w++)
if (et[i].word[w]==' ')
y++;
if(y==x)
{
et[i].count=0;
y=0;
}
else y=0;
if(et[i].count!=0)
printf("%20s%10d\n"，et[i].word，et[i].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(i<s1.length && j<s2.length)
{
if(s1.ch[i]==s2.ch[j])
{
i++;j++；/* 继续使下标移向下一种字符位置 */
}
else
{
i=i-j+1；j=0;
}
}
if (j>=s2.length)
return i-s2.length； /* 表达s1中存在s2，返回其起始位置 */
else
return -1； /* 表达s1中不存在s2，返回-1 */

}/* 函数结束 */
void substrcount()
{
FILE *fp;
string s,t； /* 定义两个串变量 */
char fname[10];
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(k<s.length-1) /* 检索整个主串S */
{
j=partposition(s,t,k)； /* 调用串匹配函数 */
if(j<0 ) break;
else
{
i++； /* 单词计数器加1 */
k=j+t.length； /* 继续下一字串检索 */
}
}
}
printf("\n单词%s在文本文献%s中共浮现%d次\n",t.ch,fname,i);/* 记录单词浮现个数 */
}
void substrint()
{
FILE *fp;
string s,t； /* 定义两个串变量 */
char fname[10];
int i,j,k,l,m;
int wz[20]； /* 存储一行中字串匹配各种位置 */
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(k<s.length-1) /* 检索整个主串S */
{
j=partposition(s,t,k)； /* 调用串匹配函数 */
if(j<0) break;
else
{
i++； /* 单词计数器加1 */
wz[i]=j； /* 记录匹配单词位置 */
k=j+t.length； /* 继续下一字串检索 */
}
}
if(i>0)
{
printf("行号：%d,次数：%d,位置分别为：",l,i);
for(m=1;m<=i;m++)
printf("第%4d个字符",wz[m]+1);
}
printf("\n");
}
printf("\n本软件自定义110个字节为一行\n\n")；
} /* 检索单词出当前文本文献中行号、次数及其位置 */
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语言版）．北京：清华大学出版社，．
[2] 蒋清明，向德生． C语言程序设计 ．北京：人民邮电出版社，．
[3] 尹德淳，龙脉工作室．C函数速查手册 ．北京：人民邮电出版社，．
[4] 闵敏，朱辉生．《数据构造》．高等教诲出版社 编著 .4
[5] 张世和．《数据构造》．清华大学出版社 .11
[6] 李玲玲．《C程序设计》．清华大学出版社
[7] 郑莉，董渊．《C++程序设计基本教程》 清华大学出版社。
[8] 社尹德淳．《C函数速查手册[M]》．北京：人民邮电出版，龙脉工作室
[9] 林小茶．《C语言程序设计》
[10]朱鸣华．《C语言程序设计教程》
[11]蒋文蓉．《数据构造》．高等教诲出版社 .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分算
五级制成绩

教 师 签 名：
批 改 日 期： 年 月 日