Thread: Array ADT Problem: PLEASE HELP!!

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

    Array ADT Problem: PLEASE HELP!!

    Hi, im new to C++, and im doing an Array ADT, the program basically works except my teacher wants me to do this right shift thing with teh array, where if you insert a number that is less than the number in the array, then it should move the number that is greater down the list, and then the lesser number should go in so that in a way it is in order. Im not allowed to use any type of sorting i suppose. i did most of the progam except this part, so here is a link to my program if you wanna compile it and stuff. the Insert function is on line 00100:
    youll know what im talking about when you see the page because the lines are numbered on the left hand side.

    http://sourcepost.sytes.net/source/s...source_id=1135


    PS My email address is [email protected], so email me if you can help!

  2. #2
    Registered User
    Join Date
    Jan 2002
    Posts
    559
    I didn't download your code, but I don't see how you can do this w/o a sort. Just doing the requirements is a sort. The requirements you state don't seem to make sense.

  3. #3
    Unregistered
    Guest
    be sure there is room in the array for the expansion (adequate capacity).
    determine current size of existing array, what is last used element
    starting with last element shift value of last element by size of expansion.
    shift next to last element (last element - 1) by size of expansion
    shift last element - 2 ty size of expansion.
    etc.
    until elements are open at site of expansion
    assign new value to open element.

  4. #4
    junior member mix0matt's Avatar
    Join Date
    Aug 2001
    Posts
    144
    you can do it without sorting, but you have to tell the method where to insert the element...here's a dirty example (didn't really test it and there's no error checking):

    Code:
    #include <iostream>
    
    using std::cout;
    using std::endl;
    
    class IntArray {
    private:
        int m_array[100];
        int m_size;
    
    public:
        IntArray (const int*, const int);
        void insert (int, int);
        void print ();
    };
    
    IntArray::IntArray (const int* array, const int size)
    {
        for (int i = 0; i < size; ++i)
            m_array[i] = array[i];
    
        m_size = size;
    }
    
    void IntArray::insert (int position, int number)
    {
        for (int i = m_size; i > position; --i)
            m_array[i] = m_array[i-1];
        m_array[position] = number;
        m_size++;
    }
    
    void IntArray::print ()
    {
        for (int i = 0; i < m_size; ++i)
            cout << m_array[i] << ' ' ;
        cout << endl;
    }
    
    int main ()
    {
        int array[] = { 1, 2,3, 5, 6, 7, 8, 9, 10 } ;
        int size = sizeof(array)/sizeof(int);
    
        IntArray ArrayObject (array, size);
        ArrayObject.print();
    
        ArrayObject.insert (3, 4);            // insert number 4 at position 3
        ArrayObject.print ();
    
        return 0;
    }
    Sorry there's no comments, but that's what you get for free.. This should help you figure out deletion too...

    also notice that my class holds a large "statically" allocated array. it would be a more useful class if it contained a dynamically allocated array, which could grow and shrink accordingly (only when necessary)...i'll let you handle that....
    Last edited by mix0matt; 01-28-2002 at 01:16 PM.

  5. #5
    Registered User
    Join Date
    Jan 2002
    Posts
    559
    The code still has to check whether the new value is larger before it shifts anything. This seems like a sorting operation on individual pairs to me.

  6. #6
    Unregistered
    Guest
    Originally posted by salvelinus
    The code still has to check whether the new value is larger before it shifts anything. This seems like a sorting operation on individual pairs to me.
    no, it doesn't....the new value is inserted at position passed in the argument regardless of the value of the surrounding values. The value of the elements in the array and the value inserted into the array are not relevant to this type of insertion...The only thing that the code should check is whether there is room in the array for the new value...

  7. #7
    Registered User
    Join Date
    Jan 2002
    Posts
    559
    Originally posted by Unregistered
    no, it doesn't....the new value is inserted at position passed in the argument regardless of the value of the surrounding values. The value of the elements in the array and the value inserted into the array are not relevant to this type of insertion...The only thing that the code should check is whether there is room in the array for the new value...
    Well, maybe I have a different idea of what a sort is. What does the following quote, from the original question posted, mean then? It seems like more than just inserting an element in the array. W/o some kind of comparison, how do you know if it's larger or not? Anf if you make a comparison and shift values around as a result, isn't that a sort operation?
    ...where if you insert a number that is less than the number in the array, then it should move the number that is greater down the list, and then the lesser number should go in so that in a way it is in order...

  8. #8
    junior member mix0matt's Avatar
    Join Date
    Aug 2001
    Posts
    144
    okay, okay...i've talked to s0ul2squeeze over email and salvelinus is correct. squeeze's teacher wants the position to be returned from a binary search function (where the value is located or where it should be inserted), which makes me think that the values will be read into the array with "insertion sort"...

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Problem Putting INTs Into a CHAR Array
    By cram in forum C++ Programming
    Replies: 13
    Last Post: 10-13-2004, 07:53 AM
  2. Problem with assigning value to array elements
    By sagitt13 in forum C++ Programming
    Replies: 3
    Last Post: 08-17-2004, 11:26 AM
  3. help w/ array problem
    By rhythm313 in forum C++ Programming
    Replies: 3
    Last Post: 11-12-2002, 12:12 AM
  4. Hi, could someone help me with arrays?
    By goodn in forum C Programming
    Replies: 20
    Last Post: 10-18-2001, 09:48 AM
  5. From stream/file to a string array problem
    By dradsws in forum C Programming
    Replies: 2
    Last Post: 10-01-2001, 06:24 PM