《数据结构课程设计报告--猴子选大王》由会员分享，可在线阅读，更多相关《数据结构课程设计报告--猴子选大王（20页珍藏版）》请在金锄头文库上搜索。
1、 - 1 -数据结构课程设计报告题目：猴子选大王采用循环链表及动态存储的实现班 级：计算机 082 班姓 名：指导教师：成 绩：信息工程学院2010 年 01 月 20 日 - 2 -目录课程设计摘要(题目) 03 1.引言 032.需求分析 042.1 问题分析 042.2 总体设计 053.概要设计 073.1 模块分析 073.1.1 链表循环输入删除输出073.1.2 各个函数之间的调用关系 093.2 函数的流程分析 104.详细设计 124.1 函数设计 124.2 程序源代码 135.测试结果 166.设计体会 187.结束语 19参考文献 20 - 3 -摘要(题目 ):猴子选
2、大王任务：一堆猴子都有编号，编号是 1，2，3 .m ,这群猴子（m个）按照 1-m 的顺序围坐一圈，从第 1 开始数，每数到第 N 个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。要求：输入数据：输入 m,n ；m,n 为整数（nnext=p-next; e=p-shifang;释放结点 p 并且返回被删除猴子的编号。删除函数为：void Delete - ()删除算法的图形表示为：当猴子报号数 n 时： - 9 -11 n - 1n - 1 n n + 1n n + 1f r o n t . . .pf t o n t图 2 循环链表释放结点循环链表模块图
3、层分析（具体如下图 2 所示）循环链表模块输入功能删除释放功能报数查找功能 释放出非猴子大王结点释放出猴子大王图 3 链表循环删除输出模块3.1.2 各个函数之间的调用关系整个函数调用关系：主函数由数据输入、链表循环删除输出操作、数据输出等组成（如下图 3 所示） - 10 -主函数最后元素输出操作链表循环删除输出操作数据输入输出猴子大王序号图 4 函数调用关系图3.2 函数的流程分析（如下图 5 流程图所示）设定链表抽象数据类型的定义ADT struct 对象数据（猴子总数，m 为整数） 操作对象:struct monkey *create() 建立循环链表 struct monkey *f
4、indout(start,n) 找出被淘汰的猴子的上一个 Struct monkey *letout(last) 删掉被淘汰的猴子，返回的指针值指向下一个猴子。 - 11 -在循环链表填入数据：猴子总数 m、报号数 nfrontdata= =n?= = n-1？建立循环单链表定义结构体及变量 front、rear、m、n结束开始释放第 n 个猴子，指针 front指向第 n+1 个结点 rear=rear-next猴王就是第 rear-data 个猴子front= =rear?= = n-1？front +YNNY输出已删除的猴子节点和猴子大王结点 - 12 -图 5 流程图4.详细设计4.1
5、 函数设计程序设计中主要包括下列函数LinkList initring(int n,linklist r) 构造一个含 n 个元素的循环链表;LinkList delete(int n,int k,linklist r) 循环删除报 k 号的元素；循环输出所删除的元素；记录链表最后所保留的元素的位置；void main ( )void outring(int n,linklist r) 输出链表最后保留的元素，即猴子大王的序号； - 13 -4.2 程序源代码#include stdio.h #include stdlib.h typedef struct node int data; str
6、uct node *next; listnode,*linklist; /* /* 函数名称:创建一个循环链表/* 功能描述:输入猴子总数数据 m 和猴子报数数据 n，每报到 n 的猴子就删除此猴子结点，/下一个猴子开始报数，每报到 n 的均删除，如此循环，循环 m-1 次，即只需删除 m-1 个/ 节点,最后剩下猴子大王/* 参数:循环链表的头指针 front，尾指针 rear /*linklist initring(int n,linklist r) /创建一个循环单链表 linklist front,rear; int i; r=rear=(listnode *)malloc(sizeo
7、f(listnode); /两个指针指向首位置for(i=1;idata=i; rear-next=front; rear=front; front-data=n; front-next=r; /头尾相连r=front; /指向头节点位置return r; linklist deleted(int n,int k,linklist r) int i,j; linklist front,rear; - 14 -front=r; /p 移至头节点位置for(i=1;inext; /front 循环移至下一个位置rear=front-next; front-next=rear-next; /报 n
8、号的猴子出列，即删除 front-nextprintf(%4d,rear-data); if(i % 6=0) printf(n); free(rear); printf(n); r=front;return r; /记录猴子大王位置并传递 void outring(int n,linklist r) int i; linklist front; front=r; /获得猴子大王位置 printf(猴子大王：);printf(%4dn,front-data); /* /* 函数名称:主函数/* 功能描述:输入猴子总数 m，猴子报数数据 n /* 参 数:m，n，j /*void main()
9、/* /* 功能描述:猴子选大王游戏 C 语言工作界面，动态显示日期和时间 /*printf(n);printf(n);system(date /t);system(time /t);system(color 16);printf(n); - 15 -printf(n); printf( n);printf( n);printf( n);printf( .欢 迎 进 入. n);printf( n);printf( .猴子选大王游戏 C 语言工作界面. n);printf( n);printf( n);printf( n);printf( n);printf( n);int xuliehao;printf(n);printf(n);printf(n);printf( 请输入密码:);scanf( %d,printf(n);while(xuliehao!=39) p
