still problem with polynom linked list

if13121 · #1 22-Nov-2004, 03:16

I make polynom using linked list
i got problem when i want to add two polynom(in AddListPol function) and return ist result in a new polynom. i use a temporary variabel that will be inseted as new polynom element but for the next element i still got the first element address. whats wrong?

the program:

CPP / C++ / C Code:

typedef int infotype;
typedef struct tSuku * address;

typedef struct tSuku
{
	infotype Degree;
	infotype Coefficient;
	address Next;
}Suku;
typedef struct
{
	address First;
}Polinom;

void InitListPol(Polinom *P)
/*is any
fs empty polinom created */
{
	(P)->First = NULL;
}
void AllocSuku(address *Pnew,int Deg,int Coef)
{
	*Pnew = (address)malloc(sizeof(Suku));
	if(*Pnew!= NULL)/*ALokasi berhasil*/
	{
		(*Pnew)->Degree=Deg;
		(*Pnew)->Coefficient=Coef;
	}

}
void CreatePol(Polinom  *P1)

{	int Deg,Coef,found;
	address Pnew,Pt,PrecPt;
	InitListPol(P1);
	printf("Input polinom ended it with -999\n");
	while(Deg != -999){
	printf("Input Polinom degree \n");
	scanf("%d",&Deg);
	if (Deg!=-999){
	printf("Input polinom coefficient\n");
	scanf("%d",&Coef);
	Pt = P1->First;//P1->First=Pt;
	PrecPt = NULL;
	found=0;
	AllocSuku(&Pnew,Deg,Coef);
		//search place
		while(Pt != NULL && found ==0){
		  	if (Deg >= Pt->Degree){
		  		found = 1;
		  }
			else{
		 		PrecPt=Pt;
		 		Pt=Pt->Next;
		 	 }
		}//insert
		if (Pt!=NULL){
		  	if (Deg != Pt->Degree){
		   		if(PrecPt == NULL){
		   			Pnew->Next=Pt;//insert first
		       			P1->First=Pnew;
		       		}
		    		else {
		    			Pnew->Next = Pt;//insert after PrecPt
		    	  		PrecPt->Next = Pnew;
		         	}
		  	}
		  	else  {//if same degree then replace
		  		PrecPt->Next=Pnew;
		    	  	Pnew->Next=Pt->Next;
		    	  	Pt=Pnew;
		  	}
	         }
	         else{	if (P1->First==NULL){//empty
	         			P1->First=Pnew;
	         	  		Pnew->Next=Pt;
	   	    	   }
	    	   	else{   Pnew->Next = Pt;//insert after PrecPt
		    	 	 PrecPt->Next = Pnew;
	         	}
	         }

	 }
    }
}


void TulisListPol(Polinom P)
/*Print Polynom to screen*/
{
	address Pt;
	Pt = P.First;
	if (Pt == NULL)
		printf("empty polynom\n");
	else{	printf("----------------------\n");
		printf("|Degree  |Coefficient|\n");
		printf("----------------------\n");
		do{
		printf("| %5d  |   %5d   |\n",Pt->Degree,Pt->Coefficient);
			Pt = Pt->Next;
		}
		while(Pt!=NULL);
		printf("----------------------\n");
	}
	printf("\n");
}
void InsertLast(address Pnew,Polinom * L,address Last)
/*is :
  fs : */
{	if(Last==NULL){
		L->First=Pnew;
		Last=L->First;
	}
	else{
		Last->Next=Pnew;
	}
}

void AddListPol(Polinom P1, Polinom P2, Polinom * P3)
/*is   : P1 ,P2 defined and may be empty
  fs   :
*/
{
	address Pt1,Pt2,Ptemp;
	address Last;
	int Sum;
	InitListPol(P3);
	Last=P3->First;
	Pt1=P1.First; 	Pt2=P2.First;
	while(Pt1 != NULL && Pt2 != NULL){
		if (Pt1->Degree==Pt2->Degree)
		{
			Sum = Pt1->Coefficient + Pt1->Coefficient;
			printf("sum=%d\n",Sum);
			if (Sum != 0){
				AllocSuku(&Ptemp,Pt1->Degree,Sum);
				printf("degree el P3 = %d\n",Ptemp->Degree);
				InsertLast(Ptemp,P3,Last);
				Pt1=Pt1->Next; Pt2=Pt2->Next;
				free(Ptemp);
			}
		}
		else{	if(Pt1->Degree> Pt2->Degree){
			printf("P1\n");
				InsertLast(Pt1,P3,Last);
				Pt1=Pt1->Next;
			}
			else{printf("P2\n");
				InsertLast(Pt2,P3,Last);
				Pt2=Pt2->Next;
			}
		}
	}
	while (Pt1 != NULL){printf("remainPt1\n");
		InsertLast(Pt1,P3,Last);
	 	Pt1=Pt1->Next;
	}
	while (Pt2 != NULL){printf("remain Pt2\n");
		InsertLast(Pt2,P3,Last);
		Pt2=Pt2->Next; 
	}
}

