八皇后数据结构实验报告 完整版

数据结构实验报告——八皇后问题实验目的：熟练掌握栈操作的基本算法实现。实现功能：利用回溯法和栈来实现八皇后问题：在8×8的国际象棋棋盘上，安放8个皇后，要求没有一个皇后能够“吃掉”任何其他一个皇后，即没有两个或两个以上的皇后占据棋盘上的同一行、同一列或同一对角线。设计思路：数据结构：enumboolean{false,true}enumbooleana[9],b[17],c[17];//检查皇后之间是否冲突//皇后位置安全性可用逻辑表达式：a[j]&&b[i+j]&&c[i-j+9]ints[9];//s[1..8]表示顺序栈，栈的下标值表示皇后所在的行号，栈的内容是皇后所在的列号。 该算法抽象描述如下：置当前行当前列均为1；while(当前行号≤8){检查当前行，从当前列起逐列试探，寻找安全列号；if(找到安全列号)放置皇后，将列号记入栈中，并将下一行置成当前行，第一列置为当前列；else退栈回溯到上一行，移去该行已放置的皇后，以该皇后所在列的下一列作为当前列；}结束程序。程序流程图：源程序：#include<stdio.h>enumboolean{FALSE,TRUE};//声明全局变量enumbooleana[9],b[17],c[17];ints[9];intnum=0;//函数声明voidprint();voidmovequeen();voideightqueen();voidmain(){//主函数eightqueen();printf("共有%d种解法\n",num);}voidprint()//输出函数{ 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()//算法函数{ 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编程更加的熟练，这个程序也一定程度的锻炼了我的