Thread: need help with pseudocode (circular doubly linked list)

  1. #1
    Registered User
    Join Date
    Feb 2002

    need help with pseudocode (circular doubly linked list)

    My pseudocode in C is the following ( i will implement this as doubly linked list ), i'm having trouble figuring out the traverse part, how do i know the node i have alreadt traversed?and I also have trouble in the bold part of the question. Thanks for any help :
    ================================================== =====================
    void initialize_list(name_of_list *a);

    void insert_end(name_of_list *a);

    void traverse_and_find(N) (name_of_list *a); <==== how to implement this function???
    find the Nth elemet, Mark it,
    then start counting N times again
    delete the last one

    /************************************************** **/
    while (insert_data != 9999) /* insert the data */
    insert_end ( ) / *insert data at end */
    M = M + 1 /* Missionary count */
    scanf (N) /* pick a number */
    if ( M %2 == 0) /* even number, clockwise*/
    for (i = 1 to M-1)
    traverse_and_find(N) /* traverse and fin */

    else /* odd number, counterclock */
    for ( i = 1 to M-1)
    traverse_and_find( N ) /* traverse and delete */


    Ok following is the problem, Thanks for any help:

    A band of M missionaries is surrounded by a tribe of cannibals. The cannibals, being folks of small appetite, only demand one of them for dinner each day. The missionaries find drawing straws distasteful for people of their learning and sophistication. Instead, they form a circle and pick an integer N out of a hat. Then beginning with the first missionary in circle (We will tell you who the first one is), they start to count from one to N. The direction in which the count proceeds depends on the initial number of missionaries in the circle. If there are an even number of them, the count goes clockwise; otherwise, it goes counter-clockwise. Whenever N is reached, that missionary steps out of the circle and the count re-starts with the next person (note that the direction of the count does not change until the dinner du jour is decided). This process repeats until only one missionary is left in the ``circle'', who is the unfortunate one.

    For example, say that you have four missionaries A, B, C and D forming a circle clockwise in that order: On the first day, they pick 3. There are four of them so the count goes clockwise for the day. C is the first person out of the circle, B is the second and D is the third; A is consumed. On the second day, the new circle is C, B, D, and the count goes counter-clockwise. They pick 6. B is the first one out and D the second; C is consumed. On the third day, the new circle is B,D. They pick 1. B is the first one out and D is eaten. On the last day, B is consumed. So the order in which they are consumed is A,C,D,B.
    Last edited by bluga; 02-23-2002 at 11:20 PM.

  2. #2
    Join Date
    Aug 2001
    Groningen (NL)
    >i'm having trouble figuring out the traverse part

    Can't a circular linked list be created by letting the next-pointer in the last node point tot the first node in the linear list? In that case you could just do something like list_pr = current_node->next_node.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 5
    Last Post: 11-04-2006, 05:39 PM
  2. Circular doubly linked list with dummy header
    By mag_chan in forum C Programming
    Replies: 5
    Last Post: 10-31-2005, 07:44 AM
  3. doubly linked list problem
    By YevGenius in forum C Programming
    Replies: 4
    Last Post: 05-02-2004, 08:54 PM
  4. Linked list with two class types within template.
    By SilasP in forum C++ Programming
    Replies: 3
    Last Post: 02-09-2002, 05:13 AM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM