第一篇：數(shù)據(jù)結(jié)構(gòu)八皇后問題實(shí)習(xí)報(bào)告（寫寫幫整理）

數(shù)據(jù)結(jié)構(gòu) 實(shí)習(xí)報(bào)告

專業(yè)：數(shù)字媒體技術(shù) 姓名：李義 年級(jí)：2013級(jí)

學(xué)號(hào)：201301052015 完成日期：2015.12.31

題目：八皇后問題

一、項(xiàng)目簡介

八皇后問題是一個(gè)古老而著名的問題，是回溯算法的典型例題。該問題是十九世紀(jì)著名的數(shù)學(xué)家高斯1850年提出：在8?8格的國際象棋棋盤上，安放八個(gè)皇后，要求沒有一個(gè)皇后能夠“吃掉”任何其他一個(gè)皇后，即任意兩個(gè)皇后都不能處于同一行、同一列或同一條對角線上，求解有多少種擺法。

高斯認(rèn)為有76種方案。1854年在柏林的象棋雜志上不同的作者發(fā)表了40種不同的解，后來有人用圖論的方法得出結(jié)論，有92種擺法。

二、概要設(shè)計(jì)

2.1 主要模塊：

這個(gè)程序主要由4個(gè)模塊組成，分別是畫棋盤模塊，畫皇后模塊，輸出皇后擺法模塊，和解決如何擺置皇后模塊。這4個(gè)模塊隸屬于主函數(shù)模塊。既主函數(shù)通過對這4個(gè)模塊的合理調(diào)用解決“8皇后問題”，同時(shí)這4個(gè)模塊之間也互有調(diào)用。

2.2 程序設(shè)計(jì)的數(shù)據(jù)結(jié)構(gòu)及其關(guān)系：

數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)：數(shù)組a[i]：a [i]表示第i個(gè)皇后放置的列；i的范圍：1-8;對角線數(shù)組：b[j](主對角線),c[j]（從對角線），根據(jù)程序的運(yùn)行，去決定主從對角線是否放入皇后；然后進(jìn)行數(shù)據(jù)的初始化。從n列開始擺放第n個(gè)皇后（因?yàn)檫@樣便可以符合每一豎列一個(gè)皇后的要求），先測試當(dāng)前位置(n,m)是否等于０（未被占領(lǐng)）:如果是，擺放第n個(gè)皇后，并宣布占領(lǐng)(切記要橫列豎列斜列一起來)，接著進(jìn)行遞歸；如果不是，測試下一個(gè)位置(n,m+1)，但是如果當(dāng)時(shí)，卻發(fā)現(xiàn)此時(shí)已經(jīng)無法擺放時(shí)，便要進(jìn)行回溯。

三、詳細(xì)設(shè)計(jì)

3.1 定義相關(guān)的數(shù)據(jù)類型： 3.1.1 定義的相關(guān)數(shù)據(jù)類型： int A[21],B[21],C[21],Y[8];void *buff1,*buff2 3.1.2 設(shè)計(jì)思想：

本程序通過對子函數(shù)void qu(int i)的調(diào)用，將八皇后的問題關(guān)鍵通過數(shù)據(jù)結(jié)構(gòu)的思想予以了實(shí)現(xiàn)。雖然題目以及演算看起來都比較復(fù)雜，繁瑣，但在實(shí)際中，只要當(dāng)一只皇后放入棋盤后，在橫與列、斜線上沒有另外一只皇后與其沖突，再對皇后的定位進(jìn)行相關(guān)的判斷。即可完成。如果在這個(gè)程序中，我們運(yùn)用的是非遞歸的思想，那么將大量使用if等語句，并通過不斷的判斷，去推出答案，而且這種非遞歸的思想，大大的增加了程序的時(shí)間復(fù)雜度。如果我們使用了數(shù)據(jù)結(jié)構(gòu)中的算法后，那么程序的時(shí)間復(fù)雜度，以及相關(guān)的代碼簡化都能取得不錯(cuò)的改進(jìn)。這個(gè)程序，我運(yùn)用到了數(shù)據(jù)結(jié)構(gòu)中的棧、數(shù)組，以及樹和回溯的方法。特別是在對于樹以及二叉樹的學(xué)習(xí)，更是為八皇后的問題提供了科學(xué)的解決方案，通過對樹的分析，把八皇后的問題看成了樹，而在衍生第一個(gè)變化后，上面的第一層八個(gè)變化就變成了八個(gè)結(jié)點(diǎn)，而這八個(gè)結(jié)點(diǎn)再繼續(xù)的衍生??，這樣比較形象的將八皇后的問題簡單化了。然后再通過回溯法進(jìn)行設(shè)計(jì)，回溯法是設(shè)計(jì)遞歸過程的一個(gè)重要的方法。它的求解過程實(shí)質(zhì)上是一個(gè)先序遍歷一棵“狀態(tài)樹“的過程。在這個(gè)程序設(shè)計(jì)中，它先進(jìn)行判斷，棋盤上是否已經(jīng)得到一個(gè)完整的布局（即棋盤是否已經(jīng)擺上8個(gè)棋子），如果是，則輸出布局；如果不是則依次先根遍歷滿足約束條件的各棵子樹，流程即是：

