《数据结构课程设计报告敢死队问题》由会员分享，可在线阅读，更多相关《数据结构课程设计报告敢死队问题（25页珍藏版）》请在金锄头文库上搜索。
1、华 北 科 技 学 院课程设计说明书（数据结构课程设计）班级: 姓名:学号：设计题目：设计时间:指导教师:评 语:_ _评阅成绩: 评阅教师: 授课：XXX数据结构课程设计实验报告开课实验室： 基础实验室 一 2010 年9 月16 日实验题目敢死队问题1.实验题目敢死队问题2.实验设备及环境PC兼容机、Windows操作系统、VB软件等。3.功能模块简介和系统结构图系统结构图本程序有四个功能模块，包括三个解决敢死队问题方案的模块和一个退出系统模块。三个解决方案分别采用了循环聊表储存结构、线性表储存结构、循环队列储存结构。功能模块如下图所示。敢死队问题循环单链表储存结构线性表储存结构循环队列储
2、存结构退出功能模块具体简介如下：(1).循环单链表以单循环链表为存储结构，包含三个模块： 1.主程序模块 包含敢死队人数的输入，死亡数字的输入，函数的调用，结果的输出。2.构造链表并初始化 构造链表，给每个结点赋值，给队员编号。3删除 当报数到死亡数字时队员出列去执行任务，删除该节点。授课：XXX开始声明类型定义变量并初始化初始化单链表循环模块输入敢死队员总数剩下的队员数1?队员报数报数值=死亡数?队员出列输出结果（2）.线性表储存结构功能设计本程序其实质是约瑟夫环问题,本次实验用了线性表数据结构,并运用模块化的程序设计思想,算法的实现是这样的:定义类类型1. 定义变量并初始化2. 线性表初始
3、化3. 当队员数小于等于1时,输出结果授课：XXX算法流程图开始声明数据类型定义变量并初始化初始化线性表输入敢死队员总数敢死队员人数线性表长度队员报数报数值=5？队员出列剩下的队员数1?输出增加存储分配循环队列储存结构解决功能设计本程序其实质是约瑟夫环问题,本次实验用了循环队列数据结构,并运用模块化的程序设计思想,算法的实现是这样的:这个方法是用队列循环来做的，实现的方法是这样的：首先从第一号开始报数，循环到指定的偏移位置删除结点，直至剩下一个结点。然后再比较一下它的号码是不是等于1，如果等于则输出开始计数位置，如果不等，继续循环查找，直到找出符合条件的计数起始位置，输出结果。算法流程图授课：
4、XXX开始声明数据类型定义变量并初始化初始化循环队列输入敢死队员总数队列满？队员报数报数值=5?队员出列即清零剩下的队员数1?输出增加存储分配编号=1？给队员编号入队列4. 系统的主要界面设计及运行说明：进入用户主界面，选者实现结果的方法授课：XXX以10个队员，死亡数字为5来运行，结果如下 选择第2项功能，运用线性表储存结构授课：XXX 选择第3项功能，运用循环队列来实现结果5.程序的主要代码：#include #include#include#include/-循环单链表-typedef struct node int data; struct node *next;LNode;/* 定义
5、结点类型 */授课：XXXLNode* 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;inext=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;inext; a=
6、T-next; T-next=a-next; free(a); T=T-next; printf(n); return (T-data);/-/-线性表-#define LIST_INIT_SIZE 100#define LISTINCCREMENT 10#define OK 1#define ERROR 0typedef int ElemType;typedef struct KList /*定义数据结构体类型*/ElemType *elem; /*存储空间基址*/授课：XXXint length; /*当前长度*/int listsize; /*当前分配的存储容量(以sizeof(Elem
7、Type)为单位)*/SqList;int InitList_Sq(SqList &L) /*创建线性表函数*/L.elem=(ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType); if(!L.elem)printf(存储分配失败);return ERROR; elseL.length=0; /*空表长度为0*/L.listsize=LIST_INIT_SIZE;return OK;/*初始存储容量*/int ListInsert_Sq(SqList &L) /*线性表再分配函数*/*SqList L;*/int *newbase;newba
8、se=(ElemType *)realloc(L.elem, (L.listsize+LISTINCCREMENT)*sizeof(ElemType); /*为顺序表增加一个大小为存储LISTINCCREMENT个数据元素的空间*/if(!newbase) printf(存储分配失败);return ERROR;else L.elem=newbase; /*新基址*/ L.listsize+=LISTINCCREMENT; /*增加存储容量*/ return OK; /-/-循环队列-#define QueueSize 1000 /假定预分配的队列空间最多为1000个元素typedef str
9、uct int dataQueueSize; int front;int rear; 授课：XXXint count; /计数器，记录队中元素总数CirQueue;void Initial(CirQueue *Q) /将顺序队列置空Q-front=Q-rear=0; Q-count=0; /计数器置 / 判队列空int Empty(CirQueue *Q) return Q-front=Q-rear; /判队列满int Full(CirQueue *Q) return Q-rear=QueueSize-1+Q-front; /进队列void EnQueue(CirQueue *Q,int x)
10、 if (IsFull(Q) printf(队列上溢); /上溢,退出运行exit(1); Q-count +; /队列元素个数加Q-dataQ-rear=x; /新元素插入队尾Q-rear=(Q-rear+1)%QueueSize; /循环意义下将尾指针加 /出队列int DeQueue(CirQueue *Q) int temp; if(IsEmpty(Q) printf(队列为空); /下溢,退出运行exit(1); temp=Q-dataQ-front; 授课：XXXQ-count-; /队列元素个数减Q-front=(Q-front+1)%QueueSize; /循环意义下的头指针加1return temp; /-void main () SqList L; int s,i,m,count=0; /*声明变量*/ LNode *p;
