单词查询系统.doc

1 命题：一个文本文件仅含有英文字母和分隔符，分隔符包括空格、逗号、句号和换行符。除此之外，该文件不含其它符号。一个单词的由一个或多个分隔符分隔的连续字母序列，例如：下面一个包含5个单词的文件_Student_ must_ _ _havea_ book.符号“_”为空格符；“”为换行符；“.”为句号。文本文件中的第一个名子是从文件头到第一个句号间的字符序列（含句号），除第一个句子之外的所有句子都是由两个句号间的所有字符组成的序列（含后面的句号）。编一程序由键盘输入一个符合上述约定的文本文件名和一个单词，计算该单词在该文件中出现的次数，并输出包含该单词的所有句子（按句子在文件中的先后次序，依次输出）。 注意： 文件中每个单词的长度不超过20个字母。 判断单词是否相同时不区分大小写。例如ABC、Abc、Abc、aBC、abc都是同一个单词。 输入数据：由键盘输入待查文本文件名和待查单词。待查文件名为：input.txt。 输出数据：输出文件为output.txt，该文件第一行为该单词在文件中出现的次数。从每行开始是依先后次序输出的包含该单词的句子。在输出句子时主注意： 每个句子无论多长只占一行； 原句中每一个换行符用一个空格符代替。 输入输出范例：查阅have单词输入文件内容：Every computer will have MsDos, Borland C Microsoft Quick Basic. And Turbo Pascal. For the translati ons the teamleaders will be provided with Microsoft Office with MS Word and Word Perfect Information on directories and last instructions will be sent to you in the last news letter and distributed on the day before the first contest day. Each student will have the opportunity for some practice. On the equipment.输出文件内容：2Every computer will have MsDos,Borland C Microsoft Quick Basic. Each student will have the opportunity for some practice.2 分析：依据命题所给，现在来进行逐个信息的分析。第一、文件仅含有英文文字的分隔符空格、逗号、句号和换行符，除些之外再不含其它文字。所以，在程序中所要考虑的情况，也就这几种。第二、一个单词的由一个或多个分隔符分隔的连续字母序列,这里表明，只有遇到形如“（分隔符）字符串（分隔符）”位于两个分隔符之间的情况才算找到一个单词。第三、文本文件中的第一个名子是从文件头到第一个句号间的字符序列（含句号），除第一个句子之外的所有句子都是由两个句号间的所有字符组成的序列（含后面的句号）。辨别所读入的字符序列是否已经是一个句子可用句号来分别。从这里以及后面的“每个句子无论多长只占一行；”我们知道，对于文本的处理，应以句子为单位，至少是在存放时应以句子为单位，以便空易实现文本的输出格式。考虑到句子的长度的变化，对于每个句子在内存中的存放形式，应该是采用数组较好些。因为采用链表的话，对每个字母进行存放，还要加一个存放指向下一个字母的指针的空间，这样的在存放了1/2的句子就已经用掉了能存放的下整个句子的空间。如果用每个单词作为一个链表结点，这样对于存放要好一些。但是，这样一来就对于比较和输出时有所不利。第四、判断单词是否相同时不区分大小写。例如ABC、Abc、Abc、aBC、abc都是同一个单词。这里要在单词识别时，需要进行大小写转换。第五、在输出数据的要求中，可得到，在进行单词查找的过程中，要对所找到的单词次数进行记录。如果遇到换行符，这是指在一个句子尚未查找完成时遇到换行符，这个时候要用空格来代替。但输出结果应是没有类似于在单词间有多个空格的形式的。通过分析，现在初步想到二种实现方法：读进后再处理，边读边处理。对于这二种情况，需要对其的执行效率和空间的占用进行考虑。现在来分析一下这二种方法的时空情况。假设硬磁盘的读写速度为Vh（B/ms），起动一次要开销为Th(ms)，内存速度为Vm(B/ms)，CPU处理一个字符所花的时间为Tc(ms)。而总共要处理的字符个数为N，其中为M句，含有所找单词的句子是K句。2.1读进后再处理该方法是一次性的把整个要处理的文件全部读到内存中。这样在读完之后不用再次对其进行读取。对于硬磁盘只需起动一次。根据计算机的存储器的实际情况，显然，这样会有一个较快的处理速度。时间：从硬磁盘读入要花时间 = N/Vh+Th；这时写入内存的时间由于比起从硬磁盘读取的时间少的多，且在读硬磁盘的同时，可对其进行写。于是可忽略不计。CPU处理过程中花费时间 = Tc*N输出所花费的时间 = 1/Vh * K + Th 注：K表示K句中总共的字符数。所以：时间开销 = 从硬磁盘读入要花时间 + 处理过程中花费时间 + 输出所花费的时间 = N/Vh + Th + Tc*N + 1/Vh*K + Th = N/Vh + 2*Th + Tc*N + 1/Vh * K = 2*Th + Tc*N + (N * K)/Vh空间：而对于空间的使用上，一次性全读入，需要把整个文件全部读到内存，这样对于一些没有包含所要找的单词的句子，也都预先读到内存。也就是说，如果，在文件中包含有所要找的单词越少，则空间浪费越多。读完之后在内存中占用空间最经济的是：N但使用固定大小的数组存放，则是：数组长度 * M；（数组长度为500B）则空间应是：500 * M注：假设句子最长为500字符。如果是在找到每个句子进行标记，则还需要有M（B）存放标记。对这样的空间利用将是：501 * M（B）（处理过程所要利用的空间对于三种方式，相差不大，这里不加考虑）。2.2 边读边处理这种方法是，顾名思义，就是读一个字符，进行一次处理。当读到句子内含有要找的单词时，这样就可以把该句子保留下来。这里又有两种考虑：一种是就在这个时候，把句子写入输出文件；另一种是先存放在内存当中。显然，前一种是非常节省空间的。不过，对速度的销耗，也是最多的。故在这里只说明后一种。至于前一种，只是把输出加到单词的查找当中就可以了。这种方法也可称为边读边处理边写。时间：读入一个字符时间：1/Vh;这里对于内存的写入，需要考虑在内。由于，内存的写和硬磁盘的读不是同步进行的。故，写一个字符到内存的时间为：1/Vm;CPU处理一个字符的过程花费时间= Tc；输出一个字符所花费的时间=1/Vm;则据此，总共要消耗的时间为：消耗的时间 = （读入一个字符时间 + 写一个字符到内存的时间 + CPU处理一个字符的过程花费时间）* 字符数 + 输出一个字符所花费的时间 * 输出字符数 + 2 * 硬磁盘一次起动时间 = (1/Vh + 1/Vm + Tc)*N +1/Vh*K + 2*Th = 2*Th + N/Vm + N*Tc + (N + K)/Th可见比起读进后处理要多消耗一些N/Vm的时间。空间：在空间方面，边读边理使用情况和读入后再处理是有很大不同的。边读边写在空间利用上是，所浪费的空间是很小的。由于它只是保存包含有所找单词的句子，所以，对于没有包含有单词的句子，将丢弃，不会占用空间。对硬磁盘读完一次后所占用的空间：K * 500（B）另外，对于边读边处理边写占用空间只为一个句子的长度，用固定大小的数组则为，500B。3 模型设计： 对于以上三种分析，通过分析可知，第一种速度最快，第三种空间利用率最高，而第二种处于两者之间。所以，程序设计取择中的一种，即，第二种，边读边处理。3.1 详细设计本程序设计利用C语言。由于，设计中并不要求有窗口的设计，而对于数据的处理，则更能体现C的高效性和对流程的控制作用。1） 建立结构体用于动态存放所要处理的字符串（句子）。只要有两项便足以。一个数组（500）、一个指针（用于指向下一个要存放的句子）。这样在输出时能够按顺序输出。符合题目的输出要求：从每行开始是依先后次序输出的包含该单词的句子。2） 对于数据的存储结构，（如图3.1.a所示）在main()中，首先创建了一个HeadElem指针，让其指向链表的表头。这样如果在模块中要用到链表时，在调用的时候就可以通过它把头地址传过去。如图3.1.a3） 读取字符，定义FILE *fp类型指针，利用fopen（）打开文件。使 *fp指向该文件。然后程序可以通过fgetc()从文件中获取一个字符。4） 处理字符，从文件中每获取一个字符，先使其与所要查找词的第一字符进行比较。如相同，则获取的下一个字符再来与要查找的单词的第二个字符比较。如果，在读取要查找单词的过程中，读到一个NULL，那么代表当前已经找到了要找的单词。那么计数count+;同时使一个起标至作用的HavOrNot置为TRUE，代表这个句子需要保存下来。只是这个句子需要保存下来，那么在取下一个句子时，就要重新申请一个空间。否则，取下一个句子时，只要先清空当前所使用的空间便可。5） 对于单词的判断还需要注意前后是否是分隔符。只有当在读取所要查找的单词的第一个字符时，所对应的从文件里取出的当前字符的前一个字符是分隔符；并且，当在读取所要查找单词时读出了NULL时，所对应的从文件里取出的当前字符也是分隔符时，才算找到一个单词。6） 对句子的识别，就是对句号的识别。即，当从文件中读取出来的字符是“。”时，表明一个句子结束。则需要清空该句所占用的空间或是再申请新的空间。7） 如果是申请新的空间，那么就要使上一个句子空间的*NextSt指向新空间的地址。当文件结束时，还要便其最后一句的*NextSt指向NULL.8） 对文件读取是否完毕的判断。依据题，所要处理的字符仅含有英文字母和分隔符，分隔符包括空格、逗号、句号和换行符。在不知道在读取文件结束时返回什么的情况下，只要判断当前读取到的是不是在这几种字符中的一种，则可判断是不是读取文件结束。结束，用fclose()将其关闭。9） 文件字符的判断，利用ASCII码来判断。当字符的ASCII码与分隔相等，字符便是分隔符；字符大于A-1小于Z+1，或大于a-1 小于z+1，则是英文字母。其它的按出错处理。10） 对于不同大小写字母，也是利用其ASCII码。这里是把大写转为小写。即：Letter-A+a；11） 句子的输出，已经建好的句子链表，头结点在main()中是HeadElem，结尾结点的NextSt已经指向NULL。这样在输出时，就是从HeadElem-NextSt开始，到NULL结束。在输出时需要建一个OUTPUT.TXT文件。每写一句后要写入一个“n”，使在写句子时从一新的行开始。写入文件的函数有：fputc()、fputs()、fprintf()等。这里用fputs()写入一句子，用fprintf()写入”n”。12） 在最后要对链表所利用了的空间进行释放。释放的函数是free()。释放成功返回1，不成功返回0。3.2 流程图 对于流程图这里只表示出关键部分。即，对字符的读取，句子的存放，单词的识别，单词个数的记录。（如图3.2.a）TRUEFALSE清空HavOrNot是HavOrNot = FALSE输入文件名m20、单词n20结束释放链表free()相同否写入OUPPUT.TXT句号否逗号、换行符、空格，英文字母不同是与n20比较HavOrNot=TRUEcount+从文件中读取一个字符取一个空间，连到链表上下班打开input.txt文件开始图3.2.a3.3 算法/建立结构体#include typedef struct IncludeWordSt char StCheked500; /*存放包含有所查单词的句子, 最多可容纳_NUM个字符*/ struct IncludeWordSt *NextSt;/*连接下一个句子*/IncludeWordSt;/读取文档并在文档中查找int ShearchWord(IncludeWordSt *HeadElem) char s = , m20,n20; int count=0; FILE *fp;/*s用来存放本次取到的字符 m在存放输入的查找文件名 n得到所要查找的单词 count计单词数 *fp指向要读取的文件*/ IncludeWordSt *NowElem; gets(m,n); /*输入要查找的文件的文件名到，要查找的单词到*/ fp=fopen(m, r); /*打开文字文件只读*/NowElem = HeadElem;for(;输入文件还未读完读完;) /*如果在上一个句子中有所要找的词，那么， 再取一个新的结点，来处理下一个句子*/if(读第一句或上一句中含有要找和单词)NowElem = 创建一个结点的地址初始化(清空)NowElemfor(i=0;取到的字符不句号 & 不是非法字符;i+)/*判断一个句子的结束*/*对分隔符的判断，逗号，句号，空格，换行*/*如果取到的字符为空格或是换行且之前已是空格，则数组退一格*/if(i0)if(NowElem-StChekedi-1= )if(s = |s = n )i-;/*当取到换行符，而之前取到的不是空格，则当前数组项应为一空格符*/if(NowElem-StChekedi = n)NowElem-StChekedi = ;/*查找是不是含有所给单词*/mj = s;j+;if(分隔符)/*碰到分隔符，表明一个单词读完，就要判断是不是要找的单词*/mj-1=;/*清分隔符*/if(CompareMN(m,n) /*比较m,n是不是同一单词*/查找到一个词;count+; /*记录找到的词的个数*/break;j = 0;/*使最后一个结点的NextSt指向空，用来判断存储的内容到此结束*/if(!EndOrNot(s)NowElem-NextSt = NULL;fclose(fp)；return count;4 源程序#include#define _NUM 500 /*最多可处理的，每个句子的长度*/#define _PNAME .txt /*输入文件名的后缀名*/#define _OUTNAME OutPut.txt /*默认的输出文件名*/#define _JUDGE (s = NowElem-StChekedi = fgetc(fp)!=. /*判断在文件中的一个句子是否结束*/#define NULL 0#define TURE 1#define FALSE 0#define _SPACE #define _ENTER n#define _COMMA ,#define _FSTOP ./*写义结构体IncludeWordSt*/typedef struct IncludeWordSt char StCheked_NUM; /*存放包含有所查单词的句子, 最多可容纳_NUM个字符*/ struct IncludeWordSt *NextSt;/*连接下一个句子*/IncludeWordSt;/*struct IncludeWordSt *InWdSt;*/*转换一个大写字母使其为小写形式*/char turnStyl(char words) if(wordsA-1)&(wordsZ+1)words=words-A+a;return words;/*清空数组*/void ClearSt(IncludeWordSt *St)int i;for(i = 0;iStChekedi = NULL;/*在FileName后加上一串字符PostName*/char *AddPostName(char FileName20,char PostName,int k) int i,j; for(i=0;i20&FileNamei;i+); for(j=0;j);gets(InRout);for(i=0;i=a&Letter=A&LetterNextSt) != NULL;)if(free(NElem) = FALSE)return FALSE;NElem = NextP;return TURE;/*连接结点*/IncludeWordSt *ConnectElem(IncludeWordSt *ElemPre)ElemPre-NextSt = CreatElem();ElemPre = ElemPre-NextSt;return ElemPre;/*读取文档并在文档中查找*/int ShearchWord(IncludeWordSt *HeadElem) static char s = , m20,n20; int i,j=0,count=0,HavOrNot = TURE; FILE *fp;/*s用来存放本次取到的字符 m在存放输入的查找文件名 n得到所要查找的单词 count计单词数 HavOrNot指示句子中是否有单词存在,FALSE没有,TURE有. *fp指向要读取的文件*/ IncludeWordSt *NowElem; printf(Input files name:);gets(m); /*输入要查找的文件的文件名到m中，要加后缀名*/ printf(nInput a word:);gets(n); /*输入要查找的单词到n中*/ fp=fopen(m, r); /*打开文字文件只读*/ if(fp=NULL) /*判断文件是否打开成功*/*当输入的文件名没有包含后缀名时，加上后缀名.txt*/fp=fopen(AddPostName(m,_PNAME,5),r); if(fp=NULL) /*如果仍然没有打开，则提示错误*/puts(File open error); /*提示打开不成功*/NowElem = HeadElem;/* ConnectElem(NowElem);*/for(;EndOrNot(s)=TURE;) /*整个输入文件是否读完*/*如果在上一个句子中有所要找的词，那么， 再取一个新的结点，来处理下一个句子*/if(HavOrNot)NowElem = ConnectElem(NowElem);/*创建一个结点*/HavOrNot = FALSE;ClearSt(NowElem); /*初始化(清空)NowElem*/for(i=0;_JUDGE & EndOrNot(s)=TURE;i+)/*判断一个句子的结束*/*对分隔符的判断，逗号，句号，空格，换行*/*如果取到的字符为空格或是换行且之前已是空格，则数组退一格*/if(i0)if(NowElem-StChekedi-1= )if(s = |s = n )i-;/*当取到换行符，而之前取到的不是空格，则当前数组项应为一空格符*/if(NowElem-StChekedi = n)NowElem-StChekedi = ;/*查找是不是含有所给单词*/mj = s;j+;if(s= |s = ,|s = n|s= .)/*碰到分隔符，表明一个单词读完，就要判断是不是要找的单词*/mj-1=;/*当前有一个字符与单词的相同时，比较下一个字符。turnStyl()使当前为大写的字母转换为小写形式*/if(CompareMN(m,n,j)HavOrNot=TURE; /*查找到一个词，标记为1*/count+; /*记录找到的词的个数*/j = 0;/*if(HavOrNot = FALSE)ClearSt(NowElem);*/*使最后一个结点的NextSt指向空，用来判断存储的内容到些结束*/if(!EndOrNot(s)NowElem-NextSt = NULL;if(fclose(fp) /*判断文件是否关闭成功*/puts(File close error); /*提示关闭不成功*/return count;/*把HeadElem为头的链表中的内容和整型数字WordCount写到文件中*/void OutSentence(IncludeWordSt *HeadElem,int WordCount)IncludeWordSt *OutElem; /*指向当前要写入文件的句子*/int i;FILE *fp; /*指向要打开或创建的文件*/fp = fopen(_OUTNAME,w); /*尝试打开或创建一个可写文件*/ for(i=0;fp =NULL&iNextSt; for(;OutElem!=NULL;) /*写当前句子到文件中*/ fputs(OutElem-StCheked,fp); OutElem=OutElem-NextSt; fprintf(fp,n); if(fclose(fp) /*判断文件是否关闭成功*/ puts(File close error); /*提示关闭不成功*/*/main() IncludeWordSt *HeadElem; /*用来存放链表的头*/ int WordCount; /*存放找到的单词数*/ clrscr(); /*清空输入窗口*/ HeadElem = CreatElem(); /*为头分配一个空间*/ WordCount = ShearchWord(HeadElem);/*从文件中读取查找*/ OutSentence(HeadElem, WordCount); /*对结果进行写操作*/if(FreeStQuery(HeadElem) /*释放被引用的空间*/puts(nThe protocol was terminate seccess!); getch(); /*等待用户响应*/5 执行结果4.1 输入文件。要注意：在文件中要只有分隔符（空格、逗号、句号的换行符），英文字母（不分大小写）。否则不能得到正确结果。(如图4.1.)a。窗口输入内容，依据提示输入。(如图4.1.b)。在输入文件句时（Input files name:）这时里可以加后缀名，也可不加。如不加，则查询系统会自动加上。在按提示输入要查找的单词后，系统便开始读取文件。图4.1.b4.2输出文件。 输出文件中，在程序执行后，会自动生成一个OUTPUT.TXT文件，并在里面存放有输出结果。并在窗口提示：The protocol was terminate seccess!（如图4.1.c）。 如果，当前目录是不可写，则系统会提示，输入要存放文件的路径。这里可进行三次输入，如三次都不正确，则系统自动结束。输入了正确路径后，如在路径中写入一个文件名，则执行结果按输入的文件名存放，否则，系统会以默认的OUTPUT.TXT来存放结果。输出文件的结果是找到单词的个数，和含有所要查找的单词的句子，每行写一个句。 （如图4.1.d）。The memory hierarchy of the embedded computers is often quite different from that of the desktop and server. First, embedded computers are often used in realtime applications, and hence programmers must worry about worst case performance. This concern is problematic for caches that improve average case performance, but can degrade worst case performance. well mention some techniques to address this laterin the chapter. Second, embedded applications are often concerned about power and battery life. The best way to save power is to have less hardware