C语言数据结构顺序表的进阶讲解

介绍

顺序表是一种数据结构，它是由一组数据元素组成的线性结构，每个元素都有一个唯一的序号来标识其位置。顺序表中的元素在内存中是连续存储的，可以通过下标直接访问任何一个元素。本文将介绍如何进阶使用顺序表来解决更加复杂的问题。

进阶使用顺序表

动态数组

顺序表的大小是在创建时确定的，在运行时不能改变大小，当插入或删除元素时，必须先移动其他元素，这可能导致性能问题。为了解决这个问题，我们可以使用动态数组。

动态数组的大小可以在运行时根据需求而改变，因此插入和删除元素时不需要移动其他元素。下面是一个动态数组的示例代码：

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

typedef struct {
    int *data;
    int size;
} dynamic_array;

void dynamic_array_init(dynamic_array *array, int size) {
    array->data = malloc(sizeof(int) * size);
    array->size = size;
}

void dynamic_array_resize(dynamic_array *array, int new_size) {
    array->data = realloc(array->data, sizeof(int) * new_size);
    array->size = new_size;
}

void dynamic_array_insert(dynamic_array *array, int index, int value) {
    if (index < 0 || index > array->size) {
        fprintf(stderr, "Invalid index\n");
        return;
    }
    if (array->size == 0) {
        dynamic_array_resize(array, 1);
    }
    if (array->size == index) {
        dynamic_array_resize(array, array->size * 2);
    }
    for (int i = array->size - 1; i > index; i--) {
        array->data[i] = array->data[i - 1];
    }
    array->data[index] = value;
    array->size++;
}

void dynamic_array_remove(dynamic_array *array, int index) {
    if (index < 0 || index >= array->size) {
        fprintf(stderr, "Invalid index\n");
        return;
    }
    for (int i = index; i < array->size - 1; i++) {
        array->data[i] = array->data[i + 1];
    }
    array->size--;
    if (array->size < array->size / 2) {
        dynamic_array_resize(array, array->size / 2);
    }
}

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

int main() {
    dynamic_array array;
    dynamic_array_init(&array, 2);
    dynamic_array_insert(&array, 0, 1);
    dynamic_array_insert(&array, 1, 2);
    dynamic_array_insert(&array, 2, 3);
    dynamic_array_print(&array);
    dynamic_array_remove(&array, 0);
    dynamic_array_print(&array);
    dynamic_array_remove(&array, 1);
    dynamic_array_print(&array);
    dynamic_array_remove(&array, 0);
    dynamic_array_print(&array);
    dynamic_array_remove(&array, 0);
    dynamic_array_print(&array);
}

在上面的代码中，我们定义了一个 dynamic_array 结构体，它包含一个指向存储数据的整型数组的指针 data，以及数组的大小 size。接下来，我们定义了一些操作函数，如 dynamic_array_init 初始化动态数组，dynamic_array_resize 调整数组大小，dynamic_array_insert 在数组中插入元素，dynamic_array_remove 删除数组中的元素，dynamic_array_print 打印数组中的元素。最后，在 main 函数中，我们演示了如何使用动态数组来操作数据。

多维数组

除了一维数组，C 语言还支持多维数组，多维数组可以简单地理解为一个数组中包含了多个数组。例如，我们可以定义一个表示二维矩阵的多维数组：

#include <stdio.h>

int main() {
    int matrix[3][3] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            printf("%d ", matrix[i][j]);
        }
        printf("\n");
    }
    return 0;
}

在上面的代码中，我们定义了一个 3x3 的二维数组 matrix，并用嵌套的循环遍历了整个数组并打印出了其中的元素。多维数组在科学计算和图像处理等领域应用广泛，因此必须掌握使用多维数组的方法。

示例说明

示例一：使用动态数组实现动态内存分配

在计算机图形学和游戏开发领域中，了解动态内存分配是非常重要的。动态内存分配是指在程序运行时根据需要动态地分配内存空间。在这种情况下，我们可以使用动态数组来分配内存。下面是一个使用动态数组实现动态内存分配的示例代码：

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

int main() {
    int n = 3;
    int *array = malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        array[i] = i * i;
    }
    for (int i = 0; i < n; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
    free(array);
    return 0;
}

在上面的代码中，我们使用 malloc 函数分配了一个长度为 n 的整型数组，并用了一个循环给数组中的元素赋值。最后，我们用另一个循环输出了数组中的元素，并通过 free 函数释放了动态分配的内存。

示例二：使用多维数组实现黑白棋游戏

黑白棋游戏是一种非常受欢迎的两人对弈游戏。在这个游戏中，棋盘是一个 8x8 的方格图，其中黑色棋子和白色棋子分别占据不同的方格。下面是一个使用多维数组实现黑白棋游戏的示例代码：

#include <stdio.h>
#include <string.h>

#define BLANK 0
#define BLACK 1
#define WHITE 2
#define SIZE 8

void print_board(int board[SIZE][SIZE]) {
    printf("  0 1 2 3 4 5 6 7\n");
    for (int i = 0; i < SIZE; i++) {
        printf("%d ", i);
        for (int j = 0; j < SIZE; j++) {
            if (board[i][j] == BLACK) {
                printf("B ");
            } else if (board[i][j] == WHITE) {
                printf("W ");
            } else {
                printf("- ");
            }
        }
        printf("\n");
    }
}

void init_board(int board[SIZE][SIZE]) {
    memset(board, BLANK, sizeof(int) * SIZE * SIZE);
    board[3][3] = WHITE;
    board[4][4] = WHITE;
    board[3][4] = BLACK;
    board[4][3] = BLACK;
}

int valid_move(int board[SIZE][SIZE], int x, int y, int color) {
    if (board[x][y] != BLANK) {
        return 0;
    }
    int dx, dy, tx, ty, flag = 0;
    for (dx = -1; dx <= 1; dx++) {
        for (dy = -1; dy <= 1; dy++) {
            if (dx == 0 && dy == 0) {
                continue;
            }
            tx = x + dx;
            ty = y + dy;
            while (tx >= 0 && tx < SIZE && ty >= 0 && ty < SIZE && board[tx][ty] != BLANK) {
                if (board[tx][ty] == color) {
                    flag = 1;
                    break;
                }
                tx += dx;
                ty += dy;
            }
            if (flag) {
                break;
            }
        }
        if (flag) {
            break;
        }
    }
    if (flag) {
        tx = x + dx;
        ty = y + dy;
        while (tx >= 0 && tx < SIZE && ty >= 0 && ty < SIZE && board[tx][ty] != BLANK && board[tx][ty] != color) {
            tx += dx;
            ty += dy;
        }
        if (tx >= 0 && tx < SIZE && ty >= 0 && ty < SIZE && board[tx][ty] == color) {
            return 1;
        }
    }
    return 0;
}

int count_chess(int board[SIZE][SIZE], int color) {
    int count = 0;
    for (int i = 0; i < SIZE; i++) {
        for (int j = 0; j < SIZE; j++) {
            if (board[i][j] == color) {
                count++;
            }
        }
    }
    return count;
}

void update_board(int board[SIZE][SIZE], int x, int y, int color) {
    board[x][y] = color;
    int dx, dy, tx, ty;
    for (dx = -1; dx <= 1; dx++) {
        for (dy = -1; dy <= 1; dy++) {
            if (dx == 0 && dy == 0) {
                continue;
            }
            tx = x + dx;
            ty = y + dy;
            int flag = 0;
            while (tx >= 0 && tx < SIZE && ty >= 0 && ty < SIZE && board[tx][ty] != BLANK) {
                if (board[tx][ty] == color) {
                    flag = 1;
                    break;
                }
                tx += dx;
                ty += dy;
            }
            if (flag == 0) {
                continue;
            }
            tx = x + dx;
            ty = y + dy;
            while (tx >= 0 && tx < SIZE && ty >= 0 && ty < SIZE && board[tx][ty] != BLANK && board[tx][ty] != color) {
                board[tx][ty] = color;
                tx += dx;
                ty += dy;
            }
        }
    }
}

int main() {
    int board[SIZE][SIZE];
    init_board(board);
    int turn = BLACK;
    while (1) {
        print_board(board);
        int count_black = count_chess(board, BLACK);
        int count_white = count_chess(board, WHITE);
        printf("Black: %d, White: %d\n", count_black, count_white);
        if (count_black + count_white == SIZE * SIZE || count_black == 0 || count_white == 0) {
            break;
        }
        int x, y;
        printf("%s, input coordinate (x, y): ", turn == BLACK ? "Black" : "White");
        scanf("%d%d", &x, &y);
        if (valid_move(board, x, y, turn)) {
            update_board(board, x, y, turn);
            turn = turn == BLACK ? WHITE : BLACK;
        } else {
            printf("Invalid move\n");
        }
    }
    int count_black = count_chess(board, BLACK);
    int count_white = count_chess(board, WHITE);
    if (count_black > count_white) {
        printf("Black wins\n");
    } else if (count_black < count_white) {
        printf("White wins\n");
    } else {
        printf("Tie\n");
    }
    return 0;
}

在上面的代码中，我们定义了一些常量，如 BLANK 表示空格，BLACK 表示黑子，WHITE 表示白子。接下来，我们定义了一些函数，如 print_board 打印棋盘，init_board 初始化棋盘，valid_move 校验是否合法，count_chess 统计棋子数量，update_board 更新棋盘。最后，在 main 函数中，我们实现了黑白棋游戏的基本流程。

结论

在本文中，我们介绍了如何使用顺序表来解决更加复杂的问题，包括动态数组和多维数组的使用。我们还通过两个示例代码说明了动态内存分配和黑白棋游戏的实现。希望本文能够帮助读者进一步掌握使用顺序表的技巧。