Module 16: Cấu trúc dữ liệu

Cấu trúc dữ liệu trong C

Stack (Ngăn xếp) - LIFO

#define MAX 100
int stack[MAX], top = -1;

void push(int v) { if (top < MAX-1) stack[++top] = v; }
int pop() { return (top >= 0) ? stack[top--] : -1; }
int peek() { return (top >= 0) ? stack[top] : -1; }

Queue (Hàng đợi) - FIFO

int queue[MAX], front = 0, rear = 0;

void enqueue(int v) { if (rear < MAX) queue[rear++] = v; }
int dequeue() { return (front < rear) ? queue[front++] : -1; }

Linked List (DS Liên kết đơn)

typedef struct Node { int data; struct Node *next; } Node;

Node *insert(Node *head, int v) {
    Node *n = malloc(sizeof(Node));
    n->data = v; n->next = head;
    return n;
}

void print(Node *h) {
    while (h) { printf("%d ", h->data); h = h->next; }
}

Binary Search Tree

typedef struct Tree { int val; struct Tree *l, *r; } Tree;

Tree *insert(Tree *t, int v) {
    if (!t) { t = malloc(sizeof(Tree)); t->val = v; t->l=t->r=NULL; return t; }
    if (v < t->val) t->l = insert(t->l, v);
    else t->r = insert(t->r, v);
    return t;
}

Độ phức tạp

• Stack/Queue: O(1) push/pop
• Linked List: O(1) insert, O(n) search
• BST: O(log n) trung bình, O(n) tệ nhất