JeffersonZU-CSDN博客

原创【数据结构】3-4 队列的应用

在操作系统中，队列是一种重要的数据结构，广泛应用于资源管理和任务调度。例如，当多个进程竞争有限的系统资源时，采用FCFS（先来先服务）策略，可以通过队列实现CPU资源的公平分配。此外，队列还用于打印数据缓冲区，确保打印任务按顺序执行。在树和图的应用中，队列也发挥着关键作用，如用于树的层次遍历和图的广度优先遍历，帮助系统地访问和处理节点数据。这些应用展示了队列在计算机科学中的多样性和重要性。

2025-05-20 16:27:38 94

栈在函数调用中扮演着重要角色，特别是在递归调用时。函数调用的特点是后进先出（LIFO），即最后被调用的函数最先执行结束。在函数调用过程中，栈用于存储返回地址、实参和局部变量。递归调用时，每次进入新的一层递归，相关信息被压入栈顶；退出时则弹出。然而，递归的效率较低，可能导致栈溢出，且常包含重复计算。因此，可以通过自定义栈将递归算法转换为非递归算法。例如，计算阶乘和裴波那契数列的递归算法，都可以通过栈结构实现非递归版本，从而提高效率和避免栈溢出问题。

2025-05-20 16:23:52 151

原创【数据结构】3-3-2 栈的应用--表达式求值

本文详细介绍了数据结构中关于表达式的三种形式：中缀、前缀和后缀表达式，并阐述了它们之间的转换方法及计算过程。中缀表达式是常见的运算符位于操作数之间的形式，如a+b；前缀表达式将运算符置于操作数之前，如+ab；后缀表达式则将运算符放在操作数之后，如ab+。文章还详细描述了如何通过栈结构将中缀表达式转换为前缀或后缀表达式，并利用栈进行表达式的计算。此外，还提供了具体的计算步骤和示例，帮助理解如何在实际操作中应用这些方法。

2025-05-20 16:17:35 345

原创【数据结构】3-3-1 栈的应用--括号匹配

使用栈实现括号匹配是一种常见的数据结构应用。算法通过扫描字符，遇到左括号时将其入栈，遇到右括号时弹出栈顶元素并检查是否匹配。匹配失败的情况包括左括号单身、右括号单身或左右括号不匹配。最后，检查栈中是否还有未匹配的括号。算法代码展示了如何初始化栈、扫描表达式并处理括号匹配的逻辑。测试代码验证了算法的正确性，通过检查不同表达式的括号匹配情况，输出相应的结果。这种方法利用了栈的“后进先出”特性，确保最后出现的左括号最先被匹配，从而有效解决括号匹配问题。

2025-05-20 14:56:30 249

原创【数据结构】3-2-4 双端队列

双端队列是一种允许从两端进行插入和删除操作的线性表。如果仅使用一端的插入和删除操作，其功能等同于栈。双端队列有两种受限形式：输入受限的双端队列，只允许从一端插入但可以从两端删除；输出受限的双端队列，允许从两端插入但只能从一端删除。判断输出序列的合法性时，需考虑这些操作限制，确保序列符合双端队列的操作规则。

2025-05-20 14:29:18 66

原创【数据结构】3-2-3 队列的链式存储

链式队列是一种使用链表实现的队列结构，其核心在于通过节点指针连接各个元素。链式队列的节点结构包含数据域和指向下一个节点的指针。队列结构体则包含指向队头和队尾的指针。链式队列的初始化分为带头节点和不带头节点两种方式，带头节点的初始化需要为头节点分配空间，并将队头和队尾指针指向头节点；不带头节点的初始化则直接将队头和队尾指针置空。入队操作通过创建新节点并将其插入队尾实现，出队操作则通过移除队头节点并更新指针完成。判空操作通过检查队头和队尾指针是否指向同一节点（带头节点）或队头指针是否为空（不带头节点）来判断队列

2025-05-19 16:16:33 593

