Im creating a program in C using structures and pointers. I have to add two polynomials together to one simplified one. The problem that I'm having is, the IsEmpty Function to test whether a linked list is empty returns true if L is empty and then prints "empty list". I am not sure why my linked list is empty after putting together my addPolynomial function. This function is located in the list.c file. Any help will be appreciated, thank you!
Header file:
#ifndef _List_H
#define _List_H
struct Node; //OK
typedef struct Node *PtrToNode; //OK
typedef PtrToNode List; //OK
typedef PtrToNode Position; //OK
List MakeEmpty( List L ); //OK
int IsEmpty( List L );
int IsLast( Position P, List L );
List addPolynomial(List L1, List L2);
Position FindPrevious( int e, List L );
void Insert( int c, int e, List L );
void DeleteList( List L );
Position Header( List L );
Position First( List L );
Position Advance( Position P );
int RetrieveCoefficient( Position P ); //OK
int RetrieveExponent( Position P ); //OK
#endif /* _List_H */
Print/test file:
#include <stdio.h>
#include <stdlib.h>
#include "list.h"
void PrintList( const List L ){
Position P = Header( L );
if( IsEmpty( L ) ) printf( "Empty list\n" );
else{
do{
P = Advance( P );
if(RetrieveCoefficient( P )>0){
printf( "%+dx^%d ", RetrieveCoefficient( P ), RetrieveExponent( P ));
}
else{
printf( "%dx^%d ", RetrieveCoefficient( P ), RetrieveExponent( P ));
}
} while( !IsLast( P, L ) );
printf( "\n" );
}
}
main(){
List L1,L2,L3;
Position P1,P2;
L1 = MakeEmpty( NULL );
P1 = Header( L1 );
L2 = MakeEmpty( NULL );
P2 = Header( L2 );
L3 = MakeEmpty( NULL );
Insert(3,5,L1);
Insert(2,3,L1);
Insert(-7,8,L1);
Insert(4,9,L1);
Insert(-9,1,L2);
printf("Polynomial 1:\n");
PrintList( L1 );
Insert(4,7,L2);
Insert(5,6,L2);
Insert(-4,3,L2);
Insert(-3,5,L2);
printf("Polynomial 2:\n");
PrintList( L2 );
L3 = addPolynomial(L1,L2);
printf("Polynomial 3:\n");
PrintList( L3 );
DeleteList( L1 );
DeleteList( L2 );
DeleteList( L3 );
return 0;
}
list.c file:
#include "list.h"
#include <stdlib.h>
#include "fatal.h"
/* Figure 3.23 Type declaration for linked list implementation of Polynomial ADT */
struct Node{
int Coefficient;
int Exponent;
PtrToNode Next;
};
List MakeEmpty( List L ){
if( L != NULL ) DeleteList( L );
L = (List) malloc( sizeof( struct Node ) );
if( L == NULL ) FatalError( "Out of memory!" );
L->Next = NULL;
return L;
}
/* Figure 3.8 Function to test whether a linked list is empty */
/* Return true if L is empty */
int IsEmpty( List L ){return L->Next == NULL;}
/* Figure 3.9 Function to test whether current position is the last in a linked list */
/* Return true if P is the last position in list L */
/* Parameter L is unused in this implementation */
int IsLast( Position P, List L ){
return P->Next == NULL;
}
/* END */
List addPolynomial(List L1, List L2){
List L; //Result of L1+L2
Position P,P1,P2;
L = MakeEmpty( NULL );
P = Header( L );
P1 = First(L1);
P2 = First(L2);
// While loops to be used
while (P1->Next && P2->Next)
{
//move pointer and leave 1st as is if exponent is greater than 2nd poly
if (P1->Exponent > P2->Exponent){
P->Exponent = P1->Exponent;
P->Coefficient = P1->Coefficient;
P1 = P1->Next;
}
//if exponent in 2nd is larger then store L2 and move pointer
else if (P1->Exponent < P2->Exponent){
P->Exponent = P2->Exponent;
P->Coefficient = P2->Coefficient;
P2 = P2->Next;
}
//if both are the same then they're added together
else{
P->Exponent = P1->Exponent;
P->Coefficient = P1->Coefficient + P2->Coefficient;
P1 = P1->Next;
P2 = P2->Next;
}
P->Next = /*(struct Node *)*/malloc(sizeof(struct Node));
P = P->Next;
P->Next = NULL;
}
while (P1->Next || P2->Next)
{
if (P1->Next) {
P->Exponent = P1->Exponent;
P->Coefficient = P1->Coefficient;
P1 = P1->Next;
}
if (P2->Next) {
P->Exponent = P2->Exponent;
P->Coefficient = P2->Coefficient;
P2 = P2->Next;
}
P->Next = /*(struct Node *)*/malloc(sizeof(struct Node));
P = P->Next;
P->Next = NULL;
}
L = P;
return L;
}
/* Figure 3.13 Insertion routine for linked lists */
/* Insert (after legal position P) */
/* Header implementation assumed */
/* Parameter L is unused in this implementation */
void Insert( int c, int e, List L){
Position TmpCell;
Position P = FindPrevious( e, L );
/* 1*/ TmpCell = malloc( sizeof( struct Node ) ); //(Position)
/* 2*/ if( TmpCell == NULL ) FatalError( "Out of space!!!" );
/* 3*/ TmpCell->Coefficient = c;
/* 4*/ TmpCell->Exponent = e;
/* 5*/ TmpCell->Next = P->Next;
/* 6*/ P->Next = TmpCell;
}
/* Figure 3.12 FindPrevious - the Find routine for use with Delete */
/* If X is not found, then Next field of returned value is NULL */
/* Assumes a header */
Position FindPrevious( int e, List L ){
Position P;
/* 1*/ P = L;
/* 2*/ while (P->Next != NULL && P->Next->Exponent != e)
/* 3*/ P = P->Next;
/* 4*/ return P;
}
/* Figure 3.15 Correct way to delete a list */
/* Correct DeleteList algorithm */
void DeleteList( List L ){
Position P, Tmp;
/* 1*/ P = L->Next; /* Header assumed */
/* 2*/ L->Next = NULL;
/* 3*/ while( P != NULL ){
/* 4*/ Tmp = P->Next;
/* 5*/ free( P );
/* 6*/ P = Tmp;
}
}
Position Header( List L ){ return L;}
Position First( List L ){ return L->Next;}
Position Advance( Position P ){ return P->Next;}
int RetrieveCoefficient( Position P ){ return P->Coefficient;}
int RetrieveExponent( Position P ){ return P->Exponent;}
fatal.h file:
#include <stdio.h>
#include <stdlib.h>
#define Error( Str ) FatalError( Str )
#define FatalError( Str ) fprintf( stderr, "%s\n", Str ), exit( 1 )
output to terminal:
Polynomial 1: +3x^5 +2x^3 -7x^8 +4x^9
Polynomial 2: -9x^1 +4x^7 +5x^6 -4x^3 -3x^5
Polynomial 3: Empty list
You just need to delete the line L = P; at the end of the function addPolynomial, then it will work.