数据结构课程设计_哈希表_最小代价生成树.docx

1 数据结构课程设计报告学院: 班级: 姓名: 学号: 设计题目:(1 )哈希表查找的设计( 2 )连通网的最小代价生成树设计时间: 2014 年1月2日至1月7日2 (一) 课题三哈希表查找的设计一、问题分析和任务定义设哈希表长为 20 ,用除留余数法构造一个哈希函数,以开放定址法中的线性探测再散列法作为解决冲突的方法,编程实现哈希表查找、插入和建立算法。二、软件设计(1) 程序框图开始→构造哈希表→输入数据元素→求得哈希地址→装入哈希表→查找元素→插入元素→结束(2) 子函数 1) 初始化哈希表动态分配存储空间 2) 求得哈希地址除留余数法 3) 冲突处理线性探测再散列法 4) 输入元素输入元素个数→循环体输入元素→考虑冲突处理→依次存入哈希地址 5 )打印哈希表 6 )查找元素直接去哈希地址比较查找→考虑冲突处理 7 )插入元素查找元素→考虑冲突次数是否过多→插入哈希表(3) 结构体 1) 哈希表结构体装有数据元素的地址;现有数据个数;哈希表长三、编码实现源代码如下: #include<> 3 #include<> #define Status int #define ElemType int #define KeyType int #define NULLKEY 0 #define EQ(x,y) x==y #define ESS 1 #define ESS 0 #define DUPLICATE -1 #define OK 1 #define MAXHSIZE 20 #define OVERFLOW -2 #define NULL 0 int hashsize []={ 20 }; typedef struct { ElemType * elem ; int count ; int sizeindex ; } HashTable ; Status InitHashTable ( HashTable *H) {H -> elem =( int *) malloc ( hashsize [0 ]* sizeof ( ElemType )); if (! H -> elem ) exit ( OVERFLOW ); H -> count =0;H -> sizeindex = hashsize [0 ]; for ( int i=0;i< hashsize [0 ];++ i) H -> elem [i ]= 0; return OK ;} Status Hash ( ElemType e) // 求得哈希地址{ ElemType i;i=e% MAXHSIZE ; return i-1; } 4 Status collision ( ElemType *p, const ElemType *c) { // (*p)+=*c; *p =(* p )+(* c ); if (* p> MAXHSIZE ) exit ( OVERFLOW ); else return ESS ; } Status InputData ( HashTable *H, int *p, int *c) { int i,n, t1 , t2 , t3 ; int * pa ; printf (" 请输入元素个数: " ); //n=getchar(); scanf ( "%d" ,& n ); pa =( int *) malloc (n* sizeof ( int )); printf (" 开始输入数据:\n" ); for (i=0;i<n ;++ i) { // scanf("%d",&t); scanf ( "%d" ,( pa +i )); // printf("%d",*(pa+i)); *p= Hash (*( pa +i )); // printf("%d",*(pa+i)); // t1=(H->elem[*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 (" 当前哈希表如下:\n" );5 for (i=0;i< MAXHSIZE >> 1 ;++ i) { printf