原创【数据结构】3-2-2 队列的顺序存储

顺序队列是一种通过静态数组实现的队列结构，使用队头（front）和队尾（rear）指针来管理队列元素。循环顺序队列通过牺牲一个存储单元来避免队满和队空条件的混淆。基本操作包括初始化队列、判断队列是否为空、入队、出队和获取队头元素。判断队满和队空的方法有多种，如通过指针位置、队列元素个数、或增加变量（如size或tag）来记录队列状态。这些方法确保了队列操作的正确性和高效性。

2025-05-19 16:03:57 652

原创【数据结构】3-2-1 队列的基本概念

队列是一种遵循先进先出（FIFO）原则的线性表，允许在一端插入元素，在另一端删除元素。其基本操作包括初始化队列（InitQueue）、销毁队列（DestroyQueue）、入队（EnQueue）、出队（DeQueue）和读取队头元素（GetHead）。此外，常用操作还包括判断队列是否为空（QueueEmpty）。这些操作共同构成了队列的基本功能，使其在数据处理和任务调度中具有广泛应用。

2025-05-19 15:54:54 175

原创【数据结构】3-1-3 栈的链式存储

链栈是一种用链表实现的栈结构，其基本操作包括初始化、入栈、出栈、获取栈顶元素、判断栈是否为空以及输出栈中所有元素。链栈的结构体由数据域和指向下一个节点的指针组成。初始化时，分配一个头节点并将其指针置为空。入栈操作通过分配新节点并将其插入链表头部实现，出栈操作则通过删除链表头部节点并释放其空间完成。获取栈顶元素和判断栈是否为空的操作分别通过检查链表头部节点和头节点的指针实现。输出栈中所有元素的操作通过遍历链表并打印每个节点的数据域完成。测试代码展示了链栈的基本操作流程，包括初始化、入栈、出栈、获取栈顶元素、判

2025-05-19 15:50:06 535

原创【数据结构】3-1-2 栈的顺序存储

顺序栈是一种采用顺序存储方式的栈，通过静态数组实现，为每个元素分配连续的存储空间，并使用栈顶指针指向栈顶元素。其基本操作包括初始化、判断栈是否为空、入栈、出栈和读取栈顶元素。初始化时，栈顶指针通常设置为-1或0，表示栈为空。入栈操作需检查栈是否已满，若未满则将新元素压入栈顶；出栈操作需检查栈是否为空，若不为空则将栈顶元素弹出。读取栈顶元素时，同样需检查栈是否为空。此外，共享顺序栈允许两个栈共享同一片存储空间，一个栈的栈底在存储空间的起始位置，另一个栈的栈底在存储空间的末尾位置。共享栈的栈满条件是两个栈的栈顶

2025-05-19 15:43:29 409

原创【数据结构】3-1-1 栈的基本概念

栈是一种遵循后进先出（LIFO）原则的线性数据结构，只允许在一端（栈顶）进行插入（进栈）和删除（出栈）操作。栈的基本操作包括初始化栈（InitStack）、销毁栈（DestroyStack）、进栈（Push）、出栈（Pop）、读取栈顶元素（GetTop）和判断栈是否为空（StackEmpty）。对于n个不同元素的进栈顺序，其出栈序列的排列个数遵循特定的组合数学规律，通常与卡特兰数相关。栈在计算机科学中广泛应用于函数调用、表达式求值、括号匹配等场景。

2025-05-19 15:37:13 102

原创【数据结构】2-7 顺序表和链表的比较

顺序表和链表是两种常见的线性表结构，分别采用顺序存储和链式存储。顺序表支持随机存取，存储密度高，但需要大片连续空间，扩展和容量调整不便。链表则通过离散的小空间分配，扩展和容量调整方便，但不支持随机存取，存储密度较低。在基本操作方面，顺序表在插入和删除时需要移动元素，时间复杂度为O(n)，而链表只需修改指针，时间复杂度同样为O(n)，但主要开销在于查找目标元素。查找操作中，顺序表按位查找为O(1)，按值查找为O(n)；链表按位和按值查找均为O(n)。适用场景上，链表适合表长难以预估且频繁增删元素的场景，而顺序

