- 区块链的概念及特点
- 区块链的学习路径
- 区块链共识算法
- 进程、线程、内存管理
- 网络通信协议、TCP/IP、UDP、网络拓扑
- 数据结构链表、哈希表、图、树、搜索算法（Python）
- 数据结构链表、哈希表、图、树、搜索算法（C语言）
数据结构链表、哈希表、图、树、搜索算法（C语言）
class C,数据结构,链表,图,树,搜索算法,排序在C语言中，数据结构和算法是计算机科学的基础知识。我们将详细介绍链表、树、图、哈希表、排序和搜索算法的理论，并用C语言实现这些数据结构和算法。每个数据结构和算法都有其特定的应用场景和实现方法。
1. 链表（Linked List）
理论
链表是一种线性数据结构，其中每个元素都是一个独立的节点，这些节点通过指针连接在一起。链表的每个节点包含两个部分：数据部分和指针部分（指向下一个节点）。
- 单链表（Singly Linked List）： 每个节点包含一个数据部分和一个指向下一个节点的指针。
- 双链表（Doubly Linked List）： 每个节点包含一个数据部分、一个指向下一个节点的指针和一个指向上一个节点的指针。
- 循环链表（Circular Linked List）： 最后一个节点的指针指向头节点，形成一个循环结构。
单链表的实现
以下是单链表的C语言实现，包括基本的操作：插入、删除和遍历。
#include <stdio.h>
#include <stdlib.h>
// 定义节点结构
struct Node {
int data;
struct Node* next;
};
// 插入新节点到链表头部
void insertAtHead(struct Node** head_ref, int new_data) {
// 分配新节点
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
// 将数据放入节点
new_node->data = new_data;
// 将新节点的 next 指针指向当前头节点
new_node->next = (*head_ref);
// 将头指针指向新节点
(*head_ref) = new_node;
}
// 删除指定值的节点
void deleteNode(struct Node** head_ref, int key) {
struct Node* temp = *head_ref, *prev;
// 检查头节点是否为要删除的节点
if (temp != NULL && temp->data == key) {
*head_ref = 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 printList(struct Node* node) {
while (node != NULL) {
printf("%d -> ", node->data);
node = node->next;
}
printf("NULL\n");
}
int main() {
struct Node* head = NULL;
insertAtHead(&head, 1);
insertAtHead(&head, 2);
insertAtHead(&head, 3);
insertAtHead(&head, 4);
printf("初始链表: ");
printList(head);
deleteNode(&head, 3);
printf("删除 3 后的链表: ");
printList(head);
return 0;
}
双链表的实现
双链表允许双向遍历，每个节点包含前驱和后继指针。
#include <stdio.h>
#include <stdlib.h>
// 定义节点结构
struct Node {
int data;
struct Node* next;
struct Node* prev;
};
// 插入新节点到链表头部
void insertAtHead(struct Node** head_ref, int new_data) {
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = (*head_ref);
new_node->prev = NULL;
if ((*head_ref) != NULL)
(*head_ref)->prev = new_node;
(*head_ref) = new_node;
}
// 删除指定值的节点
void deleteNode(struct Node** head_ref, struct Node* del) {
if (*head_ref == NULL || del == NULL)
return;
if (*head_ref == del)
*head_ref = del->next;
if (del->next != NULL)
del->next->prev = del->prev;
if (del->prev != NULL)
del->prev->next = del->next;
free(del);
}
// 遍历链表
void printList(struct Node* node) {
struct Node* last;
printf("正向遍历:\n");
while (node != NULL) {
printf("%d -> ", node->data);
last = node;
node = node->next;
}
printf("NULL\n");
printf("反向遍历:\n");
while (last != NULL) {
printf("%d -> ", last->data);
last = last->prev;
}
printf("NULL\n");
}
int main() {
struct Node* head = NULL;
insertAtHead(&head, 1);
insertAtHead(&head, 2);
insertAtHead(&head, 3);
insertAtHead(&head, 4);
printf("初始双向链表: ");
printList(head);
deleteNode(&head, head->next); // 删除第二个节点
printf("删除第二个节点后的链表: ");
printList(head);
return 0;
}
2. 树（Tree）
理论
树是一种层次化的数据结构，由节点组成，其中每个节点都有一个父节点和零个或多个子节点。树的根节点没有父节点，树中的其他节点都有且仅有一个父节点。
- 二叉树（Binary Tree）： 每个节点最多有两个子节点（左子节点和右子节点）。
- 二叉搜索树（Binary Search Tree, BST）： 对于每个节点，左子树中的所有节点值小于该节点值，右子树中的所有节点值大于该节点值。
- 平衡二叉树（Balanced Binary Tree）： 所有叶子节点的深度差不超过一定限制。
二叉搜索树的实现
以下是二叉搜索树的C语言实现，包括插入、搜索和删除操作。
#include <stdio.h>
#include <stdlib.h>
// 定义节点结构
struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
};
// 创建新节点
struct TreeNode* createNode(int data) {
struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
// 插入新节点
struct TreeNode* insert(struct TreeNode* node, int data) {
if (node == NULL)
return createNode(data);
if (data < node->data)
node->left = insert(node->left, data);
else if (data > node->data)
node->right = insert(node->right, data);
return node;
}
// 搜索节点
struct TreeNode* search(struct TreeNode* root, int data) {
if (root == NULL || root->data == data)
return root;
if (data < root->data)
return search(root->left, data);
return search(root->right, data);
}
// 找到最小值节点
struct TreeNode* findMin(struct TreeNode* node) {
struct TreeNode* current = node;
while (current && current->left != NULL)
current = current->left;
return current;
}
// 删除节点
struct TreeNode* deleteNode(struct TreeNode* root, int data) {
if (root == NULL)
return root;
if (data < root->data)
root->left = deleteNode(root->left, data);
else if (data > root->data)
root->right = deleteNode(root->right, data);
else {
if (root->left == NULL) {
struct TreeNode* temp = root->right;
free(root);
return temp;
} else if (root->right == NULL) {
struct TreeNode* temp = root->left;
free(root);
return temp;
}
struct TreeNode* temp = findMin(root->right);
root->data = temp->data;
root->right = deleteNode(root->right, temp->data);
}
return root;
}
// 中序遍历
void inorderTraversal(struct TreeNode* root) {
if (root != NULL) {
inorderTraversal(root->left);
printf("%d ", root->data);
inorderTraversal(root->right);
}
}
int main() {
struct TreeNode* root = NULL;
root = insert(root, 5);
insert(root, 3);
insert(root, 7);
insert(root, 2);
insert(root, 4);
insert(root, 6);
insert(root, 8);
printf("中序遍历: ");
inorderTraversal(root); // 输出: 2 3 4 5 6 7 8
printf("\n");
printf("搜索 4: %p\n", search(root, 4));
// 输出: 非NULL
printf("搜索 9: %p\n", search(root, 9)); // 输出: NULL
root = deleteNode(root, 4);
printf("删除 4 后中序遍历: ");
inorderTraversal(root); // 输出: 2 3 5 6 7 8
printf("\n");
return 0;
}
3. 图（Graph）
理论
图是一种非线性数据结构，由顶点（节点）和边组成。图可以是有向的或无向的，也可以是加权的或无权的。
- 有向图（Directed Graph）： 边有方向。
- 无向图（Undirected Graph）： 边无方向。
- 加权图（Weighted Graph）： 边有权重。
- 无权图（Unweighted Graph）： 边无权重。
图的表示
图可以使用邻接矩阵或邻接表表示。
邻接矩阵表示
邻接矩阵是一个二维数组，其中行列表示顶点，数组中的值表示边的存在（及其权重）。
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 100
// 邻接矩阵表示图
struct Graph {
int numVertices;
int adjMatrix[MAX_VERTICES][MAX_VERTICES];
};
// 创建图
struct Graph* createGraph(int vertices) {
struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
graph->numVertices = vertices;
for (int i = 0; i < vertices; i++)
for (int j = 0; j < vertices; j++)
graph->adjMatrix[i][j] = 0;
return graph;
}
// 添加边
void addEdge(struct Graph* graph, int src, int dest) {
graph->adjMatrix[src][dest] = 1;
graph->adjMatrix[dest][src] = 1; // 无向图
}
// 打印图
void printGraph(struct Graph* graph) {
for (int i = 0; i < graph->numVertices; i++) {
printf("顶点 %d: ", i);
for (int j = 0; j < graph->numVertices; j++) {
if (graph->adjMatrix[i][j])
printf("%d ", j);
}
printf("\n");
}
}
int main() {
struct Graph* graph = createGraph(5);
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;
}
邻接表表示
邻接表是一种更为高效的图表示方法，适用于稀疏图。每个顶点有一个链表，用于存储与该顶点相连的所有其他顶点。
#include <stdio.h>
#include <stdlib.h>
// 链表节点
struct Node {
int vertex;
struct Node* next;
};
// 图结构
struct Graph {
int numVertices;
struct Node** adjLists;
};
// 创建节点
struct Node* createNode(int v) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->vertex = v;
newNode->next = NULL;
return newNode;
}
// 创建图
struct Graph* createGraph(int vertices) {
struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
graph->numVertices = vertices;
graph->adjLists = (struct Node**)malloc(vertices * sizeof(struct Node*));
for (int i = 0; i < vertices; i++)
graph->adjLists[i] = NULL;
return graph;
}
// 添加边
void addEdge(struct Graph* graph, int src, int dest) {
struct Node* newNode = createNode(dest);
newNode->next = graph->adjLists[src];
graph->adjLists[src] = newNode;
newNode = createNode(src);
newNode->next = graph->adjLists[dest];
graph->adjLists[dest] = newNode;
}
// 打印图
void printGraph(struct Graph* graph) {
for (int v = 0; v < graph->numVertices; v++) {
struct Node* temp = graph->adjLists[v];
printf("\n 顶点 %d\n: ", v);
while (temp) {
printf("%d -> ", temp->vertex);
temp = temp->next;
}
printf("\n");
}
}
int main() {
struct Graph* graph = createGraph(5);
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;
}
4. 哈希表（Hash Table）
理论
哈希表是一种用于存储键值对的数据结构，通过哈希函数将键映射到值所在的位置。哈希表支持高效的插入、删除和查找操作。
哈希表的实现
以下是一个简单的哈希表实现，使用链地址法解决冲突。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define TABLE_SIZE 10
// 链表节点
struct Node {
int key;
int value;
struct Node* next;
};
// 哈希表
struct HashTable {
struct Node** table;
};
// 创建节点
struct Node* createNode(int key, int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->key = key;
newNode->value = value;
newNode->next = NULL;
return newNode;
}
// 创建哈希表
struct HashTable* createTable() {
struct HashTable* hashTable = (struct HashTable*)malloc(sizeof(struct HashTable));
hashTable->table = (struct Node**)malloc(TABLE_SIZE * sizeof(struct Node*));
for (int i = 0; i < TABLE_SIZE; i++)
hashTable->table[i] = NULL;
return hashTable;
}
// 哈希函数
int hashFunction(int key) {
return key % TABLE_SIZE;
}
// 插入键值对
void insert(struct HashTable* hashTable, int key, int value) {
int hashIndex = hashFunction(key);
struct Node* newNode = createNode(key, value);
if (hashTable->table[hashIndex] == NULL) {
hashTable->table[hashIndex] = newNode;
} else {
struct Node* temp = hashTable->table[hashIndex];
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
}
}
// 搜索键
int search(struct HashTable* hashTable, int key) {
int hashIndex = hashFunction(key);
struct Node* temp = hashTable->table[hashIndex];
while (temp != NULL) {
if (temp->key == key)
return temp->value;
temp = temp->next;
}
return -1;
}
// 删除键
void delete(struct HashTable* hashTable, int key) {
int hashIndex = hashFunction(key);
struct Node* temp = hashTable->table[hashIndex];
struct Node* prev = NULL;
if (temp != NULL && temp->key == key) {
hashTable->table[hashIndex] = temp->next;
free(temp);
return;
}
while (temp != NULL && temp->key != key) {
prev = temp;
temp = temp->next;
}
if (temp == NULL)
return;
prev->next = temp->next;
free(temp);
}
int main() {
struct HashTable* hashTable = createTable();
insert(hashTable, 1, 10);
insert(hashTable, 2, 20);
insert(hashTable, 3, 30);
insert(hashTable, 4, 40);
printf("搜索键 2: %d\n", search(hashTable, 2)); // 输出: 20
delete(hashTable, 2);
printf("删除键 2 后搜索键 2: %d\n", search(hashTable, 2)); // 输出: -1
return 0;
}
5. 排序算法
排序算法用于将元素按照特定顺序进行排列。常见的排序算法包括冒泡排序、选择排序、插入排序、快速排序和归并排序。
冒泡排序（Bubble Sort）
冒泡排序是一种简单的排序算法，逐步比较相邻元素，并根据需要交换元素。
#include <stdio.h>
// 冒泡排序
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
for
(int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
// 打印数组
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);
bubbleSort(arr, n);
printf("排序后的数组: ");
printArray(arr, n);
return 0;
}
快速排序（Quick Sort）
快速排序是一种分治排序算法，通过选择基准元素将数组划分为两个子数组，然后递归地排序子数组。
#include <stdio.h>
// 交换两个元素
void swap(int* a, int* b) {
int t = *a;
*a = *b;
*b = t;
}
// 划分数组
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);
}
}
// 打印数组
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main() {
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);
printf("排序后的数组: ");
printArray(arr, n);
return 0;
}
6. 搜索算法
搜索算法用于在数据结构中查找特定元素。常见的搜索算法包括线性搜索和二分搜索。
线性搜索（Linear Search）
线性搜索是最简单的搜索算法，从数组的起始位置开始逐个比较元素。
#include <stdio.h>
// 线性搜索
int linearSearch(int arr[], int n, int x) {
for (int i = 0; i < n; i++) {
if (arr[i] == x)
return i;
}
return -1;
}
int main() {
int arr[] = {2, 3, 4, 10, 40};
int n = sizeof(arr) / sizeof(arr[0]);
int x = 10;
int result = linearSearch(arr, n, x);
if (result == -1)
printf("元素不在数组中\n");
else
printf("元素在数组中的位置: %d\n", result);
return 0;
}
二分搜索（Binary Search）
二分搜索是一种高效的搜索算法，适用于有序数组。它通过不断将搜索范围减半来查找元素。
#include <stdio.h>
// 二分搜索
int binarySearch(int arr[], int l, int r, int x) {
while (l <= r) {
int m = l + (r - l) / 2;
if (arr[m] == x)
return m;
if (arr[m] < x)
l = m + 1;
else
r = m - 1;
}
return -1;
}
int main() {
int arr[] = {2, 3, 4, 10, 40};
int n = sizeof(arr) / sizeof(arr[0]);
int x = 10;
int result = binarySearch(arr, 0, n - 1, x);
if (result == -1)
printf("元素不在数组中\n");
else
printf("元素在数组中的位置: %d\n", result);
return 0;
}
这些代码和概念提供了C语言中数据结构和算法的基本实现。对于每种数据结构和算法，理解其应用场景和特性是关键。希望这些示例能帮助你更好地理解数据结构和算法的实现。如果你还有其他问题或需要更详细的解释，随时告诉我！
评论区
评论列表