Need help with C++ priority queue programming project

[Zack_9]

Hi yall!

I have to create a priority queue with out using built in librarys. I have tried to write a bit of code so far, however I dont know if it works and am a little confused on a few things.

What follows this line is the main cpp file of the project.....

#include <cstdio>
#include "stdafx.h"
#include "pqueue.h"

using namespace std;

//Structure PQCell holds an item (item), priority (priority) and
//a pointer to the next item in the priority queue.

struct PQCell 
{
    ItemType item;
    PriorityType priority;
    PQCell* node;

    PQCell() : item(0), priority(0), node()
    {
    }
};

//Checks the the first element of the linked list (q) for
//a NULL value. If the list is empty this first element will be NULL.

bool isEmpty(const PriorityQueue& q)
{
    if (q.next == NULL)
    {
        return false;
    }
    return true;
}
//-------------------------------------------------------------------

void insertCell(PriorityQueue& L, ItemType x, PriorityType p)
{
    PQCell cell;
    cell.item = x;
    cell.priority = p;
}

void insert(PriorityQueue& q, ItemType x, PriorityType p)
{
    insertCell(q, x, p);
}

int main()
{

    return 0;
}

What follows this line is the header file that is supposed to accompany the main cpp file...

// CSCI 2530
// Assignment: ***
// Author:     ***
// File:       ***
// Tab stops:  ***

// **Say what this program does here.  (replace this comment)**

#include <cstdio>
using namespace std;

struct PQCell;

//Type definitions

typedef const char* ItemType;
typedef double      PriorityType;
typedef void(*ItemPrinter)(ItemType);
typedef void(*PriorityPrinter)(PriorityType);

struct PriorityQueue
{

    PriorityQueue* next;

    PriorityQueue()
    {
        next = NULL;
    }
};
//Prototypes

bool isEmpty(const PriorityQueue& q);
void insert(PriorityQueue& q, ItemType x, PriorityType p);

I really am having a hard time understanding linked lists and how the pointers work in this project

Any help would be appriciated!

Also, here is the link to my assignment instructions...... http://cs.ecu.edu/~karl/2530/spr18/Assn/Assn6/assn6.html

[tinstaafl]

I really am having a hard time understanding linked lists and how the pointers work in this project

I agree. I think maybe you need to go back study link lists again. Maybe take a supplementary tutorial. Here's a pretty good one

[Schol-R-LEA]

Before proceeding, it should be mentioned that the header file "stdafx.h" is specific to the Windows Visual C++ compiler. Given that the professor has stated that the submitted code will be compiled using GCC under Linux, the inclusion of that header will be a showstopper for you - and one which is entirely unnecessary, as you don't use anything referenced in the header.

Now, to be fair to you, I need to note that the Visual Studio IDE will insert that into certain kinds of C++ projects automatically, on the assumption that the code is for Windows and only Windows. This is the sort of thing a novice cannot be expected to know, so it isn't your fault that you missed it.

Still, I recommend you remove it for now, and be on the lookout for it in the future.

I would recommend removing <cstdio> from the header and type implementation file as well, as it isn't actually used in either of those (yet). You probably will need it in the implementations of the functions pointed to by ItemPrinter() and PriorityPrinter(), but right now, it doesn't need to be there until you have something that actually uses the C Standard I/O library.

On a similarly pedantic and administrative note, I would recommend getting the unfilled information sections in the comments of the provided code before you go any further. It is a picayune and annoying thing, I know, but the sort of professors who give these kinds of pre-built comment headers tend to be picayune and easily annoyed if the students do the equivalent of forgetting to put their name on a test. I suggest that you should just get it out of the way first, rather than figuring to do it later and then forgetting about it.

OK, now addressing the code itself, one problem I see is something that a lot of people get hung up on: where to put the structure and class declarations, and specifically, which parts have to be in the header and which parts should be in the implementation files.

The general rule - ignoring any exceptions for the moment - is that declarations need to go in the header, and only the header, while actual functions need to go in a source file, and only that one source file. The exceptions to 'no working code in the headers' all involve edge cases - macros, inline functions, and (for most compilers) templates - things where other files have to know the implementation in order to use them. For most things, though, putting them in the header will lead to them being compiled twice, which will then cause the linker (the tool that combines parts which were compiled separately, which in most systems today is usually hidden but still there) to go bananas.

I wrote a more extensive (if tongue in cheek) explanation years ago, a somewhat updated version of which can be found here.

In this case, the header does need to have a function prototype for the constructor (in fact, the whole c'tor should probably be there, so that it gets inlined), while the code body doesn't need the whole struct declaration - only the functions insert() and insertCell() should be there, with the main() function in yet another file which also #includes the header. Something like this:

// PQueue.h

//Type definitions
typedef const char* ItemType;
typedef double      PriorityType;
typedef void(*ItemPrinter)(ItemType);
typedef void(*PriorityPrinter)(PriorityType);

struct PQCell 
{
    ItemType item;
    PriorityType priority;
    PQCell() : item(0), priority(0), node()
    {
    }
};

struct PriorityQueue
{
    PQCell* node;
    PriorityQueue* next;
    PriorityQueue()
    {
        next = NULL;
    }
};

//Prototypes
bool isEmpty(const PriorityQueue& q);
void insert(PriorityQueue& q, ItemType x, PriorityType p);

Then the PQueue implementation would be:

#include "pqueue.h"

//Checks the the first element of the linked list (q) for
//a NULL value. If the list is empty this first element will be NULL.
bool isEmpty(const PriorityQueue& q)
{
    if (q.next == NULL)
    {
        return false;
    }
    return true;
}   

//-------------------------------------------------------------------
void insertCell(PriorityQueue& L, ItemType x, PriorityType p)
{
    PQCell cell;
    cell.item = x;
    cell.priority = p;
}
void insert(PriorityQueue& q, ItemType x, PriorityType p)
{
    insertCell(q, x, p);
}

With the main program file being:

// CSCI 2530
// Assignment: ***
// Author:     ***
// File:       ***
// Tab stops:  ***
// **Say what this program does here.  (replace this comment)**

#include <cstdio>
#include "pqueue.h"

using namespace std;

int main()
{
    return 0;
}

Oh, and never, ever ever put using namespace std; in a header file. That can cause hard to fix conflicts.