Lab46 Wiki

User Tools

Site Tools

You are here: start » haas » fall2014 » data » projects » sll2
haas:fall2014:data:projects:sll2

Differences

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

Link to this comparison view

Next revision		Previous revision
haas:fall2014:data:projects:sll2 [2014/03/23 13:41] – external edit 127.0.0.1haas:fall2014:data:projects:sll2 [2014/11/03 12:38] (current) – [Errata] wedge
Line 6: Line 6:
 ~~TOC~~ ~~TOC~~
  
-======Project: SLL2: Singly-Linked Stacks======+======Project: SLL2======
  
-=====Overview===== +=====Errata===== 
-We will be extending our sll1 project in sll2 with the addition of singly-linked list-based stacks.+This section will document any updates applied to the project since original release:
  
-=====Update and Upgrade===== +  * __revision 1__: In anticipation for the release of our next project (**dll0**), I have made some tweaks to the base Makefile to allow for a smoother transition at project upgrade time. (20141026) 
-For this project, you'll update your **sll1** project to gain access to the new **upgrade-sll2** option in the Makefile:+  * __revision 2__: Typo in my original tweak preventing it from working. Now that I've tested it, we have a working solution, and dll0 can now be properly upgraded to... be sure to update before upgrading! (20141027) 
 +  * __revision 3__: Typo with for loop iterations (one too many) in unit-sortlist... now fixed. It makes a backup copy of the original, should any additional local changes have been made. (20141028) 
 +  * __revision 4__: Base Makefile aesthetic enhancements (20141103)
  
