Personal course project

Data structures: C++ templates and course labs

Shanghai University · Data Structures (autumn 2022)

Organised seven chapters of course work into 36 topic modules and two integrative projects: C++ templates for lists, stacks, queues, trees and graphs, covering KMP, Huffman, union-find, minimum spanning trees, shortest paths, topological sort and critical paths.

Background

Data Structures is a core course in the Information Engineering programme at Shanghai University. Its scope runs from lists, stacks and queues to strings, arrays and generalised lists, then trees, heaps, Huffman trees and union-find, and finally graph traversal, minimum spanning trees, shortest paths, topological sorting and critical paths.

This repository collects the course labs, the final assignment and study notes along three lines: course chapters, integrative projects and learning material. Chapters 3–7 contain 36 topic modules plus two integrative projects; the core structures are written with C++ templates.

Repository layout

src/
├── chapter03_linear_list/           # sequential list, singly/doubly linked lists, polynomials, sets
├── chapter04_stack_queue_recursion/ # stacks, queues, expression evaluation, Hanoi, rail shunting
├── chapter05_string_array_generalized_list/  # brute force, KMP, sparse matrices, generalised lists
├── chapter06_tree/                  # binary trees, threaded trees, min-heap, Huffman, union-find
├── chapter07_graph/                 # DFS/BFS, Prim/Kruskal, Dijkstra/Bellman-Ford/Floyd
├── exercises_cpp_basics/            # first two weeks of C++ exercises
└── final_project_leaf_count/        # final assignment: count binary-tree leaves

A typical module has three files: Assistance.h for status codes, exceptions and traversal helpers; a structure header such as SeqList.h or BinaryTree.h for the template implementation; and Test*.cpp, a runnable demo entry.

Technical points

  • Templates: sequential lists, linked lists, stacks, queues, binary trees and graphs all use template <class ElemType>, so one implementation can hold int, double, string or a user type.
  • Status codes instead of exceptions: insert, delete and get return SUCCESS, RANGE_ERROR, OVER_FLOW or NOT_PRESENT, and the caller must handle failure explicitly. It is the course style, and it makes edge cases visible.
  • A complete algorithm spectrum: from O(1) sequential access to O(n+m) KMP, then Prim / Kruskal / Dijkstra / Bellman-Ford / Floyd, topological sorting and critical paths.
  • Final assignment: count leaves in a binary linked tree. A null child returns 0, a node with no children returns 1, otherwise recurse into both subtrees; O(n) time and O(h) space.

Code verification

After reorganising, I ran g++ -fsyntax-only over all 38 demo entry points: 35 / 38 pass. The three failures come from the original course code and were left untouched:

  • chapter03_linear_list/seq_list/SeqList.h: getElem in the copy constructor should be GetElem;
  • chapter03_linear_list/set_intersection/SeqList.h: the same typo in an independent copy;
  • exercises_cpp_basics/Project1/main.cpp: the original demo entry has a pointer/reference parameter mismatch and is an unfinished draft.

Keeping them is deliberate: the repository is a course record first and a portfolio second. Cleaning up the original code would remove its value as study material; the README, however, must say what runs and what does not.

What I took away

The real training was not memorising algorithms, but three habits:

  • separate the logical structure (linear, tree, graph) from the physical one (sequential, linked);
  • compare implementations by complexity, not by “it feels fast”;
  • make every module compile, run and be verified on its own.

Course notes, weekly lab logs, selected lecture handouts and run screenshots are in docs/.

Source and documentation: https://gitee.com/yicongl1/data-structures-cpp

Technical notes

01 C++ template data structures: the generic boundaries of lists, stacks and queues template <class ElemType>, status codes, deep copies and capacity checks — plus a copy-constructor typo that only appears when the template is instantiated. 02 From KMP to critical paths: mapping 36 data-structure labs onto one graph Failure functions, recursive leaf counting, Dijkstra on adjacency lists and critical paths; a lab structure built from a header plus a runnable demo entry.

Related skills

  • C++
  • Git