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

《数据结构课程设计报告敢死队问题.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计报告敢死队问题.docx（29页珍藏版）》请在三一文库上搜索。

1、华北科技学院课程设计说明书（数据结构课程设计）班级：姓名：学号：设计题目：设计时间：指导教师：评 语:评阅成绩：评阅教师：数据结构课程设计实验报告开课实验室： 基础实验室 一2010 年9月16日实验题目敢死队问题1. 实验题目敢死队问题2. 实验设备及环境PC兼容机、Windows操作系统、VB软件等。3. 功能模块简介和系统结构图 系统结构图本程序有四个功能模块，包括三个解决敢死队问题方案的模块和一个退出系统模块。 三个解决方案分别采用了循环聊表储存结构、线性表储存结构、循环队列储存结构。功 能模块如下图所示。循环单链表储线性表储存循环队列储存退出敢死队问题结构结构存结构 L功能模块具体简

2、介如下: （1）.循环单链表以单循环链表为存储结构，包含三个模块:1.主程序模块 包含敢死队人数的输入，死亡数字的输入，函数的调用，结果的输出。2.构造链表并初始化构造链表，给每个结点赋值，给队员编号。3 删除当报数到死亡数字时队员出列去执行任务，删除该节点。(2).线性表储存结构功能设计本程序其实质是约瑟夫环问题，本次实验用了线性表数据结构,并运用模块化的程序设计思想，算法的实现是这样的：定义类类型1. 定义变量并初始化2. 线性表初始化3. 当队员数小于等于1时，输出结果算法流程图循环队列储存结构解决功能设计,算法本程序其实质是约瑟夫环问题，本次实验用了循环队列数据结构，并运用模块化的程序

3、设计思想 的实现是这样的这个方法是用队列循环来做的，实现的方法是这样的：首先从第一号开始报数，循环到指定的偏移位置删除结点，直至剩下一个结点。然后再比较一下它的号码是不是等于1，如果等于则输出开始计数位置，如果不等，继续循环查找，直到找出符合条件的计数起始位置，输出结果。算法流程图E "F : Debuck敢死6k- exe表列 镀表臥 隹坏出 BI M 12 3 4请选择实现结果的方祛：g10个队员，死亡数字为5来运行，结果如下?cl "F: Debug：敢死6k. exe您使用是循那链舂储存结构 请输入敢死队的人数：10请输入死亡数数字人執号战士开始计数才能让排长最后一

4、个滔下来而不去执行任务表列 链表臥 程坏岀Bf 12 3 4请选择实駆吉果的方法！ (1-4)选择第2项功能，运用线性表储存结构n x表列 程坏出 H 12 3 4叽: DebueVtt5EEk- ese弓使用的是线性表储存结构胡输入敢死队的人数；10JA第y号战士开始计数才能让排长最后一个留下耒而不去执行任务。晴选择实现结杲的方法 C1-4)选择第3项功能，运用循环队列来实现结果c；"F : DebueSlexe圾使用的是循坏臥列储存结构请输入敢死队的人数；k報号战士开始计数才能让排长最后一个留下耒而不去执行任务。表列 铤表队 程坏出 n 1 2 3 JI淸选择实现结果的方法：C1

5、-4)5.程序的主要代码:#i nclude <stdio.h>#i nclude<stri ng.h>#i nclude<stdlib.h>#i nclude<malloc.h>/循环单链表typedef struct nodeint data;struct node *n ext;LNode;/* 定义结点类型*/LNode* CREAT(int n) /*创建循环链表 */LNode *s,*q,*T;int i;if(n !=0)T=q=(LNode *)malloc(sizeof(LNode);q->data=1;/*生成第一个结

6、点并使其 data值为1 */for(i=2;i<=n ;i+)s=(LNode *)malloc(sizeof(LNode);q->n ext=s;q-> next->data=i;/*赋值 */q=q->n ext;q->n ext=T;return T;DELETE (LNode* T,int m)/* 链表的删除 */LNode *a;i nt i;while (T->n ext!=T)for (i=1;i<m-1;i+)/*查找要删除结点的前一结点*/T=T->n ext;a=T- >n ext;T->n ext=a-

7、>n ext;free(a);T=T->n ext;prin tf("n");return (T->data);/ 线性表#defi ne LIST_INIT_SIZE 100#defi ne LISTINCCREMENT 10#defi ne OK 1#defi ne ERROR 0 typedef int ElemType;typedef struct KList/*定义数据结构体类型*/ElemType *elem; /*存储空间基址*/int length;/* 当前长度 */int listsize; /*当前分配的存储容量(以sizeof(El

8、emType)为单位)*/SqList;int InitList_Sq( SqList &L)/* 创建线性表函数 */L.elem=(ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType);if(!L.elem)printf("存储分配失败");return ERROR; elseL.length=O;/* 空表长度为 0*/L.listsize=LIST_INIT_SIZE;return OK;/*初始存储容量*/int List In sert_Sq(SqList &L)/* 线性表再分配函数 */*Sq

