# ch1
* binary_search
* perm
# ch2-1

* structure/union/enum
* 怎麼令陣列

# ch2-2
* attach=接到答案d(x)上

# ch2-3
## 矩陣旋轉
bad

good
* numterm=有幾個非0元素
* row_terms=轉置後矩陣每row有幾個
* starting_pos[n]=starting_pos[n-1]+row_terms[n-1]

# ch2-4
無
# ch3-1
* queue front指向頭的前一格，rear指向尾

# ch3-2
## 迷宮

1.mark=紀錄是否走過的另一張地圖
2.dir=方向(共8個方位)
3.top=stack最上方index
4.position為走過的點，並含col,row和尚未嘗試過的方位

## 評估表達式
### precedence rule+associatuve rule?

### postfix轉為infix(使用stack)

數字堆進stack，讀到符號後pop出兩個元素與符號結合

### infix轉為postfix

用看的

or

i(in)s(stack)p(precedence)
i(in)c(comin)p(precedence)

符號要進stack前，必須把所有isp大於等於自己icp的全部pop到output才能進入stack

# ch4-1 Linklist
malloc/free

Linklist 插入刪除

* 如果沒有trail=>表示node在最前面

\*node 為一儲存記憶體位置的"變數"
\*\*node 為上者的指標

# ch4-2
## 用linklist做stack
## 用linklist做queue
* (front)item1>item2>item3>NULL(rear)
相反的話，要加東西不難，但要移除東西將困難

* if(*front)=若非空queue,插入node
否則將front設為node

最後，無論如何rear皆為node

## 多項式加法

## erase poly
* 不能直接free ptr

(top)first>null
(top)second>first>null

# ch4-3
## invert
* 不先移到定位是為了用lead測試是否為空linkedlist
* 確認不是空linklist後
1.trail,middle,lead皆前移一格
2.middle->link=trail
## 環狀linklist，便於回收
* 1.先用temp記住ptr的下一格作為開頭
2.ptr連接到欲回收陣列
3.avail(可能為內部變數?)=temp
4.~~free(ptr)~~*ptr=NULL

## evquivalence Relations
* if(out[j]){編織stack},x指向要放進stack的東西，top指向目前stack頂端

* seq[i]的stack編織完後 x=null，接下來開始pop

# 其他
注意*在函式內的用法:函式內*ptr=外面的ptr

posfix>infix:數字入stack
infix>posfix:符號入stack

# 上機考

避免空linklist
# ch1
## 二分搜/排列

#include <bits/stdc++.h>
using namespace std;

int binary_search(int data[],int target,int left,int right){
	if(right>=left){
		int i=(right+left)/2;
		if(data[i]>target){
			return binary_search(data,target,left,i-1);//要加return 
		}else if(data[i]<target){
			return binary_search(data,target,i+1,right);
		}else{
			return i;
		}
	}
	return -1;
}

void perm(int data[],int left,int right){//right不變 
	if(left==right){
		for(int i=0;i<=right;i++){
			cout<<data[i]<<" ";
		}
		cout<<endl;
	}else{
		for(int i=left;i<=right;i++){
			swap(data[left],data[i]);
			perm(data,left+1,right);//是left非i 
			swap(data[left],data[i]);
		}
	}
}

int main(){
	int data[]={1,2,4};
	//cout<<binary_search(data,9,0,4);
	perm(data,0,2);
	return 0;
}

# ch
## 迷宮

# include<iostream>
# include<stack>
using namespace std;

class cor{
	public:
	int row;
	int col;
	cor(int first,int second){
		row=first;
		col=second;
	}
};
int main(){
	int rows,cols;
	cin>>rows>>cols;
	int maze[102][102];
	fill(&maze[0][0], &maze[0][0] + 102 * 102, 1);
    for (int i = 1; i <=rows; i++) {
        for (int j = 1; j <=cols; j++) {
			cin>>maze[i][j];
        }
    }
    stack<cor> data;
    stack<cor> ans;
    cor temp(1, 1);
    data.push(temp);
    
    maze[1][1]=2; //test
    
    while(1){
    	if(data.top().row==rows && data.top().col==cols){
    		break;
		}
		if(maze[data.top().row+1][data.top().col]==0){//down
    		temp.row=data.top().row+1;
    		temp.col=data.top().col;
			data.push(temp);
			maze[data.top().row][data.top().col]=2;
		}
		else if(maze[data.top().row][data.top().col+1]==0){//right
			temp.row=data.top().row;
    		temp.col=data.top().col+1;
			data.push(temp);
			maze[data.top().row][data.top().col]=2;
		}
		else if(maze[data.top().row][data.top().col-1]==0){//left
			temp.row=data.top().row;
    		temp.col=data.top().col-1;
			data.push(temp);
			maze[data.top().row][data.top().col]=2;
		}
		else if(maze[data.top().row-1][data.top().col]==0){//up
			temp.row=data.top().row-1;
    		temp.col=data.top().col;
			data.push(temp);
			maze[data.top().row][data.top().col]=2;
		}
		else{//no road
			data.pop();
		}
		if(data.empty()){
			cout<<"Can't reach the exit"<<endl;
			break;
		}
	
	}
	
	while(!data.empty()){
		ans.push(data.top());
		data.pop();
	}
	while(!ans.empty()){
		cout<<"("<<ans.top().row-1<<","<<ans.top().col-1<<")"<<endl;
		ans.pop();
	}
	

    return 0;
}

