Linked List Problem(changing insertion pointer)

Discussion in 'C Programming' started by John N., Dec 28, 2003.

  1. John N.

    John N. Guest

    Hi All,

    Here I have a linked list each containing a char and is double linked.
    Then I have a pointer to an item in that list which is the current
    insertion point.

    In this funtion, the user hits the right
    and left keys to move this insertion point (cursor)

    Here is the problem:

    But its not stable, the insertion point seems to skip an item
    back, here and there. It could be the API Im using for the keyboard
    input but Im not sure.

    Thanks in advance for any help.
    John

    //a char structure, making a text string list
    struct Word{
    char *c;
    struct Word *next,*back;
    };
    typedef struct Word Word;

    Word *wrd;// a linked list of Word structures
    Word *insert;// pointer to the current insertion point of *wrd

    wrd = (allocate a list of Word structures)
    insert = (pointer to an insertion point in the text in the *wrd list)

    DoKey(insert,RIGHT_KEY);

    /* etc */

    void DoKey(struct Word *char_insert, int key){
    switch(key){
    case RIGHT_KEY:
    if(char_insert->next!=NULL)
    char_insert=char_insert->next;/* this is not fool proof,
    any help? */
    break;
    case LEFT_KEY:
    if(char_insert->back!=NULL)
    char_insert=char_insert->back;/* this is not fool proof,
    any help? */
    break;
    }
    }
    --
    comp.lang.c.moderated - moderation address:
     
    John N., Dec 28, 2003
    #1
    1. Advertising

  2. [Followups set to comp.lang.c - nothing personal, Seebs!]

    John N. wrote:

    > Hi All,
    >
    > Here I have a linked list each containing a char and is double linked.


    Your code says char *, not char.

    > Then I have a pointer to an item in that list which is the current
    > insertion point.

    <...>
    > But its not stable, the insertion point seems to skip an item
    > back, here and there. It could be the API Im using for the keyboard
    > input but Im not sure.


    It's your misunderstanding of pointers, I'm afraid.

    > //a char structure, making a text string list


    If you have a C99 compiler, // is legal comment syntax. Do you?

    > struct Word{
    > char *c;
    > struct Word *next,*back;
    > };
    > typedef struct Word Word;
    >
    > Word *wrd;// a linked list of Word structures
    > Word *insert;// pointer to the current insertion point of *wrd
    >
    > wrd = (allocate a list of Word structures)


    This ain't gonna compile.

    > insert = (pointer to an insertion point in the text in the *wrd list)


    Nor is this. Please remember, when posting code here, that by definition you
    do not know where the problem is. So it's not a good idea to chop out
    random chunks of it when asking for help.

    > DoKey(insert,RIGHT_KEY);
    >
    > /* etc */
    >
    > void DoKey(struct Word *char_insert, int key){
    > switch(key){
    > case RIGHT_KEY:
    > if(char_insert->next!=NULL)
    > char_insert=char_insert->next;/* this is not fool proof,
    > any help? */


    C is pass-by-value.

    void DoKey(struct Word **char_insert, int key)
    {
    switch(key)
    {
    case RIGHT_KEY:
    if((*char_insert)->next != NULL)
    {
    *char_insert = (*char_insert)->next;
    }
    break;

    case LEFT_KEY:
    if((*char_insert)->back != NULL)
    {
    *char_insert = (*char_insert)->back;
    }
    break;
    default:
    /* unhandled key event */
    break;
    }
    }

    --
    Richard Heathfield :
    "Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
    C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
    K&R answers, C books, etc: http://users.powernet.co.uk/eton
    --
    comp.lang.c.moderated - moderation address:
     
    Richard Heathfield, Dec 28, 2003
    #2
    1. Advertising

  3. John N. wrote:
    > Here I have a linked list each containing a char and is double linked.
    > Then I have a pointer to an item in that list which is the current
    > insertion point.
    >
    > In this function, the user hits the right
    > and left keys to move this insertion point (cursor)
    >
    > Here is the problem:
    >
    > But its not stable, the insertion point seems to skip an item
    > back, here and there. It could be the API Im using for the keyboard
    > input but Im not sure.


    No, it isn't likely to be that.

    > Thanks in advance for any help.
    > John
    >
    > //a char structure, making a text string list
    > struct Word{
    > char *c;
    > struct Word *next,*back;
    > };
    > typedef struct Word Word;
    >
    > Word *wrd;// a linked list of Word structures
    > Word *insert;// pointer to the current insertion point of *wrd
    >
    > wrd = (allocate a list of Word structures)


    And how is this data structure initialized? Zero pointers, or
    pointers to itself (a circular list)? Or are you allocating and
    initializing a whole bunch of Word structures, and putting them into a
    valid linked list?

    > insert = (pointer to an insertion point in the text in the *wrd list)


    So, presumably this is a contraction for 'insert = wrd;'? If not, you
    need to show the initialization, since without the initialization, it
    is hard to tell what the heck you might be doing.

    > DoKey(insert,RIGHT_KEY);


    You've not shown where the character is coming from. I know you said
    the keyboard, but which variable contains the value? Or is the
    'RIGHT_KEY' -- presumably a macro since it is in upper case -- the
    value purportedly to be inserted?

    > /* etc */
    >
    > void DoKey(struct Word *char_insert, int key){
    > switch(key){
    > case RIGHT_KEY:
    > if(char_insert->next!=NULL)
    > char_insert=char_insert->next;/* this is not fool proof,
    > any help? */
    > break;


    With a doubly-linked list, when you insert a new node, you allocate
    the new node and populate the data portion (c) with the data for the
    node. Then, assuming that the new node is inserted after the
    insertion point, you ensure that the next pointer of the new node
    points to the node that the insertion point points to as the next
    node, that the back pointer of the next node points to the new node,
    that the back pointer of the new node points to where the back pointer
    of the insertion pointer points, and the next pointer of the back node
    points to the new node. You might or might not also adjust the
    insertion point. The sequence is similar but different if the new
    node goes before the insertion point.

    You've not shown very much of any of this material. You don't
    allocate new nodes and you don't fix up the pre-existing nodes.

    > case LEFT_KEY:
    > if(char_insert->back!=NULL)
    > char_insert=char_insert->back;/* this is not fool proof,
    > any help? */
    > break;
    > }
    > }


    Any more help? Draw a diagram! Draw a lot of diagrams! And make
    sure all your pointers are initialized.

    Finally, a member 'char *c' is misleading (but not, I hasten to
    emphasize, wrong). In general, a variable c is a single character,
    not a pointer to a character. There are various possible names that
    would be happier choices - s or p are primary options, and there are a
    myriad others. From the code you show, it is impossible to deduce
    whether you store pointers to null-terminated strings or pointers to
    single characters in it - you don't show it being used at all, in fact.

    Given your problem description, you might be better off using c as a
    simple char - though a doubly linked list of single characters is an
    incredibly heavy-weight structure (typically occupying 12 bytes per
    character).

    Another reading of your problem might be that you are wondering why
    the value of 'insert' in the calling code is not modified by the code
    in DoKey -- and the answer is because you don't pass insert as a
    pointer to a Word pointer. This only applies if you are already sure
    you've built your doubly-linked list correctly, which is (as far as
    anyone can see) debatable.

    --
    Jonathan Leffler #include <disclaimer.h>
    Email: ,
    Guardian of DBD::Informix v2003.04 -- http://dbi.perl.org/
    --
    comp.lang.c.moderated - moderation address:
     
    Jonathan Leffler, Dec 28, 2003
    #3
  4. John N.

    Malcolm Guest

    "John N." <> wrote in
    >
    > struct Word{
    > char *c;
    > struct Word *next,*back;
    > };
    > typedef struct Word Word;
    >

    Run the following function

    void integrity_test(Word *head)
    {
    Word *prev = NULL:
    printf("Start\n");
    while(head)
    {
    printf("%s\n", head->c);
    prev = head;
    head = head->next;
    }
    printf("End\n");
    while(prev)
    {
    printf("%s\n", prev->c);
    prev = prev->back;
    }
    }

    This should expose problems with the linked list structure.
    --
    comp.lang.c.moderated - moderation address:
     
    Malcolm, Dec 28, 2003
    #4
  5. On 28 Dec 2003 06:39:31 GMT, (John N.) wrote:

    >Hi All,
    >
    >Here I have a linked list each containing a char and is double linked.
    >Then I have a pointer to an item in that list which is the current
    >insertion point.
    >
    >In this funtion, the user hits the right
    >and left keys to move this insertion point (cursor)
    >
    >Here is the problem:
    >
    >But its not stable, the insertion point seems to skip an item
    >back, here and there. It could be the API Im using for the keyboard
    >input but Im not sure.
    >
    >Thanks in advance for any help.
    > John
    >
    >//a char structure, making a text string list
    >struct Word{
    > char *c;
    > struct Word *next,*back;
    >};
    >typedef struct Word Word;
    >
    >Word *wrd;// a linked list of Word structures
    >Word *insert;// pointer to the current insertion point of *wrd
    >
    >wrd = (allocate a list of Word structures)
    >insert = (pointer to an insertion point in the text in the *wrd list)
    >
    >DoKey(insert,RIGHT_KEY);
    >
    >/* etc */
    >
    >void DoKey(struct Word *char_insert, int key){
    > switch(key){
    > case RIGHT_KEY:
    > if(char_insert->next!=NULL)
    > char_insert=char_insert->next;/* this is not fool proof,
    >any help? */
    > break;
    > case LEFT_KEY:
    > if(char_insert->back!=NULL)
    > char_insert=char_insert->back;/* this is not fool proof,
    >any help? */
    > break;
    > }
    >}


    The real question is why do you think it worked at all. The
    char_insert variable inside your function is not the same variable you
    defined near the top of your code.

    Your function performs all of its assignments to a local variable
    (actually a parameter which, since C passes by value, is a copy of the
    argument and not the argument itself). When the function exits, all
    local variables (other than static) are destroyed. The result of your
    function's assignments are never communicated back to the calling
    function.


    <<Remove the del for email>>
    --
    comp.lang.c.moderated - moderation address:
     
    Barry Schwarz, Dec 28, 2003
    #5
  6. John N.

    John N. Guest

    > >//a char structure, making a text string list
    > >struct Word{
    > > char *c;
    > > struct Word *next,*back;
    > >};
    > >typedef struct Word Word;
    > >
    > >Word *wrd;// a linked list of Word structures
    > >Word *insert;// pointer to the current insertion point of *wrd
    > >
    > >wrd = (allocate a list of Word structures)
    > >insert = (pointer to an insertion point in the text in the *wrd list)
    > >
    > >DoKey(insert,RIGHT_KEY);
    > >
    > >/* etc */
    > >
    > >void DoKey(struct Word *char_insert, int key){
    > > switch(key){
    > > case RIGHT_KEY:
    > > if(char_insert->next!=NULL)
    > > char_insert=char_insert->next;/* this is not fool proof,
    > >any help? */
    > > break;
    > > case LEFT_KEY:
    > > if(char_insert->back!=NULL)
    > > char_insert=char_insert->back;/* this is not fool proof,
    > >any help? */
    > > break;
    > > }
    > >}

    >
    > The real question is why do you think it worked at all. The
    > char_insert variable inside your function is not the same variable you
    > defined near the top of your code.
    >
    > Your function performs all of its assignments to a local variable
    > (actually a parameter which, since C passes by value, is a copy of the
    > argument and not the argument itself). When the function exits, all
    > local variables (other than static) are destroyed. The result of your
    > function's assignments are never communicated back to the calling
    > function.
    >


    Hi All, Thanks for the quick responses.

    I posted a shorter example of my code. The problem turned out to be
    my switch/case statement that handled key input (not posted here) and
    the insertion pointer was being misshandled.
    --
    comp.lang.c.moderated - moderation address:
     
    John N., Dec 31, 2003
    #6
    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. Jochus
    Replies:
    3
    Views:
    517
    Jochus
    Apr 21, 2005
  2. Java Newbie

    Insertion Sort on a linked list

    Java Newbie, Feb 4, 2007, in forum: Java
    Replies:
    2
    Views:
    3,376
    Mark Space
    Feb 9, 2007
  3. fool
    Replies:
    14
    Views:
    525
    Barry Schwarz
    Jul 3, 2006
  4. Julia
    Replies:
    6
    Views:
    609
    Dmitri Sologoubenko
    Aug 11, 2006
  5. joshd
    Replies:
    12
    Views:
    683
    John Carson
    Oct 2, 2006
Loading...

Share This Page