Pointers & dereferencing confusion

This is a discussion on Pointers & dereferencing confusion within the C Programming forums, part of the General Programming Boards category; Ok, so I'm working on an assignment using linked lists to add/subtract large numbers. This is what I have so ...

  1. #1
    Registered User
    Join Date
    May 2010
    Location
    San Jose, California, United States
    Posts
    22

    Question Pointers & dereferencing confusion

    Ok, so I'm working on an assignment using linked lists to add/subtract large numbers. This is what I have so far:
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    struct linked_list {
    	   int data; /* data in this element */
    	   struct linked_list *next_ptr; /* pointer to next element */
    };
    struct linked_list *first_num = NULL;
    struct linked_list *second_num = NULL;
    struct linked_list *result = NULL;
    int carry = 0;
    
    /*
    *	Takes each character (number) and stores in its respective
    *	linked_list
    */
    void storeNum(char num)
    {	...
    	return;
    }
    
    void add()
    {	struct linked_list *new_item_ptr;
    	new_item_ptr = malloc(sizeof(struct linked_list));
    	struct linked_list *temp1 = first_num;
    	struct linked_list *temp2 = second_num;
    	int sum = 0;
    	int sum_nc = 0;
    	while(temp1 != NULL && temp2 != NULL){
    		sum = temp1->data+temp2->data+carry;
    		sum_nc = sum%10;
    		new_item_ptr->data = sum_nc;
    		if(sum>9) carry = (sum - sum_nc)/10;
    		else carry = 0;
    		new_item_ptr->next_ptr = result;
    		result = new_item_ptr;
    		temp1 = temp1->next_ptr;
    		temp2 = temp2->next_ptr;
    	}
    	while(temp1!=NULL){
    		...
    		//if the first number is longer than the second, add
    		//remaining numbers to result
    		...
    	}
    	while(temp2!=NULL){
    		...
    		//if the first number is longer than the second, add
    		//remaining numbers to result
    		...
    	}
    	if(carry!=0){
    		new_item_ptr->data = carry;
    		new_item_ptr->next_ptr = result;
    		result = new_item_ptr;
    		carry = 0;
    	}
    	return;
    }
    
    int main()
    {	char strIn[16]="";
    	while(fgets(strIn, sizeof(strIn), stdin)!=NULL){
    		if(isdigit(strIn[0])){
    			for(int i=0; i<strlen(strIn)-1; i++) storeNum(strIn[i]);
    			current++;
    		}
    		else if(strncmp(strIn,"+",1)==0){
    			add();
    			current = 0;
    		}
    		else return 0;
    		if(current==2) current = 0;
    	}
    	return 0;
    }
    It's going smoothly, except I notice that when I past past line 36 in GDB, result gets tied into new_item_ptr (they both seem to point to the same location in memory so when I make a change to new_item_ptr on, say line 53, result is also affected). How do I fix this?

    Thanks!
    Attached Files Attached Files
    • File Type: c hw7.c (2.7 KB, 58 views)
    Last edited by LanguidLegend; 11-16-2011 at 01:41 PM.

  2. #2
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,640
    The reason result is pointing to the same place is because that's what you told it to do. I'm not sure what you expect to happen, so I can't really offer a solution. I can say, however, that there are some fundamental changes I think you should make to your code.

    First, read this link. Global variables are evil. Declare them in the appropriate functions and pass them into other functions as needed. Your list variables should be declared in main, your carry variable should probably be declared in add, and you don't need current.

    Second, you should work on separating your list implementation from your add/subtract algorithm and your input handling. I would write a generic function called list_prepend or something, that takes a list and a number, creates a new node with that number data, and sticks that node at the beginning of the list. You're close with storeNum, but it's not generic, it doesn't work with any list. I would work on list_prepend and list_print first. Here's a hint to get you started with list_prepend:
    Code:
    struct linked_list *list_prepend(struct linked_list *list, int num)
    {
        allocate new node
        populate data with num
        set new node's next pointer to list
        return new node
    }
    ...
    // in main
    struct linked_list *first_num = NULL;  // initialize to NULL for empty list
    char c;
    first_num = list_prepend(first_num, c - '0');
    Note, it takes an int, not char. Do the conversion from char to int before calling list_prepend. This will allow result to use list_prepend as well since it uses the data elements from the linked_list nodes, not chars from user input.

    I know restarting from scratch sounds scary, but believe me, your code will be much simpler this way, less error prone, and easier to debug if need be. A good design makes coding and testing go much more quickly.

    You should also be testing frequently, and never move on to the next part until the part you are currently working on is error-free. Write 10-20 lines, then test, write 10-20 lines, then test, ad infinitum.

    Hopefully that helps.

  3. #3
    Registered User
    Join Date
    May 2010
    Location
    San Jose, California, United States
    Posts
    22
    Thanks for your quick reply
    Quote Originally Posted by anduril462 View Post
    The reason result is pointing to the same place is because that's what you told it to do. I'm not sure what you expect to happen, so I can't really offer a solution.
    Well, what I'm trying for in that part of the code is for result to just to create list nodes for result which will receive the sum of the corresponding first and second list nodes' numbers. As for the first_num and second_num lists, all I want is access to the data so I can add them and pass the sum to the corresponding result list node.
    Last edited by LanguidLegend; 11-16-2011 at 09:31 PM.

  4. #4
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,640
    I think if there is a carry left over at the end, you have to allocate another new_item_ptr and insert that at the head of the list.

  5. #5
    Registered User
    Join Date
    May 2010
    Location
    San Jose, California, United States
    Posts
    22

    Exclamation Updated program

    Thanks for all your quick replies, I've read them over and have tried to update my code accordingly (pasted below).
    However I'm still having a pointer problem. On the second pass through line 34, result becomes infinitely long, continually assigning the last element to its respective next_ptr (when I print, the last number gets printed an infinite number of times).

    (Assume the two given numbers are 67 and 89).
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    struct linked_list {
    	   int data; /* data in this element */
    	   struct linked_list *next_ptr; /* pointer to next element */
    };
    struct linked_list *result;
    
    struct list* storeNum(struct list* list, int num)
    {	struct linked_list *new_item_ptr;
    	new_item_ptr = malloc(sizeof(struct linked_list));
    	new_item_ptr->data = num;
    	new_item_ptr->next_ptr = list;
    	list = new_item_ptr;
    	return list;
    }
    
    void add(struct linked_list *first_num,	struct linked_list *second_num)
    {	struct linked_list *new_item_ptr =
    		(struct linked_list*)malloc(sizeof(struct linked_list));
    	struct linked_list *temp1 = first_num;
    	struct linked_list *temp2 = second_num;
    	int sum = 0;
    	int sum_nc = 0;
    	int carry = 0;
    	while(temp1!=NULL && temp2!=NULL){
    		sum = temp1->data+temp2->data+carry;
    		sum_nc = sum%10;
    		new_item_ptr->data = sum_nc;
    		if(sum>9) carry = (sum - sum_nc)/10;
    		else carry = 0;
    		new_item_ptr->next_ptr = result;
    		result = new_item_ptr;
    		temp1 = temp1->next_ptr;
    		temp2 = temp2->next_ptr;
    	}
    	struct linked_list* temp_ptr =
    			(struct linked_list*)malloc(sizeof(struct linked_list));
    	if(carry!=0){
    		temp_ptr->data = carry;
    		temp_ptr->next_ptr = result;
    		result = temp_ptr;
    		carry = 0;
    	}
    	return;
    }
    
    void printLists(struct linked_list* list)
    {	struct linked_list *temp = list;
    	printf("{ ");
    	while(temp!=NULL){
    		printf("%d ",temp->data);
    		temp = temp->next_ptr;
    	}
    	printf("}\n");
    }
    
    int main()
    {	struct linked_list *first_num = NULL;
    	struct linked_list *second_num = NULL;
    	int current = 0;
    	char strIn[16]="";
    	printf("Enter a command: ");
    	while(fgets(strIn, sizeof(strIn), stdin)!=NULL){
    		if(isdigit(strIn[0])){
    			if(current == 0){
    				for(int i=0; i<strlen(strIn)-1; i++)
    					first_num = storeNum(first_num, strIn[i]-'0');
    			} else if(current == 1){
    				for(int i=0; i<strlen(strIn)-1; i++)
    					second_num = storeNum(second_num, strIn[i]-'0');
    			}
    			current++;
    			printf("First number:\n");
    			printLists(first_num);
    			printf("Second number:\n");
    			printLists(second_num);
    		}
    		else if(strncmp(strIn,"+",1)==0){
    			add(first_num, second_num);
    			current = 0;
    			printf("Result:\n");
    			printLists(result);
    		}
    		else return 0;
    		if(current == 2) current = 0;
    		printf("\n Enter a command: ");
    	}
    	return 0;
    }
    **Note: I excluded the 2 previous while loops for brevity (assume both numbers are the same length).
    Last edited by LanguidLegend; 11-17-2011 at 08:07 AM.

  6. #6
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,640
    Your storeNum and printList look great. A few small things to clear up first:

    Here's what happens when I compile your program:
    Code:
    $ gcc -Wall -g -std=c99  list.c   -o list
    list.c: In function ‘storeNum’:
    list.c:15: warning: assignment from incompatible pointer type
    list.c:16: warning: assignment from incompatible pointer type
    list.c: In function ‘main’:
    list.c:69: warning: implicit declaration of function ‘isdigit’
    list.c:71: warning: implicit declaration of function ‘strlen’
    list.c:71: warning: incompatible implicit declaration of built-in function ‘strlen’
    list.c:72: warning: passing argument 1 of ‘storeNum’ from incompatible pointer type
    list.c:10: note: expected ‘struct list *’ but argument is of type ‘struct linked_list *’
    list.c:72: warning: assignment from incompatible pointer type
    list.c:74: warning: incompatible implicit declaration of built-in function ‘strlen’
    list.c:75: warning: passing argument 1 of ‘storeNum’ from incompatible pointer type
    list.c:10: note: expected ‘struct list *’ but argument is of type ‘struct linked_list *’
    list.c:75: warning: assignment from incompatible pointer type
    list.c:83: warning: implicit declaration of function ‘strncmp’
    If you don't a list of warnings like this, then turn up the warnings on your compiler.
    • Lines 10, 15, 16, 72, 75: All these are because you used 'struct list' on line 10 instead of 'struct linked_list'
    • Line 69: You need to #include <ctype.h>
    • Line 71, 74, 83: You need to #include <string.h>


    I fixed that and ran your program with the given input. Here's what I got:
    Code:
    $ ./list
    Enter a command: 67+89
    First number:
    { 9 8 -5 7 6 }
    Second number:
    { }

    Your add doesn't work because you incorrectly build first_num and second_num. The problems are happening in main, not in add. You can tell because the lists are printed before add is called, so that's not where the problem is. Think about your parsing. Right now, you fill first_num with everything from the user input, from index 0 to length-1. You need to stop adding things to first_num when you get a '+' or '-'. Then, store the + or - for later, and read all the subsequent digits into second num. Again, there is no need for your 'current' variable. Something like:
    Code:
    i = 0
    length = strlen(input)  // this just saves us from calling strlen a bunch of times
    while i < length and input[i] is a digit
        add it to first_num
        i++
    if i < length and input[i] is a '+' or a '-'
        op = input[i]
        i++
    while i < length and input[i] is a digit
        add input[i] to second_num
        i++
    
    if op is a '+'
        result = add(first_num, second_num)
    else if op is a '-'
        result = subtract(first_num, second_num)
    print result
    result shouldn't be global. You can have the list built inside add, using storeNum (which is why I suggested you rewrite it), and simply return the pointer to the head of the list. This will also avoid any strange pointer issues. Lastly, you are making your computations overly complex. There's no need for sum_nc or your if (sum>9) bit. Try:
    Code:
    struct linked_list *add(struct linked_list *first_num, struct linked_list *second_num)
    {
        struct linked_list result = NULL; // local list, initialized to NULL
        ...
        sum = temp1->data + temp2->data + carry;
        result = storeNum(result, sum % 10);
        carry = sum / 10;
        ...
        return result;
    }

  7. #7
    Registered User
    Join Date
    May 2010
    Location
    San Jose, California, United States
    Posts
    22
    Quote Originally Posted by anduril462 View Post
    I fixed that and ran your program with the given input. Here's what I got:
    Code:
    $ ./list
    Enter a command: 67+89
    First number:
    { 9 8 -5 7 6 }
    Second number:
    { }
    Your add doesn't work because you incorrectly build first_num and second_num.
    The assignment I was given instructed me to follow the following sample format:
    Code:
    $./list
    Enter a command: 67
    
    Enter a command: 89
    
    Enter a command: +
    67 + 89 = 156

  8. #8
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,640
    Oh, okay. Well, I still recommend ditching your 'current' variable. Just ask for the input 3 times:
    Code:
    do {
        print "Enter a command: "
        read line
        add digits to first_num
    
        print "Enter a command: "
        read line
        add digits to second_num
    
        print "Enter a command: "
        read line
        if it's a "+"
            result = add(first_num, second_num)
    
        print result
    } while (!done);
    You'll have to figure out exactly what conditions to end your loop on, but that's the general idea. It should help with a few of the problems you're having.

  9. #9
    Registered User
    Join Date
    May 2010
    Location
    San Jose, California, United States
    Posts
    22

    Thumbs up

    Thanks anduril for all your help... I'm just about done I think but I have one last thing tripping me up.
    Code:
    void printList(struct linked_list* list)
    {	struct linked_list *temp = list;
    	int len = *(&temp->index);
    	int arr[len];
    	int i = 1;
    	while(temp!=NULL){
    		arr[len-i] = *(&temp->data);
    		temp = temp->next_ptr;
    		++i;
    	}
    	printf("{ ");
    	for(int i=0; i<len; i++)
    		printf("%d",arr[i]);
    	printf("}\n");
    }
    When I step through printList in gdb, it seems as though my array is not being modified, despite my attempts to assign temp->data to it.. I also tried declaring arr using int* arr = malloc(len*sizeof(int)), but same result.

  10. #10
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,640
    I don't know with out seeing your whole code. You've made some changes (notably adding an index field), so I'm not sure you're building your list with correct index values. Run through your code in a debugger and step through each line of printList one by one.

    Note that the algorithm I gave you results in first_num and second_num being stored in reverse, but result will be stored forward. You should probably leave printList as it was, and write a second function, printListReverse to print it backwards. There is a very easy recursive solution to printListReverse if you want to try that way.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Confusion With Pointers
    By ObjectWithBrain in forum C Programming
    Replies: 28
    Last Post: 07-14-2011, 12:44 PM
  2. Confusion using pointers
    By kluxy in forum C Programming
    Replies: 10
    Last Post: 03-27-2010, 01:07 AM
  3. Dereferencing Pointers help
    By Rune Hunter in forum C++ Programming
    Replies: 10
    Last Post: 07-14-2007, 07:43 PM
  4. dereferencing pointers to pointers
    By Potterd64 in forum C++ Programming
    Replies: 3
    Last Post: 07-11-2006, 05:53 AM
  5. Confusion about pointers
    By rishiputra in forum C Programming
    Replies: 1
    Last Post: 05-01-2003, 05:39 PM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21