dev-cpp-users

[Dev-C++] Single Linked List-IV

[<and...@su...>]

Dear users,
   Please consider this (modificated) Single Linked List Code:


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

#define MAX 5

struct address
{
   char name[40];
   char phone[20];
   struct address *next;
};

void slstore(struct address *, struct address **, struct address **);
void display(struct address *);
void list(struct address **);
void init(struct address **);

int main()
{
   struct address *info=NULL, *start=NULL, *last=NULL;
   int i;

   for(i=0; i<MAX; i++)
   {
      init(&info);
      printf("Enter name: ");
      gets(info->name);
      printf("Entre com phone: ");
      gets(info->phone);
      slstore(info, &start, &last);
   }
   printf("List Recorded:\n");
   list(&start);
   while (start)
   {
      info = start;
      start = start->next;
      free(info);
   }
   system("PAUSE");
   return(0);
}

void slstore(struct address *i, struct address **start_arg,
             struct address **last_arg)
{
   if(*last_arg==NULL) *start_arg=i;
   else (*last_arg)->next=i;
   i->next=NULL;
   *last_arg=i;
}

void display(struct address *info)
{
   printf("Actual address-->%p\n", info);
   printf("%s\n", info->name);
   printf("%s\n", info->phone);
   printf("Next address-->%p\n", info->next);
   printf("\n");
   system("PAUSE");
}

void list(struct address **start_arg)
{
   struct address *info;

   init(&info);
   info = *start_arg;
   while(info)
   {
      display(info);
      info = info->next;
   }
}

void init(struct address **arg)
{
   *arg= malloc(1*sizeof(struct address));
   if(!(*arg))
   {
      printf("sem memória\n");
      system("PAUSE");
      exit(EXIT_FAILURE);
   }
}

==>My questions:
A) One example of addresses that are printed on the screen are:
   002224C8
   00222510
   00222558
   002225A0
   002225E8
   The distance between theese addresses is 72 bytes, not 64 as expected
   because the size of the struct address.
   WHY?

B) Could the final loop:
   while (start)
   {
      info = start;
      start = start->next;
      free(info);
   }
   be changed by a function call for a function like

   free_ptr(&start);

   void free_ptr(struct address **arg)
   {
      struct address *info=NULL;

      while (*arg)
      {
         info = *arg;
         *arg = (*arg)->next;
         free(info);
      }
   }

Thanks
Andre

Re: [Dev-C++] Single Linked List-IV

[Per W. <pw...@ia...>]

On Fri, 6 Jun 2003, Andr=E9 Mac=E1rio Barros wrote:

> Dear users,
>    Please consider this (modificated) Single Linked List Code:
>
>
> #include <stdio.h>
> #include <stdlib.h>
>
> #define MAX 5
>
> struct address
> {
>    char name[40];
>    char phone[20];
>    struct address *next;
> };
>
> void slstore(struct address *, struct address **, struct address **);
> void display(struct address *);
> void list(struct address **);
> void init(struct address **);
>
> int main()
> {
>    struct address *info=3DNULL, *start=3DNULL, *last=3DNULL;
>    int i;
>
>    for(i=3D0; i<MAX; i++)
>    {
>       init(&info);
>       printf("Enter name: ");
>       gets(info->name);
>       printf("Entre com phone: ");
>       gets(info->phone);
>       slstore(info, &start, &last);
>    }
>    printf("List Recorded:\n");
>    list(&start);
>    while (start)
>    {
>       info =3D start;
>       start =3D start->next;
>       free(info);
>    }
>    system("PAUSE");
>    return(0);
> }
>
> void slstore(struct address *i, struct address **start_arg,
>              struct address **last_arg)
> {
}
>    if(*last_arg=3D=3DNULL) *start_arg=3Di;
>    else (*last_arg)->next=3Di;
>    i->next=3DNULL;
>    *last_arg=3Di;
> }
>
> void display(struct address *info)
> {
>    printf("Actual address-->%p\n", info);
>    printf("%s\n", info->name);
>    printf("%s\n", info->phone);
>    printf("Next address-->%p\n", info->next);
>    printf("\n");
>    system("PAUSE");
> }
>
> void list(struct address **start_arg)
> {
>    struct address *info;
>
PWM: Don't allocate any info - the list already contains the entries, and
PWM: you only want to use info as a pointer poiting to the entries
PWM: available in  the list.
PWM: Remove this line.>    init(&info);
>    info =3D *start_arg;
>    while(info)
>    {
>       display(info);
>       info =3D info->next;
>    }
> }
>
> void init(struct address **arg)
> {
>    *arg=3D malloc(1*sizeof(struct address));
>    if(!(*arg))
>    {
>       printf("sem mem=F3ria\n");
>       system("PAUSE");
>       exit(EXIT_FAILURE);
>    }
> }
>
> =3D=3D>My questions:
> A) One example of addresses that are printed on the screen are:
>    002224C8
>    00222510
>    00222558
>    002225A0
>    002225E8
>    The distance between theese addresses is 72 bytes, not 64 as expected
>    because the size of the struct address.
>    WHY?

PWM: Because the memory library have to allocate some extra space for
book-keeping. Normally malloc() will store the size of the memory block (4
byte) and a pointer to the previously allocated block (4 byte).

