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

1、数据结构课程设计报告学院： 班级： 姓名： 学号：设计题目：（1）哈希表查找的设计（2）连通网的最小代价生成树设计时间：2014年1月2日至1月7日(一)课题三 哈希表查找的设计问题分析和任务定义设哈希表长为20，用除留余数法构造一个哈希函数，以开放定址法中的线性探测再散列法作为解决冲突的方法，编程实现哈希表查找、插入和建立算法。软件设计程序框图开始构造哈希表输入数据元素求得哈希地址装入哈希表查找元素插入元素结束子函数初始化哈希表动态分配存储空间求得哈希地址除留余数法3) 冲突处理线性探测再散列法4) 输入元素输入元素个数循环体输入元素考虑冲突处理依次存入哈希地址5）打印哈希表6）查找元素直接

2、去哈希地址比较查找考虑冲突处理7）插入元素查找元素考虑冲突次数是否过多插入哈希表结构体哈希表结构体装有数据元素的地址；现有数据个数；哈希表长编码实现源代码如下：#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 MAXHSIZE 20#define OVERFLOW -2#de

3、fine 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;Status Hash(ElemType e) /求得哈希地

4、址 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(); scanf(%d,&n); pa=(int *)malloc(n

5、*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(当前哈希表如下:n); for(i=0;i1;+i) printf(%

6、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) return SUCCESS; else return UNS

7、UCCESS;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(你需要重新构造哈希表n); return 0;void main() HashT

8、able 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(哈希表中无此元素n); printf(请输入要插入的元素：);

9、 /开始插入 scanf(%d,&key); t=InsertHash(H,key); if(t) printf(插入成功!n); PrintHash(H); else RecreateHashTable(H); 软件测试编译环境为Microsoft Visual Studio 2010，运行哈希表.exe,输入元素个数10输入数据3，5，8，43， 54， 21， 8， 10, 9, 17，得到哈希表输入查找元素5，提示查找成功，说明此哈希表含有元素5（5）若输入查找元素23，则提示哈希表中无此元素插入元素23,提示插入成功，并显示当前哈希表（6）结论：程序顺利完成了使用除留余数法构建哈希表

10、，使用线性探测再散列处理冲突，查找元素和插入元素的功能，达到了预期目的。(二)课题四 连通网的最小代价生成树一、问题分析和任务定义如下图要在 n 个城市之间建立通讯联络网，则连通 n 个城市只需要修建 n-1条线路，编程实现在最节省经费的前提下建立这个通讯网。图2图1562341将图1等效为图2进行分析。如图2 ，这是一个含有6个顶点10条边的连通网，圆圈内的数字为顶点信息，边上的数字为权值。由题意，要求图1的通讯联络网最节省经费方案即转化求为图2的最小生成树问题。于是本次任务即为编程实现最小生成树的构造。软件设计程序框架输出连通网构造连通网主函数生成最小生成树输出最小生成树结束（2）子函数1

11、）确定某个元素在图中的位置循环体，判断2）构造连通网定义结构体变量循环体输入顶点元素初始化邻接矩阵循环体输入边及权值3）打印连通网（邻接矩阵的存储结构）内嵌的循环体4）构造最小生成树初始化辅助数组将起始元素u加入数集U选择其余的n-1个点打擂台法确定最小值选择数集V-U中最小的权值打印所求的边（最小生成树的树枝）将新结点归入数集U更新数集V-U中的最小权值及其对应顶点（3）结构体1）顶点信息结构体（存储权值信息或是连接于非连接信息）2）图的数组存储结构体3) 最小生成树的辅助数组结构体编码实现源代码如下：#define INFINITY 999#define MAX_VERTEX_NUM 20

12、#define VertexType int #define VRType int #define NULL 0#define InfoType int typedef int GraphKind10;#include#include#include #include #include #include #include #include #include #define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1typedef int Status; typedef int Boolean; ty

13、pedef struct ArcCell VRType adj; /顶点类型，可以是权值信息或是连接于非连接信息 InfoType *info;ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct VertexType vexsMAX_VERTEX_NUM; AdjMatrix arcs; int vexnum; int arcnum; GraphKind kind;MGraph;struct VertexType adjvex; VRType lowcost;closedgeMAX_VERTEX_NUM;int Locate

14、Vex(MGraph G,VertexType u) /* 初始条件: 图G存在,u和G中顶点有相同特征 操作结果: 若G中存在顶点u,则返回该顶点在图中位置;否则返回-1 */ int i; for(i=0;ivexnum=t1; G-arcnum=t2; printf(开始输入元素：n); /对结构体变量输入元素 for(i=0;ivexnum;+i) scanf(%d,&t3); G-vexsi=t3; for(i=0;ivexnum;+i) /初始化邻接矩阵 for(j=0;jvexnum;+j) G-arcsij.adj=INFINITY; G-=0; prin

15、tf(开始输入边及权值，格式为 边n：顶点1 顶点2 权值n); for(k=0;karcnum;+k) /输入边及权值 printf(边%d:,k+1); scanf(%d%d%d,&v1,&v2,&w); i=LocateVex(*G,v1);j=LocateVex(*G,v2); G-arcsij.adj=w; if(G-) scanf(%d,G-); G-arcsji=G-arcsij; return OK;void PrintMGraph(MGraph *G) int i,j; printf(图的邻接矩阵表示为：n); for(i=0;iv

16、exnum;+i) for(j=0;jvexnum;+j) printf(%-5d,G-arcsij.adj); printf(n); void MiniSpanTree_PRIM(MGraph G,VertexType u) int i,j,k,m=0,n=0,t=0; k=LocateVex(G,u); /确定起始元素u在矩阵图中的位置 for(j=0;jG.vexnum;+j) /初始化辅助数组 if(j!=k) closedgej.adjvex=u; closedgej.lowcost=G.arcskj.adj; closedgek.lowcost=0; /将起始元素u加入数集U fo

17、r(i=1;iG.vexnum;+i) /选择其余的n-1个点 m=0; /k=minimum(closedge); while(!closedgem.lowcost) m+; t=closedgem.lowcost; /打擂台法确定最小值，但是要保证t的初值不为零 for(m=0;mG.vexnum;+m) /选择数集V-U中最小的权值 if(closedgem.lowcost!=0)&(closedgem.lowcost=t) t=closedgem.lowcost; n=m; / k=m; k=n; printf(%d,%d) ,closedgek.adjvex,G.vexsk); /打

18、印所求的边（最小生成树的树枝） closedgek.lowcost=0; /将新结点归入数集U for(j=0;jG.vexnum;+j) /更新数集V-U中的最小权值及其对应顶点 if(G.arcskj.adjclosedgej.lowcost) closedgej.adjvex=G.vexsk; /顶点信息 closedgej.lowcost=G.arcskj.adj; /权值信息 void main() int u; MGraph GG; MGraph *G=≫ CreateUDN(G); PrintMGraph(G); printf(要开始生成图的最小生成树，请输入顶点信息：); scanf(%d,&u); printf(最小生成树为：n); MiniSpanTree_PRIM(*G,u); printf(n); getchar(); g