当前位置： 首页 > news >正文

【C语言进阶教程】数据结构与算法（4.栈 5.队列 6.树）

news 2025/1/19 17:02:34

第四章 栈 (Stack)

4.1 栈的基本概念

栈是一种重要的数据结构，其特点是后进先出（LIFO, Last In First Out）。在栈中，最新添加的元素会最先被移除。栈在计算机科学中有着广泛的应用，例如在函数调用、表达式求值和递归处理中。

  • 典型特性：
    • 后进先出：栈中的元素按照逆序进行操作。
    • 单端操作：栈的增删改查都发生在栈顶的一端。

栈的基本操作通常包括压栈（push）、弹栈（pop）、查看栈顶元素（peek）以及判断栈是否为空。

4.2 基于数组的栈

基于数组实现的栈使用数组来存储栈中的元素，操作简单且访问速度快。在C语言中，可以使用动态数组来避免数组大小固定的限制。

  • 实现要点：
    • 定义一个数组以及一个变量来表示栈顶位置。
    • 压栈操作是将元素置于数组的下一空闲位置，然后栈顶指针增量。
    • 弹栈操作是将栈顶指针减量后返回栈顶元素。
#include <stdio.h>
#include <stdlib.h>#define MAX_SIZE 100typedef struct {int data[MAX_SIZE];int top;
} Stack;// 初始化栈
void initStack(Stack *s) {s->top = -1;
}// 判断栈是否为空
int isEmpty(Stack *s) {return s->top == -1;
}// 压栈操作
int push(Stack *s, int value) {if (s->top == MAX_SIZE - 1) {printf("栈满\n");return -1;}s->data[++(s->top)] = value;return 0;
}// 弹栈操作
int pop(Stack *s) {if (isEmpty(s)) {printf("栈空\n");return -1;}return s->data[(s->top)--];
}// 查看栈顶元素
int peek(Stack *s) {if (isEmpty(s)) {printf("栈空\n");return -1;}return s->data[s->top];
}

4.3 基于链表的栈

基于链表的栈解决了数组实现中栈大小固定的问题。使用链表节点来存储每个元素，可以动态调整栈的大小。

  • 实现要点：
    • 每个元素都是链表中的一个节点。
    • 压栈将新节点插入链表头，弹栈删除链表头节点。
#include <stdio.h>
#include <stdlib.h>// 定义节点
typedef struct Node {int data;struct Node *next;
} Node;// 定义栈
typedef struct {Node *top;
} Stack;// 初始化栈
void initStack(Stack *s) {s->top = NULL;
}// 判断栈是否为空
int isEmpty(Stack *s) {return s->top == NULL;
}// 压栈操作
void push(Stack *s, int value) {Node *newNode = (Node *)malloc(sizeof(Node));newNode->data = value;newNode->next = s->top;s->top = newNode;
}// 弹栈操作
int pop(Stack *s) {if (isEmpty(s)) {printf("栈空\n");return -1;}Node *temp = s->top;int value = temp->data;s->top = temp->next;free(temp);return value;
}// 查看栈顶元素
int peek(Stack *s) {if (isEmpty(s)) {printf("栈空\n");return -1;}return s->top->data;
}

4.4 常见操作 (压栈、弹栈、查栈顶、判空)

了解栈的所有基本操作是实现栈的关键。以下是这些操作的简单描述：

  • 压栈 (Push)：将元素添加到栈顶。
  • 弹栈 (Pop)：移除并返回栈顶元素。
  • 查看栈顶元素 (Peek)：返回栈顶元素但不移除。
  • 判空 (IsEmpty)：检查栈是否为空。

这些操作在上面的代码实现中已经详细介绍。

4.5 栈在递归中的应用

栈在递归函数的执行过程中具有重要作用。每当一次递归调用发生时，函数的参数、局部变量及返回地址都会被压入系统栈。当递归过程到达终点并逐步返回时，系统栈中的信息将被依次弹出。

递归问题的求解可以通过使用栈来模拟递归过程，这有助于理解递归的实现机制。例如，斐波那契数列和阶乘等问题通常利用递归解决，我们可以用栈来迭代方式实现同一结果。

#include <stdio.h>// 递归实现阶乘
int factorial_recursive(int n) {if (n == 0) return 1;return n * factorial_recursive(n - 1);
}// 使用栈模拟递归实现阶乘
int factorial_iterative(int n) {Stack s;initStack(&s);push(&s, n);int result = 1;while (!isEmpty(&s)) {int value = pop(&s);result *= value;if (value > 1) {push(&s, value - 1);}}return result;
}int main() {int number = 5;printf("Recursive factorial of %d is %d\n", number, factorial_recursive(number));printf("Iterative factorial of %d is %d\n", number, factorial_iterative(number));return 0;
}

通过对比递归和栈的实现方法，您将能更好地理解函数调用的底层过程以及如何在没有递归支持的语言中实现递归算法。

5. 队列 (Queue)

