Script List

totoro125 · October 22, 2014, 3:29pm

I am looking at these two scripts and was wondering what would the list look like in each?

int main()
{
        int i;
        int rV = 0;
        List l = NULL;
        char* input[] = { "06", "24", "3" };
        sNode *s, *t;

        for( i=0; i<3; ++i )
        {
                t = (sNode*)malloc( sizeof( sNode ));
                if( t == NULL )
                {
                        fprintf( stderr, "Couldn't get memory for a node!  Exiting." );
                        rV = 1;
                        break;
                }
                t->data = input;
                t->next = l;
                l = t;
        }

        /* What does this list look like here? */

        s = l;
        while( s != NULL )
        {
                t = s->next;
                free( s );
                s = t;
        }

        return rV;
}

import sys

main( args=sys.argc ) :

        L = [24, None]

        t = [13, None]
        t[1] = L
        L = t

        t = [28, None]
        t[1] = L[1]
        L[1] = t

        t = [3, None]
        p = L
        while p != None :
                q = p
                p = p[1]

        if p == L :
                L = t
        else :
                q[1] = t

        print L

Corona688 · October 22, 2014, 4:16pm

Your first program is incomplete, List and sNode aren't defined anywhere, which is why it looks so weird. I can probably assume list and snode are the same, so they look like this:

typedef struct sNode {
        struct sNode *next;
        char *data;
};

#define List sNode

It is a linked list, where each element holds a reference to the next one, or a NULL reference if the list is ending.

After the first loop it looks like this:

L -> ["06"] -> NULL

Second loop:

L -> ["24"] -> ["06"] -> NULL

etc.

You can see how they create a new node with "malloc", set it to point to the old node t->next=l; and then make the root point to it l=t;

I cannot grasp that python code at all, so I can't tell how or if it's related to this, though I suspect python doesn't actually have a linked list -- it's a higher level language, operating above the level where you'd know or care how it remembers what elements go where.

totoro125 · October 22, 2014, 9:58pm

corona688:

Your first program is incomplete, List and sNode aren't defined anywhere, which is why it looks so weird. I can probably assume list and snode are the same, so they look like this:
typedef struct sNode {
   struct sNode *next;
   char *data;
};

#define List sNode
It is a linked list, where each element holds a reference to the next one, or a NULL reference if the list is ending.

After the first loop it looks like this:
L -> ["06"] -> NULL
Second loop:
L -> ["24"] -> ["06"] -> NULL
etc.

You can see how they create a new node with "malloc", set it to point to the old node t->next=l; and then make the root point to it l=t;

I cannot grasp that python code at all, so I can't tell how or if it's related to this, though I suspect python doesn't actually have a linked list -- it's a higher level language, operating above the level where you'd know or care how it remembers what elements go where.

Thank you! That helps a lot.
I am a little confused on this one also. What would this display?

#include <stdlib.h>
#include <string.h>
#include <stdio.h>

#define TABLE_SIZE  7
#define NUM_INPUTS  7

int hash( char *s )
{
        return strlen( s ) % TABLE_SIZE ;
}

typedef struct entry
{
        char *key;
        int     val;
        struct entry *next;
} entry;

entry* table[ TABLE_SIZE ] = { NULL };

void insert( char *s, int v )
        /* this insert is NOT checking for duplicates.  :/ */
{
        int h = hash( s );
        entry *t = (entry*) malloc( sizeof( entry ));

        t->key = s;
        t->val = v;
        t->next = table[h];
        table[h] = t;
}

void clean_table()
{
        entry *p, *q;
        int i;

        for( i=0; i<TABLE_SIZE; ++i )
        {
                for( p=table; p!=NULL; p=q )
                {
                        q = p->next;
                        free( p );
                }
        }       // for each entry
}       // clean_table


int main()
{
        char* keyList[] = { "Jaga", "Jesse", "Cos", "Kate", "Nash", "Vera",
                "Bob" };

        int valList[] = { 24, 78, 86, 28, 11, 99, 38 };

        int i;

        for( i=0; i<NUM_INPUTS; ++i )
                insert( keyList, valList );

        /* what does the table look like here? */

        clean_table();

        return( 0 );
}

Chubler_XL · October 23, 2014, 12:36am

This is a simplified representation of how the table array would look:

table[0] (Undefined)
table[1] (Undefined)
table[2] (Undefined)
table[3] => {"Bob", 38} -> {"Cos", 86}
table[4] => {"Vera", 99} -> {"Nash", 11} -> { "Kate", 28 } -> {"Jaga", 24 }
table[5] => {"Jesse", 78}
table[6] (Undefined)

totoro125 · October 25, 2014, 10:33pm

chubler_xl:

This is a simplified representation of how the table array would look:

table[0] (Undefined)
table[1] (Undefined)
table[2] (Undefined)
table[3] => {"Bob", 38} -> {"Cos", 86}
table[4] => {"Vera", 99} -> {"Nash", 11} -> { "Kate", 28 } -> {"Jaga", 24 }
table[5] => {"Jesse", 78}
table[6] (Undefined)

Thank you ^^ but can you explain how you got that?
Also, I was wondering if it was possible to write a function that takes a key and a reference to an integer and fills in the reference with the appropriate value, while returning true? If possible, how would you write it?

Chubler_XL · October 26, 2014, 4:20pm

entry* table[ TABLE_SIZE ] = { NULL }; this statement initializes the "table" array as a TABLE_SIZE (7) element array with NULL pointers. In C arrays are indexed from zero so we end up with:

