- **C Programming**
(*http://www.velocityreviews.com/forums/f42-c-programming.html*)

- - **Algorithms IN C**
(*http://www.velocityreviews.com/forums/t436431-algorithms-in-c.html*)

Algorithms IN CQuestion 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). [s]->[t]->[u]->[v] Will become [s]->[u]->[t]->[v] Any insight into what this question is asking would be appreciated. Thanks, William R. |

Re: Algorithms IN C"William R." <wroselli@gmail.com> wrote in message news:1105096274.197318.88790@z14g2000cwz.googlegro ups.com... > 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). > > [s]->[t]->[u]->[v] Will become [s]->[u]->[t]->[v] Yes, if that function is provided pointers to [s] and [t]. For [t] and [u] that would be [s]->[t]->[v]->[u]. > 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. |

Re: Algorithms IN CWilliam 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). > > [s]->[t]->[u]->[v] Will become [s]->[u]->[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. |

Re: Algorithms IN CIf 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 [s]->[t]->[u]->[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, [s]->[v]-[t]->[u]? 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. |

Re: Algorithms IN C"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. |

All times are GMT. The time now is 07:10 PM. |

Powered by vBulletin®. Copyright ©2000 - 2014, vBulletin Solutions, Inc.

SEO by vBSEO ©2010, Crawlability, Inc.