9、List L;*/int *n ewbase;n ewbase=(ElemType *)realloc(L.elem,(L.listsize+LISTINCCREMENT)*sizeof(ElemType);/*为顺序表增加一个大小为存储LISTINCCREMENT个数据元素的空间*/if(! newbase)printf("存储分配失败");return ERROR;elseL.elem=newbase;/* 新基址 */L.listsize+=LISTINCCREMENT;/*增加存储容量*/return OK;/ 循环队列#define QueueSize 1000

10、/假定预分配的队列空间最多为 1000个元素typedef structint dataQueueSize;int front;in t rear;in t cou nt; /计数器，记录队中元素总数CirQueue;void Initial(CirQueue *Q)/将顺序队列置空Q->fron t=Q->rear=0;Q->cou nt=0; /计数器置/判队列空int Empty(CirQueue *Q)retur n Q->fron t=Q->rear;/判队列满int Full(CirQueue *Q)retur n Q->rear=QueueSi

11、ze-1+Q->fr ont;/进队列void En Queue(CirQueue *Q,i nt x)if (IsFull(Q)printf("队列上溢");/上溢，退出运行exit(1);Q->cou nt +; /队列元素个数加Q->dataQ->rear=x; /新元素插入队尾Q->rear=(Q->rear+1)%QueueSize; /循环意义下将尾指针加/出队列int DeQueue(CirQueue *Q)int temp;if(lsEmpty(Q) printf("队列为空");/下溢，退出运行 ex

12、it(1);temp=Q->dataQ->fr on t;Q->cou nt-; /队列元素个数减循环意义下的头指针加1Q->fro nt=(Q->fro nt+1)%QueueSize; / return temp;/void mai n ()SqList L;int s,i,m,count=O;/* 声明变量 */LNode *p;int 乙y;int num;int opt;abc:printf("n");prin tf("|1.循环链表|n");prin tf("|2.线性表|n");prin t

13、f("|3.循环队列|n");prin tf("|4.退出|n");printf("n");printf(”请选择实现结果的方法：(14 ) nn");scan f("%d",&opt);if(opt>4 | opt<1)printf("输入有误请重新输入n");goto abc; switch(opt)case 1:system("cls");efg:printf("您使用是循环链表储存结构nn");printf（"

14、;请输入敢死队的人数：n"）;sea nf("%d",&nu m);if(nu m<1)printf("输入有误请重新输入n");goto efg;m:printf("请输入死亡数数字n");scan f("%d",&m);if(m>num | m<1) printf("输入有误请重新输入");goto m;elsep=CREAT (n um);y=DELETE(p,m);z=num-y+2;if(z% num=0)printf ("从第 %

15、dth:开始计数 n",z);elseprintf("从第%d号战士开始计数才能让排长最后一个留下来而不去执行去执行任务。n",(num-y+2)%num);break;case 2:system("cls");printf("您使用的是线性表储存结构nn");e:printf("请输入敢死队的人数：n");sca nf("%d",&nu m);if(nu m<1)printf("输入有误请重新输入n");goto e;m=5;In itList_Sq

16、(L);while(num>L.listsize)/*当顺序表当前分配的存储空间大小不足时进行再分配*/ListI nsert_Sq(L);for(i=0;i<num;i+) L.elemi=i+1;/* 为队员赋值 */ s=num;i=0;while(s>1)/*当所剩敢死队员总数为1时，总循环结束*/for(i=0;i <nu m;i+)if(L.elemi!=0)coun t+;if(cou nt=5)/* 报数循环 */L.elemi=0; /* 表示队员出列*/count=0;/*计数器清零*/s-;/*敢死队员数-1*/for(i=0;i< nu m

17、;i+)/* 输出 */if(L.elemi!=0)if( num-L.elemi+2)% nu m=0)printf("从第%d号战士开始计数才能让排长最后一个留下来而不去执行任务。n",num);else 任务。n",(num-L.elemi+2)%num);break;case 3:system("cls");printf("您使用的是循环队列储存结构nn");int start,co un t,j;CirQueue s;g:printf("请输入敢死队的人数：n");sca nf("%d

18、",&nu m);if(nu m<1)printf("输入有误请重新输入n");goto g;for(start=1;start<=nu m;start+)/start为测试起点In itial(& s);for(i=1;i<=nu m;i+)En Queue(&s,i);for(i=1;i<start;i+)j=DeQueue(&s);En Queue(&s,j);coun t=1;while(co untvnum)for(i=1;i<5;i+)j=DeQueue(&s);En Que

19、ue(&s,j);j=DeQueue(&s);coun t+;if(s.datas.fr on t=1)break;printf("从第%d号战士开始计数才能让排长最后一个留下来而不去执行任务。n",start);break;case 4:exit(0);goto abc;6.实验总结：通过这次课程设计我又学到了很多东西，如程序的模块化设计思想，同时也加深了对 数据结构这门课程的理解和学会了如何在实际中应用数据结构。在做程序之前，觉得敢死队这个问题，很难解决。在通过自己一次次的画图，推算 结果时，明白了该程序的主要思路。本程序其实质是约瑟夫环问题，在明白程序的实质 后开始，选择数据的存储结构类型，最开始想到的是循环队列，但是队列是在队头进行 出队列操作，队尾入队列，不能进行任意删除元素的操作，没有多想就放弃了。后来在 查阅资料时，发现可以通过，对队头的元素删除后又入队列，将头指针移到要删除的元 素的位置。以前总是不清楚数据结构它有什么用途。通过这此课程设计，明白我们所学的虽然 只是课本知识，但很多时候，我们可以利用所学的来解决生活中碰到的一些问题。同一 个问题往往可以用不同的方法来解决。