迷宫及哈希表问题程序代码.docx
《迷宫及哈希表问题程序代码.docx》由会员分享，可在线阅读，更多相关《迷宫及哈希表问题程序代码.docx（17页珍藏版）》请在冰点文库上搜索。
迷宫及哈希表问题程序代码
迷宫及哈希表问题程序代码
#include
#defineM4
#defineQ4
#defineSTACK_INIT_SIZE30//存储空间初始量
#defineSTACK_INCREMENT10//存储空间初始增量
#include
#include
#include
#defineHASHSIZE10
typedefstruct
{introw;
intcol;
intdir;
}elemtype;
typedefstruct
{elemtype*base;
elemtype*top;
intstacksize;
}Sqstack;
intmaze[M+2][Q+2];
SqstackS;
intcount=0;
intInitStack（SqstackS）//初始化栈
{SqstackS;
S.base=（elemtype*）malloc（STACK_INIT_SIZE*sizeof（elemtype））;
if（!
S.base）
exit（0）;
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return1;
}//InitStack
intStackEmpty（SqstackS）
//判断栈是否为空,如果为空返回TRUE,否则返回FALSE
{
if（S.top==S.base）
return1;
return0;
}//StackEmpty
intPush（elemtypee）
//插入元素为e的栈顶元素
{
if（S.top-S.base>=S.stacksize）
{
S.base=（elemtype*）realloc（S.base,（S.stacksize+STACK_INCREMENT）*sizeof（elemtype））;
if（!
S.base）
exit（0）;
S.top=S.base+S.stacksize;
S.stacksize+=STACK_INCREMENT;
}
*S.top++=e;
return1;
}//Push
intPop（elemtypee）
//删除栈顶元素存入e
{
if（S.top==S.base）
return0;
e=*--S.top;
return1;
}//Pop
intDestroyStack（SqstackS）
//销毁栈
{
free（S.base）;
S.top=S.base;
return1;
}//DestroyStack
voidInit_maze（）/*迷宫的初始化*/
{inti,j;
for（i=0;ifor（j=0;jmaze[i][j]=1;
printf（"pleaseinputthe%d*%drecord（0or1）beginwith0,endwith0:
\n",M,Q）;
for（i=1;ifor（j=1;jscanf（"%d",&maze[i][j]）;
}
voiddisplay_maze（）/*迷宫的显示*/
{
inti,j;
printf（"\n\t\t\t----------themaze------------\n\t\t\t"）;
for（i=0;ifor（j=0;j{printf（"%3d",maze[i][j]）;
if（j==Q+1）printf（"\n\t\t\t"）;}
printf（"--------------end-------------\n"）;
}
intpath（）/*用矩阵输出路线*/
{
inti=1,j=1;
intn,m;
elemtypet;
SqstackS;
InitStack（S）;
t.row=1;t.col=1;t.dir=-1;maze[1][1]=-1;
Push（t）;
do{n=i,m=j;
if（maze[i][j+1]==0）
{t.row=i;t.col=j+1;t.dir=1;maze[i][j+1]=-1;
Push（t）;j++;count++;
}
elseif（maze[i+1][j]==0）
{t.row=i+1;t.col=j;t.dir=2;maze[i+1][j]=-1;
Push（t）;i++;count++;
}
elseif（maze[i][j-1]==0）
{t.row=i;t.col=j-1;t.dir=-1;maze[i][j-1]=-1;
Push（t）;j--;count++;
}
elseif（maze[i-1][j]==0）
{t.row=i-1;t.col=j;t.dir=-2;maze[i-1][j]=-1;
Push（t）;i--;count++;}
if（i==M&&j==Q）return1;
}while（i!
=n||j!
=m）;
return0;
}
voidprint（）/*用坐标输出路线*/
{inti;
printf（"thefoundwayis:
\n"）;
for（i=0;iprintf（"{[%d,%d]}",S.base[i].row,S.base[i].col）;
printf（"\n"）;
}
maze_main（）/*迷宫函数*/
{inti,w;
while
（1）
{
printf（"\n\t\t*****************迷宫****************\n"）;
printf（"\t\t\t1-输入迷宫\n"）;
printf（"\t\t\t2--显示迷宫\n"）;
printf（"\t\t\t3-寻找出路\n"）;
printf（"\t\t\t4-显示路径\n"）;
printf（"\t\t\t5-退出\n"）;
printf（"\t\t*****************迷宫****************\n\n\n"）;
printf（"pleasechoosethethenumber（1-5）:
"）;
scanf（"%d",&w）;
switch（w）
{
case1:
Init_maze（）;break;
case2:
display_maze（）;break;
case3:
i=path（）;
if（i==1）
printf（"找到出路\n"）;
else
printf（"没有找到出路\n"）;break;
case4:
print（）;break;
case5:
return0;
default:
printf（"请选择编号1-5:
\n"）;break;
}
}
}
typedefstructNode
{
intnumber;
charname[10];
charaddress[20];
structNode*next;
}Node,*Datatype;
DatatypeHash[HASHSIZE];
input（DatatypeHash[]）
{inti,j,key;
DatatypeL;
for（j=0;jHash[j]=NULL;
printf（"Pleaseinputthetelephonenumber（endwith0）:
"）;
scanf（"%d",&i）;getch（）;
while（i!
=0）{
key=i%HASHSIZE;
L=（Datatype）malloc（sizeof（Node））;
L->number=i;
printf（"\nPleaseinputthename:
"）;
scanf（"%s",&L->name）;
printf（"\nPleaseinputtheaddress:
"）;
scanf（"%s",&L->address）;
if（Hash[key]==NULL）
{Hash[key]=L;//直接将L放入Hash[key]中
L->next=NULL;
}
else
{L->next=Hash[key];//头插法
Hash[key]=L;
}
printf（"\nPleaseinputthetelephonenumber（endwith0）:
"）;
scanf（"%d",&i）;}
brow（Hash）;
display（）;
}
add（DatatypeHash[]）
{inti,key;
DatatypeL;
printf（"Pleaseinputthetelephonenumber:
"）;
scanf（"%d",&i）;getch（）;
key=i%HASHSIZE;
L=（Datatype）malloc（sizeof（Node））;
L->number=i;
if（Hash[key]==NULL）
{Hash[key]=L;
L->next=NULL;
}
else
{L->next=Hash[key];
Hash[key]=L;
}
printf（"\nPleaseinputthename:
"）;
scanf（"%s",&L->name）;
printf（"\nPleaseinputtheaddress:
"）;
scanf（"%s",&L->address）;
brow（Hash）;
display（）;
}
dele（DatatypeHash[]）
{inti,key;
DatatypeL,p,q;
printf（"\nPleaseinputthetelephonenumberyouwanttodelete:
"）;
scanf（"%d",&i）;
key=i%HASHSIZE;
p=Hash[key];
if（p->number==i）
Hash[key]=p->next;
else
while（p->next!
=NULL）
{if（p->next->number==i）
{q=p->next;
p->next=q->next;
free（q）;}
else
p=p->next;
}
brow（Hash）;
display（）;
}
modi（DatatypeHash[]）
{inti,j,k,key;
Datatypep,q;
printf（"\nPleaseinputthetelephonenumberyouwanttomodify:
"）;
scanf（"%d",&i）;
key=i%HASHSIZE;
p=Hash[key];
if（p->number==i）
{printf（"\n原来的电话号码:
%d,用户姓名:
%s,用户地址:
%s",p->number,p->name,p->address）;
if（p->next==NULL）
Hash[key]=NULL;
else
Hash[key]=p->next;
printf（"\nPleaseinputthetelephonenumbernow:
"）;
scanf（"%d",&k）;getch（）;
key=k%HASHSIZE;
p->number=k;
if（Hash[key]==NULL）
{Hash[key]=p;
p->next=NULL;
}
else
{p->next=Hash[key];
Hash[key]=p;
}
printf（"\nPleaseinputthename:
"）;
scanf（"%s",&p->name）;
printf（"\nPleaseinputtheaddress:
"）;
scanf（"%s",&p->address）;
}
else
{while（p->next!
=NULL）{
if（p->next->number==i）{
q=p->next;
printf（"\n原来的电话号码:
%d,用户姓名:
%s,用户地址:
%s",q->number,q->name,q->address）;
p->next=q->next;
//free（q）;
printf（"\nPleaseinputthetelephonenumbernow:
"）;
scanf（"%d",&k）;getch（）;
key=k%HASHSIZE;
//L=（Datatype）malloc（sizeof（Node））;
q->number=k;
printf（"\nPleaseinputthename:
"）;
scanf（"%s",&q->name）;
printf（"\nPleaseinputtheaddress:
"）;
scanf（"%s",&q->address）;
if（Hash[key]==NULL）
{Hash[key]=q;
q->next=NULL;
}
else
{q->next=Hash[key];
Hash[key]=q;
}
}
else
p=p->next;
}
}
brow（Hash）;
display（）;
}
voidseek（DatatypeHash[]）
{
inti,key,result;
charnext;
Datatypep;
begin:
result=0;
printf（"\nPleaseinputthetelephonenumberyouwanttoseekfor:
"）;
scanf（"%d",&i）;
key=i%HASHSIZE;
p=Hash[key];
while（p!
=NULL）
{if（p->number==i）
{printf（"\nFind:
\n"）;
printf（"电话号码：
%d用户姓名:
%s用户地址：
%s",p->number,p->name,p->address）;
result=1;/*找到此电话号码就将result的值从新赋为1*/
break;
}
else
p=p->next;
}
if（result==0）/*未从新赋值则输出没找到的信息*/
printf（"没找到！
"）;
printf（"\n是否继续？
（y/n）"）;
next=getche（）;/*将输入的y/n赋给next*/
putchar（'\n'）;/*换行*/
if（next=='y'||next=='Y'）gotobegin;/*next==y时回到begin处*/
else
main（）;
}
brow（DatatypeHash[]）
{
intkey;
Datatypep;
for（key=0;key{
p=Hash[key];
while（p!
=NULL）
{
printf（"\n电话号码：
%d用户姓名:
%s用户地址：
%s",p->number,p->name,p->address）;
p=p->next;
}
}
display（）;
}
Hash_main（）
{
display（）;
}
display（）
{inti;
printf（"\n-欢迎来到电话号码查询系统-\n"）;
printf（"--------------------------\n"）;
printf（"---1.用户信息的输入---\n"）;
printf（"---2.用户信息的添加---\n"）;
printf（"---3.用户信息的删除---\n"）;
printf（"---4.用户信息的修改---\n"）;
printf（"---5.用户信息的查询---\n"）;
printf（"---6.用户信息的输出---\n"）;
printf（"---0.退出职工信息管理系统---\n"）;
printf（"---------------------------\n"）;
printf（"请选择0-6:
"）;
scanf（"%d",&i）;/*输出主界面*/
switch（i）/*用switch语句调用函数*/
{
case1:
input（Hash）;break;
case2:
add（Hash）;break;
case3:
dele（Hash）;break;
case4:
modi（Hash）;break;
case5:
seek（Hash）;break;
case6:
brow（Hash）;break;
case0:
printf（"再见!
\n"）;exit（0）;
}
if（i<0||i>6）/*当输入的数不在case内输出错误信息*/
printf（"输入错误，请重输!
"）;
}
main（）
{inti,w;
while
（1）
{printf（"\n\t\t*****************问题****************\n"）;
printf（"\t\t\t1--迷宫问题\n"）;
printf（"\t\t\t2--哈希表问题\n"）;
printf（"\t\t\t3--退出\n"）;
printf（"\t\t********************************************\n\n\n"）;
printf（"请选择编号1-3）:
"）;
scanf（"%d",&w）;
switch（w）
{
case1:
maze_main（）;break;
case2:
Hash_main（）;break;
case3:
exit（0）;break;
default:
printf（"错误！
请选择1-3:
\n"）;break;
}
}
}
升级会员 