数据结构课程设计选做(三)---公共钥匙盒(线性表,栈,队列)

2024-04-15 11:36

本文主要是介绍数据结构课程设计选做(三)---公共钥匙盒(线性表,栈,队列),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

2.3.1 题目内容
2.3.1-A [问题描述]

有一个学校的老师共用N个教室,按照规定,所有的钥匙都必须放在公共钥匙盒里,老师不能带钥匙回家。每次老师上课前,都从公共钥匙盒里找到自己上课的教室的钥匙去开门,上完课后,再将钥匙放回到钥匙盒中。

钥匙盒一共有N个挂钩,从左到右排成一排,用来挂N个教室的钥匙。一串钥匙没有固定的悬挂位置,但钥匙上有标识,所以老师们不会弄混钥匙。

每次取钥匙的时候,老师们都会找到自己所需要的钥匙将其取走,而不会移动其他钥匙。每次还钥匙的时候,还钥匙的老师会找到最左边的空的挂钩,将钥匙挂在这个挂钩上。如果有多位老师还钥匙,则他们按钥匙编号从小到大的顺序还。如果同一时刻既有老师还钥匙又有老师取钥匙,则老师们会先将钥匙全还回去再取出。

今天开始的时候钥匙是按编号从小到大的顺序放在钥匙盒里的。有K位老师要上课,给出每位老师所需要的钥匙、开始上课的时间和上课的时长,假设下课时间就是还钥匙时间,请问最终钥匙盒里面钥匙的顺序是怎样的?

2.3.1-B [基本要求]

(1)输入格式

输入的第一行包含两个整数N, K。

接下来K行,每行三个整数w, s, c,分别表示一位老师要使用的钥匙编号、开始

课的时间和上课的时长。可能有多位老师使用同一把钥匙,但是老师使用钥匙的时间

不会重叠。

保证输入数据满足输入格式,你不用检查数据合法性。

2)输出格式

输出一行,包含N个整数,相邻整数间用一个空格分隔,依次表示每个挂钩上挂的

钥匙编号。

样例输入

5 2

4 3 3

2 2 7

样例输出

1 4 3 2 5

样例说明

  第一位老师从时刻3开始使用4号教室的钥匙,使用3单位时间,所以在时刻6还钥匙。第二位老师从时刻2开始使用钥匙,使用7单位时间,所以在时刻9还钥匙。

  每个关键时刻后的钥匙状态如下(X表示空):

  时刻2后为1X345;

  时刻3后为1X3X5;

  时刻6后为143X5;

  时刻9后为14325。

课程设计要求:

(1)要求从文本文件中输入;

(2)根据时间进程,将取走钥匙和归还钥匙分别视为事件,放入队列中,然后通过每个事件的先后发生对钥匙盒的状态进行变更;

(3)严格按照要求的输入输出格式进行数据的输入、输出(训练CSP考试中的格式化输入输出的正确性);

(4)选做:通过图形界面来显示钥匙盒的即时状态,以及事件队列的状态。

2.3.2 算法思想

定义了一个结构体 Node,用于存储借还钥匙的信息,包括钥匙编号、时间和借还标识。

自定义了一个比较函数 cmp,用于对借还钥匙的信息进行排序。排序的规则是首先按时间早的优先,然后是还钥匙优先,最后是编号小的优先。从文件中读取钥匙盒大小 N 和操作次数 K。

初始化了一个数组 num,用于存储钥匙盒中的钥匙情况,下标表示钥匙位置,值表示钥匙编号。通过循环,读取每次操作的借还钥匙信息,并将这些信息存储在结构体数组 node 中,同时对应的操作次数进行递减。对存储的借还钥匙信息进行排序,排序规则使用了自定义的比较函数 cmp。遍历排序后的借还钥匙信息,根据借还标识将钥匙放入或取出钥匙盒中的对应位置。最后输出最终的钥匙盒情况。

