首页 > 其他分享 >嵌入式开发学习日记——数据结构基础

嵌入式开发学习日记——数据结构基础

时间：2024-10-15 19:48:09浏览次数：3  
标签：链表 队列 日记 queue int 嵌入式 数据结构 数据 stack

数据结构基础

学习内容概述 今天我开始学习数据结构，重点理解了它在编程中的重要性。数据结构是为了高效访问数据而设计的一种数据组织和存储方式。它不仅仅关注数据的存储位置，还关注数据元素之间的关系。

计算机科学家尼古拉斯·沃斯提出了著名的公式：

算法 + 数据结构 = 程序

这说明数据结构与算法是程序设计的核心。数据结构就像战场上的排兵布阵，设计良好的数据结构能让我们在处理问题时事半功倍。

内存的理解 数据结构的基础是对内存的理解。内存由许多存储单元组成，每个单元都有唯一的地址。数据可以保存在连续的内存单元中，也可以保存在分散的单元中。选择哪种方式，取决于我们想如何组织和操作这些数据。

数据结构的逻辑结构 数据的逻辑结构主要描述数据元素之间的逻辑关系，可以分为以下几类：

  • 集合结构：数据元素之间只有属于同一集合的关系。

  • 线性结构：数据元素之间存在一对一的关系，比如数组、链表等。

  • 树形结构：数据元素之间存在一对多的关系，比如家谱、文件系统。

  • 图形结构：数据元素之间存在多对多的关系，比如社交网络。

数据的存储结构 数据的存储结构是逻辑结构在计算机中的实现，可以分为：

  • 顺序存储结构：相邻的数据元素在内存中也相邻，比如数组。

  • 链式存储结构：相邻的数据元素可以在内存中不相邻，用指针链接，比如链表。

  • 索引存储结构：在数据存储之外，有一个索引目录，比如数据库的索引。

  • 散列存储结构：通过计算关键字来确定数据存储地址，比如散列表。

线性结构之数组

学习内容概述 在C语言中，数组是具有相同类型数据元素的集合。数组的特点是访问速度快，因为可以通过下标直接访问指定位置的元素。今天我学到了如何用C语言实现数组的基础操作。

代码示例：数组的定义与操作

#include <stdio.h>  // 引入标准输入输出头文件

int main() {  // 主函数入口
    int arr[5] = {10, 20, 30, 40, 50};  // 定义一个包含5个整数的数组
    // 遍历数组
    for (int i = 0; i < 5; i++) {  // 使用循环遍历数组的每个元素
        printf("arr[%d] = %d\n", i, arr[i]);  // 输出当前元素的值
    }
    return 0;  // 返回0，表示程序正常结束
}

通俗理解 数组就像是一排连续的储物柜，每个储物柜都有一个编号（下标），你可以通过编号快速找到需要的物品（数据）。数组的长度一旦确定就不能改变，这就好比一排储物柜数量固定了，不能再增加新的储物柜。

线性结构之链表

学习内容概述 链表是由一系列结点组成的线性结构，每个结点包含一个数据域和一个指针域。链表的优点是可以动态扩展，不需要预先指定大小，适合频繁插入和删除的场景。

代码示例：链表的定义与操作

#include <stdio.h>  // 引入标准输入输出头文件
#include <stdlib.h>  // 引入标准库头文件，用于动态内存分配

// 定义节点结构体
typedef struct Node {
    int data;  // 数据域，存储节点的数据
    struct Node* next;  // 指针域，指向下一个节点
} Node;

// 插入节点到链表头部
void insert(Node** head, int data) {
    Node* new_node = (Node*)malloc(sizeof(Node));  // 动态分配内存给新节点
    new_node->data = data;  // 设置新节点的数据域
    new_node->next = *head;  // 将新节点的next指向当前的头节点
    *head = new_node;  // 更新头节点指针为新节点
}

// 打印链表
void printList(Node* head) {
    Node* current = head;  // 定义当前节点指针，初始为头节点
    while (current != NULL) {  // 遍历链表直到当前节点为空
        printf("%d -> ", current->data);  // 打印当前节点的数据
        current = current->next;  // 移动到下一个节点
    }
    printf("NULL\n");  // 打印链表结束标志
}

