Problem 2.10. We wish to store a list in an array A whose cells consist of two fields,
data to store an element and position to give the (integer0 position of the element.
An integer last indicates that A[0] through A[last] are used to hold the list.
The type LIST can be defined by
type
LIST = record
last := integer;
elements: array[1.. maxlength] of record
data: elementtype;
position: integer
end
end;
//problem 2.10.
#include <iostream>
#include <string>
using namespace std;
struct REC
{
int nData;
int nPos; //starts from 1.
};
struct LIST
{
int nLast; //points to the last element in the list.
//size of the list = nLast+1
REC list[10]; //Statically allocated for simplicity.
//This would be replaced by a pointer to an array in a
//profressional program.
};
void CreateList(LIST* listStr);
bool ListHasSpace(LIST* listStr);
void PrintList(LIST* listStr);
bool AddElementToList(LIST* listStr, int data, int pos);
void DeleteElemAtPos(LIST* listStr);
void main()
{
LIST listStr;
memset(&listStr,0,sizeof(listStr)); //memset to set everything to 0.
//elements with 0 position are invalid as position starts with 1.
listStr.nLast = 9; //10-1 because the list can only hold 10 objects for now
//Create the list by taking user input
CreateList(&listStr);
cout << "List created." << endl;
PrintList(&listStr);
string sAns = "n";
while(1)
{
DeleteElemAtPos(&listStr);
PrintList(&listStr);
cout << "Continue with deletions (y/n)?:";
cin >> sAns;
if( sAns[0] == 'n' || sAns[0] == 'N' )
break;
}
}
void CreateList(LIST* listStr)
{
if( !listStr )
return;
while( ListHasSpace(listStr) )
{
int data = 0;
int pos = 0;
PrintList(listStr);
cout << "Enter the data for element in the list:";
cin >> data;
cout << endl;
cout << "Enter the position of this data item in the list:";
cin >> pos;
if( !AddElementToList(listStr, data, pos) )
{
cout << "Invalid position." << endl;
}
}
}
//Returns true if there are empty elements in the list.
//Empty elements are defined by a position of 0.
bool ListHasSpace(LIST* listStr)
{
if( !listStr )
return false;
for( int n = 0; n < listStr->nLast+1; n++ )
{
if( listStr->list[n].nPos == 0 )
return true;
}
return false;
}
void PrintList(LIST* listStr)
{
if( !listStr )
return;
if( listStr->nLast <= 0 )
return;
cout << "List --------> " << endl;
for( int n = 0; n < listStr->nLast+1; n++ )
{
if( listStr->list[n].nPos == 0 )
cout << "<Empty Element>" << endl;
else
cout << "Data [" << listStr->list[n].nData << "]" << " Pos [" << listStr->list[n].nPos << "]." << endl;
}
cout << "<----------- End of List" << endl;
}
//true if element can be successfully added - which means there is space in the list as well as position is unique
bool AddElementToList(LIST* listStr, int data, int pos)
{
if( !listStr )
return false;
if( pos == 0 )
return false;
//first validate if this position already exists in the list or not.
//if it does, error out
//and while we are traversing the list, find the next empty space too.
int nPositionInList = -1;
for( int n = 0; n < listStr->nLast+1; n++ )
{
if( nPositionInList == -1 && listStr->list[n].nPos == 0 )
nPositionInList = n;
if( listStr->list[n].nPos == pos )
{
//something is already there at this position.
return false;
}
}
if( nPositionInList == -1 )
{
return false;
}
//all set to add the element
listStr->list[nPositionInList].nData = data;
listStr->list[nPositionInList].nPos = pos;
return true;
}
void DeleteElemAtPos(LIST* listStr)
{
if( !listStr )
return;
int pos = -1;
cout << "Enter position of element to delete: " << endl;
cin >> pos;
if( pos == 0 )
{
cout << "Invalid Position." << endl;
return;
}
if( listStr->nLast <= 0 )
{
cout << "List is empty." << endl;
return;
}
//assumption: the list does not contain duplicate elements with the same position.
int posToDelete = -1;
//find the element that needs to be deleted.
for( int n = 0; n < listStr->nLast+1; n++ )
{
if( listStr->list[n].nPos == pos )
{
posToDelete = n;
break;
}
}
if( posToDelete == -1 )
{
cout << "Could not find element with position [" << pos << "]." << endl;
return;
}
cout << "Element at position [" << pos << "] will be deleted." << endl;
//Delete the element at the position by overwriting this with elements after it.
for( int n = posToDelete; n < listStr->nLast; n++ )
{
listStr->list[n].nData = listStr->list[n+1].nData;
listStr->list[n].nPos = listStr->list[n+1].nPos;
}
//one element less from the array.
listStr->nLast--;
}