判斷該子樹根的布局是否合法：如果合法的話，則先根遍歷該子樹；如果不合法的話，則剪去該子樹的分支。

3.2 相關(guān)代碼及算法

3.2.1 主模塊C碼算法： void main(void){

Queen Q;

int gdriver=DETECT,gmode;

initgraph(&gdriver,&gmode,“D://Win-TC”);

SetQueen(&Q);

setcolor(YELLOW);

QueenPic();

cleardevice();

setcolor(LIGHTGREEN);

settextstyle(0,0,3);

outtextxy(180,10,“Eight Queens”);

setcolor(WHITE);

settextstyle(0,0,1);

outtextxy(250,400,“2009.11.8 3:30pm”);

QueenRe(&Q,0);

getch();

closegraph();}

3.2.2 棋盤模塊C碼算法

void Checker(void)

/* 畫棋盤函數(shù) */ {

int i,k;

for(k=0;k<8;k++)

for(i=0;i<8;i++)

if(k%2==0&&i%2==0||k%2!=0&&i%2!=0){

setfillstyle(SOLID_FILL,LIGHTBLUE);

setcolor(LIGHTBLUE);

rectangle(i*20,20+k*20,(i+1)*20,20+(k+1)*20);

floodfill(i*20+10,20+k*20+10,LIGHTBLUE);} else {

setfillstyle(SOLID_FILL,WHITE);

setcolor(WHITE);

rectangle(i*20,20+k*20,(i+1)*20,20+(k+1)*20);

floodfill(i*20+10,20+k*20+10,WHITE);} } 3.2.3 皇后模塊C碼算法：

void QueenPic(void)

/* 畫皇后圖象，然后存儲(chǔ)到緩沖區(qū) */ {

int size，polypoints1[10]={9,1,11,1,20,20,1,20,9,1}，polypoints2[10]={29,1,31,1,40,20,21,20,29,1};

setfillstyle(SOLID_FILL,LIGHTBLUE);

/* 畫淡藍(lán)色棋格 */ setcolor(LIGHTBLUE);

rectangle(1,1,20,20);

floodfill(10,10,LIGHTBLUE);

setfillstyle(SOLID_FILL,WHITE);

/* 畫白色棋格 */

setcolor(WHITE);

rectangle(21,1,40,20);

floodfill(30,10,WHITE);

setfillstyle(SOLID_FILL,DARKGRAY);

setcolor(YELLOW);

drawpoly(5,polypoints1);

drawpoly(5,polypoints2);

floodfill(10,10,YELLOW);

floodfill(30,10,YELLOW);

size=imagesize(1,1,20,20);

/* 計(jì)算緩沖區(qū)大小，然后存儲(chǔ) */

buff1=(void *)malloc(size);

buff2=(void *)malloc(size);

getimage(1,1,20,20,buff1);

getimage(21,1,40,20,buff2);

cleardevice();} 3.2.4 八皇后擺放方法模塊C碼:

void QueenRe(Queen *Q, int y)

八皇后的遞歸算法

{int x;

if(y>7)

return;

for(x=0;x<8;x++)

if(!Q->A[x+7]&&!Q->B[x+y+7]&&!Q->C[x-y+7])下一棵要遍歷的子樹由狀態(tài)數(shù)確定

{

Q->Y[y]=x;放置皇后

Q->A[x+7]=1;標(biāo)記下次這里不能放置皇后

Q->B[x+y+7]=1;標(biāo)記下次這里不能放置皇后 Q->C[x-y+7]=1;標(biāo)記下次這里不能放置皇后

if(y==7)

PrintQueen(Q);調(diào)用輸出圖形函數(shù)

QueenRe(Q,y+1);進(jìn)入下一層遞歸

Q->A[x+7]=0;如果上次擺法導(dǎo)致后面不能繼續(xù)擺放則重置標(biāo)記為0

Q->B[x+y+7]=0;

Q->C[x-y+7]=0;

} } 3.2.5 初始化模塊C碼:

void SetQueen(Queen *Q)

/* 初始化 */ {int i;

for(i=0;i<21;i++)

{Q->A[i]=0;Q->B[i]=0;Q->C[i]=0;初始化為0，表示可以放置皇后。} for(i=0;i<8;i++)

Q->Y[i]=-1;}

3.2.6 圖形輸出：

void PrintQueen(Queen *t)

/* 圖形輸出函數(shù) */

{int k;

char str[20];

static total=0;

total++;

setviewport(240,80,400,260,1);

/* 設(shè)置窗口 */

sprintf(str,“NO.%d”,total);

setcolor(GREEN);

settextstyle(0,0,1);

outtextxy(0,0,str);

Checker();

for(k=0;k<8;k++)

if(k%2==0&&t->Y[k]%2==0||k%2!=0&&t->Y[k]%2!=0)

putimage((t->Y[k])*20,20+k*20,buff1,COPY_PUT);else

putimage((t->Y[k])*20,20+k*20,buff2,COPY_PUT);

getch();

if(getch()==27)exit(0);

clearviewport();}

void QueenRe(Queen *Q, int y)

/* 八皇后的遞歸算法 */ {int x;

if(y>7)

return;

for(x=0;x<8;x++)

if(!Q->A[x+7]&&!Q->B[x+y+7]&&!Q->C[x-y+7])/* 下一棵要遍歷的子樹由狀態(tài)數(shù)確定 */

{Q->Y[y]=x;

Q->A[x+7]=1;

Q->B[x+y+7]=1;

Q->C[x-y+7]=1;

if(y==7)

PrintQueen(Q);

QueenRe(Q,y+1);

/* 進(jìn)入下一層遞歸 */

Q->A[x+7]=0;

Q->B[x+y+7]=0;

Q->C[x-y+7]=0;} } } 3.3函數(shù)調(diào)用圖

