首页 > 代码库 > 数据结构课程设计题目十二_计算机学院学生会的打印机(优先队列)

数据结构课程设计题目十二_计算机学院学生会的打印机(优先队列)

本文出自:http://blog.csdn.net/svitter

题目12:计算机学院学生会的打印机(优先队列)

小明抱怨学生会的打印机不符合FIFO的原则,看到很多在他后面来打印的同学比他先打印出来。五分钟前,小明的文件就是下一个候选的,如今小明的文件又排到了后面。学生会的同学给小明解释说,学生会的打印机不是採用传统的队列方式,而是採用一种自定义的优先队列方式:每一个要打印的文件被赋予了一个从19的优先级(9最高,1最低)。打印规定例如以下:

将队列中要打印的文件f从队列中拿出来;

假设在队列中有优先级高于f的文件,则不打印f,将f排到队列的最后;否则打印f

小明知道打印新规以后,询问他的文件到底多长时间可以打印出来,如果没分文件打印的时间都是1分钟,小明的文件在打印队列中,而且不再有新的文件进入到打印队列。请你帮助小明计算一下他还须要等多长时间。建议完毕人数1人。


加入了小元素的筛选代码


PriorityQueue.cpp:

//============================================================================
// Name        : PriorityQueue.cpp
// Author      : vit
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <stdio.h>
#include "Queue.h"
using namespace std;

int main() {
	Queue *q;
	q = new Queue();
	int i;
	int n, m, val, num;
        int mval;
	Node *p;
	freopen("test", "r", stdin);
	while(~scanf("%d%d", &n, &m))
	{
		num = 1;
		for(i = 1; i <= n; i++)
		{
			scanf("%d", &val);
			//printf("第%d号正在增加队列...\n", i);
			p = new Node(val, NULL, i);
                        if(i == m)
                        {
                               mval = val;
                        }
			q->push(p);
		}
                q->check(mval);


		//printf("队列增加完毕。\n");
		while(!q->IsEmpty())
		{
			p = q->top();
			//printf("当前打印的是第%d号\n", p->num);
			if(p->num == m)
			{
				printf("小明在第%d分钟打印。\n", num);
			}
			q->pop();
			num++;
		}
	}
	return 0;
}


Queue.cpp:

/*
 * Queue.cpp
 *
 *  Created on: 2014Äê6ÔÂ15ÈÕ
 *      Author: vit
 */

#include <stdio.h>
#include "Queue.h"

Queue::Queue() {
	// TODO Auto-generated constructor stub
	this->front = this->rear = NULL;
}

bool Queue::IsEmpty(){
	return this->rear == NULL;
}

void Queue::push(Node *n){
	if(IsEmpty())
	{
		this->front = this->rear = n;
	}
	else
	{
		this->rear->next = n;
		this->rear = n;
	}
	return;
}

void Queue::pop(){
	if(IsEmpty())
	{
		return;
	}
	Node *p = this->front;
	if(this->front == this->rear)
	{
		p = this->front;
		this->front = this->rear = NULL;
	}
	else
	{
		p = this->front;
		this->front = this->front->next;
	}
	delete p;
}

Node * Queue::top(){
	if(IsEmpty()){
		return NULL;
	}
	int value = http://www.mamicode.com/this->front->value;>



Queue.h:

/*
 * Queue.h
 *
 *  Created on: 2014年6月15日
 *      Author: vit
 */

#ifndef QUEUE_H_
#define QUEUE_H_


class Node
{
public:
    int value;
    int num;
    Node *next;
    Node()
    {
        this->value = http://www.mamicode.com/0;>