Alphabetical Linked List Insertion

This is a discussion on Alphabetical Linked List Insertion within the C Programming forums, part of the General Programming Boards category; Hey guys, I'm trying to figure out what's wrong with my code. The goal here is to insert linked list ...

  1. #1
    Registered User
    Join Date
    Feb 2010
    Posts
    20

    Alphabetical Linked List Insertion

    Hey guys, I'm trying to figure out what's wrong with my code. The goal here is to insert linked list entries alphabetically. The basic construct of this program is as follows: You start off with a base list of nodes called p2d nodes (they are brought in automatically through the command line). These nodes are connected to one another vertically. From each one of these base nodes extends another linked list in a horizontal direction (conceptually that is). These horizontal nodes are called p1d nodes. These p1d nodes are the ones I'm trying to insert alphabetically. The variable "first" represents the first horizontal p1d attached to the vertical p2d node. Here is the code segment of interest:

    Code:
    if(p2d->first==NULL){
               p2d->first=p1d;
    	   }
    	   else{
    		while(strcmp(p2d->first->name, p1d->name) != 1){
    			p2d->first=p2d->first->next;
    		}
    			p1d->next= p2d ->first;
    			p2d->first = p1d;
    						
    	 }

  2. #2
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,293
    Have you considered what happens if the item to insert is less/greater than all other items?
    Running off the end of a list isn't pretty...
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  3. #3
    CSharpener vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,471
    who said that strcmp returns 1? read the manual
    The first 90% of a project takes 90% of the time,
    the last 10% takes the other 90% of the time.

  4. #4
    Registered User
    Join Date
    Nov 2009
    Location
    Italy
    Posts
    65
    you must consider that strcmp() returns a value greater than 0 if the second string is greater (aphabetically) than the first, 0 if they are equal and a value less than 0 otherwise, plus I suggest to use a binary search tree to do this kind of thing, since the use of strcmp at every iteration is quite a waste of space

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,293
    Quote Originally Posted by rob90 View Post
    you must consider that strcmp() returns a value greater than 0 if the second string is greater (aphabetically) than the first, 0 if they are equal and a value less than 0 otherwise, plus I suggest to use a binary search tree to do this kind of thing, since the use of strcmp at every iteration is quite a waste of space
    Well you had it right up to the word "otherwise".
    But then I kept reading and found that you'd suggested a binary search on a linked-list (which is a no-no). Then you suggested that using strcmp repeatedly wastes space, which makes no sense at all, as the amount of space required for iteratively searching a list, or using strcmp, is constant.

    I think we're waiting to hear back from the OP now.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  6. #6
    Registered User
    Join Date
    Nov 2009
    Location
    Italy
    Posts
    65
    Quote Originally Posted by iMalc View Post
    Well you had it right up to the word "otherwise".
    But then I kept reading and found that you'd suggested a binary search on a linked-list (which is a no-no). Then you suggested that using strcmp repeatedly wastes space, which makes no sense at all, as the amount of space required for iteratively searching a list, or using strcmp, is constant.

    I think we're waiting to hear back from the OP now.
    Yes you're right, I have expressed myself wrong (I'm not english), what I'm suggesting is to insert each string into a binary search tree which is lg(N) on the average case, instead of making an insertion sort into a singly linked list, I'd make something like:

    Code:
    struct node* sorted_insert(struct node* node, char* string)
    {
    if(node == NULL) return newNode(string);
    else {
    if(strcmp(string, node->string) <= 0) node->left = sorted_insert(node->left, string);
    else node->right = sorted_insert(node->right, string);
    }
    Isn't it better than doing an insertion sort into a singly linked list?

  7. #7
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,293
    Oh yes, inserting into a tree is certainly better in the long run, but I don't know if the OP has this as an option.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Problem using strcmp and strlen in a Linked List
    By matrixx333 in forum C Programming
    Replies: 4
    Last Post: 11-23-2009, 03:13 AM
  2. help! Placement of nodes in a Linked List
    By lostmyshadow in forum C Programming
    Replies: 6
    Last Post: 12-17-2007, 12:21 PM
  3. Help with Insertion sort on a single linked list
    By goron350 in forum C++ Programming
    Replies: 4
    Last Post: 07-11-2005, 08:38 PM
  4. problem with structures and linked list
    By Gkitty in forum C Programming
    Replies: 6
    Last Post: 12-12-2002, 05:40 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