auxiliary linked list index array

[Hal Styli]

hello, can someone please help...
Im interested in the use of an auxiliary
array to act like pointers for another
array, allowing the sort order to be
traversed. See code below.

I dont have an application in mind,
its more academic at this stage - but not
a homework question!

I have tried to avoid the use of a separate
variable to point to the head of the list by
using the 0th element of the indexing array.
This doesnt always work as show with array b[]

Im looking for suggestions on arranging x[] so
that it can always be used without the use of
an extra variable. Im convinced it can be done
simply because there is a 'spare' slot if you
look at x[] and y[].

Thanks for any help given...

Hal
/*----------------------------------------------------------*/
/*linked list in an array*/
#include <stdio.h>
#define nl() putchar('\n')
#define SMAX 6
/*----------------------------------------------------------*/
int main()
{
/* 0, 1, 2, 3, 4, 5 */
char a[]= {'v','n','f','j','r','b'};
int w[]= {-1, 4, 3, 1, 0, 2}; /* -1 means end of list*/
int f=5; /*head of list*/
/* 0, 1, 2, 3, 4, 5 */
int x[]= { 5, 4, 3, 1, 0, 2}; /*head is x[0]*/

/* 0, 1, 2, 3, 4, 5 */
char b[]= {'L','H','X','P','D','T'};
int y[]= { 3, 0, -1, 5, 1, 2};
int e=4; /*head of list*/
/*
b[] cannot be indexed using a representation
like x[] because the index element zero needs
to be 4 at the start and 3 later on:-
int z[]= { 4 then 3, 0, -1, 5, 1, 2};
*/
int i,p;

nl();
for(i=0,p=f; i<SMAX; i++,p=w[p])
printf("%d %c\n", p, a[p]);
nl();
for(i=0,p=x[0]; i<SMAX; i++,p=x[p])
printf("%d %c\n", p, a[p]);
nl();
for(i=0,p=e; i<SMAX; i++,p=y[p])
printf("%d %c\n", p, b[p]);
nl();
return 0;
}

 

[Richard Bos]

I have tried to avoid the use of a separate
variable to point to the head of the list by
using the 0th element of the indexing array.
This doesnt always work as show with array b[]

You cannot do that. There isn't room.

Im looking for suggestions on arranging x[] so
that it can always be used without the use of
an extra variable. Im convinced it can be done
simply because there is a 'spare' slot if you
look at x[] and y[].

The problem is _finding_ that spare slot.

/* 0, 1, 2, 3, 4, 5 */
char a[]= {'v','n','f','j','r','b'};
int w[]= {-1, 4, 3, 1, 0, 2}; /* -1 means end of list*/
int f=5; /*head of list*/
/* 0, 1, 2, 3, 4, 5 */
int x[]= { 5, 4, 3, 1, 0, 2}; /*head is x[0]*/

/* 0, 1, 2, 3, 4, 5 */
char b[]= {'L','H','X','P','D','T'};
int y[]= { 3, 0, -1, 5, 1, 2};
int e=4; /*head of list*/
/*
b[] cannot be indexed using a representation
like x[] because the index element zero needs
to be 4 at the start and 3 later on:-
int z[]= { 4 then 3, 0, -1, 5, 1, 2};

Exactly. You need to remember _two_ pieces of information: where the
logical start of the array is, and where the logical successor of
element 0 is. You cannot fit these two integers into one integer's
memory space, clearly.
It seems to work in the case of a[] because in that case the value of
these two bits of information just happens to be the same, but obviously
you cannot rely on that at all.

nl();

Bletch. What's wrong with plain putchar('\n'); or even puts("");?

Why don't you use a normal index array? Like this:

char b[]= {'L','H','X','P','D','T'};
int bi[]= { 4, 1, 0, 3, 5, 2};

for (i=0; i<SMAX; i++)
printf("%d %d %c\n", i, bi, b[bi]);

Richard