数据结构课程设计报告.docx

数据结构课程设计报告.docx

《数据结构课程设计报告.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计报告.docx（11页珍藏版）》请在冰点文库上搜索。

数据结构课程设计报告

数据结构课程设计报告

题目：

敢死队问题

院（系）：

计算机工程学院

专业：

嵌入式系统开发与设计

班级：

嵌入式109

（1）

学生：

范永亮

指导教师：

寇海洲孙成富

邱军林殷路

2010年12月

目录

一、设计目的1

二、设计内容1

三、程序设计步骤1

四、调试分析7

五、测试结果7

六、课程设计小结9

一、设计目的

1、能让学生们做一些与实际有关联的程序，提高学生们的动手能力,在实践中学习编程,并提高自己.

2、能让我们学习到更多的知识,和他人讨论来提高,分享他人的学习经验.

3、。

学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。

4、培养我们的自主学习能力.

二、设计内容

1、系统名称：

敢死队问题

•有M个敢死队队员要炸掉敌人的一个碉堡，谁都不想去，排长决定采用轮回数数的办法来决定谁去，如果前一个战士没完成任务，则再派另一个战士去，现给每个战士编号，大家围坐一圈，随便从某一战士开始计数，当数到5时，对应的战士就去执行任务，且此战士不在参加下一轮计数。

如果此战士没完成任务，再从下一个战士开始数数，被数到第5时，此战士接着去执行任务，以此类推，直到完成为止。

•排长是不愿意去的，假设排长为1号，请设计一程序，求出从第几个战士开始计数才能让排长最后一个留下来而不去执行任务。

2、要求：

•至少采用两种不同的数据结构的方法实现。

如果采用三种以上者，可加分

三、程序设计步骤

1）功能分析说明图：

2）采用主要的数据结构类型。

链表的形式

#include

#include

usingnamespacestd;

//定义结点

typedefstructnode{

intnum;

node*next;

}lnode;

typedefstruct{

lnode*cl;

}linklist;

voidmain（）

{

intM,i;

intstart,count;

linklists;

cout<<"enterthevalueofM:

";

cin>>M;

for（start=1;start<=M;start++）//start为测试起点

{

//初始化链表

lnode*p=newlnode;

s.cl=p;

s.cl->num=1;

for（i=2;i<=M-1;i++）

{

lnode*q=newlnode;

q->num=i;

p->next=q;

p=q;

}

lnode*t=newlnode;

t->num=M;

p->next=t;

p=t;

t->next=s.cl;

//找到开始人

p=s.cl;

for（i=1;i

{

p=p->next;

}

count=0;//初始计数为0

//开始循环计数

while（count<=M-1）

{

for（i=1;i<5;i++）

{

t=p;

p=t->next;

}

t->next=p->next;

count++;

p=t->next;

}

if（p->num==1）

break;

}

cout<<"startfrom:

"<

}

队列的形式

#include"stdafx.h"

#include

usingnamespacestd;

#defineQueueSize100//队列空间最多为100

//队列的类定义

typedefstruct{

intdata[QueueSize];

intfront;//头指针

intrear;//尾指针

intcount;//计数器

}CirQueue;

//把队列初始化

voidInitial（CirQueue*Q）

{

Q->front=Q->rear=0;

Q->count=0;

}

//判断是否为空

intIsEmpty（CirQueue*Q）

{

returnQ->front==Q->rear;

}

//判断是否为满

intIsFull（CirQueue*Q）

{

returnQ->rear==QueueSize-1+Q->front;

}

//新元素x进队列

voidEnQueue（CirQueue*Q,intx）

{

if（IsFull（Q））

{

printf（"队列上溢"）;

exit

（1）;//上溢,退出运行

}

Q->count++;//队列元素个数加1

Q->data[Q->rear]=x;//新元素插入队尾

Q->rear=（Q->rear+1）%QueueSize;//循环意义下将尾指针加1

}

//队头元素出队列

intDeQueue（CirQueue*Q）

{

inttemp;

if（IsEmpty（Q））

{

printf（"队列为空"）;

exit

（1）;//下溢,退出运行

}

temp=Q->data[Q->front];

Q->count--;//队列元素个数减1

Q->front=（Q->front+1）%QueueSize;//循环意义下的头指针加1

returntemp;

}

voidmain（）

{

intM,i,start,count,j;

CirQueues;//队列s

cout<<"enterthevalueofM:

";//输出

cin>>M;//输入

for（start=1;start<=M;start++）

{

Initial（&s）;//将队列s初始化

for（i=1;i<=M;i++）

{

EnQueue（&s,i）;//调用进队列

}

for（i=1;i

{

j=DeQueue（&s）;//调用出队列

EnQueue（&s,j）;//调用进队列

}

count=1;//计数1

while（count

{

for（i=1;i<5;i++）

{

j=DeQueue（&s）;//调用出队列

EnQueue（&s,j）;//调用进队列

}

j=DeQueue（&s）;//调用出队列

count++;

}

if（s.data[s.front]==1）

break;//到排长跳出

}

cout<<"startfrom:

"<

}

1、定义航班信息

四、调试分析

调试的过程中，我发现调试时不能太心急,要先编译,编译成功后,才能进行调试,不然很容易死机.

从本实习题的编制过程中容易看出，链表和队列的应用广泛，队列的存储结构，构成链栈或链队列使用。

五、测试结果

六、课程设计小结：

通过这次课程设计我又学到了很多东西,如程序的模块化设计思想，同时也加深了对数据结构这门课程的理解和学会了如何在实际中应用数据结构。

在做程序之前，觉得敢死队这个问题，很难解决。

在通过自己一次次的画图，推算结果时，明白了该程序的主要思路。

本程序其实质是约瑟夫环问题，在明白程序的实质后开始，选择数据的存储结构类型，最开始想到的是循环队列，但是队列是在队头进行出队列操作，队尾入队列，不能进行任意删除元素的操作，没有多想就放弃了。

后来在查阅资料时，发现可以通过，对队头的元素删除后又入队列，将头指针移到要删除的元素的位置。

以前总是不清楚数据结构它有什么用途。

通过这此课程设计，明白我们所学的虽然只是课本知识，但很多时候，我们可以利用所学的来解决生活中碰到的一些问题。

同一个问题往往可以用不同的方法来解决。