Lab46 Wiki

User Tools

Site Tools

You are here: start » haas » spring2015 » data » projects » sln0
haas:spring2015:data:projects:sln0

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:spring2015:data:projects:sln0 [2015/01/28 14:10] – [removing a node] wedgehaas:spring2015:data:projects:sln0 [2015/01/29 00:19] (current) – wedge
Line 18: Line 18:
 This gets us into a central theme of the course which we'll be running with from now until the end- the idea of a linked nodes, or in our current case: singly-linked nodes. This gets us into a central theme of the course which we'll be running with from now until the end- the idea of a linked nodes, or in our current case: singly-linked nodes.
  
-=====Project Overview=====+=====Overview=====
  
 For this project, we will explore a variation of C-like pseudo-code and drawings. For this project, we will explore a variation of C-like pseudo-code and drawings.
Line 40: Line 40:
 As such, if we were to have a solitary node containing a 17, and pointing at nothing (NULL), it could be drawn as follows: As such, if we were to have a solitary node containing a 17, and pointing at nothing (NULL), it could be drawn as follows:
  
-**PICTURE OF NODE**+{{ :haas:spring2015:data:projects:sln0-0.png |}}
  
 ===names and nodes=== ===names and nodes===
Line 52: Line 52:
 So here is a picture of what that same node would look like, while also associating a variable known as **start** with it. So here is a picture of what that same node would look like, while also associating a variable known as **start** with it.
  
-**PICTURE OF NAMED NODE**+{{ :haas:spring2015:data:projects:sln0-1.png |}}
  
 ===temporary node variables=== ===temporary node variables===
Line 62: Line 62:
 <code c> <code c>
 tmp = start; tmp = start;
-</code+</code>
  
 And that would produce the following result: And that would produce the following result:
  
-**IMAGE of node with tmp and start**+{{ :haas:spring2015:data:projects:sln0-2.png |}}
  
 Note that **tmp** does **NOT** point to **start**, which points to the node-- instead, **tmp** points to what **start** points to. This is very important. Note that **tmp** does **NOT** point to **start**, which points to the node-- instead, **tmp** points to what **start** points to. This is very important.
Line 80: Line 80:
 That would leave us with the following image: That would leave us with the following image:
  
-**IMAGE of updated node**+{{ :haas:spring2015:data:projects:sln0-3.png |}}
  
 ===connecting two nodes together=== ===connecting two nodes together===
 If we had a second node, **tmp2**, containing a 37 and pointing at nothing, we'd have a scenario like this: If we had a second node, **tmp2**, containing a 37 and pointing at nothing, we'd have a scenario like this:
  
-**IMAGE of two nodes**+{{ :haas:spring2015:data:projects:sln0-4.png |}}
  
 If we wanted start's node to point to tmp2's node, we'd want to do something like this: If we wanted start's node to point to tmp2's node, we'd want to do something like this:
Line 97: Line 97:
 The result of that assignment results in the following: The result of that assignment results in the following:
  
-**IMAGE of two connected nodes**+{{ :haas:spring2015:data:projects:sln0-5.png |}}
  
 ===connecting a new node, which becomes the start=== ===connecting a new node, which becomes the start===
 What if we were to add a third node to our scenario (containing a 48): What if we were to add a third node to our scenario (containing a 48):
  
-**IMAGE of our nodes**+{{ :haas:spring2015:data:projects:sln0-6.png |}}
  
 We have our existing two connected nodes, and our new node, currently identified by **tmp3**. We have our existing two connected nodes, and our new node, currently identified by **tmp3**.
Line 114: Line 114:
 </code> </code>
  
-**IMAGE of result**+{{ :haas:spring2015:data:projects:sln0-7.png |}}
  
 BUT: the intention of having **start** is to always have it pointing at the FIRST node in our list. So, as a result of that assignment, we need to re-assign start. BUT: the intention of having **start** is to always have it pointing at the FIRST node in our list. So, as a result of that assignment, we need to re-assign start.
Line 126: Line 126:
 That results in the following: That results in the following:
  
-**IMAGE of list of 3 nodes**+{{ :haas:spring2015:data:projects:sln0-8.png |}}
  
 Note that, at any point, the tmp/tmp2/tmp3 variables can go away, yet we'd still have control over our nodes (via start): Note that, at any point, the tmp/tmp2/tmp3 variables can go away, yet we'd still have control over our nodes (via start):
Line 134: Line 134:
 </code> </code>
  
-**IMAGE of 3 nodes**+{{ :haas:spring2015:data:projects:sln0-9.png |}}
  
 If it hasn't become obvious yet, drawing pictures like this (especially in a step-by-step manner) will be invaluable in aiding you through both debugging and solving these various tasks you'll face this semester. If it hasn't become obvious yet, drawing pictures like this (especially in a step-by-step manner) will be invaluable in aiding you through both debugging and solving these various tasks you'll face this semester.
Line 151: Line 151:
 The picture drawn should resemble: The picture drawn should resemble:
  
-**IMAGE**+{{ :haas:spring2015:data:projects:sln0-a.png |}}
  
 ====Copying a node==== ====Copying a node====
Line 164: Line 164:
 Which would give us: Which would give us:
  
-**IMAGE**+{{ :haas:spring2015:data:projects:sln0-b.png |}}
  
 Note that assigning a variable to an existing node is NOT the same as copying. If we were to say: Note that assigning a variable to an existing node is NOT the same as copying. If we were to say:
