敢死队问题课程设计数据结构 c语言.doc

发布时间：2022-06-08 发布人：admin 分类：说明书资料大小：0.25M 资料格式：doc 举报版权申诉

第1页 / 共15页

第2页 / 共15页

第3页 / 共15页

第4页 / 共15页

第5页 / 共15页

第6页 / 共15页

第7页 / 共15页

第8页 / 共15页

文本预览

课程设计课程设计名称：算法分析与综合课程设计专业班级：计科 0604 班学生姓名：罗化学号： 20064140426 指导教师：白浩课程设计时间： 2008 年 5 月 23 日

1 需求分析本次课程设计题目主要是要求用两种数据结构方法实现敢死队问题。题目中用到 1 到 M 个 int 数据，采用链表和队列存储，由于是轮回数数，需要循环，因此所用的链表是单向循环链表，所用的队列是循环队列。战士去执行任务，若没有完成任务，则需要把该战士的号码从队列或者链表中删除，因此题目要用到链表结点的删除和队列元素的删除。由于要求出从第几号战士开始计数才能让排长最后一个留下来而不去执行任务，所以程序从 1 号到 M 号逐个开始计数，从计数的战士开始的第五个战士去执行任务，若没完成任务，则删除之，从被删除战士下一个号码开始计数，后边的第五个战士接着开始去执行任务，若没完成任务，则删除之，如此循环，直到最后一个战士，若最后一个战士是排长，即 1 号，则终止循环，记下开始计数的战士的号码即为所求。即：（1）构造数据结构（2）数据输入（3）执行任务队员出列（4）输出要求数值（5）结束 2 概要设计 2.1 单向循环链表实现 1．定义结点 2．初始化链表 3．定义变量并初始化 4．循环开始 5．开始计数, 数到 5 的战士出列 6．终止循环，记下开始计数的号码 7．输出 2.2 循环队列实现 1．定义结构体类型 2. 初始化队列 3. 循环开始 4．清空队列 5. 删除对头元素 6. 把对头删除的元素添加到队尾 1

7.终止循环并输出 2.3 输出 1. 输入 1：单向循环链表实现 2．输入 2：循环队列实现 3. 输入 3：退出 3 运行环境 3.1 硬件环境 PC 3.2 软件环境（1）Windows XP （2）Microsoft Visual C++6.0 4 开发工具和编程语言 4.1 开发工具 Microsoft Visual C++6.0 4.2 编程语言 C 语言 5 详细设计 5.1 单向循环链表实现过程：定义结点： ypedef struct node { int num; struct node *next; }slink; 初始化链表： p=l=(slink *)malloc(LEN); l->num=1; for(i=2;i<=M-1;i++) { 2

q=(slink *)malloc(LEN); q->num=i; p->next=q; p=q; } t=(slink *)malloc(LEN); t->num=M; p->next=t; t->next=l; 开始计数, 数到 5 的战士出列： p=l; for(i=1;inext; } for(count=1;countnext; } t->next=p->next; p=t->next; } 终止循环并输出： if(p->num==1) break; } printf("第一个被点的号应为: %d\n",start); 5.2 循环队列实现过程：结构体类型定义： typedef struct { int *base; int num; int front;//头指针 int rear;//尾指针 }CirQueue; 初始化操作： void InitQueue(CirQueue *Q) { 3

Q->base=(int *)malloc(QueueSize * sizeof(int)); Q->front=Q->rear=0; } 进队列： int EnQueue(CirQueue *Q,int x) { if (IsFull(Q)) { printf("队列上溢"); //上溢,退出运行 return(0); } Q->base[Q->rear]=x; //新元素插入队尾 Q->rear=(Q->rear+1)%QueueSize; //将尾指针加 1 return (1); } 出队列： int DeQueue(CirQueue *Q) { int t; if(IsEmpty(Q)) { printf("队列为空"); //下溢,退出运行 return 0; } t=Q->base[Q->front]; Q->front=(Q->front+1)%QueueSize; //头指针加 1 return t; } 循环实现找到号码并输出： void Queue() { CirQueue *s; int M,i,start,count,j; s=(CirQueue *)malloc(sizeof(CirQueue)); InitQueue(s); printf("请输入 M 的大小（队列实现）:"); scanf("%d",&M); for(start=1;start<=M;start++)//start 为测试起点 { SetNull(s); for(i=1;i<=M;i++) 4

{ EnQueue(s,i); } for(i=1;ibase[s->front]==1) break; } printf("第一个被点的号应为:%d\n",start); } 5.3 源代码如下： #include #include #define LEN sizeof(slink) #define QueueSize 100 typedef struct node { //定义结点 //假定预分配的队列空间最多为 100 个元素 int num; struct node *next; }slink; typedef struct { int *base; int front;//头指针 int rear;//尾指针 }CirQueue; void List() { //单向循环链表实现 typedef struct node { int num; //定义结点 5

struct node *next; }slink; int M; int i; int start,count; slink * l,*p,*q,*t; printf("请输入 M 的大小（链表实现）:"); scanf("%d",&M); for(start=1;start<=M;start++)//start 为测试起点 { p=l=(slink *)malloc(LEN); l->num=1; for(i=2;i<=M-1;i++) { //初始化链表 q=(slink *)malloc(LEN); q->num=i; p->next=q; p=q; } t=(slink *)malloc(LEN); t->num=M; p->next=t; t->next=l; p=l; //找到起点 for(i=1;inext; } for(count=1;countnext; } t->next=p->next; p=t->next; } if(p->num==1) break; } printf("第一个被点的号应为: %d\n",start); } 6

//循环队列实现 //初始化操作 void InitQueue(CirQueue *Q) { Q->base=(int *)malloc(QueueSize * sizeof(int)); Q->front=Q->rear=0; } //置队列空 void SetNull(CirQueue *Q) { Q->front=Q->rear=0; } // 判队列空 int IsEmpty(CirQueue *Q) { return Q->front==Q->rear; } //判队列满 int IsFull(CirQueue *Q) { return Q->front==(Q->rear+1)%QueueSize; } //进队列 int EnQueue(CirQueue *Q,int x) { if (IsFull(Q)) { printf("队列上溢"); //上溢,退出运行 return(0); } Q->base[Q->rear]=x; //新元素插入队尾 Q->rear=(Q->rear+1)%QueueSize; //将尾指针加 1 return (1); } //出队列 int DeQueue(CirQueue *Q) { int t; if(IsEmpty(Q)) 7

分享到：

赞收藏

资料库

敢死队问题课程设计数据结构 c语言.doc

相关推荐

课程资源

热门标签

最新资料