Table of Contents

Corning Community College

CSCS2320 Data Structures

~~TOC~~

Project: DLL0

Errata

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

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         data;
        struct node *prev;
        struct node *next;
};
typedef struct node Node;
 
Node *mknode(char  );     // allocate new node containing value
Node *rmnode(Node *);     // deallocate node
Node *cpnode(Node *);     // duplicate node
 
#endif

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

The node value element has been renamed to “data”, 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:

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:

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:

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: