2006-2007年度数据结构大作业 - 对外经济贸易大学.doc

2010级数据结构大作业 2011年11月 说明： 1．每组四人，自由结合，每组推选组长一名，组内既有分工又有合作。 2．每组三道题，能够在C环境下真正运行。 3．每组趣味编程题必做，在“实验一”中选作一题。 4．第一组：2.3题、第二组：2.4题、第三组：3.3题、第四组：3.1题、 第五组：3.2题、第六组：2.1题、第七组：2.2题、第八组：4.1题、 第九组：2.4题、第十组：3.3题、第十一组：2.1题、第十二组：4.1题 第13组：3.2题、第14组：2.1题、第15组：2.2题、第16组：2.4题、 实验0、趣味编程 有一叠n张卡片，从上到下依次编号为1～n，从最上面的一张开始按如下的顺序进行操作：把最上面的第一张卡片拿掉，把下一张卡片放在这一叠卡片的最下面；再把最上面的第一张卡片拿掉，把下一张卡片放在这一叠卡片的最下面；依次重复这样做，直到手中剩下一张卡片。 要求：输入不同的n，能输出剩下的这张卡片是原来n张卡片的第几张。（两种算法） ). [实现提示] 程序运行后, 首先要求用户指定初始报数上限值, 然后读取各人的密码. 可设n=30. 此题所用的循环链表中不需要”头结点”, 请注意空表和非空表的界限. [选作内容] 向上述程序中添加在顺序结构上实现的部分. 2．3集合的并、交和差运算 [问题描述] 编织一个能演示执行集合的并, 交和差运算的程序. [基本要求] (1) 集合的元素限定为小写字母字符[′a′.. ′z′]. (2) 演示程序以用户和计算机的对话方式执行. [测试数据] (1) Set1=″magazine″, Set2=″paper″, Set1∪Set2=″aegimnprz″,Set1∩Set2=″ae″,Set1-Set2=″gimnz″. (2) Set1=″012oper4a6tion89″,Set2=″error data″, Set1∪Set2=″adeinoprt″, Set1∩Set2=″aeort″,Set1-Set2=″inp″. [实现提示] 以有序链表表示集合. [选作内容] (1) 集合的元素判定和子集判定运算. (2) 求集合的补集. (3) 集合的混合运算表达式求值. (4) 集合的元素类型推广到其他类型, 甚至任意类型。 2．4 一元多项式运算 [问题描述] 设计一个可进行一元多项式运算的演示程序。 [基本要求] 实现两个一元多项式相加，相减的运算。 [测试数据] 自定。 实验三、栈和队列及其应用 实验目的： 3．1停车场问题 [问题描述] 设停车场是一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入车场，每辆车停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。 [基本要求] 以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项；汽车“到达”或“离去”信息、汽车牌照号码以及到达或离去的时刻。对每一组输入数据进行操作后的输出信息为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表结构实现。 [测试数据] 设n=2,输入数据为：(‘A’,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)。其中，：’A’表示到达（Arrival）; ’D’表示离去（Departure）; ‘E’表示输入结束（End）。 [实现提示] 需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车，也用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含两个数据项：汽车的牌照号码和进入停车场的时刻。 [选作内容] 两个栈共享空间，思考应开辟数组的空间是多少？ 汽车可有不同种类，则他们的占地面积不同，收费标准也不同，如1辆客车和1.5辆小汽车的占地面积相同，1辆十轮卡车占地面积相当于3辆小汽车的占地面积。 汽车可以直接从