C Board  

Go Back   C Board > General Programming Boards > C Programming

Reply
 
LinkBack Thread Tools Display Modes
Old 06-26-2009, 12:04 PM   #1
Registered User
 
Join Date: May 2009
Posts: 7
Help with linked lists/ pointers

I am trying to write a simple C program that creates a linked list and then prints out the values stored in the list. I am not sure what part of the code isn't correct but when it prints out the entries it will only print out one entry and it looks to be a memory location instead of the value stored in the node. Also, and this is the part that really throws me off, sometimes when i compile the code i get the error "invalid conversion from 'void*' to 'node*' " on every line that I use malloc and other times it compiles with no errors. Here is the code:

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

typedef struct node *nodePtr;

struct node {
  int value;
  nodePtr next;
};

typedef struct node node;

void createNewNode(nodePtr head, nodePtr newNode);
void printList(nodePtr head);

int main(int argc, const char * argv[]) {
    nodePtr first = malloc(sizeof(node));
    nodePtr newNode = malloc(sizeof(node));
    int numberOfEntries = 0;

    first->next = NULL;

    printf("Number of Entries: ");
    scanf("%d", &numberOfEntries);
    printf("\n");

    if(numberOfEntries == 1) {
        printf("Enter Value: ");
        scanf("%d", first->value);
        printf("\n");
    } else {
        int i = 0;
        while(i < numberOfEntries) {
            printf("Enter Value: ");
            scanf("%d", first->value);
            printf("\n");

            createNewNode(first, newNode);
            i++;
        }
    }
    printList(first);

    return 0;
}

void createNewNode(nodePtr head, nodePtr newNode) {
    newNode->next = head;
    head = newNode;
}

void printList(nodePtr head) {
    nodePtr current = malloc(sizeof(node));
    current = head;

    while(current->next != NULL) {
        printf("Entry: %d\n", current->value);
        current = current->next;
    }

    printf("Entry: %d\n", current->value);

    free(current);
}
If someone could take a look at this and point me to where I've made a mistake I would greatly appreciate it.
anything25 is offline   Reply With Quote
Old 06-26-2009, 12:14 PM   #2
pwning noobs
 
Zlatko's Avatar
 
Join Date: Jun 2009
Location: The Great White North
Posts: 125
You're passing head to createNewNode by value.
__________________
Sun Certified Java Programmer / Developer
IEEE CSDP
Zlatko is offline   Reply With Quote
Old 06-26-2009, 12:26 PM   #3
subminimalist
 
MK27's Avatar
 
Join Date: Jul 2008
Location: NYC
Posts: 3,945
You are confusing yourself with this:
Code:
typedef struct node *nodePtr;

struct node {
  int value;
  nodePtr next;
};
Just use:
Code:
typedef struct _node {
  int value;
  struct _node *next;
} node;
Now you can properly refer to a node, and a *node.

All linked list functions should be passed pointers:
Code:
void createNewNode(node *head, node *newNode);
void printList(node *head);
__________________

Accuracy and integrity mean nothing if you don't make it past the censors...PYTHAGORAS
MK27 is online now   Reply With Quote
Old 06-26-2009, 12:28 PM   #4
Registered User
 
Join Date: May 2009
Posts: 7
I looked at createNewNode and tried changing a couple things, but that only seemed to make it worse. I am not sure that I completely understand what you mean by pass head in by value (I am pretty new to programming). Also, while that I don't doubt that the function is flawed, it still doesn't explain why the code would not work correctly if there is only one element in the list since that function would never be executed.
anything25 is offline   Reply With Quote
Old 06-26-2009, 12:28 PM   #5
C++ Witch
 
laserlight's Avatar
 
Join Date: Oct 2003
Location: Singapore
Posts: 10,365
Quote:
Originally Posted by MK27
Just use:
Alternatively, you could shift that later typedef to before the struct definition:
Code:
typedef struct node node;

struct node {
  int value;
  node *next;
};
__________________
C + C++ Compiler: MinGW port of GCC
Build + Version Control System: SCons + Bazaar

