西北工业大学数据结构课程方案实验报告.doc

西北工业大学数据结构课程方案实验报告

-- 数据结构
课程设计实验报告

学院：
班级：
姓名：
学号：
邮箱：
日期： 1月17日

《数据结构》实验报告

◎实验题目:单词<词组）检索
◎实验内容：现在有一个英文字典<每个单词都是由小写的'a'-'z'组成），单词量很大，达到 100多万的单词，而且还有很多重复的单词。另外，我们现在还有一些 Document，每个Document 包含一些英语单词。
针对这个问题，请你选择合适的数据结构，组织这些数据，使时间复杂度和空间复杂度尽可能低，而且解决下面的问题和分析自己算法的时间复杂度。

1）基本型问题<必须采用字符串哈希，hash散列算法）
<1）将所有的英文单词生成一个字典Dictionary。
<2）给定一个单词，判断这个单词是否在字典Dictionary中。如果在单词库中，输出这个单词总共出现的次数。否则输出NO。
<3）输出Dictionary中出现次数最高的10个单词。<必须采用快速排序或堆排序算法）

2）扩展型问题<可选择合适的数据结构）
<4）给定一个单词，按字典序输出字典 Dictionary 中所有以这个单词为前缀的单词。例如，如果字典 T={a,aa, aaa, b, ba}, 如果你输入 a,那么输出应该为{a, aa, aaa}。
<5）给定一个单词，输出在Dictionary 中以这个单词为前缀的单词的出现频率最高的10个单词，对于具有相同出现次数的情况，按照最近<即最后）插入的单词优先级比较高的原则输出。

对于以下问题，需采用2种不同的数据结构<hash散列与Trie树，并针对以下题目，比较两种数据结构的优缺点。）
3）高级型问题
<6）现在我们有一些Document，每个Document 由一些单词组成，现在的问题就是给你一个word，检索出哪些 Document包含这个word，输出这些Document的DocumentID<就如同搜索引擎一样，即输入一些关键字，然后检索出和这些关键字相关的文档）。
<7）在第<6）问中，我们只考虑了一个word在哪些Document中的情况，我们进一步考虑2个相邻word的情况，检索出同时包含这两个相邻word的DocumentID。

4）挑战型问题
<8）现在我们再对<7）的问题进行扩展，把<7）中的只检索相邻2个word推广到能够检索多个word<即连续的k个word，其中k>=2），检索出同时包含k个连续word的DocumentID。
◎实验目的：学会使用哈希函数检索，运用指定要求算法，解决一系列单词检索问题。
一． 需求分析
1.本演示程序中，由程序读取文件，根据程序要求自动生成所需要的文件。
2.演示程序执行结束后，由计算机终端显示“提示信息”，以示某一问题完成与否。
3.程序执行的命令包括：
（1） 读取文件；<2）构造字典；<3）实现查找；<4）实现排序；<4）写入结果。

二． 概要设计
为了实现上述操作，采用顺序表存储结构。

