Personal course project
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.
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.
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.
template <class ElemType>, so one implementation can hold int, double, string or a user type.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.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.
The real training was not memorising algorithms, but three habits:
Course notes, weekly lab logs, selected lecture handouts and run screenshots are in docs/.
Source and documentation: https://gitee.com/yicongl1/data-structures-cpp