一、题目：求解约瑟夫（Josephus）问题
1、【问题描述】：
有一个旅行社要从n个旅客中选出一名旅客，为他提供免费的环球旅行服务。旅行社安排这些旅客围成一个圆圈，并从帽子中取出一张纸条，用纸条上面写的正整数m（m<n）作为报数值。游戏进行时，从第一个人开始按顺时针方向自1开始顺序报数，当报到m时停止报数，报m的人被淘汰出列。然后从他顺时针方向上的下一个人开始从1重新报数，当再次报到m时停止报数，报m的人被淘汰出列。如此下去，直到圆圈中剩下一个人为止。这个最后的幸存者就是游戏的胜利者，他将得到免费旅行的奖励。请让计算机模拟此问题。
2、设计：
2.1概要设计:采用循环单链表实现，其中包括链表节点的设计及循环单链表类的设计。链表的数据元素有头结点和节点的数目，其中头结点的数据类型设计成节点类型，节点的数目size设计成整数类型。循环单链表类的操作集合有构造函数、析构函数、取大小函数、定位函数、插入函数、删除函数、取值函数以及求解该问题约瑟夫函数。其中的删除、取值等操作要保证参数不越界的约束条件i>=0&&i<=size-1;插入操作要满足i>=0&&i<=size;定位操作要使得i>=-1&&i<=size-1.
2.2详细设计：本问题的求解主要是对约瑟夫函数的设计。首先给该函数传入m的值，然后定义一个指针指向头结点，依照题目要求设计循环条件使指针依次指向下一结点直到找到淘汰对象，然后用事先定义的k记录，是指针指向淘汰节点的前一结点，再进行循环，直至完成题目要求。
3、测试：测试函数设计主函数接口，定义n与m的值分别为8，3.定义一个循环单链表对象，将各个数据插入到循环单链表中，再将m值传入约瑟夫函数。测试过程中出现的大部分错误主要来自于功能函数对删除节点的前一节点定位操作的错误，后来在改正过程中添加了k辅助定位，解决了该问题。
4、使用说明及设计小结：使用时每次定义好n与m的值在进行操作。该程序的设计我认为有待改进的地方还是定位操作，该解法的最终实现得益于k的引入。但不免失之普遍性，应该有更好的，更易懂的算法实现。
5、约瑟夫函数实现代码：
#include"LinList.h"
template<class T>
void LinList<T>:: Joseph(int a)
{
int k = 0;
ListNode<T> *p=head,*q;
while(p!=NULL)
{
for(int i=0;i<a;i++)
{
p=p->next;
if(p==head) i--;
}
q=p;
cout<<"淘汰第"<<q->data<<"号"<<endl;
for(int j=0;j<size;j++)
{
p = p->next;
if(p==head) k=j;
}
if(size==1)
{
cout<<"优胜者为第"<<GetData(0)<<"号"<<endl;
exit(0);
}
Delete(size - k -1);
}
}
测试函数：
#include<iostream.h>
#include<stdlib.h>
#include"LinList.h"
void main(void)
{
int m=3;
int n=8;
LinList<int> myList;
for(int i=0;i<n;i++)
myList.Insert(i+1,i);
myList.Joseph(m);
}
程序运行结果：
二、题目：停车场管理问题
1、【问题描述】:
设有一个可以停放n辆汽车的狭长停车场，它只有一个大门可以供车辆进出。车辆按到达停车场时间的早晚依次从停车场最里面向大门口处停放(最先到达的第一辆车放在停车场的最里面)。如果停车场已放满n辆车，则后来的车辆只能在停车场大门外的便道上等待，一旦停车场内有车开走，则排在便道上的第一辆车就进入停车场。停车场内如有某辆车要开走，在它之后进入停车场的车都必须先退出停车场为它让路，待其开出停车场后，这些车辆再依原来的次序进场。每辆车在离开停车场时，都应根据它在停车场内停留的时间长短交费。如果停留在便道上的车未进停车场就要离去，允许其离去，不收停车费，并且仍然保持在便道上等待的车辆的次序。编制程序模拟该停车场的管理。
2、设计
2.1概要设计：这个问题用到的数据类型有链式队列、链式堆栈、顺序堆栈。队列类的数据成员有队列节点类的对头指针和队尾指针还有整数类型的计数器count。操作集合有构造、析构函数、入队列、出队列、非空否、取对头数据元素、随机查找及删除节点、显示队列元素等操作。链式堆栈的数据成员有堆栈节点类型的头指针和整数类型的size。操作集合有入栈、出栈、取栈顶元素、堆栈非空否等操作。其中删除操作要保证size>0。顺序堆栈类的数据成员有DataType类型的堆栈数组和整数类型的栈顶指示器，操作集合有入栈、出栈、取栈顶元素、堆栈非空否等操作。其中入栈操作要保证栈顶指示器的值小于数组的上限，删除操作要保证栈顶指示器的值大于0.
2.2详细设计：本题可用以顺序栈模拟停车场，以链式队列模拟该停车场大门外的便道。需另设一个顺序栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车。输入的数据按到达或离去的时刻有序。栈中的每个元素表示一辆汽车，包括两个数据项：汽车的牌照号码和进入停车场的时刻。
3、测试:输入相应数据进行测试时，发现对于从便道转入到停车场的汽车的收费不对。改正时要将该类型汽车的入停车场时间置为为其空出车位的汽车离停车场的时间。
4、使用说明及设计总结：进行输入时要按照提示输入，注意输入的离开停车场的时间不能早于进入停车场的时间。程序的功能实现的可以，但是还是有些冗长，找到更加精练的算法会更好。
5、功能函数实现代码：
template<class T>
void Reach(SeqStack<T> & s,LinQueue<T> & q)
{
Car C;char nothing[2];
cout<<"\n请输入车牌号（例：鲁A1234）：";
cin>>C.num;
if(s.NotFull())
{
cout<<"\n请输入时间：/** **/";
cin>>C.inpark.hour>>C.inpark.minutes;
s.Push(C);
cout<<"\n汽车"<<C.num<<"进入停车厂\n";
}
else
{
cout<<"停车场已满，该车进入便道！\n";
q.Append(C);
}
}
template<class T >
void Leave(SeqStack<T> & s,LinQueue<T> & q)
{
Car C;LinStack <Car> temp;char nothing[2];
if(s.NotEmpty())
{
cout<<"请输入车牌号：";
cin>>C.num;
if(s.Search(C)) //Search()返回查找的元素是否在栈内
{
while((s.GetTop()!=C) ) //调用运算符重载
temp.Push(s.Pop());
C=s.Pop(); //要找的车出栈
C.Print(); //打印出栈车的信息
while(temp.NotEmpty()) //退出的汽车从新进入停车场
s.Push(temp.Pop());
if(q.NotEmpty()) //便道队列不空，便道车进入场栈
{
Car tC;
tC=q.Delete();
cout<<"\n便道里的车牌号为："<<tC.num<<"的车进入停车场\n";
//设置进入停车场的时间：
tC.inpark.hour=C.outpark.hour;tC.inpark.minutes=C.outpark.minutes; s.Push(tC);
}
else
cout<<"\n便道里没有车辆等待进入停车场。\n"; //便道已空，
//没有车入场栈
return;
}
//车不在场栈内，查找便道
else
{
cout<<"\n该车不在停车场内!\n";
if(q.NotEmpty())
{
if(!(q.Out(C))) //Out()在队列内查找元素，如果存在，删除，
//并返回1，否则返回0
{
cout<<"\n该车不存在!\n";
return;
}
cout<<"\n该车在便道上，不需缴纳停车费!\n";
return;
}
}
}
else cout<<"停车场已空！没有汽车！\n";
}
template<class T >
void List ( SeqStack<T> &s,LinQueue<T> &q)
{
char nothing[2];
cout<<"\n请选择： 1. 列表显示停车场内的车辆 2.列表显示便道上的车辆 :";
int ch;
while(1)
{
cin>>ch;
if(ch!=1 && ch!=2)cout<<"\n输入错误，请继续选择！";
else break;
}
if(ch==1)
{
if(s.NotEmpty())
s.Display();
else cout<<"\n停车场已空!\n";
}
else
{
if (q.NotEmpty())
q.Display();
else cout<<"\n便道已空!\n";
}
}
其中的头文件Car.h代码为：
template<class T>
void Reach(SeqStack<T> & s,LinQueue<T> & q)
{
Car C;char nothing[2];
cout<<"\n请输入车牌号（例：鲁A1234）：";
cin>>C.num;
if(s.NotFull())
{
cout<<"\n请输入时间：/** **/";
cin>>C.inpark.hour>>C.inpark.minutes;
s.Push(C);
cout<<"\n汽车"<<C.num<<"进入停车厂\n";
}
else
{
cout<<"停车场已满，该车进入便道！\n";
q.Append(C);
}
}
template<class T >
void Leave(SeqStack<T> & s,LinQueue<T> & q)
{
Car C;LinStack <Car> temp;char nothing[2];
if(s.NotEmpty())
{
cout<<"请输入车牌号：";
cin>>C.num;
if(s.Search(C)) //Search()返回查找的元素是否在栈内
{
while((s.GetTop()!=C) ) //调用运算符重载
temp.Push(s.Pop());
C=s.Pop(); //要找的车出栈
C.Print(); //打印出栈车的信息
while(temp.NotEmpty()) //退出的汽车从新进入停车场
s.Push(temp.Pop());
if(q.NotEmpty()) //便道队列不空，便道车进入场栈
{
Car tC;
tC=q.Delete();
cout<<"\n便道里的车牌号为："<<tC.num<<"的车进入停车场\n";
//设置进入停车场的时间：
tC.inpark.hour=C.outpark.hour;tC.inpark.minutes=C.outpark.minutes; s.Push(tC);
}
else
cout<<"\n便道里没有车辆等待进入停车场。\n"; //便道已空，
//没有车入场栈
return;
}
//车不在场栈内，查找便道
else
{
cout<<"\n该车不在停车场内!\n";
if(q.NotEmpty())
{
if(!(q.Out(C))) //Out()在队列内查找元素，如果存在，删除，
//并返回1，否则返回0
{
cout<<"\n该车不存在!\n";
return;
}
cout<<"\n该车在便道上，不需缴纳停车费!\n";
return;
}
}
}
else cout<<"停车场已空！没有汽车！\n";
}
template<class T >
void List ( SeqStack<T> &s,LinQueue<T> &q)
{
char nothing[2];
cout<<"\n请选择： 1. 列表显示停车场内的车辆 2.列表显示便道上的车辆 :";
int ch;
while(1)
{
cin>>ch;
if(ch!=1 && ch!=2)cout<<"\n输入错误，请继续选择！";
else break;
}
if(ch==1)
{
if(s.NotEmpty())
s.Display();
else cout<<"\n停车场已空!\n";
}
else
{
if (q.NotEmpty())
q.Display();
else cout<<"\n便道已空!\n";
}
}
测试函数代码：
#include<iostream.h>
#include<stdlib.h>
const float PRICE=0.5;
#include"Car.h"
const MaxStackSize=2;
#include"LinQueue.h"
#include"LinStack.h"
#include"SeqStack.h"
#include"Parking.h"
void main()
{
SeqStack < Car > s;
LinQueue< Car > q;
int ch;
char ch_test;
while(1)
{
cout<<"\n************停车选择****************\n"
<<"\n 1 . 车辆到达 2 . 车辆离开 3 . 列表显示 4 . 退出系统 \n"
<<" 请选择 ：";
/*这里处理的有点复杂，这样可以避免两种错误情况：
1、输入的是字母，若直接读入到int型会导致死循环，经测试，>>符输入int变量时(如 cin>>ch)，若键入字母，>>只检测流内容不提取，同时将变量置0(即ch==0);
2、若改用 char型做判断条件，当错误输入多个字符(如25 32)，由于cin>>char 只提取一个字符，会导致下面输入自动读入未提取的字符。因此，这里的实现有点复杂。*/
while(1)
{
cin>>ch_test;
if(ch_test>='0'&&ch_test<='9')
{
cin.putback (ch_test);
cin>>ch;
}
else
{
cout<<"\n输入错误，请再次选择：";
continue;
}
if(ch>=1 && ch<=4)break;
else cout<<" \n输入错误，请再次选择 ：";
}
cout<<"\n*****************************************************\n";
switch(ch)
{
case 1:Reach(s, q);break;
case 2:Leave( s, q);break;
case 3:List( s, q );break;
case 4:if (s.NotEmpty ())
{cout<<"还有车未离开，不能结束程序！";break;}
exit(0);
default:break;
}
}
}
程序运行结果:
三、题目：背包问题
1、【问题描述】：
设有一个背包可以放入的物品重量最重为s，现有n件物品，它们的重量分别为w[0]、 w[1]、w[2]、…、w[n-1]。问能否从这n件物品中选择若干件放入此背包中，使得放入的重量之和正好为s。如果存在一种符合上述要求的选择，则称此背包问题有解（或称其解为真）；否则称此背包问题无解（或称其解为假）。试用递归方法设计求解背包问题的算法。
2、设计:
2.1概要设计:为实现求解，设计了一个背包类Backpack，它的数据成员有背包的最大承重量，物品件数和各件物品重量数组，都是整数类型的。操作集合有构造函数、析构函数和knap函数。
2.2详细设计：该题的设计和一般递归问题一样，就是要找到可以迭代的步骤和递归的出口。本题是将实现主要功能的knap函数的返回值设计成布尔类型。有解则为真，否则为假。运用判别条件if (knap(s-w[n],n-1)==True)反复迭代直至递归出口。
3.测试：用数据s1=51，n1=6，w1[]={0,1,2,4,8,16,32}进行测试。
4、使用说明：分别赋予背包的最大承重量，物品件数和各件物品重量数组以数值使用即可。
5、程序实现代码：
#include <iostream.h>
enum boolean {False,True};
class Backpack
{
private:
int s; //背包最大承重量
int n; //物品件数
int *w; //各件物品重量数组
public:
Backpack(int ss,int nn,int ww[])
{
s=ss;
n=nn;
w=new int [n];//或者[n+1]
for(int i=0;i<=n;i++)
w[i]=ww[i];
}
~Backpack(void) {}
boolean knap(int s,int n)
{
if (s==0) return True;
if (s<0 ||s>0 && n<1) return False;
if (knap(s-w[n],n-1)==True)
{
cout<<w[n]<<",";
return True;
}
return knap(s,n-1);
}
};
//测试程序(主函数)
void main()
{
int s1=51; //背包最大承重量
int n1=6; //或者为int n1=7, 物品件数
int w1[]={0,1,2,4,8,16,32}; //各件物品重量数组
Backpack beb(s1,n1,w1); //生成对象
beb.knap(s1,n1); //调用递归函数
}
程序运行结果：
四、题目：选址问题
1、【问题描述】：
给定n个小区之间的交通图。若小区i与小区j之间有路可通，则将顶点i与顶点j之间用边连接，边上的权值
表示这条道路的长度。现在打算在这n个小区中选定一个小区建一所医院。试问这家医院应建在哪个小区，才能使距离医院最远的小区到医院的路程最短？请设计一个算法求解上述问题。
2、设计：将n个小区的交通图视为一张带权无向图，并利用邻接矩阵来存放带权无向图。算法的思想是：设计算法计算每对顶点之间的最短路径，然后找出从每一个顶点到其它各顶点的最短路径中最长路径，在这n条最长路径中找出最短的一条，则它的出发点即为所求。
3、测试：用一个有四个小区的交通图进行测试，注意初始化时数组的下标要对应正确的权值。
4、使用说明：将所给图示转用矩阵存储，代入数值进行使用。
5、算法实现代码：
#include <iostream.h>
const int mw=10000; //代表权重无穷大
const int mi=10000;
int ds(int a[][4],int n) //本例共4个顶点
{
int i,j,k,s,min;
for(k=0;k<n;k++)
for(i=0;i<n;i++)
for(j=0;j<n;j++)if(a[i][k]+a[k][j]<a[i][j])
a[i][j]=a[i][k]+a[k][j];
k=0;
min=mi;
for(i=0;i<n;i++)
{
s=0;
for(j=0;j<n;j++)
if(a[i][j]>s)
s=a[i][j];
if(s<min)
{
k=i;
min=s;
}
}
return k;
}
void main()
{
int n=4; //本例共4个顶点
int weight[4][4]={0,1,13,4,1,0,9,2,13,9,0,8,4,2,8,0};
int p=ds(weight,n);
cout<<p<<endl;
}
程序运行结果：
五、题目：哈夫曼编/译码器
1、[问题描述]：
利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼编/译码系统。
2、设计：
2.1概要设计：本题运用到了哈夫曼树的存储结构。其中包括哈夫曼树的节点结构和存放哈夫曼编码的数据元素结构。都是结构体数据类型。主要操作就是根据结点个数和相应权值构造哈夫曼树和由n个叶结点的哈夫曼树haffTree构造哈夫曼编码haffCode及基于以上操作的译码操作。
2.2详细设计：首先统计由终端输入的长度不超过80的字符串的长度n、以及不同字符的个数和每种字符的权值，然后建立哈夫曼树。接着利用已建好的哈夫曼树进行编码并输出，最后利用已建好的哈夫曼树和已经完成的编码进行译码并输出。
3、测试:自行从终端输入长度小于80的不带空格的字符串进行测试。测试时输入了空格，程序进入死循环。
4、使用说明：运行之后输入想要编码的字符串，注意长度要小于80且不带空格
5、主要功能实现函数
#include<string.h>
void GetIndexArry(int *Index,char *s,letter *L,int Llength)
{
for(int i=0;i<strlen(s);i++)
for(int j=0;j<Llength;j++)
if(L[j].ascii==s[i])
Index[i]=j;
;
}
void GetCharArry(int *Index,letter *L,char *s,int slength)
{
for(int i=0;i<slength;i++)
s[i]= L[Index[i]].ascii;
s[i]='\0';
}
void ChangeToCode(int * Index,Code * hcode,char *text,int n,int NodeNum)
{
int t=0,j=0,i=0;
for(i=0;i<n;i++)
{
//j=hcode[(Index[i])].start+1;
for(j=hcode[Index[i]].start+1;j<NodeNum;j++)
text[t++]=48+(hcode[Index[i]].bit[j]);
}
text[t]='\0';
}
int CodeToLetterIndex(char * text,HaffNode * HTree,int NumOfHNode,int * Index,int textlen)
{
int n=0, i=0;
int p=0;
while(i<textlen)
{
p=NumOfHNode-1; //哈夫曼树的总结点数
while(1) //从树根根据编码到达树叶，读取树叶值
{
if(text[i]=='0')
{
if(HTree[p].leftChild==-1)
{
Index[n++]=p;
Index[n-1];
break;
}
else
{
p=HTree[p].leftChild;
i++;
}
}
else
{
if(HTree[p].rightChild==-1)
{
Index[n++]=p;
Index[n-1];
break;
}
else
{
p=HTree[p].rightChild;
i++;
}
}
}
}
return n;
}
int Statistics(char * input,letter * L)
{
int slength=0,j=0;
while(1)
{
cout<<"请输入字母(不多于80个)\n";
cin>>input;
slength=strlen(input);
if(slength>80)
cout<<"字母数多于80! 请重新输入!\n";
else break;
}
for(int i=0;i<slength;i++)
{
for( j=0;j<26;j++)
{
if(L[j].weight==0)break;
if(L[j].ascii==input[i])
{
L[j].weight++;
i++;
j=0;
}
}
L[j].weight=1;
L[j].ascii=input[i];
}
j=0;
while(L[j].ascii!=0)
j++;
return j;
}
测试函数：
#include<iostream.h>
#include<string.h>
#include<stdlib.h>
//字母结构体，存储检测到的字母的个数（权值）和其ascii码
struct letter
{
int weight;
int ascii;
};
//const int MaxN=54;
const int MaxValue=10000;
const int MaxBit=10;
const int NumOfDifferentChar=26;
#include"HaffmanTree.h"
#include"function.h"
void main()
{
int ch;int num=0,j;
int slength=0,out_slen=0;
while(1) //反复运行选择菜单
{
while(1)
{
cout<<"请选择操作 : 1.输入字母串进行编码译码 2.退出程序 ：";
cin>>ch;
if(ch!=1&&ch!=2)cout<<"输入错误！\n";
else break;
}
if(ch==1)
{
//ch=5;
//***************统计过程**********************
char input [80],output[80];
letter L[NumOfDifferentChar]={0};
while(1)
{
cout<<"请输入字母(不多于80个)\n";
cin>>input;
slength=strlen(input);
if(slength>80)
cout<<"字母数多于80! 请重新输入!\n";
else break;
}
for(int i=0;i<slength;i++)
{
for( j=0;j<26;j++)
{
if(L[j].weight==0)break;
if(L[j].ascii==input[i])
{
L[j].weight++;
i++;
j=0;
}
}
L[j].weight=1;
L[j].ascii=input[i];
}
j=0;
while(L[j].ascii!=0)
j++;
num=j;
if(num>MaxBit)
{
cout<<"MaxBit 值太小，重新设置MaxBit值！";
exit(0);
}
if(num>NumOfDifferentChar)
{
cout<<"最大字符类型数（NumOfDifferentChar）太小，请重新设置！！";
exit(0);
}
int *weight=new int[num];
for(i=0;i<num;i++)
weight[i]=L[i].weight;
//*****************统计过程结束******************
//******************建树编码过程******************
HaffNode *myHaffTree = new HaffNode[2*num-1];
Code *myHaffCode = new Code[num];
Haffman(weight, num, myHaffTree);
HaffmanCode(myHaffTree, num, myHaffCode);
//***************建树编码结束*********************
//Index中存储输入字符串对应的叶节点的序号
int *IndexToCode=new int[slength];
int *IndexToLetter=new int[slength];
GetIndexArry(IndexToCode,input,L,num);
//计算字符串转换为编码后的长度
int CodeTextLen=0;
for(i=0;i<num;i++)
CodeTextLen+=(num-(myHaffCode[i].start+1))*myHaffCode[i].weight;
char *text=new char[CodeTextLen+1]; //考虑到编码为1、0，故将码文数组定义
//为char型，增加一个用于放结束符
//根据字母串对应的结点序列得到编码串
ChangeToCode(IndexToCode,myHaffCode,text,slength,num);
cout<<"***************编码结果****************\n";
cout<<text<<endl;
//解码得到对应的叶节点序列
out_slen=CodeToLetterIndex(text,myHaffTree,2*num-1,IndexToLetter,CodeTextLen);
//根据叶节点序列得到字母串序列
GetCharArry(IndexToLetter,L,output,out_slen);
cout<<"**************译码结果*****************\n";
cout<<output<<endl;
}
else exit(0);
}
}
程序运行结果：
六、题目：Hash表问题
1、[问题描述]：
假设有一个100*100的稀疏矩阵，其中1%的元素为非零元素，现要求对其非零元素进行散列存储，使之能够按元素的行、列值存取元素（即元素的行、列值联合一起作为元素的关键字），试采用除留余数法构造散列函数和线性探查法处理冲突，分别设计出建立散列表和查找散列表的算法。
2、设计
2.1概要设计:用哈希表存储结构。该结构的数据成员有DataType类型的数据值、DateType类型的哈希表数组、整数类型的哈希表长度和整数类型的当前的表项个数。操作集合有构造和析构函数、建立哈希表、采用线性探查法查找元素等操作。
2.2详细设计：该题主要需要查找操作，查找操作采用线性探查法，即根据公式d=(d+1) % TableSize逐一查找，若找到则输出查找成功并输出元素下标，否则输出查找不成功。
3、测试:构造三元组DataType a[] = {{0,3,22},{0,6,15},{1,1,11},{1,5,17},{2,3,-6},
{3,5,39},{4,0,91},{5,2,28}},并使表长为11进行测试。
4、使用说明:构造哈希表时稀疏矩阵的非零元素用三元组形式存储输入，并事先定义好哈希表的长度。给查找函数传值时行号在前列号在后
5、测试函数：
#include <iostream.h>
struct DataType
{
int row;
int col;
float val;
} ;
#include "HashTable.h"
void main(void)
{
DataType a[] = {{0,3,22},{0,6,15},{1,1,11},{1,5,17},{2,3,-6},
{3,5,39},{4,0,91},{5,2,28}}; //稀疏矩阵非零元素的三元组形式
HashTable myHashTable(11); //取m=11
int i;
int n = 8; //n为非零元素个数
for(i = 0; i < n; i++)
myHashTable.Create(a[i]);
int k=myHashTable.Search(0,6); //提供的形式参数是元素的行号和列号
if(k>=0)
cout<<"查找成功！并且它在哈稀表中的下标是"<<k<<endl;
else
cout<<"查找不成功！"<<endl;
}
程序运行结果：
七、题目：求迷宫最短路径---试从一个迷宫（maze）的入口到出口找出一条最短路经
1、[问题描述]：
迷宫问题是实验心理学中的一个经典问题。心理学家把一只老鼠从一个无顶盖的大盒子（迷宫）的入口处赶进迷宫，迷宫中设置了很多墙壁，对前进方向形成了多处障碍。心里学家在迷宫的唯一出口处放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口。如果从迷宫的入口到达出口，途中不出现行进方向错误，则将得到一条最佳线路。
求解此迷宫问题固然可以使用递归算法，但是，这里要求不使用递归算法，而是应用顺序堆栈实现迷宫问题的非递归解法。
设迷宫用一个二维整数数组maze[m][p]表示（m行，p列），并且各个元素只取0值或1值。若某个元素的值为1，则表示此处无通路；若某个元素的值为0，则表示此处为通路。
同时，还设定迷宫的入口为第一个元素maze[0][0]处，出口为最后一个元素maze[m-1][p-1]处。
另外，若存在最短路经，则输出由出口到入口这一条路径； 若不存在最短路经，则输出提示信息：THERE IS NO PATH IN MAZE.
2、设计
2.1概要设计：顺序堆栈类的数据成员有DataType类型的堆栈数组和整数类型的栈顶指示器，操作集合有入栈、出栈、取栈顶元素、堆栈非空否等操作。其中入栈操作要保证栈顶指示器的值小于数组的上限，删除操作要保证栈顶指示器的值大于0.
2.2详细设计：为了在程序中判断方便，把迷宫扩展成为maze[m+2][p+2]，即在迷宫的四周增加一圈围墙，扩展部分（即第0行和第m-1行、第0列和第p-1列）的元素设置为1，借次实现在迷宫周围布上一圈不准通过的墙，这样，在迷宫的任一位置maze[i][j]上都有8个可以移动的方向即：
北： maze[i-1][j] ------ 用0表示此方向(d=0)
东北： maze[i-1][j+1] ------ -用1表示此方向(d=1)
东： maze[i][j+1] -------用2表示此方向(d=2)
东南： maze[i+1][j+1] -------用3表示此方向(d=3)
南： maze[i+1][j] -------用4表示此方向(d=4)
西南： maze[i+1][j-1] ------ -用5表示此方向(d=5)
西： maze[i][j-1] ------- 用6表示此方向(d=6)
西北： maze[i-1][j-1] ------- 用7表示此方向(d=7)
用结构数组move[8]存放八个方向上的位置偏移量，如表-1所示：
表-1 前进方向表
数组move[8]的数据类型为：
Struct offsets
{
int a; //相对于点[i][j]的i的某个方向位置偏移量
int b; //相对于点[i][j]的j的某个方向位置偏移量
};
这样，如果当前位置在[i][j]时，若向西南方向（d=5）行走，那么下一相邻位置[g][h]则为
g=i+move[5].a=i+1;
h=j+move[5].b=j-1;
为了标志已经通过的位置，并防止重走原路，则另设一个标志数组mark[m+2][p+2]，
其初值为0，在寻找路径的过程中，若通过了位置[i][j]，则将mark[i][j]置为为1,以防再次通过此位置。
主要算法思想：
将入口maze[1][1]作为第一个出发点，直至达到出口maze[m][p],或者迷宫所有位置都搜索完毕为止。用栈来保存在试探性的前进过程中所走过的路径。栈中需保存一系列三元组以记录所走过的路径信息，这些三元组的数据类型为：
struct DataType
{
int x; //行坐标
int y; //列坐标
int dir; //方向
};
当在迷宫中向前搜索时，可能同时存在几个允许的前进方向。可以利用三元组记下当前位置和上一步前进方向，然后根据表-1选择某一个允许的前进方向前进一步，并将有关信息入栈，以记下前进路径。如果该前进方向走不通，则将位于栈顶的元素退栈，即在前进路径上回退一步，再尝试其它的允许方向。如果栈空，则表示已经回退到开始位置。
3.测试：用增加了四周围墙后的迷宫数据int Maze1[m2][p2]={ 1,1,1,1,1,1,1, 0,0,1,1,1,1,1, 1,0,1,1,1,1,1, 1,1,0,1,1,1,1, 1,1,1,0,1,1,1, 1,1,1,1,0,1,1, 1,1,1,1,1,0,1, 1,1,1,1,1,0,1, 1,1,1,1,1,0,1, 1,1,1,1,1,0,0, 1,1,1,1,1,1,1};及方向表offsets move1[8]= {{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}};进行测试。
4、使用说明：在使用之前将迷宫数据增加四周墙后用数组存储并提供标示每个路口方向的方向表，然后既可以使用。
5、应用顺序堆栈实现迷宫问题的非递归解法实现代码：
void path(int Maze[][p2],offsets move[])
{
int mark[m2][p2]; //定义标志数组
for (int i=0;i<m2;i++) //初始化标志数组
for (int j=0;j<p2;j++)
mark[i][j]=0;
mark[1][1]=1; //标记入口
SeqStack st; //生成栈对象
//初始化坐标方向三元组
DataType tmp;
tmp.x=1;
tmp.y=1;
tmp.dir=0;
st.Push(tmp); //入栈
while(st.NotEmpty()) //若栈不空，持续走下去
{
tmp=st.Pop(); //退栈
int i=tmp.x;
int j=tmp.y;
int d=tmp.dir; //d为方向表下标
while(d<8) //还有移动，继续移动
{
int g=i+move[d].a; //找下一个位置(g,h)
int h=j+move[d].b;
if(g==m && h==p) //到达出口
{
cout<<"["<<m<<","<<p<<"]";
while(st.NotEmpty()) //输出栈中各个元素(即路径)
{
DataType temp=st.Pop();
cout<<"<--["<<temp.x<<","<<temp.y<<"]";
}
cout<<endl;
return;
}
if(!Maze[g][h] && !mark[g][h]) //未到达出口
{
mark[g][h]=1; //标记已访问过
tmp.x=i;
tmp.y=j;
tmp.dir=d+1;
st.Push(tmp); //进栈
//下面是移动到(g,h)
i=g;
j=h;
d=0;
}
else
d++; //尝试下一个方向
}
}
cout<<" THERE IS NO PATH IN MAZE."<<endl;
}
用到的DataType结构体及测试函数：
#include <iostream.h>
#include <stdlib.h>
const int m=9; //指定迷宫的行数
const int p=5; //指定迷宫的列数
const int m2=m+2; //为迷宫四周增加围墙
const int p2=p+2; //为迷宫四周增加围墙
//顺序栈中数据元素的数据结构和方向表结构数组的数据结构
struct DataType
{
int x;
int y;
int dir;
};
struct offsets
{
int a;
int b;
};
const int MaxStackSize=(m2)*(p2); //顺序栈大小
#include "SeqStack1.h" //包含顺序栈类的定义与实现，参见p95
#include "Labyrinth.h" //包含求解迷宫路径的函数，参见p96
void main() //测试主函数
{
//下面的数组Maze1[m2][p2]是增加了四周围墙后的迷宫数据示例
int Maze1[m2][p2]={ 1,1,1,1,1,1,1,
0,0,1,1,1,1,1,
1,0,1,1,1,1,1,
1,1,0,1,1,1,1,
1,1,1,0,1,1,1,
1,1,1,1,0,1,1,
1,1,1,1,1,0,1,
1,1,1,1,1,0,1,
1,1,1,1,1,0,1,
1,1,1,1,1,0,0,
1,1,1,1,1,1,1};
//下面的结构数组move1[8]是方向表
offsets move1[8]={{-1,0},{-1,1},{0,1},{1,1},
{1,0},{1,-1},{0,-1},{-1,-1}};
path(Maze1,move1); //调用求迷宫路径的函数
}
程序运行结果：
