---
tags: 大二筆記
---
# 資料結構 上
### IDE Code
WEEK_2：[正課](http://tpcg.io/LPPGDK)
[9.30實習題_Insertion_Sort](http://tpcg.io/ReFUIudS)
[9.30實習題_binary_search](http://tpcg.io/R0V5GY)
[9.30加分題_交集法_DFS](http://tpcg.io/IGWVDP)
WEEK_3：
[10.7實習題_非連續子序列之兩數最大和（Struct & Sort）](http://tpcg.io/C0JIB1)
[10.7延伸題_最大非連續子序列和（DP）](http://tpcg.io/6OEW46)
[10.7加分題_奇數魔方陣](http://tpcg.io/AL4WPS)
## I/O Stream（課外補充）
### I/O 優化（加速輸入輸出 遇TLE可用）
```c=
//取消強制flush
cin.tie(0);
//取消 iostream 與 stdio 的同步使用
ios_base::sync_with_stdio(false);
//不使用 cout << endl
cout << "\n";
```
### StringStream（好工具）
getline 搭配 stringstream
### 輸出
四捨五入cout << fixed << setprecision(10); 或是更高精度 (int)10*位數+0.5
寬度 cout << setw(n) << setfill( c ) <<;
參考資料：
https://cp.wiwiho.me/
## Swap
### Define
```c=
#define swap(x, y, t) ((t) = (x), (x) = (y), (y) = (t))
```
### Call by address (Call by pointer)
```c=
void swap(int *x,int *y){
int tmp=*x;
*x=*y;
*y=tmp;
}
```
### Call by reference
```c=
void swap(int &x,int &y){
int tmp=x;
x=y;
y=tmp;
}
```
## Auto
根據使用型態變化
### 變數宣告
```c=
// int x = 1;
auto x = 1;
// double y = sin(1.3);
auto y = sin(1.3);
```
### 陣列宣告
```c=
// initializer_list<int>
auto A = { 1, 2 };
// initializer_list<int>
auto B = { 3 };
```
### 函式宣告
```c=
// int my_fun();
auto my_fun(){
int value = 3;
return value;
}
```
參考資料：
https://blog.gtwang.org/programming/cpp-auto-variable-tutorial/
https://docs.microsoft.com/zh-tw/cpp/cpp/auto-cpp?view=msvc-160
<br>
## For Loop
使用於任何陣列。
for( auto y : x ){...}
y = x.begin() → x.end()。
```c=
int x[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
//float[]、vector<double>，任何陣列。
```
### Call by value
```c=
for( auto y : x ){
y++;
}
//int x[10] = {1,2,3,4,5,6,7,8,9,10};
```
### Call by reference
可以修改陣列
```c=
for( auto &y : x ){
y++;
}
//int x[10] = {2,3,4,5,6,7,8,9,10,11};
```
參考資料：
https://docs.microsoft.com/zh-tw/cpp/cpp/range-based-for-statement-cpp?view=msvc-160
<br>
## Dynamic Memory Allocation
```c=
int *i;
float *pi;
i=(int*)malloc(sizeof(int));//動態記憶體配置
*i=1024;
pi=(float*)malloc(sizeof(float));//動態記憶體配置
*pi=3.1415;
printf("i=%d,pi=%d",*i,*pi);
free(i);
free(pi);
```
## Selection sort
從未排序中，選擇最小的放進數列中
<img src="https://codepumpkin.com/wp-content/uploads/2017/10/SelectionSort_Avg_case.gif">
```c=
//n為list大小
for(i=0;i<n;i++){ //i之前已排好
for(j=i+1;j<n;j++){ //i之後選擇最小的丟到前面去
if(list[i]>list[j]){
swap(&list[i],&list[j]);
}
}
}
for(i=0;i<n;i++){
printf("%d,",list[i]);
}
```
參考資料：
https://medium.com/appworks-school/%E5%88%9D%E5%AD%B8%E8%80%85%E5%AD%B8%E6%BC%94%E7%AE%97%E6%B3%95-%E6%8E%92%E5%BA%8F%E6%B3%95%E5%85%A5%E9%96%80-%E9%81%B8%E6%93%87%E6%8E%92%E5%BA%8F%E8%88%87%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F%E6%B3%95-23d4bc7085ff
<br>
## Insertion Sort
插入已排列的數列
題目：http://140.121.198.41:20211/contest/5/problem/2
<img src="https://upload.wikimedia.org/wikipedia/commons/9/9c/Insertion-sort-example.gif">
```c=
for(i=1;i<n;i++){ //輪到i去插入
int tmp = list[i]; // tmp = 正處理的值
j=i-1;
while( j>-1 && tmp<list[j] ){
itst[j+1]=list[j]; // 向右移
j--;
}
list[j+1]=tmp; // 插入新值
}
```
參考資料：
http://notepad.yehyeh.net/Content/Algorithm/Sort/Insertion/1.php
<br>
## Bubble Sort
<img src="https://codepumpkin.com/wp-content/uploads/2017/10/BubbleSort_Avg_case.gif">
## Merge Sort
<img src="https://cdn-images-1.medium.com/max/1600/1*d9AkauyhqsMZcLFYhrY3DQ.gif">
## Quick Sort
<img src="https://img-blog.csdnimg.cn/20191109215106141.gif">
## Binary_search
只適用於<font color="#f00">**「已排序」**</font>的數列
題目：http://140.121.198.41:20211/contest/5/problem/1
<img src="https://static.coderbridge.com/img/techbridge/images/huli/binary_search.gif">
### Main
```c=
int mid,L,R,target;
scanf("%d",&target);
L=0,R=n-1;
```
### Recursion
```c=
int binary_search(int L,int R,int list[],int target,int mid){
if(L<=R){ //終止條件
mid=(L+R)/2;
if(target==list[mid]){
return mid;
}
else if(target<list[mid]){
binary_search(L,mid-1,list,target,mid);
}
else{
binary_search(mid+1,R,list,target,mid);
}
}
return -1;
}
```
### Non-Recursion
```c=
int binary_search(int L,int R,int list[],int target,int mid){
while(L<=R){
mid=(L+R)/2;
if(target==list[mid])
return mid;
else if(target<list[mid])
R=mid-1;
else
L=mid+1;
}
return -1;
}
```
### Binary search tree
<img src="https://mmbiz.qpic.cn/mmbiz/QtPIxk7nOVeibpicoibyjNZKic9Ke41yzr53nolQM6w5ibEKzg8GCbbCrSOs75gH6ibzsKuyWLtqfJOgwMW0mibprneEQ/0?wx_fmt=gif">
參考資料：
https://www.gushiciku.cn/dc_tw/101530793
https://blog.techbridge.cc/2016/09/24/binary-search-introduction/
<br>
## 加分題_交集法（DFS）
題目：http://140.121.198.41:20211/contest/5/problem/a1
作法：
1 1 1 1 0 0 0 0 0 0
1 1 1 1 0 1 0 0 0 0
1 1 1 1 0 1 0 1 1 0 >>解答1 回復上一動
1 1 1 1 0 1 0 0 1 1 >>解答2 回復上一動
1 1 1 1 0 0 1 0 0 0
1 1 1 1 0 0 1 0 1 1 >>解答3 回復上一動
1 1 1 1 0 0 0 1 0 0
1 1 1 1 0 0 0 0 1 0
1 1 1 1 0 0 0 0 0 1
...
<img src="https://raw.githubusercontent.com/tg6169/tmp/master/new_dfs.gif">
### DFS
```c=
//input:n=10,inp[0..2]=4,1,2
//Output：0 1 1 1 0 0 0 0 1 0
//index=走訪位置，ans[]=答案，m為inp的序號
void DFS(int index,int m){
if(m==inp_size){//等於最後一個
for(int j=0;j<n;j++){ //check有重複出現的位置。
ans[j]=ans[j]&tmp[j]; //位元運算
}
}
else{
while(index<n){
if(check(index,inp[m])){ //判斷可不可以放進去。
for(int j=0;j<inp[m];j++){ //放入方塊。
tmp[index+j]=1;
}
DFS(index+inp[m],m+1); //進到下一層，左子樹。
for(int j=0;j<inp[m];j++){ //回復上一動，回節點。
tmp[index+j]=0;
}
}
index++;
}
}
}
```
### Check
```c=
bool check(int index,int m){
if((index==0||tmp[index-1]==0)&&(tmp[index+m]==0)&&((index+m)<=n)){
return true;
}
else{
return false;
}
}
```
### Main
```c=
int main() {
cin >> n; //陣列大小
inp_size=0;
while(cin >> inp[inp_size]){ //輸入input
inp_size++;
}
for(int j=0;j<n;j++){ //設為0
tmp[j]=0,ans[j]=1;
}
DFS(0,0);
for(int j=0;j<n;j++){
printf("%d ",ans[j]);
}
return 0;
}
```
## Abstraction
透過語意、規範，隱藏實作過程來簡化程式。
### Data Abstraction
透過資料型態（規範），來包裝各種元素。
* #### Array
```c=
int list[5]={0,1,2,3,4}; //儲存單一型態
```
* #### Structure
```c=
struct student{ //儲存多數型態
char lastName;
int studentId;
char grade;
}
```
### Abstraction Data Type（ADT）
以規範好的行為，去操作資料形態中的物件。
```c=
stack<int> Stack;
Stack.push(...)
Stack.pop
cout << Stack.top();
```
```c=
Bool IsZero(int x){
x==0?true:false
}
Bool Equal(int x,int y){
x==y?true:false
}
```
## Performance Analysis
### Space Complexity
```c=
float rsum(float list[ ], int n){
if(n)return rsum(list, n-1) + list[n-1];
return list[0];
}
```
Total
= float list[ ] + int n + return addres
= 4 + 4 + 4 = 12n
### Time Complexity
1. assignment
2. for loop <font color="#f00">**(n+1)**</font>
3. return
4. conditional
```c=
float sum(float list[ ], int n){
float tempsum= 0; count++; /* for assignment */
int i;
for (i= 0; i< n; i++){
count++; /* for the "for" loop */
tempsum+= list[i]; count++; /* for assignment */
}
count++; /* last execution of "for" */
count++; /* for return */
return tempsum;
}
```
### Asymptotic Notation（O, Ω, Θ）
* #### Big O
f(n) ≤ cg(n) for all n, n≥n<sub>0</sub>
<img src="https://player.slideplayer.com/25/7799420/data/images/img1.jpg">
* #### Omega Ω
f(n) ≥ cg(n) for all n, n≥n0
<img src="https://player.slideplayer.com/25/7799420/data/images/img3.jpg">
* #### Theta Θ
c<sub>1</sub> g(n) ≤ f(n) ≤ c<sub>2</sub> g(n) for all n, n≥n<sub>0</sub>
<img src="https://cdn.programiz.com/sites/tutorial2program/files/theta.png" width="280">
## Fibonacci
### Recursion
```c=
int fibonacci(int n) {
if(n<2){
return n;
}
if(n>=2){
return fibonacci(n-1)+fibonacci(n-2);
}
}
```
### Non-Recursion（DP）
```c=
int fibonacci(long long int n) {
for(int m=0;m<=n;m++){
if(m>=2){
c=a;
a=b;
b=c+b;
}
else if(m<2){
a=0;
b=1;
}
}
if(n<2&&n!=0){
return n;
}
else if(n>=2){
return b;
}
}
```
## 非連續子序列之兩數最大和（Struct & Sort）
### Struct
```c=
struct list {
int value;
int index;
};
```
### Sort compare
```c=
bool compare(list &s1, list &s2){
return s1.value > s2.value;
}
```
### Main
```c=
int main() {
int n,m;
list L[100000]; //struct
/*---------------輸入---------------*/
std::cin >> n;
for(m=0;m<n;m++){
std::cin >> L[m].value;
L[m].index=m;
}
int sub_len=m; //list長度
/*-------------搜尋比對-------------*/
if(sub_len==3){ //spical case：子序列長度=1
std::cout << L[0].value+L[2].value;
}
else{
std::sort(L,L+sub_len,compare); //找出前四大的數
int tmp,max = -INT16_MAX;
for(m=0;m<4;m++){ //比對是否相鄰
for(int i=m+1;i<4;i++){
if(abs(L[m].index-L[i].index)>1){ //比對是否相鄰
tmp=L[m].value+L[i].value; //找出最大和
if(tmp>max){
max=tmp;
}
}
}
}
std::cout << max;
}
return 0;
}
```
參考資料：範例八 https://shengyu7697.github.io/std-sort/
## 課外延伸題_最大非連續子序列和（DP）
### DP（Dynamic programming）
```c=
int sub_max(int* list){
if(sub_len==3){
return list[0]+list[2];
}
int temp[10005];
for(int m=0;m<sub_len;m++){
temp[m]=list[m];
}
temp[0]=list[0];
temp[1]=list[1]>list[0]?list[1]:list[0];
for(int i = 2;i<sub_len;i++){
temp[i]=max(max(temp[i],temp[i-1]),temp[i-2]+list[i]);
}
return temp[sub_len-1];
}
```
### Main
```c=
int main() {
int n,m;
int list[10005];
cin >> n;
for(m=0;m<n;m++){
cin >> list[m];
}
sub_len=m;//list大小,global變數
cout << sub_max(list);
return 0;
}
```
## 加分題_奇數魔方陣
題目：http://140.121.198.41:20211/contest/6/problem/a1
<img src="https://openhome.cc/Gossip/AlgorithmGossip/images/oddArray-2.jpg">
<br>
``` c=
int main(void) {
int square[row][column] = {0};
int N,K;
int r,c; //r=row_index,c=column_index
int r2,c2; //儲存上一步
cin >> N; //space
r=1; //first_step
c=N/2+1;
square[r][c]=1;
for(K=2;K<=N*N;K++){
r--; //下一步
c++;
if (r < 1)r=N; //邊界
if (c > N)c=1;
if(square[r][c]){ //重複出現
r=r2+1; //回到上一步
c=c2;
if(r>N)r=1; //邊界
}
c2=c; //儲存
r2=r;
square[r][c]=K; //放入K
}
return 0;
}
```
參考資料：
https://openhome.cc/Gossip/AlgorithmGossip/OddArray.htm
## Struct
### typedef
## Union
Sign in with Wallet
Connect another wallet