Algorithms IN C

Discussion in 'C Programming' started by William R., Jan 7, 2005.

  1. William R.

    William R. Guest

    Question for those who can help me interpret the following exercise
    from the book "Algorithms in C", by Robert Sedwewick

    "Exercise:
    3.37 Implement a code fragment for a linked list that exchanges the
    positions of the nodes after the nodes referenced by two given links t
    and u."

    Does the exercise want me to swap the links t and u? (Not structure
    data, but just pointers in the list).

    ->[t]->->[v] Will become ->->[t]->[v]


    Any insight into what this question is asking would be appreciated.
    Thanks,

    William R.
    William R., Jan 7, 2005
    #1
    1. Advertising

  2. William R.

    dandelion Guest

    "William R." <> wrote in message
    news:...
    > Question for those who can help me interpret the following exercise
    > from the book "Algorithms in C", by Robert Sedwewick
    >
    > "Exercise:
    > 3.37 Implement a code fragment for a linked list that exchanges the
    > positions of the nodes after the nodes referenced by two given links t
    > and u."
    >
    > Does the exercise want me to swap the links t and u? (Not structure
    > data, but just pointers in the list).
    >
    > ->[t]->->[v] Will become ->->[t]->[v]


    Yes, if that function is provided pointers to and [t].

    For [t] and that would be

    ->[t]->[v]->.

    > Any insight into what this question is asking would be appreciated.


    AFAICS, your interpretation of the question is (almost) correct. The point
    is, that for deleting and inserting things into a singly linked list, you
    need a pointer to the _previous_ node.

    HTH, dandelion.
    dandelion, Jan 7, 2005
    #2
    1. Advertising

  3. William R. wrote:
    > Question for those who can help me interpret the following exercise
    > from the book "Algorithms in C", by Robert Sedwewick
    >
    > "Exercise:
    > 3.37 Implement a code fragment for a linked list that exchanges the
    > positions of the nodes after the nodes referenced by two given links t
    > and u."
    >
    > Does the exercise want me to swap the links t and u? (Not structure
    > data, but just pointers in the list).
    >
    > ->[t]->->[v] Will become ->->[t]->[v]


    You are assuming too much. There is nothing in the exercise that
    suggests what the relationship of t and u is. Given an original
    situation where t and u point to the nodes tnode and unode, and those
    nodes point to tnext and unext
    t -> tnode -> tnext
    and
    u -> unode -> unext,
    change the list so
    tnode -> unext
    and
    unode -> tnext

    "exchanges the positions of" is a problematic expression, though. It
    can be interpreted so my statement above is wrong. An alternative
    interprepation leaves the links in tnode and unode as they are, and
    actually switches the contents of the nodes unext and tnext.
    Martin Ambuhl, Jan 7, 2005
    #3
  4. William R.

    William R. Guest

    If its a singly linked list, and I add a previous node link to the
    structure, wouldn't that make it a doubly-linked list?

    I may have confused the question by adding my own interpitation of the
    link list. No where in the question does it state its link list
    structure as ->[t]->->[v]

    First part of the question: "Implement a code fragment from a linked
    list" -- So we know there is a linked list, but it's order is unkown.

    Second part: " that exchanges the positions of the nodes after the
    nodes referenced by two given links t and u". --- my confusion is the
    part that says, "that exchanges the position of the nodes after the
    nodes referenced", which nodes are exchanging in the list? By your
    interpitation wouldn't the new list become, ->[v]-[t]->? Is it
    saying move everything after these links in front of them? From the
    question alone are we suppose to assume, t and u are linked together in
    order?

    It's morning hours now, so I'll email my professor see what he has to
    say. But please fill free to respond.

    Thanks,

    William R.
    William R., Jan 7, 2005
    #4
  5. William R.

    infobahn Guest

    "William R." wrote:
    >
    > If its a singly linked list, and I add a previous node link to the
    > structure, wouldn't that make it a doubly-linked list?


    Yes. Here's a single linked list.

    +----+ +----+ +----+
    | +--->| +--->| +---> NULL
    +----+ +----+ +----+

    Here's a double linked list.

    +------+ +------+ +------+
    | +--->| +--->| +---> NULL
    | | | | | |
    NULL <---+ |<---+ |<---+ |
    +------+ +------+ +------+


    > First part of the question: "Implement a code fragment from a linked
    > list" -- So we know there is a linked list, but it's order is unkown.
    >
    > Second part: " that exchanges the positions of the nodes after the
    > nodes referenced by two given links t and u". --- my confusion is the
    > part that says, "that exchanges the position of the nodes after the
    > nodes referenced", which nodes are exchanging in the list?


    You are being asked to exchange t->next with u->next, but presumably
    t->next->next and u->next->next should stay in place.

    The question is harder if t->next might be u, or u->next might be t,
    or even both! The question is a little more involved if t->next or
    u->next might be null, and borders on interestingness if t might
    be u.
    infobahn, Jan 8, 2005
    #5
    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. Andreas
    Replies:
    0
    Views:
    496
    Andreas
    Dec 2, 2003
  2. abhinav

    encryption algorithms

    abhinav, Dec 26, 2004, in forum: VHDL
    Replies:
    2
    Views:
    623
  3. Melanie Nasic
    Replies:
    19
    Views:
    3,018
    Thomas Rudloff
    Jan 1, 2006
  4. Soenke
    Replies:
    0
    Views:
    547
    Soenke
    Dec 28, 2005
  5. Oracle3001

    De-Interlacing Algorithms

    Oracle3001, Jul 21, 2003, in forum: Java
    Replies:
    0
    Views:
    489
    Oracle3001
    Jul 21, 2003
Loading...

Share This Page