Data Structures and Algorithms III

Doubly & Circularly Linked Lists


  1. The Josephus Problem:
  2. A group of m soldiers are surrounded by the enemy and there is only a single horse for escape. The soldiers determine a pact to see who will escape and summon help. They form a circle and pick a number n that is between 1 and m. A soldier is also selected at random.

    Beginning with the soldier who was picked they begin counting clockwise around the circle. When the count reaches n that soldier is removed from the circle and the count begins with the next soldier. The process continues until 1 soldier is left. This soldier takes the horse and summons help.

    Take in n, m, the ordering of the soldiers in the circle and the soldier where counting commences from the user and determine the order in which the soldiers are eliminated and which soldier escapes.

    Your solution should use a circularly linked list, in which each node represents a soldier, to solve this problem.

  3. Priority Queues

A priority Queue may be implemented using a linked list where elements of the queue are placed in the queue according to their priority. Deletion of the element of highest priority will then involve deleting the element at the head of the queue.

Implement a priority Queue using a Doubly Linked List. Each node in the Doubly Linked List may be represented as follows:

typedef struct node{

int x;

struct node * nxt; *pre;