数据结构课程设计大课ppt课件.ppt

数据结构课程设计 1 教学安排 2 设计题目 3 成绩评定 4 课程设计报告 5 研究性学习与创新性实验 1 1 教学安排 1 1 教学目的 1 2 计划学时 1 3 学习方式 1 4 教学过程 2 1 教学安排 教学目的 1 全面落实课程教学大纲 2 提升学生软件设计实践技能 3 鼓励学生研究性学习 4 鼓励学生创新性实验 3 1 教学安排 计划学时 32学时 课外自主学习 32学时 自主学习与计划学时比例 1 1 4 1 教学安排 学习方式 1 组建课程设计活动小组 2 双向自愿选题 3 课程实践 自主学习 调研 4 上机实践 技术讨论 调试 5 成果交流 5 1 教学安排 教学过程 总体分为两个阶段 1 综合训练阶段 2 研究性学习与创新性实验阶段 循序渐进 重点 逐步深入 扩展与提高 6 1 教学安排 具体教学过程 1 选题与开题 2 方案设计 总体设计 数据结构设计 3 详细设计 函数原型 算法设计 4 编程与调试 5 结题与成果交流 7 2 设计题目 分为三类 A类 综合训练性 B类 应用研究性 C类 创新设计性 8 3 成绩评定 综合评定 综合训练性 占60 应用研究性 占20 创新设计性 占20 9 4 课程设计报告 设计报告内容 1 课题背景 2 可行性与需求分析 3 总体设计 4 详细设计 5 程序实现 6 软件测试 7 总结 10 4 课程设计报告 设计报告格式 1 封面 2 任务书 3 目录 4 正文 5 附录 源代码等 11 5 研究性学习与创新性实验 设计题目举例 排队问题仿真 基于STL双端队列及应用 线段树及应用 12 排队问题仿真 排队问题 用队列结构可以模拟现实生活中 的很多排队现象 如车站候车 医院 候诊 银行排队等都可以通过程序进 行仿真模拟 并由此预测客流等多种 经营指标 例如理发店排队问题 13 问题描述 假设理发店内设有N把理发椅 可同 时为N位顾客进行理发 顾客进门 可能顾客进门 可能 有两种情况 有两种情况 若当时理发店内尚有空闲理发椅 若当时理发店内尚有空闲理发椅 则该顾客可立即入座理发 他在店内的逗则该顾客可立即入座理发 他在店内的逗 留时间即为他理发所需时间 留时间即为他理发所需时间 排队问题仿真 14 否则需要排队候理 则他在店内的否则需要排队候理 则他在店内的 逗留时间应为他理发所需时间和排队等候逗留时间应为他理发所需时间和排队等候 的时间之和 的时间之和 一旦有顾客理完发离去时 排在对头 的顾客便开始理发 顾客的到达时间和理 发所需时间均可随机生成 并约定 过了 营业时间顾客不再进门 但仍需继续为已 进入店内的顾客理发 直至最后一名顾客 离开为止 排队问题仿真 15 题目要求 编制一个事件驱动仿真程序以模拟理编制一个事件驱动仿真程序以模拟理 发店内一天的活动 要求输出在一天的营发店内一天的活动 要求输出在一天的营 业时间内 到达的顾客人数 顾客在店内业时间内 到达的顾客人数 顾客在店内 的平均逗留时间和排队等候理发的平均人的平均逗留时间和排队等候理发的平均人 数以及在营业时间内空椅子的平均数 数以及在营业时间内空椅子的平均数 通过队列模拟理发店的排队现象 通 过仿真办法评估理发店的营业状况 排队问题仿真 16 排队问题仿真 需求分析 事件驱动模拟事件驱动模拟 为计算出每个顾客自进门到出门之为计算出每个顾客自进门到出门之 间在理发馆内逗留的时间 只需要在顾间在理发馆内逗留的时间 只需要在顾 客客 进门进门 和和 出门出门 这两个时刻进行模拟这两个时刻进行模拟 处理 处理 定义在这两个时刻内发生的事情为定义在这两个时刻内发生的事情为 事件事件 整个仿真程序可以按事件发生的 整个仿真程序可以按事件发生的 先后次序逐个处理事件 这种模拟的工先后次序逐个处理事件 这种模拟的工 作方式称为作方式称为 事件驱动模拟事件驱动模拟 17 建立数据模型 数据结构设计 本题目需要两种数据结构 链队列 登录排队等候理发的顾客情 况 队列中的每个元素应包括顾客进门的 时刻和理发所需的时间 链表 登录顾客进门和出门的事件 表中的元素应包括事件类型 还应按事件 发生的先后次序有序 排队问题仿真 18 排队问题仿真 事件表数据类型定义事件表数据类型定义 typedef typedef struct struct 数据域数据域 int occurTimeint occurTime 事件发生时刻事件发生时刻 char char NTypeNType 事件类型事件类型 ElemType Event ElemType Event typedef struct typedef struct Lnode Lnode 链表结点链表结点 ElemType data ElemType data struct struct Lnode next Lnode next Link Position Link Position 19 排队问题仿真 事件链表结构定义事件链表结构定义 typedef typedef struct struct Link head tail Link head tail 头 尾指针头 尾指针 int length int length 链表长度链表长度 LinkLink current current 当前指针当前指针 Link List Link List typedef LinkList EventList 事件链表类型 定义为有序链表 20 等待队列定义等待队列定义 typedef struct typedef struct 数据域数据域 int arrivalTimeint arrivalTime 顾客到达时间顾客到达时间 int duration int duration 顾客理发所需时间顾客理发所需时间 QElemType QElemType typedef struct typedef struct Qnode Qnode 链表结点链表结点 QElemType data QElemType data struct struct Qnode next Qnode next Qnode QueuePtr Qnode QueuePtr 排队问题仿真 21 链队列结构链队列结构定义定义 typedef struct typedef struct QueuePtr front QueuePtr front 头指针头指针 QueuePtr rear QueuePtr rear 尾指针尾指针 LinkQueue LinkQueue 排队问题仿真 22 主算法设计主算法设计 假设假设进门事件类型进门事件类型为为 A A 出门事件类型 出门事件类型 为为 D D 为便于按事件发生的先后次序顺序进为便于按事件发生的先后次序顺序进 行处理 事件表应按发生的行处理 事件表应按发生的 时刻时刻 有序 有序 实际问题中 顾客进门的时刻和理发所实际问题中 顾客进门的时刻和理发所 需要的时间都是随机的 假设第一个顾客进需要的时间都是随机的 假设第一个顾客进 门的时刻为门的时刻为0 0 之后每个顾客进门的时刻在 之后每个顾客进门的时刻在 前一个顾客进门时设定 即以两个顾客之间前一个顾客进门时设定 即以两个顾客之间 的时间间隔来确定下一个顾客的到达时间 的时间间隔来确定下一个顾客的到达时间 排队问题仿真 23 生成生成 顾客顾客理发所需时间理发所需时间 durtime durtime 和和 下一顾客到达的时间间隔下一顾客到达的时间间隔 intertime intertime 两两个个 随机数随机数可从可从C C语言的随机数函数得到 语言的随机数函数得到 假设当前事件发生的时刻为假设当前事件发生的时刻为 occurtimeoccurtime 则下一顾客进门事件发生的时刻则则下一顾客进门事件发生的时刻则为为 occurtime occurtime intertime intertime 该顾客在当前时刻开始理发 经过该顾客在当前时刻开始理发 经过 durtime durtime 时间之后便可离开理发馆 则应发时间之后便可离开理发馆 则应发 生时刻为生时刻为 occurtime durtime occurtime durtime 排队问题仿真 24 排队问题主算法描述排队问题主算法描述 主算法是以处理主算法是以处理顾客进门事件顾客进门事件和和顾客离顾客离 开事件开事件为线索进行的 为线索进行的 void BarberShop Simulation int chairNum void BarberShop Simulation int chairNum int closeTime int closeTime 理发店馆业务模拟理发店馆业务模拟 chatrNum chatrNum 为假设的理发馆的为假设的理发馆的 规模规模closeTime closeTime 为营业时间为营业时间 OpenForDay OpenForDay 初始化初始化 排队问题仿真 25 while MoreEvent do while MoreEvent do EventDrived OccurTime EventType EventDrived OccurTime EventType 事件驱动事件驱动 switch EventType switch EventType case A CustomerArrived case A CustomerArrived break break 处理顾客到达事件处理顾客到达事件 case D CustomerDeparture case D CustomerDeparture break break 处理顾客离开事件处理顾客离开事件 排队问题仿真 26 default Invalid default Invalid switch switch while while CloseForDay CloseForDay 计算平均逗留时间和排队的平均长度计算平均逗留时间和排队的平均长度 BarberShop Simulation BarberShop Simulation 排队问题仿真 27 主算法详细描述 BarberShop Simulation BarberShop Simulation 设定设定事件表中的第一个元素 事件表中的第一个元素 置空队列 置空队列 while while 当事件表不空 当事件表不空 删除删除事件表中发生时刻最早的元素 事件表中发生时刻最早的元素 if if 事件类型 事件类型 0 0 处理顾客进门处理顾客进门事件事件 累计顾客进门人数 累计顾客进门人数 if if 下一个到达时刻 下一个到达时刻 关门时刻 关门时刻 进门事件插入事件表 进门事件插入事件表 排队问题仿真 28 if if 有空闲理发椅 有空闲理发椅 新新出门事件插入事件表 出门事件插入事件表 累计累计顾客逗留时间 顾客逗留时间 else else 当前顾客插入队尾 当前顾客插入队尾 累计队列长度 累计队列长度 if if 排队问题仿真 29 elseelse 事件类型事件类型 1 1 处理顾客离开事件 处理顾客离开事件 if if 队列不空 队列不空 删除队头元素 删除队头元素 记录顾客离开的最晚时间 记录顾客离开的最晚时间 新出门事件插入事件表 新出门事件插入事件表 累计顾客逗留时间 累计顾客逗留时间 if if else else while while 排队问题仿真 30 计算平均队列长度 计算平均队列长度 计算平均逗留时间 计算平均逗留时间 BarberShop Simulation BarberShop Simulation 排队问题仿真 31 void void CustomerArrived eventList evL Queue CustomerArrived eventList evL Queue Q Event en Q Event en 处理顾客进门事件处理顾客进门事件 Random 。