数据结构基础：数组、链表、栈与队列详解

数据结构基础：数组、链表、栈与队列详解 | 极客日志

// 根据数据元素的关键字直接计算出该元素的关键码，由关键码决定存储地址，又称为 Hash 存储。
// 散列表的实现原理是映射，在映射的过程中，事先设定的函数称为散列函数或者哈希函数。

// 通过 typedef 给类型取别名
typedef int element_t;

// 定义结构体，表示动态数组
typedef struct {
    element_t* data;        // 指向动态数组的指针
    size_t capacity;        // 数组容量 (最大允许的元素个数)
    size_t length;          // 数组长度 (数组中已添加的元素个数)
} DynamicArray;

/**
 * @brief 初始化动态数组，分配内存空间
 * @param DynamicArray *array 要进行初始化的动态数组
 * @param size_t initCapacity 初始容量
 */
void initDynamicArray(DynamicArray *array, size_t initCapacity) {
    // 动态分配内存
    array->data = (element_t*)malloc(sizeof(element_t) * initCapacity);
    array->capacity = initCapacity;
    array->length = 0;
}

/**
 * @brief 调整动态数组内存大小
 * @param DynamicArray *array 动态数组
 * @param size_t newCapacity 新的容量 (元素个数)
 */
void resizeDynamicArray(DynamicArray *array, size_t newCapacity) {
    // 扩容
    array->data = (element_t*)realloc(array->data, sizeof(element_t) * newCapacity);
    // 改容量
    array->capacity = newCapacity;
}

/**
 * @brief 在指定位置插入新元素
 * @param DynamicArray *array 动态数组
 * @param size_t index 位置（下标）
 * @param element_t element 新元素
 */
void insertAt(DynamicArray *array, size_t index, element_t element) {
    // 判断位置是否合理
    if (index > array->length) {
        printf("%zu 位置不合理!!!\n", index);
        return;
    }
    // 判断容量是否足够
    if (array->length == array->capacity) {
        // 扩容
        resizeDynamicArray(array, array->capacity * 2);
    }
    // 插入元素
    // 插入位置后面的元素整体向后移动
    // 倒序：从数组中最后一个元素位置 +1 开始，循环到 index 为止，每次将当前位置前面的元素往当前位置放
    for (size_t i = array->length; i > index; i--) {
        // 移动元素
        array->data[i] = array->data[i - 1];
    }
    // 将插入的元素放到 index 位置
    array->data[index] = element;
    // 数组长度自增
    array->length++;
}

/**
 * @brief 在末尾插入新元素
 * @param DynamicArray *array 动态数组
 * @param element_t element 新元素
 */
void insertEnd(DynamicArray *array, element_t element) {
    insertAt(array, array->length, element);
}

/**
 * @brief 获取动态数组长度（元素个数）
 * @param const DynamicArray *array
 * @return size_t 数组长度
 */
size_t getLength(const DynamicArray *array) {
    return array->length;
}

/**
 * @brief 删除指定位置的元素并将被删除的元素保存到第三个参数
 * @param DynamicArray *array 动态数组
 * @param size_t index 删除的位置（下标）
 * @param element_t *deleted_element 用于保存被删除的元素
 * @return bool 是否删除成功 true(1) 成功 false(0) 失败
 */
bool deleteAt(DynamicArray *array, size_t index, element_t *delete_element) {
    // 判断位置是否合理
    if (index > array->length - 1) {
        return false;
    }
    // 记录被删除元素
    *delete_element = array->data[index];
    // 删除
    // 从 index 位置开始，循环到小于长度 -1 的位置，每次将当前位置后面的元素往当前位置放
    for (; index < array->length - 1; index++) {
        array->data[index] = array->data[index + 1];
    }
    // 长度自减
    array->length--;
    return true;
}

/**
 * @brief 删除末尾的元素并将被删除的元素保存到第二个参数
 * @param DynamicArray *array 动态数组
 * @param element_t *deleted_element 用于保存被删除的元素
 * @return bool 是否删除成功 true(1) 成功 false(0) 失败
 */
bool deleteEnd(DynamicArray *array, element_t *delete_element) {
    return deleteAt(array, array->length - 1, delete_element);
}

/**
 * @brief 指定位置修改
 * @param DynamicArray *array 动态数组
 * @param size_t index 修改位置
 * @param size_t element 新的值
 */
void modifyAt(DynamicArray *array, size_t index, element_t element) {
    // 判断位置是否合理
    if (index >= array->length) {
        printf("%zu 位置不合理!!!", index);
        return;
    }
    // 修改
    array->data[index] = element;
}