thank you

davekw7x · #2 22-Nov-2004, 07:23

Quote:

Originally Posted by if13121

I make polynom using linked list
i got problem when i want to add two polynom(in AddListPol function) and return ist result in a new polynom. i use a temporary variabel that will be inseted as new polynom element but for the next element i still got the first element address. whats wrong?

t
[/c]
thank you

I can't speak for others on this forum, but as for me:

You have posted over 160 lines of code and you asked what's wrong.

Now without at least compiling and running your code with a test case, I don't think it's likely that I will spot what's wrong.

Give us a main(), explain what the program input is and what the expected output is and what you got when you ran the program. Someone here may have enough time and interest to look into it.

Regards,

Dave

if13121 · #3 22-Nov-2004, 17:52

Quote:

Originally Posted by davekw7x

I can't speak for others on this forum, but as for me:

You have posted over 160 lines of code and you asked what's wrong.

Now without at least compiling and running your code with a test case, I don't think it's likely that I will spot what's wrong.

Give us a main(), explain what the program input is and what the expected output is and what you got when you ran the program. Someone here may have enough time and interest to look into it.

Regards,

Dave

CPP / C++ / C Code:

main :
#include "Polinomlist.h"
int main()
{	int option;
	Polinom P1,P2,P3;
	do{	
		printf("============MENU============\n");
		printf("* [1] Create Polynom       *\n");
		printf("* [2] Print Polynom        *\n");
		printf("* [3] Add Polynom          *\n");
		printf("* [0] Exit                 *\n");
		printf("============================\n");
		printf("Enter number:\n");
		scanf("%d",&option); 
		switch(option){
			case 1: CreatePol(&P1);
				break;
			case 2: TulisListPol(P1);
				break;
			case 3: printf("Create First Polinom\n");
				CreatePol(&P1);
				printf("Create Second Polinom\n");
				CreatePol(&P2);
				AddListPol(P1,P2,&P3);
				printf("First Polynom=\n");
				TulisListPol(P1);
				printf("Second Polynom=\n");
				TulisListPol(P2);
				printf("First Polynom + Second Polynom=\n");
				TulisListPol(P3);
				break;
			case 0: printf("Bye..\n");
				break;	
			default : printf("Unknown option number\n");				
		}
	}
   	while(option!=0);
	return 0;
	
}

header file

CPP / C++ / C Code:

#ifndef Polinomlist_H
#define Polinomlist_H
#include <stdlib.h>
#include <stdio.h>

typedef int infotype;
typedef struct tSuku * address;

typedef struct tSuku
{
	infotype Degree;
	infotype Coefficient;
	address Next;
}Suku;
typedef struct
{
	address First;
}Polinom;

void CreatePol(Polinom  *P1);
void TulisListPol(Polinom P);
void InitListPol(Polinom *P);
void AllocSuku(address * Pnew,infotype Deg,infotype Coef);
void AddListPol(Polinom P1, Polinom P2, Polinom * P3);
void InsertLast(address Pnew,Polinom * L,address Last);
#endif

body function file:

CPP / C++ / C Code:

   #include "Polinomlist.h"
