數(shù)據(jù)結(jié)構(gòu)與算法分析實驗報告

1、數(shù)據(jù)結(jié)構(gòu)與算法分析實驗報告學(xué)院：電信學(xué)院班級：計算機06學(xué)號：xxx姓名：xxx小組成員：xxx2011年12月20日實驗四 八皇后問題1、問題描述 設(shè)在初始狀態(tài)下，在國際象棋的棋盤上沒有任何棋子（這里的棋子指皇后棋子）。然后順序在第1行，第2行第8行上布放棋子。在每一行中共有8個選擇的位置，但在任一時刻棋盤的合法布局都必須滿足3個限制條件（1）任意兩個棋子得放在同一行（2）任意兩個棋子不得放在同一列上（3）任意棋子不得放在同一正斜線和反斜線上。2、基本要求 編寫求解并輸出此問題的一個合法布局的程序。3、實現(xiàn)提示 在第i行布放棋子時，從第1列到第8列逐列考察。當(dāng)在第i行第j列布放棋子時，需要考

2、察布放棋子后在行方向列方向正斜線和反斜線方向上的布局狀態(tài)是否合法，若該棋子布放合法，再遞歸求解在第i+1行布放棋子；若該棋子布放不合法，移去這個棋子，恢復(fù)布放該棋子前的狀態(tài)，然后再試探在第i行第j列布放旗子。解：編寫程序如下：#include#define NUM 8 int aNUM+1;int main()int i,k,flag,not_finish=1,count=0;i=1; a1=1; printf(The possible configuration of 8 queens are: n);while(not_finish)while(not_finish&i=NUM) for(

3、flag=1,k=1;flag&ki;k+) if(ak=ai)flag=0;for(k=1;flag&k1&ai=NUM)ai=1; else if(i=1&ai=NUM)not_finish=0; else ai+; else if(ai=NUM) ai=1;else ai+; else if(+i=NUM)if(ai-1=NUM) ai=1;else ai=ai-1+1; if(not_finish)+count;printf(count-1)%3? %2d: : %2d: ,count);for(k=1;k=NUM;k+) printf( %d,ak);if(aNUM-10）個人按順時

4、針方向圍坐一圈，每人持有一個正整數(shù)密碼。開始時任意給出一個報數(shù)上限m，從第一個人開始順時針方向自1起報數(shù)，報到m時停止報數(shù)，報 m的人出列，將他的密碼作為新的m值，從在他順時針方向上的下一個人起重新自1報數(shù)；如此下去，直到所有人全部出列為止。2、基本要求設(shè)計一個程序模擬此過程，給出出列人的編號序列。3、實現(xiàn)提示 可考慮不帶頭指針的單鏈表結(jié)構(gòu)。4、測試數(shù)據(jù) N=7，其個人的密碼依次為：3,1,7,2,4,8,4. 初始報數(shù)上限值m=20。解：編寫程序如下：#includeclass Nodepublic:int number,data;Node *next;Node(int a,int b)nu

5、mber=a;data=b;next=0;class Circlepublic:Node *Head,*Tail;Circle()Head=Tail=0;void add(Node *p)if(Head=0)Head=Tail=p;elseTail-next=p;Tail=p;Tail-next=Head;int search(int a)Node *p,*q;int d;p=Head;if(p=p-next)coutnumberendl;return 0;for(int i=1;inext;coutnumberdata;if(i=1)q=p;p=p-next;q-data=p-data;q-

6、number=p-number;Head=q;q-next=p-next;delete p;return d;Head=q-next=p-next;delete p;return d;int out(int a)while(a=search(a);return 1;int main()Circle a;int amount,d;Node *p;cout請輸入人數(shù)amount;cout請依次輸入其密碼endl;for(int i=0;id;p=new Node(i+1,d);a.add(p);cout請輸入起始數(shù)d;cout*endl;a.out(d);return 1;運行結(jié)果如下：算法分析：S1：創(chuàng)建一個鏈表，表頭指向表尾，形成一個環(huán)；S2：從頭結(jié)點即尾結(jié)點的下一個結(jié)點，開始報數(shù)，若所報的數(shù)小于d，i+，直至所報的數(shù)等于d，將報d的結(jié)點的