1.基本操作
Create_HashTable<）
操作结果：读取文件，生成一个字典Dictionary。
Search_Data(HNode Hash[]>
初始条件：存在一个顺序表Hash；
操作结果：读取文件，查找单词在字典Dictionary对应的出现次数，并写入另一文件；若不在字典Dictionary中，则写入NO。
Sort_Count(HNode Hash[]>
初始条件：存在一个顺序表Hash；
操作结果：查找出现次数最高的10个单词，并写入另一文件。
Same_PrefixData(HNode Hash[]>
初始条件：存在一个顺序表Hash；
操作结果：读取文件中的单词，查找字典Dictionary中以此单词为前缀的所有单词，并以字典序写入另一文件；若不存在，则写入空。

2. 本程序包含四个模块
(1>主函数模块；
(2>构造字典模块；
(3>查找次数模块；
(4>前缀匹配模块；
(5>排序及写入模块；

3.函数调用关系图
主函数模块
构造字典模块
查找次数模块
前缀匹配模块
排序及写入模块

三．详细设计

3. 结构体类型
#include<stdio.h>
#include<string.h>
#include<malloc.h>
#include<stdlib.h>
#define SIZE 10000 //哈希之后的链表数
#define len 50 //定义字符串的长度
#define MAX 40000 //定义CNode类型CList长度
#define MaxSize 10000 //定义CNode类型的PList以及PClist的长度

typedef struct CNode
{
char data[len]。 //单词
int count。 //单词出现的次数
}CNode。
CNode CList[MAX]。
CNode PList[MaxSize]。
CNode PCList[MaxSize]。

typedef struct Node
{
char data[len]。 //单词
struct Node *next。 //链表指针
int count。 //单词出现的次数
}Node。

typedef struct HNode
{
Node *right。//头结点指针
}HNode。
HNode Hash[SIZE]。

4. 每个模块的分析
(1> 主函数模块
int main(>
{
Create_HashTable(>。//生成字典
Search_data(Hash>。//实现查找单词对应次数
j=Sort_Count(Hash>。//查找出现单词的次数频数前十的单词
Same_PrefixData(Hash>。//查找以某单词为前缀的单词并排序
Same_PrefixFrequence(Hash>。
}
(2) 构造字典模块
void Create_HashTable(>
{//链地址法——利用哈希函数构造字典Dictionary，单词来自文档vocabulary.txt

for(i=0。i<SIZE。i++>Hash[i].right=NULL。//Hash[].right初始化
fp1=fopen("","r">。

while(!feof(fp1>>
{ fscanf(fp1,"%s",data>。
hd=ELFHash(data>。//ELFHash返回值
q=new Node；q->data=data。
q->count=1。
p=Hash[hd].right。

if(p==NULL>q->next=NULL。Hash[hd].right=q。
else
{
while(p!=NULL>
{r=strcmp(q->data,p->data>。
if(r==0>p->count++。break。//data相同，次数加1
else if(r<0>q->next=p。Hash[hd].right=q。break。//q插在p与头结点之间
else if(r>0>
{if(p->next==NULL>p->next=q。q->next=NULL。break。//p->next为空，直接尾部接入
else if(strcmp(q->data,p->next->data><0>//插入p与q之间
{q->next=p->next。p->next=q。break。}
else p=p->next。
}
}//while(p>
}//else
}//while(fp1>
fclose(fp1>。
}//Create_HashTable生成字典Dictionary

(3) 查找次数模块
void Search_data(HNode Hash[]>
{
FILE *fp1,*fp2。
fp1=fopen(“”,“r”>。fp2=fopen(“”,“w”>。

while(!feof(fp1>>
{
fscanf(fp1,"%s",ch>。
m=ELFHash(ch>。//ELFHash返回值
p=Hash[m].right。
while(p>
{comp=strcmp(ch,p->data>。
if(comp==0>fprintf(fp2,p->count>。break。//查找成功
else p=p->next。
}
if(p==NULL>//未找到该单词，CASE i:NO
fclose(>。
}//Search_data(>

在查找次数出现最高的10个单词中，我采用了堆排序，参考课本的堆排序算法。

(4) 前缀匹配模块
void Same_PrefixData(HNode Hash[]>
{//查找以某单词为前缀的所有单词，按字典序输出，单词来自文档TotPrefixWord.txt
Node *p。
FILE *fp1,*fp2。fp1=fopen("","r">。fp2=fopen("","w">；
while(!feof(fp1>>
{
fscanf(fp1,，ch>。k=1。strl=strlen(ch>。
for(j=0。j<SIZE。j++>
{p=Hash[j].right。
while(p>
{ for(i=0。i<strl。i++>if(ch[i]==p->data[i]>continue。else break。
if(i==strl>{strcpy(PList[k].data,p->data>。flag=1。k++。//查找成功
p=p->next。
}
if(flag==0>fprintf(>。//flag=0未找到相关单词
else if(flag==1>
{
flag=0。//重置flag
quickSort(PList,k-1>。//快速排序实现字典序输出单词
fprintf(>。
for(i=1。i<k。i++>fprintf(fp2,"%s\n",PList[i].data>。
}
}
fclose(>。
}//Same_PrefixData

在实现字典序输出单词，我采用了快排法，参考课本快排递归算法。
partition(>。qSort(>。quikSort(>

3. 函数关系调用图
main(>

Sort_Count
Same_PrefixData
Search_data
Create_HashTable

HeapSort

quickSort

4. 使用说明、测试分析及结果
1.<1）本程序的运行环境为VC6.0；
<2）进入演示程序后，显示提示信息：
-------问题<1）完成-------

-------问题<2）完成-------
见文档SearchWordInVocabulary_Result.txt

-------问题<3）完成-------
见文档MostFrequenceWord.txt

-------问题<4）完成-------
见文档TotPrefixWord_Result.txt

2.测试结果与分析
详见文件夹内所附文档

3.调试过程中遇到的问题是如何解决以及对设计与实现的回顾讨论与分析
<1）首先是对构造字典时，计数的一个错误；
与所提供的文档的对比时发现对单词出现次数的计数的问题，是在Create_Hash(>
函数中分情况讨论各种插入时，对部分情况考虑不周而导致的；
错误代码：
else if(r>0>
{
if(p->next!=NULL>
{
if(strcmp(q->data,p->next->data==0>
{ p->next->count++。break。}
else if(strcmp(q->data,p->next->data><0）
{q->next=p->next。p->next=q。break。}
p=p->next。
}
else if(p->next==NULL>
{p->next=q。 q->next=NULL。}
}
正确代码：
else if(r>0>
{ if(p->next==NULL>
{p->next=q。q->next=NULL。break。}
else if(strcmp(q->data,p->next->data><0>
{q->next=p->next。p->next=q。break。}
else p=p->next。
}

对p以及p->next的情况考虑不全，在同学的帮助下解决。

（2） 对堆排序。
考虑题目要求的只需要10位次数最高，构建大顶堆，控制其只调整10次，减少时间的浪费。

（3） 对实验题目的第五问。
一个半成品，纵然使用改写的冒泡排序需要30s的运行时间，却依然无法写入正确的顺序。
保证其稳定，选择冒泡。
附第五问半成品：
void Same_PrefixFrequence(HNode Hash[]>
{ char ch[len]。
int casel=1。
int flag。
int i,j,strl,k。
Node *p。
FILE *fp1,*fp2。
fp1=fopen("PrefixFrequence.txt","r">。
fp2=fopen("PrefixFrequence_Result.txt","w">。
while(!feof(fp1>>
{//读取文件
fscanf(fp1,"%s",ch>。
k=0。
strl=strlen(ch>。
flag=0。
for(j=0。j<SIZE。j++>
{
p=Hash[j].right。
while(p>
{
for(i=0。i<strl。i++>
{
if(ch[i]==p->data[i]>continue。
else break。
}
if(i==strl>
{
flag=1。
k++。
strcpy(PCList[k].data,p->data>。
PCList[k].count=p->count。
}
p=p->next。
}
}
if(flag==0>
{
fprintf(fp2,"CASE">。
fprintf(fp2," %d:\n",casel++>。
}
else if(flag==1>
{
flag=0。
fprintf(fp2,"CASE">。
fprintf(fp2," %d:\n",casel++>。
MP_Sort(PCList,k>。//冒泡排序实现按次数大小写入单词及次数
if(k<=10>
{//按要求查找的单词个数不超过十个，则全部写入
for(i=1。i<=k。i++>
{
fprintf(fp2,"%s %d\n",PCList[i].data,PCList[i].count >。
}
}
else
{//超过十个，按出现次数大小取前十个写入
for(i=1。i<=10。i++>
{
fprintf(fp2,"%s %d\n",PCList[i].data,PCList[i].count>。
}
}
}
}
fclose(fp1>。
fclose(fp2>。
printf("\n--------问题(5>完成--------\n见文件PrefixFrequence_Result.txt\n">。
}//Same_PrefixFrequence
void MP_Sort(CNode PCList[],int n>//n为数组元素个数
{//冒泡排序实现单词次数大小有序
int i,j,t。
char data[50]。
for(j=n。j>1。j-->
{
for(i=n。i>n-j+1。i-->//从尾部开始循环比较，大的数往前移
if(CList[i].count>PCList[i-1].count>
{
t=PCList[i].count。
strcpy(data,PCList[i].data>。
PCList[i].count=PCList[i-1].count。
strcpy(PCList[i].data,PCList[i-1].data>。
PCList[i-1].count=t。
strcpy(PCList[i-1].data,data>。
}

}

}//MP_Sort

在实验了改写的冒泡的正确性时，将其植入原程序中，却依然无法得到正确结果。时间仓促，未能解决。

4.运行界面

五．实验总结

本次课程设计主要涉及三个数据结构的知识，一个是Hash表，另一个是Trie Tree，第三个个是在信息检索中普遍使用的Inverted Index。完成本次课程设计的总体感受是，本次课程设计对数据结构的应用要求比较高，在整个设计过程深刻体会从最初编写程序到最终实现题目所要求的执行，这是这个学期以来编写的最大而复杂的程序，综合利用了这个学期所学习到的数据结构知识，发现自己在知识掌握上也并不是想象中那么熟练。由于不够熟练而促使自己回归课本，不断回顾基本知识，在理解题目意义的基础上，合理利用书本及在线提供的资料。。
第一次接触这种比较大型的单词检索的程序设计，第一步很是关键。俗话说：万事开头难。拿到第一题时，脑袋里掠过很多想法，比如运用字符串的ASCII码来确定单词的储存位置，可是又考虑到单词库中单词量上万，这样巨大的数据必会造成巨大冲突，即使使用线性探测再散列处理冲突也不是很理想。因此最终选用链地址法。跨出了第一步，其实是很让人鼓舞的。这次大作业，只做出来四小问，卡壳在第五问了。有一个重要原因就是对数据结构的选择。要选择既快又准确的，应该要属键树了。可是由于自己对树的知识掌握的不够，因此没有在规定时间内完成。
这次编程的突破是学习吸收了在线资料中的哈希字符串经典函数，大大改进了运行速度。在今后编程的道路上有两点体会需要时刻提醒自己：第一、当所编写的代码过长时，一定要注意对变量的取名，以及对注释语句的重视，很容易就被长长的代码搞糊涂，也能够注意备份；第二、在对程序的检验上不能放松，一定要尽量确保其正确性，因为一旦步步联系紧密，一步错，步步错。
由于本学期学时较紧，数据结构也重在实践，从理论运用到实际过程中发现自己的不足，这些是在仅仅依靠阅读课本基础上完全体会不到的。过程是艰辛的。一次一次遇到障碍，一次次纠正，甚至有些痛苦，但当最终显示0 error(s> 0 warning(s>，运行得到你想要的结果，真的很有成就感！！在今后的学习中一定提高自己对课本上知识的掌握的熟练程度，并在此基础上希望能经过可获得渠道拓展视野以丰富自己的知识储备。

教师评语：

实验成绩：

指导教师签名：

批阅日期：