3.4項(xiàng)目流程圖

通過編譯連接后，程序基本上把八皇后的92種擺法的都進(jìn)行了演示；

但程

四、調(diào)試分析

序運(yùn)行中也出現(xiàn)了以下缺點(diǎn)：

因?yàn)榘嘶屎蟮谋憩F(xiàn)方法甚多，輸出后雖能全部顯示，但未能使屏幕停留，把一個(gè)一個(gè)的將其顯示出來,但是這樣便使得操作步驟太多,也會(huì)造成不必要的麻煩!所以只畫出了第一種和最后一種的輸出結(jié)果，演示如圖所示：

五、設(shè)計(jì)體會(huì)

該程序在調(diào)試的過程中出現(xiàn)了不少的問題！如數(shù)據(jù)溢出等（是自己過于粗心而造成的）。在調(diào)試的過程中出現(xiàn)的一個(gè)最大的問題就是：在運(yùn)行的時(shí)候出現(xiàn)解的個(gè)數(shù)大于自己所預(yù)計(jì)的。經(jīng)過不斷的查看內(nèi)存變量，操作次數(shù)但還是沒有找出問題的所在。終于在晚上十二點(diǎn)的時(shí)候，決定睡覺！但一關(guān)上電腦，躺在床上的時(shí)候，突然想到了一個(gè)問題：經(jīng)過讀了一些資料，知道八皇后問題有12組實(shí)質(zhì)解，92組全解——這說明在這12組實(shí)質(zhì)解中有其中的一組解是比其它的解要特殊一點(diǎn)的：其它的解經(jīng)過等價(jià)的變換之后都會(huì)產(chǎn)生8組等價(jià)的解，只有這個(gè)特殊的解只有4組等價(jià)的解。說不定我的問題就出在這里！我之前也寫了一些有關(guān)的代碼處理這個(gè)問題，但我之前以為這個(gè)特殊的解是一個(gè)完全中心對稱的圖形（每轉(zhuǎn)90度得到的圖形就是它自己本身），所以我的在這里的判斷就出現(xiàn)錯(cuò)誤了！后來經(jīng)過相關(guān)代碼的修改，問題終于解決了，程序正確運(yùn)行。

本課程設(shè)計(jì)本人的目的也是通過用WIN-TC程序設(shè)計(jì)平臺(tái)將一個(gè)８＊８的棋盤上放上８個(gè)皇后，使得每一個(gè)皇后既攻擊不到另外七個(gè)皇后，也不被另外七個(gè)皇后所攻擊的92種結(jié)構(gòu)予以實(shí)現(xiàn)．最終將其問題變得一目了然，更加易懂。

六、用戶使用說明

6.1 程序的使用平臺(tái)：

系統(tǒng)要求：windows2000以上操作系統(tǒng)； 語言開發(fā)平臺(tái)：WIN-TC； 6.2 源代碼分析：

首先對程序中的函數(shù)頭文件進(jìn)行引入，定位；在這個(gè)程序中，與其他C++的程序一樣，都是引入：#include；然后開始定義里面的函數(shù)所需要的數(shù)組，其中，setviewport(240,80,400,260,1);;是對總的棋盤狀態(tài)數(shù)進(jìn)行定位，記錄。接著，進(jìn)入了主函數(shù)，在主函數(shù)中，先對棋盤進(jìn)行初始化，并規(guī)定了在程序輸出時(shí)的情況；然后，對行列，對角線也進(jìn)行了初始化；并在對這些元素初始后，對子函數(shù)進(jìn)行調(diào)用； 進(jìn)入子函數(shù)后，便馬上對皇后放入的位置進(jìn)行判斷，通過語句的判斷，如果沒有沖突的話，則放下皇后，并標(biāo)記，在下一次的時(shí)候，不再放入皇后；并在主從對角線進(jìn)行判斷，標(biāo)記；然后再通過if語句判斷，如果行還沒有遍歷完，進(jìn)入下一行；接著通過放入一個(gè)for語句進(jìn)行分析，如果前次的皇后放置導(dǎo)致后面的放置無論如何都不能滿足要求，則回溯，重置；當(dāng)所有工作完成后，無沖突后，就返回主函數(shù)，并通過編譯后對結(jié)果進(jìn)行展示。

七、附錄

#include #include #include #include #include

void *buff1,*buff2;typedef struct { int A[21],B[21],C[21],Y[8];} Queen;void SetQueen(Queen *Q)

/* 初始化 */ { int i;for(i=0;i<21;i++){ Q->A[i]=0;Q->B[i]=0;Q->C[i]=0;} for(i=0;i<8;i++)Q->Y[i]=-1;} void QueenPic(void)