2025-05-19 15:27:04 92

原创【数据结构】2-6 静态链表

静态链表是一种用数组实现的链表结构，通过分配连续的内存空间来存储节点。其优点在于增删操作无需大量移动元素，但缺点是不能随机存取，且容量固定。静态链表适用于不支持指针的低级语言或数据元素数量固定的场景，如操作系统的文件分配表。静态链表的基本操作包括初始化、查找、插入和删除。初始化时，将头节点的next设为-1，其他节点设为-2表示空闲。查找操作从头节点开始遍历，插入和删除操作则需找到前驱节点并修改相关节点的next值。静态链表的实现通过数组下标模拟指针，适用于特定场景下的链表操作。

2025-05-19 15:21:02 221

原创【数据结构】2-5 循环链表

循环单链表和循环双链表是两种重要的数据结构。循环单链表在单链表的基础上，将表尾指针指向表头，形成一个环，使得从一个节点出发可以访问到所有其他节点。其基本操作包括初始化、判断是否为空、判断节点是否为尾节点等，时间复杂度为O(n)或O(1)。循环双链表则在双链表的基础上，将表头的前驱指向表尾，表尾的后继指向表头，形成双向环。其基本操作包括初始化、判断是否为空、判断节点是否为尾节点、插入和删除节点等。循环双链表的插入和删除操作需要调整前驱和后继指针，确保链表的完整性。这两种数据结构在需要循环访问的场景中具有较高的

2025-05-19 15:06:13 713

原创【数据结构】2-4 双链表

双链表在单链表的基础上增加了指向前驱节点的指针，其节点结构包括数据域、前驱指针和后驱指针。双链表的初始化涉及创建头节点并设置其前驱和后驱指针为NULL。插入操作在指定节点后插入新节点，需调整新节点及其前后节点的指针。删除操作移除指定节点的后继节点，并调整相关指针及释放节点空间。双链表的遍历操作，包括按位查找和按值查找，由于不能随机存取，必须从头节点开始顺序访问，时间复杂度为O(n)。这些操作共同构成了双链表的基本功能，使其在数据结构中具有灵活性和高效性。

2025-05-19 14:58:31 573

原创【数据结构】1-1数据结构的基本概念

数据结构是计算机科学中的核心概念，涉及数据元素、数据项、数据对象和数据类型等基本概念。数据结构的三要素包括逻辑结构、存储结构和数据的运算。逻辑结构描述数据元素之间的关系，如集合、线性结构、树形结构和图结构。存储结构涉及数据在计算机中的物理存储方式，包括顺序存储、链式存储、索引存储和散列存储。数据的运算则包括对数据进行的各种操作，如插入、删除和查找等。理解这些基本概念和结构对于设计和实现高效的算法至关重要。

2025-05-18 21:33:25 147

原创【数据结构】1-2 算法的基本概念

数据结构与算法是计算机科学中的核心概念，程序由数据结构和算法组成。数据结构用于描述和存储现实世界的问题，而算法则用于高效处理这些数据以解决实际问题。算法具有五个基本特性：有穷性、确定性、可行性、输入和输出。设计算法时应追求正确性、可读性、健壮性以及高效率和低存储量需求。正确性确保算法能准确解决问题，可读性帮助理解算法，健壮性使算法能处理非法输入，而高效率和低存储量则优化了算法的性能。

2025-05-18 21:33:11 138

原创【数据结构】1-3 算法的时间复杂度

文章主要介绍了数据结构与算法中的时间复杂度概念及其计算方法。时间复杂度用于预估算法时间开销与问题规模的关系，通常用大O记号表示。计算规则包括加法规则（保留最高阶项）、乘法规则（保留所有项）以及常见时间复杂度的比较（如O(1) < O(log2n) < O(n)等）。文章还通过示例展示了如何计算算法的时间复杂度，并介绍了最坏、平均和最好时间复杂度的概念。这些知识点对于理解和优化算法性能至关重要。

