信息学院
数据结构实验报告
学号： 课程名称：数据结构 姓名： 班级 实验名称：约瑟夫环 实验性质： ①综合性实验 √ ②设计性实验 ③验证性实验 实验时间：2017.10 本实验所用设备：PC及VS2010 【数据结构】： typedef struct _RingNode { int pos; // 位置 struct _RingNode *next; }RingNode, *RingNodePtr; 【算法思想】： 以单链表实现约瑟夫环 用户输入M,N值，从1至N开始顺序循环数数，每数到M输出该数值，直至全部输出。（约瑟夫环问题 Josephus）。以环状链表实现 【算法描述】： void CreateRing(RingNodePtr pHead, int count) { RingNodePtr pCurr = NULL, pPrev = NULL; int i = 1; pPrev = pHead; while(--count > 0) { pCurr = (RingNodePtr)malloc(sizeof(RingNode)); i++; pCurr->pos = i; pPrev->next = pCurr; pPrev = pCurr; } pCurr->next = pHead; // 构成环状链表 } 试验地点： void PrintRing(RingNodePtr pHead) { RingNodePtr pCurr; printf(\ pCurr = pHead->next; while(pCurr != NULL) { if(pCurr->pos == 1) break; printf(\ pCurr = pCurr->next; } } void KickFromRing(RingNodePtr pHead, int m) { RingNodePtr pCurr, pPrev; int i = 1; // 计数 pCurr = pPrev = pHead; while(pCurr != NULL) { if (i == m) { // 踢出环 printf(\显示出圈循序 pPrev->next = pCurr->next; free(pCurr); pCurr = pPrev->next; i = 1; } pPrev = pCurr; pCurr = pCurr->next; if (pPrev == pCurr) { // 最后一个 printf(\显示出圈循序 free(pCurr); break; } i++; } } int main() { int m = 0, n = 0; RingNodePtr pHead = NULL; printf(\ printf(\ scanf(\ printf(\ scanf(\ if(n <= 0 || m <= 0) { printf(\ system(\ return 0; } // 建立链表 pHead = (RingNodePtr)malloc(sizeof(RingNode)); pHead->pos = 1; pHead->next = NULL; CreateRing(pHead, n); #ifdef _DEBUG PrintRing(pHead); #endif // 开始出圈 printf(\ KickFromRing(pHead, m); printf(\ system(\ return 0; }