数据结构与算法分析实验报告

《数据结构与算法分析实验报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《数据结构与算法分析》实验报告学院：电信学院班级：计算机06学号：xxx姓名：xxx小组成员：xxx2011年12月20日实验四八皇后问题1、问题描述设在初始状态下，在国际象棋的棋盘上没有任何棋子（这里的棋子指皇后棋子）。然后顺序在第1行，第2行……第8行上布放棋子。在每一行中共有8个选择的位置，但在任一时刻棋盘的合法布局都必须满足3个限制条件（1）任意两个棋子得放在同一行（2）任意两个棋子不得放在同一列上（3）任意棋子不得放在同一正斜线和反斜线上。2、基本要求编写求解并输出此问题的一个合法布局的程序。3、实现提示在第i行布放棋子时，从第1

2、列到第8列逐列考察。当在第i行第j列布放棋子时，需要考察布放棋子后在行方向列方向正斜线和反斜线方向上的布局状态是否合法，若该棋子布放合法，再递归求解在第i+1行布放棋子；若该棋子布放不合法，移去这个棋子，恢复布放该棋子前的状态，然后再试探在第i行第j列布放旗子。解：编写程序如下：#include#defineNUM8inta[NUM+1];intmain(){inti,k,flag,not_finish=1,count=0;i=1;a[1]=1;printf("Thepossibleconfigurationof8quee

3、nsare:");while(not_finish){while(not_finish&&i<=NUM){for(flag=1,k=1;flag&&k

4、

5、(a[i]==a[k]+(k-i)))flag=0;if(!flag){if(a[i]==a[i-1]){i--;if(i>1&&a[i]==NUM)a[i]=1;elseif(i==1&&a[i]==NUM)not_finish=0;elsea

6、[i]++;}elseif(a[i]==NUM)a[i]=1;elsea[i]++;}elseif(++i<=NUM)if(a[i-1]==NUM)a[i]=1;elsea[i]=a[i-1]+1;}if(not_finish){++count;printf((count-1)%3?"[%2d]:":"[%2d]:",count);for(k=1;k<=NUM;k++)printf("%d",a[k]);if(a[NUM-1]

7、建一个一维数组a[n]，用n表示棋子所在的行标，a[n]值表示棋子所在的列标；S2：给第一行第一列（即a[1]）赋初值，表明有一个棋子在该处；S3：用flag作为是否处理过的标记，判断是否有多个皇后在同一行，判断是否有多个皇后在同一对角线。时间复杂度为：O（n2）空间复杂度为：O（0）实验五约瑟夫环问题仿真1、问题描述设编号为1,2，…，n（n>0）个人按顺时针方向围坐一圈，每人持有一个正整数密码。开始时任意给出一个报数上限m，从第一个人开始顺时针方向自1起报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从在他顺时针方向上的下

8、一个人起重新自1报数；如此下去，直到所有人全部出列为止。2、基本要求设计一个程序模拟此过程，给出出列人的编号序列。3、实现提示可考虑不带头指针的单链表结构。4、测试数据N=7，其个人的密码依次为：3,1,7,2,4,8,4.初始报数上限值m=20。解：编写程序如下：#includeclassNode{public:intnumber,data;Node*next;Node(inta,intb){number=a;data=b;next=0;}};classCircle{public:Node*Head,*Tail;C

9、ircle(){Head=Tail=0;}voidadd(Node*p){if(Head==0){Head=Tail=p;}else{Tail->next=p;Tail=p;Tail->next=Head;}}intsearch(inta){Node*p,*q;intd;p=Head;if(p==p->next){cout<number<next;}cout<number<data;if(i==1){q=p;p=p-

10、>next;q->data=p->data;q->number=p->number;Head=q;q->next=p->next;deletep;returnd;}Head=q-