数据结构与算法优化

## 1. 数据结构概述

### 1.1 数据结构的定义
- 数据结构是存储、组织和管理数据的方式。
- 常见的数据结构包括：`数组`、`链表`、`堆栈`、`队列`、`树`、`图`等。

### 1.2 数据结构的选择
- 根据所需操作的时间复杂度和空间复杂度选择合适的数据结构。

## 2. 线性数据结构

### 2.1 数组
- 固定大小，支持随机访问。
- 优点：访问速度快。
- 缺点：插入和删除操作较慢。

#### 示例代码
```c
#include <stdio.h>

int main() {
    int arr[5] = {1, 2, 3, 4, 5};
    for (int i = 0; i < 5; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

2.2 链表

• 动态大小，支持频繁插入和删除。
• 类别：单链表、双链表、循环链表。

示例代码

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

void printList(struct Node* n) {
    while (n != NULL) {
        printf("%d ", n->data);
        n = n->next;
    }
}

2.3 堆栈

• 后进先出（LIFO）数据结构。
• 支持入栈和出栈操作。

示例代码

#include <stdio.h>
#define MAX 100

int stack[MAX];
int top = -1;

void push(int data) {
    if (top < MAX - 1) {
        stack[++top] = data;
    }
}

int pop() {
    if (top >= 0) {
        return stack[top--];
    }
    return -1; // stack underflow
}

2.4 队列

• 先进先出（FIFO）数据结构。
• 支持入队和出队操作。

示例代码

#include <stdio.h>
#define MAX 100

int queue[MAX];
int front = -1, rear = -1;

void enqueue(int data) {
    if (rear < MAX - 1) {
        if (front == -1) front = 0;
        queue[++rear] = data;
    }
}

int dequeue() {
    if (front <= rear) {
        return queue[front++];
    }
    return -1; // queue underflow
}

3. 非线性数据结构

3.1 树

• 树是一种层级数据结构。
• 二叉树、AVL树、红黑树等。

示例代码

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

void inorderTraversal(struct TreeNode* root) {
    if (root) {
        inorderTraversal(root->left);
        printf("%d ", root->val);
        inorderTraversal(root->right);
    }
}

3.2 图

• 由节点和边组成。
• 表示方式：邻接矩阵和邻接表。

示例代码（邻接表）

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

struct Node {
    int vertex;
    struct Node* next;
};

struct Graph {
    int numVertices;
    struct Node** adjLists;
};

struct Node* createNode(int v) {
    struct Node* newNode = malloc(sizeof(struct Node));
    newNode->vertex = v;
    newNode->next = NULL;
    return newNode;
}

4. 算法优化

4.1 算法复杂度

• 时间复杂度与空间复杂度的分析。
• Big O 符号表示法。

4.2 常见算法优化技巧

• 减少不必要的计算：使用动态规划技术。
• 空间换时间：例如，使用哈希表进行查找。

4.2.1 动态规划示例

int fib(int n) {
    int dp[n + 1]; // 创建动态数组
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

4.3 优化排序算法

• 选择合适的排序算法（如快速排序、归并排序）来降低时间复杂度。

示例代码

void quicksort(int arr[], int low, int high) {
    if (low < high) {
        int pivot = partition(arr, low, high);
        quicksort(arr, low, pivot - 1);
        quicksort(arr, pivot + 1, high);
    }
}

5. 结语

• 理解不同数据结构与算法的优缺点是选择合适解决方案的关键。
• 通过练习与项目实践进一步巩固以上内容。