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

PAGEPAGE3數(shù)據(jù)結構實驗報告題目：約瑟夫環(huán)班級：1403041姓名：王超學號成日期：2015.10.31需求分析任務：約瑟夫(Joseph)問題的一種描述是：編號為1，2，…，n的n個人按順時針方向圍坐一圈，每人持有一個密碼(正整數(shù))。一開始任選一個正整數(shù)作為報數(shù)上限值m，從第一個人開始按順時針方向自1開始順序報數(shù)，報到m時停止報數(shù)。報m的人出列，將他的密碼作為新的m值，從他在順時針方向上的下一個人開始重新從1報數(shù)，如此下去，直至所有人全部出列為止。試用鏈式存儲結構存儲數(shù)據(jù)，設計一個程序求出出列順序。功能要求：利用單向循環(huán)鏈表存儲結構模擬約瑟夫環(huán)，按照出列的順序印出各人的編號。測試數(shù)據(jù)：m的上限為20，初值為20；(1)對于n=7，7個人的密碼依次為：3,1,7,2,4,8,4進行測試。(2)對于從鍵盤輸入的n和n個人的密碼進行測試。概要設計定義一個循環(huán)鏈表voidincertList(LinkList*list,LinkListq,inte1,inte2)2、定義處理成員的信息的函數(shù)voidexJoseph(LinkList*jsp,intm)

3、定義判斷輸入約瑟夫環(huán)voidCreatJoseph(LinkList*jsp,intn)詳細設計1）創(chuàng)建循環(huán)鏈表voidincertList(LinkList*list,LinkListq,inte1,inte2){LinkListp;p=(LinkList)malloc(sizeof(LNode));p->number=e1;p->psw=e2;if(!*list){*list=p;p->next=NULL;}else{p->next=q->next;q->next=p;}}2）輸入約瑟夫環(huán)的數(shù)據(jù)voidCreatJoseph(LinkList*jsp,intn){LinkListq=NULL,list=NULL;inti,e;printf("請輸入密碼\n");for(i=0;i<n;i++){scanf("%d",&e);incertList(&list,q,i+1,e);if(i==0)q=list;elseq=q->next;}q->next=list;*jsp=list;}3）處理輸出結果voidexJoseph(LinkList*jsp,intm){LinkListp,q;inti;q=p=*jsp;while(q->next!=p)q=q->next;printf("順序是\n");while(p->next!=p){for(i=0;i<m-1;i++){q=p;p=p->next;}q->next=p->next;printf("%d",p->number);m=p->psw;free(p);p=q->next;}printf("%d\n",p->number);}調試分析在設計過程中，有些函數(shù)調用的規(guī)范以及算法設計方面多次存在缺陷，多次修改之后，學到了鏈表循環(huán)中數(shù)據(jù)的處理結構，利用函數(shù)方面還需要多調用。五、測試結果附錄（源代碼）#include<stdio.h>#include<stdlib.h>#include<conio.h>/*鏈表節(jié)點定義*/typedefstructnode{intnumber;/*編號*/intpsw;/*個人密碼*/structnode*next;}LNode,*LinkList;voidincertList(LinkList*list,LinkListq,inte1,inte2){LinkListp;p=(LinkList)malloc(sizeof(LNode));p->number=e1;p->psw=e2;if(!*list){*list=p;p->next=NULL;}else{p->next=q->next;q->next=p;}}voidCreatJoseph(LinkList*jsp,intn){LinkListq=NULL,list=NULL;inti,e;printf("請輸入密碼\n");for(i=0;i<n;i++){scanf("%d",&e);incertList(&list,q,i+1,e);if(i==0)q=list;elseq=q->next;}q->next=list;*jsp=list;}voidexJoseph(LinkList*jsp,intm){LinkListp,q;inti;q=p=*jsp;while(q->next!=p)q=q->next;printf("順序是\n");while(p->next!=p){for(i=0;i<m-1;i++){q=p;p=p->next;}q->next=p->next;printf("%d",p->number);m=p->psw;free(p);p=q->next;}printf("%d\n",p->number);}intmain(){LinkListjsp;intn,m;