structs and how to access them

Discussion in 'C Programming' started by Martin Marcher, Aug 10, 2003.

  1. Hi,

    I'm working on a program that creates a linear list of structs

    struct lin_list{
    struct lin_list *next;
    char Name[BUFF];
    };

    this is what it looks like. And i got (design) problems with the search
    function and delete function. I thought about searching like this

    while(strcmp(list->next->Name, somestring) != 0){
    list = list->next;
    }

    which should do the following return the elment just before the one that
    is searched, this way I could easily reuse the search function for
    deletion because I don't have to run it twice to get the element before
    the one that gets deleted, and still use it to output the element that was
    searched for by just doing

    element = element->next;
    fprintf(stdout, "format_here");

    is this a proper way?

    I admit I didn't even try wether it will work or not, because I thought
    I'll ask you guys first if this is a proper logic to use.

    Hope that was somehow clear

    thx
    Martin

    --
    http://wiki.mnemonisch.net

    "Are [Linux users] lemmings collectively jumping off of the cliff of
    reliable, well-engineered commercial software?"
    (By Matt Welsh)
     
    Martin Marcher, Aug 10, 2003
    #1
    1. Advertising

  2. Martin Marcher

    Morris Dovey Guest

    Martin Marcher wrote:

    > I'm working on a program that creates a linear list of structs
    >
    > struct lin_list{
    > struct lin_list *next;
    > char Name[BUFF];
    > };
    >
    > this is what it looks like. And i got (design) problems with the search
    > function and delete function. I thought about searching like this
    >
    > while(strcmp(list->next->Name, somestring) != 0){
    > list = list->next;
    > }
    >
    > which should do the following return the elment just before the one that
    > is searched, this way I could easily reuse the search function for
    > deletion because I don't have to run it twice to get the element before
    > the one that gets deleted, and still use it to output the element that was
    > searched for by just doing
    >
    > element = element->next;
    > fprintf(stdout, "format_here");
    >
    > is this a proper way?
    >
    > I admit I didn't even try wether it will work or not, because I thought
    > I'll ask you guys first if this is a proper logic to use.


    Martin...

    Since you didn't want to try it out, I didn't too. You may want
    to consider what happens if the search doesn't succeed (i.e. when
    you reach the end of the list...

    You've piqued my curiosity - why aren't you comparing somestring
    to list->Name ?
    --
    Morris Dovey
    West Des Moines, Iowa USA
    C links at http://www.iedu.com/c
     
    Morris Dovey, Aug 11, 2003
    #2
    1. Advertising

  3. Martin Marcher

    CBFalconer Guest

    Morris Dovey wrote:
    > Martin Marcher wrote:
    >
    > > I'm working on a program that creates a linear list of structs
    > >
    > > struct lin_list{
    > > struct lin_list *next;
    > > char Name[BUFF];
    > > };
    > >
    > > this is what it looks like. And i got (design) problems with
    > > the search function and delete function. I thought about
    > > searching like this
    > >
    > > while(strcmp(list->next->Name, somestring) != 0){
    > > list = list->next;
    > > }
    > >
    > > which should do the following return the elment just before
    > > the one that is searched, this way I could easily reuse the
    > > search function for deletion because I don't have to run it
    > > twice to get the element before the one that gets deleted,
    > > and still use it to output the element that was searched for
    > > by just doing
    > >
    > > element = element->next;
    > > fprintf(stdout, "format_here");
    > >
    > > is this a proper way?
    > >
    > > I admit I didn't even try wether it will work or not, because
    > > I thought I'll ask you guys first if this is a proper logic to
    > > use.

    >
    > Since you didn't want to try it out, I didn't too. You may want
    > to consider what happens if the search doesn't succeed (i.e.
    > when you reach the end of the list...
    >
    > You've piqued my curiosity - why aren't you comparing somestring
    > to list->Name ?


    It is a well known algorithm for allowing list item deletion.
    However there are traps, such as how to find the first element.
    The fact that he didn't bother to try it out is significant. If
    he had he might have found the problems, which are not insoluble.

    --
    Chuck F () ()
    Available for consulting/temporary embedded and systems.
    <http://cbfalconer.home.att.net> USE worldnet address!
     
    CBFalconer, Aug 11, 2003
    #3
  4. On Mon, 11 Aug 2003 01:42:10 +0000, CBFalconer wrote:

    > Morris Dovey wrote:
    >> Martin Marcher wrote:
    >> > search function and delete function. I thought about searching like
    >> > this
    >> >
    >> > while(strcmp(list->next->Name, somestring) != 0){

    ^^^^^^^^^^^^^^^^

    That's the point, I know that I could easily test it, but as you said
    there could be Problems (I guess not in my implementation of the list, as
    I am using a dummy element as the first on - I guess Otherwise I just
    would need a cyclic list).


    >> > list = list->next;
    >> > }

    >>
    >> Since you didn't want to try it out, I didn't too. You may want to
    >> consider what happens if the search doesn't succeed (i.e. when you reach
    >> the end of the list...
    >>
    >> You've piqued my curiosity - why aren't you comparing somestring to
    >> list->Name ?


    Thats because if I want to delete elemene with list->Name == 'test' and I
    search for list->next->Name I can return the significant element (the one
    just before 'test') and then use something like:

    position = list->next; // to get the element I want to actually delete
    free(position);

    otherwise I would have a problem, as there is no pointer to the previous
    element. My question was more if the logic of accessing and deleting items
    is an [good|bad|acceptable] one then asking you guys to compile and test
    this, sorry if this came thru wrong :).
    >
    > It is a well known algorithm for allowing list item deletion. However
    > there are traps, such as how to find the first element. The fact that he
    > didn't bother to try it out is significant. If he had he might have found
    > the problems, which are not insoluble.


    As said my first element is a dummy element, so to find the first struct
    containing data, i simply use the second one which solves the problem - at
    least in some way.

    thx
    Martin

    --
    http://wiki.mnemonisch.net

    How do I type "for i in *.dvi do xdvi i done" in a GUI?
    (Discussion in comp.os.linux.misc on the intuitiveness of interfaces.)
     
    Martin Marcher, Aug 11, 2003
    #4
  5. Martin Marcher

    Chris Torek Guest

    In article <>
    Martin Marcher <> writes:
    [background discussion on why he wants to have a search function
    that finds "the item before the desired item":]
    >... if I want to delete elemene with list->Name == 'test' and I
    >search for list->next->Name I can return the significant element (the one
    >just before 'test') and then use something like:
    >
    >position = list->next; // to get the element I want to actually delete
    >free(position);
    >
    >otherwise I would have a problem, as there is no pointer to the previous
    >element. My question was more if the logic of accessing and deleting items
    >is an [good|bad|acceptable] one then asking you guys to compile and test
    >this, sorry if this came thru wrong :).


    As I think Chuck noted, you can indeed do this, although there are
    various corner cases to watch out for.

    There is, however, a "more C-like" way to handle the problem. That
    is, there is a way to do this in C that is forbidden in quite a few
    other languages. (If there is something you can do in C and assembly,
    but not in [say] Pascal, I often call that "quite C-like" :) .)

    Suppose we have a linked-list data structure:

    struct list {
    struct list *next;
    ... actual data here ...
    };

    and a pointer to the head of (i.e., first entry in) the list, which
    is initially NULL when the list is empty:

    struct list *head = NULL;

    Now, in C, we can write the "find entry in list" function so that
    it returns a pointer to the <pointer that points to the entry>
    (enclosed in <angle brackets> as the pointer points to that item).
    Assume for the moment that the item is guaranteed to be in the list,
    and consider the following code:

    struct list **searchfor(key_type key) {
    struct list **pp, *cur;

    for (pp = &head; (cur = *pp) != NULL; pp = &cur->next) {
    if (SAME_ITEM(key, cur))
    break;
    }
    return pp;
    }

    Given the "item will be in the list" assumption, one of the SAME_ITEM
    tests will succeed and the loop will stop via the "break". We then
    return "pp", the value of the pointer through which we found "cur",
    which is the matching item.

    If the matching item is the head of the list, pp == &head. Otherwise
    pp is the address of some list-item's "next" field. To remove the
    found item, we need only write:

    struct list **pp, *item;

    pp = searchfor(key);
    item = *pp;
    *pp = item->next;

    Now "item" is the found item, and *pp -- which is either "head"
    itself, or the "next" element of the list entry that points to
    "item" -- has been changed to point to item->next. In other words,
    if we found the first item in the list, we have just modified "head"
    itself, otherwise we have removed some mid-list item, or even the
    last item in the list (by having item->next==NULL).

    All of this hinges on the "item guaranteed to be in list" condition.
    What if the item is *not* in the list?

    In that case, no SAME_ITEM test will succeed, and eventually the
    loop will stop on the test in the "for" itself, i.e., when cur
    becomes NULL. In this case, "pp" is still valid, and is a pointer
    to a "struct list *", but *pp is NULL. The searchfor() function
    will return this pointer value, whatever it is.

    Thus, the test for "was the item found" is:

    pp = searchfor(key);
    item = *pp;
    if (item == NULL) /* it was not found */
    ...

    Again, it is possible that pp == &head, in which case the list is
    empty. If the list is *not* empty, however, pp points to the "next"
    pointer of the last item in the list. If we now desire to add a
    new item to the end of the list, we merely need to do this:

    /* newitem->next = NULL; -- if not already set */
    *pp = newitem;

    To make searchfor() more general, it is better to modify it so that
    "head" is not a "global variable" (whatever "global variable" means
    to you, the reader) in searchfor(). Note that the only thing
    searchfor() does with "head" is take its address. If searchfor()
    simply requires the *caller* to take the address, the function
    can then work on any list-head:

    struct list **searchfor(struct list **phead, key_type key) {
    struct list **pp, *cur;

    for (pp = phead; (cur = *pp) != NULL; pp = &cur->next) {
    if (SAME_ITEM(key, cur))
    break;
    }
    return pp;
    }

    /* and then later: */
    pp = searchfor(&head, key);

    In practice, however, linked-list walking is so trivial that doing
    this sort of fancy "search, but return a pointer to the pointer
    that points to the item" thing is rarely worthwhile. You can just
    do the loop in-line wherever needed (e.g., for deletion), and do
    the more obvious loop in-line where practical (e.g., for insertion).
    If your list is sorted, it might be OK to use this scheme -- but
    maintaining sorted lists is not something one should do all that
    often either (the time complexity is O(n^2); if the lists are short,
    the extra code does not pay off, and if the lists are long, you
    are probably better off with a balanced tree or hash table or some
    such).
    --
    In-Real-Life: Chris Torek, Wind River Systems (BSD engineering)
    Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W) +1 801 277 2603
    email: forget about it http://67.40.109.61/torek/index.html (for the moment)
    Reading email is like searching for food in the garbage, thanks to spammers.
     
    Chris Torek, Aug 11, 2003
    #5
  6. Martin Marcher

    Joe Wright Guest

    CBFalconer wrote:
    >
    > Morris Dovey wrote:
    > > Martin Marcher wrote:
    > >
    > > > I'm working on a program that creates a linear list of structs
    > > >
    > > > struct lin_list{
    > > > struct lin_list *next;
    > > > char Name[BUFF];
    > > > };
    > > >
    > > > this is what it looks like. And i got (design) problems with
    > > > the search function and delete function. I thought about
    > > > searching like this
    > > >
    > > > while(strcmp(list->next->Name, somestring) != 0){
    > > > list = list->next;
    > > > }
    > > >
    > > > which should do the following return the elment just before
    > > > the one that is searched, this way I could easily reuse the
    > > > search function for deletion because I don't have to run it
    > > > twice to get the element before the one that gets deleted,
    > > > and still use it to output the element that was searched for
    > > > by just doing
    > > >
    > > > element = element->next;
    > > > fprintf(stdout, "format_here");
    > > >
    > > > is this a proper way?
    > > >
    > > > I admit I didn't even try wether it will work or not, because
    > > > I thought I'll ask you guys first if this is a proper logic to
    > > > use.

    > >
    > > Since you didn't want to try it out, I didn't too. You may want
    > > to consider what happens if the search doesn't succeed (i.e.
    > > when you reach the end of the list...
    > >
    > > You've piqued my curiosity - why aren't you comparing somestring
    > > to list->Name ?

    >
    > It is a well known algorithm for allowing list item deletion.
    > However there are traps, such as how to find the first element.
    > The fact that he didn't bother to try it out is significant. If
    > he had he might have found the problems, which are not insoluble.
    >

    I've done it this way...

    typedef struct node {
    size_t size;
    void *allo;
    struct node *next;
    } node;
    static node dummy; /* size == 0 and pointers == NULL */
    static node *head = &dummy; /* point to the dummy */
    static node *prev, *this, *that; /* pointers for keeping track of
    things. */

    /* Find the node containing allo == p.
    Return pointer to the node or NULL if not found. */

    static node *
    fnd(void *p) {
    for (this = head->next; this; prev = this, this = this->next) {
    if (this->allo == p)
    break;
    }
    return this;
    }

    --
    Joe Wright mailto:
    "Everything should be made as simple as possible, but not simpler."
    --- Albert Einstein ---
     
    Joe Wright, Aug 11, 2003
    #6
  7. Martin Marcher

    Al Bowers Guest

    Joe Wright wrote:
    > CBFalconer wrote:
    >
    >>Morris Dovey wrote:
    >>
    >>>Martin Marcher wrote:
    >>>
    >>>
    >>>>I'm working on a program that creates a linear list of structs
    >>>>
    >>>>struct lin_list{
    >>>> struct lin_list *next;
    >>>> char Name[BUFF];
    >>>>};
    >>>>
    >>>>this is what it looks like. And i got (design) problems with
    >>>>the search function and delete function. I thought about
    >>>>searching like this
    >>>>
    >>>>while(strcmp(list->next->Name, somestring) != 0){
    >>>> list = list->next;
    >>>>}
    >>>>
    >>>>which should do the following return the elment just before
    >>>>the one that is searched, this way I could easily reuse the
    >>>>search function for deletion because I don't have to run it
    >>>>twice to get the element before the one that gets deleted,
    >>>>and still use it to output the element that was searched for
    >>>>by just doing
    >>>>
    >>>>element = element->next;
    >>>>fprintf(stdout, "format_here");
    >>>>
    >>>>is this a proper way?
    >>>>
    >>>>I admit I didn't even try wether it will work or not, because
    >>>>I thought I'll ask you guys first if this is a proper logic to
    >>>>use.
    >>>
    >>>Since you didn't want to try it out, I didn't too. You may want
    >>>to consider what happens if the search doesn't succeed (i.e.
    >>>when you reach the end of the list...
    >>>
    >>>You've piqued my curiosity - why aren't you comparing somestring
    >>>to list->Name ?

    >>
    >>It is a well known algorithm for allowing list item deletion.
    >>However there are traps, such as how to find the first element.
    >>The fact that he didn't bother to try it out is significant. If
    >>he had he might have found the problems, which are not insoluble.
    >>

    >
    > I've done it this way...
    >
    > typedef struct node {
    > size_t size;
    > void *allo;
    > struct node *next;
    > } node;
    > static node dummy; /* size == 0 and pointers == NULL */
    > static node *head = &dummy; /* point to the dummy */
    > static node *prev, *this, *that; /* pointers for keeping track of
    > things. */
    >
    > /* Find the node containing allo == p.
    > Return pointer to the node or NULL if not found. */
    >
    > static node *
    > fnd(void *p) {
    > for (this = head->next; this; prev = this, this = this->next) {
    > if (this->allo == p)
    > break;
    > }
    > return this;
    > }
    >


    I don't believe this solves the concern of the OP.
    If the return value is not NULL, then you have returned
    a pointer value which points to the found node.
    Now, you want to delete that node.
    You can do this by using the return value of function fnd as
    the arguement in function free.
    However, once the node is freed, the linked list is broken
    because the node previous(if there is one) to the deleted
    node how points to space that has been deallocated.

    There are ways to get around this problem but IMO I think
    a better way is to redesign your struct and associated functions.

    You could make the struct

    typedef struct lin_list
    {
    struct lin_list *prev;
    struct lin_list *next;
    char Name[256];
    }lin_list;

    Then the search and deletion functions are more easily made.

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

    #define BUFF 256

    typedef struct lin_list{
    struct lin_list *prev;
    struct lin_list *next;
    char Name[BUFF];
    }lin_list;

    lin_list *AddListNode(lin_list **head, const char *name);
    void DeleteListNode(lin_list **p, lin_list *del);
    lin_list *SearchList(lin_list *head, const char *name);
    void FreeList(lin_list **p);
    void PrintList(lin_list *p);

    int main(void)
    {
    lin_list *tmp,*list = NULL;

    AddListNode(&list,"Abe Lincoln");
    AddListNode(&list,"Bill Clinton");
    AddListNode(&list,"George Washington");
    AddListNode(&list, "George Bush");
    if(tmp = SearchList(list,"Bill Clinton"))
    DeleteListNode(&list,tmp); /* delete a node */
    PrintList(list);
    FreeList(&list);
    return 0;
    }

    lin_list *AddListNode(lin_list **p, const char *name)
    {
    lin_list *tmp, *current;

    if((tmp = malloc(sizeof(*tmp))) == NULL) return NULL;
    strncpy(tmp->Name,name,BUFF);
    tmp->next = NULL;
    if(*p == NULL)
    {
    tmp->prev = NULL;
    *p = tmp;
    return tmp;
    }
    for(current = *p; ; current = current->next)
    if(current->next == NULL) break;
    current->next = tmp;
    tmp->prev = current;
    return tmp;
    }

    void DeleteListNode(lin_list **p, lin_list *del)
    {
    if(del == *p) /* the head is being deleted */
    {
    if(del->next)
    del->next->prev = NULL;
    *p = del->next;
    }
    else
    {
    del->prev->next = del->next;
    del->next->prev = del->prev;
    }
    free(del);
    return;
    }

    lin_list *SearchList(lin_list *head, const char *name)
    {
    for( ; head ; head = head->next)
    if(strcmp(head->Name,name) == 0) break;
    return head;
    }

    void FreeList(lin_list **p)
    {
    lin_list *current, *tmp;

    for(current = *p; current; current = tmp)
    {
    tmp = current->next;
    free(current);
    }
    *p = NULL;
    return;
    }

    void PrintList(lin_list *p)
    {
    for( ; p; p = p->next)
    puts(p->Name);
    return;
    }



    --
    Al Bowers
    Tampa, Fl USA
    mailto: (remove the x)
    http://www.geocities.com/abowers822/
     
    Al Bowers, Aug 11, 2003
    #7
  8. On Mon, 11 Aug 2003 00:54:49 -0600, Chris Torek wrote:
    > In practice, however, linked-list walking is so trivial that doing this
    > sort of fancy "search, but return a pointer to the pointer that points to
    > the item" thing is rarely worthwhile. You can just do the loop in-line
    > wherever needed (e.g., for deletion), and do the more obvious loop in-line
    > where practical (e.g., for insertion). If your list is sorted, it might be
    > OK to use this scheme -- but maintaining sorted lists is not something one
    > should do all that often either (the time complexity is O(n^2); if the
    > lists are short, the extra code does not pay off, and if the lists are
    > long, you are probably better off with a balanced tree or hash table or
    > some such).


    Well I do this more to get two tasks in one, my next course will be "System
    Programming under UNIX" which obviously deals with C and since I don't
    have any experience at all this will be a good exercise and second (why I
    code the list) is that the exam for Algorithms and Datastructures will be
    soon. I thought trying to code lists, hash-tables, trees (and search thru them
    with the introduced algorithms) would be another good exercise, maybe I'll
    even get to 'external searching' - I don't know a better translation, I
    mean the kind of searching where you can't have all the data in memory and
    therefore have to leave parts of it on the disk.

    Well anyway pointers to pointers, like you used it, is quite a topic to
    work thru for now.

    thx
    Martin
    --
    http://wiki.mnemonisch.net

    "Oh, I've seen copies [of Linux Journal] around the terminal room at The
    Labs."
    (By Dennis Ritchie)
     
    Martin Marcher, Aug 11, 2003
    #8
  9. Martin Marcher

    Joe Wright Guest

    Al Bowers wrote:
    >
    > Joe Wright wrote:
    > > CBFalconer wrote:
    > >
    > >>Morris Dovey wrote:
    > >>
    > >>>Martin Marcher wrote:
    > >>>
    > >>>
    > >>>>I'm working on a program that creates a linear list of structs
    > >>>>
    > >>>>struct lin_list{
    > >>>> struct lin_list *next;
    > >>>> char Name[BUFF];
    > >>>>};
    > >>>>
    > >>>>this is what it looks like. And i got (design) problems with
    > >>>>the search function and delete function. I thought about
    > >>>>searching like this
    > >>>>
    > >>>>while(strcmp(list->next->Name, somestring) != 0){
    > >>>> list = list->next;
    > >>>>}
    > >>>>
    > >>>>which should do the following return the elment just before
    > >>>>the one that is searched, this way I could easily reuse the
    > >>>>search function for deletion because I don't have to run it
    > >>>>twice to get the element before the one that gets deleted,
    > >>>>and still use it to output the element that was searched for
    > >>>>by just doing
    > >>>>
    > >>>>element = element->next;
    > >>>>fprintf(stdout, "format_here");
    > >>>>
    > >>>>is this a proper way?
    > >>>>
    > >>>>I admit I didn't even try wether it will work or not, because
    > >>>>I thought I'll ask you guys first if this is a proper logic to
    > >>>>use.
    > >>>
    > >>>Since you didn't want to try it out, I didn't too. You may want
    > >>>to consider what happens if the search doesn't succeed (i.e.
    > >>>when you reach the end of the list...
    > >>>
    > >>>You've piqued my curiosity - why aren't you comparing somestring
    > >>>to list->Name ?
    > >>
    > >>It is a well known algorithm for allowing list item deletion.
    > >>However there are traps, such as how to find the first element.
    > >>The fact that he didn't bother to try it out is significant. If
    > >>he had he might have found the problems, which are not insoluble.
    > >>

    > >
    > > I've done it this way...
    > >
    > > typedef struct node {
    > > size_t size;
    > > void *allo;
    > > struct node *next;
    > > } node;
    > > static node dummy; /* size == 0 and pointers == NULL */
    > > static node *head = &dummy; /* point to the dummy */
    > > static node *prev, *this, *that; /* pointers for keeping track of
    > > things. */
    > >
    > > /* Find the node containing allo == p.
    > > Return pointer to the node or NULL if not found. */
    > >
    > > static node *
    > > fnd(void *p) {
    > > for (this = head->next; this; prev = this, this = this->next) {
    > > if (this->allo == p)
    > > break;
    > > }
    > > return this;
    > > }
    > >

    >
    > I don't believe this solves the concern of the OP.
    > If the return value is not NULL, then you have returned
    > a pointer value which points to the found node.
    > Now, you want to delete that node.
    > You can do this by using the return value of function fnd as
    > the arguement in function free.
    > However, once the node is freed, the linked list is broken
    > because the node previous(if there is one) to the deleted
    > node how points to space that has been deallocated.
    >
    > There are ways to get around this problem but IMO I think
    > a better way is to redesign your struct and associated functions.
    >
    > You could make the struct
    >

    [snip}

    I should have included more code. Note that fnd() will have set 'prev'
    to point to the node preceding 'this', therefore...

    void
    Free(void *ptr) {
    if (fnd(ptr)) {
    prev->next = this->next;
    free(this->allo);
    free(this);
    }
    }

    --
    Joe Wright mailto:
    "Everything should be made as simple as possible, but not simpler."
    --- Albert Einstein ---
     
    Joe Wright, Aug 11, 2003
    #9
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Patricia  Van Hise

    structs with fields that are structs

    Patricia Van Hise, Apr 5, 2004, in forum: C Programming
    Replies:
    5
    Views:
    641
    Al Bowers
    Apr 5, 2004
  2. Chris Hauxwell

    const structs in other structs

    Chris Hauxwell, Apr 23, 2004, in forum: C Programming
    Replies:
    6
    Views:
    560
    Chris Hauxwell
    Apr 27, 2004
  3. Paminu
    Replies:
    5
    Views:
    645
    Eric Sosman
    Oct 11, 2005
  4. Daniel Rudy
    Replies:
    15
    Views:
    1,405
    Keith Thompson
    Apr 10, 2006
  5. Tuan  Bui
    Replies:
    14
    Views:
    476
    it_says_BALLS_on_your forehead
    Jul 29, 2005
Loading...

Share This Page