How to shift elements of an array?

This is a discussion on How to shift elements of an array? within the C Programming forums, part of the General Programming Boards category; Hi, I have an 1D array with depth values (say from 0 to 5cm). The user will input an amount ...

  1. #1
    Registered User
    Join Date
    May 2009
    Posts
    16

    How to shift elements of an array?

    Hi,

    I have an 1D array with depth values (say from 0 to 5cm). The user will input an amount to shift the depth (say shift=2cm). How would I then use the value to produce a second array that has the depth from 1 to 3cm and then have zeros in the elements after 3cm so that the new array is the same size as he original?

    Such as:
    a[0]: 0
    a[1]: 1
    a[2]: 2
    a[3]: 3
    a[4]: 4
    a[5]: 5

    becomes:
    a[0]: 2
    a[1]: 3
    a[2]: 4
    a[3]: 5
    a[4]: 0
    a[5]: 0

    Thanks for your help!

  2. #2
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    Use a for loop and assignment... Try it yourself first. Just iterate over the index of the array and assign the proper value.

  3. #3
    {Jaxom,Imriel,Liam}'s Dad Kennedy's Avatar
    Join Date
    Aug 2006
    Location
    Alabama
    Posts
    1,065
    Use a loop. (show some code for further help).

    EDIT: Bummer, dup post and I was last.

  4. #4
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,692
    Better would be to use a stack. They seem to be a common subject these days so look around the C forum for implementation details.

  5. #5
    {Jaxom,Imriel,Liam}'s Dad Kennedy's Avatar
    Join Date
    Aug 2006
    Location
    Alabama
    Posts
    1,065
    Quote Originally Posted by whiteflags View Post
    Better would be to use a stack. They seem to be a common subject these days so look around the C forum for implementation details.
    Given an array of, say 4096. You think it would be better to use a stack? How would you go about this? Are you speaking of recursion?

  6. #6
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by Kennedy View Post
    Given an array of, say 4096. You think it would be better to use a stack? How would you go about this? Are you speaking of recursion?
    A stack might be defined like this:
    Code:
    struct stack {
          int *array,  
               size,
               first_element;  
    };
    Then you have push and pop functions to operate on this. Notice you can shift the first element without moving the array at all and use size-first_element to determine when to wrap around.

    More detailed explanation here:

    Stack - Array Implementation
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  7. #7
    Registered User
    Join Date
    Jan 2009
    Posts
    1,485
    I don't see how a stack could be used to shift the individual elements. But I suppose the illusion of a shift could be done by doing something similar as above, then have a function returning a pointer to the "new" base of the array.

  8. #8
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by Subsonics View Post
    I don't see how a stack could be used to shift the individual elements.
    In the OP's original post the whole thing is being shifted, there are no insertions or deletions. You pop two elements off the top ( 0 and 1) then add two zeros to the end.

    I guess that is a loose use for the term "pop" -- this is actually a double ended queue, but big dif. It's certainly much more efficient that reassigning every element to a new position.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  9. #9
    Registered User
    Join Date
    Jan 2009
    Posts
    1,485
    Yes, but if the original array is {0, 1, 2, 3, 4} then doing two pop operations would give {0, 1, 2} not
    {2, 3, 4, 0, 0}.

  10. #10
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    Why the #(-|| would you use a stack for this? That's called an anti-pattern. And a queue isn't a good idea either...
    Just use an array and a for loop.

    With a stack, we lose the possibly important feature of random access, or we use an O(n) operation for shifting.
    Granted, a queue MAY be better suited for what this guy wants, but with the information he has given us, there is no reason to assume this is the case.

  11. #11
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by Subsonics View Post
    Yes, but if the original array is (0, 1, 2, 3, 4) then doing two pop operations would give (0, 1, 2) not
    (2, 3, 4, 0, 0).
    That's why I said it's a loose use of "pop" and really this is double ended queue. Which the term I'm used to there (meaning: pop from top) is "shift". If you shift two off (0, 1, 2, 3, 4) you have (2, 3, 4). Now push two zero's.

    What that really means is you would move first_element forward two (from [0] to [2]) then replace [0] and [1] with zeros. The queue still has a size of 5, so it wraps around and the "last element" is now first_element-1, ie [1].

    I'm not gonna write the whole thing out, I think anyone with a brain can figure on the details

    Quote Originally Posted by EVOEx View Post
    With a stack, we lose the possibly important feature of random access, or we use an O(n) operation for shifting.
    Granted, a queue MAY be better suited for what this guy wants, but with the information he has given us, there is no reason to assume this is the case.
    Who's implementation are we on about?* Nb, my shift as descibed is a whole lot better than O(n). The underlying structure is still an array, not a linked list, so random access just requires quick arithmetic on first_element.

    * nb, I cannot make promises about the link I posted, I have not used it personally or looked at it thoroughly but the idea is there (you define the stack as a struct containing an array and implement push/pop functions, plus in this case I guess a shift and remove or something).
    Last edited by MK27; 06-07-2010 at 10:47 AM.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  12. #12
    Registered User
    Join Date
    Jan 2009
    Posts
    1,485
    But, to nitpick, then it's not a stack. My comment was aimed at the use of a stack nothing else. Moving pointers about, and giving the illusion of a true shift is a solution that should work as well, which I mentioned earlier as well.

    BTW if the range and size of values in the first post is representative of what is needed in the real program a true bit shift could be done on the whole array as well (given that it's < 9 in size and contains only chars).
    Last edited by Subsonics; 06-07-2010 at 11:18 AM.

  13. #13
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by Subsonics View Post
    But, to nitpick, then it's not a stack.
    Nitpick eh...I would define a stack based on it's external functionality. You have to fulfill some qualifications, like push & pop functions that work FILO. How that's accomplished doesn't matter. If you can pop and push FILO style it will be identical for the user to a stack, hence it's a stack.

    Whether or not the bottom/top corresponds absolutely to the first and last index of an array is irrelevant as long as you black box the interface (eg, use function calls -- get/set(stack_pointer, 3) -- instead of subscripting).
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  14. #14
    Registered User
    Join Date
    Jan 2009
    Posts
    1,485
    Quote Originally Posted by MK27 View Post
    Nitpick eh...I would define a stack based on it's external functionality. You have to fulfill some qualifications, like push & pop functions that work FILO. How that's accomplished doesn't matter. If you can pop and push FILO style it will be identical for the user to a stack, hence it's a stack.
    Yeah, exactly. That is what I am doing. You put things on the stack and take them out according to the LIFO principle. That's it. There is only one entry point, you can't change the base of a stack with your push and pop operations.

    Quote Originally Posted by MK27 View Post
    Whether or not the bottom/top corresponds absolutely to the first and last index of an array is irrelevant as long as you black box the interface (eg, use function calls -- get/set(stack_pointer, 3) -- instead of subscripting).
    Yeah, well if it's irrelevant that means that the use of LIFO is also irrelevant, which of course it isn't. You can only do operations on the last element added to the stack, hence it's using a Last In First Out principle. Agreed?

  15. #15
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,304
    MK27 is perfectly right. It's a stack if it's exposed functionality supports the operations of a stack.
    You can only say something is not a stack if it doesn't support the necessary operations.
    Some would go so far as to say perhaps being bounded by certain time constraints as well. e.g. amortised O(1) time pop. Using a circular buffer as the underlying container still fits that as well.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 2
    Last Post: 07-11-2008, 07:39 AM
  2. using realloc for a dynamically growing array
    By broli86 in forum C Programming
    Replies: 10
    Last Post: 06-27-2008, 05:37 AM
  3. Struct *** initialization
    By Saravanan in forum C Programming
    Replies: 20
    Last Post: 10-09-2003, 12:04 PM
  4. how to make array elements shift one to the right?
    By Unregistered in forum C++ Programming
    Replies: 4
    Last Post: 05-03-2002, 11:28 PM
  5. A simple question about selecting elements in an array
    By Unregistered in forum C++ Programming
    Replies: 1
    Last Post: 08-30-2001, 10:37 PM

Tags for this Thread


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