Data Structure Self-Learning Notes

Reference: Fundamentals of Data Structures in C＋＋, E. Horowitz, S. Sahni, and D. Mehta, 2nd ed., 2006.

Data structure 2–1 Thursday, January 7, 2021

1. Time complexity: O(logn)
2. Algorithm for binary search: pseudo code and C code
3. Recursive for binary search
4. Recursive Permutation Generator

Data structure 2–2 Friday, January 8, 2021

1. Recursive: Factorial, Permutation, Fibonacci Sequence
2. Criteria to judge a program

Data structure 2–3 Friday, January 8, 2021

1.The Tower Of Hanoi Problem

T(n):movements with disks

T(n)=T(n-1)+1+T(n-1)

移動2^n-1次

2. Asymptotic O Notation: O(): at most

Best Sorting:O(nlogn)

Data structure 4–1 Saturday, January 9, 2021

1. Selection Sort: use Swap()
2. Time Performation
3. C++ Class : four components:

• 1. class name
• 2. data members
• 3. member functions
• 4. levels of program access

4. Rectangle.h — Definition of Rectangle Class

Rectangle() — constructor — initial

~Rectangle() — destructor

Rectangle.cpp — operation Implementation

Data structure 4–2 Saturday, January 9, 2021

1. Operation Overloading

int Rectangle : : operation==(const Rectangle& s)

2. Sets in Pascal (HW2)

Data Structure Monday, January 11, 2021

第五週 Array

1. prefixsum 矩陣存放及運算 complexity
2. String Matching Problem: KMP演算法 Time complexity: O(m+n)
3. template:

template<class T>

void SelectionSort(T*a, const int n)

float array[ 100 ]

int intarray[ 200 ]

Data Structure Wednesday, January 13, 2021

1. Implementing Stack and Queue

2. HW3 西洋棋 騎士所有走的順序路徑，利用stack backtracking方法解決問題

Data Structure Saturday, January 16, 2021

7–1 Class Inheritance

7–2 1. The Mazing Problem

- Try all

- use stack to store path and direction

- 2D array recorded the road has been to

2. Infix, Postfix, Prefix Expressions

7–3 1. Postfix Expression

- Use stack

2. Algorithm -pseudo code

3. Verify postfix

4. Conversion from Infix to Postfix

HW4 use recursive

8–1 Storage Allocation

8–2 Linked List
8–3 Template Class

1.Insert List

2.Concatenate list

3.Reverse List

Data Structure Monday, January 25, 2021

9–1

1.Linked Stack

2.Linked Queue

Application:

-Revisit Polynomials

Equivalence Algorithm

- depth-first Search(Stack)

- Θ(m+n) (剛好成正比)

9–2

1.Linked list for Sparse Matrix

2.General List

9–3

General Polynomial

• Reference Counts in Shared Lists
• Add a header node
• The list can be deleted only when the reference count is 0

Data Structure Monday, May 24, 2021

第 11 12 週

List Representation of a Tree

Level-Order Traversal of a Binary Tree

Threaded Binary Tree

Insertion

Deletion

Insertion into a Max(Min) Heap

Max(Min) Heap:

Max (min) finding: O(1)

Insertion: O(log n)

Deletion: O(log n)

Binary Search Trees:

Time complexity: O(h), h:tree height

Selection Trees:

Goal: merge (合併) k ordered sequences (called runs) in nondecreasing into a single ordered sequence.

Better method: winner tree

Total time for merging k runs: O(n log2k)

Number of levels:

Forest

Representing a Forest with a Binary Tree

• leftChild=first child
• rightChild=next sibling
• Number of Distinct Binary Trees

Ch7 Sorting

best sorting algorithm with comparisons: O(nlogn)

Sequential Search

Time complexity

successful search: (n+1)/2 comparisons = O(n)

unsuccessful search: n comparisons = O(n)

binary search

needs O(log n) time to search a key in a sorted list with n records.

Data Structure Monday, May 24, 2021

Get Michael Chang’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

