Algorithms and Data Structures
Excercise 2
List

Question 1PostScript for printing

Consider the following list.
head→1→2→3→4→5→tail
Draw the procedure for the following operations in this list. Be careful about the order of changing links.

The most important thing is that each node is linked to more than one node. The order of changing links is important. The following figure shows a mistake case. There is no links to node 1, so node 0 can't link to node 1.
The note of replace

The following figure shows the procedure for an operation of replaceing the head node and node 4.
The example of how to write

Question 2

Write a function "exchange" which replaces 2 nodes. Use ex02-skel.c. It is necessary to divide processing for two adjacent node case and for non-adjacent node case.

Example:
% ./a.out
Head - 1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 - Tail

=> exchange(1,2)
Head - 2 - 1 - 3 - 4 - 5 - 6 - 7 - 8 - 9 - Tail
=> exchange(1,2)
Head - 1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 - Tail
=> exchange(4,7)
Head - 1 - 2 - 3 - 7 - 5 - 6 - 4 - 8 - 9 - Tail
=> exchange(4,7)
Head - 1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 - Tail
Question 3

Write a function "reverse" which rearrange the order of nodes (between head and tail) into its reverse. Use ex02-skel.c.

Example:
% ./a.out
Head - 1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 - Tail

=> reverse()
Head - 9 - 8 - 7 - 6 - 5 - 4 - 3 - 2 - 1 - Tail

Written by Naoki Wakamatsu. The translated document was written by Kenichi Maezu <m5061121@u-aizu.ac.jp>
and Hajime Matsui <m5061122@u-aizu.ac.jp> and checked by L. Pichl.