数据结构实验集 各种存储结构的基本函数源代码

/* * 下面是我帮你写的一个“约瑟夫环算法”的实现。经测试后是对的，好好享用吧! * :-) * 约瑟夫环是：编号为1,2, ... ,n的n个人按顺时针方向围坐一圈，每个人 * 持有一个密码。一开始任选一个正整数作为报数上限值m，从第一个人开 * 始按顺时针方向自1开始顺报数，报到m时停止报数。报到m时停止报数。 * 报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人 * 开始重新从1报数，如此下去，直至所有人全部出列为止。 * * 分析： * 可以先建一个单向循环链表；而整个“约瑟夫环”问题的过程，最终是 * 把这个链表删空为止。但在删时不能顺着删，而是按该问题的方案来删， * 这也是这个问题的价值所在。细节部分可以看StatGame函数。 *-------------------------------------------------------------- * 实现环境：Dev-C++ 4.8.6.0, TC2.0 * 完成时间：2003年10月13日 */ #include <stdio.h> #include <stdlib.h> #define MAX_NODE_NUM 100 #define TRUE 1U #define FALSE 0U typedef struct NodeType { int id; /* 编号 */ int cipher; /* 密码 */ struct NodeType *next; } NodeType; /* 创建单向循环链表 */ static void CreaList(NodeType **, const int); /* 运行 "约瑟夫环 "问题 */ static void StatGame(NodeType **, int); /* 打印循环链表 */ static void PrntList(const NodeType *); /* 得到一个结点 */ static NodeType *GetNode(const int, const int); /* 测试链表是否为空, 空为TRUE，非空为FALSE */ static unsigned EmptyList(const NodeType *); int main(void) { int n, m; NodeType *pHead = NULL; while (1) { printf( "请输入人数n（最多%d个）:", MAX_NODE_NUM); scanf( "%d", &n); printf( "和初始密码m: "); scanf( "%d", &m); if (n>MAX_NODE_NUM) { printf( "人数太多，请重新输入！\n "); continue; } else break; } CreaList(&pHead, n); printf( "\n------------ 循环链表原始打印 -------------\n "); PrntList(pHead); printf( "\n-------------- 出队情况打印 ---------------\n "); StatGame(&pHead, m); printf( "\n 约瑟夫环 问题完成!\n "); return 0; } static void CreaList(NodeType **ppHead, const int n) { int i, iCipher; NodeType *pNew, *pCur; for(i=1;i<=n;i++) { printf( "输入第%d个人的密码: ", i); scanf( "%d", &iCipher); pNew=GetNode(i,iCipher); if (*ppHead==NULL) { *ppHead=pCur=pNew; pCur-> next=*ppHead; } else { pNew-> next=pCur-> next; pCur-> next=pNew; pCur=pNew; } } printf( "完成单向循环链表的创建!\n "); } static void StatGame(NodeType **ppHead, int iCipher) { int iCounter, iFlag=1; NodeType *pPrv, *pCur, *pDel; pPrv=pCur=*ppHead; /* 将pPrv初始为指向尾结点，为删除作好准备 */ while (pPrv-> next!=*ppHead) pPrv=pPrv-> next; while (iFlag) /* 开始搞了! */ { /* 这里是记数，无非是移动iCipher-1趟指针! */ for (iCounter=1;iCounter<iCipher;iCounter++) { pPrv=pCur; pCur=pCur-> next; } if (pPrv==pCur) /* 是否为最后一个结点了 */ iFlag=0; pDel=pCur; /* 删除pCur指向的结点，即有人出列 */ pPrv-> next=pCur-> next; pCur=pCur-> next; iCipher=pDel-> cipher; printf( "第%d个人出列, 密码: %d\n ", pDel-> id, /* 这个编号标识出列的顺序 */ pDel-> cipher); free(pDel); } *ppHead=NULL; /* 没人了！为了安全就给个空值 */ } static void PrntList(const NodeType *pHead) { const NodeType *pCur=pHead; if (EmptyList(pHead)) return; do { printf( "第%d个人, 密码: %d\n ", pCur-> id, pCur-> cipher); pCur=pCur->next; } while (pCur!=pHead); } static NodeType *GetNode(const int iId, const int iCipher) { NodeType *pNew; pNew=(NodeType *)malloc(sizeof(NodeType)); if (!pNew) { printf( "Error, the memory is not enough!\n "); exit(-1); } pNew-> id=iId; pNew-> cipher=iCipher; pNew-> next=NULL; return pNew; } static unsigned EmptyList(const NodeType *pHead) { if (!pHead) { printf( "The list is empty!\n "); return TRUE; } return FALSE; } /*********************************************** */