>
> B) Could the final loop:
>    while (start)
>    {
>       info =3D start;
>       start =3D start->next;
>       free(info);
>    }
>    be changed by a function call for a function like
>
>    free_ptr(&start);
>
>    void free_ptr(struct address **arg)
>    {
>       struct address *info=3DNULL;
>
>       while (*arg)
>       {
>          info =3D *arg;
>          *arg =3D (*arg)->next;
>          free(info);
>       }
>    }
PWM: Yes, but you might consider adding a line
PWM: *arg =3D NULL;
PWM: to make sure that the caller knows that start doesn't point to any
PWM: elements anymore.

>
> Thanks
> Andre
>
>
>
>
>
> -------------------------------------------------------
> This SF.net email is sponsored by:  Etnus, makers of TotalView, The best
> thread debugger on the planet. Designed with thread debugging features
> you've never dreamed of, try TotalView 6 free at www.etnus.com.
> _______________________________________________
> Dev-cpp-users mailing list
> Dev...@li...
> TO UNSUBSCRIBE: http://www.noicys.cjb.net/devcpp/ub.htm
> https://lists.sourceforge.net/lists/listinfo/dev-cpp-users
>

RES: [Dev-C++] Single Linked List-IV

[<and...@su...>]

Crucial help!!!
Terrific!

Thank you
André

-----Mensagem original-----
De: Per Westermark [mailto:pw...@ia...]
Enviada em: sexta-feira, 6 de junho de 2003 09:44
Para: André Macário Barros
Cc: Dev-Cpp-Users
Assunto: Re: [Dev-C++] Single Linked List-IV




On Fri, 6 Jun 2003, André Macário Barros wrote:

> Dear users,
>    Please consider this (modificated) Single Linked List Code:
>
>
> #include <stdio.h>
> #include <stdlib.h>
>
> #define MAX 5
>
> struct address
> {
>    char name[40];
>    char phone[20];
>    struct address *next;
> };
>
> void slstore(struct address *, struct address **, struct address **);
> void display(struct address *);
> void list(struct address **);
> void init(struct address **);
>
> int main()
> {
>    struct address *info=NULL, *start=NULL, *last=NULL;
>    int i;
>
>    for(i=0; i<MAX; i++)
>    {
>       init(&info);
>       printf("Enter name: ");
>       gets(info->name);
>       printf("Entre com phone: ");
>       gets(info->phone);
>       slstore(info, &start, &last);
>    }
>    printf("List Recorded:\n");
>    list(&start);
>    while (start)
>    {
>       info = start;
>       start = start->next;
>       free(info);
>    }
>    system("PAUSE");
>    return(0);
> }
>
> void slstore(struct address *i, struct address **start_arg,
>              struct address **last_arg)
> {
}
>    if(*last_arg==NULL) *start_arg=i;
>    else (*last_arg)->next=i;
>    i->next=NULL;
>    *last_arg=i;
> }
>
> void display(struct address *info)
> {
>    printf("Actual address-->%p\n", info);
>    printf("%s\n", info->name);
>    printf("%s\n", info->phone);
>    printf("Next address-->%p\n", info->next);
>    printf("\n");
>    system("PAUSE");
> }
>
> void list(struct address **start_arg)
> {
>    struct address *info;
>
PWM: Don't allocate any info - the list already contains the entries, and
PWM: you only want to use info as a pointer poiting to the entries
PWM: available in  the list.
PWM: Remove this line.>    init(&info);
>    info = *start_arg;
>    while(info)
>    {
>       display(info);
>       info = info->next;
>    }
> }
>
> void init(struct address **arg)
> {
>    *arg= malloc(1*sizeof(struct address));
>    if(!(*arg))
>    {
>       printf("sem memória\n");
>       system("PAUSE");
>       exit(EXIT_FAILURE);
>    }
> }
>
> ==>My questions:
> A) One example of addresses that are printed on the screen are:
>    002224C8
>    00222510
>    00222558
>    002225A0
>    002225E8
>    The distance between theese addresses is 72 bytes, not 64 as expected
>    because the size of the struct address.
>    WHY?

PWM: Because the memory library have to allocate some extra space for
book-keeping. Normally malloc() will store the size of the memory block (4
byte) and a pointer to the previously allocated block (4 byte).

>
> B) Could the final loop:
>    while (start)
>    {
>       info = start;
>       start = start->next;
>       free(info);
>    }
>    be changed by a function call for a function like
>
>    free_ptr(&start);
>
>    void free_ptr(struct address **arg)
>    {
>       struct address *info=NULL;
>
>       while (*arg)
>       {
>          info = *arg;
>          *arg = (*arg)->next;
>          free(info);
>       }
>    }
PWM: Yes, but you might consider adding a line
PWM: *arg = NULL;
PWM: to make sure that the caller knows that start doesn't point to any
PWM: elements anymore.

>
> Thanks
> Andre
>
>
>
>
>
> -------------------------------------------------------
> This SF.net email is sponsored by:  Etnus, makers of TotalView, The best
> thread debugger on the planet. Designed with thread debugging features
> you've never dreamed of, try TotalView 6 free at www.etnus.com.
> _______________________________________________
> Dev-cpp-users mailing list
> Dev...@li...
> TO UNSUBSCRIBE: http://www.noicys.cjb.net/devcpp/ub.htm
> https://lists.sourceforge.net/lists/listinfo/dev-cpp-users
>

RE: [Dev-C++] Single Linked List-IV

[Ioannis V. <iv...@em...>]

