Lab46 Wiki

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
\\ 
<WRAP centeralign bigger><WRAP bigger fgred>Corning Community College</WRAP>
\\ 
<WRAP muchbigger>Data Structures</WRAP> 
\\ 
Linked List Knowledge Assessment: From Code to Diagrams
\\ 
</WRAP>
~~NOTOC~~

======Rules======
Open resource, closed person- do not communicate with anyone other than the instructor regarding material contained therein.

This is not take home- this is to be done during sanctioned times in the LAIR. If you do not finish, you may be able to resume work on following days (but note there may be additional content on following days).

There is the possibility of being asked to write code, debug, or draw diagrams-- all related to content and concepts we have covered.

======Reference Code======
Following will be common code utilized by the following questions:

=====Node Struct=====
<code c 1>
struct node {
    int value;
    struct node *next;
    struct node *prev;
};
</code>

=====List Struct=====
<code c 1>
struct list {
    struct node *start;
    struct node *end;
};
</code>

=====create() function=====
<code c 1>
struct node *create()
{
    struct node *tmp;
    tmp = (struct node *) malloc (sizeof(struct node));
    tmp -> prev = tmp -> next = NULL;
    tmp -> value = -1;
    return(tmp);
}
</code>

=====func1() function=====
<code c 1>
struct node *func1(int val)
{
    int i = 0, old = 0;
    struct node *tmp, *tmp2;
    
    tmp = tmp2 = create();
    
    tmp -> value = 1;
    
    for(i = 0; i < val; i++)
    {
        tmp2 -> next = create();
        tmp2 -> next -> value = tmp2 -> value + old;
        old = tmp2 -> value;
        tmp2 = tmp2 -> next;
    }
    tmp2 -> next = tmp;
    
    return(tmp2 -> next);
}
</code>

=====func2() function=====
<code c 1>
struct node *func2(int val)
{
    int i = 0;
    struct node *tmp, *tmp2;
    
    tmp2 = create();
    tmp = tmp2;
    
    tmp -> value = val;
    
    while (i < val)
    {
        tmp -> next = create();
        tmp -> next -> value = i;
        tmp = tmp -> next;
        i++;
    }
    return(tmp2);
}
</code>

=====func3() function=====
<code c 1>
struct node *func3()
{
    struct node *tmp, *tmp2;
    tmp = tmp2 = create();
    tmp2 -> next = create();
    
    tmp -> next -> prev = tmp2;
    
    return(tmp);
}
</code>

=====func4() function=====
<code c 1>
struct node *func4(struct node *tmp)
{
    while (tmp -> next != NULL)
    {
        tmp = tmp -> next;
    }
    return(tmp);
}
</code>

======Item 0x0======
Draw the diagram of the resulting linked data structure from a program that consists of the following:

<code c 1>
struct node *stuff;

stuff = func2(8);
</code>

Assume the state immediately following the function call, return, and resulting assignment to stuff.

======Item 0x1======
Draw the diagram of the resulting linked data structure from a program that consists of the following:

<code c 1>
int i = 5;
struct node *tmp, *tmp2, *a, *b, *c, *d;

b = c = tmp  = NULL;
d = tmp2 = a = NULL;

for(i = 0; i < 4; i++)
{
    if(tmp == NULL)
    {
        tmp2 = tmp = create();
        tmp -> value = i;
        tmp -> next = create();
        tmp -> next -> value = i + 4;
        a = tmp2 -> next;
        tmp = tmp -> next;
    }
    else
    {
        tmp -> next = create();
        tmp -> value = i;
        tmp -> next -> value = i + 4;
        
        if(i == 1)
            b = tmp -> next;
        else if(i == 2)
            c = tmp -> next;
        else
            d = tmp -> next;
        
        tmp = tmp -> next;
    }
}

tmp -> next = tmp2;
tmp -> value = i;
tmp = tmp -> next -> next -> next;
</code>

======Item 0x2======
Draw the diagram of the resulting linked data structure from a program that consists of the following:

<code c 1>
struct list *thing = (struct list *) malloc (sizeof(struct list));

thing -> start = func2(5);
thing -> end   = func4(thing -> start);
thing -> start -> next -> prev = func3();
thing -> start -> next -> next -> prev = func3();
thing -> end -> next = func1(7);
</code>

======Item 0x3======
Analyzing the above code and your resulting linked data structures:

  * What does the func1() function actually do?
  * What does the func2() function actually do?
  * What does the func4() function actually do?

======Submission======
Your produced output from this activity will be hand-drawn diagrams of various linked data structures (as well as responses to indicated questions).

As such, before leaving, please hand in any such papers-- even if not done, for there may be additional opportunities to work on it in future days.
Lab46 Wiki

User Tools

Site Tools

Page Tools
