Solved

Inserting into an array using pointers

Posted on 2004-10-06
16
188 Views
Last Modified: 2011-04-14
I have a struct:

struct ListArray
{
      int *list;                  
      int listMax;            
      int listCount;            
};

I created a list:

      ListArray zot;
      constructList(&zot, 15);

//function for the construct list
void constructList(ListArray *listx, int maxLength)
{
      (*listx).list = new int[maxLength];
      (*listx).listCount = 0;
      (*listx).listMax = maxLength;
}
// End of contructList

I populated the list like so:
      zot.listCount = 6;
      zot.list[0] = 47;
      zot.list[1] = 99;
      zot.list[2] = 36;
      zot.list[3] = 2;
      zot.list[4] = 15;

Now, I want to create a function, where i can send a value that will get added to this list. It will first scan through the list to see if the list is full, if so it quits. If the list is empty it adds it to the first element. If it is a non empty list (this is where i am stuck!!!) it first finds the insertion point , moves everything down one, inserts the item and adjusts the count.

Any idea how this can be done...
0
Comment
Question by:KalluMama
  • 9
  • 7
16 Comments
 
LVL 30

Expert Comment

by:Axter
Comment Utility
Why not use an std::vector or std::list container?
0
 

Author Comment

by:KalluMama
Comment Utility
it is an assignment and this is the way we gotta do it.....and i am stuck!!!
0
 
LVL 30

Expert Comment

by:Axter
Comment Utility
You can use std::copy function to move the items.

#include <algorithm>
Example:

std::copy(zot.list + startPos, zot.list + ListSize, zot.list + startPos + 1);
0
 

Author Comment

by:KalluMama
Comment Utility
can't have not been taught that...
0
 
LVL 30

Expert Comment

by:Axter
Comment Utility
By using std::copy, you can move the list object if you know StartPos, ListLen, and Quantity to move.

std::copy(zot.list + startPos, zot.list + ListSize, zot.list + startPos + MoveQty);
0
 

Author Comment

by:KalluMama
Comment Utility
not allowed to use any of that...since we are not supposed to know that...since we have not covered that...
0
 
LVL 30

Expert Comment

by:Axter
Comment Utility
>>can't have not been taught that...

Then you can do it manually, via a for-loop.

for(int* it = zot.list + startPos; it != zot.list + ListSize - MoveQty; ++i)
 *(it+MoveQty) = (*it);
0
 

Author Comment

by:KalluMama
Comment Utility
where do startpos listsize and moveqty come from??? not sure we can use these if we have not been taught these....
0
What Is Threat Intelligence?

Threat intelligence is often discussed, but rarely understood. Starting with a precise definition, along with clear business goals, is essential.

 
LVL 30

Expert Comment

by:Axter
Comment Utility
startPos should be a zero based index into the array.
MoveQty should be the number of objects you want to move.
ListSize is the size of the Current List.

So for your code it might look like this to insert one item:
for(int* it = zot.list + startPos; it != zot.list + zot.listCount ; ++i)
*(it+1) = (*it);
0
 
LVL 30

Expert Comment

by:Axter
Comment Utility
>>where do startpos listsize and moveqty come from???

These are variables that you create.
You need to create code to search for the insertion point.
Then make the startPos variable equal to the insertion point.

More then likely, you can startPos will be an int variable or size_t;
int startPos = 3; //Modify this value to the insertion point.
0
 
LVL 30

Expert Comment

by:Axter
Comment Utility
FYI:
It's against EE policy for me to provide a full and complete answer to a homework question.

We can help you along with existing code, but we can not post a complete answer.
0
 

Author Comment

by:KalluMama
Comment Utility
i understand...i don't really need the answer..but just a nudge....
0
 

Author Comment

by:KalluMama
Comment Utility
OK i have figured out how to determine where to insert, now the question is how do i make room for the new insertion??

I have already sorted the list...

      //Find insertion point
      int xx;
      int insertPt = listx->list[0];
      for (xx = 0; xx < listx->listCount; ++xx)
      {
            if (target < listx->list[xx])
            {
            insertPt = listx->list[xx];
                        //Here i know the element  from where i want to make an insertion by shifting the rest of the data down
                  cout << endl << insertPt << endl << xx;    
                  return true;
            }
      }
0
 
LVL 30

Accepted Solution