Line 174: Line 174:
 Does this create another copy? NO. It merely creates a scenario where two variables reference one node: Does this create another copy? NO. It merely creates a scenario where two variables reference one node:
  
-**IMAGE**+{{ :haas:spring2015:data:projects:sln0-c.png |}}
  
 ====Removing a node==== ====Removing a node====
Line 187: Line 187:
 The result will be this: The result will be this:
  
-**IMAGE**+{{ :haas:spring2015:data:projects:sln0-d.png |}}
  
 We can run into interesting situations when we remove a node that has multiple variables pointing at it. For instance-- tmp and tmp3. If we were to say: We can run into interesting situations when we remove a node that has multiple variables pointing at it. For instance-- tmp and tmp3. If we were to say:
Line 197: Line 197:
 We'd potentially end up with the following scenario: We'd potentially end up with the following scenario:
  
-**IMAGE**+{{ :haas:spring2015:data:projects:sln0-e.png |}}
  
 That's because when we de-allocate, it doesn't immediately go away, but is merely marked for removal. We should not rely on that data being there, even though it may still be accessible. That's because when we de-allocate, it doesn't immediately go away, but is merely marked for removal. We should not rely on that data being there, even though it may still be accessible.
Line 205: Line 205:
 So, in the case of nodes with multiple variable references, if we care about those variables, we should take care to properly set them. So, in the case of nodes with multiple variable references, if we care about those variables, we should take care to properly set them.
  
 +=====Project=====
 +Last week's project used an array to perform various transactions on a collection of items. What was the array will become a set of nodes, linked together in the fashion described in this project.
 +
 +We used nodes in a productive manner- under the guise of a list, which is merely a way of organizing nodes.
 +
 +It is important to note, with a list, that any anchoring variables (such as **start**) MUST point to their respective part of the list. If a change results in the invalidation or alteration of that variable's position, it MUST be adjusted so that it can retain its value as a list marker.
 +
 +Temporary variables come and go.. feel free to make use of them as needed; just make sure you don't overcomplicate a problem by using too many.
 +
 +For this project, I would like for you to write me the necessary pseudocode and/or draw the necessary step-by-step pictures to correctly accomplish the following:
 +
 +====Building a list====
 +Let's say we had a list generated with the following:
 +
 +<code c>
 +start = tmp = mknode(2)
 +tmp -> after = mknode(4)
 +tmp = tmp -> after
 +start -> after -> after = mknode(8)
 +tmp = tmp -> after
 +tmp -> after = mknode(16)
 +</code>
 +
 +What does the resulting list look like? Where are the start and tmp variables pointing?
 +
 +====Inserting into the list====
 +Write the code and draw the pictures to show the steps necessary for putting a new node (containing a 6) BEFORE the node containing an 8
 +
 +====Inserting into the list====
 +Assuming you do not know the composition of the list, write the code and draw the pictures to show the steps necessary for putting a new node (containing a 0) BEFORE the node containing a 2
 +
 +====Displaying the list====
 +Assuming you do not know the composition of the list, write the code to display the list contents from start to end (end is defined as when after becomes NULL)
 +
 +====Appending to the list====
 +Assuming you do not know the composition of the list, write the code and draw the pictures to show the steps necessary for putting a new node (containing a 1) after the node containing a 0
 +
 +====Grabbing from the list====
 +Assuming you do not know the composition of the list, write the code and draw the pictures to show the steps necessary for taking the node containing 6 and disconnecting it from the list. You may deallocate the node once properly disconnected.
 +
 +====Appending to the list====
 +Assuming you do not know the composition of the list, write the code and draw the pictures to show the steps necessary for putting a new node (containing a 12) after the node containing an 8
 +
 +====Copying the list====
 +Assuming you do not know the composition of the list, write the code and draw the pictures to show the steps necessary for taking the existing list (as referenced by start), and make a copy of that list, where the copied list is referenced by a variable called start2.
 +
 +====Grabbing from the list====
 +Assuming you do not know the composition of the list, write the code and draw the pictures to show the steps necessary for taking the node containing 0 (from the copied list) and disconnecting it from that list. You may deallocate the node once properly disconnected.
 +
 +====Final Results====
 +Draw pictures showing the final states of both lists, with respective variables pointing to nodes (or NULL, as appropriate).
 =====Submission Criteria===== =====Submission Criteria=====
 To be successful in this project, the following criteria must be met: To be successful in this project, the following criteria must be met:
Line 226: Line 277:
  
 ====Submit Tool Usage==== ====Submit Tool Usage====
-Let's say you have completed work on the project, and are ready to submit, you would do the following (assuming you have a program called arraylist.c):+Let's say you have completed work on the project, and are ready to submit, you would do the following (assuming you have a program called list.txt):
  
 <cli> <cli>
-lab46:~/src/data/sln0$ submit data sln0 arraylist.c+lab46:~/src/data/sln0$ submit data sln0 list.txt
 Submitting data project "sln0": Submitting data project "sln0":
-    -> arraylist.c(OK) +    -> list.txt(OK) 
  
 SUCCESSFULLY SUBMITTED SUCCESSFULLY SUBMITTED
haas/spring2015/data/projects/sln0.1422454234.txt.gz · Last modified: 2015/01/28 14:10 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