How to solve this problem using Linked List

Home Forums C Programming How to solve this problem using Linked List

This topic contains 0 replies, has 1 voice, and was last updated by  PRUTHVI KANTH 10 years, 3 months ago.

  • Author
    Posts
  • #1998

    Problem Description
    ===================
    A group of soldiers are queued arbitrarily in several rows. Each of them is given a unique natural number as his ID. Now they are supposed to be rearranged to form nice queues. The allowed operations on the queues are (You may copy these in your code to remind yourself):
    drmove n r1 r2
        Move the n-th soldier in row r1 to the end of row r2.
    srmove n r m
        Move the n-th soldier in row r so that after the move the soldier is in the m-th position in the same row.
    join r1 r2
        Join row r1 to the back of row r2.
    dispatch n r
        Delete the n-th soldier from row r

    Note: When a row becomes empty becuase of any of the above operations, the id of the subsequent row will decrease by one. For example, if you join row 2 to the end of row 3, row 2 will become empty and the new row 3 will become row 2, row 4 will become row 3, etc.
    Input
    =====
    The first line consists of a single integer r indicating the number of rows.
    The next r lines each consists of a list of integers.
    The second line is the 0-th row.

    The (r+1)-th line is the (r-1)-th row.
    The next line consists of a single integer n indicating the number of operations.
    Each of the next n lines represents a valid operation.

    Output
    ======
    Print out the final arrangement obtained by performing the given operations in the input order. The format should be the same as given in the input. Each line
    represents a row, and in a row two consecutive ID’s should be separated by a single blank.

    Sample Input
    ============
    5   // r
    1 3 4 5   // row 0
    2   // row 1
    6   // row 2
    7 8 9 10  // row 3
    101   // row 4
    5   // n
    join 1 0  
    drmove 0 1 2 
    srmove 4 0 1
    srmove 4 1 0
    dispatch 0 2
    Note: the comments above are not part of the input values.

    Sample Output
    =============
    1 2 3 4 5
    6 7 8 9 10

    Implementation notes
    ====================
    You should implement at least a linked list for integers (then you can use an array of such linked list to represent the queues). If you know how to implement
    general linked list, go ahead and do it. I would appreciate any form of help from the experts out there :)

You must be logged in to reply to this topic.

0 Shares
Share
+1
Tweet
Share
Stumble