void InitListPol(Polinom *P)
/*is any 
fs empty polinom created */
{
	(P)->First = NULL;
}
void AllocSuku(address *Pnew,int Deg,int Coef)
{
	*Pnew = (address)malloc(sizeof(Suku));
	if(*Pnew!= NULL)/*ALokasi berhasil*/
	{	
		(*Pnew)->Degree=Deg;
		(*Pnew)->Coefficient=Coef;
	}
	
}
void CreatePol(Polinom  *P1)
{	int Deg,Coef,found;
	address Pnew,Pt,PrecPt;
	InitListPol(P1);
	printf("Input polinom ended it with -999\n");
	while(Deg != -999){
	printf("Input Polinom degree \n");
	scanf("%d",&Deg);
	if (Deg!=-999){
	printf("Input polinom coefficient\n");
	scanf("%d",&Coef);
	Pt = P1->First;   
            //P1->First=Pt; note XXX 
	PrecPt = NULL; 
	found=0; 
	AllocSuku(&Pnew,Deg,Coef);
		//search place
		while(Pt != NULL && found ==0){
		  	if (Deg >= Pt->Degree){
		  		found = 1;
		  }
			else{
		 		PrecPt=Pt; 
		 		Pt=Pt->Next;
		 	 }
		}//insert
		if (Pt!=NULL){
		  	if (Deg != Pt->Degree){
		   		if(PrecPt == NULL){
		   			Pnew->Next=Pt;//insert first
		       			P1->First=Pnew;/* why if I delete this line and use note XXX above this function will not work :?: */                                                                
		       		}
		    		else {
		    			Pnew->Next = Pt;//insert after PrecPt
		    	  		PrecPt->Next = Pnew;
		         	}
		  	}
		  	else  {//if same degree then replace
		  		PrecPt->Next=Pnew; 		  		
		    	  	Pnew->Next=Pt->Next; 
		    	  	Pt=Pnew;
		  	}
	         }
	         else{	if (P1->First==NULL){//empty
	         			P1->First=Pnew;
	         	  		Pnew->Next=Pt;
	   	    	   }
	    	   	else{   Pnew->Next = Pt;//insert after PrecPt
		    	 	 PrecPt->Next = Pnew;
	         	}
	         }
	         
	 }
    }
}


void TulisListPol(Polinom P)
{
	address Pt;
	Pt = P.First;
	if (Pt == NULL)
		printf("empty polynom\n");
	else{	printf("----------------------\n");
		printf("|Degree  |Coefficient|\n");
		printf("----------------------\n");
		do{
		printf("| %5d  |   %5d   |\n",Pt->Degree,Pt->Coefficient);
			Pt = Pt->Next;
		}
		while(Pt!=NULL);
		printf("----------------------\n");
	}
	printf("\n");
}
void InsertLast(address Pnew,Polinom * L,address Last)

{	if(Last==NULL){
		L->First=Pnew;
		Last=L->First;
	} 
	else{ 	
		Last->Next=Pnew;
	}
}
void AddListPol(Polinom P1, Polinom P2, Polinom * P3)
{
	address Pt1,Pt2,Ptemp;
	address Last;
	int Sum;
	InitListPol(P3);
	Last=P3->First;
	Pt1=P1.First; 	Pt2=P2.First;
	while(Pt1 != NULL && Pt2 != NULL){
		if (Pt1->Degree==Pt2->Degree)
		{
			Sum = Pt1->Coefficient + Pt1->Coefficient;
			printf("sum=%d\n",Sum);
			if (Sum != 0){
				AllocSuku(&Ptemp,Pt1->Degree,Sum);
				printf("degree el P3 = %d\n",Ptemp->Degree);
				InsertLast(Ptemp,P3,Last);
				Pt1=Pt1->Next; Pt2=Pt2->Next; 
				free(Ptemp); //is this Ok??
			}
		}
		else{	if(Pt1->Degree> Pt2->Degree){
			printf("P1\n");
				InsertLast(Pt1,P3,Last);
				Pt1=Pt1->Next;
			}
			else{printf("P2\n");	
				InsertLast(Pt2,P3,Last);
				Pt2=Pt2->Next; 
			}
		}
	}
	while (Pt1 != NULL){printf("remainPt1\n");
		InsertLast(Pt1,P3,Last);
	 	Pt1=Pt1->Next;
	}
	while (Pt2 != NULL){printf("remain Pt2\n");
		InsertLast(Pt2,P3,Last);
		Pt2=Pt2->Next; 
	}		
}

thank you......

davekw7x · #4 22-Nov-2004, 18:12

Quote:

Originally Posted by davekw7x

Give us a main(), explain what the program input is and what the expected output is and what you got when you ran the program.

Regards,

Dave

OK for the main(), now tell us what you did, what you got, and what you expected to get (What is this supposed to do? What input did you give it, etc.)

Regards,

Dave

davekw7x · #5 22-Nov-2004, 18:46

Quote:

Originally Posted by if13121

[/c]
thank you......

Well, don't thank me for fixing your program. I don't mind looking at it for a while, but the debug is going to be up to you. I tried the following:

Select menu item 1

Enter Degree 3

It asked for a coefficient,

I Entered 1

It asked for the degree of another polynomial.

(Why not ask for the other coefficients? Is there a bug here?)

Wel I entered degree 3 again and coefficient 1 again and it crashed.

SO:

Put some printf() statements at places where you expect the program to go when you enter polynomials.

I think your mechanism for allocating structures is unnecassarily baroque: passing a pointer to a pointer (subtly disguised by a typedef in the header file, etc.) Just allocate the storage and return the pointer that malloc gave you. (Or something.)

