Lab46 Wiki

User Tools

Site Tools

You are here: start » haas » fall2014 » data » projects » dska0-solution
haas:fall2014:data:projects:dska0-solution

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision		Previous revision
haas:fall2014:data:projects:dska0-solution [2014/10/31 21:54] – [Inversion/Negation] wedgehaas:fall2014:data:projects:dska0-solution [2014/10/31 22:38] (current) – [Linked List Code Inversion] wedge
Line 29: Line 29:
 {{ :haas:fall2014:data:projects:posll0.png |}} {{ :haas:fall2014:data:projects:posll0.png |}}
  
-Note that the NULL terminating the list is to the left of the list start... so again, an inversion or negation what we are used to seeing.+Note that the NULL terminating the list is to the left of the list start... so again, an inversion or negation of what we are used to seeing.
  
-The trick here is that we still view this list from left to right-- start is on the left (or beginning), and end is on the right (the contextual end). In this scenario, the connections work against the grain when using the list.+The trick here is that we still "view" this list from left to right-- start is on the left (or beginning), and end is on the right (the contextual end). In this scenario, the connections work against the grain when using the list.
  
 =====Appending===== =====Appending=====
Line 58: Line 58:
   * **insert()** in a next-oriented singly-linked list is functionally equivalent to **append()** in a previous-oriented singly-linked list   * **insert()** in a next-oriented singly-linked list is functionally equivalent to **append()** in a previous-oriented singly-linked list
   * **append()** in a next-oriented singly-linked list is functionally equivalent to **insert()** in a previous-oriented singly-linked list   * **append()** in a next-oriented singly-linked list is functionally equivalent to **insert()** in a previous-oriented singly-linked list
-  * To display the list from start to end in a previous-oriented singly-linked list, we effectively need to perform the **displayb()** logic.+  * To display the list from start to end in a previous-oriented singly-linked list, we effectively need to use the **displayb()** logic to assist us in our task.
  
 More precisely, to convert the next-oriented linked-list **insert()** into a previous-oriented linked-list **append()**: More precisely, to convert the next-oriented linked-list **insert()** into a previous-oriented linked-list **append()**:
   * all **next** references become **prev**   * all **next** references become **prev**
   * all references to **start** become **end**   * all references to **start** become **end**
-  * all references to **end** become **start**+  * all original references to **end** become **start**
  
-You'll see that, instead of seeking from the start of the list, we must seek from the end. And just as with next-insert(), which requires us to get to the node "before", prev-append() has the same need (it is the node before, when commencing from the end).+====positioning tmp==== 
 +You'll see that, instead of seeking from the start of the list, we must seek from the end. And just as with next-insert(), which requires us to get to the node "before", prev-append() has the same need (it is the node that connects to place, and we get here from the end of the list).
  
 The only difference here (if we were to implement **getpos()/setpos()** functionality), is that when considering list position values, instead of doing: The only difference here (if we were to implement **getpos()/setpos()** functionality), is that when considering list position values, instead of doing:
Line 81: Line 82:
 </code> </code>
  
-Obviously, since **getpos()/setpos()** functions were not provided, some sort of repetition is in order (most seemed to go with a while loop, starting from the end of the list-- an excellent choice).+Note the -1 and +1 difference. 
 +====navigating with while==== 
 +Obviously, since **getpos()/setpos()** functions were not provided, some sort of repetition is in order (many seemed to go with a while loop, starting from the end of the list-- an excellent choice).
  
 Likely, something of the form: Likely, something of the form:
Line 93: Line 96:
 </code> </code>
  
 +====average case connection====
 And then we could perform the necessary hook-ups (average case consideration): And then we could perform the necessary hook-ups (average case consideration):
  
Line 100: Line 104:
 </code> </code>
  
 +====edge case connections====
 As for edge cases, aside from dealing with similar NULL and empty list scenarios, the edge cases for prev-append() would be the same as those considered in next-insert(). As for edge cases, aside from dealing with similar NULL and empty list scenarios, the edge cases for prev-append() would be the same as those considered in next-insert().
  
   * next-insert() had special consideration for inserting before the start of the list   * next-insert() had special consideration for inserting before the start of the list
-  * prev-append() has special consideration for appending after the end of the list+  * prev-append() therefore has special consideration for appending after the end of the list
  
 Similarly, as we just observed with the while loop logic: Similarly, as we just observed with the while loop logic:
  
   * next-insert() had to locate the node one list position prior to place (coming from the direction of theList -> start)   * next-insert() had to locate the node one list position prior to place (coming from the direction of theList -> start)
