Home Forums C Programming Algorithms In C++ (Urgently needed) Re: Re: Algorithms In C++ (Urgently needed)

#3579
GWILouisaxwzkla
Participant

first part:


/****************************************************************
* File Name : c:programstempCG.cpp
* Date : June,2,2009
* Comments : new project
* Compiler/Assembler :
* Modifications :
*
*
*
*
*
* Program Shell Generated At: 12:54:06 p.m.
=-=-=-=-=-=-=-=--=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=*/


#include
//#include
//#include
//#include
//#include
//#include

//using namespace std;


//@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ FUNCTION PROTOTYPES @@@@@@@@@@@@@@@@@@@@@@@@@@

int binarySearch ( int * array , int itemToFind , int maxItems );
int sequentialSearch ( int * array , int itemToFind , int maxItems );

//##################################################################################


//main function ******************************

int main ( )
{
int array [ 10 ] = { 1 , 2 , 3 , 4 , 5 , 6 ,7 , 8 , 9 , 10 };
int indexFoundAt;
int itemToFind ;

printf ( "enter an item to find ( 1 to 10 ) n" );
scanf ( "%i" , & itemToFind );



indexFoundAt = binarySearch ( array , itemToFind , 10 );
printf ( "The item %i was found at index %i n" , itemToFind , indexFoundAt );
indexFoundAt = sequentialSearch ( array , itemToFind , 10 );
printf ( "The item %i was found at index %i n" , itemToFind , indexFoundAt );
return 0 ;
}


/******************************* FUNCTION DEFINITION ******************************

Name : binarySearch
Parameters :

array a(n) int * ,
maxItems a(n) int


Returns: Void type
Comments:



++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
int binarySearch ( int * array , int itemToFind , int maxItems )
{

int left , right;
int midPoint = ( ( maxItems - 1 ) + 0 ) / 2;


left = 0;
right = maxItems - 1;

while ( array [ midPoint ] != itemToFind && right > left )
{
if ( array [ midPoint ] > itemToFind )
{
right = midPoint - 1;
midPoint = ( right + left ) / 2;
}
else
{
left = midPoint + 1;
midPoint = ( right + left ) / 2;
}

}
if ( array [ midPoint ] == itemToFind )
return midPoint;
else
return -1; //not found
}
/******************************* FUNCTION DEFINITION ******************************

Name : sequentialSearch
Parameters :

array a(n) int * ,
maxItems a(n) int


Returns: Void type
Comments:



++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
int sequentialSearch ( int * array , int itemToFind , int maxItems )
{

int i = 0;

while ( i < maxItems && array [ i ] != itemToFind )
i ++;

if ( array [ i ] == itemToFind )
return i;
else
return -1; //not found
}




second part:


/****************************************************************
* File Name : c:programstempCG.cpp
* Date : June,2,2009
* Comments : new project
* Compiler/Assembler : Visual C++ 6.0
* Modifications :
*
*
*
*
*
* Program Shell Generated At: 1:42:17 p.m.
=-=-=-=-=-=-=-=--=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=*/


#include
#include
//#include
//#include
//#include
//#include

//using namespace std;

struct node
{

int data;
node * prior;
node * next;
};



//@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ FUNCTION PROTOTYPES @@@@@@@@@@@@@@@@@@@@@@@@@@

void addNodeFront ( int item , node ** frontNode , node ** backNode );
void addNodeBack ( int item , node ** frontNode , node ** backNode );
void printList ( node * front );
void destroyList ( node * front );

//##################################################################################


//main function ******************************

int main ( )
{

node * front = 0;
node * back = 0;


addNodeFront ( 1 , & front , & back );
addNodeBack ( 2 , & back , & back );
printList ( front );
destroyList ( front );
return 0 ;
}


