Inserting alphabetically into a Linked List

This is a discussion on Inserting alphabetically into a Linked List within the C++ Programming forums, part of the General Programming Boards category; I'm having trouble figuring out how to do this. I think I'm sort of close. Code: void compclass::addstudent(char tname[]) { ...

  1. #1
    EDL
    EDL is offline
    Registered User
    Join Date
    May 2002
    Posts
    18

    Inserting alphabetically into a Linked List

    I'm having trouble figuring out how to do this. I think I'm sort of close.

    Code:
    void compclass::addstudent(char tname[]) {
    	student *newstud = new student;
    	student *head = studentlist;
    	student *tail = studentlist;
    	int count = 0;
    	
    	if (count >= 1) {
    		head = studentlist->retnext();
    	}
    	newstud->setname(tname);
    	if (studentlist == NULL) {
    		newstud->setnext(NULL);
    		studentlist = newstud;
    		count++;
    		return;
    	}
    	else {
    		if (strcmp(tail->retname(), newstud->retname()) > 0) {
    				newstud->setnext(studentlist);
    				studentlist = newstud;
    				return;
    			}
    		while (strcmp(head->retname(), newstud->retname()) < 0) {
    			
    			if (strcmp(head->retname(), newstud->retname()) < 0) {
    				newstud->setnext(head);
    				tail->setnext(newstud);
    				return;
    			}
    			tail = tail->retnext();
    			head = head->retnext();
    		}
    		tail = newstud->retnext();
    		newstud = head->retnext();
    	}
    }
    It just goes into an infinite loop, because somehow I'm linking them to each other. If I add it to where it's alphabetically lower, it works fine. When I add something alphabetically higher however, it actually looks to add ok. But when I try to print the list of students, that's when it goes into the loop.

  2. #2
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,422
    > while (strcmp(head->retname(), newstud->retname()) < 0)
    I think you need to cater for the case when the new node is appended to the end of the list

    Code:
    while ( head != NULL &&
            strcmp(head->retname(), newstud->retname()) < 0)
    If you exit the loop with head == NULL, then you need to append the new node to the end of the list

    Apart from the initial test, you don't use the tail variable, so there seems to be no point updating it

    > if (count >= 1)
    Why is this a special case?

  3. #3
    EDL
    EDL is offline
    Registered User
    Join Date
    May 2002
    Posts
    18
    Yeah, my code really makes no sense the more I look at it. I actually changed the count statement to

    Code:
     if (studentlist != NULL)
    No luck though getting this function to work properly though...

  4. #4
    EDL
    EDL is offline
    Registered User
    Join Date
    May 2002
    Posts
    18
    Ok, well, I got it partially working now. It will add on to the top of the list and to the end of the list, but will not add any names in between. So i can add say, John, then I can add Jim, then add Stuart. But If I try to add Kim, it just doesn't show up. Here's my code now:

    Code:
    void compclass::addstudent(char tname[]) {
    	student *newstud = new student;
    	student *head = studentlist;
    	student *tail = studentlist;
    	
    	
    	if (studentlist != NULL) {
    		tail = studentlist->retnext();
    	}
    	newstud->setname(tname);
    	if (studentlist == NULL) {
    		newstud->setnext(NULL);
    		studentlist = newstud;
    		
    		return;
    	}
    	else {
    		if (strcmp(head->retname(), newstud->retname()) > 0) {
    				newstud->setnext(studentlist);
    				studentlist = newstud;
    				return;
    			}
    		if ((strcmp(head->retname(), newstud->retname()) < 0) && (tail == NULL)) {
    			head->setnext(newstud);
    			newstud->setnext(NULL);
    			return;
    		}
    		while (tail != NULL && strcmp(tail->retname(), newstud->retname()) < 0) {
    			if (strcmp(tail->retname(), newstud->retname()) > 0) {
    				newstud->setnext(tail);
    				head->setnext(newstud);
    				return;
    			}
    			tail = tail->retnext();
    			head = head->retnext();
    			if (tail == NULL) {
    				head->setnext(newstud);
    				newstud->setnext(NULL);
    			}
    			
    		}
    		
    		
    	}
    }

  5. #5
    EDL
    EDL is offline
    Registered User
    Join Date
    May 2002
    Posts
    18
    Ok, I think I got it working now. In case anyone wants to see what seems to be working code, here it is:

    Code:
    void compclass::addstudent(char tname[]) {
    	student *newstud = new student;
    	student *head = studentlist;
    	student *tail = studentlist;
    	
    	
    	if (studentlist != NULL) {
    		tail = studentlist->retnext();
    	}
    	newstud->setname(tname);
    	if (studentlist == NULL) {
    		newstud->setnext(NULL);
    		studentlist = newstud;
    		
    		return;
    	}
    	else {
    		if (strcmp(head->retname(), newstud->retname()) > 0) {
    				newstud->setnext(studentlist);
    				studentlist = newstud;
    				return;
    			}
    		if ((strcmp(head->retname(), newstud->retname()) < 0) && (tail == NULL)) {
    			head->setnext(newstud);
    			newstud->setnext(NULL);
    			return;
    		}
    		while (tail != NULL && strcmp("head"->retname(), newstud->retname()) < 0) {
    			if (strcmp(tail->retname(), newstud->retname()) > 0) {
    				newstud->setnext(tail);
    				head->setnext(newstud);
    				return;
    			}
    			tail = tail->retnext();
    			head = head->retnext();
    			if (tail == NULL) {
    				head->setnext(newstud);
    				newstud->setnext(NULL);
    			}
    			
    		}
    		
    		
    	}
    }
    Only one change since my last post, so it may be hard to see, so I put Quotes around the change.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Sorting linked list please help with CODE
    By scarlet00014 in forum C Programming
    Replies: 3
    Last Post: 09-27-2008, 11:24 PM
  2. Replies: 5
    Last Post: 11-04-2006, 05:39 PM
  3. Inserting new nodes in a sorted double linked list
    By carrja99 in forum C++ Programming
    Replies: 2
    Last Post: 03-07-2003, 07:34 AM
  4. sort my linked list alphabetically
    By alfd6z in forum C Programming
    Replies: 2
    Last Post: 12-14-2002, 12:33 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM

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