【蓝桥杯】常见的数据结构

🌸个人主页：Yang-ai-cao

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

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

---

目录

🌸个人主页：Yang-ai-cao

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

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

一、 数组（Array）

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

2、访问和修改元素

3、常见操作

- 遍历数组

- 查找元素

线性查找

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

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

冒泡排序

快速排序

二、 链表（Linked List）

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

2、创建和初始化链表

常见操作

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

在头部插入节点

在尾部插入节点

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

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

删除指定值的节点

删除指定位置的节点

- 遍历链表

四、总结

---

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

一、 数组（Array）

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

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

2、访问和修改元素

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

3、常见操作

- 遍历数组

#include <stdio.h>void traverseArray(int arr[], int size) {for (int i = 0; i < size; i++) {printf("%d ", arr[i]);}printf("\n");
}int main() {int arr[] = {1, 2, 3, 4, 5};int size = sizeof(arr) / sizeof(arr[0]);traverseArray(arr, size);return 0;
}

- 查找元素

线性查找

#include <stdio.h>int linearSearch(int arr[], int size, int target) {for (int i = 0; i < size; i++) {if (arr[i] == target) {return i; // 返回目标元素的索引}}return -1; // 没有找到目标元素
}int main() {int arr[] = {1, 2, 3, 4, 5};int size = sizeof(arr) / sizeof(arr[0]);int target = 3;int result = linearSearch(arr, size, target);if (result != -1) {printf("Element found at index %d\n", result);} else {printf("Element not found\n");}return 0;
}

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

#include <stdio.h>int binarySearch(int arr[], int size, int target) {int left = 0, right = size - 1;while (left <= right) {int mid = left + (right - left) / 2;if (arr[mid] == target) {return mid; // 找到目标元素}if (arr[mid] < target) {left = mid + 1; // 向右半部分查找} else {right = mid - 1; // 向左半部分查找}}return -1; // 没有找到目标元素
}int main() {int arr[] = {1, 2, 3, 4, 5};int size = sizeof(arr) / sizeof(arr[0]);int target = 3;int result = binarySearch(arr, size, target);if (result != -1) {printf("Element found at index %d\n", result);} else {printf("Element not found\n");}return 0;
}

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

冒泡排序

#include <stdio.h>void bubbleSort(int arr[], int size) {for (int i = 0; i < size - 1; i++) {for (int j = 0; j < size - i - 1; j++) {if (arr[j] > arr[j + 1]) {// 交换元素int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}
}int main() {int arr[] = {5, 2, 9, 1, 5, 6};int size = sizeof(arr) / sizeof(arr[0]);bubbleSort(arr, size);for (int i = 0; i < size; i++) {printf("%d ", arr[i]);}printf("\n");return 0;
}

快速排序

#include <stdio.h>void swap(int* a, int* b) {int temp = *a;*a = *b;*b = temp;
}int partition(int arr[], int low, int high) {int pivot = arr[high]; // 选择最后一个元素作为枢轴int i = (low - 1); // 较小元素的索引for (int j = low; j <= high - 1; j++) {// 如果当前元素小于或等于枢轴if (arr[j] <= pivot) {i++; // 增加较小元素的索引swap(&arr[i], &arr[j]);}}swap(&arr[i + 1], &arr[high]);return (i + 1);
}void quickSort(int arr[], int low, int high) {if (low < high) {int pi = partition(arr, low, high);// 分别对枢轴元素左右两部分进行快速排序quickSort(arr, low, pi - 1);quickSort(arr, pi + 1, high);}
}int main() {int arr[] = {10, 7, 8, 9, 1, 5};int size = sizeof(arr) / sizeof(arr[0]);quickSort(arr, 0, size - 1);for (int i = 0; i < size; i++) {printf("%d ", arr[i]);}printf("\n");return 0;
}

二、 链表（Linked List）

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

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

2、创建和初始化链表

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

常见操作

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

在头部插入节点

void insertAtHead(struct Node** head, int data) {struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));newNode->data = data;newNode->next = *head;*head = newNode;
}

在尾部插入节点

void insertAtTail(struct Node** head, int data) {struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));newNode->data = data;newNode->next = NULL;if (*head == NULL) {*head = newNode;return;}struct Node* temp = *head;while (temp->next != NULL) {temp = temp->next;}temp->next = newNode;
}

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

void insertAfter(struct Node* prevNode, int data) {if (prevNode == NULL) {printf("Previous node cannot be NULL\n");return;}struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));newNode->data = data;newNode->next = prevNode->next;prevNode->next = newNode;
}

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

删除指定值的节点

void deleteNodeByValue(struct Node** head, int key) {struct Node* temp = *head;struct Node* prev = NULL;// 如果头节点就是要删除的节点if (temp != NULL && temp->data == key) {*head = temp->next; // 改变头节点free(temp); // 释放旧头节点return;}// 搜索要删除的节点，保持前一个节点的指针while (temp != NULL && temp->data != key) {prev = temp;temp = temp->next;}// 如果没有找到要删除的节点if (temp == NULL) return;// 解除节点链接prev->next = temp->next;free(temp); // 释放内存
}

删除指定位置的节点

void deleteNodeByPosition(struct Node** head, int position) {if (*head == NULL) return;struct Node* temp = *head;// 如果头节点需要被删除if (position == 0) {*head = temp->next; // 改变头节点free(temp); // 释放旧头节点return;}// 找到要删除的节点的前一个节点for (int i = 0; temp != NULL && i < position - 1; i++) {temp = temp->next;}// 如果位置超过链表长度if (temp == NULL || temp->next == NULL) return;// 节点temp->next是要删除的节点struct Node* next = temp->next->next;free(temp->next); // 释放内存temp->next = next; // 解除节点链接
}

