9种常用数据结构与算法的C语言代码实现

2023-04-15 19:19| 来源: 网络整理| 查看: 265

动态数组（Dynamic Array）

动态数组是一种可以自动调整大小的数组，具有可变长度。在C语言中，可以使用指针和内存动态分配函数（如malloc和realloc）实现动态数组。

以下是一个简单的动态数组实现示例代码：

#include #include typedef struct { int *arr; int size; int capacity; } dynamic_array; void init(dynamic_array *da, int capacity) { da->arr = (int *)malloc(capacity * sizeof(int)); da->size = 0; da->capacity = capacity; } void append(dynamic_array *da, int value) { if (da->size == da->capacity) { da->capacity *= 2; da->arr = (int *)realloc(da->arr, da->capacity * sizeof(int)); } da->arr[da->size++] = value; } void print(dynamic_array *da) { for (int i = 0; i size; i++) { printf("%d ", da->arr[i]); } printf("\n"); } int main() { dynamic_array da; init(&da, 10); append(&da, 1); append(&da, 2); append(&da, 3); print(&da); free(da.arr); return 0; }

以上代码中，动态数组通过结构体实现，其中arr指向实际存储元素的数组，size表示当前数组中的元素个数，capacity表示数组最多可以容纳的元素个数。init函数用于初始化动态数组，append函数用于在数组末尾添加元素，如果数组容量不足，则动态扩展数组容量。print函数用于打印数组中的元素。在程序结束前，需要释放动态分配的内存。

链表（Linked List）

链表是一种常见的数据结构，它由一组节点组成，每个节点包含一个值和一个指向下一个节点的指针。在C语言中，可以通过定义结构体来实现链表。

以下是一个简单的链表实现示例代码：

#include #include typedef struct node { int data; struct node *next; } node; void insert(node **head, int value) { node *new_node = (node *)malloc(sizeof(node)); new_node->data = value; new_node->next = *head; *head = new_node; } void print(node *head) { while (head) { printf("%d ", head->data); head = head->next; } printf("\n"); } int main() { node *head = NULL; insert(&head, 3); insert(&head, 2); insert(&head, 1); print(head); return 0; }

以上代码中，链表通过定义结构体来实现，其中data表示节点存储的值，next表示指向下一个节点的指针。insert函数用于在链表头部插入节点，print函数用于打印链表中的元素。在程序结束前，需要释放动态分配的内存

栈（Stack）

栈是一种后进先出（LIFO）的数据结构，它可以通过数组或链表实现。在C语言中，可以使用数组实现栈。

以下是一个简单的栈实现示例代码：

#include #define MAX_SIZE 10 typedef struct { int arr[MAX_SIZE]; int top; } stack; void init(stack *s) { s->top = -1; } void push(stack *s, int value) { if (s->top == MAX_SIZE - 1) { printf("Stack Overflow!\n"); return; } s->arr[++s->top] = value; } int pop(stack *s) { if (s->top == -1) { printf("Stack Underflow!\n"); return -1; } return s->arr[s->top--]; } int peek(stack *s) { if (s->top == -1) { printf("Stack Underflow!\n"); return -1; } return s->arr[s->top]; } int main() { stack s; init(&s); push(&s, 1); push(&s, 2); push(&s, 3); printf("%d\n", pop(&s)); printf("%d\n", peek(&s)); return 0; }

以上代码中，栈通过结构体实现，其中arr表示存储栈元素的数组，top表示栈顶元素的下标。init函数用于初始化栈，push函数用于将元素入栈，如果栈已满则报错，pop函数用于将栈顶元素出栈，如果栈为空则报错，peek函数用于查看栈顶元素，但不将其出栈。在程序结束前，不需要显式释放内存。

队列（Queue）

队列是一种先进先出（FIFO）的数据结构，它也可以通过数组或链表实现。在C语言中，可以使用数组实现队列。

以下是一个简单的队列实现示例代码：

#include #define MAX_SIZE 10 typedef struct { int arr[MAX_SIZE]; int front; int rear; } queue; void init(queue *q) { q->front = 0; q->rear = -1; } void enqueue(queue *q, int value) { if (q->rear == MAX_SIZE - 1) { printf("Queue Overflow!\n"); return; } q->arr[++q->rear] = value; } int dequeue(queue *q) { if (q->front > q->rear) { printf("Queue Underflow!\n"); return -1; } return q->arr[q->front++]; } int peek(queue *q) { if (q->front > q->rear) { printf("Queue Underflow!\n"); return -1; } return q->arr[q->front]; } int main() { queue q; init(&q); enqueue(&q, 1); enqueue(&q, 2); enqueue(&q, 3); printf("%d\n", dequeue(&q)); printf("%d\n", peek(&q)); return 0; }

以上代码中，队列通过结构体实现，其中arr表示存储队列元素的数组，front和rear分别表示队列头和队列尾元素的下标。init函数用于初始化队列，enqueue函数用于将元素入队，如果队列已满则报错，dequeue函数用于将队头元素出队，如果队列为空则报错，peek函数用于查看队头元素，但不将其出队。在程序结束前，不需要显式释放内存。

二叉树（Binary Tree）

二叉树是一种树形结构，其中每个节点最多有两个子节点，分别为左子节点和右子节点。在C语言中，可以使用结构体和指针实现二叉树。

以下是一个简单的二叉树实现示例代码：

#include #include typedef struct node { int value; struct node *left; struct node *right; } node; node *create_node(int value) { node *new_node = (node*) malloc(sizeof(node)); new_node->value = value; new_node->left = NULL; new_node->right = NULL; return new_node; } void inorder_traversal(node *root) { if (root == NULL) { return; } inorder_traversal(root->left); printf("%d ", root->value); inorder_traversal(root->right); } int main() { node *root = create_node(1); root->left = create_node(2); root->right = create_node(3); root->left->left = create_node(4); root->left->right = create_node(5); inorder_traversal(root); return 0; }

以上代码中，二叉树通过结构体实现，其中value表示节点的值，left和right分别表示左子节点和右子节点。create_node函数用于创建新节点，并返回指向该节点的指针。inorder_traversal函数用于中序遍历二叉树，即先遍历左子树，再遍历根节点，最后遍历右子树。在程序结束前，需要显式释放二叉树中所有节点的内存。

快速排序（Quick Sort）

快速排序是一种常用的排序算法，其基本思想是通过选定一个基准元素，将待排序序列划分为两个子序列，其中一个子序列的所有元素均小于等于基准元素，另一个子序列的所有元素均大于等于基准元素，然后对两个子序列分别进行递归排序，最终将整个序列排序。

以下是一个简单的快速排序实现示例代码：

#include 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 head[u]; G->head[u] = node; node = (Node*)malloc(sizeof(Node)); node->val = u; node->next = G->head[v]; G->head[v] = node; } // 初始化队列 void init_queue(Queue* Q) { Q->head = Q->tail = 0; } // 入队 void enqueue(Queue* Q, int val) { Q->data[Q->tail++] = val; } // 出队 int dequeue(Queue* Q) { return Q->data[Q->head++]; } // 判断队列是否为空 int is_empty(Queue* Q) { return Q->head == Q->tail; } // 广度优先搜索 void bfs(Graph* G, int start) { Queue Q; int visited[MAX_N] = {0}; // 标记是否已访问过 init_queue(&Q); enqueue(&Q, start); visited[start] = 1; while (!is_empty(&Q)) { int cur = dequeue(&Q); printf("%d ", cur); Node* p = G->head[cur]; while (p != NULL) { if (!visited[p->val]) { visited[p->val] = 1; enqueue(&Q, p->val); } p = p->next; } } } // 主函数 int main() { Graph G; int n, m; // n为节点数，m为边数 scanf("%d%d", &n, &m); init(&G, n); for (int i = 0; i value = value; (*root)->left = NULL; (*root)->right = NULL; } else { if (value value) { insert(&((*root)->left), value); } else { insert(&((*root)->right), value); } } } void inorder_traversal(Node *root) { if (root != NULL) { inorder_traversal(root->left); printf("%d ", root->value); inorder_traversal(root->right); } } int main() { Node *root = NULL; insert(&root, 5); insert(&root, 3); insert(&root, 7); insert(&root, 1); insert(&root, 4); insert(&root, 6); insert(&root, 8); inorder_traversal(root); return 0; }

以上代码中，二叉查找树使用递归实现。insert函数用于向二叉查找树中插入一个节点，若当前节点为空，则将新节点插入；否则，根据当前节点的值和待插入节点的值大小关系，递归调用insert函数。inorder_traversal函数用于中序遍历二叉查找树，即先遍历左子树，然后访问根节点，最后遍历右子树。在程序结束前，需要显式释放内存。

哈希表（Hash Table）

哈希表是一种基于哈希函数实现的数据结构，它具有快速查找和插入的特点。在C语言中，可以使用数组和链表来实现哈希表。

以下是一个简单的哈希表实现示例代码：

#include #include #define TABLE_SIZE 10 typedef struct node { int key; int value; struct node *next; } Node; Node *hash_table[TABLE_SIZE]; int hash(int key) { return key % TABLE_SIZE; } void insert(int key, int value) { int index = hash(key); Node *new_node = (Node*)malloc(sizeof(Node)); new_node->key = key; new_node->value = value; new_node->next = NULL; if (hash_table[index] == NULL) { hash_table[index] = new_node; } else { Node *current = hash_table[index]; while (current->next != NULL) { current = current->next; } current->next = new_node; } } int search(int key) { int index = hash(key); Node *current = hash_table[index]; while (current != NULL) { if (current->key == key) { return current->value; } current = current->next; } return -1; } int main() { insert(1, 10); insert(11, 20); insert(21, 30); printf("%d\n", search(1)); printf("%d\n", search(11)); printf("%d\n", search(21)); return 0; }

以上代码中，哈希表使用链表解决哈希冲突，每个链表节点包含一个键值对。hash函数用于计算键值对应的哈希值，insert函数用于向哈希表中插入一个键值对，若当前位置为空，则直接插入；否则，将新节点插入到链表末尾。search函数用于在哈希表中查找指定键值的值，若存在则返回其值，否则返回-1。

这些常用的C语言数据结构、算法和功能代码示例，涵盖了常见的数据结构和算法，能够满足许多实际应用的需求。需要注意的是，在实际使用时，需要根据具体情况进行优化和改进，以适应不同的应用场景。

【本文地址】

公司简介

联系我们