四大資料結構彙整

陣列 Array

靜態分配 with fix size

// store in stack
int list[3];

list[0] = 1;
list[1] = 2;
list[2] = 3;

動態分配 with dinamically size

// store in heap
int *list = malloc(3 * sizeof(int));

list[0] = 1;
list[1] = 2;
list[2] = 3;



// **CAN reallocate array by`malloc`**
int *tmp = malloc(4* sizeof(int));
if (tmp == NULL)
{
    free(list);
    return 1;
}

for (int i = 0; i < 3; i++)
{
    tep[i] = list[i];
}



// **OR CAN reallocate array by`reolloc`**
int *tmp = realloc(4* sizeof(int));
if (tmp == NULL)
{
    free(list);
    return 1;
}


// then put the new data inside and so on and so forth
temp[3] = 4;

free(list);
list = tmp;

for (int i = 0; i < 4; i++)
{
    print("%d\n",list[i]);
}
free(list);

鏈結串列 Link list

結構 structure

(by cs50x 上課PPT)

資料處理速度

1. 線性搜尋：O(n)、Ω(1)
2. 順序性插入：O(n)、Ω(1)
3. 非順序性插入：O(1)、Ω(1)

Link list 建構

• To create a new data struct called node

#include <stdio.h>
#include <stdlib.h>

// Represents a node
typedef struct node
{
    int number;
    struct node *next;
}
node;

• Create the first node

int main(void)
{
    // List (node 的 point variable) 指向一個空的 node
    node *list = NULL;

    // n (node 的 point variable) 指向一個node大小的malloc
    node *n = malloc(sizeof(node));
    if (n == NULL)
    {
        return 1;
    }
    n->number = 1;
    n->next = NULL;

    // list指向n所指向的malloc(動態內存)
    list = n;
}

• Create the second node

// 暫時變數n改指向新的(第二個)malloc
n = malloc(sizeof(node));
if (n == NULL)
{
    // 記得釋放list = n內的資料再離開
    free(list);
    return 1;
}

// 初始化第二個malloc內資料(設定n = tail)
n->number = 2;
n->next = NULL;

// list現在指向第一個的malloc
// list的next指向新的n所在位置
list->next = n;

• Create the third node

// // 暫時變數n改指向新的(第三個)malloc
n = malloc(sizeof(node));
if (n == NULL)
{
    // 先釋放第二次n指向的malloc
    free(list->next);
    // 再釋放第一次n指向的malloc
    free(list);
    return 1;
}

// 初始化第三個malloc內資料(設定n = tail)
n->number = 3;
n->next = NULL;

// list是第一次n指向的malloc
// list->next是第二次n指向的malloc
// 設定list->next->next指向第三個malloc
list->next->next = n;

• Print numbers

for (node *tmp = list; tmp != NULL; tmp = tmp->next)
{
    printf("%i\n", tmp->number);
}

• Free list

while (list != NULL)
{
    node *tmp = list->next;
    free(list);
    list = tmp;
}
return 0;

二元搜尋樹 Binary search tree (BST)

結構 structure

(by wikipedia.org)

1. 一棵樹可以拆解成很多棵小樹
2. 中間稱root / parent
3. 左右稱right child / left child
4. left child < root < right child

資料處理速度

1. 搜尋：O(logn)、Ω(1)
2. 順序性插入：O(logn)、Ω(1)

Binary search tree 建構

• define a node with two pointers

typedef struct node
{
    int number;
    struct node *left;
    struct node *right;
}
node;

• Create the first node (root of whole tree)

int main(void)
{
    // Tree of size 0
    node *tree = NULL;

    // Add number to list
    node *n = malloc(sizeof(node));
    if (n == NULL)
    {
        return 1;
    }
    n->number = 2;
    n->left = NULL;
    n->right = NULL;
    tree = n;

• Create the left child of the root node

// Add number to list
n = malloc(sizeof(node));
if (n == NULL)
{
    free_tree(tree);
    return 1;
}
n->number = 1;
n->left = NULL;
n->right = NULL;
tree->left = n;

• Create the right child of the root node and set print / free function

// Add number to list
n = malloc(sizeof(node));
if (n == NULL)
{
    free_tree(tree);
    return 1;
}
n->number = 3;
n->left = NULL;
n->right = NULL;
tree->right = n;

// Print tree
print_tree(tree);

// Free tree
free_tree(tree);
return 0;

• Print the tree

void print_tree(node *root)
{
    if (root == NULL)
    {
        return;
    }
    print_tree(root->left);
    printf("%i\n", root->number);
    print_tree(root->right);
}

• Free the tree

void free_tree(node *root)
{
    if (root == NULL)
    {
        return;
    }
    free_tree(root->left);
    free_tree(root->right);
    free(root);
}

• Search for an item

bool search(node *tree, int number)
{
    if (tree == NULL)
    {
        return false;
    }
    else if (number < tree->number)
    {
        return search(tree->left, number);
    }
    else if (number > tree->number)
    {
        return search(tree->right, number);
    }
    else if (number == tree->number)
    {
        return true;
    }
}

Hash Tables 雜湊表

結構 structure

(by cs50x 上課PPT)

1. Model => Array
2. Element => Link list
3. Hash function => 以字元的ASCII大小作排序

Hash Tables 建構

// 存放指針的Array

node *hash_table[NUMBER_OF_BUCKET];
// eg. int number[3];

typedef struct node
{
    char word[LONGEST_WORD + 1];
    struct node *next;
}
node;

Tries 查詢樹、字典樹、多叉樹

結構 structure

(by cs50x 上課PPT)

1. Model => Array
2. Element => Tree

Tries 建構

typedef struct node
{
    bool is_word;
    struct node *children[SIZE_OF_ALPHABET];
}
node;

More Data Structure

Queues 佇列、隊列 (enqueue / dequeue)

first in, first out

Stacks 堆疊、棧 (push / pop)

last in, first out