阮籍技术基础课设

实验一 约瑟夫斯问题实验报告 一 问题描述 约瑟夫斯 Josephus 问题的一种描述是 编号为 1 2 n 的 n 个人按顺时针 方向 围坐一圈 每人持有一个密码 正整数 一开始任选一个正整数作为报数上 限值 m 从第 一个人开始按顺时针方向自 1 开始报数 报到 m 时停止报数 报 m 的人出列 将他的密码作 为新的 m 值 从他在顺时针方向下一个人开始重新从 1 报数 如此下去 直至所有的人全部 出列为止 试设计一个程序 按出列顺序印出各 人编号 2 基本要求 利用单向循环链表存储结构模拟此过程 按照出列的顺序印出 各人的编号 3 测试数据 m 的初值为 20 n 7 7 个人的密码依次为 3 1 7 2 4 8 4 m 初值为 6 正确的 出列顺序应为 6 1 4 7 2 3 5 二 需求分析 1 该程序所能实现的功能 将 n 个数字按照某一特定序列输出 直至全部输出为止 2 输入的形式及输入值范围 依次输入人数 n 每个人的密码及报数上限 m 值 3 输出的形式 按照报数上限 m 及每个人的密码依次输出每个人的编号 4 测试数据要求 m 的初值为 20 n 7 7 个人的密码依次为 3 1 7 2 4 8 4 m 初值为 6 正确的出列顺序应为 6 1 4 7 2 3 5 三 概要设计 1 主程序流程 获取每个人的密码 选定 m 的初值 调用函数 按照特定要求完成输出 操作 2 核心模块的算法伪码 主程序 void main void int m people s s GetData cout 请输入 m 的初值 m DealData s m 预编译代码 include 四 详细设计 1 实现每个操作的伪码 重点语句加注释 1 建立 人 的结构体 struct people int data int num people next 2 获取每个人的相关数据 people GetData int n people p1 p2 head head NULL cout n cout 请依次输入每个人的密码 endl for int i 0 i p1 data p1 num i 1 if head NULL head p2 p1 else p2 next p1 p2 p1 中间结点 建立首结点 if head NULL p2 next head return head 2 函数调用关系图 循环链表 Main void DealData people s int m people GetData 五 调试分析 1 设计与调试过程中遇到的问题分析 体会 在调试过程中遇到了死循环的情况 自己反 复看了很久也未能查找到错误 直到请同学 帮忙看 才终于发现原来是一个在循环条件 中 写丢了一个条件 后来回想 觉得当初自己 检查的时候不够仔细 大概也有些主观 思想 认为不可能出错 掺杂其中 导致有此结 果 以后写程序要更认真才行 2 主要算法的时间 主程序 循环算法 六 使用说明 打开此程序 点击运行 按照屏幕输出显示依次输入所需数据即可 首 先输入参与的人数 然后依次输入每个人手中的密码 最后输入 m 的初值 即可得到 输 出结果 七 测试结果 八 附录 源程序 include struct people int data int num people next people GetData int n people p1 p2 head head NULL cout n cout 请依次输入每个人的密码 endl for int i 0 i p1 data p1 num i 1 if head NULL head p2 p1 else p2 next p1 p2 p1 if head NULL p2 next head return head 循环链表 中间结点 建立首结点 void DealData people s int m people p1 p2 q p1 s while p1 NULL for int i 1 inext if p1 p1 next 重新获取 m 值并删除 已读取的结点 m p1 data cout num p2 next p1 next q p1 p1 p1 next delete q else cout num delete p1 p1 NULL void main void int m people s s GetData cout 请输入 m 的初值 m DealData s m cout endl 实验二 实验二 停车场管理问题 一 问题描述 1 问题描述 设停车场是一个可停放 n 辆汽车的狭长通道 且只有一个大门可供汽车进出 汽 车在停车场内按车辆到达时间的 先后顺序 依次由北向南排列 大门在最南端 最先到 达的第一辆车停放在车场的最北端 若停车场内已经停满 n 辆车 那么后来的车只能 在门外的便道上等候 一旦有车开走 则排在便道上的第一辆车即可开入 当停车场内 某辆车要离开时 在它之后进入的车辆 必须先退出车场为它让路 待该辆车开出大门外 其他车辆再按原次序进入车场 每辆 停放在车场的车在它离开停车场时必须按它停留的 时间长短缴纳费用 试为停车场编制按 上述要求进行管理的模拟程序 2 基本要求 以栈模拟停车场 以队列模拟车场外的便 道 按照从终端读入数据的序列进行模 拟管理 每一组输入数据包括三个数据项 汽车 的 到达 A 表示 离去 或 D 表示 信息 汽车标识 牌照号 以及到达或离去的时刻 对每一组输入数据进行操 作后的输出信息为 若是车辆到达 则 输出汽车在停车场内或者便道上的停车位置 若是车辆离去 则输出汽车在停车场停留的 时间和应缴纳的费用 便道上停留的时间 不收费 栈以顺序结构实现 队列以链表结 构实现 3 测试数据 设 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 0 0 E 每一 组输入数据包括三个 数据项 汽车 到达 或 离去 信息 汽车牌照号码及到达或 离去的时刻 其中 A 表示到达 D 表示离去 E 表示输入结束 其中 A 1 5 表 示 1 号牌照车在 5 这个时刻到达 而 D 1 15 表示 1 号牌照车在 15 这 个 时刻离去 二 需求分析 需求分析 1 程序所能达到的基本可能 可实现特定停车场车辆 出入的管理功能 可以查询等车场 候车场使用情况 2 输入的形式及输入值的范围 功 能指令分为 5 种 分别是 A 到达 D 离开 P 查询停车场使用情况 W 查 询候车场使用情况 E 退出程序 车牌号 到达时间 费用及停车场容量可为任意正整 数 3 输出的形式 依据所选功能指令不同 输出形式略有不同 对于 A 指令 输出 车牌号 车位号 D 指令 输出车牌号 计费时间段 应付费用 P 指令 输出停车场 内车辆数目 W 指令 输出后车场内车辆数目 E 指令 输出退出提示 4 测试数据 要求 需另设一个栈 临时停放为给要离去的汽车让路而从停车场退出来的汽车 输入数 据按到达或离去的时刻有序 栈中每个元素表示一辆汽车 包含两个数据项 汽车的牌 照 号码和进入停车场的时刻 输入数据 程序接受 5 个命令 分别是 到达 A 车牌 号 时间 离去 D 车牌号 时间 停车场 P 0 0 显示停车场的车数 候车场 W 0 0 显示候车场的车数 退出 E 0 0 退出程序 输出数据 对于车辆 到达 要输出汽车在停车场内或者便道上的停车位置 对于车 辆离去 则输出汽车在停车 场停留的时间和应缴纳的费用 便道上不收费 三 概要设计 1 主程序流程 首先 设定停车场容量及停车场收费标准 选择功能指令 输入车牌号 到达时间 根据指令调 用不同的函数 完成指令功能 2 核心模块的算法伪码 主程序 void cout Parkingroom cout fee cout endl cout 功能指令如下 注 区分大小写 n A 到达 n D 离开 n P 停车场使用情况 n W 候车便道情况 n E 退出程序 endl cout endl main char order parking s1 s2 pave p car x int k 1 s1 new parking s2 new parking p new pave Init parking s1 Init parking s2 Init pave p while k cout order cin x num cin x intime switch order case A parkingin s1 p x break case D parkingout s1 s2 p x break case P roomsituation break case W roompave break case E k 0 cout 程序即将退出 endl break default cout 您输入的指令有错误 请重新输入 endl cout 程序结束 endl 预编译代码 include include 四 详细设计 1 实现每个操作的伪 码 重点语句加注释 车辆信息 struct car int num int intime 停车场信息 struct parking car N 10000 int top int size 便道上车辆信息 struct pavecar pavecar next int pavenum int posnum 便车道信息 struct pave pavecar front pavecar rear 初始化 栈 停车场 void Init parking parking s s top 1 初始化队列 便道 void Init pave pave s s front new pavecar s rear s front s front next NULL s front posnum 0 便道上车辆进入 void pavein pave s int num pavecar p p new pavecar p pavenum num p posnum s rear posnum 1 p next NULL if s rear s front s front next p s rear next p s rear p carwait carwait 1 便道上车辆离开 int paveout pave s pavecar p int num p s front next s front next p next if p next NULL s rear s front num p pavenum delete p return num carwait carwait 1 车辆进入停车场 int carin parking s car x if s top Parkingroom 1 cout 停车场已 满 top s N s top x carroom carroom 1 return 1 void parkingin parking s pave p car x int k k carin s x if k 0 cout n 停车场已满 请到便道上排队等候 endl pavein p x num cout 车辆 x num 已在便道等候 n endl else cout n 车辆已停入停车场 n 车牌号 x num n 车位号 top n toptop carroom carroom 1 return s N s top 1 void parkingout parking s1 parking s2 pave p car x car y int num k 0 while s1 top 1 if y num x num k carin s2 y else k 1 if y num x num cout n 车辆离开停车场 n 车牌号 x num n 计费时间段 y intime x intime n 应付费用为 x intime y intime fee 元 n top 0 y carout s2 carin s1 y num paveout p if num 0 y num num y intime x intime carin s1 y cout 便道上等候车 辆进入停车场 n 车牌号 y num n 车位号 top 1 n top 1 y carout s2 k carin s1 y cout 所查车辆不在停车场中 endl 停车场情况 void roomsituation cout n 停车场内已有车辆数 carroom 台 n endl 候车便道情况 void roompave cout n 停车场内已有车辆数 carwait 台 n 这个符号 却没深究那些到 底是不是指针类型的 结构体 于是 又重新修改 弄了一个晚上才终于把这个程序调 好 看到小黑屏跳出来 心里真的很开心呀 吸取教训 以后写程序不能 想当然 要严格按照既定的规则按 部就班地书写 否则吃亏的 真的是自己 2 主要算法的时间 和空间复杂度 六 使用说明 运行程序 输入功能指令 车牌号 车辆到达时间即可 七 测试结果 源代码 八 附录 源代码 include include int Parkingroom int fee int carroom 0 int carwait 0 车辆信息 struct car int num int intime 停车场信息 struct parking car N 10000 int top int size 便道上车辆信息 struct pavecar pavecar next int pavenum int posnum 便车道信息 struct pave pavecar front pavecar rear 初始化栈 停车场 void Init parking parking s s top 1 初始化队列 便道 void Init pave pave s s front new pavecar s rear s front s front next NULL s front posnum 0 便道上车辆进入 void pavein pave s int num pavecar p p new pavecar p pavenum num p posnum s rear posnum 1 p next NULL if s rear s front s front next p s rear next p s rear p carwait carwait 1 便道上车辆离开 int paveout pave s pavecar p int num p s front next s front next p next if p next NULL s rear s front num p pavenum delete p return num carwait carwait 1 车辆进入停车场 int carin parking s car x if s top Parkingroom 1 cout 停车场已满 top s N s top x carroom carroom 1 return 1 void parkingin parking s pave p car x int k k carin s x if k 0 cout n 停车场已满 请到便道上排队等候 endl pavein p x num cout 车辆 x num 已在便道等候 n endl else cout n 车辆已停入停车场 n 车牌号 x num n 车位号 top n toptop carroom carroom 1 return s N s top 1 void parkingout parking s1 parking s2 pave p car x car y int num k 0 while s1 top 1 if y num x num k carin s2 y else k 1 f y num x num cout n 车辆离开停车场 n 车牌号 x num n 计费时间段 y intime x intime n 应付费用为 x intime y intime fee 元 n top 0 y carout s2 carin s1 y num paveout p if