Algorithms IN C

[William R.]

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.

 

[dandelion]

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.

 

[Martin Ambuhl]

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.

 

[William R.]

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.

 

[infobahn]

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.