北郵數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)二-棧和隊(duì)列

1、數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱： 實(shí)驗(yàn)二棧和隊(duì)列學(xué)生姓名：班 級(jí)：班內(nèi)序號(hào)：學(xué) 號(hào)：日 期：1實(shí)驗(yàn)要求實(shí)驗(yàn)內(nèi)容：1、 進(jìn)一步掌握指針、模板類、異常處理的使用2、 掌握棧的操作的實(shí)現(xiàn)方法3、 掌握隊(duì)列的操作的實(shí)現(xiàn)方法4、 學(xué)習(xí)使用棧解決實(shí)際問(wèn)題的能力5、 學(xué)習(xí)使用隊(duì)列解決實(shí)際問(wèn)題的能力實(shí)驗(yàn)內(nèi)容：利用棧結(jié)構(gòu)實(shí)現(xiàn)八皇后問(wèn)題。問(wèn)題介紹：八皇后問(wèn)題19世紀(jì)著名的數(shù)學(xué)家高斯于1850年提出的。他的問(wèn)題是：在8*8的棋盤(pán)上放置8個(gè)皇后，使其不能互相攻擊，即任意兩個(gè)皇后都不能處于同一行、同一列、同一斜線上。請(qǐng)?jiān)O(shè)計(jì)算法打印所有可能的擺放方法。提示：1、可以使用遞歸或非遞歸兩種方法實(shí)現(xiàn)2、實(shí)現(xiàn)一個(gè)關(guān)鍵算法：判斷任意兩個(gè)

2、皇后是否在同一行、同一列和同一斜線上。2程序分析：程序源代碼為：#include "stdafx.h"#include<iostream>#include<cmath>using namespace std;int p=0;class Queenpublic:數(shù)int Check(int i,int k);/判斷位置是否符合要求 void putQueens(int k,int n);/遞歸調(diào)用函數(shù)，排列皇后 Queen()int s=0; void Print(int n);/輸出皇后的排列，n為行數(shù)，輸出數(shù)字為第n行中皇后位置的列private:

3、int a8; int s; ;void main() Queen Q;int n=8; cout<<"從左到右，從上到下依次為第一行到第八行排列"<<endl; cout<<"Queen的排列位置是:"<<endl; Q.putQueens(1,n); cout<<"共有 "<<p<<" 種排列方法"<<endl;void Queen:putQueens(int k,int n)/計(jì)算出皇后的排列，k是當(dāng)前皇后數(shù)量，n