> -----Original Message-----
> From: dev...@li...=20
> [mailto:dev...@li...] On Behalf=20
> Of Andr? Macario Barros
> Sent: Friday, June 06, 2003 3:16 PM
> To: Dev-Cpp-Users
> Subject: [Dev-C++] Single Linked List-IV
>=20
>=20
> Dear users,
>    Please consider this (modificated) Single Linked List Code:
>=20
>=20
> #include <stdio.h>
> #include <stdlib.h>
>=20
> #define MAX 5
>=20
> struct address
> {
>    char name[40];
>    char phone[20];
>    struct address *next;
> };
>=20
> void slstore(struct address *, struct address **, struct address **);
> void display(struct address *);
> void list(struct address **);
> void init(struct address **);
>=20
> int main()
> {
>    struct address *info=3DNULL, *start=3DNULL, *last=3DNULL;
>    int i;
>=20
>    for(i=3D0; i<MAX; i++)
>    {
>       init(&info);
>       printf("Enter name: ");
>       gets(info->name);


Dangerous, you can't expect the user to know the internals of your code =
and
limit himself to 39 characters. Use fgets() instead. Avoid gets() in
general.

fgets(info->name, 40, stdin);


>       printf("Entre com phone: ");
>       gets(info->phone);


fgets(info->phone, 20, stdin);


>       slstore(info, &start, &last);
>    }
>    printf("List Recorded:\n");
>    list(&start);
>    while (start)
>    {
>       info =3D start;
>       start =3D start->next;
>       free(info);
>    }
>    system("PAUSE");
>    return(0);
> }
>=20
> void slstore(struct address *i, struct address **start_arg,
>              struct address **last_arg)
> {
>    if(*last_arg=3D=3DNULL)
           *start_arg=3Di;
>    else
           (*last_arg)->next=3Di;

>    i->next=3DNULL;
>    *last_arg=3Di;
> }


I made the above more readable so as to understand it. Why do you use =
struct
**s and not struct *s and avoid those *s?

I cannot understand the last line, it seems to contradict with the else
statement at least. I suspect a bug here. Ommiting the last line it =
becomes:

void slstore(struct address *i, struct address *start_arg,
             struct address *last_arg)
{
   if(last_arg=3D=3DNULL)=20
      start_arg=3Di;
  =20
    else
        last_arg->next=3Di;
  =20
   i->next=3DNULL;
}



>=20
> void display(struct address *info)
> {
>    printf("Actual address-->%p\n", info);

When you pass a different pointer than expected in a variadic function =
you
must cast:

printf("Actual address-->%p\n", (void *)info);




>    printf("%s\n", info->name);
>    printf("%s\n", info->phone);
>    printf("Next address-->%p\n", info->next);


printf("Next address-->%p\n", (void *) info->next);


>    printf("\n");
>    system("PAUSE");
> }
>=20
> void list(struct address **start_arg)
> {
>    struct address *info;
>=20
>    init(&info);
>    info =3D *start_arg;
>    while(info)
>    {
>       display(info);
>       info =3D info->next;
>    }
> }


You use **s while they are not needed in the whole program.




> void init(struct address **arg)
> {
>    *arg=3D malloc(1*sizeof(struct address));
>    if(!(*arg))
>    {
>       printf("sem mem=F3ria\n");
>       system("PAUSE");
>       exit(EXIT_FAILURE);
>    }
> }


The same here. Without **s:


void init(struct address *arg)
{
   arg=3D malloc(sizeof(*arg));

   if(!arg)
   {
      printf("He was a good man, always to remember him\n");
      system("PAUSE");
      exit(EXIT_FAILURE);
   }
}


> =3D=3D>My questions:
> A) One example of addresses that are printed on the screen are:
>    002224C8
>    00222510
>    00222558
>    002225A0
>    002225E8
>    The distance between theese addresses is 72 bytes, not 64=20
> as expected
>    because the size of the struct address.
>    WHY?



If I recall correctly you create them on the free store, so their =
address
can be anywhere.





>=20
> B) Could the final loop:
>    while (start)
>    {
>       info =3D start;
>       start =3D start->next;
>       free(info);
>    }
>    be changed by a function call for a function like
>=20
>    free_ptr(&start);
>=20
>    void free_ptr(struct address **arg)
>    {
>       struct address *info=3DNULL;
>=20
>       while (*arg)
>       {
>          info =3D *arg;
>          *arg =3D (*arg)->next;
>          free(info);
>       }
>    }


Yes, isn't it exactly the same with the unneeded use of **s? Better:


void free_ptr(struct address *arg)
{
    struct address *info;
=20
    while (arg)
    {
       info =3D arg;
       arg =3D arg->next;
       free(info);
    }
}






Ioannis Vranos
=20
* Programming pages: http://www.noicys.freeurl.com
* Alternative URL 1: http://run.to/noicys
* Alternative URL 2: http://www.noicys.cjb.net

RE: [Dev-C++] Single Linked List-IV

[Per W. <pw...@ia...>]

The slstore() function DOES need it's last line, or else the list will not
get a pointer to the last element. The pointer to the last element is used
to allow insert of new elements last, without having to iterate throught
the list.

I know it's a bit extra noisy with dual indirection, but since the code
is C and not C++, slstore() can't take references to pointers.

/Per W

On Sat, 7 Jun 2003, Ioannis Vranos wrote:

> > -----Original Message-----
> > From: dev...@li...
> > [mailto:dev...@li...] On Behalf
> > Of Andr? Macario Barros
> > Sent: Friday, June 06, 2003 3:16 PM
> > To: Dev-Cpp-Users
> > Subject: [Dev-C++] Single Linked List-IV
> >
> >
> > Dear users,
> >    Please consider this (modificated) Single Linked List Code:
> >
> >
> > #include <stdio.h>
> > #include <stdlib.h>
> >
> > #define MAX 5
> >
> > struct address
> > {
> >    char name[40];
> >    char phone[20];
> >    struct address *next;
> > };
> >
> > void slstore(struct address *, struct address **, struct address **);
> > void display(struct address *);
> > void list(struct address **);
> > void init(struct address **);
> >
> > int main()
> > {
> >    struct address *info=3DNULL, *start=3DNULL, *last=3DNULL;
> >    int i;
> >
> >    for(i=3D0; i<MAX; i++)
> >    {
> >       init(&info);
> >       printf("Enter name: ");
> >       gets(info->name);
>
>
> Dangerous, you can't expect the user to know the internals of your code a=
nd
> limit himself to 39 characters. Use fgets() instead. Avoid gets() in
> general.
>
> fgets(info->name, 40, stdin);
>
>
> >       printf("Entre com phone: ");
> >       gets(info->phone);
>
>
> fgets(info->phone, 20, stdin);
>
>
> >       slstore(info, &start, &last);
> >    }
> >    printf("List Recorded:\n");
> >    list(&start);
> >    while (start)
> >    {
> >       info =3D start;
> >       start =3D start->next;
> >       free(info);
> >    }
> >    system("PAUSE");
> >    return(0);
> > }
> >
> > void slstore(struct address *i, struct address **start_arg,
> >              struct address **last_arg)
> > {
> >    if(*last_arg=3D=3DNULL)
>            *start_arg=3Di;
> >    else
>            (*last_arg)->next=3Di;
>
> >    i->next=3DNULL;
> >    *last_arg=3Di;
> > }
>
>
> I made the above more readable so as to understand it. Why do you use str=
uct
> **s and not struct *s and avoid those *s?
>
> I cannot understand the last line, it seems to contradict with the else
> statement at least. I suspect a bug here. Ommiting the last line it becom=
es:
>
> void slstore(struct address *i, struct address *start_arg,
>              struct address *last_arg)
> {
>    if(last_arg=3D=3DNULL)
>       start_arg=3Di;
>
>     else
>         last_arg->next=3Di;
>
>    i->next=3DNULL;
> }
>
>
>
> >
> > void display(struct address *info)
> > {
> >    printf("Actual address-->%p\n", info);
>
> When you pass a different pointer than expected in a variadic function yo=
u
> must cast:
>
> printf("Actual address-->%p\n", (void *)info);
>
>
>
>
> >    printf("%s\n", info->name);
> >    printf("%s\n", info->phone);
> >    printf("Next address-->%p\n", info->next);
>
>
> printf("Next address-->%p\n", (void *) info->next);
>
>
> >    printf("\n");
> >    system("PAUSE");
> > }
> >
> > void list(struct address **start_arg)
> > {
> >    struct address *info;
> >
> >    init(&info);
> >    info =3D *start_arg;
> >    while(info)
> >    {
> >       display(info);
> >       info =3D info->next;
> >    }
> > }
>
>
> You use **s while they are not needed in the whole program.
>
>
>
>
> > void init(struct address **arg)
> > {
> >    *arg=3D malloc(1*sizeof(struct address));
> >    if(!(*arg))
> >    {
> >       printf("sem mem=F3ria\n");
> >       system("PAUSE");
> >       exit(EXIT_FAILURE);
> >    }
> > }
>
>
> The same here. Without **s:
>
>
> void init(struct address *arg)
> {
>    arg=3D malloc(sizeof(*arg));
>
>    if(!arg)
>    {
>       printf("He was a good man, always to remember him\n");
>       system("PAUSE");
>       exit(EXIT_FAILURE);
>    }
> }
>
>
> > =3D=3D>My questions:
> > A) One example of addresses that are printed on the screen are:
> >    002224C8
> >    00222510
> >    00222558
> >    002225A0
> >    002225E8
> >    The distance between theese addresses is 72 bytes, not 64
> > as expected
> >    because the size of the struct address.
> >    WHY?
>
>
>
> If I recall correctly you create them on the free store, so their address
> can be anywhere.
>
>
>
>
>
> >
> > B) Could the final loop:
> >    while (start)
> >    {
> >       info =3D start;
> >       start =3D start->next;
> >       free(info);
> >    }
> >    be changed by a function call for a function like
> >
> >    free_ptr(&start);
> >
> >    void free_ptr(struct address **arg)
> >    {
> >       struct address *info=3DNULL;
> >
> >       while (*arg)
> >       {
> >          info =3D *arg;
> >          *arg =3D (*arg)->next;
> >          free(info);
> >       }
> >    }
>
>
> Yes, isn't it exactly the same with the unneeded use of **s? Better:
>
>
> void free_ptr(struct address *arg)
> {
>     struct address *info;
>
>     while (arg)
>     {
>        info =3D arg;
>        arg =3D arg->next;
>        free(info);
>     }
> }
>
>
>
>
>
>
> Ioannis Vranos
>
> * Programming pages: http://www.noicys.freeurl.com
> * Alternative URL 1: http://run.to/noicys
> * Alternative URL 2: http://www.noicys.cjb.net
>
>
>
>
> -------------------------------------------------------
> This SF.net email is sponsored by:  Etnus, makers of TotalView, The best
> thread debugger on the planet. Designed with thread debugging features
> you've never dreamed of, try TotalView 6 free at www.etnus.com.
> _______________________________________________
> Dev-cpp-users mailing list
> Dev...@li...
> TO UNSUBSCRIBE: http://www.noicys.cjb.net/devcpp/ub.htm
> https://lists.sourceforge.net/lists/listinfo/dev-cpp-users
>

