User Tools

Site Tools


Sidebar

projects

  • dsi0 (due 20150128)
  • sln0 (due 20150204)
  • sln1 (due 20150211)
  • sll0 (due 20150225)
  • sll1 (due 20150304)
  • sll2 (due 20150311)
  • sll3 (due 20150408)
  • dll0 (due 20150408)
  • dll1 (due 20150415)
  • dls0 (due 20150422)
  • dlq0 (due 20150429)
  • dlt0 (due 20150506)
  • EoCE - see bottom of Opus (due 20150514 by 4:30pm)
haas:spring2015:data:projects:dll0

This is an old revision of the document!


Corning Community College

CSCS2320 Data Structures

~~TOC~~

Project: DLL0

Errata

This section will document any updates applied to the project since original release:

  • revision #: <description> (DATESTRING)

Objective

In this project, we take our first opportunity to undergo a complete code re-write of linked list functionality, while we implement our first doubly linked list.

Project Overview

For this project, we're going to be re-implementing MOST of the previous node and list functions. There have been a few changes, namely:

In inc/node.h

1
#ifndef _NODE_H
#define _NODE_H
 
#include <stdlib.h>
 
struct node {
        char         value;
        struct node *after;
        struct node *prior;
};
typedef struct node Node;
 
Node *mknode(int   );     // allocate new node containing value
Node *cpnode(Node *);     // duplicate node
Node *rmnode(Node *);     // deallocate node
 
#endif

There is an addition of a “prior” node pointer, to allow connections to our previous neighbors.

The node info element has been renamed to “value”, just to make sure you understand what is going on code-wise.

In inc/list.h

1
#ifndef _LIST_H
#define _LIST_H
 
#include "node.h"                       // list relies on node to work
 
struct list {
    Node *start;                        // pointer to start of list
    Node *end;                          // pointer to end of list
};
typedef struct list List;               // because we deserve nice things
 
List *mklist(void  );                   // create/allocate new list struct
List *cplist(List *);                   // copy (duplicate) list
List *rmlist(List *);                   // remove all nodes from list
 
List *insert (List *, Node *, Node *);  // add node before given node
List *append (List *, Node *, Node *);  // add node after given node
List *obtain (List *, Node **       );  // obtain/disconnect node from list
 
void  display(List *, int);             // display list according to mode
 
Node *findnode(List *, int);            // locate node containing value
List *sortlist(List *, int);            // sort list (according to mode)
 
List *swapnode(List *, Node *, Node *); // swap positions of given nodes in list
 
#endif

The following changes have taken place:

  • qty has been removed from the list; any code you wrote that is based on it will need to be implemented a different way (do NOT recreate the conditions to continue relying on a count, you will lose credit if you do so).
  • getpos()/setpos() are no longer present. In many ways their functionality is no longer needed with the doubly-linked nature of the list.
  • searchlist() has been renamed to findnode() (aesthetic change, to keep function names at 8 characters or less).
  • displayf()/displayb() are gone, and previous functionality will be merged into one universal display() function.

list library

In src/node/, you will find skeletons of what was previously there, ready for you to re-implement.

In src/list/, you will find the same- skeletons of the above prototyped functions, hollowed out in anticipation of being made operational.

Figure out what is going on, the connections, and make sure you understand it.

As ALL source files are now skeletons, no sample code has been given. This is intended to be a fresh implementation. While you may reference old code, do not rely on it- try your hand at implementing the functionality from scratch (the more you do this from scratch, the more it will help you).

List library unit tests

In testing/list/unit/, you will find these new files:

  • unit-append.c - unit test for append() library function
  • 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 updates.

There are also corresponding verify-FUNCTION.sh scripts that will output a “MATCH”/“MISMATCH” to confirm overall conformance with the pertinent list functionality.

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

Of particular importance, I want you to take a close look at:

  • the source code to each of these unit tests
    • the purpose of these programs is to validate the correct functionality of the respective library functions
    • follow the logic
    • make sure you understand what is going on
    • ask questions to get clarification!
  • the output from these programs once compiled and ran
    • analyze the output
    • make sure you understand what is going on
    • ask questions to get clarification!

Expected Results

To assist you in verifying a correct implementation, a fully working implementation of the node and list libraries should resemble the following (when running the respective verify script):

node library

Here is what you should get for node:

lab46:~/src/data/dll0$ bin/verify-node.sh 
====================================================
=    Verifying Doubly-Linked Node Functionality    =
====================================================
  [mknode] Total:   5, Matches:   5, Mismatches:   0
  [cpnode] Total:   6, Matches:   6, Mismatches:   0
  [rmnode] Total:   2, Matches:   2, Mismatches:   0
====================================================
 [RESULTS] Total:  13, Matches:  13, Mismatches:   0
====================================================
lab46:~/src/data/dll0$ 

list library

Here is what you should get for list:

lab46:~/src/data/dll0$ bin/verify-list.sh 
====================================================
=    Verifying Doubly-Linked List Functionality    =
====================================================
  [mklist] Total:   5, Matches:   5, Mismatches:   0
  [cplist] Total:  30, Matches:  30, Mismatches:   0
  [rmlist] Total:   3, Matches:   3, Mismatches:   0
  [append] Total:  11, Matches:  11, Mismatches:   0
  [insert] Total:  11, Matches:  11, Mismatches:   0
  [obtain] Total:  12, Matches:  12, Mismatches:   0
 [display] Total:   6, Matches:   6, Mismatches:   0
[findnode] Total:  11, Matches:  11, Mismatches:   0
[sortlist] Total:   6, Matches:   6, Mismatches:   0
[swapnode] Total:   7, Matches:   7, Mismatches:   0
====================================================
 [RESULTS] Total: 102, Matches: 102, Mismatches:   0
====================================================
lab46:~/src/data/dll0$ 

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)
    • all requested functions must be implemented in the related library
    • 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 must be correct (i.e. the list visualization, where applicable) 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
  • Track/version the source code in a repository
  • Submit a copy of your source code to me using the submit tool (make submit will do this) by the deadline.
haas/spring2015/data/projects/dll0.1427124580.txt.gz · Last modified: 2015/03/23 15:29 by wedge