/**
 * @brief 遍历所有的元素
 * @param DynamicArray *array
 */
void printfDynamicArray(DynamicArray *array) {
    printf("容量：%zu , 长度：%zu, 元素：", array->capacity, array->length);
    for (size_t i = 0; i < array->length; i++) {
        printf("%d ", array->data[i]);
    }
    printf("\n\n");
}

/**
 * @brief 释放动态数组内存
 * @param DynamicArray *array 动态数组
 */
void freeDynamicArray(DynamicArray *array) {
    // 释放内存
    free(array->data);
    // 重置成员值
    array->data = NULL;
    array->capacity = 0;
    array->length = 0;
}

int main() {
    // 声明动态数组
    DynamicArray array;
    // 初始化动态数组
    initDynamicArray(&array, 8);
    // 末尾插入元素
    insertEnd(&array, 100);
    insertEnd(&array, 200);
    insertEnd(&array, 300);
    insertEnd(&array, 400);
    insertEnd(&array, 500);
    insertEnd(&array, 600);
    printfDynamicArray(&array);
    // 插入元素
    insertAt(&array, 2, 250);
    printfDynamicArray(&array);
    // 删除末尾元素
    element_t delete_element;
    deleteEnd(&array, &delete_element);
    printf("%d 被删除了\n", delete_element);
    printfDynamicArray(&array);
    // 指定位置删除
    deleteAt(&array, 2, &delete_element);
    printf("%d 被删除了\n", delete_element);
    printfDynamicArray(&array);
    // 指定位置修改
    modifyAt(&array, 1, 20000);
    printfDynamicArray(&array);
    return 0;
}

// 定义结点中维护的数据类型
typedef int element_t;

// 定义结构体，表示链表中的结点
typedef struct Node {
    element_t data;       // 结点中的数据
    struct Node* next;    // 下个结点的地址
} Node;

// 定义结构体，表示链表
typedef struct {
    Node *head;           // 头结点地址
    size_t length;        // 链表的长度 (已添加的结点的个数)
} LinkedList;

/**
 * @brief 初始化链表
 * @param LinkedList *list 链表
 */
void initLinkedList(LinkedList *list) {
    list->head = NULL;
    list->length = 0;
}

/**
 * @brief 返回链表的长度
 * @param const LinkedList *list
 * @return size_t 链表的长度
 */
size_t getLength(const LinkedList *list) {
    return list->length;
}

/**
 * @brief 返回指定位置的上一个结点
 * @param LinkedList *list
 * @param size_t index
 * @return Node * 指定位置的上一个结点的地址
 */
Node *getPrevNode(LinkedList *list, size_t index) {
    Node *current_node = list->head;
    for (size_t i = 1; i < index; i++) {
        // 注意：若改为 i=0 则函数返回的是指定位置的结点
        current_node = current_node->next;
    }
    return current_node;
}

/**
 * @brief 在指定位置插入新结点
 * @param LinkedList *list 链表
 * @param size_t index 位置（下标从 0 开始）
 * @param element_t element 新结点的数据值
 */
void insertAt(LinkedList *list, size_t index, element_t element) {
    // 判断插入位置是否合理
    if (index > list->length) {
        printf("%zu 位置不合理!!!\n", index);
        return;
    }
    // 动态分配内存
    Node *new_node = (Node *)malloc(sizeof(Node));
    // 给结点的成员赋值
    new_node->data = element;
    new_node->next = NULL;
    // 分两种情况:
    if (index == 0) {
        // 作为头结点插入，新节点将成为链表的新头节点。它的 next 指针指向当前的头节点，然后将链表的头指针更新为新节点。
        // 将 head 的值赋值给 new_node 的 next
        new_node->next = list->head;
        // 在将 new_node 赋值给 head
        list->head = new_node;
    } else {
        Node *current_node = getPrevNode(list, index);
        // 修改指向
        // 将 current_node 的 next 赋值给 new_node 的 next
        new_node->next = current_node->next;
        // 再将 new_node 赋值给 current_node 的 next
        current_node->next = new_node;
    }
    // 长度自增
    list->length++;
}

/**
 * @brief 在末尾插入结点
 * @param LinkedList *list 链表
 * @param element_t element 新结点的数据值
 */
void insertEnd(LinkedList *list, element_t element) {
    insertAt(list, list->length, element);
}

/**
 * @brief 删除指定位置的结点，并将删除的结点的数据值保存到第三个参数中
 * @param LinkedList *list 链表
 * @param size_t index 删除位置（索引）
 * @param element_t *deleted_element 用于存储被删除的结点的数据值
 * @return bool 是否删除成功，1 表示成功，0 表示删除失败
 */