-====Step 0. Change into project directory==== +=====Objective===== 
-Change to wherever you copied your code (I'm assuming **~/src/data/sll1** in my example):+In this project, we wrap up our singly-linked list implementation by exploring the reverse display and sorting of nodes in a list, along with writing a few application programs to see our list in action.
  
-<cli> +=====Project Overview=====
-lab46:~$ cd src/data/sll1 +
-lab46:~/src/data/sll1$  +
-</cli>+
  
-====Step 1. Update to latest release (preserves your code)====+For this project, we're going to be implementing the following functions:
  
-<cli> +<code c> 
-lab46:~/src/data/sll1$ make update +List *sortlist(List *, int);  // sort list (according to mode) 
-... +void  displayb(List *, int);  // display list in reverse order 
-</cli>+</code>
  
-====Step 2. Upgrade to sll2 project (copies over your code)==== +====list library==== 
-<cli> +In **src/list/**, you will find 2 new C files:
-lab46:~/src/data/sll1$ make upgrade-sll2 +
-... +
-</cli>+
  
-====Step 3. Change into sll2 directory====+  * **sort.c**     - which will house the list sort function 
 +  * **displayb.c** - which will handle displaying the list backwards
  
-<cli> +Take a look at the code there. These are the files that contain functions which will be compiled and archived into the node library (**liblist.a**) we will be using in this and future projects.
-lab46:~/src/data/sll1$ cd ../sll2 +
-lab46:~/src/data/sll2$  +
-</cli>+
  
-=====Layout===== +Figure out what is going on, make sure you understand it.
-This project codebase is largely identical to the sll1 codebase; it merely adds the new files for the stack functionality. Be sure to check for new files in the following directories:+
  
-  * inc - stack.h header +====List library unit tests==== 
-  * src/stack - source code for the stack operations +In **testing/list/unit/**, you will find these new files:
-  * testing - stacktest.c file (may work)+
  
-=====Stacks===== +  * **unit-sortlist.c** - unit test for **sortlist()** library function 
-A stack is another data structure, which is very heavily and widely used throughout computing and our everyday lives.+  * **unit-displayb.c** - unit test for **displayb()** library function
  
-It works on a principle of "last-in, first-out" (LIFO)... for our purposes it will be a restricted access linked list (one where only the "top" node can be accessed).+These are complete runnable programs (when compiled, and linked against the list library, which is all handled for you by the **Makefile** system in place).
  
-This restriction of access creates new possibilities for algorithms, enabling useful functionality.+Of particular importance, I want you to take a close look at:
  
-The basic stack operations are: **push()** and **pop()** which will call the necessary underlying list operations (likely **append()** and **getNode()**) while maintaining the **top** pointer (reflecting some pointer in the underlying list, perhaps **end**).+  * the source code to each of these unit tests 
 +    * the purpose of these programs is to validate the correct functionality of the respective library functions 
 +    * follow the logic 
 +    * make sure you understand what is going on 
 +    * ask questions to get clarification! 
 +  * the output from these programs once compiled and ran 
 +    * analyze the output 
 +    * make sure you understand what is going on 
 +    * ask questions to get clarification!
  
-The stack has a **size** variable, which unlike the list's **qty** (which keeps track of how many nodes are in the list at any given time), **size** mandates a maximum size a stack can be (if the **qty** has reached **size**, no new nodes should be added (i.e. **push()**ed)- this is what is known as a **stack overflow condition**)). For purposes of flexibility, a **size** of zero denotes an unbounded stack (it can grow indefinitely, just like a list).+====list testing applications====
  
-There is often a **peek()** operation also provided with many stack implementations. It is by no means necessary (the underlying functionality can be entirely accomplished, perhaps less efficiently, with just **pop()** and **push()**. It is included here for additional practice and potential usage. +===palindrome=== 
-=====Errata===== +Now that we've completed our list functionality, we can use these individual functions to piece together solutions to various everyday problems where a list could be effective. After all, that's a big aspect to learning data structures- they open doors to new algorithms and problem solving capabilities.
-====03/20/2014==== +
-  * **Update 1**: testing/stacktest.c, when run, issues a rather nasty error (double free)... it looks like I forgot to check for a NULL case. Fix has been issued (hopefully will resolve it; if not, another fix forthcoming). +
-  * By request, I've changed the deadline of sll2 to sunday instead of friday. You're welcome.+
  
-====03/22/2014==== +Our first endeavor will be that of palindromes (ie words/phrases that, when reversed, spell the same thing).
-  * **Update 2**: Minor tweaks to testing/stacktest.c; might make usage clearer. +
-  * Provides upgrade path to the new **dll1** project (your next potential code rewrite)+
  
-====03/23/2014==== +This implementation will be considered an extra credit opportunity, so as to offer those who have fallen behind (but working to get caught up) a reprieve on some of the credit they've lost.
-  * **Update 3**: Think I found the problem with **testing/stacktest.c** +
-  * Implemented another stack test program: **testing/palindrome2.c** +
-  * Apparently update 2 never copied over the Makefile, this one does +
-=====Submission===== +
-To successfully complete this project, the following criteria must be met:+
  
-  * All code must compile cleanly (no warnings or errors)+It is also highly recommended to undertake as it will give you further experience working with these concepts. 
 +=====Submission Criteria===== 
 +To be successful in this project, the following criteria must be met: 
 + 
 +  * Project must be submit on time, by the posted deadline. 
 +    * The late submission window, if any, will be far shorter and once closed, will see no project evaluations done. 
 +  * Code must compile cleanly (no warnings or errors) 
 +    * all requested functions must be implemented in the related library 
 +    * all requested functionality must conform to stated requirements (either on this project page or in comment banner in source code files themselves). 
 +  * Executed programs must display in a manner similar to provided output 
 +    * output formatted, where applicable, must match that of project requirements 
 +  * Processing must be correct based on input given and output requested 
 +  * Output must be correct (i.e. the list visualization, where applicable) based on values input
   * Code must be nicely and consistently indented (you may use the **indent** tool)   * Code must be nicely and consistently indented (you may use the **indent** tool)
   * Code must be commented   * Code must be commented
-  * Resulting libraries must be operational and functionally correct +    * Any "to be implemented" comments **MUST** be removed 
-    * stack functions must operate as described, conforming to provided function prototypes +    * Sufficient comments explaining the point of provided logic **MUST** be present
-    * code must make use of the other node/list functions as appropriate- do not reinvent the wheel +
-    * evaluations of libraries using various unit tests will be an assessment criteria+
   * Track/version the source code in a repository   * Track/version the source code in a repository
-  * Submit a copy of your source code to me using the **submit** tool (or **make submit**). +  * Submit a copy of your source code to me using the **submit** tool (**make submit** will do this) by the deadline.
- +
-To submit this program to me using the base Makefile, run the following command at your lab46 prompt: +
- +
-<cli> +
-lab46:~/src/data/sll2$ make submit +
-... +
-Submitting data project "sll2": +
-    -> sll2-20140317-18.tar.gz(OK) +
- +
-SUCCESSFULLY SUBMITTED +
-</cli> +
- +
-You should get some sort of confirmation indicating successful submission if all went according to plan. If not, check for typos and or locational mismatches. +
- +
-====Saving your work==== +
-To submit the project, you will need to create an archive and submit that using the submit tool: +
- +
-<cli> +
-lab46:~/src/data/sll2$ make save +
-... make save now issues a pre-emptive make clean ... +
-Archiving the project ... +
-Compressing the archive ... +
-Setting permissions ... +
-lab46:~/src/data/sll2$ cd .. +
-lab46:~/src/data$ ls sll2*gz +
-sll2-20140317-18.tar.gz +
-lab46:~/src/data$  +
-</cli> +
haas/fall2014/data/projects/sll2.1395582066.txt.gz · Last modified: 2014/10/05 20:22 (external edit)

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