《数据结构》实验报告

班级:_10011006_ 姓 名:__刘恋__ 学 号:_2010302521_ E-mail:_1020383169@qq.com_

日期:_20##年12月30日_

◎实验题目:

构建一个字典树，并实现相关的查找任务

◎实验目的：

设计存储结构完成字典树的构建以及设计程序完成其他功能

◎实验内容：

一、需求分析

1、 输入的形式和输入值的范围：

从文本中读入单词

2、 输出的形式：

将相应的查找结果输出到文本中

3、 程序所能达到的功能：

生成字典树并完成查找单词等的功能

4、 测试数据：

文本“vocabulary.txt”，“PrefixFrequenceWord.txt”,“TotPrefixWord.txt”,“SearchWordInVocabulary.txt”中的数据

二 概要设计

PTireNode TireTree(PTireNode node);

生成26叉树。

void InitTireTree(PTireNode Head, char str[], int num);

初始化字典。

void SearchWord(PTireNode Head, char str[], int num, FILE *f);

查找单词。

void ExportWord(PTireNode node, FILE *f);

按字典序顺序输出具有相同词头的单词。

void GetTenPreWord(PTireNode node);

找到频率最高的十个单词。

PTireNode ReadPrefix(PTireNode Head, char str[], char word[]);

读入词头并判断词头是否存在。

主程序流程：

第一步：输出提示语，用户输入数据。

第二步：判断用户的输入值，选择对应的程序实现相应的功能。

第三步：直至用户输入结束程序指令，否则重复执行第一步和第二步。

主程序中除去几个提示语句的输出，其余的操作全部调用函数完成。

三 详细设计

  实现概要设计中定义的所有数据类型，对每个操作只需要写出伪码算法；对主程序和其他模块也都需要写出伪码算法；画出函数的调用关系。 

Main()

Inputchar(from 1 to 6)

Switch()

Case 1: task1

Case 2: task2

Case 3: task3

Case 4: task4

Case 5: task5

Case 6: exit program

End

四 使用说明、测试分析及结果

1、 说明如何使用你编写的程序；

根据程序的提示语句便可使用。

2、 测试结果与分析；

测试结果和给予的程序调试结果相同

3、 调试过程中遇到的问题是如何解决提以及对设计与实现的回顾讨论和分析；

在编写第一个程序，也就是构建字典树时，并没有遇到很大问题，然而在开始编写查找单词的有关程序时便遇到了困难。其中，最主要的是对26叉树的递归遍历没能很好的写出，始终纠结在遍历算法中，没有正确认识递归的使用方法，使得我在编写程序时始终不能完成程序的功能，最终，在网上以及和同学探讨之后，理解了递归程序编写的要诀，进而完成了26叉树的递归遍历，为以后的程序奠定了基础，也让我对递归有了更深刻的认识。同时，在编写程序过程中，对递归过程中数据的记录有了更好的领悟。自己设计了一个存储结构体完成了对第三、第四、第五题的辅助存储，让程序能够顺利完成，但对于时间复杂度和空间复杂度没能很好的控制，程序的运行时间比参考时间长，很明显的是第四和第五题。或许是程序的存储结构需要改进，这个我会在接下来的时间里不断尝试，改进程序。

4、 运行界面。

程序的提示文字会引导用户使用此程序

五、实验总结

    加深了我对递归程序的理解，更加全面的让我认识到了递归操作在程序编写中所起的重要作用。同时，面对不同的问题构造不同的数据结构也让我对“数据结构”这门课程有了新的认识，提高了我将逻辑结构转化为物理结构的能了，增强了程序的编写能力。

(一) 需求分析

本程序主要是完成一个字典的构建以及相关的搜索功能

(二) 概要设计

根据程序需求，设计用26叉树完成字典树的建立的查询

1．基本操作：

void GetTenPreWord(PTireNode node)

  操作结果：找到频率最高的十个单词。

void ExportWord(PTireNode node, FILE *f)

  初始条件：字典树构建完成；

  操作结果：按字典序顺序输出具有相同词头的单词。

void SearchWord(PTireNode Head, char str[], int num, FILE *f)

   初始条件：字典树构建完成；

   操作结果：查找单词并输出结果到文本中。

PTireNode TireTree(PTireNode node)

   操作结果：生成26叉树，进而生成字典。

2．本程序包含三个模块：

（1）主程序模块；

（2）判断用户输入并选择程序功能模块

（3）运算和输出模块；

模块调用图：

 (三) 详细设计

1．元素类型，结点类型和指针类型：

typedef struct TireNode//存储的结构体：26叉树

{

    char letter;

    int tag,frequency;

    long order;//单词输入的次序

    TireNode *add[MAX_VERTEX_NUM];

}TireNode,*PTireNode;

typedef struct Record//用于作为中间存储的结构体

{

    char record[50];//记录单词

    int frequency;//记录相应单词的频率

    long order;//记录相应单词的输入顺序

}record;    

   

2．每个模块的分析：

（1）主程序模块：

int main()

{

    char tag;

    WelcomeDesk();//调用函数输出程序开始界面

    do

    {

        tag=getchar();//用户输入选项

        Selection(tag);//判断用户的输入并调用函数完成程序的功能

    }while(1);

    return 0;

}

（2）判断用户输入并选择程序功能；

void Selection(char tag)

{

//调用Task1—Task5完成程序的功能

    switch(tag)

    {

    case '1': {Task1();system("cls");WelcomeDesk();break;}

    case '2': {Task2();system("cls");WelcomeDesk();break;}

    case '3': {Task3();system("cls");WelcomeDesk();break;}

    case '4': {Task4();system("cls");WelcomeDesk();break;}

    case '5': {Task5();system("cls");WelcomeDesk();break;}

    case '6': {system("cls");printf("\n\n\n\n感谢您的使用！\n");Sleep(2000);exit(-1);break;}

    }

}

