文本文献单词的检索与计数

《数据结构》

课程设计报告书

题目：文本文献单词的检索与计数

专业：网络工程__________________

学号：_______________________

学生姓名：_________________

指导教师：________________

完毕日期：_______2023/6/7__________________

目录

1设计任务书..........................

1.1题目与规定........................

1.2知识点............................................2

1.3输入输出分析......................................2

1.4测试数据分析......................................2

2概要设计............................

2.1结构体类型及函数声明..............

2.2主程序流程........................................3

2.3模块流程说明......................................4

3具体设计............................................8

3.1数据类型实现......................................8

3.2程序代码.........................................12

4调试分析...........................................17

4.1问题分析与回顾...................................17

4.2算法时空分析.......................

4.3算法改善..........................

4.4经验和体会........................

5测试结果............................

参考文献..............................................32

评分标准.................................................24

1设计任务书

1.1题目与规定

题目：文本文献单词的检索与计数。

规定：编程建立一个文本文献，每个单词不包含空格且不跨行，单词由字符序列构

成且区分大小写；记录给定单词在文本文献中出现的总次数；检索输出某个单词出现在

文本中的行号、在该行中出现的次数以及位置。建立文本文献，文献名由用户用键盘输

入；给定单词的计数，输入一个不含空格的单词，记录输出该单词在文本中的出现次数;

检索给定单词，输入一个单词，检索并输出该单词所在的行号、该行中出现的次数以及

在该行中的相应位置。

1.2知识点

串的应用、文献、结构体、指针、数组、函数、函数的调用、循环语句、选择语

句、输入输出控制、自定义类型等。

1.3输入输出分析

（1）普通输入

在文本文献的建立中，需要先定义串变量和文本文献，从而建立文本文献；根据实

际情况，将单词的长度定义为20,规定每行最多输入110个字符。

（2）对话式输入

为便于转换及比较，对话式输入采用字符数组进行存储.为保障程序的健壮性，同

时限制对话式输入的格式，对于非法的会话式输入则提醒用户操作失败的因素。

（3）程序输出

为了能让程序输出时更加美观，程序输出重要以整齐为主，使得输出的程序结果

均整齐输出。

1.4测试数据分析

在建立文本文献名时，规定键盘输入所建立的文本文献的名称，假如所输入的文本

文献名称超过所给定的字符，将提醒输入错误，请重新输入。

在第二次输入文本文献名称以供在此文本文献中查找所给定的单词，假如用户输入

的文本文献名称与第一次不符或输入为空，系统将提醒输入错误，请重新输入。

在主控程序中，规定输入执行指令1——4,假如输入非1——4字符，系统将提醒

输入错误，请重新选择

2概要设计

2.1结构体类型及函数声明

(1)结构体

1.typedefstruct/*定义顺序串类型*/

(

charch[MaxStrSize];

intlength;

Istring;

2.typedefstruct/*记录单词出现的次数*/

(

charword[WORD_LEN];

intcount;

}elem_type;

3.typedefstruct{

elem_type*elem;/*存储空间基址*/

intlength;/*当前长度当

intlistsize;/*当前分派的存储容量*/

}sqlist;

函数：

1.建立文献：voidcreat_text_file()

2.单词记录：voidsqlist_add(sqlist*sq,elem_type*et,char*word)

3.文本文献中单词的总汇：voidsubstrsum()

4.单词的定位：voidsubstrcount()

5.主函数：intmain。

2.2主程序流程

(1)主程序调用模块图

主程序运用switch。语句实现各个模块的调用，主函数调用如图1所示。

图1主程序调用模块图

2.3模块流程说明

主函数对各重要模块进行调用，各个重要模块又分别调用其他子模块。下面用简要

流程图对各重要模块进行说明。

(1)建立文本文献主模块

如图2所示，建立文本文献模块。一方面定义一个串变量，，然后调用void

creat」ext_Ele()函数，定义文本文献，键盘输入文献名，打开该文献，循环读入文本行,

写入文本文献，最后关闭文献。

开始

图2建立文本文献模块

(2)给定单词的计数主模块

如图3所示为给定单词计数程图。其实现过程如下；一方面输入要检索的文本文

献名，打开相应的文献，然后输入要检索记录的单词，循环读文本文献，读入一行，将

其送入定义好的串中，并求该串的实际长度，调用串匹配函数进行计数。数最后关闭文

献，输出记录结果

图3单词计数模块

（3）主控程序模块

如图4为中控程序流程图。过程如下：

输入头文献

使用循环语句输出一下4个执行指令：

1.建立文本文档

2.文本单词汇总

3.给定单词定位

4.退出

如输入非1——4的韦令，系统将提醒，输入错误请重新输入。

结束

提醒：输入错误，请重新输

执行相应指令

结束

图4主控程序模块

3具体设计

3.1数据类型实现

结构体：

1.typcdefstruct/*定义顺序串类型*/

(

charchlMaxStrSizcJ:

intlength;

}string;

2.typedefstruct/*记录单词出现的次数*/

(

charwordfWORD_LEN];

intcount;

)elem_type;

