数据结构课程
实习报告
一、需求分析
1． 本程序要求根据输入建立图书名称表，采用散列表实现该表，散列函数选用BKDE 字符串哈希。
2． 若查找成功，则在界面出现要查找的图书，若查找不成功，则输出此书不存在，查找不成功。
（2） 输入：
（3） 4
（4） a
（5） ans
（6） and
（7） hellocpp
（8） 9
（9） a
（10） b
（11） an
（12） as
（13） ans
（14） and
（15） ande
（16） hellocbb
（17） hellocpp
（18）
（19）
（20） 输出：
（21） YES
（22） NO
（23） NO
（24） NO
（25） YES
（26） YES
（27） NO
（28） NO
（29） YES
（30）
二、概要设计
抽象数据类型
为实现上述程序的功能，应以字符串存储输入。
算法的基本思想
根据题目要求，采用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)称二次探测再散列;
程序的流程
程序由五个模块组成：
（1） 定义模块：对程序设计过程中用到的变量进行定义。
（2） 输入模块：编程实现从键盘输入各图书信息。
（3） 哈希模块：用BKDE字符串哈希函数建立图书名称表。
（4） 解决冲突模块：用二次探测再散列法解决冲突。
（5） 查找输出模块：根据关键字查找图书。若查找成功，显示信息，查找失败，输出：此书不存在。
三、详细设计
物理数据类型
题目要求输入每本书的书名都是一组小写字母组成，长度不超过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>>NUM_BER;
? int i;
? for(i=0;i<NUM_BER;i++){
? cout<<"请输入第"<<i+1<<"个记录的书名:\n";
? cin>>a[i].name;
?
? //gets(str2);??????
? }
? }
? void ShowInformation(Record* a)//显示输入的图书信息
? {
? int i;
? for( i=0;i<NUM_BER;i++)
? cout<<"\n第"<<i+1<<"本图书信息:\n 书 名："<<a[i].name<<"\n";
? }
? void Cls(Record* a){
? cout<<"*";
? system("cls");
? }
? unsigned int hash_BKDE(char *str)
? {
? /* 初始种子 seed 可取31 131 1313 13131 131313 etc.. */
? unsigned int seed = 131;
? unsigned int hash = 0;
? while (*str)
? {
? hash = hash * seed + (*str++);
? }
? return (hash & 0x7FFFFFFF);
? }
? Status collision(int p,int &c){//冲突处理函数，采用二次探测再散列法解决冲突
? int i,q;
? i=c/2+1;
? while(i<HASHSIZE){
? if(c%2==0){
? c++;
? q=(p+i*i)%HASHSIZE;
? if(q>=0) return q;
? else i=c/2+1;
? }
? else{
? q=(p-i*i)%HASHSIZE;
? c++;
? if(q>=0) return q;
? else i=c/2+1;
? }
? }
? return UNSUCCESS;
? }
? void benGetTime();
? void Createhash_BKDE (HashTable* H,Record* a){//建表，以书的名字为关键字，建立相应的散列表
? //若哈希地址冲突，进行冲突处理
? benGetTime();
? int i,p=-1,c,pp;
? for(i=0;i<NUM_BER;i++){
? c=0;
? p= hash_BKDE (a[i].name);
? pp=p;
? while(H->elem[pp]!=NULL) {
? pp=collision(p,c);
? if(pp<0){
? cout<<"第"<<i+1<<"记录无法解决冲突";//需要显示冲突次数时输出
? continue;
? }//无法解决冲突，跳入下一循环
? }
? H->elem[pp]=&(a[i]); //求得哈希地址，将信息存入
? H->count++;
? cout<<"第"<<i+1<<"个记录冲突次数为"<<c<<".\n";//需要显示冲突次数时输出
? }
? cout<<"\n建表完成!\n此哈希表容量为"<<HASHSIZE<<",当前表内存储的记录个数为"<<H->count<<".\n";
? benGetTime();
? }
? void Searchhash_BKDE (HashTable* H,int &c){//查找书名关键字，若查找成功，显示信息
? //c用来记录冲突次数,查找成功时显示冲突次数
? benGetTime();
? NA str;
? cout<<"\n请输入要查找记录的书名：\n";
? cin>>str;
? int p,pp;
? p= hash_BKDE (str);
? pp=p;
? while((H->elem[pp]!=NULL)&&(eq(str,H->elem[pp]->name)==-1))
? pp=collision(p,c);
? if(H->elem[pp]!=NULL&&eq(str,H->elem[pp]->name)==1){
? cout<<"\n查找成功！\n查找过程冲突次数为"<<c<<"．以下是您需要要查找的信息：\n\n";
? cout<<"书 名："<<H->elem[pp]->name<< "\n";
? }
? else cout<<"\n此书不存在，查找不成功!\n";
? benGetTime();
? }
? void benGetTime(){
? SYSTEMTIME sys;
? GetLocalTime( &sys );
? cout<<sys.wYear<<sys.wMonth<<sys.wDay<<sys.wHour<<sys.wMinute<<sys.wSecond<<sys.wMilliseconds;
? }
? void Save(){
? FILE *fp;
? if((fp=fopen("c:\test.txt", "w"))==NULL){
? printf("\nERROR opening customet file");
? }
? fclose(fp);
? }
? int main(int argc, char* argv[]){
? int c,flag=1;
? HashTable *H;
? H=(HashTable*)malloc(LEN);
? for(int i=0;i<HASHSIZE;i++)
? H->elem[i]=NULL;
? H->size=HASHSIZE;
? H->count=0;
? Record a[MAX_SIZE];
? while (1){
? cout<<"\n ┏━━━━━━━━━━━━━┓ ";
? cout<<"\n ┃ 欢迎使用图书查找系统 ┃ ";
? cout<<"\n ┏〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓┓";
? cout<<"\n ┃★ ★ ★ ★ ★ ★ ★哈希表的设计与实现★ ★ ★ ★ ★ ★ ★┃";
? cout<<"\n ┃ 【1】. 添加书本信息 ┃";
? cout<<"\n ┃ 【2】. 读取所有书本信息 ┃";
? cout<<"\n ┃ 【3】. 以书名建立哈希表(BKDE字符串哈希解决冲突) ┃";
? cout<<"\n ┃ 【4】. 查找并显示给定书名的记录 ┃";
? cout<<"\n ┃ 【5】. 清屏 ┃";
? cout<<"\n ┃ 【6】. 保存 ┃";
? cout<<"\n ┃ 【7】. 退出程序 ┃";
? cout<<"\n ┃ 温馨提示： ┃";
? cout<<"\n ┃ Ⅰ.进行4操作前 请先输出3 ┃";
? cout<<"\n ┗〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓┛";
? cout<<"\n";
? cout<<"请输入一个任务选项>>>";
? cout<<"\n";
? int num;
? cin>>num;
? switch(num){
? case 1:
? getin(a);
? break;
? case 2:
? ShowInformation(a);
? break;
? case 3:
? Createhash_BKDE (H,a); /* 以书名建立哈希表 */
? break;
? case 4:
? c=0;
? Searchhash_BKDE (H,c);
? break;
?
? case 5:
? Cls(a);
? break;
? case 6:
? Save();
? break;
? case 7:
? return 0;
? break;
? default:
? cout<<"你输错了，请重新输入!";
? cout<<"\n";
? }
? }
? system("pause");
? return 0;
? }
?