約瑟夫環(huán)數據結構實驗報告.doc

《約瑟夫環(huán)數據結構實驗報告.doc》由會員上傳分享，免費在線閱讀，更多相關內容在應用文檔-天天文庫。

1、數據結構實驗報告實驗1線性表及其應用題目：約瑟夫環(huán)一．需求分析1．本演示程序中，人數n應為任意的，首先應輸入一個值賦給初始報數上限m，程序應能自動保存出列人的序號和將出列的人所持的密碼賦給m，再次作為報數上限，如此循環(huán)，直至所有人都出列為止。2．演示程序以用戶和計算機的對話方式執(zhí)行，即在計算機終端上顯示“提示信息”之后，由用戶在鍵盤上輸入相應數據（即每個人所持的密碼），每個人的序號由程序自動分配。3．程序執(zhí)行的命令包括：（1）構造鏈表；（2）輸入數據；（3）執(zhí)行報數，儲存出列人的序號，刪除出列人的信息以及把出列人的密碼賦給m；（4）結束。4．測試數據（1）n＝

2、7，7個人的密碼依次為：3，1，7，2，4，8，4，首先m值為6，則這正確的出列順序為6，1，4，7，2，3，5。二．概要設計為了實現上述操作，應以單向循環(huán)鏈表為存儲結構。1．基本操作：new_code()操作結果：構造空鏈表，若成功就初始化每個人的相關信息delete_code()初始條件：線性鏈表存在操作結果：釋放指向出列的人的結點，并重新報數2．本程序包含三個模塊：（1）主程序模塊；（2）構造鏈表并輸入每個人信息模塊；（3）釋放結點模塊；三．詳細設計1．元素類型，結點類型和指針類型：typedefintElemType;typedefstructLNod

3、e{intnum;ElemTypedata;structLNode*next;}LNode;LNode*head;*this;*new;2．每個模塊的分析：（1）主程序模塊：main(){intm,n,i;printf("Enterthefirstcode(m):");scanf("%d",&m);printf("Enterthepeoplenumber(n):");scanf("%d",&n);getchar();printf("");new_code(n);if(head!=NULL)delete_code(n,m);else{printf("li

4、stisempty");exit();}for(i=0;inum=i;printf("enterthe%dcode(data):",i);ge

5、ts(numstr);this->data=atoi(numstr);new=(LNode*)malloc(sizeof(LNode));this->next=new;this=new;i++;}this->num=i;printf("enterthe%dcode(data):",i);gets(numstr);this->data=atoi(numstr);this->next=head;returnOK;}（1）釋放結點模塊delete_code(inta,intb){inti;intj=0;LNode*p;while((a--)!=1){for(i=1;

6、i<=b;i++){p=this;this=this->next;}b=this->data;str[j]=this->num;p->next=this->next;free(this);j++;}str[j]=this->next->num;returnOK;}2．完整的程序：#include"malloc.h"#include"stdio.h"#defineMAX100#defineERROR0#defineOK0typedefintElemType;typedefstructLNode{intnum;ElemTypedata;structLNode*ne

7、xt;}LNode;LNode*head,*this,*new;intstr[MAX];new_code(inta);delete_code(inta,intb);main(){intm,n,i;printf("Enterthefirstcode(m):");scanf("%d",&m);printf("Enterthepeoplenumber(n):");scanf("%d",&n);getchar();printf("");new_code(n);if(head!=NULL)delete_code(n,m);else{printf("listise

8、mpty");exit();}fo