Linked List question (C)

linuxlover1 · 03-07-2007, 02:17 PM

Hi , i wrote a function , that creates an order Linked-List. The problem here is when i want to add a node at the end of the list nothing happens (I print the list and the last node is missing).
If you have any idea , whats wrong with the code please help.
Thx a lot !!

Code:

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

struct linked_list {
	int num;
	struct linked_list *next;
};
typedef struct linked_list node;

void inorder(node **head,int value);
void print(node *head);

main() {
        node *head;
	head=NULL;
	printf("Implementing a Linked-List\n");
        inorder(&head,10);
        inorder(&head,7);
	inorder(&head,-1);
	inorder(&head,11);
	print(head);
}

void inorder(node **head,int value) {
	node *new_node,*start,*before;
	start=*head;
	int end=0;
	new_node=(node *)malloc(sizeof(node));
	new_node->num=value;
	if ( *head==NULL) {
		new_node->next=*head;
		*head=new_node;
	}
	else if (new_node->num < start->num) {
		new_node->next=start;
		*head=new_node;
	}
	else {
		while ( start->num < new_node->num) {
			before=start;
			start=start->next;
			if ( start==NULL) {
				start=new_node;
				new_node->next=NULL;
				end=1;
				break;
			}
		}
		if (end==0) {
			before->next=new_node;
			new_node->next=start;
		}
	}
}

void print(node *head) {
	int i=1;
	while (head != NULL ) {
		printf("Node%d=%d\n",i,head->num);
		i++;
		head=head->next;
	}
}

nadroj · 03-07-2007, 06:45 PM

Code:

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

struct linked_list {
        int num;
        struct linked_list *next;
};
typedef struct linked_list node;

void inorder(node **head,int value);
void print(node *head);

int main() { // main should be int
        node *head;
        head=NULL;
        printf("Implementing a Linked-List\n");
        inorder(&head,10);
        inorder(&head,7);
        inorder(&head,-1);
        inorder(&head,11);
        print(head);

        // here you should use a loop and free the memory. for each (successful) malloc call you need a free

        return 0;
}

void inorder(node **head,int value) {
        node *new_node,*start,*before;
        start=*head;
        int end=0;
        new_node=(node *)malloc(sizeof(node*)); //sizeof(node) and sizeof(node*) are not the same

        if (new_node == NULL) // alwayws check to see if malloc was successfully
        {
                perror("could not allocate space");
                return;
        }

        new_node->num=value;
        if ( *head==NULL) {
                new_node->next=*head;
                *head=new_node;
        }
        else if (new_node->num < start->num) {
                new_node->next=start;
                *head=new_node;
        }
        else {
                while ( start->num < new_node->num) { // the body of your while loop was the actual problem
                        before=start;
                        start=start->next;   
                        if ( start==NULL) {  
                                start=before;
                                start->next=new_node;
                                end=1;
                                break;
                        }
                }
                if (end==0) {
                        before->next=new_node;
                        new_node->next=start;
                }
        }
}

void print(node *head) {
        int i=1;
        while (head != NULL ) {
                printf("Node%d=%d\n",i,head->num);
                i++;
                head=head->next;
        }
}

hope it helps. let me know if you want to ask anything. also do some more testing to see if this is fail-proof.

v.tieubao · 03-07-2007, 09:37 PM

Quote:

Originally Posted by linuxlover1

Hi , i wrote a function , that creates an order Linked-List. The problem here is when i want to add a node at the end of the list nothing happens (I print the list and the last node is missing).
If you have any idea , whats wrong with the code please help.
Thx a lot !!

Code:

....
		while ( start->num < new_node->num) {
			before=start;
			start=start->next;
			if ( start==NULL) {
				start=new_node; //before->next=new_node;
				new_node->next=NULL;
				end=1;
				break;
			}
		}
....

See red comment on your code, hope it help.

Cheers

sundialsvcs · 03-07-2007, 09:40 PM

It's usually not considered good form to help a student with his or her homework...

The trick in working out algorithms like this one is to grab a piece of paper and a number-two pencil and draw it out.

linuxlover1 · 03-08-2007, 03:49 AM

Thx a lot men

!