数据结构课程设计报告-敢死队问题.doc

21华 北 科 技 学 院课程设计说明书（数据结构课程设计）班级: 姓名:学号：设计题目：设计时间:指导教师:评 语:_ _评阅成绩: 评阅教师: 数据结构课程设计实验报告开课实验室： 基础实验室 一 2010 年9 月16 日实验题目敢死队问题1.实验题目敢死队问题2.实验设备及环境pc兼容机、windows操作系统、vb软件等。3.功能模块简介和系统结构图系统结构图本程序有四个功能模块，包括三个解决敢死队问题方案的模块和一个退出系统模块。三个解决方案分别采用了循环聊表储存结构、线性表储存结构、循环队列储存结构。功能模块如下图所示。敢死队问题循环单链表储存结构线性表储存结构循环队列储存结构退出功能模块具体简介如下：(1).循环单链表以单循环链表为存储结构，包含三个模块： 1.主程序模块 包含敢死队人数的输入，死亡数字的输入，函数的调用，结果的输出。2.构造链表并初始化 构造链表，给每个结点赋值，给队员编号。3删除 当报数到死亡数字时队员出列去执行任务，删除该节点。开始声明类型定义变量并初始化初始化单链表循环模块输入敢死队员总数剩下的队员数1?队员报数报数值=死亡数?队员出列输出结果（2）.线性表储存结构功能设计本程序其实质是约瑟夫环问题,本次实验用了线性表数据结构,并运用模块化的程序设计思想,算法的实现是这样的:定义类类型1. 定义变量并初始化2. 线性表初始化3. 当队员数小于等于1时,输出结果算法流程图开始声明数据类型定义变量并初始化初始化线性表输入敢死队员总数敢死队员人数线性表长度队员报数报数值=5？队员出列剩下的队员数1?输出增加存储分配循环队列储存结构解决功能设计本程序其实质是约瑟夫环问题,本次实验用了循环队列数据结构,并运用模块化的程序设计思想,算法的实现是这样的:这个方法是用队列循环来做的，实现的方法是这样的：首先从第一号开始报数，循环到指定的偏移位置删除结点，直至剩下一个结点。然后再比较一下它的号码是不是等于1，如果等于则输出开始计数位置，如果不等，继续循环查找，直到找出符合条件的计数起始位置，输出结果。算法流程图开始声明数据类型定义变量并初始化初始化循环队列输入敢死队员总数队列满？队员报数报数值=5?队员出列即清零剩下的队员数1?输出增加存储分配编号=1？给队员编号入队列4. 系统的主要界面设计及运行说明：进入用户主界面，选者实现结果的方法以10个队员，死亡数字为5来运行，结果如下 选择第2项功能，运用线性表储存结构 选择第3项功能，运用循环队列来实现结果5.程序的主要代码：#include #include#include#include/-循环单链表-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;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=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; /*存储空间基址*/int length; /*当前长度*/int listsize; /*当前分配的存储容量(以sizeof(elemtype)为单位)*/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;newbase=(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 struct int dataqueuesize; int front;int rear; int 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) 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; q-count-; /队列元素个数减q-front=(q-front+1)%queuesize; /循环意义下的头指针加1return temp; /-void main () sqlist l; int s,i,m,count=0; /*声明变量*/ lnode *p; int z,y; int num;int opt; abc: printf(_n);printf(| 1.循环链表 |n);printf(| 2.线性表 |n);printf(| 3.循环队列 |n);printf(| 4.退出 |n); printf(_n);printf(请选择实现结果的方法：（14）nn);scanf(%d,&opt);if(opt4 | opt1) printf(输入有误请重新输入n);goto abc;switch(opt)case 1:system(cls);printf(您使用是循环链表储存结构nn);efg:printf(请输入敢死队的人数：n);scanf(%d,&num);if(numnum | m1) printf(输入有误请重新输入); goto m; else p=creat(num); y=delete(p,m); z=num-y+2; if(z%num=0) printf (从第 %dth:开始计数n,z); else printf(从第%d号战士开始计数才能让排长最后一个留下来而不去执行任务。n,(num-y+2)%num);break;case 2:system(cls);printf(您使用的是线性表储存结构nn);e:printf(请输入敢死队的人数：n);scanf(%d,&num);if(numl.listsize ) /*当顺序表当前分配的存储空间大小不足时进行再分配*/ listinsert_sq(l); for(i=0;i1) /*当所剩敢死队员总数为1时,总循环结束*/ for(i=0;inum;i+) if(l.elemi!=0) count+; if(count=5) /*报数循环*/ l.elemi=0; /*表示队员出列*/ count=0; /*计数器清零*/ s-; /*敢死队员数-1*/ for(i=0;inum;i+) /*输出*/if(l.elemi!=0)if(num-l.elemi+2)%num=0) printf(从第%d号战士开始计数才能让排长最后一个留下来而不去执行任务。n,num);elseprintf(从第%d号战士开始计数才能让排长最后一个留下来而不去执行任务。n,(num-l.elemi+2)%num); break;case 3:system(cls);printf(您使用的是循环队列储存结构nn);int start,count,j; cirqueue s; g:printf(请输入敢死队的人数：n);scanf(%d,&num);if(num1)printf(输入有误请重新输入n);goto g;for(start=1;start=num;start+)/start为测试起点 initial(&s); for(i=1;i=num;i+) enqueue(&s,i); for(i=1;istart;i+) j=dequeue(&s); enqueue(&s,j); count=1; while(countnum) for(i=1;i5;i+) j=dequeue(&s); enqueue(&s,j); j=dequeue(&s); count+; if(s.datas.front=1) break; printf(从第%d号战士开始计数才能让排长最后一个留下来而不去执行任务。n,start); break; case 4:exit(0);goto abc;6.实验总结：通过这次课程设计我又学到了很多东西,如程序的模块化设计思想，同时也加深了对数据结构这门课程的理解和学会了如何在实际中应用数据结构。在做程序之前，觉得敢死队这个问题，很难解决。在通过自己一次次的画图，推算结果时，明白了该程