"Nick Keighley" <ni******************@hotmail.com> wrote in message
news:11*********************@f14g2000cwb.googlegro ups.com...
Mabden wrote: "__frank__" <__*******@spam.yourself.against.a.w.all> wrote in
message news:ai******************@twister2.libero.it... I have some difficulties to learn lists and its
coding in C language.
New item: allocate memory, fill in data, set "next" pointer to null,
set current end pointer (was null) to it. Simple.
to "__frank__": Mabden's post only describes (very briefly) how to add
an item to the end of a list. It definitly isn't a complete
introduction to linked lists. The other replies you received looked
ok.
Mine's not OK? Not even OK? BTW, I was not actually going for a complete
introduction, but I challenge you to make a better one in under 20
words. Especially one better than OK.
Note: Although I "plonked" Mabden I don't actually use kill files. I
have responded to this post because his answer was poor and many
regulars have kill-filed him.
Ah, politics. Isn't that a little off-topic in a thread titled, "
How to learn lists in C"?
OK, perhaps something to entertain the more advanced programmer,
something I am trying out for my Sudoku game:
http://arxiv.org/PS_cache/cs/pdf/0011/0011047.pdf
"The dance steps. One good way to implement algorithm X is to represent
each 1 in the
matrix A as a data object x with five fields L[x],R[x], U[x],D[x],C[x].
Rows of the matrix
are doubly linked as circular lists via the L and R fields ("left" and
"right"); columns are
doubly linked as circular lists via the U and D fields ("up" and
"down"). Each column
list also includes a special data object called its list header.
The list headers are part of a larger object called a column object.
Each column object
y contains the fields L[y],R[y], U[y],D[y], and C[y] of a data object
and two additional
fields, S[y] ("size") and N[y] ("name"); the size is the number of 1s in
the column, and the
name is a symbolic identifier for printing the answers. The C field of
each object points
to the column object at the head of the relevant column.
The L and R fields of the list headers link together all columns that
still need to be
covered. This circular list also includes a special column object called
the root, h, which
serves as a master header for all the active headers. The fields
U[h],D[h],C[h], S[h], and
N[h] are not used.
For example, the 0-1 matrix of (3) would be represented by the objects
shown in
Figure 2, if we name the columns A, B, C, D, E, F, and G. (This diagram
"wraps around"
toroidally at the top, bottom, left, and right. The C links are not
shown because they
would clutter up the picture; each C field points to the topmost element
in its column.)
Our nondeterministic algorithm to find all exact covers can now be cast
in the following
explicit, deterministic form as a recursive procedure search(k), which
is invoked initially
with k = 0:
If R[h] = h, print the current solution (see below) and return.
Otherwise choose a column object c (see below).
Cover column c (see below).
For each r ? D[c], DD[c], . . . , while r 6= c,
set Ok ? r;
for each j ? R[r], RR[r], . . . , while j 6= r,
cover column j (see below);
search(k + 1);
set r ? Ok and c ? C[r];
for each j ? L[r], LL[r], . . . , while j 6= r,
uncover column j (see below).
Uncover column c (see below) and return.
The operation of printing the current solution is easy: We successively
print the rows
containing O0, O1, . . . , Ok?1, where the row containing data object O
is printed by
printing NC[O], NC[R[O]], NC[R[R[O]]], etc."
--
Mabden
