当前位置:首页 » 《资源分享》 » 正文

学懂C语言(四十):C语言 数据结构与算法详解

8 人参与  2024年09月24日 08:41  分类 : 《资源分享》  评论

点击全文阅读


目录

1. 数据结构概述

2. 常见算法

3. C语言实现示例

3.1 数组

3.2 链表

3.3 栈

3.4 队列

3.5 树

3.6 图

3.7 排序与查找

示例:冒泡排序

4. 总结


数据结构与算法是计算机科学的核心内容,C语言作为底层编程语言,广泛用于实现各种数据结构和算法。下面将详细讨论一些常见的数据结构及其相关算法。

1. 数据结构概述

数据结构是特定方式组织和存储数据的集合,以便高效地访问和修改。常见的数据结构包括:

线性数据结构

数组:固定大小的元素集合,支持随机访问。链表:节点组成的集合,每个节点包含数据和指向下一个节点的指针。 单链表:每个节点指向下一个节点。双链表:每个节点指向前一个和后一个节点。循环链表:最后一个节点指向第一个节点。

:后进先出(LIFO)结构。常用于函数调用管理、表达式求值等。

操作:push(入栈)、pop(出栈)、peek(查看栈顶元素)。

队列:先进先出(FIFO)结构。常用于任务调度、缓冲区管理等。

操作:enqueue(入队)、dequeue(出队)、front(查看队首元素)。

二叉树:每个节点最多有两个子节点。二叉搜索树:左子树所有节点小于根节点,右子树所有节点大于根节点。平衡树:如 AVL 树、红黑树,保持树的平衡性以提高查询效率。:完全二叉树,满足堆性质(最大堆或最小堆)。

:由顶点和边组成的结构,表示对象之间的关系。

表示方式:邻接矩阵、邻接表。

哈希表:通过哈希函数将键映射到数组索引,提供快速的查找和插入。

2. 常见算法

算法是对解决特定问题的步骤和逻辑的描述。常见算法包括:

排序算法

冒泡排序:重复遍历数组,比较相邻元素并交换,直到排序完成。选择排序:每次选择最小的元素,将其放到已排序部分的末尾。插入排序:将数组分为已排序和未排序部分,逐个插入未排序元素。快速排序:选择基准元素,将数组分为小于和大于基准的两部分,递归排序。归并排序:分治法将数组分为两部分,分别排序后合并。

查找算法

线性查找:逐个比较,找到目标元素。二分查找:在已排序数组中,通过不断将搜索范围减半来查找目标元素。

图算法

深度优先搜索(DFS):从一个节点出发,尽可能深入到每个分支,再回溯。广度优先搜索(BFS):从一个节点出发,先访问所有相邻节点,再从这些节点访问它们的邻居。Dijkstra 算法:求解单源最短路径的贪心算法。A 算法*:启发式搜索算法,常用于路径寻找。

动态规划

解决最优子结构问题,通过保存子问题的结果来减少计算。常见问题:斐波那契数列、背包问题、最长公共子序列等。

3. C语言实现示例

3.1 数组

数组是一种线性数据结构,支持随机访问。

示例:数组求和

#include <stdio.h>int main() {    int arr[] = {1, 2, 3, 4, 5};    int sum = 0;    int n = sizeof(arr) / sizeof(arr[0]);    for (int i = 0; i < n; i++) {        sum += arr[i]; // 累加    }    printf("数组元素的和是: %d\n", sum);    return 0;}
3.2 链表

链表是一种动态数据结构,由节点组成,每个节点包含数据和指向下一个节点的指针。

示例:单链表的基本操作

#include <stdio.h>#include <stdlib.h>// 节点结构struct Node {    int data;    struct Node* next;};// 创建新节点struct Node* createNode(int data) {    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));    newNode->data = data;    newNode->next = NULL;    return newNode;}// 打印链表void printList(struct Node* head) {    struct Node* temp = head;    while (temp != NULL) {        printf("%d -> ", temp->data);        temp = temp->next;    }    printf("NULL\n");}// 插入节点void insertAtEnd(struct Node** head, int data) {    struct Node* newNode = createNode(data);    if (*head == NULL) {        *head = newNode;        return;    }    struct Node* temp = *head;    while (temp->next != NULL) {        temp = temp->next;    }    temp->next = newNode;}int main() {    struct Node* head = NULL;    insertAtEnd(&head, 1);    insertAtEnd(&head, 2);    insertAtEnd(&head, 3);    printList(head); // 输出: 1 -> 2 -> 3 -> NULL    return 0;}
3.3 

栈是一种后进先出(LIFO)结构,常用于函数调用管理。

示例:栈的实现

#include <stdio.h>#include <stdlib.h>#define MAX 100struct Stack {    int top;    int arr[MAX];};// 初始化栈struct Stack* createStack() {    struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));    stack->top = -1; // 栈为空    return stack;}// 判断栈是否为空int isEmpty(struct Stack* stack) {    return stack->top == -1;}// 入栈void push(struct Stack* stack, int item) {    if (stack->top == MAX - 1) {        printf("栈溢出\n");        return;    }    stack->arr[++stack->top] = item;}// 出栈int pop(struct Stack* stack) {    if (isEmpty(stack)) {        printf("栈为空\n");        return -1;    }    return stack->arr[stack->top--];}// 查看栈顶元素int peek(struct Stack* stack) {    if (isEmpty(stack)) {        printf("栈为空\n");        return -1;    }    return stack->arr[stack->top];}int main() {    struct Stack* stack = createStack();    push(stack, 1);    push(stack, 2);    push(stack, 3);    printf("栈顶元素是: %d\n", peek(stack)); // 输出: 3    printf("出栈元素: %d\n", pop(stack)); // 输出: 3    printf("栈顶元素是: %d\n", peek(stack)); // 输出: 2    return 0;}
3.4 队列

队列是一种先进先出(FIFO)结构,常用于任务调度和缓冲区管理。

示例:队列的实现

#include <stdio.h>#include <stdlib.h>#define MAX 100struct Queue {    int front, rear;    int arr[MAX];};// 初始化队列struct Queue* createQueue() {    struct Queue* queue = (struct Queue*)malloc(sizeof(struct Queue));    queue->front = queue->rear = -1; // 队列为空    return queue;}// 判断队列是否为空int isEmpty(struct Queue* queue) {    return queue->front == -1;}// 入队void enqueue(struct Queue* queue, int item) {    if (queue->rear == MAX - 1) {        printf("队列满\n");        return;    }    if (isEmpty(queue)) {        queue->front = 0;    }    queue->arr[++queue->rear] = item;}// 出队int dequeue(struct Queue* queue) {    if (isEmpty(queue)) {        printf("队列为空\n");        return -1;    }    int item = queue->arr[queue->front];    if (queue->front >= queue->rear) {        queue->front = queue->rear = -1; // 队列空了    } else {        queue->front++;    }    return item;}int main() {    struct Queue* queue = createQueue();    enqueue(queue, 1);    enqueue(queue, 2);    enqueue(queue, 3);        printf("出队元素: %d\n", dequeue(queue)); // 输出: 1    printf("出队元素: %d\n", dequeue(queue)); // 输出: 2    return 0;}
3.5 

树是一种分层数据结构,常用于表示层级关系。

示例:二叉树的遍历

#include <stdio.h>#include <stdlib.h>struct Node {    int data;    struct Node* left;    struct Node* right;};// 创建新节点struct Node* createNode(int data) {    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));    newNode->data = data;    newNode->left = newNode->right = NULL;    return newNode;}// 先序遍历void preOrder(struct Node* root) {    if (root != NULL) {        printf("%d ", root->data);        preOrder(root->left);        preOrder(root->right);    }}// 中序遍历void inOrder(struct Node* root) {    if (root != NULL) {        inOrder(root->left);        printf("%d ", root->data);        inOrder(root->right);    }}// 后序遍历void postOrder(struct Node* root) {    if (root != NULL) {        postOrder(root->left);        postOrder(root->right);        printf("%d ", root->data);    }}int main() {    struct Node* root = createNode(1);    root->left = createNode(2);    root->right = createNode(3);    root->left->left = createNode(4);    root->left->right = createNode(5);    printf("先序遍历: ");    preOrder(root); // 输出: 1 2 4 5 3    printf("\n");    printf("中序遍历: ");    inOrder(root); // 输出: 4 2 5 1 3    printf("\n");    printf("后序遍历: ");    postOrder(root); // 输出: 4 5 2 3 1    printf("\n");    return 0;}
3.6 

图是由顶点和边组成的结构,表示对象之间的关系。

示例:邻接表表示的图

#include <stdio.h>#include <stdlib.h>struct Node {    int dest;    struct Node* next;};struct Graph {    int vertices;    struct Node** adjLists;};// 创建图struct Graph* createGraph(int vertices) {    struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));    graph->vertices = 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 = (struct Node*)malloc(sizeof(struct Node));    newNode->dest = dest;    newNode->next = graph->adjLists[src];    graph->adjLists[src] = newNode;}// 打印图void printGraph(struct Graph* graph) {    for (int v = 0; v < graph->vertices; v++) {        struct Node* temp = graph->adjLists[v];        printf("\n 对于顶点 %d: ", v);        while (temp) {            printf("%d -> ", temp->dest);            temp = temp->next;        }        printf("NULL");    }}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;}
3.7 排序与查找

排序与查找是常见的算法问题,涉及如何组织数据以便于访问。

示例:快速排序

#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; 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 n = sizeof(arr) / sizeof(arr[0]);    quickSort(arr, 0, n - 1);    printf("排序后的数组: \n");    for (int i = 0; i < n; i++) {        printf("%d ", arr[i]);    }    return 0;}
示例:冒泡排序
#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]) {                // 交换 arr[j] 和 arr[j+1]                int temp = arr[j];                arr[j] = arr[j + 1];                arr[j + 1] = temp;            }        }    }}int main() {    int arr[] = {64, 34, 25, 12, 22, 11, 90};    int n = sizeof(arr) / sizeof(arr[0]);    bubbleSort(arr, n);    printf("排序后的数组: \n");    for (int i = 0; i < n; i++) {        printf("%d ", arr[i]);    }    return 0;}

4. 总结

通过以上实例,可以更好地理解 C 语言中的数据结构与算法。这些结构与算法是编程的基石,掌握它们对于解决复杂问题至关重要。建议通过实际编程练习、参加算法竞赛等方式,不断提升自己的能力和经验。


点击全文阅读


本文链接:http://zhangshiyu.com/post/163762.html

<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

关于我们 | 我要投稿 | 免责申明

Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1