Corning Community College CSCS2320 Data Structures ~~TOC~~ ======Project: LIST CONCEPTUALIZATION AND IMPLEMENTATION - ARRAY-ENCAPSULATED LISTS (AEL0)====== =====Errata===== With any increasingly complex piece of code or environment, we must find effective means of organizing various processes or communications. This “Errata” section and related updates are one such instance of that; intended as a means of disseminating information on changes to the project, you can be informed what modifications have taken place, along with any unique actions you need to take to compensate. Any typos, bugs, or other updates/changes to the project will be documented here. ====Revision List==== * __revision #__: (DATESTRING) =====Objective===== In this project, we get started with a simultaneous review opportunity for your programming skills, while introducing ourselves to one of the important underlying Data Structures concepts: lists. =====Background===== In your programming travels so far, you've likely been exposed to the more tangible aspects of data; following will be some examples of different categories. If any are not familiar, please look them up and become more acclimated with the concept(s). We have storage: * bits * bytes * words data types: * char * short int * int * long int * long long int * float * double * long double address types: * pointers, which is an attribute describing a data type (int pointer, char pointer, etc.) derived types: * arrays * structures * unions signed attributes: * signed * unsigned even representation: * binary * octal * decimal * hexadecimal * ASCII * unicode * numeric * string but now we'll be building on top of those. Data Structures is an exploration of both concept and strategic arrangement of information (and the related algorithmic approaches) to enhance your programming abilities. We start out studying the concept known as the **list**, which is nothing short of a "number of connected items". They come in various forms and manifestations, but before we get to those, we need to explore the concept. For that we are going to utilize the hopefully familiar array, which will host (or encapsulate) your list, which will then be otherwise processed by program logic. This is one of those "some lists are arrays, but not all arrays are lists" sort of thing, which will be touched on more in the coming projects. =====Program===== As a means of simultaneous review, along with starting to acclimate ourselves to new concepts that we'll be encountering on a regular basis, I'd like for you to implement a program (in C) that does the following: ====menu==== * Presents the user with a menu (reference sample output below for menu specifications), having the listed features. * use numbers for input (don't get fancy) * use numbers for the functionalities given (it will make it easier for me to evaluate) * accept menu and general program input from STDIN (value followed by ENTER). * fscanf() would be an excellent function to familiarize yourself with. ====ael0==== 0. build list 1. display list forward 2. display list backward 3. insert into list 4. append into list 5. obtain from list 6. clear list 7. quit >>> The various menu options are described below: ====build list==== * build list * prompt the user to enter number after number, appending it to the list, until the user terminates the action by entering a -1. Prompt will display to STDERR. * We will check for the -1 in the array to signify the end of our list * if you're crafty about it, this doesn't have to be a unique function, but a loop (even from the menu code) calling an existing function. >>> 0 enter value (-1 to finish): 2 enter value (-1 to finish): 4 enter value (-1 to finish): 6 enter value (-1 to finish): 8 enter value (-1 to finish): -1 ====display list==== There are two modes of list display you are to implement: that of displaying forward (from start to end) and that of its reverse (from end to start). * display list forward * From the first (zero-th) element of the array clear through (and including) to the element containing the -1, * display the contained numbers, along with their array index. * as output is a core necessity of displaying, your function displaying the list can and should perform output. * I want you to have some sort of **display()** function; you can have a separate one for displaying forward (**displayf()**) and backward (**displayb()**), or one combining both functionalities. I leave that up to you. ====ael0==== 0. build list 1. display list forward 2. display list backward 3. insert into list 4. append into list 5. obtain from list 6. clear list 7. quit >>> 1 [0] 2 -> [1] 4 -> [2] 6 -> [3] 8 -> [4] -1 * display list backward * From the list termination value (the -1 following the last element) to the beginning. * display the contained numbers, along with their array index. * as output is a core necessity of displaying, your function displaying the list is where the list display output takes place. ====ael0==== 0. build list 1. display list forward 2. display list backward 3. insert into list 4. append into list 5. obtain from list 6. clear list 7. quit >>> 2 [4] -1 -> [3] 8 -> [2] 6 -> [1] 4 -> [0] 2 ====insert==== One of the two more "atomic" list addition options, insert is responsible for adding a value to the list BEFORE a referenced point. * insert into list * prompt for array index (prompt will display to STDERR) * accept new value from the user * without destroying any array contents, place new value BEFORE specified array index * this will likely involve shifting some data * this functionality should be encapsulated in a discrete **insert()** function * do NOT use global variables; pass and return necessary data * no output of any kind should take place in **insert()**, merely the specified list processing. ====ael0==== 0. build list 1. display list forward 2. display list backward 3. insert into list 4. append into list 5. obtain from list 6. clear list 7. quit >>> 3 Enter index to insert before: 2 Enter value to insert into list: 5 If you were to display the list (forward) after doing this insert, you should have: 2 4 5 6 8 (we inserted the 5 before the current element 2 (containing the 6)). ====append list==== The other of the "atomic" list addition options, append is responsible for adding a value to the list AFTER a referenced point. * append into list * prompt for array index (prompt will display to STDERR) * accept new value from the user * without destroying any array contents, place new value AFTER specified array index * this will likely involve shifting some data * this functionality should be encapsulated in a discrete **append()** function * do NOT use any global variables; pass and return necessary data * no output of any kind should take place in **append()**, merely the specified list processing. ====ael0==== 0. build list 1. display list forward 2. display list backward 3. insert into list 4. append into list 5. obtain from list 6. clear list 7. quit >>> 4 Enter index to append after: 3 Enter value to append into list: 7 ====ael0==== 0. build list 1. display list forward 2. display list backward 3. insert into list 4. append into list 5. obtain from list 6. clear list 7. quit >>> 1 [0] 2 -> [1] 4 -> [2] 5 -> [3] 6 -> [4] 7 -> [5] 8 -> [6] -1 ====obtain==== In opposition to insert and append, which put items INTO the list, obtain does the opposite: it removes it from the list. * obtain from list * prompt for array index (prompt will display to STDERR) * obtain value at array index and place it in a standalone variable (to be displayed to STDOUT) * adjust array contents to no longer include this obtained value (we've removed it from the list) * this functionality should be encapsulated in a discrete **obtain()** function * do NOT use global variables; pass and return necessary data * The "The value you obtained:" message should NOT take place within your **obtain()** function; no output of any kind should take place in **obtain()**, merely the specified list processing. ====ael0==== 0. build list 1. display list forward 2. display list backward 3. insert into list 4. append into list 5. obtain from list 6. clear list 7. quit >>> 5 Enter index to obtain: 3 The value you obtained is: 6 ====ael0==== 0. build list 1. display list forward 2. display list backward 3. insert into list 4. append into list 5. obtain from list 6. clear list 7. quit >>> 1 [0] 2 -> [1] 4 -> [2] 5 -> [3] 7 -> [4] 8 -> [5] -1 ====clear list==== * clear list * empty the array, leaving it in an initial state (-1 at the 0 index, more places if it messes up your reverse list display) * if you're crafty about it, this doesn't have to be a unique function, but a loop (even from the menu code) calling an existing function. ===quit=== * quit * Each menu item should correspond to a discrete activity you'll be performing on the list or program, and each item is implemented out in separate functions (with the exception of the quit option, and possibly the "build" and "clear" options, although you can deploy functions for those too, if you really want). * Additionally, with the exception of displaying the list, you should perform no I/O within any of these functions (do it all in main(), or where-ever your core menu logic is located). * basically, when appending, have a function that handles the actual append operation, but do the input and output in/around your menu code (so your append() function basically just manipulates the list). * This list, for now, will be housed within a statically declared integer array (of 20 elements). You are to perform whatever manipulations are needed on that array. * What if you exceed the array? You exceed it... the program may crash and or infinitely loop or otherwise be unpredictable. This program is really just to start you practicing on the important operations of inserting, appending, and obtaining. For now, just assume the user will always do the right thing and never completely fill up the list. * A "list" is, for all intents and purposes, a sequence of values located together. In this case, they do not have to be sorted, merely considered part of a group or category. Here, we will use the containing features of the array to accomplish that (while simultaneously reviewing C!) =====Further output requirements===== The menu: ====ael0==== 0. build list 1. display list forward 2. display list backward 3. insert into list 4. append into list 5. obtain from list 6. clear list 7. quit and prompt (note the trailing space after ">>> "): >>> The menu and prompt are to go to STDERR, and **NOT** STDOUT. The output from running the various menu options (pretty much the **display**() function(s)) is to go to STDOUT. ====Display arrows==== The display option arrows are to take the form " -> " (note the single space padded both before and after). ====Display values==== The index value is enclosed in square brackets (first one flush against left margin), followed by a space, then the array element (then the padded display arrow). These output specifications play important roles, from facilitated program evaluation to testing how well you can code according to specifications (the latter a very important development skill to have). In Data Structures precision and conformance to requirements will be increasingly important (not only for the scope of the project, but for your own sanity as deviating from it will likely make things far more difficult for you in implementation). Might seem a bit nitpicky, and on some level it is... but on others, a very important learning opportunity for the types of things you'll be encountering in the future. =====Review C===== In addition to writing this program, please be sure you brush up on (at least) the following: * functions (prototypes, definitions, calling, parameters, return types) * structs * pointers * formatted I/O (fprintf()/fscanf() family of functions) A decent reference for the C programming language (and therefore many of the syntactical and conceptual structures found in languages like C++, Java, PHP, etc.) is: * http://publications.gbdirect.co.uk/c_book/ =====Verify Your Program===== When your program is functional, you can test it for correctness by using the **projeval** tool on lab46. A series of tests will be run, and you will be able to see if you program is in spec (SUCCESS) or out of spec (MISMATCH). An example of a fully compliant test run follows: lab46:~/src/data/ael0$ projeval ael0 [projeval] Evaluating ael0 for username [test 0] display 4 element populated list forward ... you have: [0] 2 -> [1] 4 -> [2] 6 -> [3] 8 -> [4] -1 should be: [0] 2 -> [1] 4 -> [2] 6 -> [3] 8 -> [4] -1 Result: SUCCESS! [test 1] inserting into empty list ... you have: [0] 7 -> [1] -1 should be: [0] 7 -> [1] -1 Result: SUCCESS! [test 2] appending into empty list ... you have: [0] 7 -> [1] -1 should be: [0] 7 -> [1] -1 Result: SUCCESS! [test 3] obtaining from 1 entry list ... you have: The value you obtained is: 7 should be: The value you obtained is: 7 Result: SUCCESS! [test 4] obtaining first entry from 2 entry list ... you have: The value you obtained is: 7 should be: The value you obtained is: 7 Result: SUCCESS! [test 5] obtaining second entry from 2 entry list ... you have: The value you obtained is: 8 should be: The value you obtained is: 8 Result: SUCCESS! [test 6] inserting before first entry in list ... you have: [0] 6 -> [1] 7 -> [2] -1 should be: [0] 6 -> [1] 7 -> [2] -1 Result: SUCCESS! [test 7] inserting before second entry in list ... you have: [0] 7 -> [1] 8 -> [2] 9 -> [3] -1 should be: [0] 7 -> [1] 8 -> [2] 9 -> [3] -1 Result: SUCCESS! [test 8] appending after last entry in list ... you have: [0] 7 -> [1] 8 -> [2] 9 -> [3] -1 should be: [0] 7 -> [1] 8 -> [2] 9 -> [3] -1 Result: SUCCESS! [test 9] appending after second to last entry in list ... you have: [0] 7 -> [1] 8 -> [2] 9 -> [3] -1 should be: [0] 7 -> [1] 8 -> [2] 9 -> [3] -1 Result: SUCCESS! [test 10] clearing list then appending ... you have: [0] 7 -> [1] -1 should be: [0] 7 -> [1] -1 Result: SUCCESS! [test 11] obtaining second entry from 2 entry list (check list integrity) ... you have: [0] 7 -> [1] -1 should be: [0] 7 -> [1] -1 Result: SUCCESS! [test 12] obtaining first entry from 2 entry list (checking list integrity) ... you have: [0] 8 -> [1] -1 should be: [0] 8 -> [1] -1 Result: SUCCESS! [test 13] obtaining from 1 entry list (checking list integrity) ... you have: [0] -1 should be: [0] -1 Result: SUCCESS! lab46:~/src/data/ael0$ =====Submission Criteria===== To be successful in this project, the following criteria must be met: * Project must be submit on time, by the posted deadline. * Late submissions will lose 25% credit per day, with the submission window closing on the 4th day following the deadline. * All code must compile cleanly (no warnings or errors) * Compile with the **-Wall** and **--std=c99** compiler flags * all requested functions must be implemented in the related library or program * 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, if applicable, must be correct based on values input * Code must be nicely and consistently indented (you may use the **indent** tool) * Code must be commented * Any "to be implemented" comments **MUST** be removed * these "to be implemented" comments, if still present at evaluation time, will result in points being deducted. * Sufficient comments explaining the point of provided logic **MUST** be present * No global variables, no goto statements, no recursive calling of main()! * at minimum, a discrete **append()**, **insert()**, **obtain()**, and some form of list display functions. * with the exception of your display function(s), no I/O is to be performed. * Track/version the source code in your lab46 repository * Do NOT use any **goto** statements. * Submit a copy of your source code to me using the **submit** tool (**make submit** will do this) by the deadline. ====Submit Tool Usage==== Let's say you have completed work on the project, and are ready to submit, you would do the following (assuming you have a program called ael0.c): lab46:~/src/data/ael0$ submit data ael0 ael0.c Submitting data project "ael0": -> ael0.c(OK) SUCCESSFULLY SUBMITTED lab46:~/src/data/ael0$