haas:fall2014:data:projects:dls0
Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
| haas:fall2014:data:projects:dls0 [2014/11/01 13:15] – [list library] wedge | haas:fall2014:data:projects:dls0 [2014/11/19 14:42] (current) – [Errata] wedge | ||
|---|---|---|---|
| Line 11: | Line 11: | ||
| This section will document any updates applied to the project since original release: | This section will document any updates applied to the project since original release: | ||
| - | * __revision | + | * __revision |
| + | * logic error in **unit-cpstack**, | ||
| + | * changed ending while to do-while loop | ||
| + | * loop conditions were originally (i == 0) && (status != 0), should have been != -1 for both | ||
| + | * missing double newline after certain " | ||
| + | * Some additional aesthetic enhancements to the base Makefile were made. | ||
| + | * __revision 2__: Makefile enhancements to facilitate project usage (20141107) | ||
| + | * test reference implementation feature enhancements | ||
| + | * a slight change to the option to enable (**make use-test-reference**) | ||
| + | * a new option to restore your own code (**make use-your-own-code**) | ||
| + | * **src/ | ||
| + | * **testing/ | ||
| + | * __revision 3__: verify-stack.sh enhancements (20141119) | ||
| + | * now includes absolute totals | ||
| =====Objective===== | =====Objective===== | ||
| Line 73: | Line 86: | ||
| * **peek**: the ability to gain access to the top node without removing it from the stack | * **peek**: the ability to gain access to the top node without removing it from the stack | ||
| * **is the stack empty?**: the ability to query the stack and determine if it is empty or non-empty (or perhaps if non-empty, how full is it?) | * **is the stack empty?**: the ability to query the stack and determine if it is empty or non-empty (or perhaps if non-empty, how full is it?) | ||
| - | * **purge**: the ability to empty/clear out the stack | ||
| While we may be implementing these supplemental functions, it should be noted that not only are they in no way necessary for using a stack, they could be detrimental (just as relying on **qty** in the sll projects was), as one could rely on them as a crutch. | While we may be implementing these supplemental functions, it should be noted that not only are they in no way necessary for using a stack, they could be detrimental (just as relying on **qty** in the sll projects was), as one could rely on them as a crutch. | ||
| Line 123: | Line 135: | ||
| List *data; | List *data; | ||
| Node *top; // pointer to node at top of stack | Node *top; // pointer to node at top of stack | ||
| - | int | + | int |
| }; | }; | ||
| typedef struct stack Stack; | typedef struct stack Stack; | ||
| Line 135: | Line 147: | ||
| Node *peek(Stack * ); // grab (do not disconnect) top node off stack | Node *peek(Stack * ); // grab (do not disconnect) top node off stack | ||
| - | int | + | int |
| #endif | #endif | ||
| </ | </ | ||
| Line 150: | Line 162: | ||
| In object-oriented programming, | In object-oriented programming, | ||
| + | ====list library==== | ||
| + | Againt, in **src/ | ||
| + | |||
| + | ===display() enhancements=== | ||
| + | You are also to implement 4 additional modes to the display() function. | ||
| + | |||
| + | This means you'll need to expand the current modulus divide by 4 to one of 8. | ||
| + | |||
| + | The current modes are as follows: | ||
| + | |||
| + | <code c> | ||
| + | // | ||
| + | // 1 display the list forward, with positional values | ||
| + | // 2 display the list backwards, no positional values | ||
| + | // 3 display the list backwards, with positional values | ||
| + | </ | ||
| + | |||
| + | The new modes are (you may want to add these comments to your **display.c** file): | ||
| + | |||
| + | <code c> | ||
| + | // 4 display the list forward, no positional values, in ASCII | ||
| + | // 5 display the list forward, with positional values, in ASCII | ||
| + | // 6 display the list backwards, no positional values, in ASCII | ||
| + | // 7 display the list backwards, with positional values, in ASCII | ||
| + | </ | ||
| + | |||
| + | What has changed? In modes 4-8, instead of displaying the numeric value contained in the node's data element, you are instead to represent it as its ASCII character. | ||
| + | |||
| + | For example, if there was a numeric 65 stored in the node , in the mode 4-7 representation, | ||
| + | |||
| + | ==display() output examples based on mode== | ||
| + | Let's say we have a list with the following elements: | ||
| + | |||
| + | start -> 51 -> 49 -> 51 -> 51 -> 55 -> NULL | ||
| + | |||
| + | ==mode 0: forward, no positions, as numbers== | ||
| + | <cli> | ||
| + | 51 -> 49 -> 51 -> 51 -> 55 -> NULL | ||
| + | </ | ||
| + | |||
| + | ==mode 1: forward, with positions, as numbers== | ||
| + | <cli> | ||
| + | [0] 51 -> [1] 49 -> [2] 51 -> [3] 51 -> [4] 55 -> NULL | ||
| + | </ | ||
| + | |||
| + | ==mode 4: forward, no positions, in ASCII== | ||
| + | <cli> | ||
| + | ' | ||
| + | </ | ||
| + | |||
| + | ==mode 5: forward, with positions, in ASCII== | ||
| + | <cli> | ||
| + | [0] ' | ||
| + | </ | ||
| + | |||
| ====stack library==== | ====stack library==== | ||
| In **src/ | In **src/ | ||
| Line 157: | Line 224: | ||
| Again, your stack is to utilize the stack for its underlying data storage operations. This is what the stack' | Again, your stack is to utilize the stack for its underlying data storage operations. This is what the stack' | ||
| - | ====List library unit tests==== | + | ====Reference Implementation==== |
| - | In **testing/ | + | As the layers and complexities rise, narrowing down the source of errors becomes increasingly important. |
| - | * **unit-append.c** - unit test for **append()** library function | + | If your stack push() isn't working, is it because of a problem in push()? Or might it be in an underlying list operation it relies upon? Or perhaps even the lowest-level node functions.. |
| - | * **unit-insert.c** - unit test for **insert()** library function | + | |
| - | * **unit-swapnode.c** - unit test for **swapnode()** library function | + | |
| - | * **unit-sortlist.c** - unit test for **sortlist()** library function | + | |
| - | * **unit-display.c** - unit test for **display()** library function | + | |
| - | Additional unit tests will be provided via dll0 project | + | To aid you in your development efforts, you now have the ability to import a functioning node and list implementation into your project |
| - | There are also corresponding **verify-FUNCTION.sh** scripts that will output a " | + | This also provides another opportunity for those who have fallen behind |
| - | 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). | + | ===Using the test reference implementation=== |
| + | You'll notice that, upon running **make help** in the base-level Makefile, the following new options appear (about halfway in the middle): | ||
| + | |||
| + | < | ||
| + | ** ** | ||
| + | ** make use-test-reference | ||
| + | ** make use-your-own-code | ||
| + | ** ** | ||
| + | </ | ||
| + | |||
| + | In order to make use of it, you'll need to run **make use-test-reference** from the base of your **dls0** project directory, as follows: | ||
| + | |||
| + | < | ||
| + | lab46: | ||
| + | make[1]: Entering directory '/ | ||
| + | make[2]: Entering directory '/ | ||
| + | rm -f *.swp *.o append.o cp.o display.o insert.o mk.o obtain.o rm.o search.o sort.o swap.o core | ||
| + | make[2]: Leaving directory '/ | ||
| + | make[2]: Entering directory '/ | ||
| + | rm -f *.swp *.o cp.o mk.o rm.o core | ||
| + | make[2]: Leaving directory '/ | ||
| + | make[2]: Entering directory '/ | ||
| + | rm -f *.swp *.o cp.o isempty.o mk.o peek.o pop.o push.o rm.o core | ||
| + | make[2]: Leaving directory '/ | ||
| + | make[1]: Leaving directory '/ | ||
| + | make[1]: Entering directory '/ | ||
| + | make[2]: Entering directory '/ | ||
| + | make[3]: Entering directory '/ | ||
| + | rm -f *.swp *.o ../ | ||
| + | make[3]: Leaving directory '/ | ||
| + | make[2]: Leaving directory '/ | ||
| + | make[2]: Entering directory '/ | ||
| + | make[3]: Entering directory '/ | ||
| + | rm -f *.swp *.o ../ | ||
| + | make[3]: Leaving directory '/ | ||
| + | make[2]: Leaving directory '/ | ||
| + | make[2]: Entering directory '/ | ||
| + | make[3]: Entering directory '/ | ||
| + | rm -f *.swp *.o ../ | ||
| + | make[3]: Leaving directory '/ | ||
| + | make[3]: Entering directory '/ | ||
| + | rm -f *.swp *.o ../ | ||
| + | make[3]: Leaving directory '/ | ||
| + | make[2]: Leaving directory '/ | ||
| + | make[1]: Leaving directory '/ | ||
| + | NODE and LIST reference implementation in place, run ' | ||
| + | lab46: | ||
| + | </ | ||
| + | |||
| + | You'll see that final message indicating everything is in place (it automatically runs a **make clean** for you), and then you can go ahead and build everything with it: | ||
| + | |||
| + | < | ||
| + | lab46: | ||
| + | ... | ||
| + | </ | ||
| + | |||
| + | **__Debugging__: | ||
| + | |||
| + | ===Reverting back to using your code=== | ||
| + | If you were trying out the reference implementation to verify stack functionality, | ||
| + | |||
| + | < | ||
| + | lab46: | ||
| + | Local node/list implementation restored, run 'make clean; make' to build everything. | ||
| + | lab46: | ||
| + | </ | ||
| + | ====List Library unit tests==== | ||
| + | As a result of the required changes to **display()** and the incorporation of **qty**, pertinent list unit tests will be enhanced, so you can make use of them to ensure implementation compliance. | ||
| + | |||
| + | Be sure to run the various list unit tests and verification scripts to see which functions have fallen out of compliance with the list struct specification changes issued in this project. The **verify-list.sh** script can be especially useful in getting a big picture view of what work is needed. | ||
| + | ====Stack library unit tests==== | ||
| + | In **testing/ | ||
| + | |||
| + | * **unit-mkstack.c** - unit test for **mkstack()** library function | ||
| + | * **unit-cpstack.c** - unit test for **cpstack()** library function | ||
| + | * **unit-rmstack.c** - unit test for **rmstack()** library function | ||
| + | * **unit-push.c** - unit test for **push()** library function | ||
| + | * **unit-pop.c** - unit test for **pop()** library function | ||
| + | * **unit-peek.c** - unit test for **peek()** library function | ||
| + | * **unit-isempty.c** - unit test for **isempty()** library function | ||
| + | |||
| + | There are also corresponding **verify-FUNCTION.sh** scripts that will output a " | ||
| + | |||
| + | These are complete runnable programs (when compiled, and linked against the stack library, which is all handled for you by the **Makefile** system in place). | ||
| Of particular importance, I want you to take a close look at: | Of particular importance, I want you to take a close look at: | ||
| Line 184: | Line 330: | ||
| * ask questions to get clarification! | * ask questions to get clarification! | ||
| + | ====stack testing applications==== | ||
| + | |||
| + | ===palindrome-stack=== | ||
| + | Now that we've completed our stack functionality, | ||
| + | |||
| + | Our task (once again) will be that of palindromes (ie words/ | ||
| + | |||
| + | This implementation will be considered an extra credit opportunity, | ||
| + | |||
| + | It is also highly recommended to undertake as it will give you further experience working with these concepts. | ||
| + | |||
| + | Note this is a DIFFERENT approach than you would have taken in the program with sll2- you're to use stack functionality to aid you with the heavy lifting. While you will still make use of list functionality for grabbing the initial input, the actual palindrome comparison processing needs to heavily involve stacks. | ||
| + | |||
| + | =====Expected Results===== | ||
| + | To assist you in verifying a correct implementation, | ||
| + | |||
| + | ====node library==== | ||
| + | Here is what you should get for node: | ||
| + | |||
| + | <cli> | ||
| + | lab46: | ||
| + | ==================================================== | ||
| + | = Verifying Doubly-Linked Node Functionality | ||
| + | ==================================================== | ||
| + | [mknode] Total: | ||
| + | [cpnode] Total: | ||
| + | [rmnode] Total: | ||
| + | ==================================================== | ||
| + | | ||
| + | ==================================================== | ||
| + | lab46: | ||
| + | </ | ||
| + | |||
| + | As no coding changes were needed in the node library, these results should be identical to that of a fully functioning node implementation from the **dll0** project. | ||
| + | |||
| + | ====list library==== | ||
| + | Here is what you should get for list: | ||
| + | |||
| + | <cli> | ||
| + | lab46: | ||
| + | ==================================================== | ||
| + | = Verifying Doubly-Linked List Functionality | ||
| + | ==================================================== | ||
| + | [mklist] Total: | ||
| + | [cplist] Total: | ||
| + | [rmlist] Total: | ||
| + | [append] Total: | ||
| + | [insert] Total: | ||
| + | [obtain] Total: | ||
| + | | ||
| + | [findnode] Total: | ||
| + | [sortlist] Total: | ||
| + | [swapnode] Total: | ||
| + | ==================================================== | ||
| + | | ||
| + | ==================================================== | ||
| + | lab46: | ||
| + | </ | ||
| + | |||
| + | Due to the re-introduction of **qty** into list (impacting actions performed by **mklist()**, | ||
| + | |||
| + | Remember though- aside from the minor change of adding **qty** and enhancing **display()**, | ||
| + | |||
| + | ====stack library==== | ||
| + | Here is what you should get for stack: | ||
| + | |||
| + | <cli> | ||
| + | lab46: | ||
| + | =================================================== | ||
| + | = | ||
| + | =================================================== | ||
| + | [mkstack] Total: | ||
| + | [cpstack] Total: | ||
| + | [rmstack] Total: | ||
| + | | ||
| + | [pop] Total: | ||
| + | | ||
| + | [isempty] Total: | ||
| + | =================================================== | ||
| + | [RESULTS] Total: 106, Matches: 106, Mismatches: | ||
| + | =================================================== | ||
| + | lab46: | ||
| + | </ | ||
| =====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 195: | Line 424: | ||
| * output formatted, where applicable, must match that of project requirements | * output formatted, where applicable, must match that of project requirements | ||
| * Processing must be correct based on input given and output requested | * Processing must be correct based on input given and output requested | ||
| - | * Output must be correct | + | * Output, if applicable, |
| * 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 | ||
haas/fall2014/data/projects/dls0.1414847723.txt.gz · Last modified: 2014/11/01 13:15 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
