问题描述：
设计一个实现顺序查找、二分查找（折半查找）、二叉排序树、哈希查找算法的程序，并具有人机交互界面。
基本要求：
（1）设计一个菜单将实现的查找算法的名字显示出来，并提示用户对查找算法进行选择；
（2）分别实现顺序查找、二分查找（折半查找）、二叉排序树、哈希查找；
（3）哈希函数采用除留余数发，解决冲突的方法大家任选择一种；
（4）二叉排序树必须实现构建、查找、插入、删除四个基本 *** 作；
（5）输出各种排序的结果并进行比较。*/
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#define MAX 20
typedef struct/*顺序结构数据类型*/
{
int key
}RecordType
typedef struct
{
RecordType r[MAX+1]
int length
}RecordList
typedef struct
{
RecordType HashTable[MAX]
}RecordHash
typedef struct node /*二叉排序树的结点结构*/
{
int key
struct node *lchild,*rchild
}BSTNode,*BSTree
void page_title(char *menu_item) /*返回界面函数*/
{
clrscr()
printf("查找算法 \n\n\n\n\n%s\n\n",menu_item)
}
void return_confirm()
{
printf("按任意键返回\n")
getch() /*从键盘终端接受一个字符*/
}
RecordList creat1()/*建立线性表*/
{
RecordList h
int i,n=1
h.length=0
printf("请输入第1个数:")
scanf("%d",&i)
while(i!=0)
{
h.length++
h.r[h.length].key=i
printf("请输入第%d个数:",++n)
scanf("%d",&i)
}
return h
}
void InsertBST(BSTree &p,int k)
{
BSTNode *s
if(p==NULL)
{
s=(BSTNode*)malloc(sizeof(BSTNode))
s->key=k
s->lchild=NULL
s->rchild=NULL
p=s
}
else if(k<p->key)
InsertBST(p->lchild,k)
else if(k>p->key)
InsertBST(p->rchild,k)
}
BSTNode *creat2() /*创建二叉排序树*/
{
BSTNode *h
int k,i=1
h=NULL
printf("请输入第1个关键字:")
scanf("%d",&k)
while(k!=0)
{
InsertBST(h,k)
printf("请输入第%d个关键字:",++i)
scanf("%d",&k)
}
return h
}
void SeqSearch(RecordList l) /*顺序查找*/
{
int i
int k
page_title("顺序查找")
printf("请输入要查找的关键字:")
scanf("%d",&k)
l.r[0].key=k
i=l.length
while(l.r[i].key!=k) i--
if(i==0) printf("查找失败\n")
else
{
printf("l.r[%d].key=%d\n",i,k)
printf("查找成功\n")
}
return_confirm()
}
void Binsrch(RecordList l) /*二分查找*/
{
int k,j,i=0
int low=1,high=l.length,mid
page_title("二分查找")
printf("请输入要查找的关键字:")
scanf("%d",&k)
while(low<=high)
{
mid=(low+high)/2
if(l.r[mid].key==k)
{
i=mid
break
}
else
if(k<l.r[mid].key) high=mid-1
else low=mid +1
}
if(i!=0)
{
printf("l.r[%d].key=%d\n",i,k)
printf("查找成功\n")
}
else printf("查找失败\n")
return_confirm()
}
void SearchBST(BSTNode *h,int k) /*二叉排序树的查找*/
{
if(!h)
{
printf("查找失败\n")
return_confirm()
}
else if(h->key==k)
{
printf("查找成功\n")
return_confirm()
}
else if(h->key>k)
SearchBST(h->lchild,k)
else
SearchBST(h->rchild,k)
}
RecordHash creat3() /*创建哈希表*/
{
RecordHash ht
int i,j=1,k
for(i=0i<MAXi++)
ht.HashTable[i].key=0
printf("请输入第1个关键字:")
scanf("%d",&k)
while(k!=0&&j<MAX)
{
i=k%13
while(ht.HashTable[i].key!=0) i++
ht.HashTable[i].key=k
printf("请输入第%d个关键字:",++j)
scanf("%d",&k)
}
return ht
}
void HashSearch(RecordHash ht) /*哈希查找*/
{
int k,i
page_title("哈希查找")
printf("请输入要查找的关键字:")
scanf("%d",&k)
i=k%13
if(ht.HashTable[i].key==k)
{
printf("ht.HashTable[%d].key=%d\n",i,k)
printf("查找成功\n")
}
else
{
i=i+1
for(i<MAXi++)
if(ht.HashTable[i].key==k)
{
printf("ht.HashTable[%d].key=%d\n",i,k)
printf("查找成功\n")
break
}
if(i==MAX) printf("查找失败\n")
}
return_confirm()
}
void main()
{
RecordList L1,L2
BSTNode *pt
RecordHash ht
int k,i
printf("\n创建顺序查找线性表,输入0则结束输入(可不按顺序输入)\n")
L1=creat1()
printf("\n创建二分查找线性表，输入0则结束输入(按递增顺序输入)\n")
L2=creat1()
printf("\n创建二叉排序树，输入0则结束输入\n")
pt=creat2()
printf("\n创建哈希表\n")
ht=creat3()
menu:page_title("请选择查找方式，输入0则结束输入")
printf("顺序查找请按1\n二分查找请按2\n二叉排序树查找请按3\n哈希查找请按4\n推出请按0\n")
switch(getch())
{
case '1':
SeqSearch(L1)
break
case '2':
Binsrch(L2)
break
case '3':
page_title("二叉排序树查找")
printf("请输入要查找的关键字:")
scanf("%d",&k)
SearchBST(pt,k)
break
case '4':
HashSearch(ht)
break
case '0':
exit(0)
default :
printf("输入错误，按任意键返回")
getch()
}
goto menu
}
1。建立无向图，应该是棋盘格数的方阵，比如64×64（国际象棋）或者90×90，初始化为全零.根据马的走法，对可以直达春册银的两格建立一条边，就是对应位置为1。2。然后指定一个出发点（当然也可以是从所有点姿迅出发一一去试），沿着这些边到达下一格，并记录已达到的格中。
3.如果不重复完成，则成功。如果无法继续走到未到达的格，只能到已到达的格子，则失败。
4.这个扒宴走棋的过程需要一种策略来遍历各种情况。比如我们可以规定如果有最多八种可能，则马先测试走那种，这个编写成递归就非常方便。
java马踏棋盘设计目的是解决实际的应用问题锋改，特别是非数值计算类型的应用问题。马踏棋盘的基本过程：国际象棋的棋盘为8*8的方格棋盘薯返。现将"马"放在任意指定的方格中，按照"马"走棋的规则将"马"进行移动。要求每个方格只能进入一次，最终使得"马"走遍棋盘的64个方格。
马踏棋盘的解决方案:基于深度优先搜索的方法是比较常用的算法，深度优先搜索算法也是数据结构中的经典算法之银手判一，主要是采用递归的思想，一级一级的寻找，最后找到合适的解。
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）