# Data Struct - Class Note
###### tags: `Data Struct`

## 一 . 課堂
1. list : 加入刪除的動作方便，動態空間。
2. node link :
- node : data。
- link : pointer。
3. 初始化pointer : pointer可以直接改變memory，須注意使用細節。
4. malloc 和free要搭配，因為動態分配記憶體是存在heap中的。

## Single link list

typedef struct Node {
    int node;
    struct Node * link;  // self-reference
}Node;

void AddLisk(Node* head, int num){
    if(head==NULL)
    {
        Node* tmp=malloc(sizeof(Node));
        tmp->node=num;
        head=tmp;
        return ;
    }
    Node* tmp=malloc(sizeof(Node));
    tmp->link=head->link;
    head->link=tmp;
    return ;
}

1. self reference : 每一個node指向的data struct是本身的。

### (二) . 用list 實作 stack queue

### (三) . 用list 實作多項式
1. node結構 ：

typedef struct poly_node {
     int coef;
     int expon; 
     struct poly_node* link;
}poly_node;

2. 相加 ：
- 步驟 ： 先比較係數，同則相加。
- 分析 ： 0≦number of coefficient addition≦min{m,n}
- 時間複雜度 ： $O(m+n)$。(兩個長度為ｍ和n的多項式)

3. erase :

void erase (poly_node *ptr)
{
     /* erase the polynomial pointed to by ptr */
      poly_node temp;
      while ( *ptr) { 
         temp = *ptr;
         *ptr = (*ptr) -> link;
         free(temp); 
    }
}
   

### (四) . Circle、Chain

1. circle : 尾巴指向頭。
2. chain : 尾巴指向NULL。

### (五) . 自行管理
1. 另建一個list存放以使用但消除的node。
2. 可以使第一個node為空，可以不用先辨別是否head為空。

### (六) . 連接、反轉

### (七) . 由前面加入、由後面加入circle list。

### (八) . 集合 - 關係 ： 等價關係
1. 定義 ： 兩個集合的一個『關係』(兩個集合的笛卡爾乘積的子集)
- x = x
- x = y implies y = x
- x = y and y = z implies x = z
2. 用DFS

 void  DFS(pointer* node, poiner * father , pointer* group)
 {
     pointer* cur=node;
     while(cur!=NULL)
     { 
        if(cur->val!=father->val)
        {
           AddList(group, cur->val);
           cur=cur->next;
        }
        else
        {
           cur=cur->next;
        }
        DFS(cur, node, group);
     }
 }

3. 時間複雜度 ： $O(m+n)$
- m : 資料數。
- n : 關係個數。

### (九) . 稀疏陣列
1.