seanys/Data-Structure-Algoirthm-Tongji-SEM

本人数据结构与算法的课程算法与笔记

Notes and Code for Data Structures and Algorithms（C++）

Author: Yang Shan, Department of Management Science and Engineering, Tongji University

Environment：Apple clang version 11.0.3 (clang-1103.0.32.59), Xcode 11.4.1

This repository contains code and my notes data structures and algorithms taught in Prof. Liang Zhe's class. Algorithms in file [Final Exam Preparation&Algorithm](Final Exam Preparation&Algorithm) are achieved by myself, some of the other algorithms are adapted from nice code provided by others online and some are programmed by myself.

My notes for these algorithms will be added to this file soon.

• Basic Knowledge
  • Divide and Conquer
  • Time complexity
• Sorting Algorithms
  • Buble Sort
  • Merge Sort
  • Bucket sort
  • Binary Tree
  • Quick Sort
  • Random Quick Sort
  • Count Sort
  • Heap Sort
  • Insertion Sort
  • Radix Sort
  • Select Sort
• Data Structures
  • Binary Tree
  • Linked List
  • Double Linked List
  • Queue and Stack
  • Hash Table
  • Red Black Tree
  • Linear Table
• Graph Algorithms
  • BFS
  • DFS
  • Graph Search
  • Min Heapify
  • All pairs shortest paths
  • Bellman Ford
  • Dijkstra
  • DAG Shortest Path
  • Floyd Warshall
  • Topology
  • Tarjan
  • MST

Basic Knowledge

Divide and Conquer

The best example for divide and conquer is merge sort which divides a large sorting problem into some small compare problems. This algorithm is robust and quick.

Time complexity

For example, quick sort's average time complexity is Θ(nlgn) and the worest case O(n^2).

Sorting Algorithms

Buble Sort

Source Code: Buble Sort

Merge Sort

Source Code: Merge Sort

Bucket sort

Source Code: Bucket Sort

Binary Tree

Source Code: Binary Sort

Quick Sort

Source Code: Quick Sort

Random Quick Sort

Source Code: Random Quick Sort

Count Sort

Source Code: Count Sort

Heap Sort

Source Code: Heap Sort

Insertion Sort

Source Code: Insertion Sort

Radix Sort

Source Code: Radix Sort

Select Sort

Source Code: Select Sort

Data Structures

Binary Tree

Source Code：Binary Tree

Linked List

Source Code：Linked List

Double Linked List

Source Code：Double Linked List

Queue and Stack

Source Code：Queue and Stack

Hash Table

Source Code：Hash Table

Red Black Tree

Source Code：Red Black Tree

Linear Table

Source Code：Linear Table

Graph Algorithms

BFS

Source Code：BFS

DFS

Source Code：DFS

Graph Search

Source Code：Graph Search

Min Heapify

Source Code：Min Heapify

All pairs shortest paths

Source Code：All pairs shortest paths

Bellman Ford

Source Code：Bellman Ford

Dijkstra

Source Code：Dijkstra

DAG Shortest Path

Source Code：DAG Shortest Path

Floyd Warshall

Source Code：Floyd Warshall

Topology

Source Code：Topology

Tarjan

Source Code：Tarjan

MST

Source Code：MST