/* 畫皇后圖象，然后存儲(chǔ)到緩沖區(qū) */ { int size, polypoints1[10]={9,1,11,1,20,20,1,20,9,1}, polypoints2[10]={29,1,31,1,40,20,21,20,29,1};setfillstyle(SOLID_FILL,LIGHTBLUE);

/* 畫淡藍(lán)色棋格 */ setcolor(LIGHTBLUE);rectangle(1,1,20,20);floodfill(10,10,LIGHTBLUE);setfillstyle(SOLID_FILL,WHITE);

/* 畫白色棋格 */ setcolor(WHITE);rectangle(21,1,40,20);floodfill(30,10,WHITE);setfillstyle(SOLID_FILL,DARKGRAY);setcolor(YELLOW);drawpoly(5,polypoints1);drawpoly(5,polypoints2);floodfill(10,10,YELLOW);floodfill(30,10,YELLOW);size=imagesize(1,1,20,20);

/* 計(jì)算緩沖區(qū)大小，然后存儲(chǔ) */ buff1=(void *)malloc(size);buff2=(void *)malloc(size);getimage(1,1,20,20,buff1);getimage(21,1,40,20,buff2);cleardevice();} void Checker(void)

/* 畫棋盤函數(shù) */ { int i,k;

for(k=0;k<8;k++)for(i=0;i<8;i++)if(k%2==0&&i%2==0||k%2!=0&&i%2!=0){ setfillstyle(SOLID_FILL,LIGHTBLUE);setcolor(LIGHTBLUE);rectangle(i*20,20+k*20,(i+1)*20,20+(k+1)*20);floodfill(i*20+10,20+k*20+10,LIGHTBLUE);} else { setfillstyle(SOLID_FILL,WHITE);setcolor(WHITE);rectangle(i*20,20+k*20,(i+1)*20,20+(k+1)*20);floodfill(i*20+10,20+k*20+10,WHITE);} } void PrintQueen(Queen *t)

/* 圖形輸出函數(shù) */ {int k;char str[20];static total=0;total++;setviewport(240,80,400,260,1);

/* 設(shè)置窗口 */ sprintf(str,“NO.%d”,total);setcolor(GREEN);settextstyle(0,0,1);outtextxy(0,0,str);Checker();for(k=0;k<8;k++)if(k%2==0&&t->Y[k]%2==0||k%2!=0&&t->Y[k]%2!=0)putimage((t->Y[k])*20,20+k*20,buff1,COPY_PUT);if(!Q->A[x+7]&&!Q->B[x+y+7]&&!Q->C[x-y+7])/* 下一棵要遍歷的子樹由狀態(tài)數(shù)確定 */ {Q->Y[y]=x;Q->A[x+7]=1;Q->B[x+y+7]=1;Q->C[x-y+7]=1;if(y==7)PrintQueen(Q);QueenRe(Q,y+1);

/* 進(jìn)入下一層遞歸 */ Q->A[x+7]=0;Q->B[x+y+7]=0;Q->C[x-y+7]=0;} }

void main(void){ Queen Q;int gdriver=DETECT,gmode;initgraph(&gdriver,&gmode,“D://Win-TC”);SetQueen(&Q);setcolor(YELLOW);QueenPic();cleardevice();setcolor(LIGHTGREEN);settextstyle(0,0,3);outtextxy(180,10,“Eight Queens”);setcolor(WHITE);settextstyle(0,0,1);outtextxy(250,400,“2009.11.8 3:30pm”);QueenRe(&Q,0);getch();closegraph();}

第二篇：數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告--八皇后（寫寫幫整理）

數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告

1．實(shí)驗(yàn)要求

實(shí)驗(yàn)?zāi)康模豪脳＝Y(jié)構(gòu)實(shí)現(xiàn)八皇后問題

八皇后問題如下：八皇后問題是19世紀(jì)著名的數(shù)學(xué)家高斯于1850年提出的。他的問題是，在8*8的棋盤上放置8個(gè)皇后，使其不能互相攻擊，即任意兩個(gè)皇后都不能處于同一行，同一列，同一斜線上。

實(shí)驗(yàn)內(nèi)容：利用所學(xué)的棧結(jié)構(gòu)用遞歸或非遞歸解決八皇后問題。

2.程序分析

程序使用程序最主要只是在主函數(shù)用了一個(gè)遞歸函數(shù)Queen。

Queen函數(shù)使用了三個(gè)參數(shù)m,flag[][],chess[][]。其中m是行數(shù)，flag[][]是判斷二維數(shù)組何處可以放置皇后，chess[][]是存儲(chǔ)字符串的二維數(shù)組。

主函數(shù)中對Queen函數(shù)中的形參數(shù)組flag[][],chess[][]進(jìn)行初始化，在Queen函數(shù)中再進(jìn)行各種操作。

Queen函數(shù)執(zhí)行代碼，首先行數(shù)m為0，當(dāng)m小于7時(shí)，通過if…else…語句，利用Queen(m+1,f,c)重新執(zhí)行遞歸函數(shù)到下一行。

2.1 存儲(chǔ)結(jié)構(gòu)

存儲(chǔ)結(jié)構(gòu)：數(shù)組存儲(chǔ)。

flag[][]數(shù)組存儲(chǔ)數(shù)字判斷輸出和儲(chǔ)能放置皇后,chess[][]數(shù)組存儲(chǔ)字符串即皇后和非皇后的形狀。

2.2 關(guān)鍵算法分析

1、關(guān)鍵算法： a．

for(i=0;i<8;i++)

for(j=0;j<8;j++)

{

f[i][j]=0;

c[i][j]='*';

說明：對棋盤進(jìn)行初始化 未放置皇后的為“*” b．

for(i=0;i<8;i++)

for(j=0;j<8;j++)

{

c[i][j]=chess[i][j];

f[i][j]=flag[i][j];

} 說明：對c[][]，f[][]進(jìn)行初始化。c．

for(i=0;i<8;i++)

for(j=0;j<8;j++)

{

if(f[i][j]==0 &&(i+j==m+k || m==i || k==j || m-k==i-j))

f[i][j]=-1;

}

c[m][k]='#';

說明：已放置皇后的行、列以及對角線都不能再放置皇后。

已放置皇后的顯示為“#”。d.if(m==7)

{

cout<<“算法的第”<<++count<<“個(gè)解為：”<

for(int i=0;i<8;i++)

{

for(int j=0;j<8;j++)

{

cout<

}

cout<

}

cout<

cout<

return;

}

else Queen(m+1,f,c);

說明：首先判斷是否已執(zhí)行到最后一行

每輸出一個(gè)算法，count計(jì)數(shù)器加1 若沒有執(zhí)行到最后一行，m+1繼續(xù)執(zhí)行Queen函數(shù)

2.3 其他

要求程序在一開始創(chuàng)建一個(gè)統(tǒng)計(jì)算法解個(gè)數(shù)的加法器。

3.程序運(yùn)行結(jié)果

1、測試主函數(shù)流程：流程圖如圖所示

2、測試結(jié)論：輸出解決算法的個(gè)數(shù)及八皇后問題的圖解。

4.總結(jié)

一．問題及解決辦法

1.一開始編的時(shí)候?qū)ν恍校涣幸约巴恍毙胁荒芘呕屎蟮乃惴ú荒軠?zhǔn)確編寫，后來通過畫圖發(fā)現(xiàn)了這三個(gè)情況數(shù)組行標(biāo)和列標(biāo)的特點(diǎn)，從而解決了這個(gè)問題。

