数据结构设计报告

数据结构课程设计报告书班级 BX1001 专业计算机科学与技术学号 101003020139姓名 赵冠博课题描述：哈希表的查找与实现分析1、需求分析：本次课程设计需要实现哈希表的建立和查找，具体内容如下：建立哈希函数，从而根据用户输入的数据元素个数和各元素的值建立哈希 表，即数据的添加和存储。如果输入的元素个数超出规定范围，则打印出错信 息，并提示重新输入信息。哈希表建立好之后，用户可以输入想要查找的值，屏幕显示相应信息。如 果存在此值，屏幕显示该值信息；如果不存在，则显示该值不存在；如果想退 出系统，则按提示输入命令。2、总体结构设计：1 一个哈希表结构hashtable，2个main （）主函数（完成数据输入和函数调用）、3五个功能函数：Initialhash（）初始化哈希表Printhash（）输出哈希表的所有元素及其位置Searchhash （）查找哈希表inserthash （）查找哈希表deletehash （）/查找哈希表3、各子模块设计:构成如下图所示:【设计思想】选取某个函数，依该函数按关键字计算元素的存储位置，并按此存放；查 找时，由同一个函数对给定值kx计算地址，将kx与地址单元中元素关键字进行 比较，确定查找是否成功，这就是哈希方法。哈希方法中使用的转换函数称为哈希函数。程序首先通过插入操作建立哈希表，接着显示数据，然后运用哈希 查找找到数据，如没有找到则显示查找错误，找到则显示查找成功。4、编程实现:【实验程序主要代码】：/哈希表的最大容量，与所采用的哈希函数有关#define MAXSIZE 12 enum B00LFalse,True; enum HAVEORNOTNULLKEY,HAVEKEY,DELKEY;/哈希表元素的三种状态，没有记录、有记录、有过记录但已被删除 typedef st ruct/定义哈希表的结构 int elemMAXSIZE;/数据元素体HashTable;typedef struct int keynum;/记录的数据域，只有关键字一项Record;void InitialHash(HashTable&);/初始化哈希表void PrintHash(HashTable);/显示哈希表中的所有元素BOOL SearchHash(HashTable,i nt,int&);/在哈希表中查找元素BOOL InsertHash(HashTable&,Record);/在哈希表中插入元素BOOL DeleteHash(HashTable&,Record);/在哈希表中删除元素int Hash(int);/哈希函数void main() HashTable H;/声明哈希表H/哈希表中当前元素的个数char ch,j二，y，; int posi tion ,n,k; Record R;BOOL temp;InitialHash(H); while(j!二n)printf(nt哈希查找)printf(nt*)printf(nt*1建表*)printf (nt*2显示*)printf (nt*3查找*)printf (nt*4插入*)printf(nt*5删除*)printf(nt*0退出*)printf(nt*)HAVEORNOT elemflagMAXSIZE;/元素状态，没有记录、有记录、有过记录但已被删除 int count;printf(nnt请输入菜单号：)；scanf( %c, &ch);/输入操作选项switch(ch) case l:prin tf (n 请输入元素个数(10):);scanf(%d，&n);printf(n)；for( k=0;kn;k+) printf(请输入第%3d个整数：,k+1);scanf(%d, &R.keynum); /输入要插入的记录t emp=Inser tHash(H,R);；break;case 2: if (H.count) PrintHash(H);/ 哈希表不空else prin tf (n 散列表为空表!n); break;case 3:if(!H.count) printf(n散列表为空表！n);/ 哈希表空else prin tf(n请你输入要查找元素(in t):); scanf(%d, &R.keynum);/输入待查记录的关键字t emp=SearchHash(H,R.keynum,posi tion);/ temp二True:记录查找成功；temp二False:没有找到待查记录 辻(t emp) prin tf (n查找成功该元素位置是%dn,posi tion); else prin tf(n本散列表没有该元素!n);break;case 4:if(H.count=MAXSIZE)/ 哈希表已满 printf (n散列表已经满!n);break; prin tf (n请输入要插入元素(in t):);scanf(%d, &R.keynum);/输入要插入的记录t emp=Inser tHash(H,R);/ temp=True:记录插入成功；temp二False:已存在关键字相同的记录 if( temp) prin tf (n 元素插入成功！n);else prin tf(n元素插入失败，相同元素本散列表已经存在!n); break;case 5:printf(n请你输入 要删除元素(int):);scanf(%d, &R.keynum);/输入要删除记录的关键字t emp二Dele teHash(H,R);/ temp=True:记录删除成功；temp=False:待删记录不存在 if( temp) prin tf(n 删除成功！n);else prin tf(n删除元素不在散列表中！n); break;defau lt: j=n;printf(nt欢迎再次使用本程序，再见!n);void InitialHash(HashTable &H) / 哈希表初始化 int i;H.cou nt=0;for(i=0;iMAXSIZE;i+) H.elemflagi=NULLKEY;void PrintHash(HashTable H) /显示哈希表所有元素及其所在位置 int i;for(i=0;iMAXSIZE;i+) printf(%-4d，i);/ 显示哈希表中记录所在位置printf(n)；for(i=0;iMAXSIZE;i+)/显示哈希表中记录值if(H.elemflagi=HAVEKEY) pri ntf (%-4d,H.elemi);elseprintf(%4c,);printf(ncount:%dn,H.count);/ 显示哈希表当前记录数BOOL SearchHash(HashTable H,int k,int &p) /在开放定址哈希表H中查找关键字为k的数据元素，若查找成功，以p指示待查/数据元素在表中的位置，并返回True；否则，以p指示插入位置，并返回False int p1;p1=p=Hash(k);/求得哈希地址while(H.elemflagp=HAVEKEY&k!=H.elemp) /该位置填有记录并且关键字不相等 p+；/冲突处理方法：线性探测再散列if(p=MAXSIZE) p=p%MAXSIZE;/ 循环搜索if(p=p1) re turn False;/整个表已搜索完，没有找到待查元素if(k=H.elemp &H.elemflagp=HAVEKEY)/ 查找成功，p 指示待查元素位置return True;else re turn False;/ 查找不成功BOOL InsertHash(HashTable &H,Record e) /查找不成功时插入元素e到开放定址哈希表H中，并返回True，否则返回Falseint p;if(SearchHash(H,e.keynum,p)/表中已有与e有相同关键字的元素return False;else H.elemflagp=HAVEKEY;/设置标志为HAVEKEY，表示该位置已有记录H.elemp=e.keynum;/ 插入记录H.count+;/哈希表当前长度加一return True;BOOL DeleteHash(HashTable &H,Record e) /在查找成功时删除待删元素e,并返回True，否则返回Falseint p;if(!SearchHash(H,e.keynum,p) else H.elemflagp=DELKEY;H.count;return True;int Hash(int kn) return (kn%ll); return False;/表中不存在待删元素/设置标志为DELKEY，表明该元素已被删除/哈希表当前长度减一/ 哈希函数：H(key)=key MOD 115、测试结果:【程序运行结果】建表和显示:-|口| Xg我的工作文件、教案与课件、数据结构本人电子教案10计算机实崟Debug实鑿9 :哈希查找哈希查找表示找入留 建显杳一插删退 - -1 2 3 4 5 0请输入菜单号:1请输入元素个数10= ?入入入入入入入入入 主闻主星垦闻主星垦闻主闻主阳1个整数2个整数3个整数4个整数 E个整数6个整数 ?个整数8个整数9个整数233616284087496062表示找入留 建显查插删退 - -1 2 3 4 5 0请输人菜单号：201234567891011233616284049608762GQLint : 9查找:我的工作左件教案与课件数齬结构、本人电子教案X0计算机实SDebue实鑿9 :哙希查找 国回哈希查找表示找入富 建显查插删退 - -1 2 3 4 5 0请输入菜单号：3请你输入要查找元素 ：28 查找成功该元素位置是6哈希查找表示找入雷 建显查插删退请输入菜单号：3 请你输入要查找元素 ：2? 本散列表没有该元素？插入:7777-1 I - .T . T鮮Pl.寒:11bit ）：38看斷?.薫車门4请输人菜单号，20123-35671111& Z33bZB 4U 4!# 阳 87 强 UHlUt : 1 MZi=rK轉盖舄M7W亠:n找F示费留- 一 - 8 建並*a11退一 二一 一 一 一 一 一= 二-Z 二-一 P 一 c i i i i i - “ 二一 一一 一 i 】 1 s- 1 4- 5 BK K M * * *汁乂亡用比辽-删除:的工作立件、教案与课件数据结构本人电子教案10计算机、实feDebe实鑿9 :喑希查找-|n|x|表示找入靑 建显查插删退 - -1 2 3 4 5 0请输入菜单号：5请你输入 要删除元素int：49删除成功！哈希查找表示找入留建显查插删退-1 2 3 4 5 0请输入菜单号:201234567891011302336162840608762count: 9通过分析输入数据和运行结果，证明程序顺利完成实验内容和要求。6、总结:通过这个星期的课程设计，我的收获还是不少。我的c语言水平有了比较 大的提高，其中c语言关于指针，链表的操作理解的比以前深刻不少。另外是 数据结构方面的提咼，对存储结构，及各种查找排序方面也有不少的提咼。虽 然我做的程序里还有写问题，做的不够深入，但独立完成一个比较大一点的程 序的经历也是很宝贵的。通过这次做课程设计，使我对数据结构这门课的认识更进一步，这门课确 实是学好计算机程序设计的基础。与此同时，自己对程序设计中应该注意的一 些问题也有了自己的一些想法。首先，一个程序要达到正确性，可读性，健壮 性，高效率和低存储量的要求，这样用户在使用程序的时候才会更加满意，程 序才能得到更多的关注。其次，要养成良好的编程习惯，在做一个程序之前， 要对该程序的存储结构，抽象数据类型和应该具备的功能以及各模块之间的调 用关系有一个总体的把握，画出必要的算法流程图或写出必要的伪码来表示各 模块应该具备的功能。再次，在编写程序的过程中应该对一些难于理解的地方 加上必要的注释，这样会使在之后的调试与维护阶段更加容易，在定义功能函 数与变量时应该尽量采取有表征意义的名称，这样也可达到见名知意的效果。 最后，在程序的调试阶段，应该针对程序中用户可能进行的错误操作给出解决 的方法，要尽量选出几组具有毁灭性的数据来进行测试，在程序不能正常处理 的情况下要采取一些方案使这样的问题得以解决。做程序是一个比较累的工 作，特别是当遇到困难时，程序通不过时，真的很令人沮丧。但是改正一个错 误时，那种喜悦心情也很令人期盼，这种心情堪比久旱见甘霖的喜悦。就是因 为有这种令人身心愉悦的可能，我才得以能够整晚不睡来改程序中的不足之 处。编程中有苦有乐，其中的苦乐只有亲身经历才能体会到。要想做出好的程 序，必须做好忍受其间痛苦的准备。7、参考文献。1 严蔚敏，吴伟民.数据结构，清华大学出版社，2001年1月2 刘怀亮.数据结构习题解析与实验指导，冶金工业出版社，2005 年2月3谭浩强.数据结构，清华大学出版社，1999年12月