第 13 週

Categories of Sorting Methods

1. stable

2. internal

3. external

Sort

1. Insertion Sort

• best case : n-1
• worst case : O(n2)

2. Quick Sort

• best case : O(n log n)
• worst case : O(n2) (已排好順序最差)
• Variations of Quick Sort (改善Worst Case)

a. median of three

b. selection algorithm

3. Merge Sort

• Two-way Merge: Time complexity: O(m+n)
• Iterative Merge Sort
• Merge sort is a stable sorting method
• Time complexity: O(n log n)
• Recursive Merge Sort
• Merging Sorted Chains

Data Structure Monday, May 24, 2021

第 14 週

Heap Sort

Radix Sort

• least significant digit first (LSD)
• array處理速度快,需要較多記憶體 (time-space tradeoff)
• Linked List相反
• Time complexity: O((n+r)logrk)
• k: input data 之最大數
• r: 以 r 為基數(radix)， logrk: 位數之長度

List Sort

• 減少資料移動
• 記錄雙向link
• 不適合Quick Sort及Heap Sort
• 移動位置後改指標

Table Sort

• Suitable for all sorting methods
• Permutation Cycle
• 從第一個位置開始,找下個指標t為實際資料所在位置，直到一個循環停止
• a[t[1]]…

Internal Sort

Average Execution Time

External Sorting

• The most popular method for sorting on external storage devices is merge sort
• If shorter runs are merged first, the required time is reduced

(長度小的RUNs執行較多次，傾斜一邊的tree)

Huffman Algorithm

• to solve the problem of finding a binary tree with minimum weighted external path length.
• Construction of Huffman Tree (相加找最小放入tree)
• 應用：壓縮檔案

a. variable-length codes

b. encode, decode ＝>某一碼不會是另一個的prefix

Data Structure Tuesday, June 15, 2021

第 15 週

Static Hashing

Hash Functions選擇:

• Division 除法
• Mid-square 平方取中間位元
• Folding 折疊
• Digit Analysis 數位分析

Overflow Handling

• Linear probing 線性探測 (linear open addressing)
• Quadratic probing 二次探測
• Rehashing 再雜湊
• Linked list

Dynamic Hashing

Using Directories

• 開資料夾方式
• Only rehash the entries in the buckets that overflows

Directoryless

• 只增加overflow的格子

Data Structure Tuesday, June 15, 2021

第 16週

Efficient Binary Search Trees

Extended Binary Trees

• external nodes: failure
• External / internal path length

Algorithm for Constructing Optimal BST

- find minimized Cost

- Using dynamic programming

- Time complexity: O(n3)

AVL Trees
— Balance factor BF(v) =hL − hR = −1, 0, or 1

- insert an element into the tree, or delete an element from it, in O(log n) time

• 4 rotations for rebalancing:
  LL, RR, LR, and RL

Red-Black Trees

• handled by changing colors or a rotation

- Color Change of LLr, LRr, RRr, RLr

- Rotation and Color Change of LLb, LRb, RRb, RLb

Splay Trees

- no balanced information

- 方便拿取搜尋過的資料

Bottom-Up Splay Trees

• Move up 2 levels at a time using rotation

Top-Down Splay Trees

• small binary search tree (smaller than x)
• big binary search tree (bigger than x)
• the splay node x

Data Structure Tuesday, June 15, 2021

第 17週

Multiway Search Trees

B-tree of order m

1. 2 ≤ # children of root ≤ m
2. All nodes other than the root node and external nodes:
   ⎡m/2⎤ ≤ # children ≤ m

3. All external nodes are at the same level.

• 2–3 tree is a B-tree of order 3 and 2–3–4 tree is a B-tree of order 4.
• Insertion, deletion or searching in a B-tree

requires O(logN) time, where N denotes the number of elements in the B-tree.

B+ trees

. Index node: internal node, storing keys (not elements) and pointers

• Data node: external node, storing elements (with their keys)
• Data nodes are linked together to form a doubly linked list.