Lab46 Wiki

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
<WRAP centeralign round box>
<WRAP><color red><fs 200%>Corning Community College</fs></color></WRAP>
<WRAP><fs 150%>CSCS2320 Data Structures</fs></WRAP>
</WRAP>

======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 #__: <description> (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.

<cli>
====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
>>> 
</cli>

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 a -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.

<cli>
>>> 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
</cli>

====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.

<cli>
====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
</cli>

  * 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.

<cli>
====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
</cli>

====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.

<cli>
====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
</cli>

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.

<cli>
====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
</cli>

====obtain====
In opposition to insert and append, which put items INTO the list, obtain
does the opposite: it takes it out of 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.

<cli>
====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
</cli>

====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:

<cli>
====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
</cli>

and prompt (note the trailing space after "<nowiki>>>> </nowiki>"):

<cli>
>>> 
</cli>

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
  * library: 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:

<cli>
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$ 
</cli>

=====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 33%  credit per day, with the submission window closing on the 3rd day following the deadline.
  * All code must compile cleanly (no warnings or errors)
    * Compile with the **-Wall** and **--std=gnu18** 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
  * 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 manual 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 in any of your functions.
  * 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):

<cli>
lab46:~/src/SEMESTER/data/ael0$ submit data ael0 ael0.c
Submitting data project "ael0":
    -> ael0.c(OK) 

SUCCESSFULLY SUBMITTED
lab46:~/src/SEMESTER/data/ael0$ 
</cli>

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.

I'll be evaluating the project based on the following criteria:

<code>
52:ael0:final tally of results (52/52)
*:ael0:grabbed project by the Sunday before due date [6/6]
*:ael0:clean compile, no compiler messages [10/10]
*:ael0:runtime tests pass [20/20]
*:ael0:adequate modifications [10/10]
*:ael0:tracked in lab46 semester repo [6/6]
</code>

Additionally:

  * Solutions not abiding  by spirit of project will be  subject to a 50% overall deduction
  * Solutions  not  utilizing descriptive  why and  how comments  will be subject to a 25% overall deduction
  * Solutions not utilizing indentation to promote scope and clarity will be subject to a 25% overall deduction
  * Solutions not organized and easy to  read (assume a terminal at least 90 characters wide, 40 characters tall)  are subject to a 25% overall deduction
Lab46 Wiki

User Tools

Site Tools

Page Tools
