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

本文格式為Word版，下載可任意編輯——數(shù)據(jù)結(jié)構(gòu)與算法試驗報告題目：約瑟夫環(huán)問題

班級：姓名：學號：完成日期：2023.12.28

一、需求分析1.問題描述：設有n個人圍坐在一個圓桌周邊，現(xiàn)從第s個人開始報數(shù)，數(shù)到第m的人出列，然后從出列的下一個人重新開始報數(shù)，數(shù)到第m的人又出列，?，如此反復直到所有的人全部出列為止。2.測試時n=8，s=1，m=4，若初始的順序為1,2,3,4,5,6,7,8,則問題的解為4,8,5,2,1,3,7,6。二、概要設計

為實現(xiàn)上述程序功能，應以循環(huán)隊列表示。循環(huán)隊列可用數(shù)組實現(xiàn)，但由于n是變量，我選擇以單向鏈表實現(xiàn)循環(huán)隊列。通過移動頭結(jié)點的指針來實現(xiàn)“重新開始報數(shù)〞，以循環(huán)實現(xiàn)計數(shù)。

1.循環(huán)隊列的抽象數(shù)據(jù)類型定義為：ADTLinkQueue{

數(shù)據(jù)對象：D={ai|ai∈ElemSet,i=1,2,?,n,n≥0}

數(shù)據(jù)關(guān)系：R1={|ai-1,ai∈D,i=2,?,n}約定其中a1端為隊列頭，an端為隊列尾?；静僮鳎篒nitQueue(typedefintStatus;

typedefstructLNode{

LElemTypedata;

structLNode*next;}LNode,*LinkList;

2．根據(jù)循環(huán)隊列的特點，鏈表的頭指針和尾結(jié)點的指針都指向第一個結(jié)點。對鏈表的基本操作如下：LNode*CreateLinkList(intn)

//構(gòu)造一個空的循環(huán)隊列，長為輸入值nStatusListDelete_L(LNode*L,LElemType*e)

//若隊列不為空，則刪除Q的隊頭元素，用e返回其值，并返回OK；否則返回ERROR

其中部分操作的偽代碼如下：

LNode*CreateLinkList(intn)//順序建立鏈表,L為頭結(jié)點{

L=(LNode*)malloc(sizeof(LNode));p=(LNode*)malloc(sizeof(LNode));L->next=p;

p->next=L->next;p->data=1;x=1;

for(i=0;idata=x;//插入表尾p->next=s;p=s;}

p->next=L->next;returnL;}

StatusListDelete_L(LNode*L,LElemType*e){//刪除隊列當前位置的元素q，并用e返回其值LNode*p;LNode*q;

p=L;

if(!(p->next))returnERROR;if(p->next==p){

L->next=NULL;}else

{q=p->next;

p->next=q->next;*e=q->data;free(q);}

returnOK;}//ListDelete_L

3.主函數(shù)的偽碼算法intmain(void){

LNode*L;

cc=1;//CC用于判斷是否剛開始報數(shù)，1:剛開始2:已經(jīng)有人離開隊列scanf(\scanf(\scanf(\

L=CreateLinkList(n);

if(L->next->next==L->next)returnOK;//空表else{

for(j=1;jnext;//從第s個人開始報數(shù)}

while(L->next!=NULL){

if(cc==1){

for(j=1;jnext;}

ListDelete_L(L,//刪除第m個printf(e);//出隊列的數(shù)打印

++cc;}else{

for(j=2;jnext;}

ListDelete_L(L,//刪數(shù)第m個printf(e);//出隊列的數(shù)打印}}

returnOK;}}

四、調(diào)試分析

1.由于對算法在C語言的實現(xiàn)不是很熟練，在編寫程序的過程中犯了些語法錯誤，改正錯誤浪費了時間。

2.由于開始時對循環(huán)鏈表為空時的狀態(tài)不大明白，修改程序花費了較長時間。鏈表為空時應當為L->next=NULL。

3.本程序的模塊劃分比較合理，基本依照初步設計的算法進行實現(xiàn)。4.在調(diào)試中遇到了一些新問題，改進了算法。5.調(diào)試中遇到的問題

問題一：每次第m個出隊之后從后一個開始重新計數(shù)。解決：及時參與L=L->next;調(diào)整指針。問題二：有些操作的算法實現(xiàn)不能使用。解決：把Status換為int或者*。問題三：第一次報數(shù)會多數(shù)一人。

解決：引入了cc，cc=1則為第一次報數(shù)。6.算法的時間繁雜度分析

函數(shù)ListDelete_L的時間繁雜度均為O(1)，函數(shù)CreateLinkList的時間繁雜度為O(n)，主函數(shù)的時間繁雜度為O(n2)，綜合來看此算法的時間繁雜度為O(n+n2)=O(n2)。

五、用戶使用說明

1.本系統(tǒng)的運行環(huán)境為Windows系統(tǒng)VisualC++6.0，執(zhí)行文件為j.c。2.運行程序后即顯示

輸入總?cè)藬?shù)n的值，按Enter確認。即顯示下圖：

輸入開始計數(shù)的人的序號s的值，Enter確認后顯示如下：

輸入每次數(shù)多少個人，即m的值。按Enter后顯示所求順序。

六、測試結(jié)果

n、s、m的值分別為8、1、4時所得結(jié)果如下：

n、s、m的值分別為10、3、5時所得結(jié)果如下：

n、s、m的值分別為100、3、5時所得結(jié)果如下：

經(jīng)過手算比較，程序運行正確。

六、附錄

帶解釋的源程序為：#include#include#defineERROR-1#defineOK0

typedefintLElemType;typedefintStatus;typedefstructLNode{

LElemTypedata;structLNode*next;}LNode,*LinkList;

LNode*CreateLinkList(intn)//順序建立鏈表,L為頭結(jié)點{

inti,x;

LNode*p;LNode*s;LNode*L;

L=(LNode*)malloc(sizeof(LNode));p=(LNode*)malloc(sizeof(LNode));L->next=p;//循環(huán)鏈表空表p->next=L->next;//p為尾結(jié)點p->data=1;x=1;

for(i=0;idata=x;//插入表尾p->next=s;p=s;

//printf(\}

p->next=L->next;returnL;}

StatusListDelete_L(LNode*L,LElemType*e)

{//刪除隊列當前位置的元素q，并用e返回其值，LNode*p;LNode*q;

p=L;

if(!(p->next))returnERROR;if(p->next==p){

//printf(\//printf(\L->next=NULL;}else

{q=p->next;

p->next=q->next;*e=q->data;free(q);}

returnOK;

}//ListDelete_Lintmain(void){

ints,m,n;intj,e,cc;LNode*L;cc=1;

printf(\scanf(\

printf(\scanf(\printf(\scanf(\

L=CreateLinkList(n);

if(L->next->next==L->next)returnOK;//空表else{

for(j=1;jnext;

//從第s個人開始報數(shù)}

while(L->next!=NULL){

if(cc==1)//CC用于判斷是否剛開始報數(shù)，1為剛開始2為已經(jīng)有人離開隊列，{

for(j=1;jnext;

//printf(\//用于調(diào)試，觀測開始報數(shù)的順序，正式運行時可以解釋掉}

ListDelete_L(L,//刪數(shù)第m個printf(\//出隊列的數(shù)打印++cc;}