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

server/2024/9/23 4:16:50/

🌸个人主页：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; // 未找到键
}

总结

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


http://www.ppmy.cn/server/47454.html

相关文章

【人工智能】第二部分：ChatGPT的架构设计和训练过程

【人工智能】第二部分：ChatGPT的架构设计和训练过程

人不走空 &#x1f308;个人主页&#xff1a;人不走空 &#x1f496;系列专栏&#xff1a;算法专题 ⏰诗词歌赋&#xff1a;斯是陋室&#xff0c;惟吾德馨 目录 &#x1f308;个人主页&#xff1a;人不走空 &#x1f496;系列专栏&#xff1a;算法专题 ⏰诗词歌…
阅读更多...
Element-ui使用上传时弹框选择文件类型

Element-ui使用上传时弹框选择文件类型

实现效果 1&#xff0c;点击上传&#xff0c;上传文件&#xff1b; 2&#xff0c;选择文件&#xff1b; 3&#xff0c;弹框选择文件类型&#xff1b; 4&#xff0c;选择类型后确定上传&#xff1b; 一&#xff0c;上传 跳过&#xff1b; 二&#xff0c;定义弹框下拉框…
阅读更多...
Android电量优化，让你的手机续航更持久

Android电量优化，让你的手机续航更持久

节能减排&#xff0c;从我做起。一款Android应用如果非常耗电&#xff0c;是一定会被主人嫌弃的。自从Android手机的主人用了你开发的app&#xff0c;一天下来&#xff0c;也没干啥事&#xff0c;电就没了。那么他就会想尽办法找出耗电量杀手&#xff0c;当他找出后&#xff0c…
阅读更多...
浅谈MySQL事务

浅谈MySQL事务

目录 一&#xff0c;事务的引入 上述的特性叫做“原子性”&#xff08;事务最核心操作&#xff0c;事务还具备别的性质在下文&#xff09;&#xff1b; 二&#xff0c;日志体系 三&#xff0c;事务的使用 四&#xff0c;事务的基本特性 1.脏读&#xff1a; 2.不可重复读 …
阅读更多...
Unity3D 基于YooAssets的资源管理详解

Unity3D 基于YooAssets的资源管理详解

前言 Unity3D 是一款非常流行的游戏开发引擎&#xff0c;它提供了丰富的功能和工具来帮助开发者快速创建高质量的游戏和应用程序。其中&#xff0c;资源管理是游戏开发中非常重要的一部分&#xff0c;它涉及到如何有效地加载、管理和释放游戏中的各种资源&#xff0c;如模型、…
阅读更多...
1.3 寻找灵感：认知系谱图

1.3 寻找灵感：认知系谱图

一个比较具体的例子&#xff0c;你有一个母亲和一个父亲&#xff0c;你同时拥有他们的特点&#xff0c;但你还会有一些自己独有的特点。你继承了你爸妈的基因&#xff0c;还包括他们祖先的基因。 和你拥有一个家族系谱一样&#xff0c;你也拥有一个知识系谱。它不是来自你的家…
阅读更多...
Dinky FlinkSQL Doris读取写入

Dinky FlinkSQL Doris读取写入

Dinky运行前开启全局变量&#xff0c;以支持使用&#xff1a; sink.sink.label-prefix ${idUtil.simpleUUID()} Mysql同步Doris - testMysqlCdcDoris&#xff1a; EXECUTE CDCSOURCE demo_doris WITH (connector mysql-cdc,hostname 172.xxx,port 3306,username xxx,pas…
阅读更多...
Java Keyword

Java Keyword

文章目录 Java Keyword一、基本数据类型相关关键字(8个)&#xff08;1&#xff09;byte&#xff1a;单字节类型&#xff08;2&#xff09;short&#xff1a;短整型&#xff08;3&#xff09;int&#xff1a;整型&#xff08;4&#xff09;long&#xff1a;长整型&#xff08;5&…
阅读更多...
最新文章

Copyright @ 2022~2023