# 資料結構 Data Structure
:::info
:::spoiler Click to Open TOC
[TOC]
:::
:::spoiler 成績算法
* 小考+手寫作業：10%
* 程式作業：20%
* 出席：5%
* 期中考2次，各15%，共30%
* 期末考：20%
* 上機考：15% (據說考的跟作業一樣)
* 加分：考CPE，對1題加總分1分
:::
:::spoiler 修課規定
* 程式語言：<b>限</b> C or C++
* 每週都有程式作業
- 用[online judge](https://dsoj.ncu.edu.tw/)交
- 期限為一週(太難則會延長)
:::
## Chapter 1 Basic Concepts
### **1-1 System Life Cycle**
#### <font color="#FFAF60">【Five Points】</font>
* Requirements
* Analysis： **bottom-up vs. top-down**
* Design： **data objects** and **operations**
* Refinement(精細) and Coding
* Verification
* Program Proving
* Testing
* Debugging
$\quad$
### **1-2 Alorithm Specification**
#### <font color="#FFAF60">【Selection sort 選擇排序法】</font>
定義：在未排序序列中找到最小or大的元素
存放到排序序列的起始位置(放到最左邊)
範例：
有一未排序過陣列A如右 <font color="#69E147">`{30, 10, 50, 40, 20}`</font>，欲透過**選擇排序法**排序
1. 從A[0]開始向右找一輪(意即從A[0]~A[4])，找出最小的元素
2. 找一輪後發現最小的是A[1]的10，要將A[1]的10放到陣列的最左邊。此時有兩種做法：
- 用新陣列：將10放到新陣列的最左邊
- 用原來的：將A[1]與A[0]對調，使陣列變成 <font color="#69E147">`{10, 30, 50, 40, 20}`</font>
(老師用的方法是在原來的陣列進行交換，本共筆也以此為範例)
3. 第二輪開始，由於上一輪已將最小值10排好，排在A[0]
因此這輪從A[1]開始往後找最小值，找一輪後會發現最小值為20，位於A[4]
4. 將20移到10的後面(意即目前 *A[1]的30* 與 *A[4]的20* **對調**)
移動好的陣列會變成 <font color="#69E147">`{10, 20, 50, 40, 30}`</font>
5. 第三輪開始，以此類推往下做。應該會得到 <font color="#69E147">`{10, 20, 30, 40, 50}`</font>
> 補充：如何將陣列兩元素對調
> 上面的範例有提到將陣列中的兩個元素對調，在程式當中要如何呈現呢？
> 我們可以自定義函式來完成它，範例程式碼如下：
> ```c=
> #define SWAP(x,y,t)((t)=(x),(x)=(y),(y)=(t))
> //t是暫存的變數，透過t來暫存x，讓x可以去取得y的值
> temp = list[i];
> list[i] = list[j];
> list[j] = temp;
> ```
老師的選擇排序法程式碼：
```c=
void sort(int list[], int n)
{
int i, j, min, temp;
for (i = 0; i < n-1; i++)
{
min = i;
for (j = i+1; j < n; j++)
{
if (list[j] < list[min])
min = j;
}
SWAP(list[i], list[min], temp);
}
}
```
$\quad$
#### <font color="#FFAF60">【Binary search 二分搜尋法 (簡稱：二分搜)】</font>
定義：資料 <font color="red">**排序好**</font> 的情況下尋找特定數字
特色：不從頭開始找，而是從 **中間** 開始找
範例：
有一排序過陣列B如右 <font color="#69E147">`{8, 14, 26, 30, 43, 50, 52}`</font>，欲透過**二分搜尋法**搜尋 `43`
1. 陣列B總共有7個元素，分別從B[0]~B[6]，此時取B[$\frac{0+6}{2}$]=B[3]=30
2. 拿30與想要搜尋的數字(43)進行比較，發現30<43。
因此可以推斷，43一定在B[3]的右邊or不存在陣列B裡
3. 改從B[4]~B[6]當中來找43，此時取B[$\frac{4+6}{2}$]=B[5]=50
4. 拿50與想要搜尋的數字(43)進行比較，發現50>43
因此可以推斷，43一定在B[5]的左邊or不存在陣列B裡
5. 綜合 `2`、`4` 所述，唯一還沒被找過的是B[4]。
若B[4]=43，則表示搜尋成功；若B[4] != 43，表示43不在陣列B裡面
範例程式碼如下：
```c=
int binsearch (int list[], int searchNum, int left, int right)
{
/* search list[0] <= list[1] <= … <= list[n-1] for searchnum.
Return its position if found. Otherwise return -1 */
int middle;
while (left <= right)
{
middle = (left + right)/2;
switch ( COMPARE (list[middle], searchnum))
{
case -1:
left = middle + 1;
break;
case 0 :
return middle;
case 1 :
right = middle – 1;
}
}
return -1;
}
```
:::warning
:warning: $\;$請留意！上面程式碼第9行的 `COMPARE` 係Java的用法，但考試時只能用C、C++
:::
$\quad$
#### <font color="#FFAF60">【1.2.2 Recursive Algorithms】</font>
> ##### A funtion as something that is invoked (called) by another function.
They may call other functions that invoke the calling function again<font color="#69E147">
( **indirect recursion** 間接)</font>.
* ex. A call B, B call A, which is **extremely powerful**.
This perspective ignores the fact that functions can call themselves(direction recursion).
* ex. A call A.
> Use this algorithm when the problm itself is defined recursively.
範例程式碼如下：
```c=
int binsearch (int list[], int searchNum, int left, int right)
{
/* search list[0] <= list[1] <= … <= list[n-1] for searchnum.
Return its position if found. Otherwise return -1 */
int middle;
if (left <= right)
{
middle = (left + right)/2;
switch ( COMPARE (list[middle], searchNum))
{
case -1:
return binsearch(list, searchNum, middle + 1, right);
case 0 :
return middle;
case 1 :
return binsearch(list, searchNum, left, middle - 1);
}
}
return -1;
}
```
### **1-3 Permutation**
透過程式的方式，完成排列(Permutation)。例如，`a, b, c` 三個字母會有6種排列方式
定義：產生 list[i] 到 list[n] 的所有排列
程式碼：
> [name=songchiu]
```c=
#include<stdio.h>
#define SWAP(x,y,t) ((t)=(x), (x)=(y), (y)=(t))
void perm(char *list, int i, int n)
{
int j,temp;
if(i == n)
{
for(j=0; j<n; j++)
{
printf("%c", list[j]);//print out result
}
printf("\n");
}
else
{ /*list list[i] to list[n] has more than one permutatio,
generate these resursively*/
for(j=i; j<n;j++)
{
SWAP(list[i], list[j], temp);
perm(list, i+1, n);//用遞迴的方式去執行
SWAP(list[i], list[j], temp);
}
}
}
int main(void)
{
char list[5]={'a', 'b', 'c', 'd', 'e'};
perm(list, 0, 5);//列出5個字母的所有排列情況
return 0;
}
```
$\quad$
### 1-4 Performance Analysis
[【演算法】時間複雜度與空間複雜度Time & Space Complexity](https://jason-chen-1992.weebly.com/home/time-space-complexity)
#### <font color="#FFAF60">【Space Complexity 空間複雜度】</font>
公式：$S(P)=C+S_P(I)$
- $S(P)$: 總共的空間複雜度
- $C$: 固定會用到的一些空間，與輸入、輸出的內容無關
- $S_P(I)$ : 執行時所用的空間，與型態、大小、輸入輸出...等內容有關
由於 $C$ 是常數，因此空間複雜度取決於 $S_P(I)$
範例：
* $S_{abc}(I)=0$
```c=
float abc(float a, float b, float c)
{
return a+b+b*c+ (a+b-c)/(a+b)+4.00;
}
```
* $S_{sum}(I)=S_{sum}(n)=0$
```c=
float sum(float list[], int n)
{
float tempsum=0;
int i;
for(i=0; i<n; i++)
{
tempsum += list[i];
}
return tempsum;
}
```
$\quad$
#### <font color="#FFAF60">【Time Complexity 時間複雜度】</font>
公式：$T(P)=C+T_P(I)$
- $T(P)$: 總共的時間複雜度
- $C$: 固定會用到的一些時間，例如編譯程式(compile time)
- $T_P(I)$ : 運作這支程式所花的時間，例如跑迴圈(run or execution time)
一些會看到的符號：
- $O \rightarrow$ 上限 **(最常使用)**
- $\Omega \rightarrow$ 下限
- $\Theta \rightarrow$ 比較貼近答案的估計
$\quad$
## Chapter 2 Arrays and Structures
### **2-1 The Array as an ADT**
#### 【Implementation of 1-D array】
- list[0] $\quad \quad \quad$ //base address = $\alpha$
- list[1] $\quad \quad \quad$ //address = $\alpha$ + $1 \ast$ sizeof(int)
- list[n] $\quad \quad \quad$ //address = $\alpha$ + $n \ast$ sizeof(int)
- 以此類推
#### 【$int$ *list1 vs. $int$ list2[5]】
**Same**: list1 and list2 are pointers.
**Difference**: list2 reserves <font color = red>**5 locations**</font>.
**Notation:**
list2 － a pointer to list2[0]
(list2 + i) － a pointer to list2[i] (&list2[i])
***(list2 + i) － list2[i]**
### **2-2 Structures and Unions**
【**Padding**】
```c=
Struct {
char a;
char b;
int c;
} var;
```
【**Unions**】
>only one field of the union is "active" at any given time.
```c=
typedef struct sex_type{
enum tag_field{female, male} sex;
union{
int children;
int beard;
} u;
};
typedef struct human_being{
char name[10];
int age;
float salary;
date dob;
sex_tyoe sex_info;
};
```
$\quad$
【**Self-Referential Structures**】
```c=
typedef struct list {
char data;
list *link; //指向list的一個資料指標
}
```
### **2-3 The Polynomial ADT**
#### 【Polynomial】
```c=
#define MAX_degree 101
/*MAX degree of polynomial+1*/
//指數跨度大不適用
typedef struct{
int degree;
float coef [MAX_degree];
}polynomial;
#define MAX_TERMS 100
/*size of terms array*/
//指數跨度大適用
typedef struct{
float coef;
int expon;
}polynomial;
```
#### 【Global array】
>Use one global array to store all polynomials
* 適合長短差異大、稀疏的多項式
* 相加完的結果放在 avail
### **2-4 The Sparse Matrix ADT**
#### 【Introduction】
* Standard repretation of a matrix
* a[MAX_ROWS][MAX_COLS]
* Sparse Matrix wastes space
* store only nonzero elements
* characterized by <font color="#69E147">**(row, col, value)**</font>
```c=
#define MAX_TERMS 101 //maximum number of terms +1
typedef struct{
int col;
int row;
int value;
}term;
term a[MAX_TERMS];
```
### 【**Fast Transpose** 快速轉置矩陣】
定義: Assign $A[i][j]$ to $AT[j][i]$
時間複雜度: $O(colsB + totalb)$
```c=
void fast_transpose(term a[], b[]){
int row_terms[MAX_COL], starting_terms[MAX_COL];
int i, j, num_cols = a[0].col, num_terms = a[0].vaule;
b[0].row = num_cols;
b[0].col = a[0].row;
b[0].value = num_terms;
if(num_terms > 0){
for(int i = 0; i < num_cols; i++)
row_terms[i] = 0;
for(int i = 0; i <= num_terms; i++)
row_terms[a[i].col]++;
starting_pos[0] = 1;
for(int i = 0; i < num_cols; i++)
starting_pos[i] = starting_pos[i-1] + row_terms[i-1];
for(int i = 0; i <= num_terms; i++){
j = starting_pos[a[i].col]++;
b[j].row = a[i].col;
b[j].col = a[i].row;
b[j].value = a[i].value;
}
}
}
```
## Chapter 4 Lists
### 4-1 Pointer
#### 【**Problem**】
* Arbitrary(隨心所欲) insertion and deletion from arrays can be very time-consuming.
* Waste storage
**Solution：** using <font color=red>**linked** representation</font>
* In a linked, representation these two sequences need **not** to be the same as in the ordered list.
* Store the **address, or location, of the next element** in that list in order to access elements in the correct order with each element.
* Associated with each list element is a node which contains both a data component and a pointer to the next item in the list.
### 4-6 Circularly Linked List
#### 【**Advantage**】
1. **Any node can be a starting point**. We can **traverse the whole list** by starting from any point. We just need to **stop** when the first visited node is visited again.
2. Useful for implementation of queue. Unlike Queue – Linked List implementation, we **don’t need to maintain two pointers** for front and rear if we use circular linked list. We can **maintain** a pointer to **the last inserted node** and **front** can always be **obtained as next of last**.
3. Circular lists are useful in applications to **repeatedly go around the list**.
4. 讓最後一個node很好找
#### 【**Head Node**】
>讓我們知道**最後一個**節點或**第一個**節點
### 4-7 Equivalence Relations
#### 【Input Equivalence Pairs i **$\equiv$** j】
```c=
scanf("%d%d", &i, &j);
while( i >= 0){
x = (node_pointer)malloc(sizeof(node));
if(IS_FULL(x)){
fprintf(stderr, "The memory is full\n");
exit(1);
}
x->data = j;
x->link = seq[i];
seq[i] = x;
x = (node_pointer)malloc(sizeof(node));
if(IS_FULL(x)){
fprintf(stderr, "The memory is full\n");
exit(1);
}
x->data = i;
x->link = seq[j];
seq[j] = x;
}
scanf("%d%d", &i, &j);
```
#### 【Find all pairs of the form **<i,j>**】
```c=
for(int i = 0; i < n; i++){
if(out[i]){
printf("%d", i);
out[i] = FALSE; //標記被找到了
x = seq[i];
top = NULL; // 初始化stack
}
for(;;){ //find rest of class
while(x){
j = x->data;
if(out[j]){
printf("%d", j);
out[j] = FALSE;
y = x->link;
x->link = top;
top = x;
x = y;
}
else
x = x->link;
}
if(!top)
break;
x = sep[top->data];
top = top->link; //unstack
}
}
```
### 4-8 Doubly Linked List
#### 【**Disadvantage** of Singly Linked List】
原因： 因為我們可以藉由更改link的指向，輕易地移動Singly Linked List
```c=
typedef struct node *node_pointer;
typedef struct node{
node_pointer llink;
element item;
node_pointer rlink;
};
```
#### 【**Insertion**】
```c=
void dinsert(node_pointer node, node_pointer newnode){
newnode->llink = node;
newnode->rlink = node->rlink;
node->rlink->llink = newnode;
node->rlink = newnode;
}
```
#### 【**Deletion**】
```c=
void ddelete(node_pointer node, node_pointer deleted){
if(node == deleted)
printf("Deletion denied");
else{
deleted->llink->rlink = deleted->rlink;
deleted->rlink->llink = deleted->llink;
free(deleted);
}
}
```
## Chapter 5 Trees
**A <font color=green>tree</font> is a finite set of on or more nodes**
* There is a specially designated node called <font color=red>**root**</font>.
* The remaining nodes are partitioned into $n\geq0$ disjoint set $T_{1},...,T_{n}$, which are called the **subtrees** of the root.
Sign in with Wallet
Connect another wallet