16 数据结构与算法之数组与链表

在这一篇中，我们将深入探讨C语言中的数组和链表这两种基本数据结构。这些数据结构是理解更复杂算法的基础，同时也是编程中常用的工具。我们将通过案例和代码示例来帮助您更好地理解它们的使用场景和优缺点。

5.1 数组

1. 数组的基本概念

数组是一个固定大小的、连续存储的元素集合，所有元素具有相同的类型。在C语言中，可以使用以下方式定义一个数组：

int arr[5]; // 定义一个包含5个整数的数组

1.1 数组的特点

• 固定大小：数组的大小一旦定义，就不可改变。
• 快速访问：可以通过索引快速访问元素，时间复杂度为$O(1)$。
• 内存连续：存储的元素在内存中是连续的，这有助于提高缓存命中率。

1.2 数组的案例

下面是一个简单的数组使用示例，演示如何遍历和修改数组元素：

#include <stdio.h>

int main() {
    int arr[5] = {1, 2, 3, 4, 5};
    
    // 遍历并打印数组元素
    for (int i = 0; i < 5; i++) {
        printf("arr[%d] = %d\n", i, arr[i]);
    }

    // 修改数组中的一个元素
    arr[2] = 10;
    printf("After modification, arr[2] = %d\n", arr[2]);
    
    return 0;
}

2. 数组的优缺点

• 优点：

  • 访问速度快；
  • 易于实现和理解。

• 缺点：

  • 不支持动态调整大小；
  • 插入和删除操作较慢，时间复杂度为$O(n)$。

5.2 链表

3. 链表的基本概念

链表是一种动态数据结构，由一系列节点组成。每个节点包含数据部分和指向下一个节点的指针，这使得试图在概念上理解链表的结构。

3.1 链表的定义

在C语言中，您可以通过结构体定义一个链表节点：

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

3.2 单链表的案例

下面的代码展示了如何创建、插入和遍历一个简单的单链表：

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

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

// 插入节点到链表头
void insertAtHead(struct Node** head_ref, int new_data) {
    struct Node* newNode = createNode(new_data);
    newNode->next = *head_ref;
    *head_ref = newNode;
}

// 打印链表
void printList(struct Node* node) {
    while (node != NULL) {
        printf("%d -> ", node->data);
        node = node->next;
    }
    printf("NULL\n");
}

int main() {
    struct Node* head = NULL;

    // 向链表插入数据
    insertAtHead(&head, 1);
    insertAtHead(&head, 2);
    insertAtHead(&head, 3);
    
    // 打印链表
    printList(head);

    return 0;
}

4. 链表的优缺点

• 优点：

  • 动态大小：链表可以在运行时动态分配和释放内存；
  • 插入和删除操作的时间复杂度为$O(1)$（在已知位置的情况下）。

• 缺点：

  • 随机访问速度慢：访问一个元素的时间复杂度为$O(n)$；
  • 需要额外的内存来存储指针。

总结

在这部分中，我们分别介绍了数组和链表两种基本数据结构。数组适合需要快速随机访问的场景，而链表则在频繁插入和删除的情况下具有优势。掌握这两种数据结构是学习更复杂数据结构和算法的基础，对后续的学习，特别是会涉及到的栈和队列等结构理解会有很大的帮助。接下来，我们将深入探讨栈与队列的相关知识。