数据结构课程实习报告.doc

数据结构课程 实习报告 一、需求分析 本程序要求根据输入建立图书名称表，采用散列表实现该表，散列函数选用BKDE 字符串哈希。 若查找成功，则在界面出现要查找的图书，若查找不成功，则输出此书不存在，查找不成功。 输入： 4 a ans and hellocpp 9 a b an as ans and ande hellocbb hellocpp 输出： YES NO NO NO YES YES NO NO YES 二、概要设计 抽象数据类型 为实现上述程序的功能，应以字符串存储输入。 算法的基本思想 根据题目要求，采用BKDE字符串哈希函数，在解决冲突时使用二次探测再散列法。 二次探测再散列法的简介：Hi=(H(key) + di) MOD m, i=1,2,…, k(k<=m-1)，其中H(key)为散列函数，m为散列表长，di为增量序列， 2. di=1^2, (-1)^2, 2^2,(-2)^2, (3)^2, …, ±(k)^2,(k<=m/2)称二次探测再散列; 程序的流程 程序由五个模块组成： 定义模块：对程序设计过程中用到的变量进行定义。 输入模块：编程实现从键盘输入各图书信息。 哈希模块：用BKDE字符串哈希函数建立图书名称表。 解决冲突模块：用二次探测再散列法解决冲突。 查找输出模块：根据关键字查找图书。若查找成功，显示信息，查找失败，输出：此书不存在。 三、详细设计 物理数据类型 题目要求输入每本书的书名都是一组小写字母组成，长度不超过100字符。 编程的具体步骤 定义——输入——哈希函数——解决冲突——建表——查找输出 算法的时空分析 散列表在理想情况下，查找、插入、删除操作的时间均为O(1)，是一种高效的动态集合结构。 输入和输出的格式 输入分为两部分 第一部分，第一行是行数n，n <= 5000。余下n行，每行一个字符串。表示已存在的图书记录。 第二部分，第一行是行数m，m <= 1000。余下m行，每行一个字符串。表示要查询的图书记录。 输出： 输出为m行，如果被查的记录存在，则输出"YES",如果不存在则输出"NO"。 四、测试结果 五、用户使用说明 该程序可以实现7个任务： 输入1，实现添加书本信息的任务 输入2，实现读取所有书本信息的任务 输入3，实现以书名建立哈希表的任务 输入4，实现查找并显示给定书名的记录的任务 输入5，实现清屏的任务 输入6，实现保存的任务 输入7，实现退出程序的任务 温馨提示：在进行任务4时应该先进行任务3的操作。 六、实验心得 通过本次的数据结构实验，我学习到了很多知识，因为之前学习的C语言知识都遗忘得差不多了，所以在编写程序时遇到了很多的困难，通过上网查找相关程序并模仿学习，终于将程序改写出来了，但是在调试的过程中也遇到了不少的麻烦，出现了很多的错误，又遇上数字信号处理的考试，真的很纠结，组员们也尽力地将程序调试好，终于看到一个没有错误的程序时，我们都无比的高兴，虽然与老师的要求还是有一定的差距，但是我们在这个过程中学习到的知识是无价的，我们将会继续努力，在以后更多的实验，课题设计过程中不断积累。 七、附录 源程序： #include<stdio.h> #include<iostream.h> #include<stdlib.h> #include<string> #include <windows.h> #define MAX_SIZE 100 //书名的最大长度 #define HASHSIZE 500 //定义表长 #define SUCCESS 1 #define UNSUCCESS -1 #define LEN sizeof(HashTable) typedef int Status; typedef char NA[MAX_SIZE]; ? typedef struct{//记录 NA name; }Record; typedef struct{//哈希表 Record *elem[HASHSIZE]; //数据元素存储基址 int count; //当前数据元素个数 int size; //当前容量 }HashTable; Status eq(NA x,NA y){//关键字比较，相等返回SUCCESS；否则返回UNSUCCESS if(strcmp(x,y)==0) return SUCCESS; else return UNSUCCESS; } Status NUM_BER; //记录的个数 void getin(Record* a){//键盘输入各图书的信息 cout<<"输入要添加的个数：\n"; cin