array rotation?

This is a discussion on array rotation? within the C++ Programming forums, part of the General Programming Boards category; Can anyone show me how to write a function that takes an array of ints and moves each one forward ...

  1. #1
    Registered User
    Join Date
    Jan 2002
    Posts
    5

    Thumbs down array rotation?

    Can anyone show me how to write a function that takes an array of ints and moves each one forward replacing the first with the last without using a temporary array? -Whew!

  2. #2
    ¡Amo fútbol!
    Join Date
    Dec 2001
    Posts
    2,136
    Try using a temp variable then by pushing the last item in a row into temp and then shifting everyone over from the last one. From here, store the 1st item in the row into the temp.

    If you can't use a temp, you might need to use pop and push(which I do not know how to use)

  3. #3
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,584
    You could do this using stacks but I think this way is much easier.

    Your array, no matter how many dimensions, is just a long line of info whether it be bytes, words, or doublewords. The only temp you need is a variable. Before you rotate everything right by one, save the very last element in the array in a temp variable. This value will be rotated out of the array and you must save it.

    After rotating everything by one, place the temp value at element 0. Your array has correctly been rotated.

    0 2 4 5 7 8

    After rotation to the right by one

    0 0 2 4 5 7 -> 8 will be rotated out of the array or shifted out

    Save 8 in temp variable

    Place temp variable value (8) at start of array
    8 0 2 4 5 7 -> Array has been rotated right by 1

    If you rotate by a number larger than 1, you will need to preserve as many values as you are rotating by since they will be rotate out of the array.

    For left rotation, just preserve first value and place at last element after rotation.


    Push and pop
    Push and pop are very easy stack ops. Push will push a value onto the stack. Pop will pop the first value off of the stack. Stacks always grow downward.

    1
    0
    5
    6
    7

    stack.pop(MyValue)

    Stack now looks like this:

    0
    5
    6
    7

    and 1 has been stored in MyValue

    stack.push(10)

    will look like this

    10
    0
    5
    6
    7

    10 has been pushed onto the stack and all values move down one position. If there is no room for the bottom value in the stack after the push the stack has overflowed. In this example an overflow is no big deal, but in memory that last value will be pushed into someone else's memory space which could be code data, or some other program's stack.

    AI routines and pathfinding routines often use stacks since it is easy to do complex operations by pushing different actions onto the stack. To retrieve the current op just pop and execute the action.

    Stacks use FILO - first on, last off.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 16
    Last Post: 05-29-2009, 07:25 PM
  2. from 2D array to 1D array
    By cfdprogrammer in forum C Programming
    Replies: 17
    Last Post: 03-24-2009, 10:33 AM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Unknown Memory Leak in Init() Function
    By CodeHacker in forum Windows Programming
    Replies: 3
    Last Post: 07-09-2004, 09:54 AM
  5. Quick question about SIGSEGV
    By Cikotic in forum C Programming
    Replies: 30
    Last Post: 07-01-2004, 07:48 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21