bool deleteAt(LinkedList *list, size_t index, element_t *delete_element) {
    // 判断删除的位置是否合理
    if (index >= list->length) {
        return false;
    }
    // 定义指针，保存被删除结点的地址
    Node *delete_node;
    // 分两种情况:
    if (index == 0) {
        // 删除头结点
        // 记录被删除结点
        delete_node = list->head;
        // 保存被删除的结点的值
        *delete_element = list->head->data;
        // 修改指向
        list->head = list->head->next;
    } else {
        Node *current_node = getPrevNode(list, index);
        // 记录被删除的结点
        delete_node = current_node->next;
        // 保存将被删除节点的值
        *delete_element = current_node->next->data;
        // 修改指向
        current_node->next = current_node->next->next;
    }
    // 释放结点的内存
    free(delete_node);
    // 长度自减
    list->length--;
    return true;
}

/**
 * @brief 删除末尾元素
 * @param LinkedList *list 链表
 * @param element_t *deleted_element 用于存储被删除的结点的数据值
 * @return bool 是否删除成功，1 表示成功，0 表示删除失败
 */
bool deleteEnd(LinkedList *list, element_t *delete_element) {
    return deleteAt(list, list->length - 1, delete_element);
}

/**
 * @brief 获取指定位置的结点的数据值
 * @param LinkedList *list 用获取的链表
 * @param size_t index 获取的下标
 * @param element_t *element 用于存储结点的数据值
 */
void getValue(LinkedList *list, size_t index, element_t *element) {
    // 判断位置是否合理
    if (index >= list->length) {
        printf("%zu 位置不合理!!! \n", index);
        return;
    }
    // 分两种情况:
    if (index == 0) {
        // 头结点的值
        *element = list->head->data;
    } else {
        // 其他结点的值
        Node *prev_node = getPrevNode(list, index);
        *element = prev_node->next->data;
    }
}

/**
 * @brief 修改指定位置的结点的数据值
 * @param LinkedList *list 链表
 * @param size_t index 位置
 * @param element_t new_value 新的数据值
 */
void setValue(LinkedList *list, size_t index, element_t new_value) {
    // 判断位置是否合理
    if (index >= list->length) {
        printf("%zu 位置不合理!!! \n", index);
        return;
    }
    // 分两种情况:
    if (index == 0) {
        // 头结点的值
        list->head->data = new_value;
    } else {
        // 其他结点的值
        Node *prev_node = getPrevNode(list, index);
        prev_node->next->data = new_value;
    }
}

/**
 * @brief 释放链表内存
 * @param LinkedList *list 链表
 */
void freeLinkedList(LinkedList *list) {
    // 从头结点开始
    Node *current_node = list->head;
    Node *delete_node;
    while (current_node != NULL) {
        // 保存被释放的结点的地址
        delete_node = current_node;
        // 修改指向
        current_node = current_node->next;
        // 释放当前结点
        free(delete_node);
    }
    // 重置链表的值
    list->head = NULL;
    list->length = 0;
}

/**
 * @brief 打印链表
 * @param LinkedList *list 链表
 */
void printfLinkedList(LinkedList *list) {
    printf("长度：%zu \n", list->length);
    printf("head: %p \n", list->head); // 头结点
    Node *current_node = list->head;
    while (current_node != NULL) {
        printf("[当前节点地址：%p , 当前结点的值：%d , 下个结点的地址：%p] \n", current_node, current_node->data, current_node->next);
        // 指向下个结点
        current_node = current_node->next;
    }
    printf("\n\n");
}

int main() {
    // 声明链表
    LinkedList list;
    // 初始化链表
    initLinkedList(&list);
    // 末尾插入
    insertEnd(&list, 100);
    insertEnd(&list, 200);
    insertEnd(&list, 300);
    insertEnd(&list, 400);
    insertEnd(&list, 500);
    printfLinkedList(&list);
    // 指定位置插入
    insertAt(&list, 0, 50);
    printfLinkedList(&list);
    insertAt(&list, 3, 250);
    printfLinkedList(&list);
    // 删除尾结点
    element_t delete_element;
    deleteEnd(&list, &delete_element);
    printf("%d 被删除了!!! \n", delete_element);
    printfLinkedList(&list);
    // 指定位置删除
    deleteAt(&list, 3, &delete_element);
    printf("%d 被删除了!!! \n", delete_element);
    printfLinkedList(&list);
    // 获取指定位置结点的值
    element_t element;
    getValue(&list, 2, &element);
    printf("index = 2 的结点的值：%d \n", element);
    getValue(&list, 0, &element);
    printf("index = 0 的结点的值：%d \n", element);
    // 设置指定位置结点的值
    setValue(&list, 0, 50000);
    setValue(&list, 2, 20000);
    printfLinkedList(&list);
    // 释放
    freeLinkedList(&list);
    return 0;
}