RE: [Dev-C++] Single Linked List-IV

[Ioannis V. <iv...@em...>]

> -----Original Message-----
> From: Per Westermark [mailto:pw...@ia...] 
> Sent: Saturday, June 07, 2003 10:39 PM
> To: Ioannis Vranos
> Cc: 'Dev-Cpp-Users'
> Subject: RE: [Dev-C++] Single Linked List-IV
> 
> 
> The slstore() function DOES need it's last line, or else the 
> list will not
> get a pointer to the last element. The pointer to the last 
> element is used
> to allow insert of new elements last, without having to 
> iterate throught
> the list.


Perhaps I am missing something but as I understand it the statement

 *last_arg=i;

makes the preceding statement

else
         (*last_arg)->next=i;


redundant.



> 
> I know it's a bit extra noisy with dual indirection, but 
> since the code
> is C and not C++, slstore() can't take references to pointers.


And? double pointers occupy space themselves too.




Ioannis Vranos
 
* Programming pages: http://www.noicys.freeurl.com
* Alternative URL 1: http://run.to/noicys
* Alternative URL 2: http://www.noicys.cjb.net

RE: [Dev-C++] Single Linked List-IV

[Per W. <pw...@ia...>]

If the list is non-empty, then *last is non-NULL. In that case, the OLD
last entry should have it's next pointer pointing at the NEW last entry.

It doesn't matter if the list was empty or not. After an insert - the
insert is always at the end of the list - *last should be set to point to
the NEW last entry. Without this last line, LAST would always be NULL, and
you wouldn't get a linked list.

/Per W

On Sun, 8 Jun 2003, Ioannis Vranos wrote:

> > -----Original Message-----
> > From: Per Westermark [mailto:pw...@ia...]
> > Sent: Saturday, June 07, 2003 10:39 PM
> > To: Ioannis Vranos
> > Cc: 'Dev-Cpp-Users'
> > Subject: RE: [Dev-C++] Single Linked List-IV
> >
> >
> > The slstore() function DOES need it's last line, or else the
> > list will not
> > get a pointer to the last element. The pointer to the last
> > element is used
> > to allow insert of new elements last, without having to
> > iterate throught
> > the list.
>
>
> Perhaps I am missing something but as I understand it the statement
>
>  *last_arg=i;
>
> makes the preceding statement
>
> else
>          (*last_arg)->next=i;
>
>
> redundant.
>
>
>
> >
> > I know it's a bit extra noisy with dual indirection, but
> > since the code
> > is C and not C++, slstore() can't take references to pointers.
>
>
> And? double pointers occupy space themselves too.
>
>
>
>
> Ioannis Vranos
>
> * Programming pages: http://www.noicys.freeurl.com
> * Alternative URL 1: http://run.to/noicys
> * Alternative URL 2: http://www.noicys.cjb.net
>
>
>
>
> -------------------------------------------------------
> This SF.net email is sponsored by:  Etnus, makers of TotalView, The best
> thread debugger on the planet. Designed with thread debugging features
> you've never dreamed of, try TotalView 6 free at www.etnus.com.
> _______________________________________________
> Dev-cpp-users mailing list
> Dev...@li...
> TO UNSUBSCRIBE: http://www.noicys.cjb.net/devcpp/ub.htm
> https://lists.sourceforge.net/lists/listinfo/dev-cpp-users
>

RE: [Dev-C++] Single Linked List-IV

[Ioannis V. <iv...@em...>]

Ok, got it.





Ioannis Vranos
 
* Programming pages: http://www.noicys.freeurl.com
* Alternative URL 1: http://run.to/noicys
* Alternative URL 2: http://www.noicys.cjb.net



> -----Original Message-----
> From: Per Westermark [mailto:pw...@ia...] 
> Sent: Sunday, June 08, 2003 6:39 PM
> To: Ioannis Vranos
> Cc: Dev-C++ Mailing List
> Subject: RE: [Dev-C++] Single Linked List-IV
> 
> 
> If the list is non-empty, then *last is non-NULL. In that 
> case, the OLD
> last entry should have it's next pointer pointing at the NEW 
> last entry.
> 
> It doesn't matter if the list was empty or not. After an insert - the
> insert is always at the end of the list - *last should be set 
> to point to
> the NEW last entry. Without this last line, LAST would always 
> be NULL, and
> you wouldn't get a linked list.

RE: [Dev-C++] Single Linked List-IV

[Per W. <pw...@ia...>]

A variation on the theme is to build the list as a ring. Then you
get:

getfirst() { return last ? last->next : NULL; }
getlast() { return last; }
getnext(ptr) { return ptr == last ? NULL : ptr->next; }

