队列矩阵存储
A. 队列通常采用两种存储结构是
应该是顺序存储和链接存储，通称顺序队列和链队列，其中顺序队列一般用的是循环队列的方式
B. C++怎么用队列存储数据
#include <stdio.h>
#include <stdlib.h>
typedef int elemType;
strUCt sNode{
elemType data; /* 值域 */
struct sNode *next; /* 链接指针 */
};
struct queueLK{
struct sNode *front; /* 队首指针 */
struct sNode *rear; /* 队尾指针 */
};
/* 1.初始化链队 */
void initQueue(struct queueLK *hq)
{
hq->front = hq->rear = NULL; /* 把队首和队尾指针置空 */
return;
}
/* 2.向链队中插入一个元素x */
void enQueue(struct queueLK *hq, elemType x)
{
/* 得到一个由newP指针所指向的新结点 */
struct sNode *newP;
newP = malloc(sizeof(struct sNode));
if(newP == NULL){
printf("内存空间分配失败！ ");
exit(1);
}
/* 把x的值赋给新结点的值域，把新结点的指针域置空 */
newP->data = x;
newP->next = NULL;
/* 若链队为空，则新结点即是队首结点又是队尾结点 */
if(hq->rear == NULL){
hq->front = hq->rear = newP;
}else{ /* 若链队非空，则依次修改队尾结点的指针域和队尾指针，使之指向新的队尾结点 */
hq->rear = hq->rear->next = newP; /* 注重赋值顺序哦 */
}
return;
}
/* 3.从队列中删除一个元素 */
elemType outQueue(struct queueLK *hq)
{
struct sNode *p;
elemType temp;
/* 若链队为空则停止运行 */
if(hq->front == NULL){
printf("队列为空，无法删除！ ");
exit(1);
}
temp = hq->front->data; /* 暂存队尾元素以便返回 */
p = hq->front; /* 暂存队尾指针以便回收队尾结点 */
hq->front = p->next; /* 使队首指针指向下一个结点 */
/* 若删除后链队为空，则需同时使队尾指针为空 */
if(hq->front == NULL){
hq->rear = NULL;
}
free(p); /* 回收原队首结点 */
return temp; /* 返回被删除的队首元素值 */
}
/* 4.读取队首元素 */
elemType peekQueue(struct queueLK *hq)
{
/* 若链队为空则停止运行 */
if(hq->front == NULL){
printf("队列为空，无法删除！ ");
exit(1);
}
return hq->front->data; /* 返回队首元素 */
}
C. 栈和队列队列在存储方式上面的区别
栈和队列都是在一个特定范围的存储单元中存储的数据，这些数据都可以重新被取出使用。
不同的是，栈就象一个很窄的桶先存进去的数据只能最后才能取出来，而且队列则不一样，即“先进后出”。
队列有点象日常排队买东西的人的“队列”先牌队的人先买，后排队的人后买，即“先进先出”。有时在数据结构中还有可能出现按照大小排队或按照一定条件排队的数据队列，这时的队列属于特殊队列，就不一定按照“先进先出”的原则读取数据了。
D. 用队列实现以邻接矩阵作存储结构图的宽度优先搜索
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
int visited[20]={0};
typedef struct
{
char vexs[20];/*顶点表*/
int edges[20][20];
int n,e;
}Mgraph;
typedef struct QNode
{
int data;
struct QNode *next;
int Queusize;
}
QNode,*QueuePtr;//定义队列结点类型
typedef struct
{
QueuePtr front;
QueuePtr rear;
}
LinkQueue;//队列的类型
void InitQueue(LinkQueue *Q)//创建队列
{
Q->front=Q->rear=(QueuePtr)malloc(sizeof(QNode));
Q->front->next=NULL;
}
void EnQueue(LinkQueue *Q,int e)//将元素插入队列
{
QueuePtr p;
p=(QueuePtr)malloc(sizeof(QNode));
p->data=e;
p->next=NULL;
Q->rear->next=p;
Q->rear=p;
}
int DeQueue(LinkQueue *Q)//将元素出列且返回元素的位置
{
int e;
QueuePtr p;
p=Q->front->next;
e=p->data;
Q->front->next=p->next;
if(Q->rear==p)
Q->rear=Q->front;
free(p);
return (e);
}
int QueueEmpty(LinkQueue *Q)//判断队列是否为空
{
if(Q->front==Q->rear )
return 1;
else
return 0;
}
void CreateMGraph(Mgraph *G)
{
int i,j,k;
printf("输入顶点和边数\n");
scanf("%d %d", &G->n,&G->e);
getchar();
printf("输入%d个顶点\n",G->n);
for(i=0;i<G->n; i++ )
G->vexs[i]=getchar();
for (i = 0;i<G->n; i++)
for (j = 0;j <G->n; j++)
G->edges[i][j]=0;
printf("在矩阵中输入%d个元素:\n",2*(G->e));
for(k = 0;k<2*(G->e);k++)
{
scanf("%d%d",&i,&j);
G->edges[i][j]=1;
}
}
void BFS(Mgraph G,int i)//广度优先遍历
{
int u,j;
LinkQueue Q;
InitQueue(&Q);
printf("%c",G.vexs[i]);
visited[i]=1;//标记
EnQueue(&Q,i);
while(!QueueEmpty(&Q))
{
i=DeQueue(&Q);
for(j=0;j<G.n;j++)
if(G.edges[i][j]==1&&!visited[j])
{ printf("%c",G.vexs[j]);
visited[j]=1;
EnQueue(&Q,j);
}
}
}
void main()
{
Mgraph G;
CreateMGraph(&G);
printf("广度:\n");
BFS(G,0);
}
给你吧，有不懂再问我。
E. 简述栈和队列的顺序存储结构和链式存储结构的优缺点
顺序存储结构是在内存中开辟一个连续的空间用来存储数据,因此对于内存的需求和苛刻,必须是连续的空间.在数据查找(特别是不按照规律排列的数据),时间复杂度教少.效率高.
链式存储结构是采取连表指针来指示数据的存储位置,这就可以是在内存中随意的存储,没有必须连续储存空间的要求,对于内存的要求相对教容易.但是要是是从小到大顺序排列的数据,链式存储结构的时间复杂度教小,效率高.但是要是不规则排布的数据一般时间复杂度较高,效率更低
F. 数据结构的队列堆栈和矩阵问题（C语言）
翻严蔚敏的书吧
G. 用邻接矩阵存储无向图，并用深度优先和广度优先遍历搜索输出序列，要能运行的，并把运行的结果截图下来
#include<iostream.h>
#include<stdlib.h>
#include<malloc.h>
#define maxsize 50
struct arcnode //定义边结点 链表结点
{
int adjvex; //弧头顶点的位置
struct arcnode *nextarc; //指向相同弧尾的下一条弧的指针
};
struct vnode //定义顶点结点
{
int data; //顶点数据
struct arcnode *firstarc; //指向第一条已该点为弧尾的弧
};
int m,n,v;
void creatgraph (struct vnode a[maxsize]);
void dfstraverse(struct vnode a[maxsize]);
void bfstraverse(struct vnode a[maxsize]);
void main()
{
struct vnode adjlist[maxsize];
int cord;
do
{
cout<<"——主菜单——"<<endl;
cout<<"1.建立无向图的邻接表"<<endl;
cout<<"2.深度遍历图"<<endl;
cout<<"3.广度遍历图"<<endl;
cout<<"4.结束程序运行"<<endl;
cout<<"————————————"<<endl;
cout<<"请输入你的选择(1, 2, 3, 4:)"<<endl;
cin>>cord;
switch(cord)
{
case 1:creatgraph(adjlist);
break;
case 2:dfstraverse(adjlist);
break;
case 3:bfstraverse(adjlist);
break;
case 4:exit(0);
}
}while(cord<=4);
}
void creatgraph(struct vnode a[maxsize])
{
//a[maxsize]存放顶点
int i,j,k;
struct arcnode *p;
cout<<"请输入边数和顶点数:"<<endl;
cin>>m>>n;
for(k=0;k<n;k++) //初始化
{
a[k].data=k+1;
a[k].firstarc=NULL;
}
cout<<"输入两个相关联的顶点:"<<endl;
for(k=0;k<m;k++) //m代表边数
{
cin>>i>>j;
//输入为无向图
p=(struct arcnode*)malloc(sizeof(struct arcnode));
p->adjvex=j; //弧头顶点的位置
p->nextarc=a[i-1].firstarc; //把指向第一条以该点为弧尾的弧给指向相同弧尾的下一条弧的指针
a[i-1].firstarc=p;
p=(struct arcnode*)malloc(sizeof(struct arcnode));
p->adjvex=i;
p->nextarc=a[j-1].firstarc;
a[j-1].firstarc=p;
}
cout<<endl;
for(k=0;k<n;k++)
{
cout<<"顶点"<<a[k].data<<"相关联的顶点是:";
p=a[k].firstarc;
while(p)
{
cout<<p->adjvex<<" ";
p=p->nextarc;
}
cout<<endl;
}
}
void dfstraverse(struct vnode a[maxsize]) //深搜
{
struct arcnode *p,*ar[maxsize]; //ar[maxsize]作为顺序栈，存放遍历过程中边结点的地址
int x,y,i,top=-1;
int visited[maxsize]; //用做存放已遍历过顶点的标记
for(i=0;i<n;i++) //初始化，标记为0
visited[i]=0;
cout<<"输入遍历的第一个顶点"<<endl; //输入遍历的初始点
cin>>x; //输入图遍历的始顶点的编号
cout<<x;
visited[x-1]=1; //标记已访问的顶点
//下一个要遍历的顶点所关联的边结点，向量表的下标从0开始
p=a[x-1].firstarc; //指向第一条已该点为弧尾的弧
while((p) || (top>=0))
{
if(!p)
{
p=ar[top]; //ar[maxsize]作为顺序栈，存放遍历过程中边结点的地址
top--;
}
y=p->adjvex; //弧头顶点的位置
if(visited[y-1]==0) //若未遍历过，则遍历，并且下一个顶点进栈，从本顶点出发继续按深度遍历
{
visited[y-1]=1; //访问后进行标记
cout<<"->"<<y; //输出该顶点
p=p->nextarc; //指向相同弧尾的下一条弧的指针
if(p)
{
top++;
ar[top]=p; //ar[maxsize]作为顺序栈，存放遍历过程中边结点的地址
}
p=a[y-1].firstarc;
}
else
p=p->nextarc;
}
cout<<endl;
}
void bfstraverse(struct vnode a[maxsize]) //广搜
{
//数组a[max]为顺序栈列存放刚遍历过的顶点号
struct arcnode *p;
int x,y,i,front=-1,rear=-1,ar[maxsize],visited[maxsize];//数组ar[maxsize]为顺序队列存放刚遍历过的顶点号
for(i=0;i<n;i++) //初始化标记数组
visited[i]=0;
cout<<"输入遍历的第一个顶点"<<endl;
cin>>x;
cout<<x;
visited[x-1]=1;
p=a[x-1].firstarc; //指向第一条已该点为弧尾的弧
while((p) || (front!=rear))
{
if(!p)
{
front++;
y=ar[front];
p=a[y-1].firstarc; //指向第一条已该点为弧尾的弧
}
y=p->adjvex; //弧头顶点的位置
if(visited[y-1]==0) //遍历顺点并插入队列
{
visited[y-1]=1;
cout<<"->"<<y;
rear++;
ar[rear]=y;
}
p=p->nextarc; //指向相同弧尾的下一条弧的指针
}
cout<<endl;
}
H. 队列的两种存储方式对比
队列的两种存储方式分为消息投递实时性：使用短轮询方式，实时性取决于轮询间隔时间：使用长轮询，同写入实时性一致，消息的写入延时通常在几个毫秒。总结：短轮询：周期性的向服务提供方发起请求，获取数据优点：前后端程序编写比较容易。缺点：请求中有大半是无用，难于维护，浪费带宽和服务器资源；响应的结果没有顺序（因为是异步请求，当发送的请求没有返回结果的时候，后面的请求又被发送。而此时如果后面的请求比前面的请 求要先返回结果，那么当前面的请求返回结果数据时已经是过时无效的数据了）。长轮询：客户端向服务器发送请求，服务器接到请求后保持住连接，直到有新消息才返回响应信息并关闭连接，客户端处理完响应信息后再向服务器发送新的请求。优点：在无消息的情况下不会频繁的请求，耗费资源小。缺点：服务器hold连接会消耗资源，难于管理维护。消费失败重试Kafka：消费失败不支持重试RocketMQ：消费失败支持定时重试，每次重试间隔时间顺延总结：kafka也可以通过编写代码来实现写入和消费失败的重试机制，这种要求需要用户来编写代码实现，kafka只是提供了这种方式，但并不是他推荐的使用方式，他的设计模式上只是兼顾了这种情况，并不是重点。RocketMQ在设计上就考虑了这种情况，在提供的官方api中提供了重试的设置，用户可以选择多种模式的重试机制，以及自定义的重试逻辑，简单场景下用户只用设置一下参数即可。关于需要重试的场景例如充值类应用，当前时刻调用运营商网关，充值失败，可能是对方压力过多，稍后在调用就会成功，如支付宝到银行扣款也是类似需求。这里的重试需要可靠的重试，即失败重试的消息不因为Consumer宕机导致丢失。
I. 队列怎么存储与实现PASCAL
队列是一种特殊的表，因此凡是可以用来实现表的数据结构都可以用来实现队列。不过，队列的中的元素的个数通常不固定，因此常用循环数组和链表两种方法实现队列。
链队列:
用指针实现队列得到的实际上是一个单链表。由于入队在队尾进行，所以用一个指针来指示队尾可以使入队操作不必从头到尾检查整个表，从而提高运算的效率。另外，指向队头的指针对于Gethead和Dequeue运算也是必要的。为了便于表示空队列，我们仍使用一个表头单元，将队头指针指向表头单元。当队头和队尾指针都指向表头单元时，表示队列为一个空队列。
用指针实现队列时，单元类型及队列类型可说明如下:
type
queueptr=^queuenode;
queuenode=record
data:elemtp;
next:queueptr;
end;
linkedquetp=record
front,rear:queueptr;
end;
其中front为队头指针，rear为队尾指针。图2是用指针表示队列的示意图。
图2
面我们来讨论队列的5种基本运算。
函数
Gethead(Q)
功能
这是一个函数，函数值返回队列Q的队头元素。
实现
Function
Gethead(var
Q:linkedquetp):elemtp;
begin
if
Empty(Q)
then
error('The
queue
is
empty!')
else
return(Q.front^.next^.data);
end;
函数
Enqueue(Q,x)
功能
将元素x插入队列Q的队尾。此运算也常简称为将元素x入队。
实现
Procere
Enqueue(x:elemtp;var
Q:linkedquetp);
begin
new(Q.rear^.next);
Q.rear:=Q.rear^.next;
Q.rear^.data:=x;
Q.rear^.next:=nil;
end;
函数
Empty(Q)
功能
这是一个函数，若Q是一个空队列，则函数值为true，否则为false。
实现
Function
Empty(var
Q:QueueType):Boolean;
begin
return(Q.front=Q.rear);
end;
函数
Dequeue(Q)
功能
将Q的队头元素删除，简称为出队。
实现
Procere
Dequeue(var
Q:linkedquetp);
var
p:queueptr;
begin
if
Empty(Q)
then
Error('The
queue
is
empty!')
else
begin
p:=Q.front;
Q.front:=Q.front^.next;
dispose(p);
end;
end;
函数
Clear(Q)
功能
使队列Q成为空队列。
实现
Procere
clear(var
Q:linkedquetp);
begin
Q.rear:=Q.front;
while
Q.front<>nil
do
begin
Q.front:=Q.front^.next;
dispose(Q.rear);
Q.rear:=Q.front;
end;
new(Q.front);
Q.front^.next:=nil;
Q.rear:=Q.front;
end;
循环队列:
我们可以将队列当作一般的表用数组实现，但这样做的效果并不好。尽管我们可以用一个游标last来指示队尾，使得Enqueue运算可在O(1)时间内完成，但是在执行Dequeue时，为了删除队头元素，必须将数组中其他所有元素都向前移动一个位置。这样，当队列中有n个元素时，执行Dequeue就需要O(n)时间。为了提高运算的效率，我们用另一种方法来表达数组中各单元的位置关系。设想数组中的单元不是排成一行，而是围成一个圆环
，我们将队列中从队头到队尾的元素按顺时针方向存放在循环数组中一段连续的单元中。当需要将新元素入队时，可将队尾游标Q.rear按顺时针方向移一位，并在新的队尾游标指示的单元中存入新元素。出队操作也很简单，只要将队头游标Q.front依顺时针方向移一位即可。容易看出，用循环数组来实现队列可以在O(1)时间内完成Enqueue和Dequeue运算。执行一系列的入队与出队运算，将使整个队列在循环数组中按顺时针方向移动。通常，用队尾游标Q.rear指向队尾元素所在的单元，用队头游标Q.front指向队头元素所在单元的前一个单元，并且约定只能存放maxsize-1个元素如图3所示。
图3
此时队列的定义如下:
const
m=maxsize-1
type
cyclicquetp=record
elem:array[0..m]
of
elemtp;
rear,front:0..m;
end;
var
sq:cyclicquetp;
这时
当
sq.rear=sq.front
时队空
当
(sq.rear+1)
mod
maxsize=sq.front
时队满
先
sq.rear=(
sq.rear+1)
mod
maxsize
后进队
先
sq.front=(sq.front+1)mod
maxsize
后出队
队列中元素的个数(sq.rear-sq.front+maxsize)
mod
maxsize
J. 求八数码问题算法，并说明下该算法优缺点，要算法，不是源代码（可以没有）。
八数码问题
一.八数码问题
八数码问题也称为九宫问题。在3×3的棋盘，摆有八个棋子，每个棋子上标有1至8的某一数字，不同棋子上标的数字不相同。棋盘上还有一个空格，与空格相邻的棋子可以移到空格中。要求解决的问题是：给出一个初始状态和一个目标状态，找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。所谓问题的一个状态就是棋子在棋盘上的一种摆法。棋子移动后，状态就会发生改变。解八数码问题实际上就是找出从初始状态到达目标状态所经过的一系列中间过渡状态。
八数码问题一般使用搜索法来解。搜索法有广度优先搜索法、深度优先搜索法、A*算法等。这里通过用不同方法解八数码问题来比较一下不同搜索法的效果。
二.搜索算法基类
1.八数码问题的状态表示
八数码问题的一个状态就是八个数字在棋盘上的一种放法。每个棋子用它上面所标的数字表示，并用0表示空格，这样就可以将棋盘上棋子的一个状态存储在一个一维数组p[9]中，存储的顺序是从左上角开始，自左至右，从上到下。也可以用一个二维数组来存放。
2.结点
搜索算法中，问题的状态用结点描述。结点中除了描述状态的数组p[9]外，还有一个父结点指针last，它记录了当前结点的父结点编号，如果一个结点v是从结点u经状态变化而产生的，则结点u就是结点v的父结点，结点v的last记录的就是结点u的编号。在到达目标结点后，通过last 可以找出搜索的路径。
3.类的结构
在C++中用类来表示结点，类将结点有关的数据操作封装在一起。
不同的搜索算法具有一定共性，也有各自的个性，因此这里将不同搜索算法的共有的数据和功能封装在一个基类中，再通过继承方式实现不同的搜索算法。
4.结点扩展规则
搜索就是按照一定规则扩展已知结点，直到找到目标结点或所有结点都不能扩展为止。
八数码问题的结点扩展应当遵守棋子的移动规则。按照棋子移动的规则，每一次可以将一个与空格相邻棋子移动到空格中，实际上可以看作是空格作相反移动。空格移动的方向可以是右、下、左、上，当然不能移出边界。棋子的位置，也就是保存状态的数组元素的下标。空格移动后，它的位置发生变化，在不移出界时，空格向右、下、左和上移动后，新位置是原位置分别加上1、3、-1、-3，如果将空格向右、下、左和上移动分别用0、1、2、3表示，并将-3、3、-1、1放在静态数组d[4]中，空格位置用spac表示，那么空格向方向i移动后，它的位置变为spac+d[i]。空格移动所产生的状态变化，反映出来则是将数组p[]中，0的新位置处的数与0交换位置。
5.八数码问题的基类
八数码问题的基类及其成员函数的实现如下：
#define Num 9
class TEight
{
public:
TEight(){}
TEight(char *fname); //用文件数据构造节点
virtual void Search()=0; //搜索
protected:
int p[Num];
int last,spac;
static int q[Num],d[],total;
void Printf();
bool operator==(const TEight &T);
bool Extend(int i);
};
int TEight::q[Num];//储存目标节点
int TEight::d[]={1,3,-1,-3};//方向
int TEight::total=0;//步数
TEight::TEight(char *fname)
{
ifstream fin;
fin.open(fname,ios::in);
if(!fin)
{
cout<<"不能打开数据文件!"<<endl;
return;
}
int i;
for(i=0;i<Num;)//得到源节点
fin>>p[i++];
fin>>spac;
for(i=0;i<Num;)//得到目标节点
fin>>q[i++];
fin.close();
last=-1;
total=0;
}
void TEight::Printf()//把路径打印到结果文件
{
ofstream fout;
fout.open("eight_result.txt",ios::ate|ios::app);
fout<<total++<<"t";
for(int i=0;i<Num;)
fout<<" "<<p[i++];
fout<<endl;
fout.close();
}
bool TEight::operator==(const TEight &T)//判断两个状态是否相同
{
for(int i=0;i<Num;)
if(T.p[i]!=p[i++])
return 0;
return 1;
}
bool TEight::Extend(int i)//扩展
{
if(i==0 && spac%3==2 || i==1 && spac>5
|| i==2 && spac%3==0 || i==3 && spac<3)
return 0;
int temp=spac;
spac+=d[i];
p[temp]=p[spac];
p[spac]=0;
return 1;
}
数据文件的结构：
一共三行，第一行是用空格隔开的九个数字0~8，这是初始状态。第二行是一个数字，空格（数字0）的位置，第三行也是用空格隔开的九个数字0~8，这是目标状态。
三.线性表
搜索法在搜索过程中，需要使用一个队列存储搜索的中间结点，为了在找到目标结点后，能够找到从初始结点到目标结点的路径，需要保留所有搜索过的结点。另一方面，不同问题甚至同一问题的不同搜索方法中，需要存储的结点数量相差很大，所以这里采用链式线性表作为存储结构，同时，为适应不同问题，线性表设计成类模板形式。
template<class Type> class TList; //线性表前视定义
template<class Type> class TNode //线性表结点类模板
{
friend class TList<Type>;
public:
TNode(){}
TNode(const Type& dat);
private:
TNode<Type>* Next;
Type Data;
};
template<class Type> class TList
{
public:
TList(){Last=First=0;Length=0;} //构造函数
int Getlen()const{return Length;} //成员函数，返回线性表长度
int Append(const Type& T); //成员函数，从表尾加入结点
int Insert(const Type& T,int k); //成员函数，插入结点
Type GetData(int i); //成员函数，返回结点数据成员
void SetData(const Type& T,int k); //成员函数，设置结点数据成员
private:
TNode<Type> *First,*Last; //数据成员，线性表首、尾指针
int Length; //数据成员，线性表长度
};
template<class Type> int TList<Type>::Append(const Type& T)
{
Insert(T,Length);
return 1;
}
template<class Type> int TList<Type>::Insert(const Type& T,int k)
{
TNode<Type> *p=new TNode<Type>;
p->Data=T;
if(First)
{
if(k<=0)
{
p->Next=First;
First=p;
}
if(k>Length-1)
{
Last->Next=p;
Last=Last->Next;
Last->Next=0;
}
if(k>0 && k<Length)
{
k--;
TNode<Type> *q=First;
while(k-->0)
q=q->Next;
p->Next=q->Next;
q->Next=p;
}
}
else
{
First=Last=p;
First->Next=Last->Next=0;
}
Length++;
return 1;
}
template<class Type> Type TList<Type>::GetData(int k)
{
TNode<Type> *p=First;
while(k-->0)
p=p->Next;
return p->Data;
}
template<class Type> void TList<Type>::SetData(const Type& T,int k)
{
TNode<Type> *p=First;
while(k-->0)
p=p->Next;
p->Data=T;
}
线性表单独以头文件形式存放。
四.广度优先搜索法
在搜索法中，广度优先搜索法是寻找最短路经的首选。
1.广度优先搜索算法的基本步骤
1）建立一个队列，将初始结点入队，并设置队列头和尾指针
2）取出队列头（头指针所指）的结点进行扩展，从它扩展出子结点，并将这些结点按扩展的顺序加入队列。
3）如果扩展出的新结点与队列中的结点重复，则抛弃新结点，跳至第六步。
4）如果扩展出的新结点与队列中的结点不重复，则记录其父结点，并将它加入队列，更新队列尾指针。
5）如果扩展出的结点是目标结点，则输出路径，程序结束。否则继续下一步。
6）如果队列头的结点还可以扩展，直接返回第二步。否则将队列头指针指向下一结点，再返回第二步。
2.搜索路径的输出
搜索到目标结点后，需要输出搜索的路径。每个结点有一个数据域last，它记录了结点的父结点，因此输出搜索路径时，就是从目标结点Q出发，根据last找到它的父结点，再根据这个结点的last找到它的父结点，....,最后找到初始结点。搜索的路径就是从初始结点循相反方向到达目标结点的路径。
3.广度优先搜索法TBFS类的结构
广度优先搜索法TBFS类是作为TEight类的一个子类。其类的结构和成员函数的实现如下：
class TBFS:public TEight
{
public:
TBFS(){}
TBFS(char *fname):TEight(fname){}
virtual void Search();
private:
void Printl(TList<TBFS> &L);
int Repeat(TList<TBFS> &L);
int Find();
};
void TBFS::Printl(TList<TBFS> &L)
{
TBFS T=*this;
if(T.last==-1)
return;
else
{
T=L.GetData(T.last);
T.Printl(L);
T.Printf();
}
}
int TBFS::Repeat(TList<TBFS> &L)
{
int n=L.Getlen();
int i;
for(i=0;i<n;i++)
if(L.GetData(i)==*this)
break;
return i;
}
int TBFS::Find()
{
for(int i=0;i<Num;)
if(p[i]!=q[i++])
return 0;
return 1;
}
void TBFS::Search()
{
TBFS T=*this;
TList<TBFS> L;
L.Append(T);
int head=0,tail=0;
while(head<=tail)
{
for(int i=0;i<4;i++)
{
T=L.GetData(head);
if(T.Extend(i) && T.Repeat(L)>tail)
{
T.last=head;
L.Append(T);
tail++;
}
if(T.Find())
{
T.Printl(L);
T.Printf();
return;
}
}
head++;
}
}
4.广度优先搜索法的缺点
广度优先搜索法在有解的情形总能保证搜索到最短路经，也就是移动最少步数的路径。但广度优先搜索法的最大问题在于搜索的结点数量太多，因为在广度优先搜索法中，每一个可能扩展出的结点都是搜索的对象。随着结点在搜索树上的深度增大，搜索的结点数会很快增长，并以指数形式扩张，从而所需的存储空间和搜索花费的时间也会成倍增长。
五、A*算法
1.启发式搜索
广度优先搜索和双向广度优先搜索都属于盲目搜索，这在状态空间不大的情况下是很合适的算法，可是当状态空间十分庞大时，它们的效率实在太低，往往都是在搜索了大量无关的状态结点后才碰到解答，甚至更本不能碰到解答。
搜索是一种试探性的查寻过程，为了减少搜索的盲目性引，增加试探的准确性，就要采用启发式搜索了。所谓启发式搜索就是在搜索中要对每一个搜索的位置进行评估，从中选择最好、可能容易到达目标的位置，再从这个位置向前进行搜索，这样就可以在搜索中省略大量无关的结点，提高了效率。
2.A*算法
A*算法是一种常用的启发式搜索算法。
在A*算法中，一个结点位置的好坏用估价函数来对它进行评估。A*算法的估价函数可表示为：
f'(n) = g'(n) + h'(n)
这里，f'(n)是估价函数，g'(n)是起点到终点的最短路径值（也称为最小耗费或最小代价），h'(n)是n到目标的最短路经的启发值。由于这个f'(n)其实是无法预先知道的，所以实际上使用的是下面的估价函数：
f(n) = g(n) + h(n)
其中g(n)是从初始结点到节点n的实际代价，h(n)是从结点n到目标结点的最佳路径的估计代价。在这里主要是h(n)体现了搜索的启发信息，因为g(n)是已知的。用f(n)作为f'(n)的近似，也就是用g(n)代替g'(n)，h(n)代替h'(n)。这样必须满足两个条件：（1）g(n)>=g'(n)（大多数情况下都是满足的，可以不用考虑），且f必须保持单调递增。（2）h必须小于等于实际的从当前节点到达目标节点的最小耗费h(n)<=h'(n)。第二点特别的重要。可以证明应用这样的估价函数是可以找到最短路径的。
3.A*算法的步骤
A*算法基本上与广度优先算法相同，但是在扩展出一个结点后，要计算它的估价函数，并根据估价函数对待扩展的结点排序，从而保证每次扩展的结点都是估价函数最小的结点。
A*算法的步骤如下：
1）建立一个队列，计算初始结点的估价函数f，并将初始结点入队，设置队列头和尾指针。
2）取出队列头（队列头指针所指）的结点，如果该结点是目标结点，则输出路径，程序结束。否则对结点进行扩展。
3）检查扩展出的新结点是否与队列中的结点重复，若与不能再扩展的结点重复（位于队列头指针之前），则将它抛弃；若新结点与待扩展的结点重复（位于队列头指针之后），则比较两个结点的估价函数中g的大小，保留较小g值的结点。跳至第五步。
4）如果扩展出的新结点与队列中的结点不重复，则按照它的估价函数f大小将它插入队列中的头结点后待扩展结点的适当位置，使它们按从小到大的顺序排列，最后更新队列尾指针。
5）如果队列头的结点还可以扩展，直接返回第二步。否则将队列头指针指向下一结点，再返回第二步。
4.八数码问题的A*算法的估价函数
估价函数中，主要是计算h，对于不同的问题，h有不同的含义。那么在八数码问题中，h的含意是各什么？八数码问题的一个状态实际上是数字0~8的一个排列，用一个数组p[9]来存储它，数组中每个元素的下标，就是该数在排列中的位置。例如，在一个状态中，p[3]=7，则数字7的位置是3。如果目标状态数字3的位置是8，那么数字7对目标状态的偏移距离就是3，因为它要移动3步才可以回到目标状态的位置。
八数码问题中，每个数字可以有9个不同的位置，因此，在任意状态中的每个数字和目标状态中同一数字的相对距离就有9*9种，可以先将这些相对距离算出来，用一个矩阵存储，这样只要知道两个状态中同一个数字的位置，就可查出它们的相对距离，也就是该数字的偏移距离：
0 1 2 3 4 5 6 7 8
0 0 1 2 1 2 3 2 3 4
1 1 0 1 2 1 2 3 2 3
2 2 1 0 3 2 1 4 3 2
3 1 2 3 0 1 2 1 2 3
4 2 1 2 1 0 1 2 1 2
5 3 2 1 2 1 0 3 2 1
6 2 3 4 1 2 3 0 1 2
7 3 2 3 2 1 2 1 0 1
8 4 3 2 3 2 1 2 1 0
例如在一个状态中，数字8的位置是3，在另一状态中位置是7，那么从矩阵的3行7列可找到2，它就是8在两个状态中的偏移距离。
估价函数中的h就是全体数字偏移距离之和。显然，要计算两个不同状态中同一数字的偏移距离，需要知道该数字在每个状态中的位置，这就要对数组p[9]进行扫描。由于状态发生变化，个数字的位置也要变化，所以每次计算h都沿线扫描数组，以确定每个数字在数组中的位置。为了简化计算，这里用一个数组存储状态中各个数字的位置，并让它在状态改变时随着变化，这样就不必在每次计算h时，再去扫描状态数组。
例如，某个状态中，数字5的位置是8，如果用数组r[9]存储位置，那么就有r[5]=8。
现在用数组r[9]存储当前状态的数字位置，而用s[9]存储目标状态的数字位置，那么当前状态数字i对目标状态的偏移距离就是矩阵中r[i]行s[i]列对应的值。
5.A*算法的类结构
A*算法的类声明如下：
class TAstar:public TEight
{
public:
TAstar(){} //构造函数
TAstar(char *fname); //带参数构造函数
virtual void Search(); //A*搜索法
private:
int f,g,h; //估价函数
int r[Num]; //存储状态中各个数字位置的辅助数组
static int s[Num]; //存储目标状态中各个数字位置的辅助数组
static int e[]; //存储各个数字相对距离的辅助数组
void Printl(TList<TAstar> L); //成员函数，输出搜索路径
int Expend(int i); //成员函数，A*算法的状态扩展函数
int Calcuf(); //成员函数，计算估价函数
void Sort(TList<TAstar>& L,int k); //成员函数，将新扩展结点按f从小到大顺序插入待扩展结点队列
int Repeat(TList<TAstar> &L); //成员函数，检查结点是否重复
};
int TAstar::s[Num],TAstar::e[Num*Num];
TAstar::TAstar(char *fname):TEight(fname)
{
for(int i=0;i<Num;)
{
r[p[i]]=i; //存储初始状态个个数字的位置
s[q[i]]=i++; //存储目标状态个个数字的位置
}
ifstream fin;
fin.open("eight_dis.txt",ios::in); //打开数据文件
if(!fin)
{
cout<<"不能打开数据文件!"<<endl;
return;
}
for(int i=0;i<Num*Num;i++) //读入各个数字相对距离值
fin>>e[i];
fin.close();
f=g=h=0; //估价函数初始值
}
void TAstar::Printl(TList<TAstar> L)
{
TAstar T=*this;
if(T.last==-1) return;
else
{
T=L.GetData(T.last);
T.Printl(L);
T.Printf();
}
}
int TAstar::Expend(int i)
{
if(Extend(i)) //结点可扩展
{
int temp=r[p[r[0]]]; //改变状态后数字位置变化，存储改变后的位置
r[p[r[0]]]=r[0];
r[0]=temp;
return 1;
}
return 0;
}
int TAstar::Calcuf()
{
h=0;
for(int i=0;i<Num;i++) //计算估价函数的 h
h+=e[Num*r[i]+s[i]];
return ++g+h;
}
void TAstar::Sort(TList<TAstar>& L,int k)
{
int n=L.Getlen();
int i;
for(i=k+1;i<n;i++)
{
TAstar T=L.GetData(i);
if(this->f<=T.f)
break;
}
L.Insert(*this,i);
}
int TAstar::Repeat(TList<TAstar> &L)
{
int n=L.Getlen();
int i;
for(i=0;i<n;i++)
if(L.GetData(i)==*this)
break;
return i;
}
void TAstar::Search()
{
TAstar T=*this; //初始结点
T.f=T.Calcuf(); //初始结点的估价函数
TList<TAstar> L; //建立队列
L.Append(T); //初始结点入队
int head=0,tail=0; //队列头和尾指针
while(head<=tail) //队列不空则循环
{
for(int i=0;i<4;i++) //空格可能移动方向
{
T=L.GetData(head); //去队列头结点
if(T.h==0) //是目标结点
{
T.Printl(L);//输出搜索路径
T.Printf(); //输出目标状态
return; //结束
}
if(T.Expend(i)) //若结点可扩展
{
int k=T.Repeat(L); //返回与已扩展结点重复的序号
if(k<head) //如果是不能扩展的结点
continue; //丢弃
T.last=head; //不是不能扩展的结点，记录父结点
T.f=T.Calcuf(); //计算f
if(k<=tail) //新结点与可扩展结点重复
{
TAstar Temp=L.GetData(k);
if(Temp.g>T.g) //比较两结点g值
L.SetData(T,k); //保留g值小的
continue;
}
T.Sort(L,head) ; //新结点插入可扩展结点队列
tail++; //队列尾指针后移
}
}
head++; //一个结点不能再扩展，队列头指针指向下一结点
}
}
六、测试程序
A*算法的测试：
int main()
{
TAstar aStar("eight.txt");
aStar.Search();
system("pauze");
return 0;
}
eight.txt文件中的数据（初始态和目标态）：
一共三行，第一行是用空格隔开的九个数字0~8，这是初始状态。第二行是一个数字，空格（数字0）的位置，第三行也是用空格隔开的九个数字0~8，这是目标状态。
8 3 5 1 2 7 4 6 0
8
1 2 3 4 5 6 7 8 0
eight_dis.txt中的数据（估计函数使用）
0 1 2 1 2 3 2 3 4
1 0 1 2 1 2 3 2 3
2 1 0 3 2 1 4 3 2
1 2 3 0 1 2 1 2 3
2 1 2 1 0 1 2 1 2
3 2 1 2 1 0 3 2 1
2 3 4 1 2 3 0 1 2
3 2 3 2 1 2 1 0 1
4 3 2 3 2 1 2 1 0
eight_Result.txt中的结果（运行后得到的结果）
七、算法运行结果
1.BFS算法只能适用于到达目标结点步数较少的情况，如果步数超过15步，运行时间太长，实际上不再起作用。
2.对于随机生成的同一个可解状态，BFS算法最慢，DBFS算法较慢，A*算法较快。但在15步以内，DBFS算法与A*算法相差时间不大，超过15步后，随步数增加，A*算法的优势就逐渐明显，A*算法要比DBFS算法快5倍以上，并随步数增大而增大。到25步以上，DBFS同样因运行时间过长而失去价值。
3.一般来说，解答的移动步数每增加1，程序运行时间就要增加5倍以上。由于八数码问题本身的特点，需要检查的节点随步数增大呈指数形式增加，即使用A*算法，也难解决移动步数更多的问题。
八、问题可解性
八数码问题的一个状态实际上是0~9的一个排列，对于任意给定的初始状态和目标，不一定有解，也就是说从初始状态不一定能到达目标状态。因为排列有奇排列和偶排列两类，从奇排列不能转化成偶排列或相反。
如果一个数字0~8的随机排列871526340，用F(X)表示数字X前面比它小的数的个数，全部数字的F(X)之和为Y=∑(F(X))，如果Y为奇数则称原数字的排列是奇排列，如果Y为偶数则称原数字的排列是偶排列。
例如871526340这个排列的
Y=0+0+0+1+1+3+2+3+0=10
10是偶数，所以他偶排列。871625340
Y=0+0+0+1+1+2+2+3+0=9
9是奇数，所以他奇排列。
因此，可以在运行程序前检查初始状态和目标状态的窘是否相同，相同则问题可解，应当能搜索到路径。否则无解。
PS:整理自网络