資訊二乙 11027248 陳品澔 筆記
# 第五章 堆疊
先進後出
### 迴文
先讀前半部進stack,後檢查並消除,若不一樣長return false
### ADT
>isEmpty
>push
>pop
>getTop
### 比較
pointer: more efficient
ADT list: much simpler, save time
### 後序計算
數字放進去,遇運算子pop掉並計算,算完放回去stack.
### 應用
路線圖, 迷宮, 最短路徑
# 第六章 佇列
佇列 = 排隊
先進先出
## ADT queue operations
create an empty queue 解構
destroy a queue 建構
determine whethe is empty 是否為空
Add 新增
Remove 移除
Retrieve 擷取
### 一般連結串列
``` c
void Queue enqueue(queueitem &newitem){
newPtr->item = newitem ;
newPtr->next = NULL ;
if(isEmpty())
frontPtr = newPtr ;
else backPrt->next = NewPtr ;
backPtr = newPtr ;
} // end enqueue
```
```c
void dequeue(){
if(isEmpty())
cout << "error" ;
else {
QueueNode *tempPtr = frontPtr ;
if(frontPtr = backPtr){
frontPtr = NULL ;
backPtr = NULL ;
}
else frontPtr = frontPtr->next ;
tempPtr->next = NULL ;
delect tempPtr ;
}
}
```
### 環狀連結串列
``` c
void Queue enqueue(queueitem &newitem){
newPtr->item = newitem ;
if(isEmpty())
newPtr->next = newPtr ;
else {
NewPtr->next = backPrt->next ;
backPtr->next = newPtr ;
}
backPtr = newPtr ;
} // end enqueue
```
```c
void dequeue(){
if(isEmpty())
cout << "error" ;
else {
QueueNode *tempPtr = backPtr->next ;
if(backPtr == backPtr->next)
backPtr = NULL ;
else backPtr->next = tempPtr->next ;
tempPtr->next = NULL ;
delect tempPtr ;
}
} // end dequeue
```
### 環狀陣列
```c
bool isEmpty(){
return (!isFull)&&(front ==(back+1)%MAX_QUEUE);
}
void enqueue(Queueitem newitem){
if(isFull == true)
throw ;
else {
back = (back+1)%MAX_QUEUE ;
items[back] = newitem ;
if(front == (back+1)%MAX_QUEUE)
isFull = true ;
}
}
void dequeue(){
if(isEmpty())
throw ;
else {
front = (front+1)%MAX_QUEUE ;
if(isFull == true)
isFull = false ;
}
}
```
# 第七章 演算法效率
### Alogorithm Growth Rates
n^2 and n are growth-rate functions 成長函數
Alogorithm A is O(n^2) order n^2
Alogorithm B is O(n) order n
* Properties of growth-rate functions
O(5f(n)) = O(f(n)): ignore umltiplicate constant
O(f(n)) + O(g(n)) = O(f(n)+g(n))
### Stable Sort
Stable: bubble, insertion, merge, radix
Unstable: selection, quick, heap
## Insertion Sort
```c=
void insertionSort(int A[], int n){
for(int unstored = 1;unstored < n;unstored++){
int loc = unstored ;
int nextItem = A[unstored] ;
for(;(loc >= 0)&&(A[loc-1] > nextItem);loc--) // >= unstable
A[loc] = A[loc-h] ;
A[loc] = nextItem ;
}
} // 由小到大
```
## ShellSort
```c=
void shellSort(int A[], int n){
for(int h = n/2;h > 0;h = h/2)
for(int unstored = h;unstored < n;unstored++){
int loc = unstored ;
int nextItem = A[unstored] ;
for(;(loc >= h)&&(A[loc-h] > nextItem);loc = loc - h)
A[loc] = A[loc-h] ;
A[loc] = nextItem ;
}
} // 由小到大
```
## MergeSort O(n*logn)
先分組再合併 O(n*logn)*O(n)
```c=
void mergeSort(int Array[], int first, int last){
if(first < last){
int mid = (first+mid)/2 ;
mergeSort(Array, first, mid) ;
mergeSort(Array, mid+1, last) ;
merge(Array, first, mid, last) ; // 3n-1
}
}
void merge(int Array[], int first, int mid, int last){
int tempArray[MAX_SIZE] ;
int first1 = first, last1 = mid ;
int first2 = mid + 1, last2 = last ;
int index = first ;
for(;(first1 <= last1)&&(first2 <= last2);index++){
if(Array[first1] < Array[first2]){ // <= 是stable
tempArray[index] = Array[first1] ;
first1++ ;
}
else {
tempArray[index] = Array[first2] ;
first2++ ;
}
}
for(;first1 <= last1;first1++, index++)
tempArray[index] = Array[first1] ;
for(;first2 <= last2;first2++, index++)
tempArray[index] = Array[first2] ;
for(index = first;index <= last;index++) // 寫回資料
Array[index] = tempArray[index] ;
}
```
## QuickSort O(n*logn)
先分組後遞迴呼叫
* average case:O(n*logn)
* worst case:O(n^2)
```c=
void quickSort(int Array[], int first, int last){
int pivotIndex ;
if(first < last){
partition(Array, first, last, pivorIndex) ;
quickSort(Array, first, pivotIndex-1) ;
quickSort(Array, pivotIndex+1, last) ;
} // if
}
void partition(int Array[], int first, int last, int& pivotIndex){
choosePivot(Array, first, last) ;
int pivot = Array[first] ;
int lastS1 = first+1 ;
int firstUnknown = first+1 ;
while(firstUnknown <= last){ // 分組
if(Array[firstUnknown] < pivot){
lastS1++ ;
swap(Array[lastS1], Array[firstUnknown]) ;
}
firstUnknown++ ;
} // while()
swap(Array[first], Array[lastS1]) ;
pivotIndex = lastS1 ; // 放回最後
}
```
## Radix Sort O(n)
先分組後串接 O(2*n*d)
由餘數來分組最後組合起來
# 第八章 樹
### position oriented ADTs: 位置導向
example:list, stack, queue, binary tree
### Value-oriented ADTs: 內容導向
example:sort list, binary search tree
### Terminology
parent and child between two nodes
ancestor-descendant among nodes
subtree 子樹
Root : the tree with no parent
Leaf : a node with no child
Siblings : nodes with a common parent
ancestor of node : 往上同一條線上
descendant of node : 往下同一條線上
## Binary tree
最大階層等於樹高
若空 height = 0
### Full binary tree
除了leafs以外都有node都有兩個child
### Complete binary tree
It is full to level-h, 而且最下層盡可能往左靠
>leftChild = 2*parent + 1
rightChild = 2*parent + 2
parent = (child-1) / 2
### Balanced binary tree
子樹樹高相差不超過一
leaf nodes = internal nodes + 1
前序 在遞迴之前 root->left->right
中序 在遞迴中間 left->root->right
後序 在遞迴之後 left->right->root
前序和後序不可還原成一棵樹
build a binary search tree by insertion
average: O(n*logn)
worst: O(n^2)
Sign in with Wallet
Connect another wallet