---
# System prepended metadata

title: Data Struct - Class Note
tags: [Data Struct]

---

# 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
````c=
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結構 ： 

```c=
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 : 
```c=
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
```c=
 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. 