// 释放链表内存
void freeList(Node* head) {
    Node* current = head;  // 定义当前节点指针
    Node* next_node;  // 定义下一个节点指针
    while (current != NULL) {  // 遍历链表直到当前节点为空
        next_node = current->next;  // 保存下一个节点的位置
        free(current);  // 释放当前节点的内存
        current = next_node;  // 移动到下一个节点
    }
}

int main() {
    Node* head = NULL;  // 初始化链表为空
    insert(&head, 10);  // 插入数据10到链表头部
    insert(&head, 20);  // 插入数据20到链表头部
    insert(&head, 30);  // 插入数据30到链表头部
    printList(head);  // 打印链表内容
    freeList(head);  // 释放链表内存，防止内存泄漏
    return 0;  // 返回0，表示程序正常结束
}

通俗理解 链表就像是一串珍珠项链，每颗珍珠（节点）都有一根线（指针）连接到下一颗珍珠。你可以随时在项链中加入或取出一颗珍珠，而不需要重新排列所有珍珠，因此链表非常适合需要频繁添加或删除数据的场景。

线性结构之栈

学习内容概述 今天我还学习了栈这一数据结构。栈是一种只能在表的一端进行插入和删除操作的线性表，其特点是后进先出（LIFO）。栈的应用非常广泛，比如函数调用栈、表达式求值等。

代码示例：栈的实现（基于数组）

#include <stdio.h>  // 引入标准输入输出头文件
#include <stdlib.h>  // 引入标准库头文件

#define MAX 100  // 定义栈的最大容量为100

typedef struct {
    int data[MAX];  // 用数组表示栈的数据存储
    int top;  // 栈顶指针，表示栈中数据的位置
} Stack;

// 初始化栈
void init(Stack* stack) {
    stack->top = -1;  // 初始化栈顶指针为-1，表示栈为空
}

// 判断栈是否为空
int isEmpty(Stack* stack) {
    return stack->top == -1;  // 如果栈顶指针为-1，则栈为空
}

// 判断栈是否为满
int isFull(Stack* stack) {
    return stack->top == MAX - 1;  // 如果栈顶指针等于最大容量减1，则栈为满
}

// 入栈操作
void push(Stack* stack, int value) {
    if (isFull(stack)) {  // 判断栈是否已满
        printf("栈已满，无法入栈\n");  // 输出栈已满信息
    } else {
        stack->data[++stack->top] = value;  // 将数据压入栈顶，并更新栈顶指针
    }
}

// 出栈操作
int pop(Stack* stack) {
    if (isEmpty(stack)) {  // 判断栈是否为空
        printf("栈为空，无法出栈\n");  // 输出栈为空信息
        return -1;  // 返回-1表示栈为空时无法出栈
    } else {
        return stack->data[stack->top--];  // 返回栈顶数据，并更新栈顶指针
    }
}

// 获取栈顶元素
int peek(Stack* stack) {
    if (isEmpty(stack)) {  // 判断栈是否为空
        printf("栈为空，无法获取栈顶元素\n");  // 输出栈为空信息
        return -1;  // 返回-1表示栈为空时无法获取栈顶元素
    } else {
        return stack->data[stack->top];  // 返回栈顶元素
    }
}

int main() {
    Stack stack;  // 定义一个栈变量
    init(&stack);  // 初始化栈
    push(&stack, 10);  // 压入数据10到栈中
    push(&stack, 20);  // 压入数据20到栈中
    push(&stack, 30);  // 压入数据30到栈中
    printf("栈顶元素: %d\n", peek(&stack));  // 获取并打印栈顶元素
    printf("出栈元素: %d\n", pop(&stack));  // 弹出栈顶元素并打印
    printf("出栈元素: %d\n", pop(&stack));  // 弹出栈顶元素并打印
    return 0;  // 返回0，表示程序正常结束
}

