c语言课程设计作业迷宫问题求解哈希表查找的设计.docx
- 文档编号:9687904
- 上传时间:2023-05-20
- 格式:DOCX
- 页数:16
- 大小:195.04KB
c语言课程设计作业迷宫问题求解哈希表查找的设计.docx
《c语言课程设计作业迷宫问题求解哈希表查找的设计.docx》由会员分享,可在线阅读,更多相关《c语言课程设计作业迷宫问题求解哈希表查找的设计.docx(16页珍藏版)》请在冰点文库上搜索。
c语言课程设计作业迷宫问题求解哈希表查找的设计
一
设计题目
迷宫问题求解
任务
迷宫问题是取自心理学的一个古典实验。
实验中,把一只老鼠从一个没有顶的大盒子的门放入,在盒中设置了许多墙,对行进的方向形成了多处阻挡。
盒子仅仅有一个出口,在出口处放置了一块奶酪,吸引老鼠在迷宫中寻找道路以到达出口。
重复对老鼠进行上述实验,看老鼠能在多久找到出口。
功能要求
输入迷宫布局
输出走出迷宫的路径图
需求分析
用以下测试数据,0表示可以行走的区域,1表示不可行走的区域。
入口
1
0
0
0
1
0
1
1
0
1
0
1
1
0
1
1
0
1
1
0
0
1
0
1
1
1
1
0
出口
概要设计
structpoint
{
introw;
intcol;
intpredecessor;
}queue[512];
voidmap_maze(intm,intn)
voidresult_maze(intm,intn)
voidenqueue(structpointp)
structpointdequeue()
intempty()
voidvisit(introw,intcol,intmaze[20][20])
intpath(intmaze[20][20],intm,intn)
程序调用关系如下:
主程序模块
寻找路径模块
输出迷宫及路径模块
输入迷宫模块
详细设计
#include
#include
intX=1;
intmaze[20][20];
inthead=0,tail=0;
structpoint
{
introw;
intcol;
intpredecessor;
}queue[512];
voidmap_maze(intm,intn)
{
inti,j;
printf("输入迷宫(0为路1为墙):
\n");
for(i=0;i for(j=0;j scanf("%d",&maze[i][j]); printf("\n##############################################################################\n\n"); printf("生成迷宫: \n\n"); printf("入口\n"); printf("↓"); for(i=0;i { printf("\n"); for(j=0;j { if(maze[i][j]==0) printf("0"); if(maze[i][j]==1) printf("1"); } } printf("→出口\n"); } voidresult_maze(intm,intn) { inti,j; printf("迷宫通路为(用*表示): \n\n"); printf("入口\n"); printf("↓"); for(i=0;i { printf("\n"); for(j=0;j { if(maze[i][j]==0||maze[i][j]==2)printf("0"); if(maze[i][j]==1)printf("1"); if(maze[i][j]==3)printf("*"); } } printf("→出口\n"); } voidenqueue(structpointp) { queue[tail]=p; tail++; } structpointdequeue() { head++; returnqueue[head-1]; } intempty() { returnhead==tail; } voidvisit(introw,intcol,intmaze[20][20]) { structpointvisit_point={row,col,head-1}; maze[row][col]=2; enqueue(visit_point); } intpath(intmaze[20][20],intm,intn) { structpointp={0,0,-1}; if(maze[0][0]==1) { printf("\n##############################################################################\n\n"); printf("迷宫无解\n\n"); X=0; return0; } maze[0][0]=2; enqueue(p); while(! empty()) { p=dequeue(); if((p.row==m-1)&&(p.col==n-1)) break; if((p.row+1 visit(p.row+1,p.col,maze); if((p.col+1 visit(p.row,p.col+1,maze); if((p.row-1>=0)&&(maze[p.row-1][p.col]==0)) visit(p.row-1,p.col,maze); if((p.col-1>=0)&&(maze[p.row][p.col-1]==0)) visit(p.row,p.col-1,maze); } if(p.row==m-1&&p.col==n-1) { printf("\n##############################################################################\n\n"); maze[p.row][p.col]=3; while(p.predecessor! =-1) { p=queue[p.predecessor]; maze[p.row][p.col]=3; } } else{printf("\n##############################################################################\n"); printf("迷宫无解\n\n"); X=0; return0; } return0; } voidmain() { intm,n; printf("***************************数据结构课程设计*************************************\n"); printf("******课题三迷宫问题求解******\n"); printf("********************************************************************************\n"); printf("迷宫行数(1-20): \n"); scanf("%d",&m); printf("迷宫列数(1-20): \n"); scanf("%d",&n); while((m<=0||m>=21)||(n<=0||n>=21)) { printf("\n输入的行列数超出预设范围(1-20,1-20),重新输入: \n\n"); printf("行数: "); scanf("%d",&m); printf("\n"); printf("列数: "); scanf("%d",&n); } map_maze(m,n); path(maze,m,n); if(X! =0)result_maze(m,n); } 调试分析 1、加入了输入数字位数超过有效位数时提示错误并可重新输入。 2、开始时多定义了变量,调试时发现无用,于是去掉。 用户手册 1、演示程序的运行环境为WindowsVista系统,MicrosoftVisualStudio6.0中的MicrosoftVisualC++6.0中运行。 执行文件为: 迷宫问题求解.exe 2、进入演示程序后即显示DOS形式的界面: 3、输入迷宫布局。 系统会自动给出路径。 测试结果 二 设计题目 哈希表查找的设计 任务 设哈希表长为20,用除留余数法构造一个哈希函数,以开放定址法中的线性探测再散列法作为解决冲突的方法,编程实现哈希表查找、插入和建立算法。 功能要求 输入关键字个数和关键字组和不大于关键字个数的除数 输出哈希表地址和对应的关键字 需求分析 关键字组为{19,01,23,14,55,20,84,27,68,11,10,77},哈希函数为H(key)=key%13 概要设计 typedefstruct { intkeyword; }hashtable; intSearchHashTable(hashtableht[],intkeyword,intp,intnumber) intInsertHashTable(hashtableht[],intkeyword,intp,intnumber) voidCreateHashTable(hashtableht[]) 主程序模块 程序调用关系如下: 输出模块 创建哈希表模块 插入哈希表模块 查找哈希表模块 详细设计 #include typedefstruct { intkeyword; }hashtable; intSearchHashTable(hashtableht[],intkeyword,intp,intnumber) { intaddress=0,i=0; address=keyword%p;//求哈希地址 while((keyword! =ht[address].keyword)&&(ht[address].keyword! =NULL)) { address=(address+1)%20;//线性探测再散列法 } returnaddress; } intInsertHashTable(hashtableht[],intkeyword,intp,intnumber) { intresult=0;//结果 result=SearchHashTable(ht,keyword,p,number); if(ht[result].keyword==0) { ht[result].keyword=keyword; printf("插入成功\n"); return1; } else { printf("插入失败(已有该关键字)\n"); return0; } } voidCreateHashTable(hashtableht[]) { intnumber=0,keyword=0,p; printf("输入哈希表中关键字的个数(不要超过20): \n"); scanf("%d",&number); while(number>20||number<=0) { printf("输入哈希表中关键字的个数大于20,重新输入: \n"); scanf("%d",&number); } printf("输入哈希函数除留余数法中的除数: \n"); scanf("%d",&p); for(inti=0;i { printf("输入哈系表的关键字: \n"); scanf("%d",&keyword); InsertHashTable(ht,keyword,p,number); } } intmain() { hashtableht[20]; intkeyword=0; printf("***************************数据结构课程设计*************************************\n"); printf("******课题四哈希表查找的设计******\n"); printf("********************************************************************************\n"); for(inti=0;i<20;i++) { ht[i].keyword=NULL; } CreateHashTable(ht); printf("输出哈希表: \n"); printf("哈希表地址关键字\n"); for(intj=0;j<20;j++) { if(ht[j].keyword! =NULL) printf("%6d%9d\n",j,ht[j].keyword); elsecontinue; } return0; } 调试分析 1、输入哈希表中关键字的个数大于20时仍然运行,加入了大于20重新输入的语句。 用户手册 1、演示程序的运行环境为WindowsVista系统,MicrosoftVisualStudio6.0中的MicrosoftVisualC++6.0中运行。 执行文件为: 哈希表查找的设计.exe 2、进入演示程序后即显示DOS形式的界面: 3、输入关键字个数和关键字和除数,系统输出哈希表地址和对应的关键字 测试结果
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 语言 课程设计 作业 迷宫 问题 求解 哈希表 查找 设计