MHB What is the Efficient Way to Perform a Zig-Zag Traversal in a List?

[evinda]

Hello! (Smile)

Suppose that each node of a list has the following structs:

• string
  $$$$
• num
  $$$$
• next

It is given a string $w$. Suppose that $w$ is in the list at a node $p$, of which the struct num has the value n.
We are looking for the value of the struct string of the node that precedes $p$ for $n$ positions in the list.View attachment 3606

So, do we have to traverse the whole list, till we find a node with struct num equal to $n$ and then with a while loop find the desired value or is there also a better way? (Thinking)

 

[I like Serena]

It is given a string $w$. Suppose that $w$ is in the list at a node $p$, of which the struct num has the value n.
We are looking for the value of the struct string of the node that precedes $p$ for $n$ positions in the list.

So, do we have to traverse the whole list, till we find a node with struct num equal to $n$ and then with a while loop find the desired value or is there also a better way? (Thinking)

Hi! (Smirk)

If I understand your problem statement correctly, $n$ is not given, only $w$ is.
So I think we first have to look up $w$ before we can tell what $p$ and $n$ are.
And then we have to find the node that precedes $p$ by $n$ positions.

Or am I wrong? (Wondering)
Is there an example?

 

[evinda]

Hi! (Smirk)

If I understand your problem statement correctly, $n$ is not given, only $w$ is.
So I think we first have to look up $w$ before we can tell what $p$ and $n$ are.
And then we have to find the node that precedes $p$ by $n$ positions.

I think so... (Thinking)

Is there an example?

No, there isn't an example... (Shake)

 

[I like Serena]

I think so... (Thinking)

No, there isn't an example... (Shake)

Then, out of hand, I see 2 approaches.We can iterate through the list until we find $w$, which is when we find $n$.
At the same time we track how many items we have passed, say $m$.
Then we iterate again for $m-n$ items. (Smirk)Alternatively, we can iterate through the list until we find $w$, and store the pointer to each item in an array.
(It would help if we have a clue how big the array should be. (Thinking))
Then we can look up $m-n$ in the array. (Thinking)

 

[evinda]

Then, out of hand, I see 2 approaches.We can iterate through the list until we find $w$, which is when we find $n$.
At the same time we track how many items we have passed, say $m$.
Then we iterate again for $m-n$ items. (Smirk)Alternatively, we can iterate through the list until we find $w$, and store the pointer to each item in an array.
(It would help if we have a clue how big the array should be. (Thinking))
Then we can look up $m-n$ in the array. (Thinking)

Is it right like that? (Thinking)

Algorithm(pointer L)
   pointer R;
   *R=L;
    int i;
    while (R->num!=n){   
             R=R->next;
    }
     for (i=0; i<n; i++){
           R=R->next;
           i=i+1;
     }
     printf("%c",R->string)

 

[I like Serena]

Is it right like that? (Thinking)

1. Algorithm(pointer L)
2.   pointer R;
3.   *R=L;
4.    int i;
5.    while (R->num!=n){   
6.             R=R->next;
7.    }
8.     for (i=0; i<n; i++){
9.           R=R->next;
10.          i=i+1;
11.    }
12.    printf("%c",R->string)

Well... in line 3 you have an assignment that won't compile. (Worried)

In line 5 you are matching $n$... but I thought we had to match $w$.

Then, in line 8, I presume you should be restarting from the beginning.
But if so, R should be assigned to L yet again. (Doh)

 

[evinda]

I retried it... (Wait)
Is it maybe like that? (Thinking)

    Algorithm(pointer L, string w){
        pointer R=L;
        int times=0;
        if (R==NULL) return;
        while (R!=NULL and R->string!=w){
              times++;
              R=R->next;
        }
        n=R->num;
        if (times>n){
            int i=0;
            p=L;
            while (i<times-n){
                   p=p->next;
                   i++;
            }
            return p->string;
        }
    }