---
# System prepended metadata

title: Data Structure 資料結構

---

# Data Structure 資料結構

Stack
---

- 性質
    - 堆疊(疊盤子)
    - Last in First out (LIFO)
        - 最先丟進去的最後拿出來
        - 最後放進去的最先拿出來
![](https://hackmd.io/_uploads/Bk-aPmhx6.png)

- 基本操作
    - push: 把一個元素放進 stack
    - pop: 把一個元素拿出 stack 

### Implement stack by using arrays
- 用一個變數top紀錄頂端的位置
    - when top=-1 stack 是空的
    - push top+1
    - pop top-1
    
#### Example Stack_example.c
- Output pairs (u,v) such that the left parenthesis atposition u is matched with the right parenthesis at v.
    - For example ((a+b)x(c+d))
    - the answer is (1, 5), (7, 11), (0, 12)
![](https://hackmd.io/_uploads/BJAEwXnla.png)


### Homework Homework.c
- 第一部分
  - 使用下列定義及宣稱所創造的堆疊結構：
```c
#define SIZE 100
int stack[SIZE];
top = -1;
```
- 第二部分
  - 能夠同時判斷 () 以及 []
  - Add watch 變數 symb, pos, top, A[top] 之新值
  - 堆疊變化與對應輸出的說明圖（含當時堆疊內容與top指向）

Queue
---
### Remedies
- Define a boolean variable lastOperationIsPush
    - Following each push set this variable to true
    - Following each pop set to false
    - Queue is empty if(front==rear) && !lastOperationIsPush
    - Queue is full if(front==rear) && lastOperationIsPush

- Using `k = rand() % 100` to generate random number 1 to 100

```c
#define SIZE 100
int queue[SIZE]
int front = rear = -1;
int TotalinQueue;

struct queue {
    int  A[SIZE];
    int front, rear;
}

int empty(){
    // if(top==-1) return 1;
    // else return 0;。。
    // return (front == rear && !lastOperationIsAddq);    
    // return (TotalinQueue == 0);
    return (front == rear);
}
int full(){
    // if(top==SIZE-1) return 1;
    // else return 0;
    // return (front == rear && !lastOperationIsAddq);
    // return (TotalinQueue == SIZE);
    return (front == (rear+1) % SIZE);
}
void addq(int x){
    if(full()){
        printf("the queue is full");
        exit(1);
    }
    rear = (rear+1)%SIZE;
    
}
int deleteq(struct queue *pq){
    if(empty(pq)){
        printf("the queue is empty");
        exit(2);
    } 
}

int main(){
    struct queue Q, Q1;
    
    addq(&Q1, Q = deleteq(&Q));
    if(empty(&Q)){
        printf("one-element queue");
        exit(1);
    }
    addq(&S1, k = deleteq(&Q));
    while(!empty(&Q))
        addq(&Q, deleteq(&Q));
    while(!empty(&Q1))
        addq(&Q1, deleteq(&Q1));
}
```


Linked Lists
---
```c=
struct element {
    int data;
    int link;
}
struct element A[100];
```

```c=
typedef int nba;
nba i, j, k;
```

陣列的size過小的時候不夠裝就滿了，過小的話很容易浪費空間。
Linked Lists 的存在就是要多少資料有多少資料

```c=
typedef struct listNode *listPointer;
struct listNode {
    chat data[4];
    listPointer link;
};

listPointer p; 
struct listNode *p; 

malloc(5); // 系統配置 5 個 byte 個空間 
malloc(sizeof(struct listNode));
free(p); // 釋放空間
```

first data = 20 -> first link -> second -> second data = 10 -> second link = NULL
```c=
listPointer create2(){
    listPointer first, second;
    MALLOC(first, sizeof(*first)); // first = (listPointer) malloc(sizeof(struct listNode));
    MALLOC(second, sizeof(*second)); // second = (listPointer) malloc(sizeof(struct listNode));
    second->link = NULL;
    second->data = 20;
    first->data = 10;
    first->link = second;
    return first;
}
```

利用 key 搜尋我們要的 data 並且建立兩個 node 來回傳資料

## Representing Chains in C

![IMG_0682](https://hackmd.io/_uploads/B1Trw0b4T.jpg)
![IMG_0683](https://hackmd.io/_uploads/BkWOuAWET.jpg)
![IMG_0684](https://hackmd.io/_uploads/B1i4UIQE6.jpg)


要 insert 在 node x 的位置進入到這個 Linked Lists 裡面。

- 如果 first 所索引的值為 **NULL** `if(*first == NULL)` 則做 a 部分
- 如果 first 所索引的值不為 **NULL** `if(*first != NULL)` 則做 b 部分
    - 為什麼要 `temp->link = NULL` ？
        - 將此值設置為 NULL 才能指向下一個資料 `*first = temp`

```c=
void insert(listPointer *first, listPointer x) {
    /* insert a new node with data = 50 into the chain
     * first after node x
     */
    listPointer temp;
    MALLOC(temp, sizeof(*temp));
    temp->data = 50;
    if(*first) { // a
        temp->link = x->link;
        x->link = temp;
    }
    else { // b
        temp->link = NULL;
        *first = temp;
    }

}
```

### delete data in Linked list

如果 `trail == NULL` 代表說是第一個 Node，代表要將第一筆資料給 delete 掉
first 所指的為第一個 Node，然後把 first node 指派給 下一個 x->link
`free(x)` 將 x 的記憶體位置給釋放

```c=
temp = *first;
temp = temp->link;
while(temp->link != x)
```

```c=
void delete(listPointer *first, listPointer trail, listPointer x){
    // delete x from the list, trail is the preceding node and *first is the front of the list
    if(trail)
        trail->link = x->link;
    else
        *first = (*first)->link;
    free(x); // 

}
```

將資料 print 出來 從 first 到 最後一個 Node
```c=
void printList(listPointer first){ // first 為第一個 Node 的值 而非位置位置 若為位置則是 *first
    printf("The list contains: ");
    for(; first; first = first->link) // first != NULL
        printf("%4d", first->data);
    printf("\n");
    // for(temp=*first; temp->link != x; temp = temp->link) 
}
```

## Linked stack and queues
- stack implemented by ~~arrarys~~ Linked lists 
    - 利用 Linked lists 的底層來保留空間
- queues implemented by Linked lists

這個寫法不是一個很好的寫法，因為限制了這個 Stacks 的最多數值只能有 10 個而已
```c=
#define MAX_STACKS 10
typedef struct { 
    int key; // 這裡可以有很多的資料 char name; int num; ... 以此類推
} element;
typedef struct stack *stackPointer; // *stackPointer 就如同前面所宣告的 *listPointer
struct stack { // listNode
    element data; 
    stackPointer link; 
};
stackPointer top[MAX_STACKS];

// Linked lists implement in Stack
/* struct stack S, S1;
 * S.top = S1.top = NULL;
 */ 
```

Linked lists implement in Stack
- push 等同於 insert node in the end
    - push ==> insert stack in the front
- pop 等同於 delete node in the end
    - pop ==> delete stack in the front
![IMG_0686](https://hackmd.io/_uploads/Hk7eD87VT.jpg)

```c=
typedef struct listNode *listPointer;
struct listNode {
    int data;
    listPointer link;
};

struct stack {
    listPointer top;
} S, S1;

listPointer top = NULL; // initial empty stack

int empty(struct stack *ps){
    return (ps->top==NULL);
}

void push(struct stack *ps, int x){ // push x onto stack -> insert node in the front
    listPointer p = (listPointer) malloc(sizeof(struct listNode));
    p->data = x;
    p->link = ps->top; // top == NULL
    ps->top = p;
}

int pop(struct stack *ps){ // pop stack and return the popped element -> delete node in the front
    if(empty(ps)) printf("stack is empty");
    listPointer p = ps->top;
    int x = p->data;
    ps->top = p->link;
    free(p);
    return x;
}

// stack 的底層是 Linked list
// 利用 stack 實現 queue 的資料結構

struct stack Q, Q1;

int emptyq(struct stack *q){
    return (empty(q));    
}

void addq(int x, strcut stack *q){
    return (push(x, q));
}

int deleteq(struct stack *q){
    return (pop(q));
}

/* int full(){
 * }
 * 不需要 full() 因為 Linked lists 不會有資料滿出來的問題
 */
```

                

### Linked list implement in queue
```c=
typedef struct listNode *listPointer;
struct listNode {
    int data;
    listPointer link;
};

struct queue {
    listPointer front, rear;
} Q, Q1;

listPointer front = NULL, rear = NULL;

int emptys(struct queue *pq){
    return (pq->front == NULL); 
}

void addq(struct queue *pq, int x){
    listPointer p = (listPointer)malloc(sizeof(struct listNode));
    p->data = x;
    p->link = NULL;
    if(emptys(pq)) pq->front = p;
    else pq->rear->link = p;
	pq->rear = p;
}

int deleteq(struct queue *pq){
    if(emptys(pq)){
        printf("the queue is empty");
        exit(2);
    }
    listPointer p = pq->front;
    int x = p->data; 
    pq->front = p->link; // one-node queue => front = NULL(no need to change rear)
    free(p);
    return x;
}


/* int full(){
 * }
 * 不需要 full() 因為 Linked lists 不會有資料滿出來的問題
 */
```

反轉資料
- before: 1 2 3 4 5
- after:  5 4 3 2 1
```c=
listPointer invert(listPointer lead){
    // invert the list pointed to by lead
    listPointer middle, trail;
    middle = NULL;  // 如果沒有這行的話，trail 有可能是不必要的資料                        
    while(lead){
        trail = middle;
        middle = lead;
        lead = lead->link;
        middle->link = trail;
    }
    return middle;
}
```

![IMG_0728](https://hackmd.io/_uploads/HyywXU4Bp.jpg)

結合資料(將兩個 Linklist 合在一起)
- ptr1 = 1 2 3 4 5
- ptr2 = 6 7 8 9 10
- new data = 1 2 3 4 5 6 7 8 9 10

```c=
listPointer concatenate(listPointer ptr1, listPointer ptr2) {
    /* produce a new list that contains the list
     * ptr1 follwed by the list ptr2.
     * The list poitned to by ptr1 is changed permanetly
    */
    
    // check for empty list
    if(!ptr1) return ptr2;
    if(!ptr2) return ptr1;
    
    // neither list is empty, find end of first list
    for(temp = ptr1; temp->link; temp = temp->link);
    
    // link end of first to strat of second
    temp->link = ptr2;
}
```

插入資料至前方
- 使用此方式的前提必須是 **環狀 List** (circular list)
    - `listPointer Lin2Cir(listPointer first)`
    - `for(temp = ptr; temp->link; temp = temp->link);`  // to find the last data 
    - 然後將 Last 去指向 first 的資料 
- 需要加入一個 last 索引，去指向第一筆資料

```c=
void insertFront(listPointer *last, listPointer node){
    // insert node at the front of the circular list whose last node is last
    if(!(*last)){
        // list is empty, change last to point to new entry
        *last = node;
        node->link = node;
    }
    else {
        // list is not empty, add new entry at front
        node->link = (*last)->link;
        (*last)->link = node;
    }
}
```

```c=
int length(listPointer last){
    listPointer temp;
    int count=0;
    if(last){
        temp = last;
        do {
            count++;
            temp = temp->link;
        } while(temp != last);
    }
    return count;
}
```

insert in the front
```c=
int x;
listPointer save;
temp = first;
while(temp != NULL && x > temp->data){
    save = temp;
    temp = temp->data;
}

// ~(P&Q)
// ~P & Q temp==NULL && x > temp->data (insert in the end) 
// P & ~Q temp!=NULL && x <= temp->data (insert in the middle)
// ~P & ~Q temp==NULL && x<= temp->data (Null list or smallest number) (insert in the front)
```

Doubly linked circular list
```c=
void dinsert(nodePointer node, nodePointer newnode){
    newnode->llink = node;
    newnode->rlink = node->rlink;
    node->rlink->llink = newnode;
    node->rlink = newnode;
}
```

```c=
void ddelete(nodePointer node, nodePointer deleted){
    if(node==deleted) printf("Deletion of header node permitted");
    else {
        deleted->llink->rlink = deleted->rlink;
        deleted->rlink->llink = deleted->llink;
        free(deleted);
    }
}
```

Qustion:
- Q1. 為什麼 rear 不需要設定初始值？
    - addq -> insert in the end
    - pop == deleteq -> delete node from  the front
- Q2. 為什麼可以利用 Stack Linked list 來實現 queue 的資料結構?
- Q3. 要怎麼得獲取到最後一筆 Last 的資料
    - `for(temp=ptr; temp->link; temp = temp->link);`
    - last = temp->link;


## Tree

Node in [n] -> left child will be in [x]
- Right child will be in [y]

Left child x = 2n + 1 (in terms of n)
Right child y = 2n + 2 (in terms of n)

Left child of any node in [x] -> x is odd
Right child of any node in [y] -> y is even

Parent node of any node (in [n]) will be in [x]?

if x is odd -> x = (n-1)/2 (in terms of n)
- left child
if x is even -> x = (n-2)/2 (in terms of n)
- right child

```c=
#define SIZE 100
int tree[SIZE];
```

Tree implement by linked list 
```c=
typedef struct node *treePointer;
struct node {
    int data;
    treePointer leftChild, rightChild;
}
```

```c=
void inorder(treePointer ptr){
    /* inorder tree traversal */
    if(ptr){
        inorder(ptr->leftChild);
        printf("%d", ptr->data);
        inorder(ptr->rightChild);
    }
}

chat tree[100];
tree[0] = "A";
tree[1] = "B";

```

```c=
void preorder (treePointer ptr){ 
    if (ptr){ 
        printf(“%d”,ptr->data);
        preorder (ptr->leftChild);
        preorder (ptr->rightChild);
    }
}
```

```c=
void postorder (treePointer ptr){ 
    if (ptr){ 
        postorder (ptr->leftChild);
        postorder (ptr->rightChild);
        printf(“%d”,ptr->data);
    }
}
```

```c=
void iterInorder(treePointer node){
    int top = -1;
    treePointer stack[MAX_STACK_SIZE];
    for(;;){
        for(; node; node->leftChild)
            push(node);
        node = pop();
        if(!node) break;
        printf("%d", node->data);
        node = node->rightChild;
    }
}

treePointer pop(){
    if(empty()) return NULL;
}
```

```c=
void levelOrder(treePointer ptr){
    int front = rear = 0;
    treePointer queue[MAX_QUEUE_SIZE];
    if(!ptr) return;
    addq(ptr);
    for(;;){
        ptr = deleteq();
        if(ptr){
            printf("%d", ptr->data);
            if(ptr->leftChild)
                addq(ptr->leftChild);
            if(ptr->rightChild)
                addq(ptr->rightChild);
        } else break;
    }
}
```




reference
---

[[資訊之芽 算法班] 02. 基礎資料結構](https://www.youtube.com/watch?v=EH5XO2iYJvM&t=489s)
