Memory allocation help

Hello, I am trying to write a simple program where I want to find sum of polynomials. I've found out the my code is somewhere wrong during the sorting step using valgrind but I don't know why? Could anyone help me clear up my realloc basics?

Here's the full code:

Code:

---

#include <stdio.h>#include <stdlib.h>


struct poly
{
    float exp;
    float coeff;
}*arr,*add;
int main(void)
{
    int i,j,c=0,n,m,sum=0,k=0,f=0;
arr=NULL;
    //INPUTTING POLYNOMIALS
    printf("Enter no. of polynomials ");
    scanf("%d", &n);
    for (i=0;i<n;i++)
    {
        printf("Enter no. of terms in polynomial ");
        scanf("%d", &m);
        arr= (struct poly*)realloc(arr, m*sizeof(struct poly));
        for (j=0;j<m;j++)
        {
            printf("Enter coefficient: ");
            scanf("%f", &arr[c].coeff);
            printf("Enter exponent: ");
            scanf("%f", &arr[c].exp);
            c++;
        }
    }
    //PRINTING
    for (i=0;i<c;i++)
    {
        printf("%0.2f x^0.2f +", arr[i].coeff, arr[i].exp);
    }
    //SORTING


    for (i=0;i<c;i++)
        for (j=0;j<c-i-1;j++)
        {
            if (arr[j].exp>arr[j+1].exp)
            {
                n=arr[j].exp;arr[j].exp=arr[j+1].exp=arr[j].exp; arr[j+1].exp=n;
        m=arr[j].coeff; arr[j].coeff=arr[j+1].coeff; arr[j+1].coeff=m;
            }
        }
    //PRINTING
    for (i=0;i<c;i++)
    {
        printf("\n%0.2fx^0.2f +", arr[i].coeff, arr[i].exp);
    }
return 0;
}

---

Your problem is that you are reading all the polynomials into the same array. In the end, you will only have the last polynomial.
You need a struct to actually stand for the polynomial, not just one term.

Code:

---

typedef struct Term {
    int    exp;  // are the exponents integers, perchance?
    double coef; // no reason to use a float unless you're trying to save space
} Term;

typedef struct Poly {
    int nTerms;
    Term *terms;
} Poly;

---

Quote:

---

Originally Posted by algorism

Your problem is that you are reading all the polynomials into the same array. In the end, you will only have the last polynomial.
You need a struct to actually stand for the polynomial, not just one term.

Code:

---

typedef struct Term {
    int    exp;  // are the exponents integers, perchance?
    double coef; // no reason to use a float unless you're trying to save space
} Term;

typedef struct Poly {
    int nTerms;
    Term *terms;
} Poly;

---

---

Thanks for your input but I don't want to create more structures. Basically, I don't need to differentiate the polynomials when I am going to add them. Also when I read the polynomial terms I use a different counter, so it's an array of structs? When I print it for the first time it works actually. Something like this: Attachment 15175

Quote:

---

Originally Posted by Iiz

Thanks for your input but I don't want to create more structures. Basically, I don't need to differentiate the polynomials when I am going to add them. Also when I read the polynomial terms I use a different counter, so it's an array of structs?

---

Oh, I see. (Pretty stupid of me not to notice that.)
In that case, you need to realloc based on c + m, not just m.

EDIT: Now that I've actually tried to run your code there's two problems.
You're missing some % signs in the printf's.
And in your sort, you have this:

Code:

---

arr[j].exp=arr[j+1].exp=arr[j].exp;

---

Some human-readable spacing might have helped you to see that.

Quote:

---

Originally Posted by algorism

Oh, I see. (Pretty stupid of me not to notice that.)
In that case, you need to realloc based on c + m, not just m.

---

Augh, I am so stupid this is my previous code which had the realloc mistake. Could you kindly check this one instead:

Code:

---

#include <stdio.h>#include <stdlib.h>