Why did it crash? Almost certainly because you were trying to write to a place pointed to by a pointer whose value was NULL or some illegal value.

For example

CPP / C++ / C Code:

        else {
            Pnew->Next = Pt;//insert after PrecPt
            PrecPt->Next = Pnew;
          }
        }
        else  {//if same degree then replace
          printf("Pnew = %p, PrecPt = %p\n");/* <=== Note printf() for debug */
          PrecPt->Next=Pnew;           
          Pnew->Next=Pt->Next; 
          Pt=Pnew;

I think this is where it crashed. Note that I put a printf statement just before the assignment. You should sprinkle printf() all over the landscape until you get to the bottom of it.

Regards,
Dave

if13121 · #6 22-Nov-2004, 21:12

Quote:

Originally Posted by davekw7x

Well, don't thank me for fixing your program. I don't mind looking at it for a while, but the debug is going to be up to you. I tried the following:

Select menu item 1

Enter Degree 3

It asked for a coefficient,

I Entered 1

It asked for the degree of another polynomial.

(Why not ask for the other coefficients? Is there a bug here?)

Wel I entered degree 3 again and coefficient 1 again and it crashed.

SO:

Put some printf() statements at places where you expect the program to go when you enter polynomials.

I think your mechanism for allocating structures is unnecassarily baroque: passing a pointer to a pointer (subtly disguised by a typedef in the header file, etc.) Just allocate the storage and return the pointer that malloc gave you. (Or something.)

Why did it crash? Almost certainly because you were trying to write to a place pointed to by a pointer whose value was NULL or some illegal value.

For example

CPP / C++ / C Code:

        else {
            Pnew->Next = Pt;//insert after PrecPt
            PrecPt->Next = Pnew;
          }
        }
        else  {//if same degree then replace
          printf("Pnew = %p, PrecPt = %p\n");/* <=== Note printf() for debug */
          PrecPt->Next=Pnew;           
          Pnew->Next=Pt->Next; 
          Pt=Pnew;

I think this is where it crashed. Note that I put a printf statement just before the assignment. You should sprinkle printf() all over the landscape until you get to the bottom of it.

Regards,
Dave

sorry , i don't really understand what you mean in:
"I think your mechanism for allocating structures is unnecassarily baroque: passing a pointer to a pointer (subtly disguised by a typedef in the header file, etc.) Just allocate the storage and return the pointer that malloc gave you. (Or something.)"

sorry again, the instruction in my program was not clear
you should end input polynom by enter -999 when it asked for degree.
Yes there is a bugs if you enter the same degree with last degree you enter the program will crashed and i still don't know why.
I forget to asked about this.

this is some output i got when running the program:
if13121@leuser-15 krisantus]$ ./main
============MENU============
* [1] Create Polynom *
* [2] Print Polynom *
* [3] Add Polynom *
* [4] Substract Polynom *
* [5] Derive Polynom *
* [0] Exit *
============================
Enter number:
1
Input polinom ended it with -999
Input Polinom degree
3
Input polinom coefficient
1
Input Polinom degree
3
Input polinom coefficient
1
Segmentation fault
[if13121@leuser-15 krisantus]$ ./main
============MENU============
* [1] Create Polynom *
* [2] Print Polynom *
* [3] Add Polynom *
* [4] Substract Polynom *
* [5] Derive Polynom *
* [0] Exit *
============================
Enter number:
1
Input polinom ended it with -999
Input Polinom degree
3
Input polinom coefficient
2
Input Polinom degree
1
Input polinom coefficient
4
Input Polinom degree
-999
============MENU============
* [1] Create Polynom *
* [2] Print Polynom *
* [3] Add Polynom *
* [4] Substract Polynom *
* [5] Derive Polynom *
* [0] Exit *
============================
Enter number:
2
----------------------
|Degree |Coefficient|
----------------------
| 3 | 2 |
| 1 | 4 |
----------------------

============MENU============
* [1] Create Polynom *
* [2] Print Polynom *
* [3] Add Polynom *
* [4] Substract Polynom *
* [5] Derive Polynom *
* [0] Exit *
============================
Enter number:
3
Create First Polinom
Input polinom ended it with -999
Input Polinom degree
1
Input polinom coefficient
2
Input Polinom degree
3
Input polinom coefficient
4
Input Polinom degree
5
Input polinom coefficient
6
Input Polinom degree
-999
Create Second Polinom
Input polinom ended it with -999
Input Polinom degree
1
Input polinom coefficient
2
Input Polinom degree
3
Input polinom coefficient
4
Input Polinom degree
-999
P1
sum=8
degree el P3 = 3
sum=4
degree el P3 = 1
First Polynom=
----------------------
|Degree |Coefficient|
----------------------
| 5 | 6 |
| 3 | 4 |
| 1 | 2 |
----------------------

