Thread: memory issue

  1. #1
    Registered User
    Join Date
    Sep 2008
    Posts
    43

    Exclamation memory issue

    i have posted this before. please see this

    i am almost 100% positive that it is a memory problem in my program. the program is supposed to turn a sting of numbers in to a linked list. each node in the list is a digit of the number and the number is stored backward.

    the program needs to add or subtract the 2 number that were read (1 is add 2 is subtract) then print the answer.

    the file format:
    first line has an int threat tells the number of lines after it.
    first number in the line is read in to indicate add or subtract
    second number is read as a string then converted to a linked list
    third number is read as a sting then converted to a linked list

    looks like this:
    3
    2 7987892049 485928347598
    1 829347598 48398
    1 27309857023987 2093857023947

    there is a little more information on the other page as well as the test file i am really using.

    i really need help i have had a lot of plp look at this but no one seems to know why it doesn't work. also no one has really looked at it or had the proper tools to rally debug it. i don't have enough knowledge to us the tools to debug it.

    anyway here is the code. (571 lines sorry but i don't know where the problem is for sure.)
    Code:
    //John Torres
    //COP 3223-0002
    //Assignment #3
    //Febuary, 20, 2009
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    struct integer* read_integer(char* stringInt);
    struct integer* read_integerRec(char* stringInt, int len);
    void print(struct integer *p);
    void printRec(struct integer *p, int list_len);
    struct integer* add(struct integer *p, struct integer *q);
    struct integer* addRec(struct integer *p, struct integer *q, int carry);
    struct integer* subtract(struct integer *p, struct integer *q);
    struct integer* subtractRec(struct integer *p, struct integer *q, int barrow);
    int compare(struct integer *p, struct integer *q);
    int compareRec(struct integer* p, struct integer* q, int len);
    void FreeList(struct integer *p);
    struct integer* ResizeList(struct integer *p);
    struct integer* ResizeListRec(struct integer *p, int len);
    int ListSize(struct integer *p);
    
    struct integer{
    	int digit;
    	struct integer *next;
    };
    
    int main(void)
    {
        struct integer* head[3];
        char number[201];
        int file_len;
        int test1;
        int test2;
        int i,j;
        
        FILE *fin;
        
        //open file and get number of file lines
        fin = fopen("bigint.txt", "r");
        fscanf(fin, "%d", &file_len);
    
        //loop breaks after file is done
        for(i = 0; i < file_len; i++)
        {
            //read operation type, 1=add, 2=sub
            fscanf(fin,"%d", &test1);
            
            //reads the 2 strings and converts them to numbers
            for(j = 0; j < 2; j++)
            {
                fscanf(fin, "%s", number);
                head[j] = read_integer(number);
            }
            //if add
            if(test1 == 1)
            {
                //add function
                head[2] = add(head[0], head[1]);
                //resize
                head[2] = ResizeList(head[2]);
                
                //print operation
                print(head[0]);
                printf("\n+\n");
                print(head[1]);
                printf("\n=\n");
                print(head[2]);
                printf("\n\n");
            }
            //if subtract
            else if(test1 == 2)
            {
                //subtract function
                head[2] = subtract(head[0], head[1]);
                //resize answer
                head[2] = ResizeList(head[2]);
                //check order
                test2 = compare(head[0], head[1]);
                
                //print operation
                if(test2 == -1)
                {//if second is larger
                    print(head[1]);
                    printf("\n-\n");
                    print(head[0]);
                    printf("\n=\n");
                    print(head[2]);
                    printf("\n");
                }
                else
                {//if same or first is larger
                    print(head[0]);
                    printf("\n-\n");
                    print(head[1]);
                    printf("\n=\n");
                    print(head[2]);
                    printf("\n");
                }
            }
            //if first number was not a 1 (add) or a 2 (sub)
            else
            {
                printf("BAD DATA");
            }
            
            system("pause");
            //free lists
            FreeList(head[0]);
            FreeList(head[1]);
            FreeList(head[2]);
        }
        
        return 0;
    }
    
    ////////////////////////////////////////////////////////////////////////////////
    //Preconditions:    the first parameter is string that stores
    //                  only contains digits, doesn't start with
    //                  0, and is 50 or fewer characters long.
    //
    //Postconditions:   The function will read the digits of the
    //	                large integer character by character, 
    //	                convert them into integers and place them in 
    //	                nodes of a linked list. The pointer to the 
    //	                head of the list is returned.
    //
    //Discription:      
    ////////////////////////////////////////////////////////////////////////////////
    struct integer* read_integer(char* stringInt)
    {
        struct integer* temp;
        int len;
        //find number of digits
        len = strlen(stringInt) - 1;
        //build struct
        return read_integerRec(stringInt, len);
    }
    struct integer* read_integerRec(char* stringInt, int len)
    {
        struct integer* temp;
        //allocate memory
        temp = (struct integer*) malloc(sizeof(struct integer));
        
        //end case
        if(len == 0)
        {
            temp->digit = (int) stringInt[0] - '0';
            temp->next = NULL;
            return temp;
        }
        //base case
        else
        {
            temp->digit = (int) stringInt[len] - '0';
            temp->next = read_integerRec(stringInt, len-1);
            return temp;
        }
    }
    
    ////////////////////////////////////////////////////////////////////////////////
    //Preconditions:    p is a pointer to a big integer, stored in
    //                  reverse order, least to most significant 
    //                  digit, with no leading zeros.
    //
    //Postconditions:   The big integer pointed to by p is 
    //                  printed out.
    //
    //Discription:      
    ////////////////////////////////////////////////////////////////////////////////
    void print(struct integer *p)
    {
        int list_len;
        //find list lenth
        list_len = ListSize(p);
        //print function
        printRec(p, list_len);
    }
    void printRec(struct integer *p, int list_len)
    {
        struct integer* temp;
        int i;
        
        //end case
        if(list_len == 0)
        {
            printf("%d", p->digit);
        }
        //base case
        else
        {
            temp = p;
            
            //move pointer to end of list
            for(i = 0; i < list_len; i++)
            {
                temp = temp->next;
            }
            //print last number in list (first digit in number)
            printf("%d", temp->digit);
            
            //do it again
            printRec(p, list_len-1);
        }
    }
    
    ////////////////////////////////////////////////////////////////////////////////
    //Preconditions:    p and q are pointers to big integers, 
    //                  stored in reverse order, least to most 
    //                  significant digit, with no leading zeros.
    //
    //Postconditions:   A new big integer is created that stores
    //                  the sum of the integers pointed to by p
    //                  and q and a pointer to it is returned.
    //
    //Discription:      
    ////////////////////////////////////////////////////////////////////////////////
    struct integer* add(struct integer *p, struct integer *q)
    {
        return addRec(p, q, 0);
    }
    struct integer* addRec(struct integer *p, struct integer *q, int carry)
    {
        struct integer* big_number;
    
        //allocate memory
        big_number = (struct integer*) malloc(sizeof(struct integer));
    
        //if nothing left to add
        if(q->next == NULL && p->next == NULL)
        {
            big_number->digit = p->digit + q->digit + carry;
            big_number->next = NULL;
            return big_number;
        }
        //if q is has no more numbers
        else if(q->next == NULL)
        {
            big_number->digit = q->digit+ p->digit + carry;
            big_number->next = p->next;
            return big_number;
        }
        //if p has no more numbers
        else if(p->next == NULL)
        {
            big_number->digit = p->digit + q->digit + carry;
            big_number->next = q->next;
            return big_number;
        }
        //base case
        else
        {
            //add
            big_number->digit = p->digit + q->digit + carry;
            
            //...carry the one...
            if(big_number->digit > 9)
            {
                big_number->digit -= 10;
                carry =1;
            }
            //reset carry
            else
            {
                carry = 0;
            }
            
            //do it again
            big_number->next = addRec(p->next, q->next, carry);
            
            return big_number;
        }
    }
    
    ////////////////////////////////////////////////////////////////////////////////
    //Preconditions:    p and q are pointers to big integers, 
    //                  stored in reverse order, least to most 
    //                  significant digit, with no leading zeros.
    //
    //Postconditions:   A new big integer is created that stores
    //                  the absolute value of the difference 
    //                  between the two and a pointer to this is
    //                  returned.
    //
    //Discription:      
    ////////////////////////////////////////////////////////////////////////////////
    struct integer* subtract(struct integer *p, struct integer *q)
    {
        struct integer* big_number;
        int test;
        
        //compare list to find grater number
        test = compare(p, q);
    
        
        
        //if first is grater
        if(test == 1)
        {
            big_number = subtractRec(p, q, 0);
        }
        //if second is grater
        else if(test == -1)
        {
            big_number = subtractRec(q, p, 0);
        }
        //if both are same
        else
        {
            //allocate memory
            big_number = (struct integer*) malloc(sizeof(struct integer));
            big_number->digit = 0;
            big_number->next = NULL;
        }
        
        return big_number;
    }
    struct integer* subtractRec(struct integer *p, struct integer *q, int barrow)
    {
        struct integer* big_number;
        
        //allocate memory
        big_number = (struct integer*) malloc(sizeof(struct integer));
        
        //if q has no more numbers after this one
        //and p is more then q + barrow
        //end case
        if(q->next == NULL && p->digit >= (q->digit + barrow))
        {
            big_number->digit = p->digit - q->digit - barrow;
            big_number->next = p->next;
            barrow = 0;
            return big_number;
        }
        //if q and p have no more numbers after this one
        //end case
        else if(q->next == NULL && p->next == NULL)
        {
            big_number->digit = p->digit - q->digit - barrow;
            big_number->next = NULL;
            barrow = 0;
            return big_number;
        }
        //if q has no more numbers after this one
        //and q + barrow is more then p
        //end case
        else if(q->next == NULL)
        {
            big_number->digit = p->digit - q->digit - barrow + 10;
            big_number->next->digit = p->next->digit - 1;
            big_number->next->next = p->next->next;
            barrow = 0;
            return big_number;
        }   
        //base case, p > q + barrow (dont need to barrow from next number)
        else if(p->digit >= (q->digit + barrow))
        {
            big_number->digit = p->digit - q->digit - barrow;
            big_number->next = subtractRec(p->next, q->next, 0);
            return big_number;
        }
        //base case, p < q + barrow (need to barrow from next number)
        else
        {
            big_number->digit = p->digit - q->digit - barrow + 10;
            big_number->next = subtractRec(p->next, q->next, 1);
            return big_number;
        }
    }
    
    ////////////////////////////////////////////////////////////////////////////////
    //Preconditions:    Both parameters of the function are 
    //	                pointers to struct integer. 
    //
    //Postconditions:   The function compares the digits of two 
    //	                numbers recursively and returns: 
    //                      -1 if the first number is smaller than the second, 
    //                      0 if the first number is equal to the second number,
    //                      1 if the first number is greater than the second.
    //
    //Discription:      
    ////////////////////////////////////////////////////////////////////////////////
    int compare(struct integer *p, struct integer *q)
    {
        int p_len;
        int q_len;
        
        //finds number of digits in numbers
        p_len = ListSize(p);
        q_len = ListSize(q);
        
        //compares lenths
        if(p_len > q_len)
        {//p is longer
            return 1;
        }
        else if(p_len < q_len)
        {//q is longer
            return -1;
        }
        else
        {//need more info
            return compareRec(p, q, p_len);
        }
    }
    int compareRec(struct integer* p, struct integer* q, int len)
    {
        struct integer* temp_p;
        struct integer* temp_q;
        int i;
        
        //assing temp pointers
        temp_p = p;
        temp_q = q;
    
        //end case
        if(len <= 1)
        {
            //if p<q
            if(p->digit < q->digit)
            {
                return -1;
            }
            //if p>q
            else if(p->digit > q->digit)
            {
                return 1;
            }
            //if p=q
            else
            {
                return 0;
            }
        }
        //base case
        
        //move pointer to end of list (first number)
        for(i = 1; i < len; i++)
        {
            temp_p = temp_p->next;
            temp_q = temp_q->next;
        }
        //check
        //if p>q
        if(temp_p->digit > temp_q->digit)
        {
            return 1;
        }
        //if p<q
        else if(temp_p->digit < temp_q->digit)
        {
            return -1;
        }
        //need more info, do it again
        else
        {
            return compareRec(temp_p, temp_q, len-1);
        }
    }
    
    ////////////////////////////////////////////////////////////////////////////////
    //Preconditions:    A valid list header
    //
    //Postconditions:   All nodes in list are freed
    //
    //Discription:      
    ////////////////////////////////////////////////////////////////////////////////
    void FreeList(struct integer *p)
    {
        struct integer* temp;
        //base case
        if(p != NULL)
        {
            
            //temp point to 2nd node
            temp = p->next;
            //do it again
            FreeList(temp);
            //free first node
            free(p);
        }
        //end case (nothing...this is a void function)
    }
    
    ////////////////////////////////////////////////////////////////////////////////
    //Preconditions:    Valid list of numbers
    //
    //Postconditions:   returns a head pointer to a resied list. The new list has
    //                  no ending zeros.
    //
    //Discription:      
    ////////////////////////////////////////////////////////////////////////////////
    struct integer* ResizeList(struct integer *p)
    {
        struct integer* temp;
        int len;
        
        //get list size (number of digits)
        len = ListSize(p);
    
        return ResizeListRec(p, len);
    }
    struct integer* ResizeListRec(struct integer *p, int len)
    {
        struct integer* temp;
        int i;
        
        //keeps the last number, no matter what (even 0)
        //end case
        if(len == 1)
        {
            temp = p->next;
            p->next = NULL;
            free(temp);
            return p;
        }
        if(len == 0)
        {
            return p;
        }
        //assign temp
        temp = p;  
    
        //put temp to last node (first digit)
        for(i = 0; i < len - 1 ; i++)
        {
            temp = temp->next;
        }
        //check to see if digit is 0
        if(temp->next->digit == 0)
        {
            //free usless node
            free(temp->next->next);
            //changes pointer to null (end of list)
            temp->next = NULL;
            //do it again
            return ResizeListRec(p, len - 1);
        }
        //if digit is not 0
        //end case
        else
        {
            return p;
        }
    }
    
    ////////////////////////////////////////////////////////////////////////////////
    //Preconditions:    Valid list of numbers
    //
    //Postconditions:   Returns an int the size of the number of nodes in the list
    //
    //Discription:      
    ////////////////////////////////////////////////////////////////////////////////
    int ListSize(struct integer *p)
    {
        struct integer* temp;
        int i;
        
        //assign temp
        temp = p;
        
        //count number of digits in list
        for(i = 0; temp->next != NULL; i++)
        {
            temp = temp->next;
        }
        return i;
    }

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Both the problems from the other thread seemed to be on subtracts, and more importantly subtracts with "bad" answers (-1, and 0). So check to see what happens when you try to borrow a number that you don't actually have (I didn't actually trace through your code, but that's my guess).

    How do you intend to handle negative numbers?

  3. #3
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    At least you are getting some practice writing code! 571 lines is a lot!

    Anyway, if you are still stuck on this point and having trouble, consider what I wrote to someone else here (post #2) about simple debugging techniques. You should not end up with so much code that contains such an ambiguous problem -- there is a real danger if you continue, that you will end up having to chuck days of work because you literally lost control of your own design. The fact that the assignment is so unorthodox makes this even trickier.

    You should always try and write so that your code can be executed at each (reasonable) step. I've written things that are thousands of lines and took weeks, but I never added more than twenty lines at a time without compiling and making sure everything runs. If that means sometimes having to write smaller temporary programs to test a thesis, that's fine. The bigger a program gets, the scarier it is when something doesn't work and the more crucial it is to isolate the problem, especially if you need to go to other people (who didn't write it) for help.

    That's like exponentially true when you start to consider memory issues, because an overwrite from any one place can doom you in any other. This is why I'm stressing the double-free concept again, because it's a shame you got to this point and were unaware of it. You have to develop your own way of keeping a firm handle on these things, whether it's learning to use a debugger or whatever, and you have to do it now. There is no way you can rely on others for this because they simply may be unable to do anything either.

    I'm sure I sound pompous and I wish I could be more help, t014y.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Need Help finding potential Memory issue
    By JoshNCSU22 in forum C Programming
    Replies: 9
    Last Post: 10-29-2008, 09:58 AM
  2. What's the difference?
    By Stonehambey in forum C++ Programming
    Replies: 9
    Last Post: 04-02-2008, 10:26 AM
  3. threads and memory issue
    By Anubhav in forum C Programming
    Replies: 6
    Last Post: 07-25-2006, 04:51 AM
  4. Memory Leak Help
    By (TNT) in forum Windows Programming
    Replies: 3
    Last Post: 06-19-2006, 11:22 AM
  5. Accessing Video Memory Information...need help
    By KneeLess in forum C++ Programming
    Replies: 8
    Last Post: 08-24-2003, 03:53 PM