by:
Axter earned 500 total points
Comment Utility
Example:
   //Find insertion point
     int xx;
     int insertPt = listx->list[0];
     for (xx = 0; xx < listx->listCount; ++xx)
     {
          if (target < listx->list[xx])
          {
            insertPt = listx->list[xx];
                        //Here i know the element  from where i want to make an insertion by shifting the rest of the data down
               cout << endl << insertPt << endl << xx;    
               
               //Now move xx to xx+1 until the end of the list
               for(int* it = zot.list + xx; it != zot.list + zot.listCount ; ++i)
                  *(it+1) = (*it);

               //Now set xx to target
               listx->list[xx] = target;

               return true;
          }
     }
0
 

Author Comment

by:KalluMama
Comment Utility
I got it to work. The thing was i was not supposed to sort the list, just plug each value in as it comes in, so this is what it did:

/////////////////////////////////////////////////////////////////////////
// Insert an item into the list (ordered)                                             
/////////////////////////////////////////////////////////////////////////
bool insertOrdered(ListArray *listx, int target)
{
      //If list is full insertion fails
      if(listx->listCount == listx->listMax)
            return false;

      //Insert into empty list
      if(!listx->listCount)            
      {
            listx->list[0] = target;
            ++listx->listCount;
            return true;
      }

      //If the list is not empty or full, do this...

      //First, find the insertion point by putting a work pointer variable
      //(insertionPoint) on the first item of the list
      int *insertionPoint;
      int myCount = 0;
      bool insertFound = false;            //if False, then not found, if True then record found

      insertionPoint = listx->list;

      //use this while statement to find the insertion point
      while(myCount <= listx->listCount && insertFound == false)
      {
            if(target >= *insertionPoint)            //insertion point not found
            {
                  ++insertionPoint;                        //move the insertion point to the next element
            }
            else                                                //insertion point found
            {
                  insertFound = true;                        //set this to true since you found the insertion point
                  cout << endl << endl << "Addess: " << insertionPoint << endl << "Contents:" << *insertionPoint;
            }//end if

            ++myCount;                                          //count to see how many elements i have read
      }//end while


      //There are two reasons the loop finished, one coz we reached the end of the list or
      //we found the insertion point
      if (myCount > listx->listCount)                  //if we reached the end of the list then...
      {
            listx->list[listx->listCount] = target; //...append target to the end of it
            ++listx->listCount;
            return true;
      }
      else                                                            //if we found the insertion point...
      {
            int *moveDown;
            moveDown = &listx->list[listx->listCount - 1];

            while(moveDown >= insertionPoint)
            {
                  moveDown[1] = *moveDown;
                  --moveDown;

                  
            } //end while

            *insertionPoint = target;
            //listx->list[listx->listCount - 1] = target;
            ++listx->listCount;
            return true;

      }//end if


      return true;
}
// end of insertOrdered

I called it this way::::

      int target = 0;
      target = 420;
      cout << endl
             << "inserting: "
             << target;
      if(!insertOrdered(&zot, target))
            cout << endl
                   << "List zot: insertion failed";
            cout << endl
             << "list zot";
      displayList(zot);
getch();

      target = 68;
      cout << endl
             << "inserting: "
             << target;
      if(!insertOrdered(&zot, target))
            cout << endl
                   << "List zot: insertion failed";
            cout << endl
             << "list zot";
      displayList(zot);
getch();


Thanks for your help Axter!!!
0
 
LVL 30

Expert Comment

by:Axter
Comment Utility
Thank you for the A grade :-)
0

Featured Post

Highfive Gives IT Their Time Back

Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

Join & Write a Comment

This article will show you some of the more useful Standard Template Library (STL) algorithms through the use of working examples.  You will learn about how these algorithms fit into the STL architecture, how they work with STL containers, and why t…
IntroductionThis article is the second in a three part article series on the Visual Studio 2008 Debugger.  It provides tips in setting and using breakpoints. If not familiar with this debugger, you can find a basic introduction in the EE article loc…
The goal of the tutorial is to teach the user how to use functions in C++. The video will cover how to define functions, how to call functions and how to create functions prototypes. Microsoft Visual C++ 2010 Express will be used as a text editor an…
The viewer will be introduced to the technique of using vectors in C++. The video will cover how to define a vector, store values in the vector and retrieve data from the values stored in the vector.

763 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

9 Experts available now in Live!

Get 1:1 Help Now