struct poly
{
    float exp;
    float coeff;
}*arr,*add, temp;
int main(void)
{
    int i,j,c=0,n,m,sum=0,k=0,f=0;
    arr=NULL;
    //INPUTTING POLYNOMIALS
    printf("Enter no. of polynomials ");
    scanf("%d", &n);
    for (i=0;i<n;i++)
    {
        printf("Enter no. of terms in polynomial ");
        scanf("%d", &m);
    f+=m;
        if (arr==NULL)
        arr= (struct poly*)malloc(m*sizeof(struct poly));
        else
        arr= (struct poly*)realloc(arr, f*sizeof(struct poly));
        for (j=0;j<m;j++)
        {
            printf("Enter coefficient: ");
            scanf("%f", &arr[c].coeff);
            printf("Enter exponent: ");
            scanf("%f", &arr[c].exp);
            c++;
        }
    }
    //PRINTING
    for (i=0;i<c;i++)
    {
        printf("%0.2fx^%0.2f +", arr[i].coeff, arr[i].exp);
    }
    //SORTING


    for (i=0;i<c;i++)
        for (j=0;j<c-1;j++)
        {
            if (arr[j].exp>arr[j+1].exp)
            {
        temp=arr[j];
        arr[j]=arr[j+1];
        arr[j+1]=temp;
                /*n=arr[j].exp;
        arr[j].exp=arr[j+1].exp=arr[j].exp;
        arr[j+1].exp=n;
            m=arr[j].coeff;
        arr[j].coeff=arr[j+1].coeff;
        arr[j+1].coeff=m;*/
            }
        }
    //PRINTING
    for (i=0;i<c;i++)
    {
        printf("\n%0.2fx^%0.2f +", arr[i].coeff, arr[i].exp);
    }


//ADDING
    for (i=0;i<c;i++)
    {
    if (arr[i].exp == arr[i+1].exp) sum+=arr[i].coeff;
    else {
    add=(struct poly*)realloc(add,k*sizeof(struct poly));
    add[k].coeff=sum+arr[i].coeff;
    add[k].exp = arr[i].exp;
    k++;
    }
    }


    //PRINTING
    for (i=0;i<k;i++)
    {
        printf("\n%0.2fx^%0.2f +", add[i].coeff, add[i].exp);
    }


return 0;
}

---

As far as I think, my input should be working now. I think I mostly need help with the sorting and adding sections. (I am confused how my sorting works when I use a struct to swap them but stops working when I do it manually using two variables, I've put that part in comment section in the sorting area which didn't work)

Should I update the main post with the corrected code?

ED1 - Thanks again, I read through that horrible sorting re-assigning issue. So now I know why my struct swapping was working and not manual one. Also that code was outdated one, so I fixed my printf % signs as well. So far, inputting and sorting seems ok. (Thanks a lot :P) Now, I just need help with the addition issue. The addition part is in this code.

You need to use (k + 1) when reallocing in your add routine.

You're also accessing beyond the end of arr. Your if needs to include the test that i < c - 1.

And you're not resetting sum to 0 at the end of the else.

BTW, you shouldn't need to typecast the return value of malloc/realloc. If your compiler complains, then you're compiling as C++.

Quote:

---

Originally Posted by algorism

You need to use (k + 1) when reallocing in your add routine.

You're also accessing beyond the end of arr. Your if needs to include the test that i < c - 1.

And you're not resetting sum to 0 at the end of the else.

BTW, you shouldn't need to typecast the return value of malloc/realloc. If your compiler complains, then you're compiling as C++.

---

Ahhh, it's working now. I ran the loop to c-1 and changed the allocation to k+1, I forgot initially k was 0. Not tried to remove the recast thing yet. I can now free the old arr without any problem right?

Is this optimal memory usage or do you have any ideas on how it can be done better? It works now at least. Thanks a lot. :D

ED1 - The last element isn't printing after summation though. Do you think my loop change is the issue?

edited code:

Code:

---

#include <stdio.h>
#include <stdlib.h>


