Home Forums C Programming Structures and Algorithms in C++ Re: Re: Structures and Algorithms in C++

#3620
GWILouisaxwzkla
Participant

could try:


/****************************************************************
* File Name : cgt.cpp
* Date : April,10,2007
* Comments : new project
* Compiler/Assembler : VC++ 6.0
*
*
*
*
*
* Program Shell Generated At: 2:59:58
=-=-=-=-=-=-=-=--=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=*/


#include < iostream >
//#include < string.h >
//#include < conio.h >
//#include < math.h >

using namespace std;

struct node
{

int data;
node * next;
node * back;

};


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

void readList ( node ** list );
bool listsAreEqual ( node * left , node * right );
node * copyList ( node * list );
void printList ( node * list );
void destroyList ( node ** list );
bool listsContainEqualMembers ( node * left , node * right );

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

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

int main ( )
{

node * head1 = 0;
node * head2 = 0;

cout << "enter first list :" << endl;
readList ( & head1 );
cout << "enter second list: " << endl;
readList ( & head2 );

if ( listsAreEqual ( head1 , head2 ) )
cout << endl << "The lists are equal" << endl;
else
cout << endl << "The lists are not equal" << endl;

cout << endl;
if ( listsContainEqualMembers ( head1 , head2 ) )
cout << endl << "lists contain equal members" << endl;
else
cout << endl << "lists do not contain equal members " << endl;


node * copy = copyList ( head1 );
cout << endl << "copy of first list is: ";
printList ( copy );
destroyList ( & head1 );
destroyList ( & head2 );
destroyList ( & copy );
return 0 ;
}


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

Name : readList
Parameters :



Returns: Void type
Comments:



++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
void readList ( node ** list )
{

cout << "enter an integer ( -1 to stop ) ";
int i;
cin >> i;
node * temp = 0;

while ( i != -1 )
{

temp = new node;
if ( temp == 0 )
{
cout << " allocation error" ;
( * list ) = 0;
return;
}
temp -> data = i ;
if ( ( * list ) == 0 )
{
( * list ) = temp;
temp -> next = 0;
temp -> back = temp;

}
else
{
( * list ) -> back -> next = temp;
temp -> next = temp -> back = 0;
( * list ) -> back = temp;
}
cout << "enter a number ( -1 to stop ) ";
cin >> i;
}

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

Name : listsAreEqual
Parameters :



Returns: user defined type , bool

Comments:



++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
bool listsAreEqual ( node * left , node * right )
{

bool matches = true;

while ( left != 0 && right != 0 && matches )
{

if ( left -> data != right -> data )
matches = false;
else
{
left = left -> next;
right = right -> next;
}
}
if ( ! left && ! right && matches )
return true;

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

Name : copyList
Parameters :



Returns: user defined type , node *

Comments:



++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
node * copyList ( node * list )
{

node * temp = 0;
node * newList = 0;

while ( list )
{

temp = new node;
if ( ! temp )
{
cout << "allocation error! ";
return 0;
}
if ( newList == 0 )
{
newList = temp;
temp -> data = list -> data;
newList -> next = 0;
newList -> back = temp;
}
else
{
temp -> data = list -> data;
newList -> back -> next = temp;
newList -> back = temp;
temp -> next = temp -> next = 0;
}
list = list -> next;
}
return newList;
}
void printList ( node * temp )
{


cout << "list read is " ;
while ( temp )
{
cout << temp -> data << " ";
temp = temp -> next;
}
cout << endl;
}
/******************************* FUNCTION DEFINITION ******************************

Name : destroyList
Parameters :



Returns: user defined type , void

Comments:



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


node * temp = ( * list );
node * temp2 = 0;
while ( temp )
{

temp2 = temp;
temp = temp -> next;
delete temp2;
}

( * list ) = 0;
}
/******************************* FUNCTION DEFINITION ******************************

Name : listsContainEqualMembers
Parameters :



Returns: Void type
Comments:



++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
bool listsContainEqualMembers ( node * left , node * right )
{


node * temp1 = left;
node * temp2 = right;
bool matches ;
int length1 = 0 , length2 = 0;
int numItems1 = 0 , numItems2 = 0;

while ( temp1 && matches )
{
temp2 = right;
matches = false;
length1 ++; //get length of first list
while ( temp2 && ! matches )
{
if ( temp1 -> data == temp2 -> data )
matches = true;
if ( ! matches )
temp2 = temp2 -> next;
}
if ( matches )
temp1 = temp1 -> next;
}
temp2 = right;
while ( temp2 )
{
length2 ++ ;
temp2 = temp2 -> next;
}
if ( length1 == length2 && matches )
return true;
return false;
}