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

數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告——八皇后問題實(shí)驗(yàn)?zāi)康模菏炀氄莆諚２僮鞯幕舅惴▽?shí)現(xiàn)。實(shí)現(xiàn)功能：利用回溯法和棧來實(shí)現(xiàn)八皇后問題：在8×8的國際象棋棋盤上，安放8個(gè)皇后，要求沒有一個(gè)皇后能夠“吃掉”任何其他一個(gè)皇后，即沒有兩個(gè)或兩個(gè)以上的皇后占據(jù)棋盤上的同一行、同一列或同一對(duì)角線。設(shè)計(jì)思路：數(shù)據(jù)結(jié)構(gòu)：enumboolean{false,true}enumbooleana[9],b[17],c[17];//檢查皇后之間是否沖突//皇后位置安全性可用邏輯表達(dá)式：a[j]&&b[i+j]&&c[i-j+9]ints[9];//s[1..8]表示順序棧，棧的下標(biāo)值表示皇后所在的行號(hào)，棧的內(nèi)容是皇后所在的列號(hào)。 該算法抽象描述如下：置當(dāng)前行當(dāng)前列均為1；while(當(dāng)前行號(hào)≤8){檢查當(dāng)前行，從當(dāng)前列起逐列試探，尋找安全列號(hào)；if(找到安全列號(hào))放置皇后，將列號(hào)記入棧中，并將下一行置成當(dāng)前行，第一列置為當(dāng)前列；else退棧回溯到上一行，移去該行已放置的皇后，以該皇后所在列的下一列作為當(dāng)前列；}結(jié)束程序。程序流程圖：源程序：#include<stdio.h>enumboolean{FALSE,TRUE};//聲明全局變量enumbooleana[9],b[17],c[17];ints[9];intnum=0;//函數(shù)聲明voidprint();voidmovequeen();voideightqueen();voidmain(){//主函數(shù)eightqueen();printf("共有%d種解法\n",num);}voidprint()//輸出函數(shù){ intk; printf("\n"); printf("NO.%d\n",++num); printf("行號(hào):12345678\n"); printf("列號(hào):"); for(k=1;k<=8;k++) printf("%3d",s[k]);printf("\n");}voidmovequeen(inti,intj){ a[j]=TRUE;b[i+j]=TRUE;c[i-j+9]=TRUE;}voideightqueen()//算法函數(shù){ inti,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){ a[j]=FALSE;b[i+j]=FALSE; c[i-j+9]=FALSE; s[i]=j; if(i==8){ num++；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++;}} }}實(shí)驗(yàn)心得：通過本次實(shí)驗(yàn)大大的提高了我個(gè)人的動(dòng)手能力，對(duì)VC編程更加的熟練，這個(gè)程序也一定程度的鍛煉了我的