函数调用关系图

3．完整的程序：(见源文件).

 (四) 程序使用说明及测试结果

1．程序使用说明

（1）本程序的运行环境为VC6.0。

（2）进入演示程序后即显示提示信息：

/*****************************************/

        欢迎使用本程序！

请按照选项进行操作

1：建立字典树

2：查找单词

3：输出前缀单词（按字典序顺序）

4：输出频率最高的十个前缀单词

5：输出字典中所有单词中频率最高的十个单词

6：退出程序

/*****************************************/

请选择程序的功能：

2．测试结果

结果分别输出“SearchWordInVocabulary_Result.txt”，“PrefixFrequence_Result.txt”，“TotPrefixWord_Result.txt”，“MostFrequenceWord.txt”中。

3．调试中的错误及解决办法。(遇到时给出)

一开始编写递归输出查询的单词，总是将新的单词连接到之前输出的单词后面，在调试过程中发现在我使用的简介存储结构字符串中，需要对字符串的下一个字母位置进行标记，从而在递归的过程中明确每一个存入的字母的位置，进而使用了“depth”这个“指针”指示字母的位置：进入递归的时候指针后移，跳出递归的时候指针回退。这样就完成了对字典树上不同层的字母的存储和输出，解决了遇到的问题。

4．运行界面

在每次程序完成功能后都会返回欢迎界面等待用户的再次选择，直到用户选择关闭程序才退出程序界面。（所有的操作结果输出到指定的文本中）

（五）、实验总结(实验心得)

本次程序实验大课，每天平均6个小时的程序编写让我真切的感受到一个计算机学院学生应该有的大学生活，虽然说长时间面对电脑不是一件好事，不过对于我们这个专业而言，只有长时间的在电脑上调试自己的程序才能对课本上学到的东西有更深刻的理解。同时，在编写程序过程中，和同学的交流也是至关重要的，互相的交流可能没有什么实际的结果，但会给自己的思路提供一个更广阔的平台，减少“弯路”，更快的达到程序的目的。同时，在程序实践中不能因为学习的越多，思路就越复杂。程序的目的是完成相应的功能，一昧的讲究程序结构的建设可能会抹杀我们程序的初衷，在本次试验过程中我就经历过这样的事情，一位同学用很简单，很直接的思路解决了一个问题，但我还是纠结在结构的构架上。虽然他的思路被证实在数据只要多一点点就无法执行，但也给我不少启示，程序的编写结构固然重要，但是思路的清晰和明了才是最重要的，否则程序只能是一团乱麻，并且还降低了编写程序的信心。实验大课结束了，但我还有后面几道题没能完成，其实第六题已经能够查找1000个文件了，但是数量一多程序就崩溃了，希望在以后的时间里我能够完成本次实验的所有题目，并对之前的程序加以优化。

教师评语：

实验成绩：

指导教师签名：      

批阅日期：      

第二篇：数据结构大作业实验报告要求 [1]

浙江工商大学计算机与信息工程学院

数据结构实验大作业报告

专 业：

班 级：

学 号： 1092110101 姓 名：

指导教师：

20xx年物流管理 物流10甲 汪法成 杨文武 月 12

一、 大作业报告内容包括以下几个部分

⒈ 问题描述：(题目)

⒉ 设计：

⑴ 数据结构设计和核心算法设计描述；

⑵ 主控及功能模块层次结构；

⑶ 主要功能模块的输入、处理(算法框架描述)和输出；

⑷ 功能模块之间的调用与被调用关系等。

⒊ 测试： 测试范例，测试结果，测试结果的分析与讨论，测试过程中遇到的主要问题及所采用的解决措施。

⒋ 使用说明和作业小结：

⑴ 使用说明主要描述如何使用你的程序以及使用时的主要事项；

⑵ 在小结中说明程序的改进思想、经验和体会；

⒌整理一份程序清单及运行示例的结果。

将以上各项文字材料及程序清单等装订成册，形成一个完整的报告。

题目从以下题目中任选一个，每人1个题目。

（三）停车场管理问题

[问题描述] 设有一个可以停放n辆汽车的狭长停车场，它只有一个大门可以供车辆进出。车辆按到达停车场时间的早晚依次从停车场最里面向大门口处停放(最先到达的第一辆车放在停车场的最里面)。如果停车场已放满n辆车，则后来的车辆只能在停车场大门外的便道上等待，一旦停车场内有车开走，则排在便道上的第一辆车就进入停车场。停车场内如有某辆车要开走，在它之后进入停车场的车都必须先退出停车场为它让路，待其开出停车场后，这些车辆再依原来的次序进场。每辆车在离开停车场时，都应根据它在停车场内停留的时间长短交费。如果停留在便道上的车未进停车场就要离去，允许其离去，不收停车费，并且仍然保持在便道上等待的车辆的次序。编制一程序模拟该停车场的管理。

[实现要求] 要求程序输出每辆车到达后的停车位置(停车场或便道上)，以及某辆车离开停车场时应交纳的费用和它在停车场内停留的时间。

[实现提示] 汽车的模拟输入信息格式可以是：(到达／离去，汽车牌照号码，到达／离去的时刻)。例如，(‘A’，，1，5)表示1号牌照车在5这个时刻到达，而(‘D’，，5，20)表示5号牌照车在20这个时刻离去。整个程序可以在输入信息为(‘E’，0，0)时结束。本题可用栈和队列来实现。