/******************************* FUNCTION DEFINITION ******************************

Name : addNodeFront
Parameters :

item a(n) int ,
frontNode a(n) node ** ( node ** )


Returns: Void type
Comments:



++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
void addNodeFront ( int item , node ** frontNode , node ** backNode )
{

node * temp = ( node * ) malloc ( sizeof ( node ) );
if ( temp == 0 )
{
printf ( "allocation error n " );
return;
}

if ( * frontNode == 0 ) //empty list
{
temp -> data = item;
temp -> prior = 0;
temp -> next = 0;
* frontNode = temp;
* backNode = temp;
}
else //one node
{
temp -> data = item;
temp -> next = * frontNode;
( * frontNode ) -> prior = temp;
temp -> prior = 0;
* frontNode = temp;
}
return;
}
/******************************* FUNCTION DEFINITION ******************************

Name : addNodeBack
Parameters :

item a(n) int ,
backNode a(n) node ** ( node ** )


Returns: Void type
Comments:



++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
void addNodeBack ( int item , node ** frontNode , node ** backNode )
{

node * temp = ( node * ) malloc ( sizeof ( node ) );
if ( temp == 0 )
{
printf ( "allocation error n " );
return;
}

if ( * frontNode == 0 ) //empty list
{
temp -> data = item;
temp -> prior = 0;
temp -> next = 0;
* frontNode = temp;
* backNode = temp;
}
else //one node
{
temp -> data = item;
temp -> next = 0;
( * backNode ) -> next = temp;
temp -> prior = * backNode;
* backNode = temp;
}
return;


}
/******************************* FUNCTION DEFINITION ******************************

Name : printList
Parameters :

front a(n) node * ( node * )


Returns: Void type
Comments:



++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
void printList ( node * front )
{

node * temp = front;

while ( temp != 0 )
{
printf ("%i " , temp -> data , " " );
temp = temp -> next;

}
return;
}
/******************************* FUNCTION DEFINITION ******************************

Name : destroyList
Parameters :

front a(n) node * ( node * )


Returns: Void type
Comments:



++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
void destroyList ( node * front )
{

node * temp = front;

while ( temp != 0 )
{
front = temp -> next;
free ( temp );
temp = front;
}

return;
}

bubble sort:


/****************************************************************
* File Name : c:programstempCG.cpp
* Date : March,28,2009
* Comments : new project
* Compiler/Assembler : Visual C++ 6.0
* Modifications :
*
* Notes: A good sort for a small number of items. Total run time
* is proportional to the number of items squared ( o ( N^2 ) ).
*
*
* Program Shell Generated At: 11:25:48 a.m.
=-=-=-=-=-=-=-=--=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=*/


#include
//#include
//#include
//#include
//#include
//#include
#include
#include

using namespace std;

//>>>>>>>>>>>>>>>>>>>>>>>> GLOBAL DATA <<<<<<<<<<<<<<<<<<<<<<<<<
const int MAX_NUMBERS = 50;
int NUMBERS_PER_LINE = 15;
//<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<




//@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ FUNCTION PROTOTYPES @@@@@@@@@@@@@@@@@@@@@@@@@@

void generateNumbers ( int * numbers , int numberItems );
void bubbleSort ( int * array , int numberItems );
void printArray ( int * array , int numberItems );

//##################################################################################


//main function ******************************

int main ( )
{

int array [ MAX_NUMBERS ];
generateNumbers ( array , MAX_NUMBERS );
cout << endl << endl;
cout << "unsorted array " << endl;
printArray ( array , MAX_NUMBERS );
bubbleSort ( array , MAX_NUMBERS );
cout << endl << endl << "sorted array: " << endl;
printArray ( array , MAX_NUMBERS );
cout << endl;


return 0 ;
}


