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

Viewing 0 reply threads
  • Author
    • #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.
      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.

      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 :)

Viewing 0 reply threads
  • The forum ‘C Programming’ is closed to new topics and replies.