C语言程序设计进阶：链表的高级应用——可变数组

# 1. 链表和可变数组的初步介绍

## 1.1 链表的基本概念和C语言中的实现
链表是一种常用的数据结构，由多个节点组成，每个节点包含数据和指向下一个节点的指针。相比于数组，链表的长度可以动态地增长或缩减，有更好的灵活性。在C语言中，可以通过结构体和指针来实现链表的存储和操作。

链表的基本概念：
- 节点：链表中的一个元素，包含数据和指针。
- 头节点：链表的第一个节点。
- 尾节点：链表的最后一个节点，其指针指向NULL。
- 空链表：不包含任何节点的链表，头节点为NULL。

C语言中实现链表的基本步骤：
1. 定义节点结构体：包含数据和指向下一个节点的指针。
2. 创建头节点并初始化：将头节点的指针设置为NULL。
3. 添加节点到链表末尾：
- 创建新节点并初始化。
- 遍历链表找到尾节点。
- 将尾节点的指针指向新节点。
4. 遍历链表：通过指针依次访问每个节点并处理数据。
5. 释放链表内存：依次释放每个节点的内存。

示例代码（C语言）：

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

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

// 创建链表，返回头节点指针
struct Node* createLinkedList() {
    struct Node* head = NULL;
    return head;
}

// 在链表末尾添加节点
void appendNode(struct Node** head, int data) {
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    new_node->data = data;
    new_node->next = NULL;

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

// 遍历链表并输出数据
void printLinkedList(struct Node* head) {
    struct Node* current = head;

    if (current == NULL) {
        printf("Linked List is empty.\n");
    } else {
        printf("Linked List: ");
        while (current != NULL) {
            printf("%d ", current->data);
            current = current->next;
        }
        printf("\n");
    }
}

// 释放链表内存
void freeLinkedList(struct Node** head) {
    struct Node* current = *head;
    struct Node* next;

    while (current != NULL) {
        next = current->next;
        free(current);
        current = next;
    }

    *head = NULL;
}

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

    appendNode(&head, 1);
    appendNode(&head, 2);
    appendNode(&head, 3);

    printLinkedList(head);

    freeLinkedList(&head);

    return 0;
}

代码解析：
- `createLinkedList`函数用于创建并返回一个空链表，即头节点指针为NULL。
- `appendNode`函数接收头节点指针和要添加的数据作为参数，在链表末尾添加节点。
- `printLinkedList`函数接收头节点指针作为参数，遍历链表并输出数据。
- `freeLinkedList`函数用于释放链表的内存，包括所有节点。

代码运行结果：

Linked List: 1 2 3

通过以上示例代码，我们完成了第一章节的内容，介绍了链表的基本概念和在C语言中的实现。接下来，我们将继续探讨可变数组的概念和实现方式。

# 2. 用链表实现可变数组

链表是一种动态数据结构，可以轻松实现可变长度的数组。在这一章节中，我们将介绍如何利用链表结构实现一个可变数组，并给出基于链表的可变数组的实现示例。

### 2.1 如何利用链表结构实现一个可变数组

可变数组是指长度可以在运行时动态改变的数组。使用链表来实现可变数组的好处是，增删元素的操作时间复杂度为O(1)，不需要进行内存的拷贝操作。

链表由节点组成，每个节点包含一个数据元素和一个指向下一个节点的指针。为了实现可变数组，我们需要定义链表的头节点，并维护一个指向尾节点的指针。

具体实现可参考以下代码示例：

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next = new_node
            self.tail = new_node

    def get(self, index):
        if index < 0:
            return None
        current = self.head
        for _ in range(index):
            if not current:
                return None
            current = current.next
        if not current:
            return None
        return current.data

### 2.2 在C语言中编写和操作基于链表的可变数组

在C语言中，我们可以使用结构体来定义链表和节点。通过指针关系，我们可以实现链表中节点的增加和删除。

以下是基于链表实现的可变数组示例代码：

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

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

typedef struct LinkedList {
    Node* head;
    Node* tail;
} LinkedList;

LinkedList* createLinkedList() {
    LinkedList* list = (LinkedList*)malloc(sizeof(LinkedList));
    list->head = NULL;
    list->tail = NULL;
    return list;
}

void append(LinkedList* list, int data) {
    Node* new_node = (Node*)malloc(sizeof(Node));
    new_node->data = data;
    new_node->next = NULL;
    if (list->head == NULL) {
        list->head = new_node;
        list->tail = new_node;
    } else {
        list->tail->next = new_node;
        list->tail = new_node;
    }
}

int get(LinkedList* list, int index) {
    if (index < 0) {
        return -1;
    }
    Node* current = list->head;
    for (int i = 0; i < index; i++) {
        if (current == NULL) {
            return -1;
        }
        current = current->next;
    }
    if (current == NULL) {
        return -1;
    }
    return current->data;
}

通过上述示例代码，我们可以实现基于链表的可变数组，并进行增加和获取元素的操作。

这就是用链表实现可变数组的基本原理和方法。接下来，我们将在第三章节中讨论如何动态扩展和收缩可变数组的长度。

# 3. 动态扩展和收缩可变数组

在本章节中，我们将讨论如何实现动态扩展和收缩可变数组。可变数组是一种非常灵活的数据结构，但在实际使用中经常需要动态地调整数组的大小以满足需求。我们将深入探讨如何高效地进行动态扩展