Thread: linked list

  1. #1
    Registered User
    Join Date
    Dec 2010
    Posts
    8

    linked list

    Hello,
    I am new to C. I have some experience with Java, because that is what they are teaching us. But I really want to learn C because I want to get a decent job doing decent code, so I am redoing my homeworks in C, or at least attempting to. Anyway I have a long way to go.
    I am struggling with my attempt to use a linked list to implement a queue.
    I include my code below.
    Basically I want a queue struct containing a counter (for O(1) queue-count) and a link to the first node of the queue.
    I then have a node struct.
    My problem is with the add function - it should add new entries to the end of the linked list - which is accessed through the queue struct instance.
    However it is hanging in the node traversal loop. I do not know why. I have included print statements to see/show where the problem is.
    I am probably misunderstanding something fundamental, but I do not know what it is, and I have researched the web for hours, but have not found an example that works for me. I am using VS2010.

    The relevant code, I think, is the main method, the makeQueue() method, and the add() method. I include the rest simply to give the full context.

    I would be really grateful is someone could give me some constructive help here, as I would really love to improve my core programming skills. For the same reason I do not want to use any higher order library functions - I want to use the basic functionalities of C for this.

    Thanks so much for your help!

    Code:
    #include "stdafx.h"
    #include <stdio.h>
    #include <iostream>
    #include "stdlib.h"
    #include <string.h>
    
    
    typedef struct node{			//a string node struct
    	char* val;
    	struct node* next;
    } list_node;
    
    typedef struct queue{    //queue struct
    	struct node* first;
    	int count;
    } list_queue;
    
    
    list_queue* makeQueue();
    void add(list_queue*, char*);
    char* remove(list_queue*);
    int isEmpty();
    void print(list_queue*);
    
    int main()
    {
    	list_queue* myQueue = makeQueue();
    
    	int xx = 1;
    	while(xx){
    	
    		printf("Enter: Insert, Remove, GetSize, Quit:\n");
    		char input[16];
    		scanf("%s",input);
    		//printf("%i",strlen(input));
    		if(*input == 'I' || *input == 'i'){
    			char name[30];
    			printf("Enter Name:\n");
    			scanf("%s",name);
    			add(myQueue, name);
    		}
    		else if(*input == 'R' || *input == 'r'){
    			remove(myQueue);
    		}
    		else if(*input == 'G' || *input == 'g'){
    			printf("%i\n",myQueue->count);
    		}
    		else if(*input == 'Q' || *input == 'q'){
    			break;		
    		}
    		print(myQueue);
    	}
    
    	printf("\n");
    
    	char* cl;
    	printf("\n\nEnter any character and press enter:");
    	scanf("%1s", &cl);
    	return 0;
    }
    
    list_queue* makeQueue(){          //return *list_queue
    	list_queue* l_s = (list_queue*) malloc(sizeof(list_queue)); 
    	l_s->first = NULL;
    	l_s->count = 0;
    	return l_s;
    }
    
    void add(list_queue* s, char* c){
    	if(s->first == NULL){
    		printf("FIRST NODE\n");
    		s->first = (list_node*) malloc(sizeof(list_node));
    		s->first->val = c;
    		s->first->next = NULL;
    	}
    	else{
    		printf("HELLO\n");
    		list_node* prior = s->first;
    		list_node* current = s->first;
    		printf("HELLO2\n");            //THIS IS WHERE IT ALL GOES WRONG
    		if(current!=NULL) printf("NOT NULL\n");
    		while(current != NULL);
    		{	printf("HELLO3\n");
    			prior = current;
    			current = current->next;
    		}
    
    		current = (list_node*) malloc(sizeof(list_node));
    		current->val = c;
    		current->next = NULL;
    		prior->next = current;
    	}
    	s->count++;
    }
    
    char* remove(list_queue* s){
    	char* c = s->first->val;
    	list_node* t = s->first;
    	s->first = s->first->next;
    	free(t);
    	s->count--;
    	return c;
    }
    
    void print(list_queue* s){
    
    	list_node* t = s->first;
    	while(t != NULL){
    		int n = strlen(t->val);
    		char* str = t->val;
    		for(int i = 0; i < n; i++){
    			printf("%c", *(str+i));
    		}
    		printf(" ");
    		t = t->next;
    	}
    	printf("\n");
    }

  2. #2
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,909
    Code:
    while(current != NULL);
    Ditch that semicolon. It's running the while loop with no body, so you never update current. Hence your infinite loop.

    The other problem I noticed is that you are assigning the name entered to c in add. C doesn't support assignment of strings, or anything that's pointed to, the way java does it for you behind the scenes. This causes every node in your queue to point to the address of the name variable in your main function. You need to allocate enough space for the string, plus 1 for the null, then copy it in, like so:
    Code:
    s->first->val = malloc(strlen(c) + 1);
    strcpy(s->first->val, c);
    Check the tutorials here for a little more info on strings and pointers:
    C Strings - C++ Tutorial - Cprogramming.com
    Cprogramming.com Tutorial: Pointers

  3. #3
    Registered User
    Join Date
    Dec 2010
    Posts
    8
    Hey Anduril,
    Thanks a million.
    Sorry about that semi-colon stupidity. It was not there at one point - I think tiredness got the better of me there.
    Once it was removed I was right back to an earlier problem - the very one you explained re: the char* - I am guessing that this is why earlier I kept on getting the last name I entered repeated through the list!
    Your answer is spot on. Thanks for the explanation, and thanks for looking past the dumb semi-colon mistake to show me the deeper problem.

    Junket

  4. #4
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,909
    You're welcome, and don't sweat the little error. Happens to all of us (it's just more embarrassing when you've been doing this 10 years and get caught up by something like that).

    And yes, that's what caused your same name problem.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. C++ Linked list program need help !!!
    By dcoll025 in forum C++ Programming
    Replies: 1
    Last Post: 04-20-2009, 10:03 AM
  2. Following CTools
    By EstateMatt in forum C Programming
    Replies: 5
    Last Post: 06-26-2008, 10:10 AM
  3. Reverse function for linked list
    By Brigs76 in forum C++ Programming
    Replies: 1
    Last Post: 10-25-2006, 10:01 AM
  4. Template Class for Linked List
    By pecymanski in forum C++ Programming
    Replies: 2
    Last Post: 12-04-2001, 09:07 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM

Tags for this Thread