[课程笔记]2024春夏 ZJU 数据结构基础

教师：朱建科
TA：陈浩鹏
讲授基本的数据结构定义、实施以及一些相关的简单算法(list, queue, stack, tree, graph, priority queue…)
平时每节课有作业，加上三个 lab，分为normal（总分 25）和hard模式（总分 30）基本完成了就能接近满分（如果能重来，我一定选困难模式——能够弥补一点平时扣分（忘作业,ԾㅂԾ,）更容易拿到满分
期末：考试注重理论，判断+选择+程序填空+一道函数题（二叉树的最大深度+用二维数组返回所有最大深度的路径） 相比图 的函数题要简单很多，不过做的时候还是绕了点路,ԾㅂԾ,，AC 的时候大概排名 80/599
把数据结构分成基础（FDS）和进阶（ADS）部分，两个学期上完。相比清华一个学期“速通”数据结构还是友好一点。通过学习，可以说把基础数据结构内涵以及算法实施都掌握地十分牢靠

ALGO Analysis

• Definition (asymptotic notation)
  N: sufficient large
  • Big-Oh O( f(N) )
    T(N) = O( f(N) ) if there are a c $>0$ and $n_0$ such that T(N) $\le$ c f(N) when N $\le$ $n_0$
    describe the growth rate (less than or equal to f(N) upper bond(worse case)
    always take the smallest one (as tight as possible)
  • little-Oh
    less than
  • $\Omega$
    greater than or equal (lower bound)
  • $\Theta$
    equals

Induction Analysis

$T(N) = 2T(\frac{N}{2}) +cN$ $T(1) = O(1)$

$T\left(\frac{N}{2}\right) = 2T(\frac{N}{2^2}) + \frac{cN}{2}$

…

$\frac{N}{2^{k}} = 1$ 且 $k = \log_2{N}$

$T(N)=NT(1)+kcN$ = $O(N+NlogN)$ = $O(NlogN)$

Abstract Data Type

Data type = Objects + Operations

List

Objects : ( $item_0,item_1,item_2....$ )
Operations : - length? - print - make an empty list - insert - delete - find next - find previous

Array

arry[i] = item_i

cons - max size should be estimated - Insertion and deletion $O(N)$ and involve lots of data movement
pros - find $k$-th item $O(1)$

Linked List

cons - requires more system function calls
pros - conserve memory

Implementation (with a dummy head)

definition

typedef Node* ptrToNode;
typedef ptrToNode List;
typedef preToNode Position;

typedef struct _node {
	int val;
	Position next;
}Node;

functions

List createList(List L) {
	L = (List)malloc(sizeof(Node));
	L->next = NULL;
	return L;
}

bool isLast(List L, Position P) {
	return p->next == NULL
}

List insert(List L, Position P, int x) {
	Position tmpCell = (Position)malloc(sizeof(Node));
	tmpCell->val = x;
	tmpCell->next = P->next;
	P->next = tmpCell;
	return L;
}

ptrToNode findPre(List L, int x) {
	ptrToNode p = L;
	for(;p->net != NULL && p->next->val != x; p = p->next) {
	}
	return p
}

List Delete(List L, int x) {
	Position pre = findPre(L, x);
	Position tmpCell = (Position)malloc(sizeof(Node));
	tmpCell = pre->next;
	pre->next = tmpCell->next;
	free(tmpCell);
}

std::list<int> L;

Stack

LIFO
ADT error: pop from an empty stack
Implementation error: push to a full stack

Implementation

definition

typedef struct stackRecord* Stack;

struct stackRecord{
	int capacity;
	int top;
	int* array;
};

functions

Stack createStack(int capacity) {
	Stack S = (Stack)malloc(sizeof(struct stackRecord));
	S->capacity = capacity;
	S->top = 0;
	S->array = (int*)malloc(sizeof(int) * capacity);
	return S;
}

void push(Stack S, int x) {
	if(S->top == S->capacity - 1) {
		exit(EXIT_FAILURE);
	} else {
		S->array[++S->top] = x;
	}
}

int pop(Stack S) {
	if(0 == S->top) {
		exit(EXIT_FAILURE);
	} else {
		return S->array[S->top--];
	}
}//pop and top

Utilities

1.Infix to Postfix Conversion

When encountering an operator, push it onto the stack. For operators with higher priority, pop out all operators with lower priority before pushing them onto the stack. When encountering a right parenthesis, pop out all operators until a left parenthesis is encountered.

2.Postfix Evaluation

When encountering a number, push it onto the stack. When encountering an operator, pop out two numbers, perform the calculation, and push the result back onto the stack.

e.g.

• Push 5 characters ooops onto a stack. In how many different ways that we can pop these characters and still obtain ooops?
  • 5

Queue

FIFO

Implementation (Circular)

definition

typedef struct queueRecord* Queue;

struct queueRecord {
	int capacity;
	int size;//not necessary
	int front;
	int rear;
	int* array;
}

functions

Queue createQue(int capacity) {
	Queue Q = (Queue)malloc(sizeof(struct queueRecord));
	Q->capacity = capacity;
	Q->size = 0;
	Q->front = 0;
	Q->rear = -1;
	Q->array = (int*)malloc(sizeof(int) * capacity);
	return Q;
}

void enqueue(Queue Q, int x) {
	if(Q->capacity == Q->size) {
		exit(EXIT_FAILURE);
	} else {
		Q->size++;
		Q->array[(++Q->rear) % (Q->capacity)] = x;
	}
}

int dequeue(Queue Q) {
	if(0 == Q->size) {
		exit(EXIT_FAILURE);
	} else {
		int val = Q->array[Q->front++];
		if(Q->front == Q->capacity) {
			Q->front -= Q->capacity;
		}
		Q->size--;
		return val;
	}
}

cpp Version

vector<int> que;
que.push_back(x);
que.pop_back();
que.erase(que.begin());
que.front();

Hashing

Problems

• Collision
• Overflow

Collision

How to solve hashing collision?

1 Open Addressing

$$index = (hash(key) + f(i)) \mod table size$$

Linear probing

$$f(i) = i \text{ i = collision number}$$

loading density:

$$\frac{\text{number of elements}}{\text{bucket size}}$$

average searching time: $$\frac{\sum \text{search counts}}{\text{number of elements}}$$

Quadratic probing

$$f(i) = i^{2}$$

Theorem : if table size is prime, a new element can always be inserted if the table is half empty ($\lambda < \frac{1}{2}$)

CollisionNum = 0;
CurPositon  = hash(Key, table);
while(!CurPosition empty && CurPosition != key) {//delete === set the flag to empty
	CurPosition += 2 * ++CollisionNum - 1 //induction of (hash(key) + f(i))
	if(CurPosition >= TableSize) CurPosition -= TableSize; //mod tablesize(speed up by using '-' as opposed to '%')
}

2 Separate chaining

3 Double Hashing

$f(i) = i * hash_{2}(x)--e.g.R-(x \mod R)$ noted that R is a prime number smaller than table size

Overflow

Rehashing

if $\lambda > \frac{1}{2}$ there might happen insertion fail

the new table size is a prime which is at least two times bigger than the previous one

when rehash?
1 as soon as half full
2 when insertion fail
3 when the table reaches a certain load factor

e.g.

• The average search time of searching a hash table with N elements is
  • can’t be determined $O(1) \text{ to } O(N)$

Tree

Properties

depth : the length from root to the specific node depth(root) = 0

height : the length of the longest path from the node to a leaf height(leaf) = 0

Traversal

Tree traversal: liner time complexity
Graph traversal: number of edges + vertices

Preorder Traversal $\Rightarrow$ Postfix Expression

print root node first
deep into the hierarchy. On meeting a node, print it
if can not deep in, go back and find another way

void preOrder(Tree T) {
	if(T) {    //tree != NULL (stop and return when reaching the child of leaf)
		visit(T)   //on meeting a tree node, print it
		for(each child C of T) {
			preorder(C);
		}
	}
}

Postorder Traversal $\Rightarrow$ Prefix Expression

deep in as far as possible
meet NULL
return and print

void postOrder(Tree T) {
	if(T) {
		for(each chlid C in T) {
			postOrder(C);
		}
		visit(T);  //first reach here when every child of T is NULL(T is a leaf)
	}
}

Levelorder Traversal (with queue ADT)

visit level by level

levelOrder(Tree T) {
	enQueue(T);
	while(queue is not empty) {
		visit(T = deQueue());
		for(each child C in T) {
			enQueue(C);
		}
	}
}

Inorder Traversal (Binary Tree) $\Rightarrow$ Infix Expression

can be used to regenerate infix expression from a Expression Tree

void inOrder(Tree T) {
	if(T != NULL) {
		inOrder(T->Left);
		visit(T->Element);    //print
		inOrder(T->Right);
	}
}

first visit the most left Node

Rebuild a tree with two traversal sequences

Inorder + preorder/postorder
1 find root
2 find length of left subtree and right subtree
3 recursion

Threaded Tree

four types

e.g.

• Given a tree of degree 3. Suppose that there are 3 nodes of degree 2 and 2 nodes of degree 3. Then the number of leaf nodes must be ____.
  • nodes with degree 1 do not affect number of leaves
  • Handshake theorem
• It is always possible to represent a tree by a one-dimensional integer array.
  • T
• In a binary search tree which contains several integer keys including 4, 5, and 6, if 4 and 6 are on the same level, then 5 must be their parent.
  • F inorder 3 4 5 7 6

Binary Search Tree

Implementation

typedef Node* Tree;
typedef Node* ptrToNode

typedef struct _Node {
	int val;
	ptrToNode left;
	ptrToNode right;
}Node;

Functions

Tree insert(Tree T, int x) {
	if(!T) {
		T = (Tree)malloc(sizeof(Node));
		T->val = x;
		T->left = null;
		T->right = null;

	}
	if(T->val >= x) insert(T->left, x);
	else insert(T->right, x);
	return T;
}


preToNode find(Tree T, int x) {
	if(!T) {
		return NULL;
	}
	if(T->val > x) {
		return find(T->left, x);
	} else if(T->val < x) {
		return find(T->right, x);
	} else {
		return T;
	}
}

ptrToNode findMin(Tree T) {
	if(!T) {
		return NULL;
	}
	if(T->left != NULL) {
		return findMin(T->left);
	} else {
		return T;
	}
}

Tree delete(Tree T, int x) {
	ptrToNode pos = find(T, x);
	if(!pos) {
		exit(EXIT_FAILURE);
	}
	ptrToNode tmpCell;
	if(pos->left && pos->right) {
		tmpCell = findMax(pos->left);
		pos->val = tmpCell->val;
		delete(T->left, pos->val);
/*
		ptrToNode tmpCell;
		tmpCell = findMin(pos->right);
		pos->val = tmpCell->val;
		delete(T->right, pos->val);
*/
	} else {
		tmpCell = pos;
		if(NULL == pos->left) {
			pos = pos->right
		}
		if(NULL == pos->right) {
			pos = pos->left;
		}
		free(tmpCell);
	}
	return T;
}

Heap (Priority Queue)

Implementation

typedef struct heapRecord* Heap

struct heapRecord {
	int capacity;
	int size;
	int* array
};

Functions max Heap (array[0] is empty)

Heap initHeap(int capacity) {
	Heap H = (Heap)malloc(sizeof(struct heapRecord));
	H->size = 0;
	H->capacity = capacity;
	H->array = (int*)malloc(sizeof(int) * (capacity + 1));
	H->array[0] = INT_MAX;
	return H;
}

Heap percolateUp(Heap H, int Idx) {
	int i = Idx;
	int x = H->array[Idx];
	for(; H->array[i/2] < x; i /= 2) {
		H->array[i] = H->array[i/2];
	}
	H->array[i] = x;
	return H;
}

Heap percolateDown(Heap H, int Idx) {
	int x = H->array[Idx];
	int i = Idx;
	int child;
	for(; (i * 2) <= H->size; i = child) {
		child = i * 2;
		if((child < H->size) && (H->array[child] < H->array[child + 1])) {
			child++;
		}
		if(H->array[child] > x) {
			H->array[i] = H->array[child];
		} else {
			break;
		}
	}
	H->array[i] = x;

	return H;
}

build Heap (linear time complexity)

int seq[];
memcpy(H->array, seq, sizeof(seq));
H->array[0] = INT_MAX;
int size = sizeof(seq)/sizeof(int);
//build heap from bottom to the top
//procolate down (start from first non-lraf node)
for(int n = (size - 1) / 2; n >= 1; n--) {
	percolateDown(H, n);
}

cpp Version

vector<int> munbers = { };
std::make_Heap(numbers.begin(), numbers.end());

or

std::priority_queue<int> maxHeap;
std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;

Heap.push(x); //int x
Heap.pop();
Heap.top();

1. Element type (int): This is the data type of the elements in the priority queue. In this example, we are using the int type.

2. Container type (std::vector<int>): This is the type of container used to store the elements of the priority queue. std::vector is a dynamic array in the C++ standard library that provides random access and dynamic resizing capabilities. In this example, we are using std::vector<int> as the container, which means the elements of the priority queue will be stored in a dynamically sized array of integers.

3. Comparator (std::greater<int>()): This is the comparator used to determine the priority of elements. std::greater<int>() is a template function that defines the comparison rule for two int type elements, i.e., a > b. When creating a min-heap, we use std::greater<int>() as the comparator, so that the top element of the heap will be the smallest element in the heap.

Disjoint Set

Elements of the sets: 1, 2, 3, 4, … N
Sets: $S_1,S_2,S_3...S_n$ $S_{i}\cap S_{j}= \emptyset$

Implementation

#define SETNUM 10
int S[SETNUM + 1];

Functions

void init(int* S) {
	for(int i = 1; i <= SETNUM; i++) {
		S[i] = -1;//union by size
		S[i] = 0;
	}
}

int find(int* S, int x) {
	int root;
	for(root = x; S[root] > 0; root = S[root]){;}
	return root;
}

void union(int* S, int x, int y) {
	//by size
	rootX = find(S, x);
	rootY = find(S, y);
	if(rootX == rootY) {
		return;
	}
	if(S[rootX] >= S[rootY]) {
		S[rootY] += S[rootX]
		S[rootX] = rootY;

	} else {
		S[rootX] += S[rootY]
		S[rootY] = rootX;
	}

	//by rank
	if(S[rootX] < S[rootY]) {
		S[rootY] = rootX;
	} else if(S[rootX] == S[rootY]) {
		S[rootX]--;
		S[rootY] = rootX;
	} else {
		S[rootX] = rootY;
	}

}// the depth would not exceed O(logN)

int find_with_pathCompression(int* S, int x) {
	int root, lead, trail;
	root = find(S, x);
	for(trail = x; S[trail] > 0; trail = lead) {
		lead = S[trail];
		S[trail] = root;
	}
	return root;
}

e.g.

• Let T be a tree created by union-by-size with N nodes, then the height of T can be
  • at most log2​(N)+1
• There exists a binary tree with 2016 nodes in total, and with 16 nodes having only one child.
  • F $0\cdot x_{0}+ 1\cdot x_{1}+ 2\cdot x_{2} = \text{edge}$

Graph

Topological Sort

AOV network

activities on the vertex $E(G)$ represent the precedence relations
i is a predecessor of j ( j is the successor of i ), existing a path $i\rightarrow j$
irreflexive ( $i\rightarrow i$ is illegal )

//get indegree of all the vertex
vector<int> indegree;

void Topsort(Graph G) {
	vector<int> que;
	int Counter = 0;
	auto tar = ranges::find(indegree.begin(), indegree.end(), 0);
	que.push_back(tar - indegree.begin());
	while(!que.empty()) {
		int V = que.back();
		counter++;
		que.pop_back();
		for(each W adjacent to V) {
			if(0 == --indegree[W]) {
				que.push_back(W);
			}
		}
	}
	if(counter != number of vertex) {
		//exist a circle
	}

}

time complexity $O(|V|^{2}+|E|) = O(|V|^{2})$

Unweighted Graph (Shortest Path) -> BFS

time complexity : $O(|E|+|V|)$

vector<int> que;
que.push_back(src)  //enquue src vertex
while(!que.empty()) {
	int V = que.back();
	que.pop_back();
	for(each W adjacent to V) {
		if(!visited[W]) {
			visited[W] = true;
			dist[W] = dist[V] + 1;
		}
	}
}

Weighted Graph (Shortest Path) -> Dijkstra Algo

$O((|V|+|E|)|V|)$
with min heap : $O((|E| + |V|)log(|V|))$

visited[vertex];
dist[vertex];

Dijkstra(Graph G, int src) {
	vesited[src] = true;
	dist[src] = 0;
	int dijIdx = 0;
	dijSeq[dijIdx] = src;
	for(dijIdx = 1; dijIdx < V_NUM; dijIdx++) {
		int V;
		int minDist = INT_MAX;
		int minV;
		for(V = 0; V < V_NUM; V++) {
			if(!visited[V] && dist[V] < minDist) {
				minV = V;
			}
		}
		visited[V] = true;
		for(each W adjacent to V) {
				dist[W] = min(dist[W], dist[V] + edge[V][W]);
		}
	}
}

Weighted Graph with negative weight (Shortest Path)

$O(|V|\times|E|)$

dist[src] = 0
enqueue(src);
while(!que.empty()) {
	int V = dequeue();
	for(each W adjacent to V) {
		update min dist of W;
		if(ranges::find(que.begin(),que.end(), W) == que.end()){ //not found
			enqueue(W)
		}
	}
}

Minimal Spanning Tree

Prim’s Algo

int src;
dist[src] = 0;
visited[src] = true

for(each W adjacent to src) {
	update dist[W];
}
for(int i = 1; i < V_NUM; i++) {
	find an unvisited vertex with minimal dist = V
	for(each W adjacent to V) {
		update dist[W];
	}
	MST[cnt++] = W;
}

Kruskal’s Algo

Kruskal(G):
1. Sort all the edges of graph G in non-decreasing order of their weight.
2. Initialize an empty set MST to store the minimum spanning tree.
3. for each edge e in the sorted edge list:
4.     if adding edge e to MST does not form a cycle:  //using disjoint Set
5.         Add edge e to the MST.
6. Return MST.

Uniqueness of MST

• perform Kruskal’s algo
   - when encountering an edge where the starting point and ending point are already in the same connected component, the code checks if this edge has been marked as known. If the edge is marked as known, it indicates that this edge is not a unique minimum spanning tree edge

maximum flow problem

Ford-Fulkerson algo

time complexity : $O(f\cdot |E|)$

function FordFulkerson(Graph, source, sink):
    for each edge in Graph:
        (u, v) = edge.start, edge.end
        edge.flow = 0

    maxFlow = 0
    while (there is a path from source to sink in the residual network):
        // Find the path with available capacity in the residual network
        pathFlow = findPath(Graph, source, sink)

        // Update the flow along the path
        for each edge in the path:
            edge.flow += pathFlow
            reverseEdge(edge).flow -= pathFlow

        // Add path flow to overall flow
        maxFlow += pathFlow

    return maxFlow

Find strongly connected components

1. DFS -> get a sequence
2. reverse Graph
3. DFS : source node according to the sequence (unvisited->add to a connected component)

Bi-connectivity - Find Articulation Point

Acyclic Graph (AOE network)

Earliest Event Latest Event Earliest Activity Latest Activity

Slack time = Latest Activity - Earliest Activity

Euler Circuit(destination = source)/Tour

Undirected

• Circuit: all vertex have even degree
• Path: only two vertices have odd degree

Directed

• Circuit: every vertex indegree == outdegree
• Path: only one vertex indegree = outdegree + 1, another outdegree = indegree + 1

Sorting

Any ALGO that sort by exchanging adjacent elements requires $\Omega(N^{2})$ eliminate one inversion once
Any ALGO sorting by comparison only worst case $O(NlogN)$

Common stable sorting algorithms include:

1. Bubble Sort
2. Insertion Sort
3. Merge Sort
4. Radix Sort

Common unstable sorting algorithms include:

1. Selection Sort
2. Quick Sort
3. Shell Sort
4. Heap Sort

Bubble Sort

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        for (int j = 0; j < n-i-1; j++) {
            if (arr[j] > arr[j+1]) {
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

Insertion Sort

void insertionSort(int arr[], int n) {
    int i, key, j;
    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

Merge Sort

void merge(int arr[], int l, int m, int r) {
    // Merge two subarrays of arr[]
    // First subarray is arr[l..m]
    // Second subarray is arr[m+1..r]
    // Merge the subarrays
}

void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
        merge(arr, l, m, r);
    }
}

Selection Sort

void selectionSort(int arr[], int n) {
    int i, j, min_idx;
    for (i = 0; i < n-1; i++) {
        min_idx = i;
        for (j = i+1; j < n; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }
        int temp = arr[min_idx];
        arr[min_idx] = arr[i];
        arr[i] = temp;
    }
}

Shell Sort (with Shell Increment)

void shellSort(int arr[], int n) {
    for (int gap = n/2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; i++) {
            int temp = arr[i];
            int j;
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
                arr[j] = arr[j - gap];
            }
            arr[j] = temp;
        }
    }
}

