sorting of a linked list 
Author Message
 sorting of a linked list

Anybbody has an idea why this piece of code works when i enter names in
the order of
anne john etc... but crashes if I enter john anne etc?

I've been trying to figure it out for a few days now and i can't. Any
answers will be very appreciated. Thanks.

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

typedef struct words
  {
                char name[20];
                struct words *next;

  }box;

box *head_list, *current, *previous;
box *new,*dummy;

/*Function to add a word in the list*/

void add (char *name)

 {
        new = ( box *) malloc (sizeof(box)); /*Allocating memory for new
"boxes"*/
        if (new)                       /*Checking if the allocation        */
        printf("Allocation succesful\n");    /*was succesful                  */

        current = head_list;
      strcpy(new->name, name);

        if (head_list ==0)
         {
               head_list = new;
               new->next = 0;
                return;

         }
         else
          {
            previous = current;
            current = head_list;

         while ( current != 0)
           {

              if (strcmp(name, current->name) >= 0)
              {
               previous = current;
            current = current->next;
               }
               else if(strcmp(name, current->name) < 0)
                {
                 previous->next = new;
                 new->next =current;
                 return;
                }

             }
           }

          if (current == 0)
           {

            previous->next = new;
            new->next = 0;
            return;
           }

 }

/*Function to  clear and remove */

 box * remove_item ( box *new)
  {
        box *tempp;
        printf("Element removed is %s\n", new->name);
        tempp = new->next;
        free ( new);
        return tempp;
  }

main()
{

        box * remove_item ( box *new);
        char the_end[] = "done";
        void add (char *name);
        char name[20];

        do
         {
                printf("Enter a name(When done type 'done'):\n");
                scanf("%s", name);
                if ( strcmp(name, the_end) == 0)
                        break;
                add(name);
         }
        while ( strcmp(name, the_end) != 0);

        printf("\n\n");
        dummy = head_list;

        while (head_list != 0)
         {
                printf("%s\n",head_list->name);
               head_list = head_list->next;

         }
        printf("\n\n\n");
        head_list =dummy;
        while (head_list!= 0)
          {
               remove_item(head_list);
                head_list =head_list->next;
          }

Quote:
}

--
Themis Katsianos
Graduate student, Faculty of Music
Mcgill University, Canada

--
Themis Katsianos
Graduate student, Faculty of Music
Mcgill University, Canada



Sat, 25 Jul 1998 03:00:00 GMT  
 sorting of a linked list

Quote:
>Anybbody has an idea why this piece of code works when i enter names in
>the order of
>anne john etc... but crashes if I enter john anne etc?

<snip>

