# Data Structure 資料結構
Stack
---
- 性質
- 堆疊(疊盤子)
- Last in First out (LIFO)
- 最先丟進去的最後拿出來
- 最後放進去的最先拿出來
- 基本操作
- 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)
### 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
要 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
```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;
}
```
結合資料(將兩個 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)
Sign in with Wallet
Connect another wallet