通俗理解 栈就像是一摞书，新的书只能放在最上面（压栈），取书也只能从最上面开始拿（弹栈）。这种“后进先出”的特点非常适合处理那些需要按相反顺序进行的操作，比如浏览器的后退功能或者函数的递归调用。

线性结构之队列

学习内容概述 今天我学习了队列这一数据结构。队列是一种只能在一端插入数据，在另一端删除数据的线性表，其特点是先进先出（FIFO）。队列的应用也非常广泛，比如任务调度、数据流处理等。

代码示例：队列的实现（基于数组）

#include <stdio.h>  // 引入标准输入输出头文件
#include <stdlib.h>  // 引入标准库头文件

#define MAX 100  // 定义队列的最大容量为100

typedef struct {
    int data[MAX];  // 用数组表示队列的数据存储
    int front;  // 队列头指针，表示队列中第一个元素的位置
    int rear;  // 队列尾指针，表示队列中最后一个元素的位置
} Queue;

// 初始化队列
void initQueue(Queue* queue) {
    queue->front = 0;  // 初始化队列头指针为0
    queue->rear = 0;  // 初始化队列尾指针为0
}

// 判断队列是否为空
int isEmptyQueue(Queue* queue) {
    return queue->front == queue->rear;  // 如果队列头指针等于队列尾指针，则队列为空
}

// 判断队列是否为满
int isFullQueue(Queue* queue) {
    return (queue->rear + 1) % MAX == queue->front;  // 如果队列尾的下一个位置等于队列头，则队列为满
}

// 入队操作
void enqueue(Queue* queue, int value) {
    if (isFullQueue(queue)) {  // 判断队列是否已满
        printf("队列已满，无法入队\n");  // 输出队列已满信息
    } else {
        queue->data[queue->rear] = value;  // 将数据加入队列尾部
        queue->rear = (queue->rear + 1) % MAX;  // 更新队列尾指针
    }
}

// 出队操作
int dequeue(Queue* queue) {
    if (isEmptyQueue(queue)) {  // 判断队列是否为空
        printf("队列为空，无法出队\n");  // 输出队列为空信息
        return -1;  // 返回-1表示队列为空时无法出队
    } else {
        int value = queue->data[queue->front];  // 获取队列头部数据
        queue->front = (queue->front + 1) % MAX;  // 更新队列头指针
        return value;  // 返回队列头部数据
    }
}

int main() {
    Queue queue;  // 定义一个队列变量
    initQueue(&queue);  // 初始化队列
    enqueue(&queue, 10);  // 入队数据10
    enqueue(&queue, 20);  // 入队数据20
    enqueue(&queue, 30);  // 入队数据30
    printf("出队元素: %d\n", dequeue(&queue));  // 出队并打印元素
    printf("出队元素: %d\n", dequeue(&queue));  // 出队并打印元素
    return 0;  // 返回0，表示程序正常结束
}

通俗理解 队列就像排队买票的人群，新的顾客只能站到队伍的末尾（入队），而服务总是从队伍的最前面开始（出队）。这种“先进先出”的特点非常适合任务调度的场景，比如打印机任务或者操作系统中的进程管理。

心得总结 栈的“后进先出”特性在程序设计中非常有用，尤其是处理递归调用或需要逆序操作的场景。通过实际编写代码，我更好地理解了栈的工作原理，并体验到了栈在内存管理和函数调用中的重要性。对于实现栈，我学到了基于数组的顺序栈和基于链表的链式栈的不同实现方式，分别有各自的优缺点，选择时需要根据具体场景进行权衡。通过学习队列，我理解了队列的先进先出特性，以及它在数据处理和任务调度中的重要性。通过编写队列代码，我更好地理解了如何用数组实现队列，并学会了如何判断队列的空和满情况。对于队列的实现，还可以使用链表来实现一个动态队列，这样就不再受限于数组的固定大小。

标签：链表,队列,日记,queue,int,嵌入式,数据结构,数据,stack
From： https://blog.csdn.net/Find_tim/article/details/142962944

相关文章

  • 数据结构--线性表
    一、线性表的类型定义数据元素类型：线性表由一系列数据元素组成，这些数据元素可以是基本数据类型（如整型、浮点型、字符型等），也可以是复杂的数据类型（如结构体、类、指针等）。存储结构：线性表的存储结构可以是顺序存储或链式存储。顺序存储：使用连续的存储空间来存储线性表的元......
  • 数据结构与算法篇（回溯&递归&分治 - 刷题篇）（目前一天图片上传太多加载不出来）（后续更新）
    目录1.没有重复项数字的全排列（中等）1.1.题目描述1.2解题思路1.3代码实现方法一：递归方法二：非递归版2.有重复项数字的全排列（中等）2.1.题目描述2.2.解题思路2.3.代码实现递归+回溯（推荐使用）3.岛屿数量（中等）3.1.题目描述3.2.解题思路3.3代码实现方法一：dfs......
  • 代码随想录刷题学习日记
    仅为个人记录复盘学习历程，解题思路来自代码随想录代码随想录刷题笔记总结网址:代码随想录替换数字给定一个字符串s，它包含小写字母和数字字符，请编写一个函数，将字符串中的字母字符保持不变，而将每个数字字符替换为number。提供参数：strings主要操作：将数组扩容到所有数字都......
  • 嵌入式片上系统（SoC）最全面试题及参考答案
    目录解释什么是片上系统（SoC）请简述SoC的基本概念和组成部分SoC的主要组成部分有哪些列举常见的SoC架构及其特点SOC与传统微处理器在架构上的主要区别SoC设计流程及关键概念SoC设计流程通常包括哪些步骤？在SoC设计中，什么是硬核、软核和半硬核？SOC设计中IP核......
  • 【日记】可以不用考了，感觉铁过不了（413 字）
    正文可能是上午睡了一整个上午，中午直接睡不着了。不知道为什么，上午特别困，给主管说了一声，去隔壁休息室里开躺。有业务时又出来，脑袋晕晕的。办完又回去睡觉了。中午玩了会儿，打过了劫波，开始探小雷音寺。下午做了一套经济师经济基础知识的卷子，单选题70道，错了34道......
  • 嵌入式编程思想
    1、所有嵌入式程序，都是一个死循环。飞控是最复杂的死循环。操作系统也是？死循环的控制周期、任务调度，如何处理？5ms中断，作为控制周期。任务调度，需要考虑跨周期指令，需要存储为全局或static，每个任务开始还需要初始化清空。【这个就是下面的控制结构。】涉及多周期的控制结构，复......
  • LeetCode刷题日记之回溯算法（四）
    目录前言非递减子序列全排列全排列II总结前言今天是学习回溯算法的第四天，我们继续来一起学习回溯算法蕴含的逻辑处理，希望博主记录的内容能够对大家有所帮助，一起加油吧朋友们！......
  • ArrayList源码分析（底层数据结构，成员变量，构造方法）以及面试题（基于JDK1.8）
    要分析Arraylist,我们首先要从它的底层数据结构实现出发，再结合其底层源码，可能能让读者理解的更加深刻一点。1，底层数据结构（数组）Arraylist底层是基于动态数组实现的。数组是一种使用连续储存空间储存相同数据类型的线性数据结构。面试题1为什么数组索引从0开始不从1开始？分......
  • 嵌入式分享#1：Vim 的高效秘籍
    1前言Vim（ViIMproved）是一个高度可配置的文本编辑器，旨在让用户能够高效地创建和编辑文本。Vim是基于早期的Vi编辑器开发而来的，它在功能上进行了扩展，增加了许多现代化的特性，适合程序员和普通用户使用。2常用命令在日常工作中比较常用的vim命令，整理如下。当然，vim命令还有......
  • 软考14——数据结构
    ◆无向图：图的结点之间连接线是没有箭头的，不分方向。◆有向图：图的结点之间连接线是箭头，区分A到B，和B到A是两条线。◆完全图：无向完全图中，节点两两之间都有连线，n个结点的连线数为(n·1)+(n-2)+.+1=n*(n-1)/2；有向完全图中，节点两两之间都有互通的两个箭头，n个节点的连线数为n*(n-1)◆度......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99