2025-05-18 21:32:53 274

原创【数据结构】2-3-4 单链表的建立

尾插法和头插法是建立单链表的两种常见方法。尾插法将新节点插入链表尾部，通过维护一个指向尾节点的指针实现。具体步骤包括：创建头节点，为新节点分配空间并赋值，将尾节点的指针指向新节点，最后将新节点设为尾节点。头插法则将新节点插入链表头部，步骤包括：创建头节点并初始化链表为空，为新节点分配空间并赋值，将新节点的指针指向原头节点的下一个节点，最后将新节点设为头节点。两种方法均通过循环输入数据，直到输入特定值（如9999）结束。

2025-05-18 21:24:05 532

原创【数据结构】2-3-3单链表的查找

本文介绍了单链表的三种基本操作：按位查找、按值查找和求表长度。按位查找操作通过遍历链表找到第i个节点并返回其值，若位置不合法则返回NULL。按值查找操作则遍历链表寻找与给定值匹配的节点并返回。求表长度操作通过遍历链表计算节点数量并返回长度。这些操作是单链表数据结构中的核心功能，适用于数据检索和链表管理。

2025-05-18 21:21:23 328

原创【数据结构】2-3-2 单链表的插入删除

本文介绍了单链表的几种基本操作，包括按位序插入、指定节点的前插后插、按位序删除节点以及指定节点的删除。对于按位序插入，分为带头节点和不带头节点两种情况，均需找到第i-1个节点后插入新节点。指定节点的前插后插操作则直接在指定节点前后插入新节点。按位序删除节点需要找到第i-1个节点后删除第i个节点，而指定节点的删除则是通过交换数据域并调整指针来实现。这些操作是单链表的基本操作，掌握它们对于理解和应用链表数据结构至关重要。

2025-05-18 21:08:26 441

原创【数据结构】2-3-1单链表的定义

单链表是一种常见的数据结构，其存储结构由节点组成，每个节点包含数据域和指向下一个节点的指针。单链表的优点在于不需要大片连续的内存空间，且容量调整灵活；缺点是无法随机存取元素，且需要额外空间存储指针。单链表的节点定义通常使用结构体，包含数据域data和指向下一个节点的指针next。这种结构适用于频繁插入和删除操作的场景，但访问效率较低。

2025-05-18 20:48:52 205

原创【数据结构】2-2-2 顺序表的插入删除查找

本文介绍了顺序表的基本操作及其时间复杂度分析。插入操作ListInsert在顺序表中第i个位置插入元素e，时间复杂度在最坏情况下为O(n)，最好情况下为O(1)。删除操作ListDelete删除第i个元素并返回其值，时间复杂度与插入操作相同。按位置查找操作GetElemByPosition可以直接访问第i个元素，时间复杂度为O(1)。按值查找操作GetElemByValue从左至右遍历查找元素，最好时间复杂度为O(1)，最坏和平均情况下为O(n)。这些操作展示了顺序表在内存中连续存储的特性及其对操作效率的影

2025-05-18 20:43:02 629

原创【数据结构】2-2-1顺序表的定义以及实现

顺序表是一种线性表的顺序存储结构，通过将逻辑上相邻的元素存储在物理位置上也相邻的存储单元中来实现。顺序表可以通过静态分配或动态分配方式实现。静态分配法一次性分配固定大小的连续存储空间，表长确定后无法更改，可能导致内存浪费。动态分配法则通过malloc和free函数动态申请和释放空间，支持扩展容量，但复制元素时时间开销较大。顺序表的特点包括：支持随机访问（O(1)时间复杂度）、存储密度高、扩展容量不便、插入和删除操作需要移动大量元素。

2025-05-17 15:22:30 430

原创【数据结构】2-1线性表的定义及操作

