隊列矩陣存儲
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:整理自網路