Quick insert both at head and tail, but list only needs one pointter.

/Per W

On Mon, 9 Jun 2003, Ioannis Vranos wrote:

> Ok, got it.
>
>
>
>
>
> Ioannis Vranos
>
> * Programming pages: http://www.noicys.freeurl.com
> * Alternative URL 1: http://run.to/noicys
> * Alternative URL 2: http://www.noicys.cjb.net
>
>
>
> > -----Original Message-----
> > From: Per Westermark [mailto:pw...@ia...]
> > Sent: Sunday, June 08, 2003 6:39 PM
> > To: Ioannis Vranos
> > Cc: Dev-C++ Mailing List
> > Subject: RE: [Dev-C++] Single Linked List-IV
> >
> >
> > If the list is non-empty, then *last is non-NULL. In that
> > case, the OLD
> > last entry should have it's next pointer pointing at the NEW
> > last entry.
> >
> > It doesn't matter if the list was empty or not. After an insert - the
> > insert is always at the end of the list - *last should be set
> > to point to
> > the NEW last entry. Without this last line, LAST would always
> > be NULL, and
> > you wouldn't get a linked list.
>
>
>
>
> -------------------------------------------------------
> This SF.net email is sponsored by:  Etnus, makers of TotalView, The best
> thread debugger on the planet. Designed with thread debugging features
> you've never dreamed of, try TotalView 6 free at www.etnus.com.
> _______________________________________________
> Dev-cpp-users mailing list
> Dev...@li...
> TO UNSUBSCRIBE: http://www.noicys.cjb.net/devcpp/ub.htm
> https://lists.sourceforge.net/lists/listinfo/dev-cpp-users
>

Re: [Dev-C++] Single Linked List-IV

[Luigi S. <gi...@li...>]

On Sat, Jun 07, 2003 at 09:38:34PM +0200, Per Westermark wrote:
> [...]
> 
> I know it's a bit extra noisy with dual indirection, but since the code
> is C and not C++, slstore() can't take references to pointers.
> 
> /Per W

Probably, he could have avoided the double indirection using
something like:

  struct slist
  {
     struct address *start;
     struct address *last;
  };

so that a pointer to "struct slist" would be used, still allowing
all changes to "start" and "last" to be made.

-- 
>> gisan >>

RE: [Dev-C++] Single Linked List-IV

[Ioannis V. <iv...@em...>]

> -----Original Message-----
> From: dev...@li... 
> [mailto:dev...@li...] On Behalf 
> Of Luigi Santillo
> Sent: Sunday, June 08, 2003 9:15 AM
> To: 'Dev-Cpp-Users'
> Subject: Re: [Dev-C++] Single Linked List-IV
> 
> 
> On Sat, Jun 07, 2003 at 09:38:34PM +0200, Per Westermark wrote:
> > [...]
> > 
> > I know it's a bit extra noisy with dual indirection, but 
> since the code
> > is C and not C++, slstore() can't take references to pointers.
> > 
> > /Per W
> 
> Probably, he could have avoided the double indirection using
> something like:
> 
>   struct slist
>   {
>      struct address *start;
>      struct address *last;
>   };
> 
> so that a pointer to "struct slist" would be used, still allowing
> all changes to "start" and "last" to be made.



And why use such tricks in the first place and not single pointers?






Ioannis Vranos
 
* Programming pages: http://www.noicys.freeurl.com
* Alternative URL 1: http://run.to/noicys
* Alternative URL 2: http://www.noicys.cjb.net

Re: [Dev-C++] Single Linked List-IV

[Luigi S. <gi...@li...>]

> > > On Sat, Jun 07, 2003 at 09:38:34PM +0200, Per Westermark wrote:
> > > [...]
> > > 
> > > I know it's a bit extra noisy with dual indirection, but 
> > > since the code
> > > is C and not C++, slstore() can't take references to pointers.
> > > 
> > > /Per W



> > On Sun, June 08, 2003 9:15 AM +0200, Luigi Santillo wrote:
> > Probably, he could have avoided the double indirection using
> > something like:
> > 
> >   struct slist
> >   {
> >      struct address *start;
> >      struct address *last;
> >   };
> > 
> > so that a pointer to "struct slist" would be used, still allowing
> > all changes to "start" and "last" to be made.



> Mon, 9 Jun 2003 06:09:28 +0300 Ioannis Vranos wrote:
> And why use such tricks in the first place and not single pointers?



Well the "trick" I suggest above, reflects my personal C-newbie tastes :-)
I immagine that experienced programmers have more elegant solutions. 

However, allow me to say something about the interface of a list
which, for simplicity, has the following two functions:

 - push_back = append an element
 - pop_front = extract front element

So far, 3 solutions seem to have arisen:

 #1: "dual indirection" proposed by Andre' Macario Barros
 #2: "list structure" (that is, the newbie "trick" suggested by me)
 #3: "single pointers" as I seem to have understood from mail sent 
     by Ioannis Vranos


Here is a possible way the 3 interfaces might look.


--------------- #1: dual indirection ---------------------
#ifndef list_h
#define list_h

struct l_node
{
  void *data;          /* address of item to be stored */
  struct l_node *next; /* next element on the list */
};

/* add data to the back, return 0 if unable to allocate memory for a
   new element, 1 on success */
int
l_push_back(void *data, struct l_node **head_ptr, struct l_node **tail_ptr);


