Link list sort no work.

This is a discussion on Link list sort no work. within the C++ Programming forums, part of the General Programming Boards category; I have rewritten my sort numerous times, but it doesn't work. can anybody see why. I've asked this question numerous ...

  1. #1
    essence of digital xddxogm3's Avatar
    Join Date
    Sep 2003
    Posts
    589

    Question Link list sort no work.

    I have rewritten my sort numerous times, but it doesn't work.
    can anybody see why. I've asked this question numerous times, but noone has been able to point me in the correct direction. This below is my newest revision, but it still doesn't work. It hangs. I believe it hangs due to the red location.
    prior thread on this question

    Code:
     
    	void linklist::orderedlist(linklist *list)
    	{  
    		initializeData();
    
    		list->current=list->head;
    
    		while (list->current != NULL)  
    		{		
    			current = previous = head;
    
    			link* newlink = new link;
    
    			 strcpy(newlink->fname,list->current->fname); //hangs after this change was made.
    			strcpy(newlink->lname,list->current->lname); 
    			strcpy(newlink->ssnumber,list->current->ssnumber);
    			newlink->age=list->current->age;
    			newlink->weight=list->current->weight;
    
    			newlink->next = NULL;
    
    			if (head == NULL) //this tells me I have an empty list
    			{
    				head = newlink;
    				tail = head;
    			}
    			else
    			{
    				//find the position to insert it
    				while ( strcmp(current->lname,buffer2)==1 && current->next !=NULL)
    				{
    					previous = current;
    					current = current->next;
    				}
    
    				if (current==head)//it will become the new head
    				{
    					newlink->next=head;
    					head=newlink;
    				}
    				else
    				{
    					if (current->next==NULL)//becomes the new tail
    					{
    						tail->next=newlink;
    						tail = newlink;
    					}
    					else
    					{
    						previous->next=newlink;
    						newlink->next=current;
    					}
    				}
    			}
    		}
    	}
    Attached Files Attached Files
    Last edited by xviddivxoggmp3; 10-13-2003 at 11:57 PM.
    "Hence to fight and conquer in all your battles is not supreme excellence;
    supreme excellence consists in breaking the enemy's resistance without fighting."
    Art of War Sun Tzu

  2. #2
    Registered User jlou's Avatar
    Join Date
    Jul 2003
    Posts
    1,088
    Here's a few things I've noticed:
    1. Your c style strings have a size of SIZE. That means that array indexes 0 through SIZE-1 are valid. In all your initialization code, you set buffer[SIZE] = '\0', which is writing to memory off the end of the array. You should declare you char arrays to be size SIZE+1, or always set SIZE-1 to null. (Note: when I initialize char arrays to null, I just use memset to set the entire thing to 0).
    2. In your orderedList method, you never change list->current, so it goes into an infinite loop. Are you supposed to be setting list->current to list->current->next after each pass through the loop?
    3. I don't remember any of your other posts, so I don't know if anybody has mentioned it, but you should probably learn the standard string class. If this is for an assignment and you aren't allowed to use it, that sucks for you, but you should still learn on your own when you get a chance.
    4. Again, you might have heard this over and over, but why do you use <iostream.h> and void main()? Both are wrong.
    Anyway, hope that helps you a bit.

  3. #3
    essence of digital xddxogm3's Avatar
    Join Date
    Sep 2003
    Posts
    589
    Thanks for the response.
    Your c style strings have a size of SIZE. That means that array indexes 0 through SIZE-1 are valid. In all your initialization code, you set buffer[SIZE] = '\0', which is writing to memory off the end of the array. You should declare you char arrays to be size SIZE+1, or always set SIZE-1 to null. (Note: when I initialize char arrays to null, I just use memset to set the entire thing to 0).
    Doesn't the below code initialize all locations of the array to '\0'?
    Code:
     
    		buffer1[SIZE]='\0';
    And what does memset do? I have never seen that before.
    In your orderedList method, you never change list->current, so it goes into an infinite loop. Are you supposed to be setting list->current to list->current->next after each pass through the loop?
    Thanks I fixed that and it at least merges the lists now, but still the sort doesn't work.
    I don't remember any of your other posts, so I don't know if anybody has mentioned it, but you should probably learn the standard string class. If this is for an assignment and you aren't allowed to use it, that sucks for you, but you should still learn on your own when you get a chance.
    My teacher has never shown us how to use these. My books do not state anything of relivence on this. And what I've read from the below url has shown me nothing but compile errors. Do you know of another location for beginer details on string classes?
    ANSI string class
    Again, you might have heard this over and over, but why do you use <iostream.h> and void main()? Both are wrong.
    I have never been told this before. I thought void main() was ok due to I'm not returning anything. And as for <iostream.h> I have tried to replace it with <iostream> and using namespace std;. That also creates massive amounts of compile errors.
    Last edited by xviddivxoggmp3; 10-14-2003 at 09:02 PM.
    "Hence to fight and conquer in all your battles is not supreme excellence;
    supreme excellence consists in breaking the enemy's resistance without fighting."
    Art of War Sun Tzu

  4. #4
    Registered User jlou's Avatar
    Join Date
    Jul 2003
    Posts
    1,088
    Originally posted by xviddivxoggmp3
    Doesn't the below code initialize all locations of the array to '\0'?
    Code:
    		buffer1[SIZE]='\0';
    No. In your case SIZE = 81. Also, buffer1 is declared as char buffer1[SIZE], which means buffer1 is declared as an array of 81 chars. An array is indexed starting from 0, so the indexes 0 through 80 are valid indexes to that array (0 through 80 totals 81 separate indexes).

    So what that code is doing is setting buffer1[81] = '\0'. In other words it is setting the char at index 81 to the character '\0'. Other than the fact that 81 is out of bounds of your array, it is similar to buffer1[13] = 'a'. You are just setting one of the chars in the array. The other chars are still uninitialized.

    I'd try: memset(buffer1, '\0', SIZE);

    The string class in that link does look like the one I would recommend learning. To me, it is easier to use and much more difficult to screw up (like you accidentally did above) than char array style strings.

    As for <iostream.h>, it is difficult sometimes to get <iostream> to work when you aren't used to it. I think its more important right now for you to work on fixing your program, but I would try to use it for your next program from the beginning.

    And I say void main() is wrong only because the creator of C++ says that it is wrong. It works on some compilers, but you should just change it to int main() and put return 0; at the end if you don't like the compiler warnings.

  5. #5
    carry on JaWiB's Avatar
    Join Date
    Feb 2003
    Location
    Seattle, WA
    Posts
    1,972
    Code:
    while ( strcmp(current->lname,buffer2)==1 && current->next !=NULL)
    Hm, doesn't strcmp have more than 2 return values? I thought there was one for equality, one for greater than and one for less than?
    "Think not but that I know these things; or think
    I know them not: not therefore am I short
    Of knowing what I ought."
    -John Milton, Paradise Regained (1671)

    "Work hard and it might happen."
    -XSquared

  6. #6
    essence of digital xddxogm3's Avatar
    Join Date
    Sep 2003
    Posts
    589
    memset(buffer1, '\0', SIZE);
    Initialization:
    This compiled quite easily, but I'm not sure what it does.
    It looks like a function call with 3 parameters. Is this a string function? If I'm reading this correctly it looks like I'm using memset to initialize buffer1 of size (SIZE) to '\0'. If I'm translating this correctly that means my book is showing me the incorrect way to initialize data. It stated that to initialize data we need only to input it like buffer1[SIZE]='\0'. I have gathered from what you have said that this is incorrect. Before I thought we only had to initialize one location in the array to 0 or '\0' and the remaining will automatically be initialized to that value. Will memset work for other types of arrays? (double, int, float)
    String Class:
    I have had good luck retrying string classes with a fresh program v.s. jumping into the program midway and trying to rewrite it using string classes.
    Code:
    while ( strcmp(current->lname,buffer2)==1 && current->next !=NULL)
    Hm, doesn't strcmp have more than 2 return values? I thought there was one for equality, one for greater than and one for less than?
    Should this matter. My code is only looping to the next time in the list I can input the node. I do not think that this would create an issue. It might if I wanted to catigorize it by first name if the last is the same. What issue do you think this creates? Early exit or no execution?
    Last edited by xviddivxoggmp3; 10-14-2003 at 09:43 PM.
    "Hence to fight and conquer in all your battles is not supreme excellence;
    supreme excellence consists in breaking the enemy's resistance without fighting."
    Art of War Sun Tzu

  7. #7
    carry on JaWiB's Avatar
    Join Date
    Feb 2003
    Location
    Seattle, WA
    Posts
    1,972
    Well, what if it returns -1 (which i think would mean "less than") still the strings are not equal. I wasn't really looking at what you wanted to do, but if you are trying to loop while the two strings are not equal then it might not always work...You could do:

    while( (!strcmp(current->lname,buffer2)) && current->next != NULL)

    It looks like a function call with 3 parameters. Is this a string function? If I'm reading this correctly it looks like I'm using memset to initialize buffer1 of size (SIZE) to '\0'. If I'm translating this correctly that means my book is showing me the incorrect way to initialize data.
    All correct, unless you are misreading your book, memset sets every element of the array to whatever you specified by the second parameter (in this case '\0')


    It stated that to initialize data we need only to input it like buffer1[SIZE]='\0'. I have gathered from what you have said that this is incorrect. Before I thought we only had to initialize one location in the array to 0 or '\0' and the remaining will automatically be initialized to that value.
    Initializing buffer1[SIZE] will only initialize element SIZE, so if SIZE == 50 then you are changing buffer1[50] to '\0', but not the rest of the array.


    Will memset work for other types of arrays? (double, int, float)
    Yes, it takes a void pointer (void*) as its first argument
    "Think not but that I know these things; or think
    I know them not: not therefore am I short
    Of knowing what I ought."
    -John Milton, Paradise Regained (1671)

    "Work hard and it might happen."
    -XSquared

  8. #8
    Registered User jlou's Avatar
    Join Date
    Jul 2003
    Posts
    1,088
    You don't need to use the memset thing if you aren't familiar with it. That's not really important, its just another way to do it. Mostly, I want you to understand that:

    buffer1[SIZE]='\0';

    could cause crashes in your program. Change it to:

    buffer1[SIZE-1]='\0';

    Let me know if you still aren't sure why that change is necessary (I kinda explained it already but I know my explanations are confusing ).

    As far as the strcmp problem, it appears you are wanting to sort, so you are correct in checking it for a positive value. Don't change it. (Ok, maybe change it to > 0 instead of == 1).

  9. #9
    essence of digital xddxogm3's Avatar
    Join Date
    Sep 2003
    Posts
    589
    I understand why. My book is misleading.
    Deitel and Deitel C++ How to program Third Edition.
    I made the appropriate changes and they took to the program quite easily. I'm still at the same location for the sorted link list.
    My code still only merges, but doesn't create it sorted. It will create a fresh list sorted, but not when I'm combining 2 already built lists.
    "Hence to fight and conquer in all your battles is not supreme excellence;
    supreme excellence consists in breaking the enemy's resistance without fighting."
    Art of War Sun Tzu

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 26
    Last Post: 07-05-2010, 11:43 AM
  2. Need help sorting a linked list. Beginner
    By scarlet00014 in forum C Programming
    Replies: 1
    Last Post: 09-27-2008, 07:16 PM
  3. help! Placement of nodes in a Linked List
    By lostmyshadow in forum C Programming
    Replies: 6
    Last Post: 12-17-2007, 01:21 PM
  4. Replies: 6
    Last Post: 03-02-2005, 02:45 AM
  5. How can I traverse a huffman tree
    By carrja99 in forum C++ Programming
    Replies: 3
    Last Post: 04-28-2003, 06:46 PM

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