2.程序只能輸出從65至99的解，其他解不顯示，后來發(fā)現(xiàn)是因?yàn)榻缑嫣〉脑颉６牡皿w會(huì)

對于剛學(xué)的棧表以及遞歸函數(shù)一定要多用才能熟悉，才能知道實(shí)現(xiàn)的具體細(xì)節(jié)問題。對一些出現(xiàn)的錯(cuò)誤一點(diǎn)要仔細(xì)分析，明白以后就會(huì)掌握的很牢固。對于遞歸函數(shù)一定要充分理解它的意義才能用好它。

在編寫代碼中如果對于一些抽象的算法構(gòu)思感到困難，可以通過畫圖，在紙上先進(jìn)行演算推導(dǎo)出各變量之間的關(guān)系，再進(jìn)行編寫可能會(huì)使問題變得簡單明了一些。三．改進(jìn)

遞歸算法解決八皇后問題比較簡單明了，下次可以嘗試不使用遞歸而用非遞歸編寫算法，這樣可能會(huì)更牢固更好的掌握棧的思想，鞏固已學(xué)的知識(shí)。

第三篇：哈爾濱理工大學(xué)信管專業(yè)數(shù)據(jù)結(jié)構(gòu)課程實(shí)踐報(bào)告之八皇后問題 優(yōu)秀案例

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

學(xué)院：管理學(xué)院班級(jí)：信息 11-2班

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)八皇后問題

一、內(nèi)容

設(shè)計(jì)程序完成如下要求：在8×8的國際象棋棋盤上，放置8個(gè)皇后，使得這8個(gè)棋子不能互相被對方吃掉。

要求：(1)依次輸出各種成功的放置方法。(2)最好能畫出棋盤的圖形形式，并在其上動(dòng)態(tài)地標(biāo)注行走的過程。(3)程序能方便地移植到其他規(guī)格的棋盤上。

八皇后問題是一個(gè)古老而著名的問題，是回溯算法的典型例題。該問題是十九世紀(jì)著名的數(shù)學(xué)家高斯1850年提出：在8X8格的國際象棋上擺放八個(gè)皇后，使其不能互相攻擊，根據(jù)國際象棋的規(guī)定，皇后可以攻擊與它在同一行、同一列或者同一斜線上的棋子，即任意兩個(gè)皇后都不能處于同一行、同一列或同一斜線上，問有多少種擺法。在8!=40320種排列中共有92種解決方案。

二、本程序需要解決的問題

1、建立合適的數(shù)據(jù)類型表示皇后在棋盤上所處的位置。

2、成功的輸出全部正確的放置方法。

3、畫出棋盤形式，在上面動(dòng)態(tài)的標(biāo)注其行走的過程。

4、預(yù)期目標(biāo)：運(yùn)用C++程序設(shè)計(jì)的編程思想編寫代碼，實(shí)現(xiàn)八皇后問題的所有（92種）擺放情況。

三、數(shù)據(jù)結(jié)構(gòu)的選擇和概要設(shè)計(jì)

1、為了簡單易行的表示皇后在棋盤所處的位置，在此建立一個(gè)整型數(shù)組queen[i]來表示，若queen[3]=2則表示皇后處在8×8棋盤的第三行和第二列。

2、列：規(guī)定每一列放一個(gè)皇后，就不會(huì)造成列上的沖突；行：當(dāng)?shù)趇行被某個(gè)皇后占據(jù)時(shí)，該行所有空格就都不能放置其他皇后；對角線：對角線有兩個(gè)方向，在同一對角線上的所有點(diǎn)都不能有沖突。

四、代碼編寫

第一種：

#include

#define true 1

#define false 0

int a[9],b[17],c[17];

int s[9];

void main()

{

void print(),movequeen(),eightqueen();

eightqueen();

}

void print()

{

int k;

printf(“n行號(hào):123456

printf(”列號(hào):“);

for(k=1;k<=8;k++)

printf(”%4d“,s[k]);printf(”n“);

}

void movequeen(int i,int j)

{

a[j]=1;b[i+j]=1;c[i-j+9]=1;

}

void eightqueen()

{

int i,j;

for(i=2;i<=16;i++)

{

if(i>=2 && i<=9)

a[i-1]=true;

b[i]=true;

c[i]=true;

}

i=1;j=1;

while(i>=1)

{

while(j<=8)

{

if(a[j] && b[i+j] && c[i-j+9])break;

j++;

}

if(j<=8)78n”);

a[j]=false;

b[i+j]=false;

c[i-j+9]=false;

s[i]=j;

if(i==8)

{

print();

movequeen(i,j);

i--;

j=s[i];

movequeen(i,j);

j++;

}

else

{

i++;

j=1;

}

}

else

{

i--;

if(i>=1)

{

j=s[i];

movequeen(i,j);

j++;

}

}

}

}

運(yùn)行結(jié)果：以行號(hào)和列號(hào)的形式出現(xiàn)92種結(jié)果。

第二種：

#include

static char Queen[8][8];

static int a[8];

static int b[15];

static int c[15];

static int iQueenNum=0;//記錄總的棋盤狀態(tài)數(shù)

void qu(int i);//參數(shù)i代表行

{

int iLine,iColumn;

//棋盤初始化，空格為*，放置皇后的地方為@

for(iLine=0;iLine<8;iLine++)

{

a[iLine]=0;//列標(biāo)記初始化，表示無列沖突

for(iColumn=0;iColumn<8;iColumn++)

Queen[iLine][iColumn]='*';

}

//主、從對角線標(biāo)記初始化，表示沒有沖突

for(iLine=0;iLine<15;iLine++)

b[iLine]=c[iLine]=0;

qu(0);

return 0;

}

void qu(int i)

{

int iColumn;

for(iColumn=0;iColumn<8;iColumn++)

{

if(a[iColumn]==0&&b[i-iColumn+7]==0&&c[i+iColumn]==0)

//如果無沖突

{

Queen[i][iColumn]='@';//放皇后

a[iColumn]=1;//標(biāo)記，下一次該列上不能放皇后

b[i-iColumn+7]=1;//標(biāo)記，下一次該主對角線上不能放皇后

c[i+iColumn]=1;//標(biāo)記，下一次該從對角線上不能放皇后if(i<7)qu(i+1);//如果行還沒有遍歷完，進(jìn)入下一行

else //否則輸出

{

//輸出棋盤狀態(tài)

int iLine,iColumn;

printf(“第%d種狀態(tài)為：n”,++iQueenNum);

for(iLine=0;iLine<8;iLine++)

{

for(iColumn=0;iColumn<8;iColumn++)

printf(“%c ”,Queen[iLine][iColumn]);

printf(“n”);

}

printf(“nn”);

}

//如果前次的皇后放置導(dǎo)致后面的放置無論如何都不能滿足要求，則回溯，重置Queen[i][iColumn]='*';

a[iColumn]=0;b[i-iColumn+7]=0;c[i+iColumn]=0;}

}

}

運(yùn)行結(jié)果：出現(xiàn)92種狀態(tài)。

第四篇：數(shù)據(jù)結(jié)構(gòu)實(shí)習(xí)報(bào)告

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)的實(shí)習(xí)報(bào)告怎么寫呀，請求做過課設(shè)的同學(xué)發(fā)一篇范文過來謝謝-_-規(guī)范實(shí)習(xí)報(bào)告的開頭應(yīng)給出題目、班級(jí)、姓名、學(xué)號(hào)和完成日期，并包括以下七個(gè)內(nèi)容：

1、需求分析以無歧義的陳述說明程序設(shè)計(jì)的任務(wù)，強(qiáng)調(diào)的是程序要做什么?明確規(guī)定：(1)輸入的形式和輸入值的范圍；(2)輸出的形式；(3)程序所能達(dá)到的功能；(4)測試數(shù)據(jù)：包括正確地輸入及其輸出結(jié)果和含有錯(cuò)誤的輸入及其輸出結(jié)果，數(shù)據(jù)結(jié)構(gòu)實(shí)習(xí)報(bào)告。

2、概要設(shè)計(jì)說明本程序中用到的所有抽象數(shù)據(jù)類型的定義、主程序的流程以及各程序模塊之間的層次(調(diào)用)關(guān)系。

