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

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