数据结构课程设计-哈希表-最小代价生成树.docx
《数据结构课程设计-哈希表-最小代价生成树.docx》由会员分享,可在线阅读,更多相关《数据结构课程设计-哈希表-最小代价生成树.docx(18页珍藏版)》请在沃文网上搜索。
1、数据结构课程设计报告学院: 班级: 姓名: 学号:设计题目: (1)哈希表查找的设计(2)连通网的最小代价生成树设计时间:2014年1月2日至1月7日(一)课题三 哈希表查找的设计一、 问题分析和任务定义设哈希表长为20,用除留余数法构造一个哈希函数,以开放定址法中的线性探测再散列法作为解决冲突的方法,编程实现哈希表查找、插入和建立算法。二、 软件设计(1) 程序框图开始构造哈希表输入数据元素求得哈希地址装入哈希表查找元素插入元素结束(2) 子函数1) 初始化哈希表动态分配存储空间2) 求得哈希地址除留余数法3) 冲突处理线性探测再散列法4) 输入元素输入元素个数循环体输入元素考虑冲突处理依次
2、存入哈希地址5)打印哈希表6)查找元素直接去哈希地址比较查找考虑冲突处理7)插入元素查找元素考虑冲突次数是否过多插入哈希表(3) 结构体1) 哈希表结构体装有数据元素的地址;现有数据个数;哈希表长三、 编码实现源代码如下:#include#include #define Status int #define ElemType int#define KeyType int#define NULLKEY 0#define EQ(x,y) x=y#define SUCCESS 1#define UNSUCCESS 0#define DUPLICATE -1#define OK 1#define MA
3、XHSIZE 20#define OVERFLOW -2#define NULL 0int hashsize=20;typedef struct ElemType *elem; int count; int sizeindex;HashTable;Status InitHashTable(HashTable *H) H-elem=(int *)malloc(hashsize0*sizeof(ElemType); if(!H-elem)exit(OVERFLOW); H-count=0; H-sizeindex=hashsize0; for(int i=0;ielemi=0; return OK
4、;Status Hash(ElemType e) /求得哈希地址 ElemType i; i=e%MAXHSIZE; return i-1;Status collision(ElemType *p,const ElemType *c) / (*p)+=*c; *p=(*p)+(*c); if(*pMAXHSIZE) exit(OVERFLOW); else return SUCCESS;Status InputData(HashTable *H,int *p,int *c) int i,n,t1,t2,t3; int *pa; printf(请输入元素个数:); /n=getchar(); s
5、canf(%d,&n); pa=(int *)malloc(n*sizeof(int); printf(开始输入数据:n); for(i=0;ielem*p!=NULLKEY); / t2=!(EQ(*(pa+i),H-elem*p); / printf(%d,*(pa+i); while(H-elem*p!=NULLKEY)&!(EQ(*(pa+i),H-elem*p) t3=+(*c); collision(p,c); H-elem*p=*(pa+i); H-count+; return 0;Status PrintHash(HashTable *H) int i; printf(当前哈希
6、表如下:n); for(i=0;i1;+i) printf(%5d,H-elemi); putchar(n); for(;ielemi); putchar(n); printf(按任意键继续n); getchar(); getchar(); /Menu(); return 0;Status SearchHash(HashTable H,KeyType K,int *p,int *c) int t; *p=Hash(K); while (H.elem*p!=NULLKEY&!(EQ(K,H.elem*p) t=+(*c); collision(p,&t); if (EQ(K,H.elem*p)
7、return SUCCESS; else return UNSUCCESS;Status InsertHash(HashTable *H,ElemType e) int c=0; int p; p=Hash(e); / printf(%d,e); if(SearchHash(*H,e,&p,&c) return DUPLICATE; else if(csizeindex/2) H-elemp=e; +H-count; return OK; else return UNSUCCESS; Status RecreateHashTable(HashTable *H) printf(你需要重新构造哈希
8、表n); return 0;void main() HashTable HH; int pp=0,cc=0; int t=0,key=0,*p=&pp,*c=&cc; HashTable *H=&HH; InitHashTable(H); /初始化哈希表,分配内存 InputData(H,p,c); /构造哈希表,输入元素数据 PrintHash(H); /打印哈希表 printf(请输入查找元素:); /开始查找 scanf(%d,&key); t=SearchHash(*H,key,p,c); if(t) printf(查找成功!n); PrintHash(H); else printf(
9、哈希表中无此元素n); printf(请输入要插入的元素:); /开始插入 scanf(%d,&key); t=InsertHash(H,key); if(t) printf(插入成功!n); PrintHash(H); else RecreateHashTable(H); 四、 软件测试(1) 编译环境为Microsoft Visual Studio 2010,运行哈希表.exe,(2) 输入元素个数10(3) 输入数据3,5,8,43, 54, 21, 8, 10, 9, 17,得到哈希表(4) 输入查找元素5,提示查找成功,说明此哈希表含有元素5(5)若输入查找元素23,则提示哈希表中无
10、此元素(5) 插入元素23,提示插入成功,并显示当前哈希表(6)结论:程序顺利完成了使用除留余数法构建哈希表,使用线性探测再散列处理冲突,查找元素和插入元素的功能,达到了预期目的。(二)课题四 连通网的最小代价生成树一、问题分析和任务定义如下图要在 n 个城市之间建立通讯联络网,则连通 n 个城市只需要修建 n-1条线路,编程实现在最节省经费的前提下建立这个通讯网。图2图1562341将图1等效为图2进行分析。如图2 ,这是一个含有6个顶点10条边的连通网,圆圈内的数字为顶点信息,边上的数字为权值。由题意,要求图1的通讯联络网最节省经费方案即转化求为图2的最小生成树问题。于是本次任务即为编程实
- 1.请仔细阅读文档,确保文档完整性,对于不预览、不比对内容而直接下载带来的问题本站不予受理。
- 2.下载的文档,不会出现我们的网址水印。
- 3、该文档所得收入(下载+内容+预览)归上传者、原创作者;如果您是本文档原作者,请点此认领!既往收益都归您。
下载文档到电脑,查找使用更方便
20 积分
下载 | 加入VIP,下载更划算! |
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 课程设计 哈希表 最小 代价 生成