《中南大学数据结构实验报告(共24页).docx》由会员分享，可在线阅读，更多相关《中南大学数据结构实验报告(共24页).docx（25页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精选优质文档-倾情为你奉上中南大学数据结构试验报告题 目 实验二 学生姓名 王云鹏 学 号 指导老师 郑 瑾 学 院 计算机学院 专业班级 物联网1802 完成时间 2020.6 指导老师评定 签名 实验二1. 需求分析1栈和队列操作的实现（验证性实验） 问题描述 (1) 建立一个顺序栈。 (2) 建立一个循环顺序队列。 (3) 分别实现栈和队列的基本操作。 2数制转换问题（设计性实验） 问题描述 十进制数n和其他d进制数的转换是计算机实现计算的基本问题，其解决方案很多，其中最简单的 方法基于下列原理，即除d取余法。例如，(1348)10(2504)8。 N n div 8 n mod 8 1
2、348 168 4 168 21 0 21 2 5 2 0 2 从中可以看出，最先产生的余数4是转换结果的最低位，这正好符合栈先进后出的特性，所以可 以用顺序栈来模拟这个过程。 基本要求 从键盘输入任意一个非负的十进制整数，打印输出与其等值的八进制数。由于上述的计算过程是 从低位到高位顺序产生的八进制数的各个数位，而打印输出一般来说应从高位到低位进行，恰好与计 算过程相反。因此，可以先将计算过程中得到的八进制数的各位进栈，待相对应的八进制数的各位均 产生以后，再使其按顺序出栈，并打印输出。这样就得到了与输入的十进制数相对应的八进制数。 测试数据 由读者依据软件工程的测试技术自己确定。注意测试边
3、界数据5. 停车场管理（综合性实验） 问题描述 设停车场内是一个可停放n辆汽车的狭长区域，且只有一个大门可供汽车进出。在停车场内，汽 车按到达时间的先后顺序，依次由北向南排列（假设大门在最南端，最先到达的那辆车停放在车场的 最北端）。若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候。一旦有车开走，则排在 便道上的第一辆车即可开入。当停车场内某辆车要离开时，在它之后开入的车辆必须先退出车场为它 让路，待该车开出大门外，其他车再按原次序返回停车场。每辆停放在车场的车离开停车场时，必须 按其停留时间的长短交费。试为停车场编制按上述要求进行管理的模拟程序。 测试数据 设n2，输入数据为(A,
4、 1, 5)、(A, 2, 10)、(D, 1, 15)、(A, 3, 20)、(A, 4, 25)、(A, 5, 30)、(D, 2, 35)、 (D, 4, 40)和(E, 0, 0)。每一组输入数据包括3个数据项：汽车“到达”或“离去”信息、汽车牌照号码 及到达或离去的时刻，其中，“A”表示到达，“D”表示离去，“E”表示输入结束。基本要求 以顺序栈模拟停车场，以链队列模拟便道，按照从终端读入的输入数据序列进行模拟管理。每一 组输入数据包括3项：是“到达”还是“离去”、汽车牌照号码及“到达”或“离去”的时刻。对每一 组输入数据进行操作后的输出数据为：如果是到达的车辆，则输出其在停车场内或
5、便道上的停车位置； 如果是离去的车辆，则输出其在停车场内的停留时间和应交的费用（在便道上停留的时间不收费）。 栈以顺序结构实现，队列以链表实现。 实现提示 需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车，也用顺序存储结构实 现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含两个数据项：汽车的牌照 号码和进入停车场的时刻。 选作内容 (1) 两个栈共享空间，思考应开辟数组的空间是多少？ (2) 汽车可有不同种类，则它们的占地面积不同，收费标准也不同，如1辆客车和1.5辆小汽车的 占地面积相同，1辆十轮卡车占地面积相当于3辆小汽车的占地面积。 (3) 汽车可以直接
6、从便道上开走，此时排在它前面的汽车要先开走让路，然后再依次排到队尾。 (4) 停放在便道上的汽车也收费，收费标准比停放在停车场的车低，请思考如何修改结构以满足 这种要求。2. 概要设计n 验证性实验函数：n 设计性实验函数：n 综合性实验函数：3. 详细设计n 验证性实验#include#include#definemaxsize10typedefintElemType;typedefstructElemType*base;ElemTypetop;/下标stack;stack*Init()/初始化函数stack*s;s-base=(ElemType*)malloc(maxsize*sizeof
7、(ElemType);/申请空间if(s=NULL)printf(mallocfailinInit);returnNULL;s-top=0;returns;voidpush(stack*s,ElemTypee)/压栈if(s-top=maxsize)/溢出printf(stackisoverflow);return;*(s-base+s-top)=e;/压入s-top+;/栈顶上移intpop(stack*s)/出栈if(s-top=0)/空栈printf(stackisunderflow);return0;s-top-;/栈顶下移return*(s-base+s-top);/返回移出的值in
8、tgetTop(stack*s)/取栈顶，而不动栈顶指针if(s-top=0)/空栈printf(stackisunderflow);return0;return*(s-base+s-top-1);voidprint(stack*s)/从栈顶到栈底打印栈printf(stack:n);for(inti=s-top-1;i=0;i-)printf(%dn,*(s-base+i);intmain()stack*s=(stack*)malloc(sizeof(stack);/产生一个栈s-base=(ElemType*)malloc(maxsize*sizeof(ElemType);if(s=NUL
9、L)printf(mallocfailinmain);return0;s-top=0;/栈顶指针初始为0，该指针仅代表数组的下标push(s,1);push(s,2);push(s,3);print(s);printf(pop:%dn,pop(s);print(s);printf(getTop:%dn,getTop(s);return0;#include#include#definequeuesize100#defineoverflow1#defineunderflow-1#defineok0typedefintElemType;typedefstructsqueueElemTypesqque
10、uesize;ElemTypefront;ElemTyperear;queue;inten_cycque(queue*q,ElemTypex)/入队inti=(q-rear+1)%queuesize;/循环队列if(i=q-front)/空出一个不用printf(overflown);/溢出returnoverflow;q-sqq-rear=x;/写入,rear指向队列最后一个元素后面的位置q-rear=i;/尾指针移动returnok;intdl_cycque(queue*q,ElemType*x)/出队if(q-front=q-rear)/空队printf(underflown);retu
11、rnunderflow;*x=q-sqq-front;/用x带出q-front=(q-front+1)%queuesize;/头指针后移，从队头删除returnok;intprint(queue*q)/打印队列if(q-front=q-rear)/溢出printf(underflown);returnunderflow;elseif(q-rear+1)%queuesize=q-front)/空队printf(overflow);returnoverflow;elseif(q-rearq-front)/若队尾指针在队头指针后面for(inti=q-front;irear;i+)/遍历打印prin
12、tf(%dn,q-sqi);elseif(q-rearfront)/若队尾指针在队头指针前面for(inti=q-front;isqi);for(inti=0;irear;i+)printf(%dn,q-sqi);intmain()queueq;/生成循环队列q.front=0;/使队头队尾皆为0q.rear=0;en_cycque(&q,1);en_cycque(&q,2);en_cycque(&q,3);print(&q);inte;/带出删掉的元素dl_cycque(&q,&e);/printf(%dn,e);/查看删掉的元素print(&q);return0;n 设计性实验#inclu
13、de#include#definemaxsize10typedefintElemType;typedefstructElemType*base;ElemTypetop;/下标stack;voidpush(stack*s,ElemTypee)/压栈if(s-top=maxsize)/溢出printf(stackisoverflow);return;*(s-base+s-top)=e;/压入s-top+;/栈顶上移voidprint(stack*s)/从栈顶到栈底打印栈for(inti=s-top-1;i=0;i-)printf(%d,*(s-base+i);intmain()/产生一个栈stac
14、k*s=(stack*)malloc(sizeof(stack);/产生一个栈s-base=(ElemType*)malloc(maxsize*sizeof(ElemType);if(s=NULL)printf(mallocfailinmain);return0;s-top=0;/栈顶指针初始为0，该指针仅代表数组的下标/转换数制intd=8;/要转化为的数制intdest=1348;/目标数intcout=dest;/记录，用于输出intremainder=0;/余数while(1)remainder=dest%d;/取余，压到栈中push(s,remainder);dest=dest/d;
15、if(dest=0)break;printf(十进制数%d转化为八进制数后为：,cout);print(s);n 综合性实验#include#include/栈#definemaxsize2/栈的空间#definefull1#definenotfull-1#defineempty0#definenotempty1#defineok0#definefail1#defineunderflow-1typedefintElemType;typedefstruct/栈ElemType*base;/基指针ElemTypetop;/下标stack;voidInit(stack*s)/初始化函数s-base=
16、(ElemType*)malloc(maxsize*sizeof(ElemType);/申请空间if(s=NULL)printf(mallocfailinInit);return;s-top=0;/初始化时下标为0voidpush(stack*s,ElemTypee)/压栈if(s-top=maxsize)/溢出printf(stackisoverflow);return;*(s-base+s-top)=e;/压入s-top+;/栈顶上移intpop(stack*s)/出栈if(s-top=0)/空栈printf(stackisunderflow);return0;s-top-;/栈顶下移re
17、turn*(s-base+s-top);/返回移出的值intisfull(stacks)/是否满栈if(s.top=maxsize)returnfull;elsereturnnotfull;intisempty(stacks)/是否空栈if(s.top=0)returnempty;elsereturnnotempty;voidstack_print(stack*s)/从栈顶到栈底打印栈printf(stack:n);for(inti=s-top-1;i=0;i-)printf(%dn,*(s-base+i);/队列typedefintQElemType;typedefstructQNode/节
18、点QElemTypedata;structQNode*next;/链队列QNode;typedefstructQNode*front;/头指针，带空头节点QNode*rear;/尾指针LinkQueue;intInitQueue(LinkQueue*q)/初始化q-front=q-rear=(QNode*)malloc(sizeof(QNode);/申请空间，front指向头节点（空的）if(q-front=NULL)/若是申请失败printf(mallocfailinInitQueue);returnfail;q-front-next=NULL;/空队的头节点下一个自然为空returnok;
19、intEnQueue(LinkQueue*q,QElemTypee)/插入QNode*p=(QNode*)malloc(sizeof(QNode);/将要插入的节点if(p=NULL)printf(mallocfailinEnQueue);returnfail;p-data=e;/p的值为ep-next=NULL;/在尾部插入，其下一个为空q-rear-next=p;/接到尾节点的下一个q-rear=p;/p为新的尾节点returnok;intDeQueue(LinkQueue*q,QElemType*e)/删除if(q-front=q-rear)/空队无法删除printf(underflow
20、n);returnunderflow;QNode*p=q-front-next;/需要删除的节点*e=p-data;/用e带出删掉的值q-front-next=p-next;/将要删除的节点从链中断开if(q-rear=p)/加入原来队中只有一个节点q-rear=q-front;/删完后为空队，头节点与尾节点指到一起free(p);returnok;intqueue_isempty(LinkQueueq)/判断是否空队if(q.front=q.rear)returnempty;elsereturnnotempty;intqueue_print(LinkQueueq)/打印队列，从队头到队尾QN
21、ode*p=q.front;/头节点为空，不需要打印while(1)p=p-next;/下一个节点printf(%dn,p-data);/打印值if(p=q.rear)/到队尾退出break;/parkstaticintpos_walk=0;/静态全局变量，用于记录可以获得的便道的停车位置intarrive(stack*park,stack*time,LinkQueue*walk,intlicense,intarrival)/若有车到达if(isfull(*park)=notfull)/若停车场还有位置push(park,license);/将车牌号和到达时间压入栈push(time,arri
22、val);printf(gotNO.%dpositioninparkn,park-top);/输出在停车场中的位置elseif(isfull(*park)=full)/若停车场已满，新来的车停入便道pos_walk+;/便道进入一辆车EnQueue(walk,license);/将车牌号压入便道栈printf(gotNO.%dpositioninsidewalkn,pos_walk);/输出在便道中的位置returnok;intdepart(stack*park,stack*time,LinkQueue*walk,intlicense,intarrival)/若有车要离开stacktemp_l
23、icense;/用来存暂时退开的车Init(&temp_license);stacktemp_time;Init(&temp_time);while(1)/1号车离开，先将2号车存入另外一个栈，pop(1),push(2)intmed_license=pop(park);/取出的车牌号intmed_time=pop(time);/被取出车的进入时间if(med_license!=license)/不是要离开的车，就存入另一个栈push(&temp_license,med_license);push(&temp_time,med_time);continue;elseif(med_license
24、=license)/是要离开的车，输出停车时间和停车费，并将另外一个栈的车还回来intpark_time=arrival-med_time;/停车时间intmoneyEvery=10;/每单位时间停车费intmoney=park_time*moneyEvery;/停车费printf(thecarof%dhaveparkedfor%dtimen,license,park_time);/输出停车时间printf(feesis%dn,money);/输出停车费while(isempty(temp_license)=notempty)/若temp未空，就一直出栈/从temp还回暂时退开的车push(p
25、ark,pop(&temp_license);push(time,pop(&temp_time);break;/还完车就算这辆车成功离开/离开一辆车后，若便道上有车等待，则车进入停车场if(queue_isempty(*walk)=notempty)/若便道上有车等待QElemTypee;DeQueue(walk,&e);/从便道驶出一辆车pos_walk-;/便道停车位置减一push(park,e);/走一辆车就进一辆车push(time,arrival);/其进入停车场时间就是上一辆车离开的时间returnok;intread(stack*park,stack*time,LinkQueue
26、*walk)/读入数据，并处理while(1)charorder;/A或D或Eintlicense;/车牌号intarrival;/到达时间scanf(%c,%d,%d,&order,&license,&arrival);if(order=A)/若有车到达arrive(park,time,walk,license,arrival);elseif(order=D)/若有车离开depart(park,time,walk,license,arrival);elseif(order=E)/模拟结束break;returnok;/主函数intmain()stackpark;/停车场Init(&park)
27、;stacktime;/进入停车场的时间Init(&time);LinkQueuewalk;/便道InitQueue(&walk);read(&park,&time,&walk);/读入处理数据return0;4.调试分析1) 采用IDE中自带的调试功能进行调试，手动添加断点和查看程序。2) 对设计和编码的讨论和分析。该程序实现了顺序栈的操作。分析程序代码的质量，主要从以下几个方面考虑。 正确性。在一定的数据范围内，该程序能实现所需功能，所以正确性是没有问题的。 健壮性。在一定的数据输入范围内，该程序能较好的实现操作。但是如果输入数 据非法，该程序还是可能会产生一些预想不到的输出结构，或是不做任何处理。所以， 该程序的健壮性有待进一步的提高。要综合考虑一些情况，当输入有误时，应返回一个 表示错误的值，并中止程序的执行，以便在更高的抽象层次上进行处理。5.使用说明按照屏幕提示，选择想要的功能并输入对应数字，按下ENTER键后，根据屏幕提示进行输入，即可得到想要的结果。6.测试程序运行结果n 验证性实验n 设计性实验n 综合性实验7. 心得体会通过本次实验，使我对数据结构有了更深的理解，对指针的运用更加熟练，熟悉了对函数的定义和操作。专心-专注-专业