线性表是由相同数据类型的有限序列组成的数据结构，其中元素按顺序排列，每个元素（除首尾外）都有唯一的前驱和后继。线性表的基本操作包括初始化、销毁、插入、删除、查找、获取元素、求长度、输出和判空等。这些操作涵盖了数据的创建、销毁、增删改查等基本功能。在实际开发中，可以根据需求扩展或修改这些操作。函数定义时需注意参数类型和返回值类型，若需修改参数并保留结果，应使用引用传递。线性表是数据结构中的基础，广泛应用于各种算法和程序设计中。

2025-05-17 15:20:55 226

原创【数据结构】1-4算法的空间复杂度

空间复杂度是衡量算法在运行过程中所需内存空间的指标，表示为S(n)，其中n代表问题规模。当算法所需内存空间不随n变化，即固定为常量时，空间复杂度为O(1)，称为“原地工作”。例如，若一个int变量占4B，内存空间需求为4n+8，则空间复杂度为O(n)。加法规则指出，总空间复杂度为各操作空间复杂度之和，取最大值。常见的空间复杂度从小到大依次为：O(1)、O(log2n)、O(n)、O(nlog2n)、O(n²)、O(n³)、O(2ⁿ)、O(n!)、O(nⁿ)。递归函数的空间复杂度通常与递归深度相关。

2025-05-17 15:15:14 259

原创【shell】shell脚本综合案例6--随机点名器

这篇笔记介绍了如何使用Shell脚本编写一个随机点名器。脚本的主要功能包括：从给定的名单文件中随机选取指定数量的名字，确保名字不重复且不为空，并将选取的名字输出到屏幕上。脚本通过使用Shell的函数、随机数生成、数组操作以及sed指令进行文本处理，实现了这一功能。具体步骤包括：初始化检查名单文件、读取用户输入的点名数量、初始化名字数组、随机生成名字并输出。脚本还提供了错误处理和用户友好的提示信息，确保使用过程中的合法性和便利性。通过该脚本，用户可以轻松实现随机点名功能。

2025-05-17 15:14:42 152

原创【shell】shell脚本综合案例5--随机密码生成器

这篇笔记介绍了一个使用Shell脚本生成随机密码的示例。用户可以通过指定密码的总位数以及各类字符（大写字母、小写字母、数字、特殊字符）的位数，生成符合要求的随机密码。脚本通过初始化字符数组、随机插入字符到密码数组等步骤，确保密码的随机性和多样性。代码中使用了循环、条件判断、数组操作等Shell编程技巧，并提供了详细的用法说明和错误处理。最终生成的密码会显示在终端上，方便用户直接使用。

2025-05-16 19:47:33 334

原创【shell】shell脚本综合案例4--石头剪刀布小游戏

这篇文章介绍了如何使用Shell脚本编写一个简单的“石头剪刀布”小游戏。文章首先展示了完整的代码，代码中使用了case语句、if语句和while循环来实现游戏逻辑。用户可以通过输入数字或文字来选择出拳，计算机则随机出拳，程序会根据双方的出拳结果判断输赢。游戏还提供了退出功能，用户可以通过输入特定命令结束游戏。文章最后附上了游戏运行结果的截图，展示了游戏的实际效果。通过这个示例，读者可以学习到Shell脚本中的基本控制结构和条件判断的使用方法。

2025-05-16 19:35:51 179

原创【shell】shell脚本综合案例3--机选双色球

本文介绍了如何使用Shell脚本实现机选双色球功能。脚本通过生成随机数来选取红色球和蓝色球，确保红色球号码不重复。红色球从1到33中选取6个，蓝色球从1到16中选取1个。脚本中使用了循环、条件判断、数组和随机数生成等技术。最终，脚本会输出生成的红色球和蓝色球号码。通过这个示例，读者可以熟悉Shell编程中的函数运用、随机数生成和数组操作。

2025-05-16 19:26:27 120