- 遍历链表

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

三、栈（Stack）

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

// 使用数组实现栈
#define MAX 100struct Stack {int top;int items[MAX];
};// 初始化栈
void initStack(struct Stack* s) {s->top = -1;
}// 检查栈是否为空
int isEmpty(struct Stack* s) {return s->top == -1;
}// 检查栈是否满
int isFull(struct Stack* s) {return s->top == MAX - 1;
}

2、 常见操作

- 压栈（Push）

void push(struct Stack* s, int item) {if (isFull(s)) {printf("Stack is full\n");return;}s->items[++s->top] = item;
}

- 弹栈（Pop）

int pop(struct Stack* s) {if (isEmpty(s)) {printf("Stack is empty\n");return -1;}return s->items[s->top--];
}

- 获取栈顶元素（Peek）

int peek(struct Stack* s) {if (isEmpty(s)) {printf("Stack is empty\n");return -1;}return s->items[s->top];
}

四、 队列（Queue）

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

// 使用数组实现队列
#define MAX 100struct Queue {int front, rear, size;int items[MAX];
};// 初始化队列
void initQueue(struct Queue* q) {q->front = 0;q->rear = MAX - 1;q->size = 0;
}// 检查队列是否为空
int isEmpty(struct Queue* q) {return q->size == 0;
}// 检查队列是否满
int isFull(struct Queue* q) {return q->size == MAX;
}

2、常见操作

- 入队（Enqueue）

void enqueue(struct Queue* q, int item) {if (isFull(q)) {printf("Queue is full\n");return;}q->rear = (q->rear + 1) % MAX;q->items[q->rear] = item;q->size++;
}

- 出队（Dequeue）

int dequeue(struct Queue* q) {if (isEmpty(q)) {printf("Queue is empty\n");return -1;}int item = q->items[q->front];q->front = (q->front + 1) % MAX;q->size--;return item;
}

- 获取队首元素（Front）

int front(struct Queue* q) {if (isEmpty(q)) {printf("Queue is empty\n");return -1;}return q->items[q->front];
}

五、树 (Tree)

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

1、二叉树节点结构定义

#include <stdio.h>
#include <stdlib.h>// 定义二叉树节点结构
struct TreeNode {int data;struct TreeNode* left;struct TreeNode* right;
};

2、插入节点

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

插入节点的过程

1. 检查根节点是否为空：
   • 如果根节点为空，创建一个新的节点并将其作为根节点返回。
2. 比较插入值与当前节点值：
   • 如果插入值小于当前节点值，递归地在左子树中插入该值。
   • 如果插入值大于当前节点值，递归地在右子树中插入该值。

// 插入节点函数
struct TreeNode* insertNode(struct TreeNode* root, int data) {if (root == NULL) {struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));newNode->data = data;newNode->left = newNode->right = NULL;return newNode;}if (data < root->data) {root->left = insertNode(root->left, data);} else {root->right = insertNode(root->right, data);}return root;
}

3、遍历二叉树

// 中序遍历函数
void inorderTraversal(struct TreeNode* root) {if (root != NULL) {inorderTraversal(root->left);printf("%d ", root->data);inorderTraversal(root->right);}
}

六、图 (Graph)

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

邻接矩阵表示图

#include <stdio.h>
#include <stdlib.h>#define MAX_VERTICES 5// 添加边的函数
void addEdge(int graph[MAX_VERTICES][MAX_VERTICES], int u, int v) {graph[u][v] = 1;graph[v][u] = 1; // 如果是无向图
}// 打印图的函数
void printGraph(int graph[MAX_VERTICES][MAX_VERTICES]) {for (int i = 0; i < MAX_VERTICES; i++) {for (int j = 0; j < MAX_VERTICES; j++) {printf("%d ", graph[i][j]);}printf("\n");}
}int main() {int graph[MAX_VERTICES][MAX_VERTICES] = {0};addEdge(graph, 0, 1);addEdge(graph, 0, 4);addEdge(graph, 1, 2);addEdge(graph, 1, 3);addEdge(graph, 1, 4);addEdge(graph, 2, 3);addEdge(graph, 3, 4);printGraph(graph);return 0;
}

七、哈希表 (Hash Table)

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

1、哈希表节点结构定义

#include <stdio.h>
#include <stdlib.h>
#include <string.h>#define TABLE_SIZE 10// 定义哈希表节点结构
struct HashNode {int key;int value;struct HashNode* next;
};// 定义哈希表结构
struct HashTable {struct HashNode* table[TABLE_SIZE];
};

2、哈希函数

// 哈希函数
int hashFunction(int key) {return key % TABLE_SIZE;
}

3、插入键值对

// 插入键值对的函数
void insert(struct HashTable* hashTable, int key, int value) {int hashIndex = hashFunction(key);struct HashNode* newNode = (struct HashNode*)malloc(sizeof(struct HashNode));newNode->key = key;newNode->value = value;newNode->next = hashTable->table[hashIndex];hashTable->table[hashIndex] = newNode;
}

4、查找键值对

// 查找键值对的函数
int search(struct HashTable* hashTable, int key) {int hashIndex = hashFunction(key);struct HashNode* node = hashTable->table[hashIndex];while (node != NULL) {if (node->key == key) {return node->value;}node = node->next;}return -1; // 未找到键
}

总结

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