// 定义栈中元素的类型
typedef int element_t;

// 定义结构体，表示栈
typedef struct {
    element_t* data;      // 内存空间地址
    size_t capacity;      // 栈容量 (允许的最大元素个数)
    size_t length;        // 栈长度 (已入栈的元素个数)
} Stack;

/**
 * @brief 初始化栈
 * @param Stack *stack
 * @param size_t initCapacity
 */
void initStack(Stack *stack, size_t initCapacity) {
    // 动态分配内存
    stack->data = (element_t*)malloc(sizeof(element_t) * initCapacity);
    // 其他成员赋值
    stack->capacity = initCapacity;
    stack->length = 0;
}

/**
 * @brief 返回栈内元素个数
 * @param const Stack *stack
 * @return size_t 元素个数
 */
size_t getLength(const Stack *stack) {
    return stack->length;
}

/**
 * @brief 调整动态栈结构内存大小
 * @param Stack *stack 栈
 * @param size_t newCapacity 新的容量
 */
void resizeStack(Stack *stack, size_t newCapacity) {
    stack->data = (element_t*)realloc(stack->data, sizeof(element_t) * newCapacity);
    stack->capacity = newCapacity;
}

/**
 * @brief 入栈 (添加元素)
 * @param Stack *stack
 * @param element_t element 要添加的元素值
 */
void pushStack(Stack *stack, element_t element) {
    // 判断容量是否足够
    if (stack->length == stack->capacity) {
        // 扩容
        resizeStack(stack, stack->capacity * 2);
    }
    // 从栈的尾部入栈
    stack->data[stack->length] = element;
    // 长度自增
    stack->length++;
}

/**
 * @brief 出栈（删除元素）
 * @param Stack *stack
 * @param element_t *deleted_element 用于存储被删除的元素
 * @return bool 1 表示成功 0 表示失败
 */
bool popStack(Stack *stack, element_t *deleted_element) {
    // 判断是否为空栈
    if (stack->length == 0) {
        return false;
    }
    // 出栈
    *deleted_element = stack->data[stack->length - 1];
    // 长度自减
    stack->length--;
    return true;
}

/**
 * @brief 释放栈内存
 * @param Stack *stack
 */
void freeStack(Stack *stack) {
    free(stack->data);
    stack->data = NULL;
    stack->capacity = 0;
    stack->length = 0;
}

// 定义队列中元素的类型
typedef int element_t;

// 定义结构体，描述队列
typedef struct {
    element_t* data;      // 内存地址
    size_t capacity;      // 队列容量
    size_t length;        // 队列长度
    size_t front;         // 队首 (指向下一个出队的元素)
    size_t rear;          // 队尾 (指向下一个入队的位置)
} Queue;

/**
 * @brief 初始化队列
 * @param Queue *queue
 * @param size_t initCapacity
 */
void initQueue(Queue *queue, size_t initCapacity) {
    // 动态分配内存
    queue->data = (element_t*)malloc(sizeof(element_t) * initCapacity);
    // 其他成员赋值
    queue->capacity = initCapacity;
    queue->length = 0;
    queue->front = 0;
    queue->rear = 0;
}

/**
 * @brief 返回队列内元素个数
 * @param const Queue *queue
 * @return size_t 元素个数
 */
size_t getLength(const Queue *queue) {
    return queue->length;
}

/**
 * @brief 入队，添加新元素
 * @param Queue *queue
 * @param element_t element
 */
void enqueueQueue(Queue *queue, element_t element) {
    // 判断队列是否满，满队列不允许入队
    if (queue->length == queue->capacity) {
        printf("队列满，%d 入队失败!!!\n", element);
        return;
    }
    // 入队
    queue->data[queue->rear] = element;
    // 计算下个入队的位置
    queue->rear = (queue->rear + 1) % queue->capacity;
    // 长度自增
    queue->length++;
}

/**
 * @brief 出队，删除元素
 * @param Queue *queue
 * @param element_t *deleted_element 用于存储被删除的元素
 * @return bool 1 表示出队成功，0 表示出队失败
 */
