• 【蓝桥杯】C语言常见数据结构

    🌸个人主页：Yang-ai-cao

    📕系列专栏：蓝桥杯    C语言

       🍍博学而日参省乎己，知明而行无过矣

    目录

    🌸个人主页：Yang-ai-cao

    📕系列专栏：蓝桥杯    C语言

       🍍博学而日参省乎己，知明而行无过矣

    一、 数组（Array）

    1、定义和初始化数组是一种线性数据结构，用于存储固定大小的相同类型元素。

    2、访问和修改元素

    3、常见操作

    - 遍历数组

    - 查找元素

    线性查找

    二分查找（适用于有序数组）

    - 排序数组（如冒泡排序、快速排序等）

    冒泡排序

    快速排序

    二、 链表（Linked List）

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

    2、创建和初始化链表

    常见操作

    - 插入节点（在头部、尾部或中间插入）

    在头部插入节点

    在尾部插入节点

    在中间插入节点（在指定位置后插入）

    - 删除节点（删除指定值的节点或指定位置的节点）

    删除指定值的节点

    删除指定位置的节点

    - 遍历链表

    四、总结

    在蓝桥杯竞赛中，C语言是常用的编程语言之一。参赛者需要掌握一些常见的数据结构，以便高效地解决竞赛中的问题。以下是C语言中常见的几种数据结构及其基本操作的介绍。

    一、 数组（Array）

    1、定义和初始化
    数组是一种线性数据结构，用于存储固定大小的相同类型元素。

    1. // 定义和初始化一个整型数组
    2. int arr[5] = {1, 2, 3, 4, 5};
    3.  
    4. // 动态分配数组
    5. int *arr = (int *)malloc(5 * sizeof(int));

    2、访问和修改元素

    1. // 访问数组元素
    2. int value = arr[2]; // 获取第三个元素
    3.  
    4. // 修改数组元素
    5. arr[2] = 10; // 将第三个元素修改为10

    3、常见操作


    - 遍历数组
    1. #include 
    2.  
    3. void traverseArray(int arr[], int size) {
    4.     for (int i = 0; i < size; i++) {
    5.         printf("%d ", arr[i]);
    6.     }
    7.     printf("\n");
    8. }
    9.  
    10. int main() {
    11.     int arr[] = {1, 2, 3, 4, 5};
    12.     int size = sizeof(arr) / sizeof(arr[0]);
    13.     traverseArray(arr, size);
    14.     return 0;
    15. }

    - 查找元素
    线性查找
    1. #include <stdio.h>
    2.  
    3. int linearSearch(int arr[], int size, int target) {
    4.     for (int i = 0; i < size; i++) {
    5.         if (arr[i] == target) {
    6.             return i; // 返回目标元素的索引
    7.         }
    8.     }
    9.     return -1; // 没有找到目标元素
    10. }
    11.  
    12. int main() {
    13.     int arr[] = {1, 2, 3, 4, 5};
    14.     int size = sizeof(arr) / sizeof(arr[0]);
    15.     int target = 3;
    16.     int result = linearSearch(arr, size, target);
    17.     if (result != -1) {
    18.         printf("Element found at index %d\n", result);
    19.     } else {
    20.         printf("Element not found\n");
    21.     }
    22.     return 0;
    23. }
    二分查找（适用于有序数组）
    1. #include 
    2.  
    3. int binarySearch(int arr[], int size, int target) {
    4.     int left = 0, right = size - 1;
    5.     while (left <= right) {
    6.         int mid = left + (right - left) / 2;
    7.         if (arr[mid] == target) {
    8.             return mid; // 找到目标元素
    9.         }
    10.         if (arr[mid] < target) {
    11.             left = mid + 1; // 向右半部分查找
    12.         } else {
    13.             right = mid - 1; // 向左半部分查找
    14.         }
    15.     }
    16.     return -1; // 没有找到目标元素
    17. }
    18.  
    19. int main() {
    20.     int arr[] = {1, 2, 3, 4, 5};
    21.     int size = sizeof(arr) / sizeof(arr[0]);
    22.     int target = 3;
    23.     int result = binarySearch(arr, size, target);
    24.     if (result != -1) {
    25.         printf("Element found at index %d\n", result);
    26.     } else {
    27.         printf("Element not found\n");
    28.     }
    29.     return 0;
    30. }
    - 排序数组（如冒泡排序、快速排序等）
    冒泡排序
    1. #include <stdio.h>
    2.  
    3. void bubbleSort(int arr[], int size) {
    4.     for (int i = 0; i < size - 1; i++) {
    5.         for (int j = 0; j < size - i - 1; j++) {
    6.             if (arr[j] > arr[j + 1]) {
    7.                 // 交换元素
    8.                 int temp = arr[j];
    9.                 arr[j] = arr[j + 1];
    10.                 arr[j + 1] = temp;
    11.             }
    12.         }
    13.     }
    14. }
    15.  
    16. int main() {
    17.     int arr[] = {5, 2, 9, 1, 5, 6};
    18.     int size = sizeof(arr) / sizeof(arr[0]);
    19.     bubbleSort(arr, size);
    20.     for (int i = 0; i < size; i++) {
    21.         printf("%d ", arr[i]);
    22.     }
    23.     printf("\n");
    24.     return 0;
    25. }
    快速排序
    1. #include 
    2.  
    3. void swap(int* a, int* b) {
    4.     int temp = *a;
    5.     *a = *b;
    6.     *b = temp;
    7. }
    8.  
    9. int partition(int arr[], int low, int high) {
    10.     int pivot = arr[high]; // 选择最后一个元素作为枢轴
    11.     int i = (low - 1); // 较小元素的索引
    12.     for (int j = low; j <= high - 1; j++) {
    13.         // 如果当前元素小于或等于枢轴
    14.         if (arr[j] <= pivot) {
    15.             i++; // 增加较小元素的索引
    16.             swap(&arr[i], &arr[j]);
    17.         }
    18.     }
    19.     swap(&arr[i + 1], &arr[high]);
    20.     return (i + 1);
    21. }
    22.  
    23. void quickSort(int arr[], int low, int high) {
    24.     if (low < high) {
    25.         int pi = partition(arr, low, high);
    26.  
    27.         // 分别对枢轴元素左右两部分进行快速排序
    28.         quickSort(arr, low, pi - 1);
    29.         quickSort(arr, pi + 1, high);
    30.     }
    31. }
    32.  
    33. int main() {
    34.     int arr[] = {10, 7, 8, 9, 1, 5};
    35.     int size = sizeof(arr) / sizeof(arr[0]);
    36.     quickSort(arr, 0, size - 1);
    37.     for (int i = 0; i < size; i++) {
    38.         printf("%d ", arr[i]);
    39.     }
    40.     printf("\n");
    41.     return 0;
    42. }

    二、 链表（Linked List）

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

    1. // 定义链表节点结构
    2. struct Node {
    3.     int data;
    4.     struct Node *next;
    5. };

    2、创建和初始化链表

    1. // 创建一个新节点
    2. struct Node* createNode(int data) {
    3.     struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    4.     newNode->data = data;
    5.     newNode->next = NULL;
    6.     return newNode;
    7. }
    8. // 初始化链表
    9. struct Node* head = createNode(1);
    10. head->next = createNode(2);
    11. head->next->next = createNode(3);

    常见操作


    - 插入节点（在头部、尾部或中间插入）
    在头部插入节点
    1. void insertAtHead(struct Node** head, int data) {
    2.     struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    3.     newNode->data = data;
    4.     newNode->next = *head;
    5.     *head = newNode;
    6. }
    在尾部插入节点
    1. void insertAtTail(struct Node** head, int data) {
    2.     struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    3.     newNode->data = data;
    4.     newNode->next = NULL;
    5.     if (*head == NULL) {
    6.         *head = newNode;
    7.         return;
    8.     }
    9.     struct Node* temp = *head;
    10.     while (temp->next != NULL) {
    11.         temp = temp->next;
    12.     }
    13.     temp->next = newNode;
    14. }
    在中间插入节点（在指定位置后插入）
    1. void insertAfter(struct Node* prevNode, int data) {
    2.     if (prevNode == NULL) {
    3.         printf("Previous node cannot be NULL\n");
    4.         return;
    5.     }
    6.     struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    7.     newNode->data = data;
    8.     newNode->next = prevNode->next;
    9.     prevNode->next = newNode;
    10. }
    - 删除节点（删除指定值的节点或指定位置的节点）
    删除指定值的节点
    1. void deleteNodeByValue(struct Node** head, int key) {
    2.     struct Node* temp = *head;
    3.     struct Node* prev = NULL;
    4.  
    5.     // 如果头节点就是要删除的节点
    6.     if (temp != NULL && temp->data == key) {
    7.         *head = temp->next; // 改变头节点
    8.         free(temp); // 释放旧头节点
    9.         return;
    10.     }
    11.  
    12.     // 搜索要删除的节点，保持前一个节点的指针
    13.     while (temp != NULL && temp->data != key) {
    14.         prev = temp;
    15.         temp = temp->next;
    16.     }
    17.  
    18.     // 如果没有找到要删除的节点
    19.     if (temp == NULL) return;
    20.  
    21.     // 解除节点链接
    22.     prev->next = temp->next;
    23.  
    24.     free(temp); // 释放内存
    25. }
    删除指定位置的节点
    1. void deleteNodeByPosition(struct Node** head, int position) {
    2.     if (*head == NULL) return;
    3.  
    4.     struct Node* temp = *head;
    5.  
    6.     // 如果头节点需要被删除
    7.     if (position == 0) {
    8.         *head = temp->next; // 改变头节点
    9.         free(temp); // 释放旧头节点
    10.         return;
    11.     }
    12.  
    13.     // 找到要删除的节点的前一个节点
    14.     for (int i = 0; temp != NULL && i < position - 1; i++) {
    15.         temp = temp->next;
    16.     }
    17.  
    18.     // 如果位置超过链表长度
    19.     if (temp == NULL || temp->next == NULL) return;
    20.  
    21.     // 节点temp->next是要删除的节点
    22.     struct Node* next = temp->next->next;
    23.  
    24.     free(temp->next); // 释放内存
    25.  
    26.     temp->next = next; // 解除节点链接
    27. }
    - 遍历链表
    1. void traverseList(struct Node* head) {
    2.     struct Node* temp = head;
    3.     while (temp != NULL) {
    4.         printf("%d -> ", temp->data);
    5.         temp = temp->next;
    6.     }
    7.     printf("NULL\n");
    8. }

    三、栈（Stack）

    1、定义和初始化
    栈是一种后进先出（LIFO）的数据结构，可使用数组或链表实现。

    1. // 使用数组实现栈
    2. #define MAX 100
    3.  
    4. struct Stack {
    5.     int top;
    6.     int items[MAX];
    7. };
    8.  
    9. // 初始化栈
    10. void initStack(struct Stack* s) {
    11.     s->top = -1;
    12. }
    13.  
    14. // 检查栈是否为空
    15. int isEmpty(struct Stack* s) {
    16.     return s->top == -1;
    17. }
    18.  
    19. // 检查栈是否满
    20. int isFull(struct Stack* s) {
    21.     return s->top == MAX - 1;
    22. }

    2、 常见操作


    - 压栈（Push）
    1. void push(struct Stack* s, int item) {
    2.     if (isFull(s)) {
    3.         printf("Stack is full\n");
    4.         return;
    5.     }
    6.     s->items[++s->top] = item;
    7. }
    - 弹栈（Pop）
    1. int pop(struct Stack* s) {
    2.     if (isEmpty(s)) {
    3.         printf("Stack is empty\n");
    4.         return -1;
    5.     }
    6.     return s->items[s->top--];
    7. }
    - 获取栈顶元素（Peek）
    1. int peek(struct Stack* s) {
    2.     if (isEmpty(s)) {
    3.         printf("Stack is empty\n");
    4.         return -1;
    5.     }
    6.     return s->items[s->top];
    7. }

    四、 队列（Queue）

    1、定义和初始化
    队列是一种先进先出（FIFO）的数据结构，可使用数组或链表实现。

    1. // 使用数组实现队列
    2. #define MAX 100
    3.  
    4. struct Queue {
    5.     int front, rear, size;
    6.     int items[MAX];
    7. };
    8.  
    9. // 初始化队列
    10. void initQueue(struct Queue* q) {
    11.     q->front = 0;
    12.     q->rear = MAX - 1;
    13.     q->size = 0;
    14. }
    15.  
    16. // 检查队列是否为空
    17. int isEmpty(struct Queue* q) {
    18.     return q->size == 0;
    19. }
    20.  
    21. // 检查队列是否满
    22. int isFull(struct Queue* q) {
    23.     return q->size == MAX;
    24. }

    2、常见操作


    - 入队（Enqueue）
    1. void enqueue(struct Queue* q, int item) {
    2.     if (isFull(q)) {
    3.         printf("Queue is full\n");
    4.         return;
    5.     }
    6.     q->rear = (q->rear + 1) % MAX;
    7.     q->items[q->rear] = item;
    8.     q->size++;
    9. }
    - 出队（Dequeue）
    1. int dequeue(struct Queue* q) {
    2.     if (isEmpty(q)) {
    3.         printf("Queue is empty\n");
    4.         return -1;
    5.     }
    6.     int item = q->items[q->front];
    7.     q->front = (q->front + 1) % MAX;
    8.     q->size--;
    9.     return item;
    10. }
    - 获取队首元素（Front）
    1. int front(struct Queue* q) {
    2.     if (isEmpty(q)) {
    3.         printf("Queue is empty\n");
    4.         return -1;
    5.     }
    6.     return q->items[q->front];
    7. }

    五、树 (Tree)

    树是一种分层数据结构，由节点（Node）组成，每个节点包含一个值和指向子节点的指针。最常见的树类型是二叉树（Binary Tree），其中每个节点最多有两个子节点。

    1、二叉树节点结构定义
    1. #include 
    2. #include 
    3.  
    4. // 定义二叉树节点结构
    5. struct TreeNode {
    6.     int data;
    7.     struct TreeNode* left;
    8.     struct TreeNode* right;
    9. };
    2、插入节点

    以  二叉搜索树（Binary Search Tree, BST） 的插入函数为例。二叉搜索树是一种特殊的二叉树，其中每个节点的左子树包含的节点值都小于该节点的值，而右子树包含的节点值都大于该节点的值。

    插入节点的过程

    1. 检查根节点是否为空：
      • 如果根节点为空，创建一个新的节点并将其作为根节点返回。
    2. 比较插入值与当前节点值：
      • 如果插入值小于当前节点值，递归地在左子树中插入该值。
      • 如果插入值大于当前节点值，递归地在右子树中插入该值。
    1. // 插入节点函数
    2. struct TreeNode* insertNode(struct TreeNode* root, int data) {
    3.     if (root == NULL) {
    4.         struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    5.         newNode->data = data;
    6.         newNode->left = newNode->right = NULL;
    7.         return newNode;
    8.     }
    9.     if (data < root->data) {
    10.         root->left = insertNode(root->left, data);
    11.     } else {
    12.         root->right = insertNode(root->right, data);
    13.     }
    14.     return root;
    15. }
    3、遍历二叉树
    1. // 中序遍历函数
    2. void inorderTraversal(struct TreeNode* root) {
    3.     if (root != NULL) {
    4.         inorderTraversal(root->left);
    5.         printf("%d ", root->data);
    6.         inorderTraversal(root->right);
    7.     }
    8. }

    六、图 (Graph)

    图是一种非线性数据结构，由节点（顶点）和连接这些节点的边组成。图可以是有向的（Directed）或无向的（Undirected）。

    邻接矩阵表示图

    1. #include 
    2. #include 
    3.  
    4. #define MAX_VERTICES 5
    5.  
    6. // 添加边的函数
    7. void addEdge(int graph[MAX_VERTICES][MAX_VERTICES], int u, int v) {
    8.     graph[u][v] = 1;
    9.     graph[v][u] = 1; // 如果是无向图
    10. }
    11.  
    12. // 打印图的函数
    13. void printGraph(int graph[MAX_VERTICES][MAX_VERTICES]) {
    14.     for (int i = 0; i < MAX_VERTICES; i++) {
    15.         for (int j = 0; j < MAX_VERTICES; j++) {
    16.             printf("%d ", graph[i][j]);
    17.         }
    18.         printf("\n");
    19.     }
    20. }
    21.  
    22. int main() {
    23.     int graph[MAX_VERTICES][MAX_VERTICES] = {0};
    24.  
    25.     addEdge(graph, 0, 1);
    26.     addEdge(graph, 0, 4);
    27.     addEdge(graph, 1, 2);
    28.     addEdge(graph, 1, 3);
    29.     addEdge(graph, 1, 4);
    30.     addEdge(graph, 2, 3);
    31.     addEdge(graph, 3, 4);
    32.  
    33.     printGraph(graph);
    34.  
    35.     return 0;
    36. }

    七、哈希表 (Hash Table)

    哈希表是一种用于快速查找的数据结构，通过哈希函数将键映射到数组中的位置。

    1、哈希表节点结构定义

    1. #include 
    2. #include 
    3. #include 
    4.  
    5. #define TABLE_SIZE 10
    6.  
    7. // 定义哈希表节点结构
    8. struct HashNode {
    9.     int key;
    10.     int value;
    11.     struct HashNode* next;
    12. };
    13.  
    14. // 定义哈希表结构
    15. struct HashTable {
    16.     struct HashNode* table[TABLE_SIZE];
    17. };

    2、哈希函数

    1. // 哈希函数
    2. int hashFunction(int key) {
    3.     return key % TABLE_SIZE;
    4. }

    3、插入键值对

    1. // 插入键值对的函数
    2. void insert(struct HashTable* hashTable, int key, int value) {
    3.     int hashIndex = hashFunction(key);
    4.     struct HashNode* newNode = (struct HashNode*)malloc(sizeof(struct HashNode));
    5.     newNode->key = key;
    6.     newNode->value = value;
    7.     newNode->next = hashTable->table[hashIndex];
    8.     hashTable->table[hashIndex] = newNode;
    9. }

    4、查找键值对

    1. // 查找键值对的函数
    2. int search(struct HashTable* hashTable, int key) {
    3.     int hashIndex = hashFunction(key);
    4.     struct HashNode* node = hashTable->table[hashIndex];
    5.     while (node != NULL) {
    6.         if (node->key == key) {
    7.             return node->value;
    8.         }
    9.         node = node->next;
    10.     }
    11.     return -1; // 未找到键
    12. }

    总结

         掌握这些常见的数据结构及其基本操作是参加蓝桥杯竞赛的基础。通过练习和理解这些数据结构，咱将能够更高效地解决竞赛中的各种编程问题。希望这些介绍对你有所帮助！如果你有任何具体问题或需要进一步的帮助，请随时告诉我。

  • 相关阅读:
    九、SpringMVC（3）
    Python课程设计之学生信息管理系统
    算法面试-深度学习基础面试题整理-AIGC相关（2023.9.01）
    软件工程理论与实践 (吕云翔) 第八章 软件体系结构与设计模式课后习题及其答案解析
    SQL必需掌握的100个重要知识点：更新和删除数据
    淘宝战场分离，淘宝商家跻身抖音电商，是自掘坟墓还是另有他法？
    Llama 3 开源了「GitHub 热点速览」
    HTML5学习笔记（一）
    linux使用vi/vim进行多行注释和取消
    LeetCode_贪心算法_困难_630.课程表 III
  • 原文地址：https://blog.csdn.net/aaaa_hsjsueu/article/details/139417715