Algorithms and Programming

Assignment 3 (Structures, Dynamic Memory, Linked Lists)

(Due on Wed 11th October 2017)

This assignment asks you to implement a priority queue using a linked
list. The elements in the queue have a key id, and a "priority". The
priority is a unsigned char, and the higher the number the more the
priority. The priority queue behaves like a queue, with operations to
enqueue and dequeue elements from the queue. However, in a priority
queue, the elements are maintained in decreasing order of
priority. Thus the enqueue operation inserts a given element with
priority "k" at the end of all the elements with priority "k" that are
already in the list (but ahead of elements with priority less than
"k").

Use the following struct declaration:

struct node {
  int key;
  unsigned char prio;
  struct node * next;
}

typedef struct node *queue;

Implement the following functions on the priority queue:

(a) int enqueue(queue q, int k, prio p)

    This function should allocate a new node, initialize it, and
    enqueue it in the list q, giving due weightage to its priority.
    Returns 1 for successful enqueue and 0 otherwise.

(b) int dequeue(queue q)

    Dequeues the node at the head of the queue, and returns its key
    value. It also free's the memory used by the node.

(c) int search(queue q, ink key)

    Returns 1 if the key occurs in the list, else 0.

(d) int length(queue q)

    Returns the number of elements in the queue.

(e) int remove(queue q, int k)
  
    Removes (unlinks) the node with key value  k.

(f) void print(queue q)
  
    Prints the elements of the list in order, starting from the head
    of the queue.

Finally, implement a user-interface that creates a queue and allows a
user to call the different operations above on the queue. Present a
menu to the user like:

  Enter an option:

  1. Enqueue
  2. Dequeue
  3. Print elements in the list
  4. Remove a element from the list
  5. Search for an element in the list
  6. Print the length of the list
  7. Exit