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

一、设计题目：单词（词组）检索

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

1）基本型问题

1）选择合适的数据结构，将所有的英文单词生成一个字典dictionary。

2）给定一个单词，判断这个单词是否在字典 dictionary中。如果在单词库中，输出这个单词总共出现的次数。否则输出no。

2）扩展型问题

3）给定一个单词，按字典序输出字典 dictionary 中所有以这个单词为前缀的单词。例如，如果字典 t=, 如果你输入 a,那么输出应该为。

4）给定一个单词，输出在dictionary 中以这个单词为前缀的单词的出现频率最高的10个单词，对于具有相同出现次数的情况，按照最近（即最后）插入的单词优先级比较高的原则输出。

5）输出dictionary**现次数最高的10个单词。

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）问，题目要求选择适当的数据结构将一百二十多万个英文单词生成一个字典。我采用经典字典树结构进行构造，每个节点包括频度，时间，和后继二十六个指针。其中频度为单词的频度，若该字母为单词的最后一个字母，则该字母的pin为该单词的频度，否则pin为零。

时间为单词最后一次出现的次序，为（4）问服务。

对于（2）问，题目要求在字典里查询指定单词，若在字典中则输出在字典**现的次数，否则输出no。读入字母，根据字典树进行查找。若在字典树中存在最后一个字母，且最后一个字母的频度不为零，则该单词存在，出现次数即为该字母频度。

否则，该单词不存在。

对于（3）问，题目要求查找以指定单词为前缀的所有单词，并输出所有单词，若不存在，什么也不输出。我使用数组存储前缀和以此前缀为前缀的单词。若在字典树中存在这样的前缀，则从此节点按照字典顺序遍历字典树，并输出所有以此为前缀的所有单词。

若不存在这样的前缀，则什么也不输出。

对于（4）问，题目要求查找以指定单词为前缀的频度最高的十个单词，并按频度高低顺序输出。若频度相同，则按照最近（即最后）插入的单词优先级比较高的原则输出。若不满十个则全部输出。

我采用node t[10]存储频度最高的前十个单词，排序使用插入排序，对频度相同的单词，比较它们的time，若time比较大，则插到前面。

对于（5）问，题目要求输出字典中频度最高的十个单词。我采用node top[10]存储频度最高的前十个单词，遍历字典树，按照插入排序进行排序。

对于（6）问，题目要求在若干document中查找指定单词，若存在该单词，则输出所在document的id，要求输出所有存在的id。若不存在什么也不输出。由于（6）（7）（8）问与前五问使用的文件不相同，我在编写程序时，就把前五问与后面几问分开了。

我同样采用了字典树结构进行存储document中的单词，不过字母节点变成频度、坐标和二十六个后继指针。其中坐标为单词所在document的id和所在document的第几个顺序。在此问中，按照字典树查找指定单词，并输出单词所在document的id。

对于（7）问，题目要求在document中查找两个单词组成的词组。我先将读入的词组分成两个单词，分别在字典树中查找两个单词，得到两个单词的坐标。先比较两个单词的id，若id相同，则比较在document中的顺序，若前后两个单词的顺序，后一个单词比前一个单词顺序大1，则输出该id。

否则不输出。

对于（8）问，题目要求在document中查找k个单词组成的词组。由于时间的原因，我仅仅有思路，但未能将程序编写出来。我的思路是将词组拆分成k个单词，分别在字典树中查找，得出k个单词的坐标。

先对k个单词的id求交，得出在相同的id，再比较k个单词在document的位置是否连续，若连续则输出id。否则不输出。

三、概要设计：

1、节点设计：

前五问：typedef struct tnode

struct tnode *point[26];

int pin;

int time;

tnode;

/字典树节点，pin记录单词出现次数，time记录单词最后一次出现的次序。

typedef struct node

char k[40];

int flag;

int time;

node;/用来存前缀最高的十个单词。

2、主函数：

一至五问：void main()

int i;

tnode *root;

root=(struct tnode *)malloc(sizeof (struct tnode));

for (i=0;i<26;i++)

printf("程序开始运行打开文件“开始生成字典");

createtree(root);

printf("生成字典成功第一问解决打开文件“开始查找单词");

search(root);

printf("查找结束结果保存在文件“searchwordinvocabulary_第二问解决打开文件“开始查找前缀单词");

prefix(root);

printf("查找结束结果保存在文件“totprefixword_第三问解决打开文件“开始查找前缀出现频率最高的十个单词");

prefixqueue(root);

printf("查找结束结果保存在文件“prefixfrequence_第四问解决开始查找频率最高的十个单词");

mostfrequence(root);

printf("查找结束结果保存在文件“前五问解决");

3、函数分析：

一至五问：1） void createtree(tnode *root)

（1）读入单词，构造字典树）

2） void search(tnode *root)

（2）读入要查找的单词进行查找，若在字典中存在，则输出频度。否则输出no）

3） void printf(tnode *item,file *fp2,char *a,int k)

4） void prefix(tnode *root)

查找指定前缀，若存在，则在（3）中进行输出以该单词为前缀的所有单词；若不存在，什么也不输出）

5） void printf1(tnode *item,char *a,int k,node *t)

6） void prefixqueue(tnode *root)

（6）查找指定前缀，若存在，则在（5）中进行排序并输出频度最高的十个单词；否则什么也不输出）

7） void most(tnode *item,int i,node *top,char *a)

8） void mostfrequence(tnode *root)

四测试结果：

注：大约八秒程序执行完毕。

五设计心得：

这次的课程设计，加强了我们动手能力。巩固和加深了对数据结构的理解，提高综合运用本课程所学知识的能力。培养了我选用参考书，查阅手册及文献资料、灵活运用网络的能力。

培养独立思考，深入研究，分析问题、解决问题的能力。通过实际问题的分析设计、编程调试，掌握具体问题的分析方法和解决问题方法。通过课程设计，培养了我严肃认真的学习态度，逐步建立正确的部分与全局的观念。

而且做课程设计同时也是对课本知识的巩固和加强，平时看课本时，有些问题就不是很能理解，做完课程设计，那些问题就迎刃而解了。而且还可以记住很多东西。认识**于实践，实践是认识的动力和最终目的，实践是检验真理的唯一标准。

这次的课程设计使我懂得了理论与实际相结合是很非常重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，才能提高自己的实际动手能力和独立思考的能力。在整个设计过程中，构思是很花费时间的。调试时经常会遇到这样那样的错误，有的是因为粗心造成的语法错误。

当然，很多也时用错了算法，总是实现不了。同时在设计的过程中发现了自己的不足之处，对以前所学过的知识理解得不够深刻，掌握得不够牢固。

通过这次的课程设计，让我更加了解到数据结构的重要性。以及它对我们专业的发展发挥的作用。对我们而言，知识上的收获很重要，但精神上的丰收更加可喜。

让我知道了学无止境的道理。我们每一个人永远不能满足于现有的成就。此次课程设计，学到了很多课内学不到的东西，比如独立思考解决问题，出现差错的随机应变，这些都让我受益非浅。

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

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

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

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

其他用户还读了