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

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的最小生成树问题。于是本次任务即为编程实

11、现最小生成树的构造。五、 软件设计（1） 程序框架输出连通网构造连通网主函数生成最小生成树输出最小生成树结束（2）子函数1）确定某个元素在图中的位置循环体，判断2）构造连通网定义结构体变量循环体输入顶点元素初始化邻接矩阵循环体输入边及权值3）打印连通网（邻接矩阵的存储结构）内嵌的循环体4）构造最小生成树初始化辅助数组将起始元素u加入数集U选择其余的n-1个点打擂台法确定最小值选择数集V-U中最小的权值打印所求的边（最小生成树的树枝）将新结点归入数集U更新数集V-U中的最小权值及其对应顶点（3）结构体1）顶点信息结构体（存储权值信息或是连接于非连接信息）2）图的数组存储结构体3) 最小生成树的辅

12、助数组结构体六、 编码实现源代码如下：#define INFINITY 999#define MAX_VERTEX_NUM 20#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

13、#define INFEASIBLE -1typedef int Status; typedef int Boolean; typedef 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 Ver

14、texType adjvex; VRType lowcost;closedgeMAX_VERTEX_NUM;int LocateVex(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) /初始化邻接矩阵

15、for(j=0;jvexnum;+j) G-arcsij.adj=INFINITY; G-arcsij.info=0; printf(开始输入边及权值，格式为 边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-arcsij.info) scanf(%d,G-arcsij.info); G-arcsji=G-arcsij; return OK;void

16、 PrintMGraph(MGraph *G) int i,j; printf(图的邻接矩阵表示为：n); for(i=0;ivexnum;+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; clos

17、edgej.lowcost=G.arcskj.adj; closedgek.lowcost=0; /将起始元素u加入数集U for(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.lowcos

18、t; n=m; / k=m; k=n; printf(%d,%d) ,closedgek.adjvex,G.vexsk); /打印所求的边（最小生成树的树枝） 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=&

19、GG; CreateUDN(G); PrintMGraph(G); printf(要开始生成图的最小生成树，请输入顶点信息：); scanf(%d,&u); printf(最小生成树为：n); MiniSpanTree_PRIM(*G,u); printf(n); getchar(); getchar();七、 软件测试(1) 编译环境为Microsoft Visual Studio 2010，运行最小生成树.exe,(2) 输入元素个数6，边数10(3) 输入元素：1 2 3 4 5 6 (4) 输入各边及权值数据，出现图的邻接矩阵表示，其中999代表顶点不相邻（5）输入顶点，开始生成最小生

20、成树（6）最小生成树为（1,6）（6,2）（1,5）（6,3）（1,4）结论：程序顺利完成了构造最小生成树的功能，得到了最后解决方案如右图所示：(三)心得体会：这四天的数据结构课程设计，我顺利完成了两个课题。应该说过程是辛苦的，但收获是丰盛的。我耐心写好课题规划，设计程序框图，我不担心准备的时间过长，因为我觉得准备充分了后面才做得顺利，才不需要返工。事实正是如此，我分析了任务定义，详细研究了哈希表和最小代价生成树的思路和算法，然后画出大致的程序框图，理清思路，边写代码边参考我拟定的程序框图，这样代码写下来就更加清晰。但是书本给的算法并不是完整的代码语言，我在将算法思想转化为代码语言时也遇到过诸如指针引用不当，类型不匹配等令人恼怒的问题。在不断调试的过程中，我还自己摸索了VC2010编译器强大的调试功能，像设置断点，查看局部变量等功能。借助编译器，我一步一步调试，缩小错误范围，找到并修正错误，最后完成了程序调试，出结果的那一瞬间，我激动万分。的确，自己亲手做课程设计是挺辛苦，但我知道，过程越是坎坷曲折，收获的知识与能力越是刻骨铭心。18