table[0] (Undefined)
table[1] (Undefined)
table[2] (Undefined)
table[3] (Undefined)
table[4] (Undefined)
table[5] (Undefined)
table[6] (Undefined)

I use (Undefined) here, as the table array element contains a NULL pointer. In the context of this code (empty) could be a better analogy.

The insert code calculates a hash value of the input string being the length of the string modulo the TABLE_SIZE (7). This is a pretty simple hash which results in strings of various lengths being inserted into the table array as follows:

table[0] ~ lengths     7, 14, 21, 28, etc
table[1] ~ lengths 1,  8, 15, 22, 29, etc
table[2] ~ lengths 2,  9, 16, 23, 30, etc
table[3] ~ lengths 3, 10, 17, 24, 31, etc
table[4] ~ lengths 4, 11, 18, 25, 32, etc
table[5] ~ lengths 5, 12, 19, 26, 33, etc
table[6] ~ lengths 6, 13, 20, 27, 34, etc

Looking at this code in the insert function:

        t->key = s;
        t->val = v;
        t->next = table[h];
        table[h] = t;

we can see that each element of table is a linked list and new values are inserted at the front of the list.

So "Jaga" is inserted into the table[4] list first, then later "Kate" is inserted in front of "Jaga" then "Nash", and so forth.

Here is the update code you requested:

int update( char *s, int v )
/* Update 1st found entry with a key matching s assign new val of v
    returns 1 if an entry is updated and 0 otherwise */
{
        int h = hash( s );
        entry *t;

        for(t=table[h]; t!=NULL; t=t->next)
            if (!strcmp(s, t->key)) {
                 t->val = v;
                 return 1;
            }
        return 0;
}

totoro125 · October 26, 2014, 4:37pm

chubler_xl:

entry* table[ TABLE_SIZE ] = { NULL }; this statement initializes the "table" array as a TABLE_SIZE (7) element array with NULL pointers. In C arrays are indexed from zero so we end up with:
table[0] (Undefined)
table[1] (Undefined)
table[2] (Undefined)
table[3] (Undefined)
table[4] (Undefined)
table[5] (Undefined)
table[6] (Undefined)
I use (Undefined) here, as the table array element contains a NULL pointer. In the context of this code (empty) could be a better analogy.

The insert code calculates a hash value of the input string being the length of the string modulo the TABLE_SIZE (7). This is a pretty simple hash which results in strings of various lengths being inserted into the table array as follows:
table[0] ~ lengths     7, 14, 21, 28, etc
table[1] ~ lengths 1,  8, 15, 22, 29, etc
table[2] ~ lengths 2,  9, 16, 23, 30, etc
table[3] ~ lengths 3, 10, 17, 24, 31, etc
table[4] ~ lengths 4, 11, 18, 25, 32, etc
table[5] ~ lengths 5, 12, 19, 26, 33, etc
table[6] ~ lengths 6, 13, 20, 27, 34, etc
Looking at this code in the insert function:
   t->key = s;
   t->val = v;
   t->next = table[h];
   table[h] = t;
we can see that each element of table is a linked list and new values are inserted at the front of the list.

So "Jaga" is inserted into the table[4] list first, then later "Kate" is inserted in front of "Jaga" then "Nash", and so forth.

Here is the update code you requested:
int update( char *s, int v )
/* Update 1st found entry with a key matching s assign new val of v
   returns 1 if an entry is updated and 0 otherwise */
{
   int h = hash( s );
   entry *t;

   for(t=table[h]; t!=NULL; t=t->next)
   if (!strcmp(s, t->key)) {
   t->val = v;
   return 1;
   }
   return 0;
}

Thank you so much! This helps a lot =D
One last thing, would you happen to know how to run the python code? I know it's incomplete but I am not sure what to add so I can make it run and see the output.

Chubler_XL · October 26, 2014, 4:59pm

I'm not entirely sure the code you posted was python, their is no sys.argc and instead you would use len ( sys.argv ) , however if we forget about the main function definition you can get some output ( [13, [28, [24, [3, None]]]] ) using

#!/usr/bin/env python

L = [24, None]

t = [13, None]
t[1] = L
L = t

t = [28, None]
t[1] = L[1]
L[1] = t

t = [3, None]
p = L
while p != None :
        q = p
        p = p[1]

if p == L :
        L = t
else :
        q[1] = t

print L

Note: that indents are a part of the python language and you must keep them consistent or the program will refuse to run with errors like unexpected indent or unindent does not match any outer indentation level

totoro125 · October 26, 2014, 5:16pm

chubler_xl:

I'm not entirely sure the code you posted was python, their is no sys.argc and instead you would use len ( sys.argv ) , however if we forget about the main function definition you can get some output ( [13, [28, [24, [3, None]]]] ) using
#!/usr/bin/env python

L = [24, None]

t = [13, None]
t[1] = L
L = t

t = [28, None]
t[1] = L[1]
L[1] = t

t = [3, None]
p = L
while p != None :
   q = p
   p = p[1]

if p == L :
   L = t
else :
   q[1] = t

print L
Note: that indents are a part of the python language and you must keep them consistent or the program will refuse to run with errors like unexpected indent or unindent does not match any outer indentation level

Thank you again! ^^
I noticed that python can be a little annoying with the indenting. It was driving me crazy before because I kept receiving those errors when I tried writing a python script.