/******************************* FUNCTION DEFINITION ******************************

Name : bubbleSort
Parameters :

array a(n) int * ,
numberItems a(n) int


Returns: Void type
Comments:



++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
void bubbleSort ( int * array , int numberItems )
{

int endSortedArray = numberItems - 1;
int lastSwapIndex;
int temp;
while ( endSortedArray > 0 ) //while not at the end of the unsorted array
{
lastSwapIndex = 0; //save index of the last item swapped
int i = 0; //start at the beggining of the unsorted array
while ( i < endSortedArray ) //while not in the sorted items
{
if ( array [ i ] > array [ i + 1 ] ) //if current item is smaller than next , bubble up
{
//swap array [ i ] and array [ i + 1 ]
temp = array [ i ];
array [ i ] = array [ i + 1 ];
array [ i + 1 ] = temp;
lastSwapIndex = i;
}
i ++;
}
endSortedArray = lastSwapIndex; //reset swap boundry
}



return;
}
/******************************* FUNCTION DEFINITION ******************************

Name : printArray
Parameters :

array a(n) int * ,
numberItems a(n) int


Returns: Void type
Comments:



++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
void printArray ( int * array , int numberItems )
{


int i = 0;
cout << endl << endl;
cout << "array : " << endl;
while ( i < numberItems )
{
cout << array [ i ] << " " ;
if ( i != 0 )
if ( i % NUMBERS_PER_LINE == 0 )
cout << endl;
i ++;
}

return;
}
/******************************* FUNCTION DEFINITION ******************************

Name : generateNumbers
Parameters :

numbers a(n) int ,
numberItems a(n) int


Returns: Void type
Comments:



++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
void generateNumbers ( int * numbers , int numberItems )
{

int i = 0;

srand ( time ( NULL ) );
while ( i < numberItems )
{
numbers [ i ] = rand () % MAX_NUMBERS;
i ++;
}


return;
}


selection sort:


/****************************************************************
* File Name : c:programstempCG.cpp
* Date : March,28,2009
* Comments : new project
* Compiler/Assembler : Visual C++ 6.0
* Modifications :
*
* Notes: A good sort for a small number of items. Total run time
* is proportional to the number of items squared ( o ( N^2 ) ).
*
*
* Program Shell Generated At: 11:25:48 a.m.
=-=-=-=-=-=-=-=--=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=*/


#include
//#include
//#include
//#include
//#include
//#include
#include
#include

using namespace std;

//>>>>>>>>>>>>>>>>>>>>>>>> GLOBAL DATA <<<<<<<<<<<<<<<<<<<<<<<<<
const int MAX_NUMBERS = 50;
int NUMBERS_PER_LINE = 15;
//<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<




//@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ FUNCTION PROTOTYPES @@@@@@@@@@@@@@@@@@@@@@@@@@

void generateNumbers ( int * numbers , int numberItems );
void selectionSort ( int * array , int numberItems );
void printArray ( int * array , int numberItems );

//##################################################################################


//main function ******************************

int main ( )
{

int array [ MAX_NUMBERS ];
generateNumbers ( array , MAX_NUMBERS );
cout << endl << endl;
cout << "unsorted array " << endl;
printArray ( array , MAX_NUMBERS );
selectionSort ( array , MAX_NUMBERS );
cout << "sorted array: " << endl;
printArray ( array , MAX_NUMBERS );
cout << endl;


return 0 ;
}


/******************************* FUNCTION DEFINITION ******************************

Name : selectionSort
Parameters :

array a(n) int * ,
numberItems a(n) int


Returns: Void type
Comments: Slow n^2 algorithm



++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
void selectionSort ( int * array , int numberItems )
{

int i = 0 , j , minimumIndex , temp;

while ( i <= numberItems )
{
minimumIndex = i; //select i to be smallest index
j = minimumIndex + 1; //start sorting at next index after
while ( j <= numberItems )
{
if ( array [ j ] < array [ minimumIndex ] ) //if we have found a smaller than minimum
{ //element , mark current as smallest
minimumIndex = j;
}
j ++; //goto next item in the array
}
if ( minimumIndex != numberItems ) //if we found a smaller item put it at the front
{ //of the sorted array
temp = array [ minimumIndex ]; //swap items
array [ minimumIndex ] = array [ i ];
array [ i ] = temp;
}
i ++; //goto next item in the array
}


return;
}
/******************************* FUNCTION DEFINITION ******************************

Name : printArray
Parameters :

array a(n) int * ,
numberItems a(n) int


Returns: Void type
Comments:



++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
void printArray ( int * array , int numberItems )
{


int i = 0;
cout << endl << endl;
cout << "array : " << endl;
while ( i < numberItems )
{
cout << array [ i ] << " " ;
if ( i != 0 )
if ( i % NUMBERS_PER_LINE == 0 )
cout << endl;
i ++;
}

return;
}
/******************************* FUNCTION DEFINITION ******************************

Name : generateNumbers
Parameters :

numbers a(n) int ,
numberItems a(n) int


Returns: Void type
Comments: Generates an array of random numbers.



++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
void generateNumbers ( int * numbers , int numberItems )
{

int i = 0;

srand ( time ( NULL ) );
while ( i < numberItems )
{
numbers [ i ] = rand () % MAX_NUMBERS;
i ++;
}


return;
}