3.typcdcfstruct{

elem_type*elem;/*存储空间基址*/

intlength;/*当前长度*/

intlistsize;/*当前分派的存储容量*/

}sqlist;

函数：

1.建立文献：voidcreat_text_file()

2.单词记录：voidsqlist_add(sqlist*sq,elem_type*et,char*word)

3.文本文献中单词的总汇：voidsubstrsum()

4.单词的定位：voidsubstrcount()

5.主函数：intmain。

3.2程序代码

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#defineLISTJNIT_SIZE500/*线性表存储空间的初始分派量*/

#defineLISTINCREMENT1()/*线性表存储空间的分派增量*/

#defineFILE_NAME_LEN20/*文献名长度列

#defineWORD_LEN20/*单词长度*/

#defineMaxStrSize256

#definellength11()/*规定一行有110个字节"/

typcdefstruct

charch[MaxStrSize];/*ch是一个可容纳256个字符的字符数组*/

inilength;

)string;/*定义顺序串类型*/

typedefstruct

charword[WORD_LEN];/*存储单词，不超过20个字符*/

intcount;/*单词出现的次数列

}clcm_type;

typedefstruct)

clem_type*elcm;/*存储空间基址*/

intlength;/*当前长度*/

intlistsize;/*当前分派的存储容量*/

}sqlist;

voidsqlist_init(sqlist木sq,elem_type*et)

(

sq->elem=et;sq->length=0;

}

voidsqlist_add(sqlist*sq,elem_type*et,char*word)