/* pop data from front of a list, return 0 if there is nothing on the
   list or pointer stored on the list */
void *
l_pop_front(struct l_node **head_ptr, struct l_node **tail_ptr);

#endif
--------------- #1: end ----------------------------------



---------------- #2: list structure  ---------------------
#ifndef list_h
#define list_h

struct l_node
{
  void *data;          /* address of item to be stored */
  struct l_node *next; /* next element on the list */
};


struct list
{
  struct l_node *head; /* first node: where pop occurs */
  struct l_node *tail; /* last node: where push occurs */
};


/* add data to the back, return 0 if unable to allocate memory for a
   new element, 1 on success */
int
l_push_back(void *data, struct list *lptr);


/* pop data from front of a list, return 0 if there is nothing on the
   list or pointer stored on the list */
void *
l_pop_front(struct list *lptr);

#endif
---------------- #2: end ---------------------------------



---------------- #3: single pointers ---------------------
#ifndef list_h
#define list_h

struct l_node
{
  void *data;          /* address of item to be stored */
  struct l_node *next; /* next element on the list */
};

/* add data to the back, return 0 if unable to allocate memory for a
   new element, 1 on success */
int
l_push_back(void *data, struct l_node *head, struct l_node *tail);


/* pop data from front of a list, return 0 if there is nothing on the
   list or pointer stored on the list */
void *
l_pop_front(struct l_node *head, struct l_node *tail);

#endif
---------------- #3: end ---------------------------------


It is clear to me that, upon pushing some data on the list, the
"head" might change while the "tail" will surely change; thus:

 - solution proposed by Andre' Macario Barros (dual indirection),
   is correct, in fact passing the address of "head" and "tail"
   allows changes made by function "l_push_back" to be seen outside
   the scope of the function.

 - my "trick" (list structure) is correct too, in fact by passing
   the address of the list structure and modifying "head" and "tail"
   inside function "l_push_back", again changes are seen outside
   the scope of the function.

 - using "single pointers", seems not to be correct, in that changes
   made to "head" and "tail", are changes made to a copy of the pointers
   local to the function "l_push_back", thus the updated values are 
   not seen outside the scope of the function.

Similar reasoning holds for function "l_pop_front". 


For the sake of completeness, here are the 3 implementations which
complete the "list" and which I have used for my simple tests.


---------------- #1: dual indirection --------------------
#include <stdlib.h>
#include "list.h"

/********************************************************************/
int
l_push_back(void *data, struct l_node **head_ptr, struct l_node **tail_ptr)
{
  struct l_node *nptr = malloc(sizeof(struct l_node));

  if (nptr) /* load node and link it */
    {
      nptr->data = data;
      nptr->next = 0; /* new node will be last one */
      
      if (*tail_ptr) /* there is already something */
        (*tail_ptr)->next = nptr;
      else /* first node */
        *head_ptr = nptr;
      
      *tail_ptr = nptr; /* new nodes becomes last one */
      
      return 1;
    }
  else
    return 0;
}

/********************************************************************/
void *
l_pop_front(struct l_node **head_ptr, struct l_node **tail_ptr)
{
  void *data = *head_ptr ? (*head_ptr)->data : 0; 
  
  if (*head_ptr) /* detach first node */
    {
      struct l_node *ptr = *head_ptr;

      *head_ptr = ptr->next; /* set new head */
      free(ptr); /* deallocate memory */
      
      if (*head_ptr == 0) /* there is nothing left */
        *tail_ptr = 0; /* reset tail pointer */
    }
  
  return data;
}
---------------- #1: end ---------------------------------



---------------- #2: list structure  ---------------------
#include <stdlib.h>
#include "list.h"

/********************************************************************/
int
l_push_back(void *data, struct list *lptr)
{
  struct l_node *nptr = malloc(sizeof(struct l_node));

  if (nptr) /* load node and link it */
    {
      nptr->data = data;
      nptr->next = 0; /* new node will be last one */
      
      if (lptr->tail) /* there is already something */
        lptr->tail->next = nptr;
      else /* first node */
        lptr->head = nptr;
      
      lptr->tail = nptr; /* new nodes becomes last one */
      
      return 1;
    }
  else
    return 0;
}

/********************************************************************/
void *
l_pop_front(struct list *lptr)
{
  void *data = (lptr->head) ? lptr->head->data : 0; 
  
  if (lptr->head) /* detach first node */
    {
      struct l_node *ptr = lptr->head;

      lptr->head = ptr->next; /* set new head */
      free(ptr); /* deallocate memory */
      
      if (lptr->head == 0) /* there is nothing left */
        lptr->tail = 0; /* reset tail pointer */
    }
  
  return data;
}
---------------- #2: end ---------------------------------



---------------- #3: single pointers ---------------------
#include <stdlib.h>
#include "list.h"

/********************************************************************/
int
l_push_back(void *data, struct l_node *head, struct l_node *tail)
{
  struct l_node *nptr = malloc(sizeof(struct l_node));

  if (nptr) /* load node and link it */
    {
      nptr->data = data;
      nptr->next = 0; /* new node will be last one */
      
      if (tail) /* there is already something */
        tail->next = nptr;
      else /* first node */
        head = nptr;
      
      tail = nptr; /* new nodes becomes last one */
      
      return 1;
    }
  else
    return 0;
}