struct poly
{
    float exp;
    float coeff;
}*arr,*add, temp;
int main(void)
{
    int i,j,c=0,n,m,sum=0,k=0,f=0;
    arr=NULL;
    //INPUTTING POLYNOMIALS
    printf("Enter no. of polynomials ");
    scanf("%d", &n);
    for (i=0;i<n;i++)
    {
        printf("Enter no. of terms in polynomial ");
        scanf("%d", &m);
    f+=m;
        if (arr==NULL)
        arr= (struct poly*)malloc(m*sizeof(struct poly));
        else
        arr= (struct poly*)realloc(arr, f*sizeof(struct poly));
        for (j=0;j<m;j++)
        {
            printf("Enter coefficient: ");
            scanf("%f", &arr[c].coeff);
            printf("Enter exponent: ");
            scanf("%f", &arr[c].exp);
            c++;
        }
    }
    //PRINTING
    for (i=0;i<c;i++)
    {
        printf("%0.2fx^%0.2f +", arr[i].coeff, arr[i].exp);
    }
    //SORTING


    for (i=0;i<c;i++)
        for (j=0;j<c-1;j++)
        {
            if (arr[j].exp>arr[j+1].exp)
            {
        temp=arr[j];
        arr[j]=arr[j+1];
        arr[j+1]=temp;
                /*n=arr[j].exp;
        arr[j].exp=arr[j+1].exp;
        arr[j+1].exp=n;
            m=arr[j].coeff;
        arr[j].coeff=arr[j+1].coeff;
        arr[j+1].coeff=m;*/
            }
        }
    //PRINTING
    for (i=0;i<c;i++)
    {
        printf("\n%0.2fx^%0.2f +", arr[i].coeff, arr[i].exp);
    }


//ADDING
    for (i=0;i<c-1;i++)
    {
    if (arr[i].exp == arr[i+1].exp) sum+=arr[i].coeff;
    else {
    add=(struct poly*)realloc(add,(k+1)*sizeof(struct poly));
    add[k].coeff=sum+arr[i].coeff;
    add[k].exp = arr[i].exp;
    k++;
    sum=0;
    }
    }


    //PRINTING
    printf("\nSUMMATION:");
    for (i=0;i<k;i++)
    {
        printf("\n%0.2fx^%0.2f +", add[i].coeff, add[i].exp);
    }


return 0;
}

---

I didn't mean for you to only loop up to < c - 1. You need to loop up to < c or you won't get the last element. Instead, change your if condition to:

Code:

---

if (c < c - 1 && arr[i].exp == arr[i+1].exp)

---

Yes you can free arr.

I wouldn't worry about optimal memory usage. Clearly this isn't "optimal" since it would obviously be possible to do it all within the original array. But does it really matter?

BTW, we wouldn't normally make arr, add, and temp global.
And breaking it into functions would be a good idea.

Quote:

---

Originally Posted by algorism

I didn't mean for you to only loop up to < c - 1. You need to loop up to < c or you won't get the last element. Instead, change your if condition to:

Code:

---

if (c < c - 1 && arr[i].exp == arr[i+1].exp)

---

Yes you can free arr.

I wouldn't worry about optimal memory usage. Clearly this isn't "optimal" since it would obviously be possible to do it all within the original array. But does it really matter?

BTW, we wouldn't normally make arr, add, and temp global.
And breaking it into functions would be a good idea.

---

Do you mean i<c-1 ? I don't get this part at all. c<c-1 doesn't help, neither dose changing it to i<c-1. Why isn't it actually printing the last element?

Quote:

---

Originally Posted by Iiz

Do you mean i<c-1 ? I don't get this part at all. c<c-1 doesn't help, neither dose changing it to i<c-1. Why isn't it actually printing the last element?

---

Oops! Yes, of course it's i < c - 1. And it should work. You'll have to post your code if it doesn't. Did you also change the loop limit back to i < c ???

Quote:

---

Originally Posted by algorism

Oops! Yes, of course it's i < c - 1. And it should work. You'll have to post your code if it doesn't. Did you also change the loop limit back to i < c ???

---

Now for sure, I can say it's working. Whew, so why was it not working before and skipping the last term? i<c-1 means that second last element right? What was I not taking into account?

Quote:

---

Originally Posted by Iiz

Now for sure, I can say it's working. Whew, so why was it not working before and skipping the last term? i<c-1 means that second last element right? What was I not taking into account?

---

I haven't seen every iteration of your code so I couldn't tell you.
But it should look something like this:

Code:

---

    struct poly *add = NULL;
    int k = 0, sum = 0;
    for (int i = 0; i < c; i++)
    {
        if (i < c - 1 && arr[i].exp == arr[i+1].exp)
            sum += arr[i].coeff;
        else {
            add = realloc(add, (k+1) * sizeof(struct poly));
            add[k].coeff = sum + arr[i].coeff;
            add[k].exp = arr[i].exp;
            k++;
            sum = 0;
        }
    }

---

Like I said, it would be good to break it up into functions. E.g.,

Code:

---

void print_poly(struct poly *arr, int n) {
    for (int i = 0; i < n; i++) {
        if (i > 0) printf(" + ");
        printf("%0.2fx^%0.2f", arr[i].coeff, arr[i].exp);
    }
    printf("\n\n");
}

---

I think I somehow get it, I'll look over it. For now, it's working. I have not freed the memory arr takes but I don't think it'll cause any problem. Thanks, is there any way to mark it solved in here?

Please use functions. They make life easier. Your code at the moment does not handle malloc or realloc failing (i.e. returning NULL) and to restructure it in it's current form so that it does will just make it ugly.