## 翻轉矩陣

#include <bits/stdc++.h>
using namespace std;

struct martix{
	int row;
	int col;
	int value;
};

int main(){
	int row,col,value,newposition;
	cout<<"orignal: "<<endl;
	cin>>row>>col>>value;
	map<int,int> data;
	martix *a=new martix[value+1];//動態陣列
	martix *b=new martix[value+1];
	a[0].row=row;a[0].col=col;a[0].value=value;
	b[0].row=col;b[0].col=row;b[0].value=value;
	
	for(int i=1;i<=a[0].value;i++){//輸入A矩陣
		cin>>row>>col>>value;
		martix tmp;
		tmp.row=row;
		tmp.col=col;
		tmp.value=value;
		a[i]=tmp;
	}
	for(int i=1;i<=a[0].value;i++){//紀錄每個A矩陣元素col有多少
		data[a[i].col]++;
	}
	int *starting_point=new int[a[0].col];
	starting_point[0]=1;
	for(int i=1;i<a[0].col;i++){//每個不同col元素的起始位置
		starting_point[i]=starting_point[i-1]+data[i-1];
	}
	for(int i=1;i<=a[0].value;i++){//形成B矩陣
		newposition=starting_point[a[i].col];
		b[newposition].col=a[i].row;
		b[newposition].row=a[i].col;
		b[newposition].value=a[i].value;
		starting_point[a[i].col]++;
	}
	cout<<"result: "<<endl;
	for(int i=0;i<=b[0].value;i++){
		cout<<b[i].row<<" "<<b[i].col<<" "<<b[i].value<<endl;
	}
	return 0;
}

## 多項式相加

#include <bits/stdc++.h>
using namespace std;

typedef struct poly *poly_ptr;
struct poly{
	int exp;
	int cof;
	poly* next=nullptr;
};
poly_ptr add(poly_ptr a,poly_ptr b){
		poly_ptr ans,now;
		now=(poly_ptr)malloc(sizeof(poly));
		ans=(poly_ptr)malloc(sizeof(poly));
		now=ans;
		while(a!=nullptr && b!=nullptr){
			poly_ptr tmp;
			tmp=(poly_ptr)malloc(sizeof(poly));
			tmp->next=nullptr;
			if(a->exp>b->exp){
				tmp->exp=a->exp;
				tmp->cof=a->cof;
				a=a->next;
			}else if(a->exp<b->exp){
				tmp->exp=b->exp;
				tmp->cof=b->cof;
				b=b->next;
			}else{
				tmp->exp=b->exp;
				tmp->cof=b->cof + a->cof;
				b=b->next;
				a=a->next;
			}
			now->next=tmp;
			now=tmp;
		}
		while(a!=nullptr){
			poly_ptr tmp;
			tmp=(poly_ptr)malloc(sizeof(poly));
			tmp->exp=a->exp;
			tmp->cof=a->cof;
			tmp->next=nullptr;
			a=a->next;
			now->next=tmp;
			now=tmp;
		}
		while(b!=nullptr){
			poly_ptr tmp;
			tmp=(poly_ptr)malloc(sizeof(poly));
			tmp->exp=b->exp;
			tmp->cof=b->cof;
			tmp->next=nullptr;
			b=b->next;
			now->next=tmp;
			now=tmp;
		}
		return ans->next;
	}
	void output(poly_ptr head){
		while(head != nullptr){
			cout<<head->cof<<"x^"<<head->exp;
			if(head->next==nullptr){
				cout<<endl;
			}else{
				cout<<"+";
			}
			head=head->next;
		}
	}
int main() {
	int exp,cof;
    poly_ptr a,b,a_now,b_now,ans;
    a=(poly_ptr)malloc(sizeof(poly));
	b=(poly_ptr)malloc(sizeof(poly));
	a_now=(poly_ptr)malloc(sizeof(poly));
    b_now=(poly_ptr)malloc(sizeof(poly));
	ans=(poly_ptr)malloc(sizeof(poly));
    a_now=a;b_now=b;
    for(int i=0;i<3;i++){
    	poly_ptr tmp;
		tmp=(poly_ptr)malloc(sizeof(poly));
    	cin>>cof>>exp;
    	tmp->next=nullptr;
    	tmp->cof=cof;
    	tmp->exp=exp;
    	a_now->next=tmp;
    	a_now=tmp;
	}
	   for(int i=0;i<2;i++){
    	poly_ptr tmp;
    	tmp=(poly_ptr)malloc(sizeof(poly));
    	cin>>cof>>exp;
    	tmp->next=nullptr;
    	tmp->cof=cof;
    	tmp->exp=exp;
    	b_now->next=tmp;
    	b_now=tmp;
	}
	ans= add(a->next,b->next);
	cout<<"get ans"<<endl;
	output(ans);
    return 0;
}