2.3.3 源代码 [共87]
#include<iostream>
#include<algorithm>
#include<fstream>
using namespace std;int num[1005]; // 用于存储钥匙盒中的钥匙情况,下标表示钥匙位置,值表示钥匙编号struct Node
{int key; // 钥匙编号int time; // 时间int sign; // 借还标识,借为0,还为1
} node[20002]; // 存储借还钥匙的信息// 自定义比较函数,用于排序
bool cmp(Node a, Node b)
{if(a.time != b.time)return a.time < b.time; // 时间早的优先else{if(a.sign != b.sign) return a.sign > b.sign; // 还优先else return a.key < b.key; // 编号小优先}
}int main()
{ifstream a;a.open("data.txt",ios::in);if(a.eof()){cout<<"打开文件失败!"<<endl;a.close();exit(0);}int N, K;a>> N >> K; // 输入钥匙盒大小和操作次数for(int i = 1; i <= N; i++) num[i] = i; // 初始化钥匙盒int n = 0;while(K--){int w,s,c;//cin >> w >> s >> c; // 输入借还钥匙的信息a>>w>>s>>c;// 存储借钥匙的信息node[n].key = w;node[n].time = s;node[n++].sign = 0;//0代表借 // 存储还钥匙的信息node[n].key = w;node[n].time = s + c;node[n++].sign = 1;//1代表还 }sort(node, node + n, cmp); // 对借还钥匙的信息进行排序for(int i = 0; i < n; i++){if(node[i].sign){ // 还钥匙for(int j = 1; j <= N; j++){if(!num[j]){num[j] = node[i].key; // 找到空位,放入还的钥匙break;}    }   }else{ // 借钥匙for(int j = 1; j <= N; j++){if(num[j] == node[i].key)num[j] = 0; // 找到对应的钥匙,置为空位}   } }for(int i = 1; i <= N; i++)cout << num[i] << " "; // 输出最终的钥匙盒情况a.close();return 0;
}
2.3.4 测试数据与运行结果
2.3.4-A 测试数据

2.3.4-B 运行结果

源码地址:GeekclubC/Course-Design-of-Data-Structure: 用C++完成的数据结构课程设计 (github.com)

这篇关于数据结构课程设计选做(三)---公共钥匙盒(线性表,栈,队列)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/905708

相关文章

hdu1180(广搜+优先队列)

此题要求最少到达目标点T的最短时间,所以我选择了广度优先搜索,并且要用到优先队列。 另外此题注意点较多,比如说可以在某个点停留,我wa了好多两次,就是因为忽略了这一点,然后参考了大神的思想,然后经过反复修改才AC的 这是我的代码 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

poj1330(LCA最近公共祖先)

题意:求最近公共祖先 思路:之前学习了树链剖分,然后我就用树链剖分的一小部分知识就可以解这个题目了,记录每个结点的fa和depth。然后查找时,每次将depth大的结点往上走直到x = y。 代码如下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstring>

6.1.数据结构-c/c++堆详解下篇(堆排序,TopK问题)

上篇:6.1.数据结构-c/c++模拟实现堆上篇(向下,上调整算法,建堆,增删数据)-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小): 2.2 C语言代码(手写堆) 2.3 C++代码(使用优先级队列 priority_queue)

poj 3190 优先队列+贪心

题意: 有n头牛,分别给他们挤奶的时间。 然后每头牛挤奶的时候都要在一个stall里面,并且每个stall每次只能占用一头牛。 问最少需要多少个stall,并输出每头牛所在的stall。 e.g 样例: INPUT: 51 102 43 65 84 7 OUTPUT: 412324 HINT: Explanation of the s

poj 2431 poj 3253 优先队列的运用

poj 2431: 题意: 一条路起点为0, 终点为l。 卡车初始时在0点,并且有p升油,假设油箱无限大。 给n个加油站,每个加油站距离终点 l 距离为 x[i],可以加的油量为fuel[i]。 问最少加几次油可以到达终点,若不能到达,输出-1。 解析: 《挑战程序设计竞赛》: “在卡车开往终点的途中,只有在加油站才可以加油。但是,如果认为“在到达加油站i时,就获得了一

poj3750约瑟夫环,循环队列

Description 有N个小孩围成一圈,给他们从1开始依次编号,现指定从第W个开始报数,报到第S个时,该小孩出列,然后从下一个小孩开始报数,仍是报到S个出列,如此重复下去,直到所有的小孩都出列(总人数不足S个时将循环报数),求小孩出列的顺序。 Input 第一行输入小孩的人数N(N<=64) 接下来每行输入一个小孩的名字(人名不超过15个字符) 最后一行输入W,S (W < N),用

《数据结构(C语言版)第二版》第八章-排序(8.3-交换排序、8.4-选择排序)

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多,算法平均时间性能比直接插入排序差。当初始记录无序,n较大时, 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In

POJ2010 贪心优先队列

c头牛,需要选n头(奇数);学校总共有f的资金, 每头牛分数score和学费cost,问合法招生方案中,中间分数(即排名第(n+1)/2)最高的是多少。 n头牛按照先score后cost从小到大排序; 枚举中间score的牛,  预处理左边与右边的最小花费和。 预处理直接优先队列贪心 public class Main {public static voi

Java并发编程之——BlockingQueue(队列)

一、什么是BlockingQueue BlockingQueue即阻塞队列,从阻塞这个词可以看出,在某些情况下对阻塞队列的访问可能会造成阻塞。被阻塞的情况主要有如下两种: 1. 当队列满了的时候进行入队列操作2. 当队列空了的时候进行出队列操作123 因此,当一个线程试图对一个已经满了的队列进行入队列操作时,它将会被阻塞,除非有另一个线程做了出队列操作;同样,当一个线程试图对一个空