《数据结构课程设计报告--猴子选大王.doc》由会员分享，可在线阅读，更多相关《数据结构课程设计报告--猴子选大王.doc（20页珍藏版）》请在金锄头文库上搜索。
1、 数据结构课程设计报告题目：猴子选大王采用循环链表及动态存储的实现班 级：计算机082班姓 名：指导教师：成 绩： 信息工程学院 2010年01 月 20 日 目录课程设计摘要(题目) 03 1.引言 032.需求分析 04 2.1问题分析 04 2.2总体设计 053.概要设计 073.1模块分析 073.1.1链表循环输入删除输出073.1.2各个函数之间的调用关系 09 3.2函数的流程分析 104.详细设计 124.1函数设计 124.2程序源代码 135.测试结果 166.设计体会 187.结束语 19参考文献 20摘要(题目):猴子选大王任务：一堆猴子都有编号，编号是1，2，3 .
2、m ,这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。要求：输入数据：输入m,n ；m,n 为整数（nnext=p-next; e=p-shifang;释放结点p并且返回被删除猴子的编号。删除函数为：void Delete - ()删除算法的图形表示为：当猴子报号数n时： 图2 循环链表释放结点循环链表模块图层分析（具体如下图2所示）循环链表模块输入功能删除释放功能报数查找功能释放出非猴子大王结点释放出猴子大王图3 链表循环删除输出模块3.1.2各个函数之间的调用关系整个函数调用关系：主函数由数
3、据输入、链表循环删除输出操作、数据输出等组成（如下图3所示）主函数最后元素输出操作链表循环删除输出操作数据输入输出猴子大王序号图4 函数调用关系图3.2函数的流程分析（如下图5 流程图所示）设定链表抽象数据类型的定义ADT struct 对象数据（猴子总数，m为整数） 操作对象:struct monkey *create() 建立循环链表 struct monkey *findout(start,n) 找出被淘汰的猴子的上一个 Struct monkey *letout(last) 删掉被淘汰的猴子，返回的指针值指向下一个猴子。在循环链表填入数据：猴子总数m、报号数nfrontdata= =n
4、?= = n-1？建立循环单链表定义结构体及变量front、rear、m、n结束开始释放第n个猴子，指针front指向第n+1个结点rear=rear-next猴王就是第rear-data 个猴子front= =rear?= = n-1？front +YNNY输出已删除的猴子节点和猴子大王结点 图5 流程图4.详细设计4.1函数设计程序设计中主要包括下列函数LinkList initring(int n,linklist r) 构造一个含n个元素的循环链表;LinkList delete(int n,int k,linklist r) 循环删除报k号的元素； 循环输出所删除的元素；记录链表最后
5、所保留的元素的位置；void main ( )void outring(int n,linklist r) 输出链表最后保留的元素，即猴子大王的序号；4.2程序源代码#include stdio.h #include stdlib.h typedef struct node int data; struct 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(sizeof(listnode); /两个指针
