CS 241: System Programming

Machine Problem 0
Implementing Priority Queue using Linked List

Deadline: Monday, January 30, 4:00pm
(electronic submission)

Solution: Makefile, pqueue.h, pqueue.c, main.c
Description The goal of this MP is to expose you to the POSIX programming environment and help you refresh your knowledge from CS225.

We will be using the CSIL linux machines for all MPs including MP0. Information about the machines can be found here. Linux machines are physically located in 1245 DCL and 1265 DCL. You can also use ssh to remotely access them at csil-linux[1-55].cs.uiuc.edu. All CS students and non-CS students who take CS241 should have CSIL accounts by now. You can log-in with your netid and AD password. However, if you have any problems in login 24 hours after you register CS241, email userhelp@cs.uiuc.edu.

In MP0, you will implement a priority queue in C. To begin with, go over any CS225 or related materials to make sure you understand priority queues.

There are some adjustments to be made when implementing a priority queue in C. One of the main differences between C and C++ is that C does not support classes unlike C++. Therefore you will need struct to represent complex data structures. For example, each node in a linked list containing an integer value can be represented as follows. You may want to modify this to implement each element of your priority queues.

struct Element {
    int value;
    struct Element *next;
};

First, write a program (pqueue.c, pqueue.h) which contains priority queue operations as C functions. In pqueue.h, you will need to define two data structures: one for each node (define its type as elementT), and the other for your priority queue (define its type as pqueueT). typedef keyword will be useful to introduce a type name. For example,

typedef struct Element {
    int value;
    struct Element *next;
} ElementNode;

Each elementT should include an integer value as well as an integer priority. Here are the functions that you will need to implement in pqueue.c. Before implementing, get familiar with functions on dynamic memory allocation such as malloc and free (defined in stdlib.h), as you will not be allowed to use new and delete in C++.
  • pqueueT* Initialize(void): this function is equivalent to the constructor in C++, which dynamically allocates the memory for a queue and returns an empty queue. Note that malloc is a function for dynamic memory allocation. A reference is also linked here.
  • void Free(pqueueT* q): this function is equivalent to the destructor in C++, which deallocates the memory previously assigned. Use free function for this purpose. A reference is also linked here.
  • void SortedInsert(pqueueT* q, elementT* e): inserts an element into the queue, so that the elements are sorted in an increasing order by priority.
  • elementT* Remove(pqueueT* q): removes and returns the first item from the front of the priority queue.
  • int IsEmpty(pqueueT* q): returns 1 if the queue is empty, 0 if the queue is not empty.
  • void Print(pqueueT* q): prints out the queue. Format is defined below.
Second, write a main program (main.c) that (1) receives standard input to execute each operation defined above, and (2) prints out the result of each operation. Make sure your include pqueue.h to define your queue structure in main.c. For intput and output, get familiar with printf and scanf (defined in stdio.h). User input is defined as follows.

[operationnum] ([value],[priority])

operationnum=1..5 (1:Initialize, 2:Free, 3:SortedInsert, 4:Remove, 5:Exit)
value=int, priority=int

Assume that value and priority are always non-negative. Except for SortedInsert, the (value,priority) pair is obviously not necessary. For your convenience, you can assume that a garbage value (-1,-1) follows to be ignored if operationnum = 1, 2, 4, 5.

After each input, you need to print out current status of the priority queue. Here is the output format of queue status.

([value1],[priority1]) -> ([value2],[priority2]) -> ... -> ([valuen],[priorityn])

The front item is printed out first. If the queue is empty, print out EMPTY. If there is no defined queue, print out UNDEFINED. For invalid operations such as remove from an empty queue, print out ERROR. The following is a sample input and output.

UNDEFINED
1 (-1,-1)
EMPTY
3 (1,1)
(1,1)
3 (2,3)
(1,1) -> (2,3)
3 (3,2)
(1,1) -> (3,2) -> (2,3)
4 (-1,-1)
(3,2) -> (2,3)
2 (-1,-1)
UNDEFINED
5 (-1,-1)

Deliverable This assignment is expected to be completed via pair programming. You are encouraged to form a group of 2, although you may elect to work alone. Newsgroup communication about general issues is allowed. You can use the CSIL Linux machines to do the assignment.

You are strictly required to use C (use stdio.h and printf for output, etc). Create pqueue.c, pqueue.h for priority queue operations and main.c for input/output. Create a makefile which builds both (an executable named main and an object file named pqueue.o). Add to makefile a label clean that deletes all executables and object files.

Create a README file as well, detailing any problems encountered during program design or execution. Also include in the README the following information:
  1. MP number and title
  2. Your names and netids
  3. How you split the work for the entire MP
  4. An outline of your implementation
  5. A brief justification of the data structures used for implementation
Handin Use Compass to electronically handin those 5 files (makefile, pqueue.c, pqueue.h, main.c, README) under the "MP0 Handin" assignment. Before you actually try to hand in, be sure to read the handin instruction. This must be done before 4pm on Monday, Jan 30. Every hour late is minus 2% credit. No submissions accepted after 4pm on Tuesday, Jan 31.

Grading Criteria Priority Queue Implementation (pqueue.c, pqueue.h) – 50%
Main Program (main.c) – 20%
Makefile – 20%
README – 10%