-  * prev-append() has to locate the node one list position after place (coming from the direction of theList -> end)+  * prev-append() therefore has to locate the node one list position after place (coming from the direction of theList -> end)
  
 +=====example append() implementation=====
 +To aid in understanding, here is my reference implementation of append() for the previous-oriented singly-linked list:
  
 +<code c 1>
 +#include "list.h"
 +
 +//////////////////////////////////////////////////////////////////////
 +//
 +// append() - add newNode to the list after place
 +//
 +List *append(List *theList, Node *place, Node *newNode)
 +{
 +    //////////////////////////////////////////////////////////////////
 +    //
 +    // tmp will be our "after" pointer, allowing the side of the list
 +    // to the right of place to connect in to newNode
 +    //
 +    Node *tmp                   = NULL;
 +
 +    //////////////////////////////////////////////////////////////////
 +    //
 +    // edge case: should the list pointer be NULL, allocate a new List
 +    //            and initialize theList -> start and end to sane
 +    //            initial values. This is essentially what mklist()
 +    //            does in the sll projects.
 +    //
 +    if (theList                == NULL)
 +    {
 +        theList                 = (List *) malloc(sizeof(List));
 +        theList -> start        = NULL;
 +        theList -> end          = NULL;
 +    }
 +
 +    //////////////////////////////////////////////////////////////////
 +    //
 +    // edge case: the only thing that can gum up the works now is a
 +    //            NULL newNode; so if one is encountered, do nothing
 +    //            and return the list as-is.
 +    //
 +    if (newNode                != NULL)
 +    {
 +        //////////////////////////////////////////////////////////////
 +        //
 +        // edge case: if we have an empty list, newNode becomes the
 +        //            list contents.
 +        //
 +        if ((theList -> start  == NULL) &&
 +            (theList -> end    == NULL))
 +        {
 +            //////////////////////////////////////////////////////////////
 +            //
 +            // this is the simplest case- nothing exists so newNode IS
 +            // the list contents. Merely update the start and end
 +            // pointers and we're all set.
 +            //
 +            theList -> start    = newNode;
 +            theList -> end      = newNode;
 +        }
 +
 +        //////////////////////////////////////////////////////////////
 +        //
 +        // edge case: if we're appending after end, we need to take
 +        //            care to update theList -> end
 +        //
 +        else if (place         == theList -> end)
 +        {
 +            //////////////////////////////////////////////////////////////
 +            //
 +            // this is the next simplest case to connect, as we only have
 +            // to deal with one connection (hooking newNode into the list;
 +            // then update theList -> end as appropriate).
 +            //
 +            newNode -> prev     = theList -> end;
 +            theList -> end      = newNode;
 +        }
 +
 +        //////////////////////////////////////////////////////////////
 +        //
 +        // average case: if we're dealing with a typical append, we
 +        //               do the following. We're also protecting 
 +        //               against a rogue edge case of the list being
 +        //               non-empty yet place being NULL (trying to
 +        //               process that condition would result in 
 +        //               certain disaster).
 +        //
 +        else if (place         != NULL)
 +        {
 +            //////////////////////////////////////////////////////////////
 +            //
 +            // positioning tmp: we can only navigate from the end of the
 +            //                  list, so we must start tmp there; then,
 +            //                  keep seeking until we arrive at the node
 +            //                  one prev away from place.
 +            //
 +            tmp                 = theList -> end;
 +            while (tmp -> prev != place)
 +            {
 +                tmp             = tmp -> prev;
 +            }
 +
 +            //////////////////////////////////////////////////////////////
 +            //
 +            // connecting it: newNode connects to place, and the existing
 +            //                list node connecting to place hooks to
 +            //                newNode.
 +            //
 +            newNode -> prev     = place;
 +            tmp     -> prev     = newNode;
 +        }
 +    }
 +
 +    //////////////////////////////////////////////////////////////////
 +    //
 +    // whether we modify the list or bail out, we'll always return
 +    // the right thing.
 +    //
 +    return(theList);
 +}
 +</code>
haas/fall2014/data/projects/dska0-solution.1414792454.txt.gz · Last modified: 2014/10/31 21:54 by wedge

Page Tools

Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Share Alike 4.0 International
CC Attribution-Share Alike 4.0 International Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki