C语言数据结构简介：数组与链表

# 1. C语言数据结构概述

### 1.1 数据结构的定义与作用

数据结构是指数据元素之间的关系和数据的组织方式，它是计算机存储、组织和操作数据的基础。数据结构的设计和选择直接影响算法的效率和程序的性能。常见的数据结构有数组、链表、栈、队列、树等。

### 1.2 C语言中的数据结构相关概念

在C语言中，数据结构常常通过结构体来实现。结构体是由不同类型的数据组合而成的自定义数据类型。通过结构体，可以将不同类型的数据作为一个整体进行操作和管理。

### 1.3 数据结构在C语言中的应用场景

数据结构在C语言中有广泛的应用场景，例如：

- 数组：用于存储一组相同类型的数据，常用于存储线性表、矩阵等；
- 链表：用于动态存储数据，通过指针的方式组织数据元素；
- 栈：用于实现递归、表达式求值等；
- 队列：用于实现任务调度、消息传递等；
- 树：用于实现数据的层次结构、搜索算法等。

C语言提供了丰富的数据结构和相关操作，可以满足不同场景下的需求。在接下来的章节中，我们将重点介绍数组和链表这两种常用的数据结构，并探讨它们在C语言中的实现和应用。

# 2. C语言数组基础

### 2.1 数组的定义与特性

数组是一种线性数据结构，由相同类型的元素组成，这些元素在内存中连续存储。数组可以通过下标来访问和修改其中的元素，下标从0开始计数。

#### 2.1.1 数组的定义

在C语言中，可以使用以下语法来定义一个数组：

<类型> <数组名称>[<数组大小>];

例如，下面的代码定义了一个包含5个整数元素的数组：

int arr[5];

#### 2.1.2 数组的特性

- 数组的元素类型必须是相同的。
- 数组的大小在定义时确定，并在整个生命周期内保持不变。
- 数组的下标从0开始，最大下标为数组大小减1。
- 数组在内存中是连续存储的。

### 2.2 C语言中数组的基本操作

#### 2.2.1 访问数组元素

可以通过数组的下标来访问和修改数组中的元素。例如，使用以下语法可以访问数组中的第i个元素：

<数组名称>[i]

下面的代码示例演示了如何访问和修改数组中的元素：

#include <stdio.h>

int main() {
    int arr[5] = {1, 2, 3, 4, 5};
    // 访问数组元素
    printf("arr[0]: %d\n", arr[0]); // 输出 1
    printf("arr[2]: %d\n", arr[2]); // 输出 3
    // 修改数组元素
    arr[1] = 10;
    printf("arr[1]: %d\n", arr[1]); // 输出 10
    return 0;
}

#### 2.2.2 遍历数组

可以使用循环结构来遍历数组，依次访问数组中的每一个元素。例如，使用for循环可以遍历数组，并输出每一个元素：

#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]);
    }
    return 0;
}

#### 2.2.3 数组作为函数参数

数组可以作为函数的参数传递。在函数定义时，可以使用以下语法来接收一个数组作为参数：

void <函数名>(<类型> <数组名称>[]){}

下面的代码示例演示了如何将数组作为参数传递给函数，并在函数中遍历和修改数组：

#include <stdio.h>

void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        printf("arr[%d]: %d\n", i, arr[i]);
    }
}

int main() {
    int arr[5] = {1, 2, 3, 4, 5};
    printArray(arr, 5);
    return 0;
}

### 2.3 数组的优缺点分析

#### 2.3.1 优点

- 数组在内存中是连续存储的，访问元素效率高。
- 数组的下标直接映射到元素的内存地址，可以快速访问和修改指定位置的元素。

#### 2.3.2 缺点

- 数组的大小在定义时确定，并且不能动态改变，导致内存利用率较低。
- 插入和删除元素的操作比较麻烦，可能需要移动其他元素。

综上所述，数组在C语言中是一种基本的数据结构，具有简单、高效的特点。在适合固定大小且频繁访问元素的场景中，数组是一种理想的选择。但在需要频繁插入和删除元素的场景中，链表等其他数据结构可能更适合。

# 3. C语言中的链表概述

#### 3.1 链表的定义与特性

链表（Linked List）是一种常用的数据结构，由一系列节点（Node）组成，每个节点包含数据域和指针域。数据域用于存储数据，指针域用于指向下一个节点。链表中的节点可以是任意类型的对象，可以根据实际需要自定义节点的结构。

链表的特性包括：
- 链表是动态的数据结构，内存空间可以根据需要进行动态分配和释放。
- 每个节点都有指针域，使得节点之间可以通过指针进行连接，形成一个链式结构。
- 链表的长度不固定，可以根据实际情况进行动态调整。

#### 3.2 链表的分类与应用场景

根据节点之间的连接方式的不同，链表可以分为以下几种常见的类型：
- 单链表（Single Linked List）：每个节点只有一个指针域，指向下一个节点。
- 双向链表（Doubly Linked List）：每个节点有两个指针域，分别指向前一个节点和后一个节点。
- 循环链表（Circular Linked List）：链表中最后一个节点的指针域指向头节点，形成一个闭环。

链表在实际应用中有广泛的应用场景，例如：
- 存储和处理大量的数据集合，链表可以根据需求进行动态调整，适用于插入和删除频繁的场景。
- 实现队列（Queue）和栈（Stack）等抽象数据类型时，链表可以简洁高效地实现。
- 在图算法和树算法中，链表常被用于存储和遍历节点。

#### 3.3 链表与数组的对比

链表和数组是常见的数据结构，具有不同的特点和适用场景。

链表相对于数组的优点包括：
- 内存占用灵活：链表采用动态内存分配，可以根据需要按需分配内存空间，不浪费内存。
- 插入和删除操作高效：链表在插入和删除节点时，只需要修改指针域，不需要移动其他元素，时间复杂度为O(1)。
- 大型数据集的处理：链表适用于存储和处理大量的数据集合，不受固定长度限制。

数组相对于链表的优点包括：
- 随机访问性能好：通过索引可以快速访问数组中的任意元素，时间复杂度为O(1)。
- 缓存友好：数组的元素在内存中是连续存储的，可以利用局部性原理进行高效的缓存预取。
- 一维表格处理：对于一维表格或矩阵等结构化数据，数组通常更加直观和易于理解。

综上所述，链表和数组各自有自己的特点和适用场景，在实际应用中需要根据具体需求进行选择。

希望这部分内容能够满足您的需求，如果需要其他章节的内容，请告诉我。

# 4. C语言中的链表实现

链表是一种常见的数据结构，用于存储和组织数据。与数组相比，链表具有动态性和灵活性，可以动态添加、删除和修改节点。

#### 4.1 单链表的定义与实现

单链表是一种线性表的链式存储结构，其每个节点包含一个数据元素和一个指向下一个节点的指针。

在C语言中，可以通过结构体来定义单链表节点的数据结构。下面是一个例子：

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

该结构体包含一个整型的数据域和一个指向下一个节点的指针域。

单链表的实现主要包括以下几个步骤：

1. 定义一个头节点指针，并将其初始化为NULL，表示链表为空。
2. 创建新节点，为其分配内存空间，并将数据存储在该节点中。
3. 将新节点插入到链表的合适位置，即通过修改指针的指向来连接新节点与链表。
4. 删除节点时，通过修改指针的指向来断开节点与链表的连接，并释放节点的内存空间。
5. 遍历链表，可以通过循环遍历每个节点，并访问、操作节点的数据。

下面是单链表的实现示例代码：

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

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

// 在链表末尾插入新节点
void insert(struct Node **head, int data) {
    struct Node *newNode = (struct Node *)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;

    if (*head == NULL) {
        *head = newNode;
    } else {
        struct Node *temp = *head;
        while (temp->next != NULL) {
            temp = temp->next;
        }
        temp->next = newNode;
    }
}

// 删除指定位置的节点
void deleteNode(struct Node **head, int position) {
    if (*head == NULL) {
        return;
    }

    struct Node *temp = *head;
    if (position == 0) {
        *head = temp->next;
        free(temp);
        return;
    }

    for (int i = 0; temp != NULL && i < position-1; i++) {
        temp = temp->next;
    }
    if (temp == NULL || temp->next == NULL) {