安格格数据构.docx

数据结构第三次上机作业 安格格 099 计科三班 编写一个程序exp3_6.cpp，求解皇后问题，在n×n的方格棋盘上，放置n个皇后，要求每个皇后不同行、不同列、不同左右对角线。 要求：（1）皇后的个数n由用户输入，其值不能超过20，输出所有的解。 （2）采用类似于栈求解迷宫问题的方法。 分析：定义一个类，类中包含打印皇后，检查位置，设置皇后位置和对总的皇后放置 方法计数四个公有函数，和皇后的数量，存放皇后位置的数组两个私有变量。 首先输入皇后的数量，如果小于0，则输入错误，否则从第一行开始，检测相应 行的每列是否可以放置皇后，当检测到可以放置皇后的列，讲列值存入存放皇后 位置的数组，然后检测下一行可以存放皇后的列，当行达到用户输入的皇后数， 放置方法加一，最后输出每种放置皇后的方法。 每行的列值检测方法是，判断列值是否与已有皇后的列值相同，以检测皇后是否 同行，然后判断行值和已有皇后的行值之差的绝对值是否与列值和相对应行皇后的列值之差的绝对值相等，以检测皇后是否同对角线。 程序： #includeiostream #includecmath using namespace std; #define N 10 class Queen { public: Queen(){num=-1;} void Print(int n); int Check(int i,int k); void Queens(int k,int n); int count(); private: int q[N]; int num; }; void main() { Queen Q; int n; cout请输入Queen的数目(n0):endl; cinn; if(n0) { coutQueen可能的位置坐标:endl; Q.Queens(1,n); cout共有 Q.count() 种方法放置Queenendl; } else cout输入数字错误endl; } void Queen::Queens(int k,int n)//计算出皇后的排列，k是当前皇后数量，n是数量上限 { int i; if(kn)//如果达到要求的数量输出皇后排列 { Print(n); count(); } else //否则在适当的位置添加一个新皇后 { for(i=1;i=n;i++) if(Check(i,k)) //判断该行中该位置放置“皇后”是否符合要求 { q[k]=i; //记录改行中该点的位置 Queens(k+1,n); //放置下一行的“皇后” } } } void Queen::Print(int n) { int i; for(i=1;i=n;i++) cout(i,q[i]); coutendl; } int Queen::Check(int i,int k) { int j; j=1; while(jk) { if((q[j]==i) || abs(q[j]-i)==abs(j-k)) //判断列，判断斜线 return 0; //不符合返回0 j++; } return 1; //符合返回 } int Queen::count() { num++; return num; } 结果： 心得：从大框架到小细节的实现必须一步一步，有条理，否则，程序写到一半就乱了。 2、编写一个程序exp3_7.cpp，反映病人到医院看病，排队看医生的情况。在病人排队过程 中，主要重复两件事： 病人到达诊室，将病历交给护士，排到等待队列中候诊。 护士从等待队列中取出下一位病人的病历，该病人进入诊室就诊。 要求模拟病人等待就诊这一过程。程序采用菜单方式，其选项及功能说明如下： 排队-----输入排队病人的病历号，加入到病人排队队列中； 就诊-----病人排队队列中最前面的病人就诊，并将其从队列中删除； 查看排队-----从队首到队尾列出所有的排队病人的病历号； 不再排队，余下依次就诊-----从队首到队尾列出所有的排队病人的病历号，并退出运行； 下班-----退出运行。 分析：由于程序使用菜单方式，所以每一个菜单项对应一个函数。排队项对应入队；就 诊项对应出队，并输出出队项；查看排队对应输出所有队中数据；不再排队对应 输出所有队中数据，并释放队列，退出运行；下班对应退出运行。主函数