Look up a C/C++ Reference and learn How To Ask Questions The Smart Way
laserlight is online now   Reply With Quote
Old 06-26-2009, 12:38 PM   #6
subminimalist
 
MK27's Avatar
 
Join Date: Jul 2008
Location: NYC
Posts: 3,945
Quote:
Originally Posted by anything25 View Post
Also, while that I don't doubt that the function is flawed, it still doesn't explain why the code would not work correctly if there is only one element in the list since that function would never be executed.
It is very important that you use one of the forms recommended by either me or laserlight. You need to pass pointers without obfuscating the fact; this will make debugging your program that much easier as well.

You are not actually passing by value, it just looks that way because you have created a datatype which is a pointer. There is no need for that and it is obviously confusing you *and* the people you are looking to for help.
__________________

Accuracy and integrity mean nothing if you don't make it past the censors...PYTHAGORAS
MK27 is online now   Reply With Quote
Old 06-26-2009, 12:38 PM   #7
pwning noobs
 
Zlatko's Avatar
 
Join Date: Jun 2009
Location: The Great White North
Posts: 125
Quote:
Originally Posted by anything25 View Post
I looked at createNewNode and tried changing a couple things, but that only seemed to make it worse. I am not sure that I completely understand what you mean by pass head in by value (I am pretty new to programming). Also, while that I don't doubt that the function is flawed, it still doesn't explain why the code would not work correctly if there is only one element in the list since that function would never be executed.
OK, there may be a number of issues here, but remember if you have a function that takes an integer
Code:
void foo(int i)
{
     i = i + 1
}
int main()
{
   int i  = 0;
   foo(i);
}
and you increment i in the function, the caller will not see the change because i is a copy of what the caller passed in.

Now you have a pointer called first in main and you're passing it into creatNewNode as head and you want first in main to be changed to point to newNode so you must pass in the address of the variable to be changed.

The function should be
Code:
void createNewNode(nodePtr* head, nodePtr newNode)
{
   newNode->next = *head;
   *head = newNode;
}

May I ask, what development tools are you using?

Best regards
Zlatko
__________________
Sun Certified Java Programmer / Developer
IEEE CSDP
Zlatko is offline   Reply With Quote
Old 06-26-2009, 12:42 PM   #8
subminimalist
 
MK27's Avatar
 
Join Date: Jul 2008
Location: NYC
Posts: 3,945
Quote:
Originally Posted by Zlatko View Post
and you increment i in the function, the caller will not see the change because i is a copy of what the caller passed in.
This is a good explanation of the difference between pass by value/pass by reference *but* Zlatko, look, the OP is passing by reference:

Code:
typedef struct node *nodePtr;
That is the first thing which needs to be fixed tho, since this is not a nice way to program at all.
__________________

Accuracy and integrity mean nothing if you don't make it past the censors...PYTHAGORAS
MK27 is online now   Reply With Quote
Old 06-26-2009, 12:49 PM   #9
Registered User
 
Join Date: May 2009
Posts: 7
Thanks for all of the replies. I see what you guys mean about the form it is in and have changed the code so that it shouldn't be as confusing. Here is the changed code:
Code:
#include <stdio.h>
#include <stdlib.h>

typedef struct node {
  int value;
  struct node *next;
} node;

void createNewNode(node *head, node *newNode);
void printList(node *head);

int main(int argc, const char * argv[]) {
    node *first;
    first = malloc(sizeof(node));
    node *newNode;
    newNode = malloc(sizeof(node));
    int numberOfEntries = 0;

    first->next = NULL;

    printf("Number of Entries: ");
    scanf("%d", &numberOfEntries);
    printf("\n");

    if(numberOfEntries == 1) {
        printf("Enter Value: ");
        scanf("%d", first->value);
        printf("\n");
    } else {
        int i = 0;
        while(i < numberOfEntries) {
            printf("Enter Value: ");
            scanf("%d", first->value);
            printf("\n");

            createNewNode(first, newNode);
            i++;
        }
    }
    printList(first);

    return 0;
}

void createNewNode(node *head, node *newNode) {
    newNode->next = head;
    head = newNode;
}