原创【shell】shell脚本综合案例2--批量修改文件扩展名

本文介绍了如何使用Shell脚本批量修改文件扩展名。首先，文章强调了掌握Shell中字符串操作和条件语句（如if、for）的重要性。接着，提供了一个完整的Shell脚本示例，该脚本允许用户指定目录、原扩展名和目标扩展名，并逐一确认是否修改每个文件的扩展名。脚本通过mv命令实现文件扩展名的修改，并在每次操作后输出结果。文章最后展示了脚本执行后的效果图，帮助读者直观理解脚本的功能。

2025-05-16 19:15:08 156

原创【shell】shell脚本综合案例1--监控系统状态

本文介绍了一个用于获取系统性能指标并与预设阈值进行比较的Shell脚本。脚本通过读取系统文件（如/proc/loadavg、/proc/meminfo等）获取CPU负载、内存使用、磁盘空间等信息，并使用条件判断语句对这些指标进行监控。当内存、CPU负载或磁盘空间低于预设阈值时，脚本会输出警告信息。文章还提供了代码示例，展示了如何格式化输出和进行条件测试。该脚本适用于系统管理员监控服务器性能，确保系统资源处于合理范围内。

2025-05-16 19:09:11 237

原创【shell】awk指令基础知识

本文介绍了Shell脚本中常用的数据处理工具awk的基本用法和功能。awk是一种基于模式匹配的文本处理引擎，常用于逐行处理文本数据并输出指定内容。文章详细讲解了awk的两种基本格式、内置变量、常用选项（如-F指定分隔符）以及处理时机（BEGIN{}、{}、END{}）。此外，还介绍了awk的条件判断（正则表达式、数值/字符比较、逻辑比较、运算符）、流程控制（if判断、for循环）以及数组的定义、调用和遍历方法。通过示例和图示，帮助读者更好地理解和应用awk进行文本数据处理。

2025-05-16 18:57:59 303

原创【shell】sed指令基础知识

本文介绍了sed命令在Shell脚本中的基本语法和常用选项。sed是一种流编辑器，用于对文本进行处理和转换。其基本语法格式为sed [选项] '[定位符]指令' 文件名，或通过管道与其他命令结合使用。常用选项包括-n（屏蔽默认输出）、-i（直接修改源文件）和-r（支持扩展正则）。定位符可以通过行号或正则表达式来指定操作范围。常用指令包括p（打印行）、d（删除行）、c（替换行）、s（替换关键词）、=（打印行号）、i（插入行）、a（追加行）、r（写入文件内容）和w（导出内容到文件）。这些功能使得sed成为处理文

2025-05-16 18:32:27 311

原创【shell】shell中的正则表达式

本文介绍了Shell Bash编程中的grep命令及其相关正则表达式的使用。grep命令用于在文件中搜索匹配的文本行，常用选项包括-i（忽略大小写）、-v（取反匹配）、-w（匹配单词）和-q（静默匹配）。文章还详细讲解了基本正则表达式和扩展正则表达式的概念，扩展正则表达式通过grep的-E选项支持。文中通过图片展示了正则表达式的具体应用示例，帮助读者更好地理解和掌握这些工具的使用方法。

2025-05-16 18:17:46 210

原创【shell】shell中的字符串处理

本文介绍了Shell Bash编程中常用的字符串操作技巧，包括字符串截取、替换、掐头、去尾以及变量初始化。字符串截取使用${变量:起始位置:长度}格式，起始位置从0开始，截取后原字符串不变。字符串替换分为单个替换${变量/旧字串/新字串}和全部替换${变量//旧字串/新字串}，替换后原字符串也不变。掐头和去尾操作分别使用${变量#关键字}和${变量%关键字}，同样不影响原字符串。变量初始化使用${变量:-关键词}，若变量无值则返回初始值。这些操作在Shell脚本中非常实用，能够高效处理字符串和变量。

2025-05-16 18:04:59 435

空空如也

空空如也