數(shù)據(jù)結(jié)構(gòu)與算法分析實(shí)驗(yàn)報(bào)告.doc

數(shù)據(jù)結(jié)構(gòu)與算法分析實(shí)驗(yàn)報(bào)告學(xué)院：電信學(xué)院班級(jí)：計(jì)算機(jī)06學(xué)號(hào)：xxx姓名：xxx小組成員：xxx2011年12月20日實(shí)驗(yàn)四 八皇后問題1、問題描述 設(shè)在初始狀態(tài)下，在國(guó)際象棋的棋盤上沒有任何棋子（這里的棋子指皇后棋子）。然后順序在第1行，第2行第8行上布放棋子。在每一行中共有8個(gè)選擇的位置，但在任一時(shí)刻棋盤的合法布局都必須滿足3個(gè)限制條件（1）任意兩個(gè)棋子得放在同一行（2）任意兩個(gè)棋子不得放在同一列上（3）任意棋子不得放在同一正斜線和反斜線上。2、基本要求 編寫求解并輸出此問題的一個(gè)合法布局的程序。3、實(shí)現(xiàn)提示 在第i行布放棋子時(shí)，從第1列到第8列逐列考察。當(dāng)在第i行第j列布放棋子時(shí)，需要考察布放棋子后在行方向列方向正斜線和反斜線方向上的布局狀態(tài)是否合法，若該棋子布放合法，再遞歸求解在第i+1行布放棋子；若該棋子布放不合法，移去這個(gè)棋子，恢復(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(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）個(gè)人按順時(shí)針方向圍坐一圈，每人持有一個(gè)正整數(shù)密碼。開始時(shí)任意給出一個(gè)報(bào)數(shù)上限m，從第一個(gè)人開始順時(shí)針方向自1起報(bào)數(shù)，報(bào)到m時(shí)停止報(bào)數(shù)，報(bào) m的人出列，將他的密碼作為新的m值，從在他順時(shí)針方向上的下一個(gè)人起重新自1報(bào)數(shù)；如此下去，直到所有人全部出列為止。2、基本要求設(shè)計(jì)一個(gè)程序模擬此過程，給出出列人的編號(hào)序列。3、實(shí)現(xiàn)提示 可考慮不帶頭指針的單鏈表結(jié)構(gòu)。4、測(cè)試數(shù)據(jù) N=7，其個(gè)人的密碼依次為：3,1,7,2,4,8,4. 初始報(bào)數(shù)上限值m=20。解：編寫程序如下：#includeclass Nodepublic:int number,data;Node *next;Node(int a,int b)number=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-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請(qǐng)輸入人數(shù)amount;cout請(qǐng)依次輸入其密碼endl;for(int i=0;id;p=new Node(i+1,d);a.add(p);cout請(qǐng)輸入起始數(shù)d;cout*endl;a.out(d);return 1;運(yùn)行結(jié)果如下：算法分析：S1：創(chuàng)建一個(gè)鏈表，表頭指向表尾，形成一個(gè)環(huán)；S2：從頭結(jié)點(diǎn)即尾結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)，開始報(bào)數(shù)，若所報(bào)的數(shù)小于d，i+，直至