void printList(node *head) {
    node *current;
    current = malloc(sizeof(node));
    current = head;

    while(current->next != NULL) {
        printf("Entry: %d\n", current->value);
        current = current->next;
    }

    printf("Entry: %d\n", current->value);

    free(current);
}
I am still pretty lost with what else is wrong with the code.... Linked lists are confusing the hell out of me lol

Last edited by anything25; 06-26-2009 at 01:05 PM.
anything25 is offline   Reply With Quote
Old 06-26-2009, 12:57 PM   #10
Registered User
 
Join Date: May 2009
Posts: 7
Also, as Ive been playing with the code I've realized that the while loop in the printList function never executes. I think I have that code right so I'm assuming that it is probably due to one of my other errors in the code.
anything25 is offline   Reply With Quote
Old 06-26-2009, 01:08 PM   #11
and the Hat of Guessing
 
tabstop's Avatar
 
Join Date: Nov 2007
Posts: 8,740
Quote:
Originally Posted by MK27 View Post
This is a good explanation of the difference between pass by value/pass by reference *but* Zlatko, look, the OP is passing by reference:

Code:
typedef struct node *nodePtr;
That is the first thing which needs to be fixed tho, since this is not a nice way to program at all.
I think you've lost the plot, MK. No matter what the typedef is, this code:
Code:
void createNewNode(nodePtr head, nodePtr newNode) {
    newNode->next = head;
    head = newNode;
}
cannot possibly change head in the main function. The fact that it is a pointer is completely irrelevant.
tabstop is offline   Reply With Quote
Old 06-26-2009, 01:29 PM   #12
pwning noobs
 
Zlatko's Avatar
 
Join Date: Jun 2009
Location: The Great White North
Posts: 125
Code:
#include <stdio.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct node {
  int value;
  struct node *next;
} node;

void createNewNode(node **head, node *newNode);
void printList(node *head);

int main(int argc, const char * argv[]) {
    node *first;
    first = (node*)malloc(sizeof(node));
    first->next = NULL; //Change // ALWAYS DO THIS
    node *newNode = NULL;
    //Change newNode = (node*)malloc(sizeof(node));
    int numberOfEntries = 0;

    first->next = NULL;

    printf("Number of Entries: ");
    scanf("%d", &numberOfEntries);
    printf("\n");

    if(numberOfEntries == 1) {
        printf("Enter Value: ");
        scanf("%d", &(first->value));
        printf("\n");
    } else {
        int i = 0;
        while(i < numberOfEntries) {
            printf("Enter Value: ");
            
            int value;
            scanf("%d", &value); // Change 
            if (i == 0) // Change
            {
                first->value = value;
            }
            else
            {
                newNode = (node*)malloc(sizeof(node)); //Change
                newNode->value = value;
                newNode->next = NULL; // ALWAYS DO THIS
                createNewNode(&first, newNode); // Change
            }
            printf("\n");
            i++;
        }
    }
    printList(first);

    return 0;
}

void createNewNode(node **head, node *newNode) {
    //newNode->next = head;
    //head = newNode;
    // Changed
    newNode->next = *head;
    *head = newNode;
}

void printList(node *head) {
    //node *current;
    //current = (node*)malloc(sizeof(node));
    //current = head;

    //while(current->next != NULL) {
    //    printf("Entry: %d\n", current->value);
    //    current = current->next;
    //}

    //printf("Entry: %d\n", current->value);

    //free(current);


    node* current = head;
    while(current != NULL)
    {
        printf("Entry: %d\n", current->value);
        current = current->next;
    }
}
OK, I don't want to be accused of corrupting the youth, but I felt I had to post the entire code to explain it.

1. You don't need to allocate a newNode at the start of main. You need to allocate it in the while(i<numberOfEntries) loop.

2. Always set your pointers to NULL in your structs as soon as you do the malloc, otherwise you'll forget.

3. Scanf into an address scanf("%d", node->value) does not scan into value. It takes node->value and looks at value and treats that as an address. The syntax should be scanf("%d", &(node->value))

4. On the first time through the loop use the node* first already allocated. This is not how I'd organize the loop, but OK.

