正文

C语言打造高效容器：轻松实现动态数组、链表与栈

/0 浏览量
0330

在C语言编程中，容器是处理数据的一种重要方式。高效的容器可以极大地提升程序的执行效率和性能。本文将介绍如何使用C语言实现三种常见的容器：动态数组、链表与栈。通过学习这些内容，你将能够更好地理解数据结构在编程中的应用。

动态数组

动态数组是一种可以动态调整大小的数组。在C语言中，我们可以使用指针和malloc函数来实现动态数组。

动态数组的基本操作

  1. 初始化：使用malloc函数分配内存空间，并初始化指针。
  2. 插入：在数组末尾添加元素，如果数组已满，则重新分配更大的内存空间。
  3. 删除：删除数组中的元素，如果删除后数组空间过大，则释放多余内存。
  4. 遍历：使用循环遍历数组中的元素。

代码示例

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

#define INITIAL_SIZE 10

typedef struct {
    int *array;
    int size;
    int capacity;
} DynamicArray;

void initArray(DynamicArray *arr) {
    arr->array = (int *)malloc(INITIAL_SIZE * sizeof(int));
    arr->size = 0;
    arr->capacity = INITIAL_SIZE;
}

void insertArray(DynamicArray *arr, int value) {
    if (arr->size == arr->capacity) {
        arr->capacity *= 2;
        arr->array = (int *)realloc(arr->array, arr->capacity * sizeof(int));
    }
    arr->array[arr->size++] = value;
}

void deleteArray(DynamicArray *arr, int index) {
    if (index < 0 || index >= arr->size) {
        return;
    }
    for (int i = index; i < arr->size - 1; i++) {
        arr->array[i] = arr->array[i + 1];
    }
    arr->size--;
    if (arr->size <= arr->capacity / 4) {
        arr->capacity /= 2;
        arr->array = (int *)realloc(arr->array, arr->capacity * sizeof(int));
    }
}

void traverseArray(DynamicArray *arr) {
    for (int i = 0; i < arr->size; i++) {
        printf("%d ", arr->array[i]);
    }
    printf("\n");
}

void freeArray(DynamicArray *arr) {
    free(arr->array);
    arr->array = NULL;
    arr->size = 0;
    arr->capacity = 0;
}

链表

链表是一种由节点组成的线性结构，每个节点包含数据和指向下一个节点的指针。

链表的基本操作

  1. 初始化：创建一个头节点，并初始化指针。
  2. 插入：在链表的指定位置插入节点。
  3. 删除：删除链表中的节点。
  4. 遍历：使用循环遍历链表中的节点。

代码示例

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

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

Node *createNode(int value) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = NULL;
    return newNode;
}

void insertNode(Node **head, int value, int index) {
    Node *newNode = createNode(value);
    if (index == 0) {
        newNode->next = *head;
        *head = newNode;
    } else {
        Node *current = *head;
        for (int i = 0; i < index - 1; i++) {
            if (current == NULL) {
                return;
            }
            current = current->next;
        }
        newNode->next = current->next;
        current->next = newNode;
    }
}

void deleteNode(Node **head, int index) {
    if (index < 0 || *head == NULL) {
        return;
    }
    Node *current = *head;
    if (index == 0) {
        *head = current->next;
        free(current);
    } else {
        for (int i = 0; i < index - 1; i++) {
            if (current == NULL) {
                return;
            }
            current = current->next;
        }
        Node *temp = current->next;
        current->next = temp->next;
        free(temp);
    }
}

void traverseList(Node *head) {
    Node *current = head;
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");
}

void freeList(Node *head) {
    Node *current = head;
    while (current != NULL) {
        Node *temp = current;
        current = current->next;
        free(temp);
    }
}

栈

栈是一种后进先出（LIFO）的数据结构。在C语言中，我们可以使用数组或链表来实现栈。

栈的基本操作

  1. 初始化：创建一个栈，并初始化指针。
  2. 压栈：将元素添加到栈顶。
  3. 出栈：从栈顶删除元素。
  4. 遍历：使用循环遍历栈中的元素。

代码示例

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

#define STACK_SIZE 10

typedef struct {
    int data[STACK_SIZE];
    int top;
} Stack;

void initStack(Stack *stack) {
    stack->top = -1;
}

int push(Stack *stack, int value) {
    if (stack->top == STACK_SIZE - 1) {
        return -1;
    }
    stack->data[++stack->top] = value;
    return 0;
}

int pop(Stack *stack) {
    if (stack->top == -1) {
        return -1;
    }
    return stack->data[stack->top--];
}

void traverseStack(Stack *stack) {
    for (int i = stack->top; i >= 0; i--) {
        printf("%d ", stack->data[i]);
    }
    printf("\n");
}

通过学习本文，你将能够使用C语言实现动态数组、链表和栈。这些容器在编程中有着广泛的应用，掌握它们将有助于你更好地解决实际问题。

-- 展开阅读全文 --