Corning Community College CSCS2320 Data Structures ~~TOC~~ ======Project: DLL1: Doubly-Linked Lists (and Queues)====== =====Overview===== We will be extending our sll2 project in dll1 with the addition of doubly-linked lists, as well as the implementation of the queue data structure (using a doubly linked list). You are also to enhance/rewrite/reimplement all existing code based on a singly linked list (node, list, and stack) to make effective use of the doubly linked list. =====Update and Upgrade===== For this project, you'll update your **sll2** project to gain access to the new **upgrade-dll1** option in the Makefile: ====Step 0. Change into project directory==== Change to wherever you copied your code (I'm assuming **~/src/data/sll2** in my example): lab46:~$ cd src/data/sll2 lab46:~/src/data/sll2$ ====Step 1. Update to latest release (preserves your code)==== lab46:~/src/data/sll2$ make update ... ====Step 2. Upgrade to dll1 project (copies over your code)==== lab46:~/src/data/sll2$ make upgrade-dll1 ... ====Step 3. Change into dll1 directory==== lab46:~/src/data/sll2$ cd ../dll1 lab46:~/src/data/dll1$ =====Layout===== This project codebase is largely identical to the sll2 codebase; it merely adds the new files for the doubly linked list and queue functionality. Be sure to check for new files in the following directories: * inc - queue.h header and updated node.h header * src/queue - source code for the queue operations * testing - queuetest.c file (should work as well as the most recent stacktest) =====Queues===== Queues are frequently considered a peer to the stack data structure, in that the two share many common traits (an underlying linked list) but differ in the restrictions placed upon accessing the linked list. It works on a principle of "first-in, first-out" (FIFO), which makes it great to use as a buffer for information (order is preserved). Everyone has real-life experience with a queue... every time you have waited in line somewhere; the grocery store, the bank, midnight release of Super Mario Bros. 2... you "enqueue" yourself at the back of the line, and wait- people are dequeued from the front of the line. Eventually, you will get to the front of the line, and when it is your turn, you dequeue. So, with a queue, we only add to the back, and take off from the front. No other aspect of the linked list is modified or accessed under the guise of a queue. This restriction of access creates new possibilities for algorithms, enabling useful functionality. The basic queue operations are: **enqueue()** and **dequeue()** which will call the necessary underlying list operations (likely **append()** and **getNode()**) while maintaining the **back** and **front** pointers (reflecting some pointer in the underlying list, perhaps **start** and **end**). The queue has a **buffer** variable, which unlike the list's **qty** (that keeps track of how many nodes are in the list at any given time), **buffer** mandates a maximum size a queue can be (if the **qty** has reached **buffer**, no new nodes should be added (i.e. **enqueue()**ed)- this is what is known as a **buffer overrun condition**)). For purposes of flexibility, a **buffer** of zero denotes an unbounded queue (it can grow indefinitely, just like a list). To further test your understanding, you are to implement the queue's **mkqueue()** function this time around. =====Errata===== ====03/23/2014==== * **Update 1**: The issue with stacktest.c would also exist in queuetest.c, so any changes to that need to be forward ported. This has been done. * An attempt to standardize replaced files has been started- any replaced files will be renamed with a **.rev-PREVIOUSREV** extension. So going from rev 0 to rev 1, should now end with **.rev-0** =====Submission===== To successfully complete this project, the following criteria must be met: * All code must compile cleanly (no warnings or errors) * Code must be nicely and consistently indented (you may use the **indent** tool) * Code must be commented * Resulting libraries must be operational and functionally correct * stack functions must operate as described, conforming to provided function prototypes * 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 * Submit a copy of your source code to me using the **submit** tool (or **make submit**). To submit this program to me using the base Makefile, run the following command at your lab46 prompt: lab46:~/src/data/dll1$ make submit ... Submitting data project "dll1": -> dll1-20140412-14.tar.gz(OK) SUCCESSFULLY SUBMITTED 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: lab46:~/src/data/dll1$ make save ... make save now issues a pre-emptive make clean ... Archiving the project ... Compressing the archive ... Setting permissions ... lab46:~/src/data/dll1$ cd .. lab46:~/src/data$ ls dll1*gz dll2-20140412-14.tar.gz lab46:~/src/data$