約瑟夫環(huán)數(shù)據(jù)結構實驗報告

數(shù)據(jù)結構上機實驗報告1、需求分析1：用一個循環(huán)鏈表實現(xiàn)n個人按順時針排成一圈,每個人看作一個節(jié)點,每個節(jié)點都是一個結構體類型,包含三個域:序號域(data),密碼域(key),指向下一個人的指針域(next).2：程序開始時由用戶任意輸入人數(shù)n及一個正整數(shù)作為報數(shù)上限值m,一個正整數(shù)作為密碼最大值，判斷所輸密碼是否在范圍內。然后為依次每一個人指定一個密碼3：初始密碼為用戶外部輸入的密碼m,從第一個人開始按順市針方向自1開始報數(shù).,報道m(xù)的時停止,報m的人出列,將他的密碼作為新的密碼值(m),從他在順針方向的下一個人開始重新從1報數(shù),如此下去,直至所有的人全部出列為止.4：本程序最終結果為n的人的出列順序5：測試數(shù)據(jù):m的初值為1;n=5(即有5個人)57個人的密碼依次為:1，2，3,4，5.首先沒的值為1,正確的出列順序應為1，2，4，3，5。2概要分析抽象數(shù)據(jù)類型的定義：為實現(xiàn)上述程序的功能，可以用整數(shù)存儲用戶的輸入。并將用戶輸入的值存儲于線性表中。算法的基本思想：約瑟夫環(huán)問題中的數(shù)據(jù)是人所在的位置，而這種數(shù)據(jù)是存在“第一元素、最后元素”，并且存在“唯一的前驅和后繼的”，符合線性表的特點。由于需要模擬約瑟夫環(huán)的出列問題，可以采用順序表來實現(xiàn)線性表，完成出列順序的輸出。核心算法主要分為兩步：1、確定需要刪除的位置，2、設置并刪除該位置。已知報數(shù)間隔m，我們可以把當前位置加上m獲得需要刪除的位置，如果獲得的位置超過順序表中實際元素的總長度，則可以通過減去數(shù)組的實際長度來修正（即模擬環(huán)狀計數(shù)）。然后把順序表中的當前指向位置設置為該位置，繼而刪掉該位置。反復進行上述確定位置和刪除位置的操作，直到順序表為空。主程序的流程：程序由三個模塊組成：（1）輸入模塊：無提示語句，直接輸入總人數(shù)n和報數(shù)次數(shù)m，中間用逗號隔開。（2）構造鏈表并輸入每個人信息模塊：（3）主要處理出列的函數(shù)：分別在DOS下和文件中，按移除元素的順序依次顯示其位置。3、詳細設計

1.本程序包含三個模塊

1)主程序模塊

intmain()

{

intm,n,i=0;

LinkLists;

printf("請輸入報數(shù)上限m和人數(shù)n:\n");

do{

if(i>0)

printf("輸入有誤，請重新輸入:\n");

scanf("%d",&m);

getchar();

scanf("%d",&n);

getchar();

i++;

}while(m<=0||n<=0);

s=CreatList_L(n);

ListDelete_L(s,m,n);

return0;

}

2)構造鏈表并輸入每個人信息模塊；LinkListL,r,q;

inti,key;

printf("請輸入%d個數(shù)字作為每個人的密碼:\n",n);

for(i=1;i<=n;i++)

{

scanf("%d",&key);

//輸入每個人的密碼

r=(LinkList)malloc(sizeof(LNode));

if(i==1)

{

L=q=r;

}

else{

q->next=r;

q=r;

}

r->num=i;

r->pwd=key;

}

r->next=L;//使最后節(jié)點指向首節(jié)點，形成循環(huán)鏈表

returnL;//向主函數(shù)返回創(chuàng)建完成的循環(huán)鏈表首節(jié)點的地址}3）主要處理出列的函數(shù)：voidListDelete_L(LinkList&L,intm,intn){

LinkListp,s;

intj;

while(n>0){//只要人數(shù)大于0就繼續(xù)，直到全部出列

p=L;

for(j=1;j<m;j++){

//順序找到第m個節(jié)點（人）并使指針指向該節(jié)點

s=p;

p=p->next;

}

printf("出列人原來的序號是:%d\n",p->num);//輸出出列人序號

m=p->pwd;//將出列人的密碼作為新的報數(shù)值m

s->next=p->next;//將出列的節(jié)點（人）從循環(huán)鏈表中刪除

L=p->next;

free(p);

n--;

}}4、調試分析（1）編寫程序時，指針運用不熟練，導致調試時錯誤過多，花費了太多時間，后通過對指針相關知識的進一步了解，改正了程序中的錯誤，正確運行了程序。（2）數(shù)據(jù)結構是一門比較抽象的課程，但是也是一門最基礎的課程學的過程。在現(xiàn)實生活的也非常廣泛通過設計該實驗讓我更加深刻的掌握了有關鏈表的知識，同時也認識到了自己在平時學習當中的盲點。通過這次實驗發(fā)現(xiàn)了自己在數(shù)據(jù)結構這門功課上存在嚴重的不足。鏈表中的指針理解不夠，運用不夠熟練，常常出現(xiàn)一些莫名其妙的問題，調試費時太多。今后一定會多編程，多思索。在以后的學習過程中還需要不斷的完善學習，希望能把數(shù)據(jù)結構這門課學習的更加深入，更加透徹。5、測試結果6、附錄#include<stdio.h>#include<malloc.h>typedefstructLNode{

intpwd,num;

structLNode*next;}LNode,*LinkList;LinkListCreatList_L(intn){

//建立循環(huán)鏈表

LinkListL,r,q;

inti,key;

printf("請輸入%d個數(shù)字作為每個人的密碼:\n",n);

for(i=1;i<=n;i++)

{

scanf("%d",&key);

//輸入每個人的密碼

r=(LinkList)malloc(sizeof(LNode));

if(i==1)

{

L=q=r;

}

else{

q->next=r;

q=r;

}

r->num=i;

r->pwd=key;

}

r->next=L;//使最后節(jié)點指向首節(jié)點，形成循環(huán)鏈表

returnL;//向主函數(shù)返回創(chuàng)建完成的循環(huán)鏈表首節(jié)點的地址}voidListDelete_L(LinkList&L,intm,intn){

LinkListp,s;

intj;

while(n>0){//只要人數(shù)大于0就繼續(xù)，直到全部出列

p=L;

for(j=1;j<m;j++){

//順序找到第m個節(jié)點（人）并使指針指向該節(jié)點

s=p;

p=p->next;

}

printf("出列人原來的序號是:%d\n",p->num);//輸出出列人序號

m=p->pwd;//將出列人的密碼作為新的報數(shù)值m

s->next=p->next;//將出列的節(jié)點（人）從循環(huán)鏈表中刪除

L=p->next;

free(p);

n--;

}}

intmain()

{

intm,n,i=0;

LinkLists;

printf("請輸入報數(shù)上限m和人數(shù)n:\n");

do{

if(i>0)

printf("輸入有誤，