队列是一种先进先出（FIFO，First In First Out）的线性数据结构，适合将数据按需进行顺序处理。与栈不同，队列在尾部（称为队尾）进行入队操作，在头部（称为队头）进行出队操作。

5.1 队列的基本概念

  • 基本操作：

    • 入队（Enqueue）：将元素添加到队尾。
    • 出队（Dequeue）：从队头移除元素。
    • 判空：判断队列是否为空。
    • 判满（通常用于固定大小的实现）：判断队列是否已达到最大容量。
    • 查看队头元素：获取队头元素但不移除。

  • 应用场景：

    • 任务调度：用于操作系统中的任务调度。
    • 广度优先搜索（BFS）：在图的遍历中使用。
    • 带宽管理：在网络流量管理中控制数据包的发送顺序。
5.2 线性队列

线性队列可以通过两种方式实现，数组和链表。

5.2.1 基于数组的队列

基于数组实现队列结构是初学者容易理解的一个方法。数组实现简单高效，但有固定长度限制，需要维护两个指针或索引：队头和队尾。

#include <stdio.h>
#define MAX 100typedef struct {int data[MAX];int front; // 队头int rear;  // 队尾
} Queue;// 初始化队列
void initQueue(Queue *q) {q->front = 0;q->rear = 0;
}// 入队操作
int enqueue(Queue *q, int value) {if (q->rear < MAX) {q->data[q->rear++] = value;return 1; // 成功入队}return 0; // 队列已满
}// 出队操作
int dequeue(Queue *q, int *value) {if (q->front < q->rear) {*value = q->data[q->front++];return 1; // 成功出队}return 0; // 队列为空
}int main() {Queue q;initQueue(&q);enqueue(&q, 10);enqueue(&q, 20);int value;if (dequeue(&q, &value)) {printf("Dequeued: %d\n", value);}return 0;
}

这个实现无法重用已移除元素的空间。循环队列可以解决这个问题。

5.2.2 基于链表的队列

链表实现没有固定大小限制，可以动态调整其长度。

#include <stdio.h>
#include <stdlib.h>// 队列节点
typedef struct Node {int data;struct Node *next;
} Node;// 队列结构
typedef struct {Node *front;Node *rear;
} Queue;// 初始化队列
void initQueue(Queue *q) {q->front = q->rear = NULL;
}// 入队操作
void enqueue(Queue *q, int value) {Node *newNode = (Node *)malloc(sizeof(Node));if(newNode == NULL) return; // 内存分配失败newNode->data = value;newNode->next = NULL;if (q->rear == NULL) {q->front = q->rear = newNode;} else {q->rear->next = newNode;q->rear = newNode;}
}// 出队操作
int dequeue(Queue *q, int *value) {if (q->front == NULL) return 0; // 队列为空Node *temp = q->front;*value = temp->data;q->front = q->front->next;if (q->front == NULL) {q->rear = NULL;}free(temp);return 1;
}int main() {Queue q;initQueue(&q);enqueue(&q, 10);enqueue(&q, 20);int value;if (dequeue(&q, &value)) {printf("Dequeued: %d\n", value);}return 0;
}
5.3 循环队列

循环队列通过将数组的最后一个位置与第一个位置连接成环来实现，利用空间复用。此方法需要使用(rear + 1) % MAX来判断队满。

5.4 双端队列 (Deque)

双端队列允许在队列的任一端进行插入和删除。它是栈和队列功能的结合体，既可以从一端执行栈的操作，也可以从两端进行队列的操作。

5.5 优先队列 (Priority Queue)

在优先队列中，元素按照其优先级进行排序，出队操作总是优先级最高的元素。可以通过堆实现优先队列，保持插入和删除操作的高效性。

6. 树 (Tree)

树是一种重要的非线性数据结构，用于表示具有层次结构的数据。树结构在计算机科学中广泛应用，下面我们将详细介绍树的基础概念、常见类型及其操作。

6.1 树的基本概念和术语
  • 节点 (Node)：树的基本组成元素，每个节点包含数据以及指向其子节点的链接。
  • 根节点 (Root)：树的顶层节点，没有父节点，一个树只有一个根节点。
  • 子节点 (Child)：一个节点的直接后继节点。
  • 父节点 (Parent)：具有子节点的节点称为子节点的父节点。
  • 叶节点 (Leaf)：没有子节点的节点。
  • 深度 (Depth)：节点到跟节点的边数。
  • 高度 (Height)：节点到叶节点的最长路径上的边数。
  • 子树 (Subtree)：某个节点及其所有后代节点构成的树。
6.2 二叉树

二叉树是一种特殊的树结构，每个节点最多有两个子节点，通常称为左子节点和右子节点。

6.2.1 二叉树的创建与基本操作

二叉树的基本操作包括插入、删除、查找等，需要通过指针和递归操作进行。

#include <stdio.h>
#include <stdlib.h>// 定义二叉树节点结构
typedef struct TreeNode {int data;struct TreeNode* left;struct TreeNode* right;
} TreeNode;// 创建新节点
TreeNode* createNode(int data) {TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));if (!newNode) {printf("内存分配失败\n");return NULL;}newNode->data = data;newNode->left = newNode->right = NULL;return newNode;
}// 插入节点
TreeNode* insertNode(TreeNode* root, int data) {if (root == NULL) {root = createNode(data);return root;}if (data < root->data)root->left = insertNode(root->left, data);elseroot->right = insertNode(root->right, data);return root;
}// 查找节点
TreeNode* search(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);
}
6.2.2 二叉搜索树 (BST)

