程序设计《任选一题》

/*查找算法
问题描述：
设计一个实现顺序查找、二分查找（折半查找）、二叉排序树、哈希查找算法的程序，并具有人机交互界面。
基本要求：
（1）设计一个菜单将实现的查找算法的名字显示出来，并提示用户对查找算法进行选择；
（2）分别实现顺序查找、二分查找（折半查找）、二叉排序树、哈希查找；
（3）哈希函数采用除留余数发，解决冲突的方法大家任选择一种；
（4）二叉排序树必须实现构建、查找、插入、删除四个基本操作；
（5）输出各种排序的结果并进行比较。*/

#include
#include
#include
#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(kkey)
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 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=0;i ht.HashTable[i].key=0;
printf("请输入第1个关键字:");
scanf("%d",&k);
while(k!=0&&j {
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 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;
}

【问题描述】
马的遍历问题。在8×8方格的棋盘上，从任意指定方格出发，为马寻找一条走遍棋盘每一格并且只经过一次的一条路径。
【初步设计】
首先这是一个搜索问题，运用深度优先搜索进行求解。算法如下：
1、 输入初始位置坐标x,y；
2、 步骤 c:
如果c>64输出一个解，返回上一步骤c--
(x,y) ← c
计算(x,y)的八个方位的子结点，选出那此可行的子结点
循环遍历所有可行子结点，步骤c++重复2
显然（2）是一个递归调用的过程，大致如下：
void dfs(int x,int y,int count)
{
int i,tx,ty;
if(count>N*N)
{
output_solution();//输入一个解
return;
}
for(I=0;i<8;++i)
{
tx=hn[i].x;//hn[]保存八个方位子结点
ty=hn[i].y;
s[tx][ty]=count;
dfs(tx,ty,count+1);//递归调用
s[tx][ty]=0;
}
}
这样做是完全可行的，它输入的是全部解，但是马遍历当8×8时解是非常之多的，用天文数字形容也不为过，这样一来求解的过程就非常慢，并且出一个解也非常慢。
怎么才能快速地得到部分解呢？
【贪心算法】
其实马踏棋盘的问题很早就有人提出，且早在1823年，J.C.Warnsdorff就提出了一个有名的算法。在每个结点对其子结点进行选取时，优先选择‘出口’最小的进行搜索，‘出口’的意思是在这些子结点中它们的可行子结点的个数，也就是‘孙子’结点越少的越优先跳，为什么要这样选取，这是一种局部调整最优的做法，如果优先选择出口多的子结点，那出口少的子结点就会越来越多，很可能出现‘死’结点（顾名思义就是没有出口又没有跳过的结点），这样对下面的搜索纯粹是徒劳，这样会浪费很多无用的时间，反过来如果每次都优先选择出口少的结点跳，那出口少的结点就会越来越少，这样跳成功的机会就更大一些。这种算法称为为贪心算法，也叫贪婪算法或启发示算法，它对整个求解过程的局部做最优调整，它只适用于求较优解或者部分解，而不能求最优解。这样的调整方法叫贪心策略，至于什么问题需要什么样的贪心策略是不确定的，具体问题具体分析。实验可以证明马遍历问题在运用到了上面的贪心策略之后求解速率有非常明显的提高，如果只要求出一个解甚至不用回溯就可以完成，因为在这个算法提出的时候世界上还没有计算机，这种方法完全可以用手工求出解来，其效率可想而知。
在前面的算法基础之上，增添一些程序加以实现：
函数1：计算结点出口多少
int ways_out(int x,int y)
{
int i,count=0,tx,ty;
if(x<0||y<0||x>=N||y>=N||s[x][y]>0)
return -1;//-1表示该结点非法或者已经跳过了
for(i=0;i<8;++i)
{
tx=x+dx[i];
ty=y+dy[i];
if(tx<0||ty<0||tx>=N||ty>=N)
continue;
if(s[tx][ty]==0)
++count;
}
return count;
}
函数2：按结点出口进行排序
void sortnode(h_node *hn,int n)//采用简单排序法，因为子结点数最多只有8
{
int i,j,t;
h_node temp;
for(i=0;i {
for(t=i,j=i+1;j if(hn[j].waysout t=j;
if(t>i)
{
temp=hn[i];
hn[i]=hn[t];
hn[t]=temp;
}
}
}
函数3：修改后的搜索函数
void dfs(int x,int y,int count)
{
int i,tx,ty;
h_node hn[8];
if(count>N*N)
{
output_solution();
return;
}
for(i=0;i<8;++i)//求子结点和出口
{
hn[i].x=tx=x+dx[i];
hn[i].y=ty=y+dy[i];
hn[i].waysout=ways_out(tx,ty);
}
sortnode(hn,8);
for(i=0;hn[i].waysout<0;++i);//不考虑无用结点
for(;i<8;++i)
{
tx=hn[i].x;
ty=hn[i].y;
s[tx][ty]=count;
dfs(tx,ty,count+1);
s[tx][ty]=0;
}
}
函数4：主调函数
void main()
{
int i,j,x,y;
for(i=0;i for(j=0;j s[i][j]=0;
printf("Horse jump while N=%d\nInput the position to start:",N);
scanf("%d%d",&x,&y);//输入初始位置
while(x<0||y<0||x>=N||y>=N)
{
printf("Error! x,y should be in 0~%d",N-1);
scanf("%d%d",&x,&y);
}
s[x][y]=1;
dfs(x,y,2);//开始搜索
}

http://blog.csdn.net/tomatoyou/

1、问题描述:
M行、N列棋盘，棋子从起始点P1按照中国象棋“马”的z走法，走跳遍所有点，每个点仅能走一次，最后一步跳至目的点P2。
2、算法分析:
有可采用两种算法，深度优先搜索(DFS)和广度优先搜索(BFS)。两种算法优劣可参考人工智能书籍中关于状态空间搜索算法分析。本人认为，只要方法得当，两种算法均可以求得问题的全部解。而针对“马踏棋盘”这个问题，DFS缺在效率上高于BFS，BFS求解过程的存贮空间需求要远低于BFS。DFS算法需要1个链栈表作为辅助，BFS算法需要2个双向链表。
3、实现伪码:
以下伪码实现DFS算法，函数返回TRUE表明求出一个解，数组BOARD 中各个元素值即为行走步骤。也可以逆向访问栈求解。修改部分代码可以求得全部通路，但是求解时间可能特别长(M=N=5,P1={0,0},P2={4,4}情况下求得全部解56个解时间在1秒左右)。

#define M 5
#define N 5

ElemType{POINT pt; BOOL expanded; void* parent;} 链表节点数据类型
STACK OPEN；
int BOARD[M][N]；//棋盘数组

int ExpandNode(POINT pt,POINT* pts);//根据某种策略扩展节点pt并保存在pts,返回扩展总数。

BOOL SearchByDFS(POINT P1,POINT P2) /*POINT P1,P2入口、出口点*/
{
ListNode tail,head;
POINT ptsExpanded[7];
int Marked=0;

ElemType append,data={P1,FALSE,NULL};
Push( OPEN,data );
BOARD[P1]=++marked;

while(NULL!=(tail=GetTop(OPEN)))//GetTop()返回栈顶指针
{
data=tail.data;
if( Marked==M*N && data.pt==P2) //最后一步并且是目标节点，OK
{
BOARD[data.pt]=++marked;
return TRUE;
}

if( data.expanded==TRUE )//该节点已经扩展过则移除
{
BOARD[data.pt]=0; --marked;
Pop( OPEN );
continue;
}

tail->data.expanded=true; BOARD[data.y][data.x]=++marked; //首先标记
numExpanded=ExpandNode( data.pt, ptsExpanded[]);//扩展节点
for(i=0;i {
append={ptsExpanded[ i], FALSE, (void *)tail };
Push(OPEN, append); //扩展节点放入OPEN表
}
}//end while
}

4。节点扩展策略：

函数ExpandNode(POINT pt,POINT* pts)的策略将极大影响求解效率及解的顺序。8个方位可供测试，若在棋盘上，再测试该点没有走过（BOARD[pt] ==0），若是目标点P2则应该满足当前已经走过的点数(marked)等于MN-1。