/********************************************************************/
void *
l_pop_front(struct l_node *head, struct l_node *tail)
{
  void *data = head ? head->data : 0; 
  
  if (head) /* detach first node */
    {
      struct l_node *ptr = head;

      head = ptr->next; /* set new head */
      free(ptr); /* deallocate memory */
      
      if (head == 0) /* there is nothing left */
        tail = 0; /* reset tail pointer */
    }
  
  return data;
}
---------------- #3: end ---------------------------------




Finally here are the 3 functions I used to test the "list"

---------------- #1: dual indirection --------------------
#include <stdio.h>
#include "list.h"

static void
print(const struct l_node *head);

int
main()
{
  struct l_node *head = 0; /* first element */
  struct l_node *tail = 0; /* last element */  
  int data[] = { 1 , 2, 3, 0 }; /* data */
  int *p = 0; /* iterator */

  
  puts("\n\n1) Loading list from back");  
  for (p = data; *p; p++) /* add another element to the list */
    {
      printf("\n\npushing value: %d\n", *p);
      l_push_back(p, &head, &tail);
      print(head);
    }

  puts("\n\n2) Popping values from front");
  while ((p = (int *)l_pop_front(&head, &tail)))
    {
      printf("\n\npopped value: %d\n", *p);
      print(head);      
    }

  return 0;
}

/********************************************************************/
void
print(const struct l_node *head)
{
  const struct l_node *iter;

  printf("%5s  %10s  %10s\n", "data", "node", "next");

  for (iter = head; iter; iter = iter->next)
    {
      int *p = (int *)iter->data;
      
      printf("%5d  %10p  %10p\n", *p, iter, iter->next);
    }
}
---------------- #1: end ---------------------------------




---------------- #2: list structure  ---------------------
#include <stdio.h>
#include "list.h"

static void
print(const struct list *lptr);

int
main()
{
  struct list ls = { 0, 0 }; /* list to be filled */
  int data[] = { 1 , 2, 3, 0 }; /* data */
  int *p = 0; /* iterator */

  
  puts("\n\n1) Loading list from back");  
  for (p = data; *p; p++) /* add another element to the list */
    {
      printf("\n\npushing value: %d\n", *p);
      l_push_back(p, &ls);
      print(&ls);
    }

  puts("\n\n2) Popping values from front");
  while ((p = (int *)l_pop_front(&ls)))
    {
      printf("\n\npopped value: %d\n", *p);
      print(&ls);  
    }

  return 0;
}

/********************************************************************/
void
print(const struct list *lptr)
{
  struct l_node *iter;

  printf("%5s  %10s  %10s\n", "data", "node", "next");

  for (iter = lptr->head; iter; iter = iter->next)
    {
      int *p = (int *)iter->data;
      
      printf("%5d  %10p  %10p\n", *p, iter, iter->next);
    }
}
---------------- #2: end ---------------------------------




---------------- #3: single pointers ---------------------
#include <stdio.h>
#include "list.h"

static void
print(const struct l_node *head);

int
main()
{
  struct l_node *head = 0; /* first element */
  struct l_node *tail = 0; /* last element */  
  int data[] = { 1 , 2, 3, 0 }; /* data */
  int *p = 0; /* iterator */

  
  puts("\n\n1) Loading list from back");  
  for (p = data; *p; p++) /* add another element to the list */
    {
      printf("\n\npushing value: %d\n", *p);
      l_push_back(p, head, tail);
      print(head);
    }

  puts("\n\n2) Popping values from front");
  while ((p = (int *)l_pop_front(head, tail)))
    {
      printf("\n\npopped value: %d\n", *p);
      print(head);      
    }

  return 0;
}

/********************************************************************/
void
print(const struct l_node *head)
{ /* same implementation of the case #1: "dual indirection" */ }

---------------- #3: end ---------------------------------


Excuse me for the long post and forgive me if I have missed the point
about the "single pointer" approach; at the heart I am a newbie and
have much yet to learn.

Regards
--
>> gisan >>

RE: [Dev-C++] Single Linked List-IV

[Ioannis V. <iv...@em...>]

> -----Original Message-----
> From: dev...@li... 
> [mailto:dev...@li...] On Behalf 
> Of Luigi Santillo
> Sent: Tuesday, June 10, 2003 6:30 PM
> To: 'Dev-Cpp-Users'
> Subject: Re: [Dev-C++] Single Linked List-IV
> 
>  - using "single pointers", seems not to be correct, in that changes
>    made to "head" and "tail", are changes made to a copy of 
> the pointers
>    local to the function "l_push_back", thus the updated values are 
>    not seen outside the scope of the function.


Yes you are right, I did not think a lot. He has to change the pointer
values so ** is needed in C, ** or reference (the last using templates) in
C++.

Well I say some b*llshit from time to time. :)






Ioannis Vranos
 
* Programming pages: http://www.noicys.freeurl.com
* Alternative URL 1: http://run.to/noicys
* Alternative URL 2: http://www.noicys.cjb.net

Re: [Dev-C++] Single Linked List-IV

[Luigi S. <gi...@li...>]

On Wed, Jun 11, 2003 at 10:33:05AM +0300, Ioannis Vranos wrote:
> [...]
> 
> Well I say some b*llshit from time to time. :)
>

Could be the heat wave sweeping across southern europe? :-) 

-- 
>> gisan >>
You have an unusual magnetic personality.  Don't walk too close to
metal objects which are not fastened down.