敢死队问题1.doc

华 北 科 技 学 院 课程设计说明书 （数据结构课程设计） 班级: 姓名: 学号： 设计题目： 设计时间: 指导教师: 评 语:________________________________ _________________________________________ _________________________________________ _________________________________________ _________________________________________ 评阅成绩:＿＿ ＿＿评阅教师:＿＿ ＿＿＿ 《数据结构》课程设计实验报告 开课实验室： 基础实验室 一 2010 年9 月16 日 实验题目 敢死队问题 1.实验题目 敢死队问题 2.实验设备及环境 PC兼容机、Windows操作系统、VB软件等。 3.功能模块简介和系统结构图 系统结构图 本程序有四个功能模块，包括三个解决敢死队问题方案的模块和一个退出系统模块。三个解决方案分别采用了循环聊表储存结构、线性表储存结构、循环队列储存结构。功能模块如下图所示。 功能模块具体简介如下： (1).循环单链表 以单循环链表为存储结构，包含三个模块： 1.主程序模块 包含敢死队人数的输入，死亡数字的输入，函数的调用，结果的输出。 2.构造链表并初始化 构造链表，给每个结点赋值，给队员编号。 3．删除 当报数到死亡数字时队员出列去执行任务，删除该节点。 （2）.线性表储存结构 功能设计本程序其实质是约瑟夫环问题,本次实验用了线性表数据结构,并运用模块化的程序设计思想,算法的实现是这样的: 定义类类型 定义变量并初始化 线性表初始化 当队员数小于等于1时,输出结果 算法流程图 循环队列储存结构解决 功能设计 本程序其实质是约瑟夫环问题,本次实验用了循环队列数据结构,并运用模块化的程序设计思想,算法的实现是这样的: 这个方法是用队列循环来做的，实现的方法是这样的：首先从第一号开始报数，循环到指定的偏移位置删除结点，直至剩下一个结点。然后再比较一下它的号码是不是等于1，如果等于则输出开始计数位置，如果不等，继续循环查找，直到找出符合条件的计数起始位置，输出结果。 算法流程图 系统的主要界面设计及运行说明： 进入用户主界面，选者实现结果的方法 以10个队员，死亡数字为5来运行，结果如下 选择第2项功能，运用线性表储存结构 选择第3项功能，运用循环队列来实现结果 5.程序的主要代码： #include stdio.h #includestring.h #includestdlib.h #includemalloc.h //-------------------循环单链表---------------------------------------------- typedef struct node { int data; struct node *next; }LNode;/* 定义结点类型 */ LNode* CREAT(int n) /* 创建循环链表 */ { LNode *s,*q,*T; int i; if(n!=0) { T=q=(LNode *)malloc(sizeof(LNode)); q-data=1;/* 生成第一个结点并使其data值为1 */ for(i=2;i=n;i++) { s=(LNode *)malloc(sizeof(LNode)); q-next=s; q-next-data=i;/*赋值*/ q=q-next; } q-next=T; } return T; } DELETE (LNode* T,int m)/* 链表的删除 */ { LNode *a;int i; while (T-next!=T) { for (i=1;im-1;i++)/*查找要删除结点的前一结点*/ T=T-next; a=T-next; T-next=a-next; free(a); T=T-next; } printf(\n); return (T-data); } //---------------------------------------------------------------