5. When calling createNewNode, you must pass in the address of the first pointer. If you wanted to change an integer in a function and have the change visible to the caller, you would pass in a pointer to the integer. Here you want to change a pointer and have the change visible to the caller so you must pass in a pointer to a pointer.

6. Watch how node**head is used in createNewNode. Make sure you understand that.

7. While printing the list, there is no need to allocate new memory. You simply walk through the existing memory.

Best regards
Zlatko
__________________
Sun Certified Java Programmer / Developer
IEEE CSDP
Zlatko is offline   Reply With Quote
Old 06-26-2009, 01:31 PM   #13
subminimalist
 
MK27's Avatar
 
Join Date: Jul 2008
Location: NYC
Posts: 3,945
Here's a little thing that might cause a problem:
Code:
scanf("%d", &first->value);
Again, this is a value vs. reference issue; scanf expects an address reference, so use the &address of operator.

It's not that the printList while loop isn't executing, it's that createNewNode doesn't work. Also, why do you have a malloc call in printList()? Malloc allocates memory for a node -- that is part of what is missing in createNewNode.

You do not need to create more than one *node in main(), namely "head", and malloc it there. No matter what, for the first entry, use that one. For the subsequent ones, you pass the head to createNewNode, which malloc's a new node and set's the last node's next to that:
Code:
void createNewNode(node *head, int val) {
	node *new = malloc(sizeof(node)), *cur=head;
	new->value = val;
	while (cur->next) cur=cur->next;
	cur->next=new;
}
So now your main should look something like this:
Code:
   node *first = malloc(sizeof(node));
    int numberOfEntries = 0, value;
	int i = 0;

    printf("Number of Entries: ");
    scanf("%d", &numberOfEntries);
    printf("\n");

	printf("Enter Value: ");
	scanf("%d", &first->value);
	printf("\n");
        while(i < numberOfEntries-1) {
            printf("Enter Value: ");
            scanf("%d", &value);
            printf("\n");

            createNewNode(first,value);
            i++;
        }
Zlatko, becasue of issue #5 above, uses a pointer to a pointer (**) to accomplish the same thing, you may find my method somewhat simpler and easy to understand (or it may be the other way around).

@tabstop: my point was the unorthodox typedef'ing is the first mistake that needs correcting. Neither I nor you nor anyone else will want to correct the OP while maintaining that.
__________________

Accuracy and integrity mean nothing if you don't make it past the censors...PYTHAGORAS

Last edited by MK27; 06-26-2009 at 01:38 PM.
MK27 is online now   Reply With Quote
Old 06-26-2009, 01:32 PM   #14
pwning noobs
 
Zlatko's Avatar
 
Join Date: Jun 2009
Location: The Great White North
Posts: 125
Keep at it until you understand it.
Step through it with a debugger.
Ask questions
We want you to pass your course!


EDIT:
IMHO there was nothing wrong with your originaly typedef-ing
__________________
Sun Certified Java Programmer / Developer
IEEE CSDP

Last edited by Zlatko; 06-26-2009 at 01:36 PM.
Zlatko is offline   Reply With Quote
Old 06-26-2009, 02:41 PM   #15
Registered User
 
Join Date: May 2009
Posts: 7
Thank you everyone so much for the help! I've got the code working and also understand pointers a whole lot more then when I started. Thanks again!
anything25 is offline   Reply With Quote
Reply

Thread Tools
Display Modes

Forum Jump

Similar Threads
Thread Thread Starter Forum Replies Last Post
Doubly linked lists mohanlon C Programming 7 06-27-2009 07:45 PM
Linked Lists wvu2005 C Programming 12 10-06-2005 11:36 AM
Linked Lists 101 The Brain C++ Programming 5 07-24-2004 04:32 PM
eof in fstream & singly linked lists mazo C++ Programming 3 06-03-2002 09:50 AM
Linked lists and file i/o, and some other stuff ninja C++ Programming 9 05-19-2002 07:15 PM


All times are GMT -6. The time now is 07:43 AM.


Powered by vBulletin® Version 3.8.1
Copyright ©2000 - 2009, Jelsoft Enterprises Ltd.
Search Engine Optimization by vBSEO 3.3.0 RC2

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