算法与数据结构学习笔记

链表是一种常见的基础数据结构，它由节点组成，每个节点包含数据域和指针域。以下是单链表的基本实现：

// 定义链表节点结构
struct Node {
    int data;
    struct Node* next;
};

// 创建新节点
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// 在链表头部插入节点
struct Node* insertAtHead(struct Node* head, int data) {
    struct Node* newNode = createNode(data);
    newNode->next = head;
    return newNode;
}

主要操作包括：

• 插入节点（头部、尾部、中间位置）
• 删除节点
• 查找节点
• 遍历链表

快速排序是一种高效的排序算法，基于分治策略。以下是其基本实现：

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

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = (low - 1);
    
    for (int j = low; j <= high - 1; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

算法特点：

• 平均时间复杂度：O(nlogn)
• 空间复杂度：O(logn)
• 不稳定排序

二叉树是一种重要的数据结构，常用于表示层次关系。以下是二叉树的基本实现及遍历方法：

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

// 前序遍历
void preOrder(struct TreeNode* root) {
    if (root != NULL) {
        printf("%d ", root->data);
        preOrder(root->left);
        preOrder(root->right);
    }
}

// 中序遍历
void inOrder(struct TreeNode* root) {
    if (root != NULL) {
        inOrder(root->left);
        printf("%d ", root->data);
        inOrder(root->right);
    }
}

// 后序遍历
void postOrder(struct TreeNode* root) {
    if (root != NULL) {
        postOrder(root->left);
        postOrder(root->right);
        printf("%d ", root->data);
    }
}

遍历方式包括：

• 前序遍历
• 中序遍历
• 后序遍历

堆排序是一种基于比较的排序算法，利用堆这种数据结构。以下是堆排序的基本实现：

void heapify(int arr[], int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < n && arr[left] > arr[largest])
        largest = left;

    if (right < n && arr[right] > arr[largest])
        largest = right;

    if (largest != i) {
        swap(&arr[i], &arr[largest]);
        heapify(arr, n, largest);
    }
}

void heapSort(int arr[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);
    for (int i = n - 1; i > 0; i--) {
        swap(&arr[0], &arr[i]);
        heapify(arr, i, 0);
    }
}

堆排序特点：

• 时间复杂度：O(nlogn)
• 空间复杂度：O(1)
• 不稳定排序

图是一种复杂的数据结构，常用于表示网络关系。以下是图的基本表示方法：

#define MAX 100
int graph[MAX][MAX]; // 邻接矩阵
int visited[MAX]; // 访问标记

// 深度优先遍历
void DFS(int v, int n) {
    visited[v] = 1;
    printf("%d ", v);
    for (int i = 0; i < n; i++) {
        if (graph[v][i] && !visited[i]) {
            DFS(i, n);
        }
    }
}

// 广度优先遍历
void BFS(int start, int n) {
    int queue[MAX], front = 0, rear = 0;
    visited[start] = 1;
    queue[rear++] = start;

    while (front < rear) {
        int v = queue[front++];
        printf("%d ", v);
        for (int i = 0; i < n; i++) {
            if (graph[v][i] && !visited[i]) {
                visited[i] = 1;
                queue[rear++] = i;
            }
        }
    }
}

遍历方式包括：

• 深度优先遍历（DFS）
• 广度优先遍历（BFS）

动态规划是一种解决复杂问题的方法，通过将问题分解为更小的子问题来解决。以下是斐波那契数列的动态规划实现：

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];
}

动态规划的关键在于：

• 重叠子问题
• 最优子结构

哈希表是一种高效的数据结构，支持快速查找。以下是哈希表的基本实现：

#define TABLE_SIZE 100
struct HashNode {
    int key;
    int value;
    struct HashNode* next;
};

struct HashNode* hashTable[TABLE_SIZE];

// 哈希函数
int hash(int key) {
    return key % TABLE_SIZE;
}

// 插入
void insert(int key, int value) {
    int index = hash(key);
    struct HashNode* newNode = (struct HashNode*)malloc(sizeof(struct HashNode));
    newNode->key = key;
    newNode->value = value;
    newNode->next = hashTable[index];
    hashTable[index] = newNode;
}

// 查找
int search(int key) {
    int index = hash(key);
    struct HashNode* node = hashTable[index];
    while (node != NULL) {
        if (node->key == key) {
            return node->value;
        }
        node = node->next;
    }
    return -1; // 未找到
}

哈希表的特点：

• 平均时间复杂度：O(1)
• 处理冲突的方法：链地址法、开放地址法

递归是一种解决问题的方法，通过函数调用自身来实现。回溯是一种特定的递归方法，常用于解决组合问题。以下是回溯算法的示例：

void backtrack(int start, int* nums, int n) {
    if (start == n) {
        // 处理当前组合
        return;
    }
    for (int i = start; i < n; i++) {
        swap(&nums[start], &nums[i]);
        backtrack(start + 1, nums, n);
        swap(&nums[start], &nums[i]); // 回溯
    }
}

回溯的应用场景包括：

• 排列组合
• 图的遍历
• 解决约束满足问题

贪心算法是一种通过选择当前最优解来解决问题的方法。以下是一个经典的贪心算法示例：找零问题：