3、詳細(xì)設(shè)計(jì)實(shí)現(xiàn)概要設(shè)計(jì)中定義的所有數(shù)據(jù)類型，對每個(gè)操作只需要寫出偽碼算法；對主程序和其他模塊也都需要寫出偽碼算法(偽碼算法達(dá)到的詳細(xì)程度建議為：按照偽碼算法可以在計(jì)算機(jī)鍵盤直接輸入高級(jí)程序設(shè)計(jì)語言程序)；畫出函數(shù)的調(diào)用關(guān)系圖。

4、調(diào)試分析內(nèi)容包括：(1)調(diào)試過程中遇到的問題是如何解決的以及對設(shè)計(jì)與實(shí)現(xiàn)的回顧討論和分析；(2)算法的時(shí)空分析(包括基本操作和其他算法的時(shí)間復(fù)雜度和空間復(fù)雜度的分析)和改進(jìn)思想；(3)經(jīng)驗(yàn)和體會(huì)等，實(shí)習(xí)報(bào)告《數(shù)據(jù)結(jié)構(gòu)實(shí)習(xí)報(bào)告》。

5、用戶使用說明說明如何使用你編寫的程序，詳細(xì)列出每一步操作步驟。

6、測試結(jié)果列出你的測試結(jié)果，包括輸入和輸出。這里的測試數(shù)據(jù)應(yīng)該完整和嚴(yán)格，最好多于需求分析中所列。

7、附錄題目：約瑟夫-實(shí)習(xí)報(bào)告尺寸：約瑟夫-實(shí)習(xí)報(bào)告.doc目錄：

一、需求分析

二、概要設(shè)計(jì)

三、程序具體設(shè)計(jì)及函數(shù)調(diào)用關(guān)系

四、調(diào)試分析

五、測試結(jié)果原文：實(shí)習(xí)報(bào)告題目：約瑟夫(Joseph)問題的一種描述是：編號(hào)為1，2，.，n的n個(gè)人按順時(shí)針方向圍坐一圈，每人持有一個(gè)密碼(正整數(shù))。一開始任選一個(gè)整數(shù)作為報(bào)數(shù)上限值m，從第一個(gè)人開始按順時(shí)針方向自1開始順序報(bào)數(shù)，報(bào)到m時(shí)停止報(bào)數(shù)。報(bào)m的人出列，將他的密碼作為新的m值，從他在順時(shí)針方向上的下一個(gè)開始重新從1報(bào)數(shù)，如此下去，直至年有人全部出列為止。試設(shè)計(jì)一個(gè)程序求出出列順序。班級(jí)：姓名：學(xué)號(hào)：完成日期：

一、需求分析1.本演示程序中，利用單向循環(huán)鏈表存儲(chǔ)結(jié)構(gòu)存儲(chǔ)約瑟夫環(huán)數(shù)據(jù)(即n個(gè)人的編號(hào)和密碼)。2.演示程序以用戶和計(jì)算機(jī)的對話方式執(zhí)行，即在計(jì)算機(jī)終端上顯示“提示信息”之后，由用戶在鍵盤上輸入演示程序中需要輸入的數(shù)據(jù)，運(yùn)算結(jié)果顯示在其后。3.程序執(zhí)行的命令包括：1)構(gòu)造單向循環(huán)鏈表；2)4.測試數(shù)據(jù)m的初值為20；n=7，7個(gè)人的密碼依次為：3，1，7，2，4，8，4，首先m值為6(正確的出列順序?yàn)?，1，4，7，2，1，3，5)。