4、是數(shù)量上限 int i;置void Queen:Print(int n)cout<<"第"<<p+1<<"種排列方式是："<<endl;int i; putQueens(k+1,n); /調(diào)用遞歸函數(shù)，放置下一行皇后 if(k>n)/如果達(dá)到要求的皇后數(shù)量，則輸出皇后排列順序 Print(n); else /否則在該行中某位置添加一個(gè)皇后 for(i=1;i<=n;i+) if(Check(i,k) /判斷該行中該位置放置能否放置皇后 ak=i; /若可以添加，則記錄該行中該點(diǎn)的位置，作為排列皇

5、后的位示for(i=1;i<=n;i+) for(int p=1;p<=8;p+) if(p=ai) cout<<"Q "/在有“皇后”的位置，用大寫(xiě)字母“Q”標(biāo)記表示 else cout<<"0 "cout<<" "/在沒(méi)有“皇后”的位置，用數(shù)字“0”標(biāo)記表 if(i%4=0)/經(jīng)過(guò)調(diào)試能看到當(dāng)每行只有棋盤(pán)上一行排列時(shí)，屏幕大小不夠輸出所有排列，故而棋盤(pán)上的每四行輸出在屏幕上一行，棋盤(pán)上各行用空格隔開(kāi)int Queen:Check(int i,int k)int j; j=1; whi

6、le(j<k) if(aj=i) | abs(aj-i)=abs(j-k) /判斷列上是否有重復(fù)皇后|利用絕 cout<<endl; p+; 對(duì)值判斷對(duì)角線上是否有皇后return 0; /不符合上述條件則返回0 j+; return 1; /符合條件，保證在同列、同對(duì)角線上沒(méi)有重復(fù)皇后則返回12.1存儲(chǔ)結(jié)構(gòu)：棧（利用遞歸函數(shù)）2.2 關(guān)鍵算法分析基本思路：利用遞歸函數(shù)，實(shí)現(xiàn)不同行之間的遞歸調(diào)用，實(shí)現(xiàn)八皇后問(wèn)題?！緜未a】1、 令k=1，皇后數(shù)目n=8；2、 判斷k是否大于n3.1 是：打印出可以實(shí)現(xiàn)的排列方案3.2 否：循環(huán)行位置1判斷該位置是否符合要求，若符合記錄ak的縱

7、坐標(biāo)值k+1 重復(fù)上述步驟?！娟P(guān)鍵算法】1.遞歸函數(shù)putQueensvoid Queen:putQueens(int k,int n)/計(jì)算出皇后的排列，k是當(dāng)前皇后數(shù)量，n是數(shù)量上限 int i;置解析過(guò)程：先要判斷k是否已經(jīng)達(dá)到8，判斷方法是看整數(shù)k+1是否超過(guò)n=8，若沒(méi)有超過(guò)，則每次對(duì)于函數(shù)中的第k行，都從第k行第i=1個(gè)位置開(kāi)始判斷能否添加皇后。若不符合放置條件，則令位置i自增1，并且繼續(xù)循環(huán)；若第i個(gè)位置符合放置皇后的條件，即為（Check（i，k）=1），那么則讓數(shù)組a中的ak元素等于i，相當(dāng)于在二維棋盤(pán)上的第k行中第i個(gè)元素標(biāo)記為Q，則第k行的皇后位置已經(jīng)確定，令k自增1，重

8、新調(diào)用putQueens函數(shù)，層層遞歸調(diào)用，直至能使得k=n=8，則停止調(diào)用putQueens函數(shù)，輸出排列結(jié)果。 其時(shí)間復(fù)雜度為O(n*n).2.判斷位置能否放置皇后int Queen:Check(int i,int k) putQueens(k+1,n); /調(diào)用遞歸函數(shù)，放置下一行皇后 if(k>n)/如果達(dá)到要求的皇后數(shù)量，則輸出皇后排列順序 Print(n); else /否則在該行中某位置添加一個(gè)皇后 for(i=1;i<=n;i+) if(Check(i,k) /判斷該行中該位置放置能否放置皇后 ak=i; /若可以添加，則記錄該行中該點(diǎn)的位置，作為排列皇后的位 in

9、t j;j=1; while(j<k) if(aj=i) | abs(aj-i)=abs(j-k) /判斷列上是否有重復(fù)皇后|利用絕對(duì)值判斷對(duì)角線上是否有皇后return 0; /不符合上述條件則返回0j+;解析過(guò)程：利用while對(duì)數(shù)字j循環(huán)，判斷能否放入皇后。若aj也等于I,即為棋盤(pán)上第j行第i個(gè)元素被標(biāo)記為Q，那么則不能在這個(gè)位置放入皇后，return 值為0；如果循環(huán)中aj-i等于j-k的絕對(duì)值，即對(duì)應(yīng)棋盤(pán)上某一行放置Q元素的縱坐標(biāo)數(shù)減去該位置的縱坐標(biāo)數(shù)，絕對(duì)值和行數(shù)j與行數(shù)k的差的絕對(duì)值相等，那么顯然不能符合對(duì)角線不多于一個(gè)皇后的條件，也會(huì)return 0。只有在上面兩個(gè)條件都

10、符合的情況下，才會(huì)return 1，保證任意一個(gè)縱列，任意一個(gè)任意對(duì)角線不出現(xiàn)兩個(gè)皇后。3.輸出棋盤(pán)：void Queen:Print(int n)cout<<"第"<<p+1<<"種排列方式是："<<endl;示if(i%4=0)/經(jīng)過(guò)調(diào)試能看到當(dāng)每行只有棋盤(pán)上一行排列時(shí)，屏幕大小不夠輸int i; for(i=1;i<=n;i+) for(int p=1;p<=8;p+) if(p=ai) cout<<"Q "/在有“皇后”的位置，用大寫(xiě)字母“Q”標(biāo)記表示 r

11、eturn 1; /符合條件，保證在同列、同對(duì)角線上沒(méi)有重復(fù)皇后則返回1 else cout<<"0 "cout<<" "/在沒(méi)有“皇后”的位置，用數(shù)字“0”標(biāo)記表出所有排列，故而棋盤(pán)上的每四行輸出在屏幕上一行，棋盤(pán)上各行用空格隔開(kāi)解析過(guò)程：通過(guò)循環(huán)實(shí)現(xiàn)輸出棋盤(pán)。通過(guò)遞歸調(diào)用，已經(jīng)確定了某一個(gè)可行棋盤(pán)對(duì)應(yīng)的數(shù)組a8.其中的每一個(gè)元素ak,代表對(duì)應(yīng)棋盤(pán)上第k行的皇后的縱坐標(biāo)為ak。那么我們可以這 cout<<endl; p+;樣寫(xiě)出一個(gè)函數(shù)：令整型變量p=0。在每一個(gè)k下，p每次循環(huán)自增，當(dāng)p=ak時(shí)，輸出字母Q，代表皇

12、后的位置。而p不等于ak時(shí)，表明棋盤(pán)上該位置沒(méi)有皇后，則輸出空格。再通過(guò)k的自增從而實(shí)現(xiàn)該可行排列下所有行的輸出。3. 程序運(yùn)行結(jié)果(1) 測(cè)試主函數(shù)流程(2) 測(cè)試條件n取值大于0小于10本題中由于已經(jīng)確定是八皇后問(wèn)題，故而在main函數(shù)里面直接將n定義為8.(3)測(cè)試結(jié)果4. 總結(jié)（1）調(diào)試時(shí)出現(xiàn)的問(wèn)題及解決的方法很明顯使用VS2010，不能在一行輸出棋盤(pán)上一行的條件下把92種情形全部打印出來(lái)，否則前面的幾十種情況將無(wú)法顯示出，。為了彌補(bǔ)這個(gè)問(wèn)題，我將棋盤(pán)橫向打印，使得屏幕上一行打印出棋盤(pán)上四行，這個(gè)需要一些語(yǔ)句的控制才能實(shí)現(xiàn)。但是即使這樣，最后效果不如按照8*8打印出來(lái)的直觀漂亮。（2）需要總結(jié)：通過(guò)本