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:01] – [the stack] 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 112: | Line 124: | ||
| With that said, you likely only have to make changes to 4 functions in order to appropriately accommodate **qty**-- any low-level list operation that is responsible for initializing, | With that said, you likely only have to make changes to 4 functions in order to appropriately accommodate **qty**-- any low-level list operation that is responsible for initializing, | ||
| - | ====In inc/list.h==== | + | ====In inc/stack.h==== |
| <code c 1> | <code c 1> | ||
| - | # | + | # |
| - | # | + | # |
| - | + | ||
| - | #include " | + | |
| - | struct | + | #include "list.h" |
| - | | + | // (which relies on node) |
| - | Node *end; // pointer to end of list | + | struct stack { |
| + | | ||
| + | Node *top; // pointer to node at top of stack | ||
| + | int | ||
| }; | }; | ||
| - | typedef struct | + | typedef struct |
| - | List *mklist(void | + | Stack *mkstack(int ); // create new stack (of max size) |
| - | List *cplist(List *); | + | Stack *cpstack(Stack * |
| - | List *rmlist(List *); | + | Stack *rmstack(Stack * |
| - | List *insert | + | int push(Stack **, Node * ); // put new node on top of stack |
| - | List *append | + | int pop (Stack **, Node **); // grab (and disconnect) top node off stack |
| - | List *obtain | + | |
| - | void display(List *, int); | + | Node *peek(Stack * ); // grab (do not disconnect) top node off stack |
| + | int | ||
| + | #endif | ||
| + | </ | ||
| - | Node *findnode(List *, int); // locate node containing value | + | For our stack implementation, we will make increased used of the double pointer, in order to achieve passing parameters by address. |
| - | List *sortlist(List *, int); // sort list (according | + | |
| - | List *swapnode(List *, Node *, Node *); // swap positions of given nodes in list | + | This is necessary so that we can free up the return value of **push()** and **pop()** to be used for status (ie look out for stack overflows and underflows). |
| - | #endif | + | peek() and isEmpty() are being implemented as an exercise to aid in your understanding of stacks. Again, avoid their use except is a means of convenience (or to further optimize your code). The general rule of thumb is that the use of peek() and isEmpty() should result in shortening your code in a clear or clever way. |
| - | </code> | + | |
| - | The following changes have taken place: | + | If you cannot think of how to solve a problem without the use of peek()/ |
| - | | + | Also, while nothing is stopping you from doing so, the idea here is that things like **size** and the underlying |
| - | | + | |
| - | * **searchlist()** has been renamed to **findnode()** (aesthetic change, to keep function names at 8 characters or less). | + | |
| - | | + | |
| + | In object-oriented programming, | ||
| ====list library==== | ====list library==== | ||
| - | In **src/node/**, you will find skeletons | + | Againt, in **src/list/**, you are to add support for **qty** so that, just as the list's **start** and **end** maintain an accurate positioning of their respective aspects |
| - | In **src/list/**, you will find the same- skeletons of the above prototyped functions, hollowed out in anticipation of being made operational. | + | ===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== | ||
| + | < | ||
| + | 51 -> 49 -> 51 -> 51 -> 55 -> NULL | ||
| + | </ | ||
| + | |||
| + | ==mode 1: forward, with positions, as numbers== | ||
| + | < | ||
| + | [0] 51 -> [1] 49 -> [2] 51 -> [3] 51 -> [4] 55 -> NULL | ||
| + | </ | ||
| + | |||
| + | ==mode 4: forward, no positions, in ASCII== | ||
| + | < | ||
| + | ' | ||
| + | </ | ||
| + | |||
| + | ==mode 5: forward, with positions, in ASCII== | ||
| + | < | ||
| + | [0] ' | ||
| + | </ | ||
| + | |||
| + | ====stack library==== | ||
| + | In **src/stack/**, you will find skeletons of the above prototyped functions, hollowed out in anticipation of being made operational. | ||
| Figure out what is going on, the connections, | Figure out what is going on, the connections, | ||
| - | As ALL source files are now skeletons, no sample code has been given. This is intended | + | 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 187: | 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 198: | 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.1414846885.txt.gz · Last modified: 2014/11/01 13:01 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
