南航 计算机实践报告数据结构Word文档下载推荐.docx
- 文档编号:8570417
- 上传时间:2023-05-11
- 格式:DOCX
- 页数:51
- 大小:557.11KB
南航 计算机实践报告数据结构Word文档下载推荐.docx
《南航 计算机实践报告数据结构Word文档下载推荐.docx》由会员分享,可在线阅读,更多相关《南航 计算机实践报告数据结构Word文档下载推荐.docx(51页珍藏版)》请在冰点文库上搜索。
3)主函数流程图
主程序:
#include
<
stdio.h>
malloc.h>
stdlib.h>
time.h>
typedef
int
ElemType;
struct
node
{
ElemType
data;
num;
node
*next;
}SLNODE;
//单链表的定义
*create_sl(int
n);
void
Josephus(SLNODE
*head,int
n,int
m);
main()
//主函数
SLNODE
*head;
n,m;
time_t
rawtime;
tm
*
timeinfo;
time
(&
rawtime);
timeinfo
=
localtime
head=(SLNODE
*)malloc(sizeof(SLNODE));
printf("
实验名称:
试验一:
约瑟夫斯问题求解\n"
);
//初始界面
*******29\n"
陈叶杭\n"
/-------------------/\n"
printf
("
程序运行开始,Current
local
and
date:
%s"
asctime(timeinfo));
请输入总人数n=\n"
scanf("
%d"
&
请输入报数上限值(为正整数)m=\n"
head=create_sl(n);
//创建单链表
Josephus(head,n,m);
程序运行结束,Current
return
0;
}
n)
*p,*s,*head;
x;
a;
p=head;
head->
next=head;
for(a=1;
a<
=n;
a++)
//循环直到输入n个密码值跳出循环
s=(SLNODE
请输入第%d个人的密码值\n"
a);
x);
s->
data=x;
num=a;
if(head->
next==head)
head=s;
else
p->
next=s;
p=s;
head;
m)//约瑟夫斯问题求解
*p,*q;
i;
出列序列:
"
while(p->
next!
=p)
{
for(i=1;
i<
m;
i++)
//程序运行到第m个人跳出循环
q=p;
p=p->
next;
}
m=p->
//读取新的密码值
%4d"
p->
num);
q->
next=p->
//删除p节点
free(p);
p=q->
%4d\n"
运行结果:
实验调试和感想
开始先去搜索程序开始和结束时间代码,发现有错误,一直以为是格式错了,后来反复查验后发现是开始没有调用时间函数。
主程序调试时,开始有一个错误,也是再找原因,后来仔细检查后,发现是链表定义错误,定义成循环链表,应该是用单链表做。
后来改过来后就没错了。
由于是第一次做数据结构的实验,而上学期的C++也因长时间没有碰过而稍显手生,在码程序的过程中遇到了很多问题,但通过翻看教材已基本解决。
约瑟夫虽然构思起来比较简单,但实际执行时经常出现各种意想不到的问题,如输出次数不对等等,通过将近两天的调试才终于完成,很有成就感。
接下来如果有时间可以在原程序中加入其实位置编号,使得起始位置也可由用户自定。
停车场管理问题
设停车场是一个可停放n辆汽车的狭长通道,且只有一个大门可供汽车进出。
汽车在停车场内按车辆到达时间的先后顺序,依次由北向南排列。
若停车场内已经停满n辆车,那么后来的车只能在门外的便车道上等候。
一旦有车开走,则排在便道上的第一辆车即可开入。
当停车场内某辆车要离开时,在它之后进入的车辆必须退出车场为它开路,待该辆车开出大门外,其他车辆再按原次序进入车场。
每辆停放在车场的车在它离开停车场时必须按照它停留的时间长短缴纳费用。
试为停车场编制按上述要求进行管理的模拟程序。
基本要求:
以栈模拟停车场,以队列模拟车场外的便道,按照终端读入数据的序列进行模拟管理。
每一组输入数据包括三个数据项:
汽车的“到达”(‘A’表示)或“离去”(‘D’表示)信息、汽车标识(车牌号)以及到达或离去的时刻。
对每一组输入数据进行操作后的输出信息为:
若是车辆到达,则输出汽车在停车场内或者便道上的停车位置;
若是要离去,则输出汽车在停车场停留的时间和应缴纳的费用(便道上停留的时间不收费)。
栈以顺序结构实现,队列以链表结构实现。
设n=2,输入数据为:
(‘A’,1,5),(‘A’,2,10),(‘D’,1,5),(‘A’,3,20),(‘A’,4,25),(‘A’,5,30),(‘D’,2,35),(‘D’,4,40),(‘E’,0,0)。
主程序模块:
出栈:
判断栈是否为空:
判断栈是否已满:
判断队列是否为空:
出队:
关于算法,题中解析说的已经很清楚了,主要是编程时用到了一些数据结构需要用单独的类定义出来,使得程序清晰完整。
这一问题一个重要的思路是对于汽车出停车场时,由于不一定每次都是最外面的车出去,所以需要用到另一个栈存储车辆。
如图,将要出停车场的车i上面的车都倒入另一个栈中,然后将i删除,再将栈Park2中的都倒回停车场park1中即可。
对于数据的输出:
输入A:
输出在停车场或者候车场的位置,编号由北向南1~2;
输入D:
输出车辆停靠时间(出栈时间减去入栈时间)(这里涉及到一个计算:
并不是出去时间减去到达时间,因为有可能到达后在候车区等待一段时间,这段时间不能算收费时间),和收费。
输入P时按照从栈顶到栈底输出车辆车牌号;
输入W时,输出候车区车辆总数;
输入E,退出程序
这个程序设计需要栈和队列的相关操作,所以在程序设计过程中逐渐熟悉了栈和队列的相关操作,由于像栈,队列这样,有判断栈空,栈满,入栈,出栈这样的操作,使自己更加熟悉了栈和队列的相关知识。
主程序
#include<
#defineOK1
#defineERROR0
#defineMAX_STACK_SIZE2/*停车场大小*/
typedefintStackData;
typedefintQueueData;
typedefintElemType;
typedefstructNode
intNo;
intTimeinit;
}Node;
typedefstructQueueNode/*队列*/
structNodedata;
structQueueNode*next;
}QueueNode;
typedefstructLinkQueue/*链式队列*/
structQueueNode*rear,*front;
}LinkQueue;
typedefstructSqStackNode/*栈*/
{
inttop;
intbottom;
structNodestack_array[MAX_STACK_SIZE+1];
}SqStackNode;
SqStackNode*InitStack()/*初始化栈*/
SqStackNode*S=(SqStackNode*)malloc(sizeof(SqStackNode));
S->
bottom=S->
top=0;
return(S);
intFullStack(SqStackNode*S)
returnS->
top==MAX_STACK_SIZE;
intpushStack(SqStackNode*S,Nodedata)/*入栈*/
if(FullStack(S))
{
returnERROR;
}
top++;
(S->
stack_array[S->
top]).No=data.No;
top]).Timeinit=data.Timeinit;
returnOK;
intpopStack(SqStackNode*S,Node*data)/*弹出栈顶元素*/
if(S->
top==0)
(*data).No=(S->
top]).No;
(*data).Timeinit=(S->
top]).Timeinit;
top--;
intFindStack(SqStackNode*S,Nodedata)/*搜索栈内元素*/
inti;
for(i=1;
=S->
top;
i++)
stack_array[i].No==data.No)
returnERROR;
LinkQueue*InitQueue(void)/*初始化队列*/
LinkQueue*Q=(LinkQueue*)malloc(sizeof(LinkQueue));
Q->
rear=Q->
front=NULL;
returnQ;
intQueueEmpty(LinkQueue*Q)
returnQ->
front==NULL;
intGetFrontQueue(LinkQueue*Q,Node*data)/*取队首*/
if(QueueEmpty(Q))return0;
(*data).No=(Q->
front->
data).Timeinit;
return1;
intEnQueue(LinkQueue**Q,Nodedata)/*入队*/
QueueNode*p=(QueueNode*)malloc(sizeof(QueueNode));
(p->
data).No=data.No;
data).Timeinit=data.Timeinit;
p->
next=NULL;
if((*Q)->
front==NULL)
(*Q)->
front=(*Q)->
rear=p;
else
rear=(*Q)->
rear->
next=p;
intDeQueue(LinkQueue**Q,Node*data)/*出队*/
if(QueueEmpty(*Q))
return0;
QueueNode*p=(*Q)->
front;
(*data).No=p->
data.No;
(*data).Timeinit=p->
data.Timeinit;
(*Q)->
if((*Q)->
front==NULL)(*Q)->
rear=NULL;
free(p);
Parking(LinkQueue**Q,SqStackNode*S)/*停车*/
Nodedata;
printf("
请输入车牌号\n"
scanf("
%d"
data.No);
请输入停车时间\n"
data.Timeinit);
if(S->
{
printf("
该车已停好\n"
return;
}
EnQueue(Q,data);
/*进入候车队列*/
while(!
QueueEmpty(*Q))
if(FullStack(S))
printf("
请稍等...\n"
break;
else
DeQueue(Q,&
data);
/*候车队列车出队*/
pushStack(S,data);
/*进入停放栈*/
停车成功\n"
return;
leaving(SqStackNode*S,SqStackNode*B,LinkQueue**Q)/*离开停车场*/
bottom==S->
top)
停车场内无车:
\n"
inti,n;
floatcharge;
intparking_time;
请输入车牌号:
scanf("
i);
请输入离开时间:
data.No=i;
if(!
FindStack(S,data))
车库内无此车\n"
while(S->
top].No!
=i)/*此车后的车依次出栈入让路栈*/
{
popStack(S,&
pushStack(B,data);
}
popStack(S,&
/*此车出停放栈*/
parking_time=n-data.Timeinit;
/*计算收费*/
charge=parking_time*10;
车辆:
%d停车时长:
从%d到%d共%d收费(10元/h):
$%g\n"
data.No,data.Timeinit,n,parking_time,charge);
while(B->
bottom!
=B->
top)/*让路栈内的车依次出栈入停放栈*/
popStack(B,&
pushStack(S,data);
while(!
FullStack(S)&
&
(!
QueueEmpty(*Q)))/*等待队列的车进入停车场栈*/
DeQueue(Q,&
data.Timeinit=n;
}
situationH(LinkQueue**Q)/*查看候车场车数*/
intparking_time;
structQueueNode*p;
intwait_count=0;
p=(*Q)->
if(p==NULL)
Waitingcar:
0\n"
else
do
wait_count++;
p=p->
}while(p!
=NULL);
等待的车辆有:
%d\n"
wait_count);
situationP(SqStackNode*P)/*查看停车场车数*/
if(P->
top==P->
bottom)
停车场内的没有车\n"
停车场内的车辆有%d\n"
P->
top);
intmain()
inti,No,Time;
charA;
SqStackNode*park;
SqStackNode*back;
LinkQueue*wait;
park=InitStack();
back=InitStack();
wait=InitQueue();
while
(1)
system("
cls\n"
***********************实验2:
停车场管理问题***********************\n"
姓名:
学号:
031520629\n"
\nA.停车\n"
B.取车\n"
C.查看停车场车数\n"
D.查看候车场车数\n"
E.离开\n"
\n请输入你要进行的操作:
%c,%d,%d"
A,&
No,&
Time);
if(A=='
A'
)
i=1;
elseif(A=='
B'
i=2;
C'
i=3;
D'
i=4;
E'
i=5;
输入有误请重新输入\n"
getchar();
system("
PAUSE"
switch(i)
switch(i)
case1:
/*停车*/
{
system("
Parking(&
wait,park);
getchar();
break;
}
case2:
/*离开*/
leaving(park,back,&
wait);
case3:
/*查看停车情况*/
situationP(park);
case4:
/*查看候车情况*/
system("
situationH(&
case5:
/*退出*/
return0;
default:
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 南航 计算机实践报告 数据结构 计算机 实践 报告