Quote:
>/*Function to add a word in the list*/
>void add (char *name)
> {
>        new = ( box *) malloc (sizeof(box)); /*Allocating memory for new
>"boxes"*/
>        if (new)                       /*Checking if the allocation        */
>        printf("Allocation succesful\n");    /*was succesful                  */
>        current = head_list;
>        strcpy(new->name, name);
>        if (head_list ==0)

I know NULL is (almost?) always defined as 0 but you really should use
NULL here instead of 0. (Just a bit of friendly advice).

Quote:
>         {
>               head_list = new;
>               new->next = 0;
>                return;
>         }
>         else
>          {
>            previous = current;
>            current = head_list;

The last line is not necessary, because current is still equal to
head_list.

Quote:

>         while ( current != 0)
>           {

>              if (strcmp(name, current->name) >= 0)
>              {
>               previous = current;
>            current = current->next;
>               }
>               else if(strcmp(name, current->name) < 0)
>                {
>                 previous->next = new;
>                 new->next =current;
>                 return;
>                }

>             }
>           }

Consider the following scenario:

 head_list
         --->[ 1st elem ]--->NULL

Assume that the name field of this single element is 'anne', and that
we want to add the name 'john'. Since strcmp('john', 'anne')<0 we will
wind up in the 'else if' part of your code. After we execute the
commands 'previous->next=new; new->next=current;' your list will look
like:
                  ________________________________
                 |                                |
 head_list       v                                |
 current --->[ 1st elem ]--->[ 2nd elem (new) ]---
 previous

[Note: head_list, current and previous all point to the first
element.]

An endless loop in your list!!
I will leave it to you to fix this (you've come this far, so I know
that you can :-)
Good luck!

Later,

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
"The Wheel weaves as the Wheel wills." -- R.Jordan, WoT



Sun, 26 Jul 1998 03:00:00 GMT  
 sorting of a linked list

Quote:
(Kelvin Klijnsma) writes:

<snip>
   >        if (head_list ==0)

   I know NULL is (almost?) always defined as 0 but you really should use
   NULL here instead of 0. (Just a bit of friendly advice).

Assuming head_list is a pointer, you are wrong if you think that the
meaning of the above code can change if you replace 0 by NULL. In the
expression head_list == 0, it is 0 that is converted to the same
pointer type, head_list is not converted to an integer.

Irrespective of the representations of null pointer, and definition of
NULL (which need not be `0': it can be ((void*)0) also, for
example. In principle it can be a any compile time constant
expressions, roughly speaking, evaluating to 0, or such cast to
(void*)), a C compiler must convert an integer constant 0 to a null
pointer.

Correct use of NULL never gains you anything except
readability. Incorrect use can result in disasters of course.

Cheers
Tanmoy
--

Tanmoy Bhattacharya O:T-8(MS B285)LANL,NM87545 H:#9,3000,Trinity Drive,NM87544
Others see <gopher://yaleinfo.yale.edu:7700/00/Internet-People/internet-mail>,
<http://alpha.acast.nova.edu/cgi-bin/inmgq.pl>or<ftp://csd4.csd.uwm.edu/pub/
internetwork-mail-guide>. -- <http://nqcd.lanl.gov/people/tanmoy/tanmoy.html>
fax: 1 (505) 665 3003   voice: 1 (505) 665 4733    [ Home: 1 (505) 662 5596 ]



Sun, 26 Jul 1998 03:00:00 GMT  
 sorting of a linked list

Quote:

>Correct use of NULL never gains you anything except
>readability. Incorrect use can result in disasters of course.

^^^^^^^^^^^^ my point exactly 8^)

     ________________________________________________
    |_                                              _|
   (__)              Kelvin Klijnsma               (__)

   (__)   http://www.inter.nl.net/hcc/K.Klijnsma   (__)
    |________________________________________________|



Mon, 27 Jul 1998 03:00:00 GMT  
 sorting of a linked list

Quote:
>Anybbody has an idea why this piece of code works when i enter names in
>the order of
>anne john etc... but crashes if I enter john anne etc?
>I've been trying to figure it out for a few days now and i can't. Any
>answers will be very appreciated. Thanks.
>#include <stdio.h>
>#include <string.h>
>#include <stdlib.h>
>typedef struct words
>  {
>                char name[20];
>                struct words *next;
>  }box;
>box *head_list, *current, *previous;
>box *new,*dummy;
>/*Function to add a word in the list*/
>void add (char *name)
> {
>        new = ( box *) malloc (sizeof(box)); /*Allocating memory for new
>"boxes"*/

when allocating new list nodes, I always use calloc() to insure all
fields (including the "next" field) are initialized to 0 (NULL).

Quote:
>        if (new)                       /*Checking if the allocation        */
>        printf("Allocation succesful\n");    /*was succesful                  */

Ah, but what if the allocation wasn't successful!
I'd suggest:

        if(new==NULL) exit(1);

Quote:
>        current = head_list;

this statement is unnecessary here

Quote:
>      strcpy(new->name, name);

better make sure you don't overrun your array:
e.g.    sprintf(new->name, "%.19s", name);
or      strncpy(new->name, name, 19); new->name[19]=0;
or even better, make box->name a pointer and allocate strlen(name)+1,
then strcpy [or use strdup() if you have it, same thing].
Don't forget to free the string in the "remove_item" function.

Quote:

>        if (head_list ==0)
>         {
>               head_list = new;
>               new->next = 0;
>                return;
>         }
>         else
>         {

since you're doing a return if head_list==NULL, there's no need
for the "else" (and the extra indentation level).

Quote:
>            previous = current;
>            current = head_list;

>         while ( current != 0)
>           {

>              if (strcmp(name, current->name) >= 0)
>              {
>               previous = current;
>            current = current->next;
>               }
>               else if(strcmp(name, current->name) < 0)

superfluous call to strcmp (just "} else {" will do)

Quote:
>                {
>                 previous->next = new;
>                 new->next =current;
>                 return;

Here is your problem.  Think about what will happen if the new
name is alphabetically "smaller" than head_list->name.
Does "head_list" get updated?  Does the new item get inserted
_before_ "head_list"?

Quote:
>                }

>             }
>           }
>          if (current == 0)

condition is always true.

- Show quoted text -

Quote:
>           {

>            previous->next = new;
>            new->next = 0;
>            return;
>           }

> }
>/*Function to  clear and remove */
> box * remove_item ( box *new)
>  {
>        box *tempp;
>        printf("Element removed is %s\n", new->name);
>        tempp = new->next;
>        free ( new);
>        return tempp;
>  }
>main()
>{
>        box * remove_item ( box *new);
>        char the_end[] = "done";
>        void add (char *name);
>        char name[20];
>        do
>         {
>                printf("Enter a name(When done type 'done'):\n");
>                scanf("%s", name);
>                if ( strcmp(name, the_end) == 0)

strcmp(name, "done") would also work.

Quote:
>                        break;
>                add(name);
>         }
>        while ( strcmp(name, the_end) != 0);

superfluous call to strcmp (condition is always true, since you
break out of the loop if it isn't)

Quote:
>        printf("\n\n");
>        dummy = head_list;
>        while (head_list != 0)
>         {
>                printf("%s\n",head_list->name);
>               head_list = head_list->next;
>         }
>        printf("\n\n\n");
>        head_list =dummy;
>        while (head_list!= 0)
>          {
>               remove_item(head_list);
>                head_list =head_list->next;

head_list has already been freed!
Since you were careful enough to have remove_item() return the next
(box *), why not use it?:

        head_list=remove_item(head_list);

As a matter of style: when "looping" through a linked list, one tends
to use a variable like "dummy" (or "t", or "p", or whatever) to do
the actual looping, not the list head pointer itself.  The idiom is
something like:

struct node *list_header; /* might be a global variable */
...
struct node *p; /* should be a local variable */

for(p=list_header; p; p=p->next) {
        /* do stuff with p */

Quote:
}
>          }

>}
>--
>Themis Katsianos
>Graduate student, Faculty of Music
>Mcgill University, Canada

==
Miguel Carrasquer Vidal                     ~ ~
Amsterdam                   _____________  ~ ~

========================== Ce .sig n'est pas une .cig



Tue, 28 Jul 1998 03:00:00 GMT  
 sorting of a linked list

Quote:

>>typedef struct words
>>  {
>>                char name[20];
>>                struct words *next;
>>  }box;
>>box *head_list, *current, *previous;
>>box *new,*dummy;
>>/*Function to add a word in the list*/
>>void add (char *name)
>> {
>>        new = ( box *) malloc (sizeof(box)); /*Allocating memory for new
>>"boxes"*/
>when allocating new list nodes, I always use calloc() to insure all
>fields (including the "next" field) are initialized to 0 (NULL).

Unfortunately, calloc() does not make any such assurance.  Memory
returned from calloc() is initailized to all bits zero, but null
pointers and zero-valued floats need not be all bits zero.

What I do is declare a properly initialized static struct variable
and assign it to the new struct.  Thus, something like:

        void add(char *name)
        {
          static const box init_box = {{'\0'}, NULL};

          new = malloc(sizeof(box));
          *new = init_box;

          /* ... */
        }

--
                Matthew Saltzman
                Clemson University Math Sciences



Wed, 29 Jul 1998 03:00:00 GMT  
 sorting of a linked list

Quote:

>Assume that the name field of this single element is 'anne', and that
>we want to add the name 'john'. Since strcmp('john', 'anne')<0

Given my mental block about "strcmp" I have carefully checked this in
my references.  I am fairly confident now that strcmp("john", "anne")

Quote:
> 0.

==
Miguel Carrasquer Vidal                     ~ ~
Amsterdam                   _____________  ~ ~

========================== Ce .sig n'est pas une .cig



Wed, 29 Jul 1998 03:00:00 GMT  
 sorting of a linked list

Quote:
Carrasquer Vidal) writes:

<snip>
   >        new = ( box *) malloc (sizeof(box)); /*Allocating memory for new
   >"boxes"*/

   when allocating new list nodes, I always use calloc() to insure all
   fields (including the "next" field) are initialized to 0 (NULL).

Well, change your habits when programming portably then :-) calloc does
not gurantee that pointers in the region it allocates are NULL.

calloc guarantees _very little_. You can be guaranteed that all your
character strings are initialized to '\0'; you can probably argue that
all integral valued objects are usually zero ... but that is about
all.

If you need to set a pointer or floating point value to 0, do so
explicitly. I would say that as a first approximation, calloc in a
portable program is a mistake. I have seen it being used correctly: to
initialize a string before strncpy/memcpy; but that use is too subtle
for my taste.

Cheers
Tanmoy
--

Tanmoy Bhattacharya O:T-8(MS B285)LANL,NM87545 H:#9,3000,Trinity Drive,NM87544
Others see <gopher://yaleinfo.yale.edu:7700/00/Internet-People/internet-mail>,
<http://alpha.acast.nova.edu/cgi-bin/inmgq.pl>or<ftp://csd4.csd.uwm.edu/pub/
internetwork-mail-guide>. -- <http://nqcd.lanl.gov/people/tanmoy/tanmoy.html>
fax: 1 (505) 665 3003   voice: 1 (505) 665 4733    [ Home: 1 (505) 662 5596 ]



Wed, 29 Jul 1998 03:00:00 GMT  
 sorting of a linked list


 > > {
 > >        new = ( box *) malloc (sizeof(box)); /*Allocating memory for new
 > >"boxes"*/
 >
 > when allocating new list nodes, I always use calloc() to insure all
 > fields (including the "next" field) are initialized to 0 (NULL).

This is one thing it does not ensure. There is no guarantee that 'all
bits zero' represents a null pointer (or a zero values floating point
number for that matter). You're only guaranteed that integers are 0. So
even if you use calloc always assign NULL explicitly if a null pointer
is wanted.

--
-----------------------------------------


-----------------------------------------



Wed, 29 Jul 1998 03:00:00 GMT  
 sorting of a linked list
Sorting a linked list is about like trying to rearrange
knots on a piece of string.  


Wed, 05 Aug 1998 03:00:00 GMT  
 sorting of a linked list


 > Sorting a linked list is about like trying to rearrange
 > knots on a piece of string.  

The natural 'efficient' way to sort linked lists is a list merge sort.
Perhaps you could explain how your statement may be applied to this? :-)

--
-----------------------------------------


-----------------------------------------



Sun, 09 Aug 1998 03:00:00 GMT  
 
 [ 11 post ] 

 Relevant Pages 

1. basic sort for singly linked list...

2. insertion sort algorithm on linked list?

3. Sorting a double linked list

4. Generic sort routine for linked lists

5. : Insertion sort with doubly linked lists

6. sorting a double link list

7. link list of a linked list (chained links?)

8. Link-list sort algorithm question

9. deleting and sorting items in a linked list

10. Linked List Sort/Search/delete code ??Help????

11. Linked list sorting...

12. quick-sorting a linked list?

 

 
Powered by phpBB® Forum Software