Doubly Doubly Linked Lists¶

In this assignment your task is to implement a special kind of doubly-linked lists inside a class called Exam_database.

Conceptually, an Exam_database stores (name, score) pairs, where name is the name of a person who wrote an exam, and score is the score they got on it. For simplicity, we’ll assume names are not empty and contain no spaces. Also, a given name occurs at most once in an Exam_database. A score can be any int (even negative!).

Internally, Exam_database should store (name, score) pairs in a private Node struct/class. Each Node should have at least these 4 pointers:

A pointer to the next node whose name occurs alphabetically after the current one.
A pointer to the previous node whose name occurs alphabetically before the current one.
A pointer to the next node with the next higher score after this one.
A pointer to the previous node with the next lower score before this one.

The idea is that the two alphabetical-order pointers form a doubly-linked list ordered by names, and the two score-order pointers form a different doubly- linked list ordered by scores. The (name, score) nodes should only occur once — don’t just implement two separate doubly-linked lists.

In addition to the Node struct/class, Exam_database needs two head pointers and two tail pointers. One head points to the exam node whose name comes first alphabetically, and the other head points to the exam node with the lowest score. Similarly, one tail points to the alphabetically last node, and the other tail points to the node with the highest score.

With these nodes and pointers, it is now easy to print out the list in forward order, or reverse order, by name or by score: just follow the correct pointers. For example, if you start at the exam with the highest score and follow the next lowest exam pointers, you will traverse the exams from highest score to lowest score.

When add_exam is called, a Node should be created and inserted into the correct place according to both the name pointers and the score pointers. Do not use any kind of sorting routine anywhere in your code! Use only basic C++ features (such as raw pointers) in your solution.

What to Submit¶

Submit just the file Exam_database.h, and nothing else. It should have this format (please fill in the header at the top with your specific info):

// Exam_database.h

/////////////////////////////////////////////////////////////////////////
//
// Student Info
// ------------
//
// Name : <put your full name here!>
// St.# : <put your full SFU student number here>
// Email: <put your SFU email address here>
//
//
// Statement of Originality
// ------------------------
//
// All the code and comments below are my own original work. For any non-
// original work, I have provided citations in the comments with enough
// detail so that someone can see the exact source and extent of the
// borrowed work.
//
// In addition, I have not shared this work with anyone else, and I have
// not seen solutions from other students, tutors, websites, books,
// etc.
//
/////////////////////////////////////////////////////////////////////////

#include "cmpt_error.h"
#include <iostream>
#include <string>

using namespace std;

class Exam_database {
private:

    // ... put private variables and methods here ...

public:
    // Pre-condition:
    //    none
    // Post-condition:
    //    constructs a new empty Exam_database
    // Note:
    //    you can use an initialization with this constructor
    Exam_database();

    // Pre-condition:
    //    none
    // Post-condition:
    //    destructs Exam_database, i.e. ensures all memory (or other resources)
    //    owned by this object are properly deleted
    ~Exam_database();

    // Pre-condition:
    //    name is non-empty and contains no spaces
    //    use cmpt::error to throw an exception if this is not satisfied
    // Post-condition:
    //    adds (name, score) to this object; if a pair in the database already
    //    has the name, then its corresponding score is set to score
    void add_exam(const string& name, int score);

    // Pre-condition:
    //    name is non-empty and contains no spaces
    //    use cmpt::error to throw an exception if this is not satisfied
    // Post-condition:
    //    deletes the (name, score) pair from this Exam_database; if there is no
    //    pair with the given name, then this does nothing
    void remove_exam(const string& name);

    // Pre-condition:
    //    none
    // Post-condition:
    //    print (to cout) all (name, score) pairs in alphabetical order by name
    void print_by_name() const;

    // Pre-condition:
    //    none
    // Post-condition:
    //    print (to cout) all (name, score) pairs in reverse alphabetical order
    //    by name
    void print_by_name_rev() const;

    // Pre-condition:
    //    none
    // Post-condition:
    //    print (to cout) all (name, score) pairs from smallest to biggest by score
    void print_by_score_ascending() const;

    // Pre-condition:
    //    none
    // Post-condition:
    //    print (to cout) all (name, score) pairs from biggest to smallest by score
    void print_by_score_descending() const;

    //
    // ... you can add other helper methods here if you need them ...
    //

}; // class Exam_database

Don’t change the name or details of any of the given methods/constructors! If you do, you’re program will fail in testing.

Do not #include any other files in this header file.

You can add extra helper methods (or functions) if you wish.

Please put all your code in Exam_database.h, and test it by #include-ing it into a .cpp file (e.g. called a2.cpp) that includes your testing code. This is not the best way to organize a C++ class, but it is simple and straightforward and lets us focus on the details of the data structures and algorithms instead of the particular details of C++.

The marker will test your Exam_database.h code by including it in a test program compiled with the standard course makefile. You can assume that cmpt_error.h is in the same folder.

See Canvas for the due date and details of the marking scheme.

Please note that if you’re program doesn’t compile, or does not follow the rules of this assignment, then you will get 0.

Hints¶

Don’t put a main function in Exam_database.h — that will cause it to fail when it is marked! The marker will supply their own .cpp file with a main function that #includes your Exam_database.h file.
You may want to build your program using the -B option with make to force it to re-compile your program every time, e.g.:
```
$ make -B a2
```
If a2.cpp #includes Exam_database.h, then make a2.cpp will not re-compile a2.cpp if you’ve only made changes to Exam_database.h.
Use valgrind to help ensure your program has no memory leaks or other memory errors, e.g.:
```
$ make -B a2

$ valgrind ./a2

// ... lots of output ...
```
A program is considered to have no memory leaks or problems if:
- In the LEAK SUMMARY, definitely lost, indirectly lost, and possibly lost must all be 0.
- The ERROR SUMMARY must report 0 errors.
- It is usually okay if still reachable reports a non-zero number of bytes.
Use only new and delete to allocate and de-allocate memory. Do not use malloc and free.
Do not use C++ smart pointers, such as unique_ptr or shared_ptr. Stick to raw pointers, and use new and delete (or delete[]) and constructors/destructors (plus valgrind) to manage memory.
Do not use any pre-defined data structure (such as array or vector) or algorithms to implement your solution — do it using only basic C++ functions and features.
You must include the large comment section with student info and the statement of originality. If your submitted file does not have this, then we will assume your work is not original and it will not be marked.

If your program meets all these basic requirements, then it will graded using the marking scheme on Canvas.

Table Of Contents

Previous topic

Next topic

Doubly Doubly Linked Lists¶

What to Submit¶

Hints¶