二叉搜索树是一种有序二叉树，其中每个节点比其左子树的所有节点大，比其右子树的所有节点小。这一属性使得查找、插入和删除操作高效。

TreeNode* insertBST(TreeNode* root, int data) {if (root == NULL)return createNode(data);if (data < root->data)root->left = insertBST(root->left, data);else if (data > root->data)root->right = insertBST(root->right, data);return root;
}
6.2.3 平衡二叉树 (AVL 树)

AVL树是一种自平衡二叉搜索树。在插入和删除操作后，AVL树通过旋转操作保持树的平衡，即任一节点的左右子树的高度差不超过1。

6.3 常见的树遍历算法 (前序，中序，后序，层序)
  • 前序遍历 (Pre-order)：访问根节点，遍历左子树，遍历右子树。
  • 中序遍历 (In-order)：遍历左子树，访问根节点，遍历右子树。
  • 后序遍历 (Post-order)：遍历左子树，遍历右子树，访问根节点。
  • 层序遍历 (Level-order)：按层次逐层访问节点，通常使用队列实现。
void preOrder(TreeNode* root) {if (root != NULL) {printf("%d ", root->data);preOrder(root->left);preOrder(root->right);}
}void inOrder(TreeNode* root) {if (root != NULL) {inOrder(root->left);printf("%d ", root->data);inOrder(root->right);}
}void postOrder(TreeNode* root) {if (root != NULL) {postOrder(root->left);postOrder(root->right);printf("%d ", root->data);}
}
6.4 堆 (Heap)

堆是一种特殊的树状数据结构，可以高效地支持优先队列操作。

6.4.1 最小堆与最大堆
  • 最小堆：每个节点的值小于等于其子节点的值。根节点为最小值。
  • 最大堆：每个节点的值大于等于其子节点的值。根节点为最大值。
6.4.2 堆排序

堆排序是一种基于比较的数据排序算法，它构建了堆结构并将最大或最小元素移至堆顶。

void heapify(int arr[], int n, int i) {int largest = i;int left = 2 * i + 1;int right = 2 * i + 2;if (left < n && arr[left] > arr[largest])largest = left;if (right < n && arr[right] > arr[largest])largest = right;if (largest != i) {int temp = arr[i];arr[i] = arr[largest];arr[largest] = temp;heapify(arr, n, largest);}
}void heapSort(int arr[], int n) {for (int i = n / 2 - 1; i >= 0; i--)heapify(arr, n, i);for (int i = n - 1; i >= 0; i--) {int temp = arr[0];arr[0] = arr[i];arr[i] = temp;heapify(arr, i, 0);}
}

通过以上内容，您可以掌握树的基本概念、操作方法及其在不同应用场景中的实现。树结构在许多应用程序中扮演着重要角色，如数据库索引、文件系统、网络路由等。继续深入理解并实践是提高技能的好方法。


http://www.mrgr.cn/news/46622.html

相关文章：

  • springboot 集成javaFx 两个面板之间如何进行跳转
  • 【微服务justsoso-cloud系列】目录
  • 你喜欢用什么编辑器?
  • web-app uniapp监测屏幕大小的变化对数组一行展示数据作相应处理
  • llama.cpp 模型可视化工具 GGUF Visualizer
  • 追溯 RFC817：网络性能优化的先驱智慧与启示
  • 【Tourism】Zhengzhou
  • SQL第15课挑战题
  • The Android SDK location cannot be at the filesystem root
  • 吴恩达深度学习笔记：卷积神经网络（Foundations of Convolutional Neural Networks）2.7-2.8
  • 实现多线程方法有哪些
  • 如何配置 Nginx：从入门到进阶
  • AcWing 802. 区间和（离散化算法，python）
  • 先进封装技术 Part03---重布线层（RDL）的科普
  • 腾讯云SDK项目管理
  • Java 运算符（详细介绍）
  • 来来来！聊聊Secure Debug~
  • springboot 项目使用 gitlab 的 API
  • 数据结构——排序（选择排序）
  • springboot+vue前后端分离-使用腾讯云服务器部署网站
  • 指针 （八）例题深度解析
  • 【093】基于SpringBoot+Vue实现的精品水果线上销售系统
  • Python 入门教程（6）函数 | 6.1、函数定义
  • ICE/TURN/STUN/Coturn服务器搭建
  • 多线程—— Thread 类及常见用法（详解）
  • 【测开】接口路由分类与技巧，GraphQL，WebSocket，RESTFUL方法（PUT、PATCH、OPTIONS、HEAD、TRACE）