(

inti;

intj;

for(i=0;i<sq->lcngth;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("空间局限性，单词[%$]插入失败失”,word);

return;

I

for(j=sq->length;j>i;j—)

(

memcpy(et+j,et+j-1,sizeof(elem_type));

)

sq->length++;

strcpy(etlij.word,word);

et[ij.count=1;

intsqlist_count(sqlist*sq,elem_type*et)

inti;

intj=0;

fdr(i=O;i<sq->length;i++)

j=j+et[i].count;

returnj;

)

voidcreat_text_file()

(

elem_typew;

sqlists;

charfile_name[FILE_NAME_LEN+l],yn;

FILE*fp;

printf("输入要建立的文献名：”)；

scanf("%sn,file_name);

fp=fopen(file_name,"w");

yn-nr;/*输入结束标志初值*/

whilc(yn==,n,||yn=-N,)

(

primf("请输入一行文本:");

gets(w.word);

gets(w.word);

s.length=strlen(w.word);

fwrite(&w,s.length,1,fp);

「printf(fp，"％c”[O)；/*是输入换行*/

primf("结束输入吗？yorn:")；yn=getchar();

)

fclose(fp);/*关闭文献*/

printfT建立文献结束!\n")；

)

voidsubstrsum()

(

charfilc_namc[FILE_NAME_LEN+1];

charword[WORD_LEN+l];

FILE*fp;

inti;

intj,q=O;

intw,x,y=0;

elem_lypeet[LISTJNIT_SIZE];

sqlistsq;

sqlist_init(&sq,et);

prinlf("请输入文献名：”)；

scanf(n%s",file_name);

fp=fbpen(file_name,"r");

if(fp=NULL)

(

primf("打开文献失败!\n");

return;

1

while(fscanf(fp."%s';word)!=EOF)

sqlist_add(&sq,et,word);

}

fclose(fp);

printf(n单词个数\n”)；

for(i=0;i<sq.length;i++)

(

x=strlen(et[i].word);

fbr(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=();w<x;w++)

if(et[i].word[w]==*')

y++;

ifiy==x)

(

et[i].count=0;

y=0；

)

elsey=0;

if(et[i].count!=0)

printf(n%20s%10d\n",etfij.word,etfi].count);

elseq++;

)

j=sqlist_count(&sq,et);

printf("\n%s的单词总数为％dj\n”,file_name,j);

printf("\n%s的非单词个数为％(1种\n",file_name,q);

printfCVn");

}

intpartposition(stringsi,strings2,intk)

(

inti,j;

i=k-l;/*扫描si的下标，由于c中数组下标是从0开始，串中序号相差1*/

j=0;/*扫描s2的开始下标*/

while(i<s1.length&&j<s2.length)

(

if(sl.ch[i]==s2.ch[j])

(

i++;j++;/*继续使下标移向下一个字符位置*/

}

else

(

i=i-j+l;j=O;

}

)

if(j>=s2.length)

returni-s2.length;/*表达si中存在s2,返回其起始位置*/

else

return-1;/*表达si中不存在s2,返回-1*/

}/*函数结束*/

voidsubstrcount()

(

FILE*fp;

strings,t;/*定义两个串变置*/

charfname[10';

inii=O,j,k;

printf("输入文本文献名：”)；

scanf(n%s'\fname);

fp=fopen(fname,"r");

printf("输入要记录计数的单词：”)；

scanf("%s'\t.ch);

t.length=strlen(t.ch);

while(!feof(fp))

(

memselCs.ch/XO,J10);

fgets(s.ch,l10,fp);

s.length=strlcn(s.ch);

k=0;/*初始化开始检索位置*/

while(k<s.length-l)/*检索整个主串S*/

j=partposition(s,t,k);/*调用串匹配函数*/

if(j<0)break;

else

(

i++;/*单词计数器加1*/

k=j+t.length;/*继续下一字串的检索*/

)

}

)

printf("\n单词％s在文本文献％s中共出现％d次",t.ch,fname,i);/*记录单词

出现的个数*/

I

voidsubstrint()

(

FILE*fp;

strings,t;/*定义两个串变量*/

charfnamc[10j

int

intwz[20];/*存放一行中字串匹配的多个位置*/

printf("输入文本文献名：”)；

scanf("%s'\fname);

fp=fopen(fname,nr");

printf("输入要检索的单词：");

scanf("%s",t.ch);

t.length=strlen(t.ch);

1=0;/*行计数器置0*/

while(!feof(fp))/*扫描整个文本文献*/

memset(s.ch,'\0',110);

fgets(s.ch,l10,fp);

s.lcngth=strlcn(s.ch);

1++;/*行计数器自增1*/

k=0;/*初始化开始检索位置*/

i=0;」，*初始化单词计数器*/

while(k<s.length-l)/*检索整个主串S*/

I

j=partposition(s,t,k);/*调用串匹配函数*/

if(j<0)break;

else

i++；/*单词计数器加1*/

wz[i]=j;/x记录匹配单词位置*/

k=j+t.length;/*继续下一字串检索*/

)

if(i>0)

printf("行号:%d,次数：%d,位置分别为：

for(m=1;m<=i;m++)

primf("第％4d个字符”,wz[m]+l);

}

printf("\n");

1

printf("\n本软件自定义110个字节为一行\n\n")；

I/*检索单词出现在文本文献中的行号、次数及其位置*/

voidsubstrio()

voidsubstrcount(),substrint();

chart;

while(l)

(

printf("============================================\n");

printf(n请输入:")；

printf("||文本文献单词字串的定位记录及定位||\n")；

printf("||==================================||\n");

printfCHa.单词出现次数|W);

printfCHl|\nH);

printfC'Hl!\nH);

printf("||b.单词出现位置||\n");

printfCHl|\nH);

printf("An,1);

scanf("%c",&t);

switch(t){

case'a*:substrcount();

break;

case'b':substrint();

break;

default:return;

}

)

)

intmain()

(

voidcreat_text_file(),substrsum(),substrio();

intxz;

while(l)

printf("==============================================\n");

printfC'll文本文献的检索、字串的记录及定位||\nu);

primf("||=—=====—==============="3");

printf("||1.建立文本文献IW)；

printfC'll2.单词字串的计数IW);

printfC'll3.单词字串的定位IW)；

printfC'll4.退出整个程序IH);

printf("\n");

printf("请选择(l--4)\n”)；

scanf(,'%d,,,&xz);

switch(xz)

(

case1:creat_text_file();

break;

case2:substrsum();

break;

case3:substrio();

break;

case4:return0;

default:printf("选择错误，重新选\n");

1

)

return0;

I

4调试分析

4.1问题分析与回顾

问题1：在语句“请输入一行文本”后边，只写一句接受语句，结果运营时，请输

入文本和结束输入吗？演示在一起，并且不能接受文本输入。

解决：和同学讨论后，加入了文本接受语句，成功运营。

问题2：当要检索文本时，输入为空，或输入非建立的文本文献名，系统不能正常

运营。

分析：缺少判断语句。

解决：当出现这种情况时，系统提醒输入错误，请重新输入。

4.2算法时空分析

拟定给定单词出现的个数，需要记录文本文献中所有的单词，因此时间复杂度为

O(n)；

拟定给定单词出现的位置，需要显示其所在的行和列，时间复杂度为O(i*l)；

4.3算法改善

此算法虽然基本实现了功能，但却仍存在许多局限性，例如当当前建立的文献名与

之前相同时，没有错误提醒，另如在对单词的检索方面，时间复杂度及空间复杂度仍不

尽如人意。仍需要改善代码，达成算法的高效性。

4.4经验和体会

通过本次数据结构的课程设计，让我对数据结构这门课有了更加深刻的结识。数据

结构这门课程的理论性只是较强，要学好这门课程，就必要在掌握好理论知识的同时，

加强上机操作，碰到问题，解决问题，这样才会有更大的进步。

我课程设计的题目是文献文本的检索与计数，由于这个课题要用到串的知识。而

我对之前对串的定义却不是很明确，于是我有具体的学习了课本上的知识并查阅了很多

文献。在着手作程序的过程中，经常碰到程序运营不出来，运营达不到效果等问题，特

别是接受文本，搜索时如何定位等方面碰到了很多问题。但我通过请教老师和同学，查

阅文献，然后基本上解决了这些问题。在这个过程中我学到了很多，我结识到了坚持不

懈的重要性，在我一遍一遍的调试下，终于成功的写出了程序。在编写本次程序时，我

学会了先用流程图对进行算法分析•，这样是自己的思绪更加清楚，而不是像之前那样对

整个函数没有整体的认知，而导致经常无从下手。

之前我对数据结构的各种算法都感到畏惧，感觉很抽象，而这次通过自己几周的努

力，在老师和同学们的帮助下，终于完毕了本次课程设计，这对我来说无疑是极大的鼓

舞，极大的增强了我学数据结构的自信心。并且我也充足结识到数据结构自身就是一门

实践性很强的课程，只有加强实践，才干学得更好！

5测试结果

(1)输入建立文献名

如图5所示为输入建立文献测试

X

文本文件的检索、字串的统计及定位

立文

1Nr」

生

2词u=

的定

子

3词un

程序

4出整/k

请无择＜1—4〉

1

入

,建立的文件名：fanxiang

输又一行支本：

图5输入建立文献测试

(2)输入一行文本测试

如图6所示建立一行文本，建立文献结束界而.

■*G：建奏结的课程设计\Debug\l.exe'

文本文件的检索、字串的统计及定位

立

^NL年

{

词ulpx

xun定

词

的

u台

子u

序

出

程

整/\

名

入

建

立的

件

费aX

文

一

行et

要

：wefriends71

？

入

一

萼yy

一

束

件

一♦

・

一

一

一.

文本文件的检索、字串的统计及定位

建

立文

4年

O

单

词主

H定

词子

—

H的

序

出整

-程

请选择＜1—4)

图6建立文献结束测试

(3)单词字串的计数测试

如图7,单词字串的计数测试界面。

[01回

文本文件的检索、字串的统计及定位：:

、

并

建"4

词

定

单1

词

子

蚩

序

出

整

—

请选择《1—4〉

2

请输入文件名：fanxiang

单词个数

are1

friends1

we1

fanxiang的单词总数为3个

fanxiang的非单词个数为1.种

文本文件的检索、字串的统计及定位

图7单词字串的计数测试

(4)单词字串的定位测试

如图8和图9所示.

II

黔懿獭播鬻即

单词toe在文本文件fanxiang中共出现1■次

请输入:；;文本文件单词字串的定位统计及定位;

单词出现次数

单词出现位置

文本文件的检索、字串的统计及定位

建立

1zL洋

\

词

2单unS

un定

词

—

Un的

3子U

序

出

r-1程

4整/)

请选择《1—4)

图8单词字串的定位测试

图9单词字串的定位测试

（5）程序结束退出，如图10所示

■'G:谨据结的课程设计\Debug\l.exe，IoI回

文本文件的检索、字串的统计及定位

建立^#

{N\

词un

单xuif

的定

词un

子u

用n

程

序

出、

整/

请选择“一4〉

1

觎入擘建安的文件名：fanxiang

清输入—行文本：wearefriengs

结束输入吗？yorn：y

建美支件曙束？

文本文件的检索、字串的统计及定位；；

文

文

建^#

立z\

的

生

单

词un

itn

的

子

—

定

词un

un

程

整

序

出/\

请选择〈1—4)

4

Pressanykeytocontinue

图10程序结束退出

参考文献

［1］严蔚敏，吴伟民.数据结构（C语言版）.北京：清华大学出版社，2023.

［2］蒋清明，向德生.C语言程序设计.北京：人民邮电出版社，2023.

［3］尹德淳，龙脉工作室.C函数速查手册.北京：人民邮电出版社，2023.

14］闵敏，朱辉生.《数据结构》.高等教育出版社编著2023.4

［5］张世和.《数据结构》.清华大学出版社2023.11

16］李玲玲.《C程序设计》.清华大学出版社

［7］郑莉，董渊.《C++程序设计基础教程》清华大学出版社。

［8］社尹德淳.《C函数速查手册［M］》.北京：人民邮电出版，龙脉工作室2023

19］林小茶.《C语言程序设计》

［10］朱鸣华.《C语言程序设计教程