bool dequeueQueue(Queue *queue, element_t *deleted_element) {
    // 判断是否为空队列，空队列不允许出队
    if (queue->length == 0) {
        printf("空队列不允许出队\n");
        return false;
    }
    // 出队的元素保存下来
    *deleted_element = queue->data[queue->front];
    // 计算下个出队的位置
    queue->front = (queue->front + 1) % queue->capacity;
    // 长度自减
    queue->length--;
    return true;
}

/**
 * @brief 释放队列内存
 * @param Queue *queue
 */
void freeQueue(Queue *queue) {
    free(queue->data);
    // 重置成员值
    queue->data = NULL;
    queue->capacity = 0;
    queue->length = 0;
    queue->front = 0;
    queue->rear = 0;
}

/**
 * @brief 遍历队列
 * @param Queue *queue
 */
void printfQueue(Queue *queue) {
    printf("capacity: %zu , length: %zu , front: %zu , rear: %zu \n", queue->capacity, queue->length, queue->front, queue->rear);
    printf("元素：");
    for (size_t i = 0; i < queue->length; i++) {
        // 计算接下来要出队的位置
        size_t index = (queue->front + i) % queue->capacity;
        printf("%d ", queue->data[index]);
    }
    printf("\n\n");
}

int main() {
    // 声明队列
    Queue queue;
    // 初始化队列
    initQueue(&queue, 5);
    // 入队
    enqueueQueue(&queue, 100);
    enqueueQueue(&queue, 200);
    enqueueQueue(&queue, 300);
    enqueueQueue(&queue, 400);
    enqueueQueue(&queue, 500);
    enqueueQueue(&queue, 600);
    printfQueue(&queue);
    // 出队
    element_t delete_element;
    dequeueQueue(&queue, &delete_element);
    printfQueue(&queue);
    dequeueQueue(&queue, &delete_element);
    printfQueue(&queue);
    // 释放
    freeQueue(&queue);
    return 0;
}

数据结构基础：数组、链表、栈与队列详解

数据结构基础

1.1 数据结构基础

1.1.1 数据的逻辑结构

1.1.2 数据的存储结构

1.1.3 数据的运算

1.2 数组

1.2.1 数组优缺点

1.2.2 代码设计

1、定义

2、initDynamicArray 函数

3、resizeDynamicArray 函数

4、insertAt 函数

5、insertEnd 函数

6、getLength 函数

7、deleteAt 函数

8、deleteEnd 函数

9、modifyAt 函数

10、printfDynamicArray 函数

11、freeDynamicArray 函数

12、主函数

1.3 链表

1.3.1 链表结构

1.3.2 链表分类

1.3.3 链表优缺点

1.3.4 代码设计

1、定义

2、initLinkedList 函数

3、getLength 函数

4、getPrevNode 函数

5、insertAt 函数

6、insertEnd 函数

7、deleteAt 函数

8、deleteEnd 函数

9、getValue 函数

10、setValue 函数

11、freeLinkedList 函数

12、printfLinkedList 函数

13、主函数

1.4 栈

1.4.1 栈的定义

1.4.2 代码设计

1、定义

2、initStack 函数

3、getLength 函数

4、resizeStack 函数

5、pushStack 函数

6、popStack 函数

7、freeStack 函数

1.5 队列

1.5.1 队列的定义

1.5.2 代码设计

1、定义

2、initQueue 函数

3、getLength 函数

4、enqueueQueue 函数

5、dequeueQueue 函数

6、freeQueue 函数

7、printfQueue 函数

8、主函数

微信扫一扫，关注极客日志

更多推荐文章

相关免费在线工具

2、`initDynamicArray` 函数

3、`resizeDynamicArray` 函数

4、`insertAt` 函数

5、`insertEnd` 函数

6、`getLength` 函数

7、`deleteAt` 函数

8、`deleteEnd` 函数

9、`modifyAt` 函数

10、`printfDynamicArray` 函数

11、`freeDynamicArray` 函数

2、`initLinkedList` 函数

3、`getLength` 函数

4、`getPrevNode` 函数

5、`insertAt` 函数

6、`insertEnd` 函数

7、`deleteAt` 函数

8、`deleteEnd` 函数

9、`getValue` 函数

10、`setValue` 函数

11、`freeLinkedList` 函数

12、`printfLinkedList` 函数

2、`initStack` 函数

3、`getLength` 函数

4、`resizeStack` 函数

5、`pushStack` 函数

6、`popStack` 函数

7、`freeStack` 函数

2、`initQueue` 函数

3、`getLength` 函数

4、`enqueueQueue` 函数

5、`dequeueQueue` 函数

6、`freeQueue` 函数

7、`printfQueue` 函数