Second Polynom=
----------------------
|Degree |Coefficient|
----------------------
| 3 | 4 |
| 1 | 2 |
----------------------

First Polynom + Second Polynom=
----------------------
|Degree |Coefficient|
----------------------
| 0 | 4 |
----------------------

============MENU============
* [1] Create Polynom *
* [2] Print Polynom *
* [3] Add Polynom *
* [4] Substract Polynom *
* [5] Derive Polynom *
* [0] Exit *
============================
Enter number:
0
Bye..

davekw7x · #7 22-Nov-2004, 21:37

Quote:

Originally Posted by if13121

sorry , i don't really understand what you mean in:
"I think your mechanism for allocating structures is unnecassarily baroque: passing a pointer to a pointer (subtly disguised by a typedef in the header file, etc.) Just allocate the storage and return the pointer that malloc gave you. (Or something.)"

sorry again, the instruction in my program was not clear
you should end input polynom by enter -999 when it asked for degree.
Yes there is a bugs if you enter the same degree with last degree you enter the program will crashed and i still don't know why.
I forget to asked about this.

I shouldn't have made general criticism without saying something more helpful. If you are happy with your allocation scheme and it seems to work for you, then don't try to change it.

I think you should break the problem down into smaller steps:

When you want to create a polynomial of, say degree 3, what does the program expect?

I can't tell what's happening; you have to make sure it's doing what you intended.

If I were writing a program and the user indicated that he wanted to create a polynomial of degree 3, I would expect the program to ask for the coefficients.
How many? probably 3 (maybe 4, depending on how the polynomial is represented). Does your program flow indicate that this is happening?

If not, then ---stop--- make sure you can construct the polynomial. If this is happening ok for you. then see if you can print out the coefficients.

I would build the program from this point of view: make sure each step is perfect (as much as you can test it), then go on to the next.

I haven't spent enough time on it to see what the heck you are doing in the creation process. You can put printf() statements at each step to see if it is going where you want it to.

Regards,

Dave

davekw7x · #8 22-Nov-2004, 23:02

Quote:

Originally Posted by davekw7x

I can't tell what's happening; you have to make sure it's doing what you intended.

I haven't spent enough time on it to see what the heck you are doing in the creation process. You can put printf() statements at each step to see if it is going where you want it to.

Regards,

Dave

Well, I think I see how you are building the polynomials with CreatePol().

I can see how, if everything is entered correctly the polynomials can be printed out.

One thing I see about the process of creating the sum is as follows:

Look in your InsertLast:

CPP / C++ / C Code:

void InsertLast(address Pnew,Polinom * L,address Last)
{
  if(Last==NULL) {
    L->First=Pnew;
    Last=L->First;
  } 
  else {   
    Last->Next=Pnew;
  }
}

Now, I think you want to change Last each time, but that doesn't change the value of Last in the program that calls InsertLast()

Verify this by adding a printf():

CPP / C++ / C Code:

        printf("degree el P3 = %d\n",Ptemp->Degree);
        printf("Before InsertLast: Ptemp = %p, P3= %p, Last = %p\n",
                  Ptemp, P3, Last);
        InsertLast(Ptemp, P3, Last);
        printf("After InsertLast: Ptemp = %p, P3= %p, Last = %p\n",
                  Ptemp, P3, Last);

Perhaps you may want to change InsertLast to something like this

CPP / C++ / C Code:

void InsertLast(address Pnew, Polinom *L, address *Last)

Now, look at this:

CPP / C++ / C Code:

 free(Ptemp); //is this OK?

Ptemp is the memory that you have allocated to hold the term that you just built. Why would you free it here? Not until you are finished with it.

Note: this is important... You Must go back through all of your polynomials and free all memory that was allocated before you exit the program. Otherwise there is a potential memory leak that will eventually bring your computer to its knees. (You may have to reboot to get the memory back.)

Regards,

Dave

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Rate This Thread
Rate This Thread:

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
linked list problem	if13121	C Programming Language	10	11-Nov-2004 12:34
Problem with the function creating updating a linked list	nkhambal	C Programming Language	3	28-Oct-2004 20:45
Insert problem in Linked list	Kay Chan	C Programming Language	1	03-Sep-2004 17:06
Insert problem in linked list with two function code	Kay Chan	C++ Forum	1	03-Sep-2004 09:52
help on linked lists any1?????	nick4	C Programming Language	1	17-May-2004 09:32