void coinChange(int coins[], int m, int V) {
    int result[m];
    for (int i = 0; i < m; i++) {
        result[i] = 0;
    }
    for (int i = 0; i < m; i++) {
        while (V >= coins[i]) {
            V -= coins[i];
            result[i]++;
        }
    }
    // 输出结果
}

贪心算法的特点：

• 局部最优解不一定能得到全局最优解
• 适用于某些特定问题，如活动选择、最小生成树等

查找算法用于在数据结构中查找特定元素。以下是几种常见查找算法的比较：

// 线性查找
int linearSearch(int arr[], int n, int key) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == key) {
            return i;
        }
    }
    return -1;
}

// 二分查找
int binarySearch(int arr[], int left, int right, int key) {
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == key) {
            return mid;
        }
        if (arr[mid] < key) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

查找算法特点：

• 线性查找：时间复杂度O(n)，适用于无序数组
• 二分查找：时间复杂度O(logn)，适用于有序数组

栈是一种后进先出（LIFO）的数据结构。以下是栈的基本实现：

#define MAX 100
struct Stack {
    int top;
    int items[MAX];
};

// 初始化栈
void initStack(struct Stack* s) {
    s->top = -1;
}

// 判断栈是否为空
int isEmpty(struct Stack* s) {
    return s->top == -1;
}

// 入栈
void push(struct Stack* s, int item) {
    if (s->top < MAX - 1) {
        s->items[++(s->top)] = item;
    }
}

// 出栈
int pop(struct Stack* s) {
    if (!isEmpty(s)) {
        return s->items[(s->top)--];
    }
    return -1; // 栈空
}

栈的主要操作包括：

• 入栈（push）
• 出栈（pop）
• 查看栈顶元素

队列是一种先进先出（FIFO）的数据结构。以下是队列的基本实现：

#define MAX 100
struct Queue {
    int front, rear;
    int items[MAX];
};

// 初始化队列
void initQueue(struct Queue* q) {
    q->front = q->rear = -1;
}

// 判断队列是否为空
int isEmpty(struct Queue* q) {
    return q->front == -1;
}

// 入队
void enqueue(struct Queue* q, int item) {
    if (q->rear < MAX - 1) {
        if (isEmpty(q)) {
            q->front = 0;
        }
        q->items[++(q->rear)] = item;
    }
}

// 出队
int dequeue(struct Queue* q) {
    if (!isEmpty(q)) {
        int item = q->items[q->front];
        if (q->front >= q->rear) {
            q->front = q->rear = -1; // 队列空
        } else {
            q->front++;
        }
        return item;
    }
    return -1; // 队列空
}

队列的主要操作包括：

• 入队（enqueue）
• 出队（dequeue）
• 查看队头元素

Trie树是一种用于高效存储和查找字符串的数据结构。以下是Trie树的基本实现：

#define ALPHABET_SIZE 26
struct TrieNode {
    struct TrieNode* children[ALPHABET_SIZE];
    int isEndOfWord;
};

// 创建新节点
struct TrieNode* createNode() {
    struct TrieNode* node = (struct TrieNode*)malloc(sizeof(struct TrieNode));
    node->isEndOfWord = 0;
    for (int i = 0; i < ALPHABET_SIZE; i++) {
        node->children[i] = NULL;
    }
    return node;
}

// 插入单词
void insert(struct TrieNode* root, const char* word) {
    struct TrieNode* pCrawl = root;
    for (int level = 0; level < strlen(word); level++) {
        int index = word[level] - 'a';
        if (!pCrawl->children[index]) {
            pCrawl->children[index] = createNode();
        }
        pCrawl = pCrawl->children[index];
    }
    pCrawl->isEndOfWord = 1;
}

// 查找单词
int search(struct TrieNode* root, const char* word) {
    struct TrieNode* pCrawl = root;
    for (int level = 0; level < strlen(word); level++) {
        int index = word[level] - 'a';
        if (!pCrawl->children[index]) {
            return 0; // 未找到
        }
        pCrawl = pCrawl->children[index];
    }
    return (pCrawl != NULL && pCrawl->isEndOfWord);
}

Trie树的特点：

• 高效的前缀查找
• 适用于自动补全和拼写检查

并查集是一种用于处理不相交集合的数据结构，常用于网络连接问题。以下是并查集的基本实现：

#define MAX 100
int parent[MAX];

// 初始化并查集
void initUnionFind(int n) {
    for (int i = 0; i < n; i++) {
        parent[i] = i;
    }
}

// 查找根节点
int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]); // 路径压缩
    }
    return parent[x];
}

// 合并两个集合
void unionSets(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    if (rootX != rootY) {
        parent[rootY] = rootX; // 合并
    }
}

并查集的特点：

• 支持快速合并和查找操作
• 常用于解决连通性问题

位运算是对整数在二进制位上进行操作的技术，常用于高效算法。以下是一些常见的位运算操作：

// 判断奇偶
int isOdd(int n) {
    return n & 1; // 1为奇数，0为偶数
}

// 交换两个数
void swap(int* a, int* b) {
    *a = *a ^ *b;
    *b = *a ^ *b;
    *a = *a ^ *b;
}

// 计算n的二进制中1的个数
int countOnes(int n) {
    int count = 0;
    while (n) {
        count += n & 1;
        n >>= 1;
    }
    return count;
}

位运算的应用包括：

• 快速计算
• 图像处理
• 加密算法