二、概要設(shè)計(jì)1.單向循環(huán)鏈表的抽象數(shù)據(jù)類型定義為：ADT List{數(shù)據(jù)對象：D={ai|ai∈正整數(shù)，I=1，2，.，n,n≥0}數(shù)據(jù)關(guān)系：R1={ai-1，ai|，ai-1，ai∈D,I=1，2，.，n}基本操作：Init List(&L)操作結(jié)果：構(gòu)造一個(gè)空的線性表L。List Insert(&L,i,e)初始條件：線性表L已存在，1≤i≤List Length(L)+1.操作結(jié)果：在L中第i個(gè)位置之前插入新的數(shù)據(jù)無素e，L長度加1。List Delete(&L,i,&e)初始條件：線性表L存在非空，1≤i≤List Length(L).操作結(jié)果：刪除L的第i個(gè)元素，并用e返回其值，L長度減1。2.程序包含四個(gè)模塊：1)主程序模塊：void main(){.

第五篇：數(shù)據(jù)結(jié)構(gòu)實(shí)習(xí)報(bào)告

數(shù)據(jù)結(jié)構(gòu)第六次作業(yè)p134

——11411203張玉

24.template

void SeqQueue::EnQueue(const T& x){//插入函數(shù)

if(IsFull()==true){

maxSize=2*maxSize;

elements[rear]=x;

rear=(rear+1)%maxSize;

}

elements[rear]=x;

rear=(rear+1)%maxSize;

};

template

bool SeqQueue::DeQueue(const T& x){//刪除函數(shù)if(IsEmpty()==true)return false;

if(rear<=maxSize/4){

maxSize=maxSize/2;

x=elements[front];

front=(front+1)%maxSize;

}

x=elements[front];

front=(front+1)%maxSize;

return true;

};

29.// 利用優(yōu)先級(jí)隊(duì)列實(shí)現(xiàn)棧和隊(duì)列

#include

template class PQueue;//前視的類定義

template class Stack;

template class Queue;//優(yōu)先級(jí)隊(duì)列結(jié)點(diǎn)類的定義 template

class PQueueNode

{

friend class PQueue;//PQueue類作為友元類定義friend class Stack;

friend class Queue;

public:

PQueueNode(T &value, int newpriority, PQueueNode priority(newpriority), link(next){}//構(gòu)造函數(shù) * next):data(value),virtual T GetData(){ return data;}//取得結(jié)點(diǎn)數(shù)據(jù)

virtual int GetPriority(){ return priority;}//取得結(jié)點(diǎn)優(yōu)先級(jí)

virtual PQueueNode * GetLink(){ return link;}//取得下一結(jié)點(diǎn)地址

virtual void SetData(T& value){ data = value;}//修改結(jié)點(diǎn)數(shù)據(jù)

virtual void SetPriority(int newpriority){ priority = newpriority;} //修改結(jié)點(diǎn)優(yōu)先級(jí)

virtual void SetLink(PQueueNode * next){ link = next;}//修改指向下一結(jié)點(diǎn)的指針 private:

T data;//數(shù)據(jù)

int priority;//優(yōu)先級(jí)

PQueueNode *link;//鏈指針

};

//優(yōu)先級(jí)隊(duì)列的類定義

template

class PQueue

{

friend class Stack;

friend class Queue;

public:

PQueue():front(NULL), rear(NULL){}//構(gòu)造函數(shù)

virtual ~PQueue(){ MakeEmpty();}//析構(gòu)函數(shù)

virtual void Insert(T &value, int newpriority);//插入新元素value到隊(duì)尾 virtual T Remove();//刪除隊(duì)頭元素并返回 virtual T Get();//讀取隊(duì)頭元素的值 virtual void MakeEmpty();//置空隊(duì)列

virtual int IsEmpty(){ return front == NULL;}//判隊(duì)列空否private:

PQueueNode *front, *rear;//隊(duì)頭指針, 隊(duì)尾指針

};template

void PQueue::MakeEmpty()

{

//將優(yōu)先級(jí)隊(duì)列置空

PQueueNode *q;

while(front!= NULL)//鏈不空時(shí), 刪去鏈中所有結(jié)點(diǎn)

{

//循鏈逐個(gè)刪除

q = front;

front = front->link;

delete q;

}

rear = NULL;//隊(duì)尾指針置空

}template

void PQueue::Insert(T &value, int newpriority)

{

//插入函數(shù)

PQueueNode *q = new PQueueNode(value, newpriority, NULL);if(IsEmpty())

front = rear = q;//隊(duì)列空時(shí)新結(jié)點(diǎn)為第一個(gè)結(jié)點(diǎn)

else

{

PQueueNode *p = front, *pr = NULL;//尋找q的插入位置

while(p!= NULL && p->priority >= newpriority)//隊(duì)列中按優(yōu)先級(jí)從大到小鏈接{

pr = p;

p = p->link;

}

if(pr == NULL)

{

//插入在隊(duì)頭位置

q->link = front;

front = q;

}

else

{

q->link = p;

pr->link = q;//插入在隊(duì)列中部或尾部

if(pr == rear)

rear = q;

}

}

}

//刪除隊(duì)頭元素并返回

template

T PQueue::Remove()

{

if(IsEmpty())

return NULL;PQueueNode *q = front;

front = front->link;//將隊(duì)頭結(jié)點(diǎn)從鏈中摘下

T &retvalue = q->data;

delete q;

if(front == NULL)

rear = NULL;return retvalue;

}

//讀取隊(duì)頭元素的值

template

T PQueue::Get()

if(IsEmpty())

return NULL;

else

return front->data;

}

//(1)棧的定義與實(shí)現(xiàn)

template

class Stack:public PQueue

{

//棧類定義

public:

Stack():PQueue(){} //構(gòu)造函數(shù)

void Insert(T & value);//插入新元素value到隊(duì)尾

};template

void Stack::Insert(T & value)

{

//插入函數(shù)

PQueueNode *q = new PQueueNode(value, 0, NULL);if(IsEmpty())front = rear = q;//?？諘r(shí)新結(jié)點(diǎn)為第一個(gè)結(jié)點(diǎn)

else

{

//插入在前端

q->link = front;

front = q;

}

}//--------------------------Queue //(2)隊(duì)列的定義與實(shí)現(xiàn)

template

class Queue:public PQueue

{

//隊(duì)列類定義

public:

Queue():PQueue(){}//構(gòu)造函數(shù)

void Insert(T & value);//插入新元素value到隊(duì)尾

};template

void Queue::Insert(T & value)

{

//插入函數(shù)

PQueueNode *q = new PQueueNode(value, 0, NULL);

if(IsEmpty())

front = rear = q;//隊(duì)列空時(shí)新結(jié)點(diǎn)為第一個(gè)結(jié)點(diǎn)

else

rear = rear->link = q;//插入在隊(duì)尾位置

void main(){

Stack aStack;Queue aQueue;

int n = 1;

aStack.Insert(n);aQueue.Insert(n);}