Shell Increment

best case $O(kN)=O(N)$
worst case $O(N^{2})$

Hibbard Increment

worst case $O(N^{\frac{3}{2}})$
average case $O(N^{\frac{5}{4}})$

Heap Sort

build Heap $O(N)$ or $O(logN)$
delete min for N times ($O(N\cdot logN$)
the space requirement is doubled (malloc an extra buffer to store the sorted array)

Q Sort

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}


int mediumThree(int A[], int left, int right) {
    int center = (left + right) / 2;
    if (A[left] > A[center])
        swap(&A[left], &A[center]);
    if (A[left] > A[right])
        swap(&A[left], &A[right]);
    if (A[center] > A[right])
        swap(&A[center], &A[right]);

    swap(&A[center], &A[right - 1]);
    return A[right - 1];
}

void Qsort(int A[], int left, int right, int cutoff) {
    if (right - left >= cutoff) {
        int pivot = mediumThree(A, left, right);
        int i = left;
        int j = right - 1;

        for (;;) {
            while (A[++i] < pivot) {}
            while (A[--j] > pivot) {}

            if (i < j) {
                swap(&A[i], &A[j]);
            } else {
                break;
            }
        }

        swap(&A[i], &A[right - 1]);

        Qsort(A, left, i - 1, cutoff);
        Qsort(A, i + 1, right, cutoff);
    }
}

$T(N) = T(i) + T(N-i-1)+cN$
worst case : $T(N)=T(N - 1)+cN=O(N^{2})$ every pivot is the first element
best case : $T(N)=2T(\frac{N}{2})+cN=O(NlogN)$
average case : $O(NlogN)$

qsort(void* base, size_t num, size_t size, int(*cmp)(const void* a, const void* b))

int cmp(const void* a, const void* b) {
	return *((int*)a) - *((int*)b);
	//return *((int*)b) - *((int*)a);
}

Bucket Sort

The key is to know the range in advance and then allocate different buckets reasonably.

Radix Sort

First compare the numbers with the smallest impact on the data (ones place) Put them into buckets 0-9 respectively Then compare the tens place and put them into buckets 0-9 in order Finally, compare the hundreds place

Another example is sorting playing cards by suit first and then by number.

$$$$