haas:fall2014:data:projects:dls0
Differences
This shows you the differences between two versions of the page.
| Next revision | Previous revision | ||
| haas:fall2014:data:projects:dls0 [2014/11/01 12:11] – created 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 74: | Line 87: | ||
| * **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?) | ||
| - | There | + | 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. |
| + | |||
| + | Their inclusion should ONLY be viewed as a means of convenience (in certain scenarios they may result in less code needing to be written), but NOT as something you should routinely make use of. | ||
| + | ====size can matter==== | ||
| + | |||
| + | With a stack, there sometimes exists a need to cap its total size (especially in applications on the computer, we may have only allocated a fixed amount of space and cannot exceed it). For this reason, we will need to maintain a count of nodes in the stack (ie the underlying list). For this reason, **qty** makes an appearance once again in the list struct. | ||
| + | |||
| + | Additionally, | ||
| + | |||
| + | It should also be pointed out that in other applications, | ||
| + | |||
| + | ====stack error conditions==== | ||
| + | There are two very important operational error conditions a stack can experience: | ||
| + | |||
| + | * __stack **over**flow__: | ||
| + | * __stack **under**flow__: | ||
| =====Project Overview===== | =====Project Overview===== | ||
| - | For this project, we're going to be re-implementing | + | For this project, we're going to be implementing |
| + | ====In inc/ | ||
| + | There is one change (an addition) that has been made to **list.h**, and that is the return of the **qty** element: | ||
| - | ====In inc/ | + | <code c> |
| - | <code c 1> | + | struct list { |
| - | #ifndef _NODE_H | + | Node *start; |
| - | #define _NODE_H | + | Node *end; // pointer to end of list |
| + | int | ||
| + | }; | ||
| + | typedef struct list List; // because we deserve nice things | ||
| + | </ | ||
| - | #include <stdlib.h> | + | It should be noted (and stressed) that the utilization of **qty** should JUST be in maintaining a count. You need not re-implement or change the logic of any of your list functionality to base its operations or to rely on **qty** in any way (just as before, if you do you'll lost credit). |
| + | |||
| + | From the list's point of view, its sole purpose is for show. | ||
| + | |||
| + | 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/stack.h==== | ||
| + | |||
| + | <code c 1> | ||
| + | #ifndef _STACK_H | ||
| + | #define _STACK_H | ||
| - | struct | + | #include " |
| - | | + | // (which relies on node) |
| - | | + | struct stack { |
| - | struct | + | List *data; // pointer to list containing data |
| + | | ||
| + | int size; // maximum stack size (0 is unbounded) | ||
| }; | }; | ||
| - | typedef struct | + | typedef struct |
| - | Node *mknode(char | + | Stack *mkstack(int ); // create |
| - | Node *rmnode(Node *); | + | Stack *cpstack(Stack * |
| - | Node *cpnode(Node *); | + | Stack *rmstack(Stack * |
| + | int push(Stack **, Node * ); // put new node on top of stack | ||
| + | int pop (Stack **, Node **); // grab (and disconnect) top node off stack | ||
| + | |||
| + | Node *peek(Stack * ); // grab (do not disconnect) top node off stack | ||
| + | int isempty(Stack * ); // determine if the stack is empty or not | ||
| #endif | #endif | ||
| </ | </ | ||
| - | There is an addition | + | For our stack implementation, |
| - | The node value element has been renamed | + | This is necessary so that we can free up the return |
| - | ====In inc/list.h==== | + | 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 c 1> | + | If you cannot think of how to solve a problem without the use of peek()/ |
| - | #ifndef _LIST_H | + | |
| - | #define _LIST_H | + | |
| - | #include "node.h" | + | Also, while nothing is stopping you from doing so, the idea here is that things like **size** and the underlying list **qty** in stack transactions will **NOT** be accessed outside of the push() and pop() functions. Just like my warnings about using **qty** in your list solutions-- do not consider **size** as a variable for your general use. |
| - | struct | + | In object-oriented programming, |
| - | | + | ====list library==== |
| - | Node *end; // pointer to end of list | + | 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 |
| - | }; | + | |
| - | typedef struct list List; // because we deserve nice things | + | |
| - | List *mklist(void | + | ===display() enhancements=== |
| - | List *cplist(List *); // copy (duplicate) list | + | You are also to implement 4 additional modes to the display() function. |
| - | List *rmlist(List *); // remove all nodes from list | + | |
| - | List *insert (List *, Node *, Node *); // add node before given node | + | This means you'll need to expand the current modulus divide by 4 to one of 8. |
| - | List *append (List *, Node *, Node *); // add node after given node | + | |
| - | List *obtain (List *, Node ** | + | |
| - | void display(List *, int); // display list according to mode | + | The current modes are as follows: |
| - | Node *findnode(List *, int); | + | <code c> |
| - | List *sortlist(List *, int); | + | // |
| + | // 1 display the list forward, with positional values | ||
| + | // 2 display the list backwards, no positional values | ||
| + | // 3 display the list backwards, with positional values | ||
| + | </ | ||
| - | List *swapnode(List *, Node *, Node *); // swap positions of given nodes in list | + | The new modes are (you may want to add these comments to your **display.c** file): |
| - | #endif | + | <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 | ||
| </ | </ | ||
| - | The following changes have taken place: | + | 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. |
| - | * **qty** has been removed from the list; any code you wrote that is based on it will need to be implemented | + | For example, if there was a numeric 65 stored in the node , in the mode 4-7 representation, an ' |
| - | * **getpos()**/ | + | |
| - | * **searchlist()** has been renamed to **findnode()** (aesthetic change, to keep function names at 8 characters or less). | + | |
| - | * **displayf()/ | + | |
| - | ====list | + | ==display() output examples based on mode== |
| - | In **src/ | + | Let's say we have a list with the following elements: |
| - | In **src/list/**, you will find the same- skeletons of the above prototyped functions, hollowed out in anticipation of being made operational. | + | 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 179: | 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 190: | 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.1414843872.txt.gz · Last modified: 2014/11/01 12:11 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
