数据结构与算法（Python版）-课件全套 王强 项目1-7 初探数据结构与算法 -高效查找算法设计与应用

数据结构与算法（Python版）全课导航

初探数据结构与算法01

线性表与数组的应用02

栈与队列的应用03

树的结构与应用04

图算法与应用05

高效排序算法与应用实践06

高效查找算法设计与应用07项目1初探数据结构与算法项目概述本项目以“从问题建模到算法优化”为核心路径，结合数据结构的发展历程、经典案例（如学生成绩表、七桥问题等）及高频应用场景，帮助读者掌握数据结构的逻辑关系、存储方式，培养“时空权衡”思维和工程实践能力，最终实现从理论到实战的转化。知识目标理解数据结构的定义、发展历程掌握集合结构、线性结构、树形结构、图形结构的逻辑特性熟悉顺序存储结构、链式存储结构、哈希存储结构的原理掌握算法的定义概念、特性及评价方法项目目标能力目标识别实际问题的抽象模型用伪代码描述简单数据结构素养目标建立科技史观与绿色计算理念培养“时空权衡”决策能力树立科技报国情怀与团队协作精神全班学生以3～5人为一组进行分组，各组选出组长。组长组织组员观看“什么是数据结构”视频/video/BV1Kj41117xR/，讨论并回答下列问题。问题1：生活里有哪些场景用到了数据结构？举1-2个例子。问题2：为什么我们学习编程/计算机知识，需要先学习数据结构？项目准备项目导航任务1.1数据结构入门认知任务1.2算法启航任务1.1

数据结构入门认知Text5

自20世纪80年代起，数据结构进入“面向对象与多元化”阶段。面向对象思想（OOP）的兴起将数据与操作封装为对象，通过继承和多态支持树、图等复杂关系的建模，进一步扩展了数据结构的表达能力。面向对象与多元化阶段数据结构的发展始于20世纪40年代

至60年代的“无结构阶段”。早期计算机以科学计算为核心，数据多为离散数值形式，处理方式依赖数学公式或模型，缺乏系统性组织概念无结构阶段数据结构的发展历程数据结构是数据元素按特定结构组合而成的集合，描述了一组数据自身及数据之间的相互关系。1.1.1数据结构简介数据结构：从问题到模型的数据抽象用计算机解决一个具体的问题时，大致需要经过以下3个步骤：（1）分析问题，抽象并构建对应的数据模型。（2）设计相应的算法。（3）编写程序，运行并调试程序，直至得到正确的结果。1.1.1数据结构简介构建数学模型的实质是分析问题，从中提取操作的对象，并梳理操作对象之间的逻辑关系，然后用数学语言或结构化语言加以描述。有些问题的数据模型可以用具体的代数方程、矩阵等来表示，但更多的实际问题是无法用数学方程来表示的，下面通过例子加以说明。如图1-1所示是一个学生成绩表，表中的每一行都称为一条记录，并按学号升序排列，它们之间存在一对一的关系，是一种线性结构，它构成了学生成绩表的逻辑结构。学生成绩表在计算机外存中的存储方式构成该表的存储结构，在该表中执行查找、插入、删除以及对记录排序等操作共同构成该数据结构对应的基本数据运算。图1-1学生成绩表1.1.1数据结构简介

如图1-2所示是某高校组织的树形结构示意图，在图中学校是根结点，下设部门为中间结点，每个部门的下级末端单位为树叶，整体构成树形结构。树形结构通常用来表示结点的分层组织，结点之间存在一对多的关联，除根结点外，每个结点有且只有一个父结点。这种结构也是一种数据结构，其主要操作是遍历、查找、插入、删除等。图1-2某高校组织的树形结构示意图1.1.1数据结构简介七桥问题：欧拉在

1736年访问普鲁士的哥尼斯堡时，发现当地居民正从事一项有趣味的消遣活动。哥尼斯堡城中有普雷格尔河穿城而过，河上建有七座桥，如图1-3所示。这项消遣活动要求：星期六散步走过全部七座桥，每座桥只能经过一次，而且起点与终点必须是同一地点。1.1.1数据结构简介设四块陆地分别为A、B、C、D，欧拉将每一块陆地抽象为顶点，连接陆地的桥抽象为边，如图1-4所示。图1-4

七桥问题的抽象图1.1.1数据结构简介

欧拉后来通过推论证明：满足条件的行走路线不存在。他的论点是这样的：除了起点外，人由一座桥进入某块陆地（或顶点）时，必然要由另一座桥离开，即每个点如果有进去的边就必须有出来的边。因此图中每一块陆地与其他陆地连接的桥数边数必为偶数。而七桥问题对应的图中，四点顶点对应的边数全部为奇数，因此图中的任务是不可能实现的。

与七桥问题类似，生活中还有不少的实例，如通信网，公路网中的元素都是多对多的关系，具备该特征的数据结构称为图结构。图结构的主要操作有图遍历、最短路径求解等。

类似的还有工资管理系统、棋类对弈等问题。这类问题均依靠表、树、图等数据结构，并且这些数据结构的元素和元素之间存在着逻辑关系。因此，数据结构是一门抽象地研究数据之间关系的学科。1.1.1数据结构简介1.1.2核心概念与术语1.数据结构的基本概念数据（Data）：是描述客观事物的符号记录，是信息的载体。在计算机科学中，数据指能够被计算机输入、存储、处理和输出的一切信息，是计算机承载信息的特定符号表示形式，包括数字、英文、汉字，以及用于表示图形、音频、光电信号的各类符号。数据项（Data

Item）：是构成数据元素、具备独立含义且不可分割的最小数据单位，即数据表中的字段，如图

1-1所示。数据元素（Data

Element）：是数据的基本单位，在计算机信息处理中通常作为一个整体来考虑。一个数据元素可以由若干数据项组成，数据元素也可称为元素、结点、顶点、记录，如图1-1所示。数据对象（Data

Object）：是性质相同的数据元素构成的有限集合，是数据的子集。例如，小写字母数据对象集合

C=｛‘a’，‘b’，‘c’，

…,‘z’｝，整数数据对象集合N=｛0，±

1，±

2，

…

}。数据类型（Data

Type）：是一个值的集合和定义在这个值集合上的一组操作的总称。数据类型中定义了两个集合：值的集合和操作集合。其中，值的集合定义了该类型数据元素的取值，操作集合定义了该类型数据支持的运算。例如在

Python

中，int

是任意精度整数类型，这意味着它的取值范围在理论上没有限制，仅受计算机内存的约束；Python

为整数提供了丰富的运算符和内置函数，涵盖算术、逻辑、位运算等多个方面。数据结构（Data

Structure）：是带结构的数据元素的集合，用于描述一组数据元素以及元素之间的关联。数据结构包括3个要素：数据的逻辑结构、存储结构和操作集合。1.1.2核心概念与术语2.数据的逻辑结构

数据的逻辑结构是描述数据元素之间逻辑关系的方式，它是独立于计算机存储的抽象模型。根据数据元素之间的不同关系，有以下4种基本逻辑结构，如图1-5所示：1.1.2核心概念与术语数据的逻辑结构又可概括为两大类：线性结构和非线性结构。线性结构包括线性表、栈、队列、字符串、数组等；非线性结构包括广义表、树、二叉树和图等。一个数据结构的逻辑结构G可以用二元组来表示：G=（D，R）其中，D是数据元素的集合；R是D上所有数据元素之间关系的集合（表示各元素的前驱、后继关系）。R中的关系用圆括号表示是双向的，尖括号表示是单向的。1.1.2核心概念与术语3.数据的存储结构顺序存储结构链式存储结构索引存储结构哈希（散列）存储结构数据的存储结构使用一组连续的存储单元来存放所有数据元素。使用一组任意的存储单元来存储数据元素，每个数据元素都使用一个结点来存储，结点包含数据元素本身以及指向下一个结点的指针。在存储结点信息的同时建立附加的索引表，索引表中的每个索引项都包含一个关键字和一个指向主数据表的指针。根据结点的关键字直接计算出该结点的存储地址。1.1.2核心概念与术语操作集合基本操作：插入、删除、查找、更新、遍历高级操作：排序、合并、拆分、复制、比较其他操作：求长度、求和、查找极值、去重4.

操作集合1.1.2核心概念与术语知行合一任务描述：

数据结构是组织数据的方式，解决的是数据如何高效存储与摆放的问题，通过数据结构可以将信息转化为可高效处理的形式。本任务旨在通过理解数据结构的定义（带结构的数据集）及4种逻辑结构（集合结构/线性结构/树形结构/图形结构）来初步认识数据结构。任务目标：

明确数据结构的核心定义（数据+逻辑关系），理解早期无结构阶段与现代结构化阶段的技术差异；能够识别实际问题的抽象模型。任务实施：通过二元组与数据结构图之间的映射关系，让读者深入理解数据结构的基础。1.任务要求（1）用二元组方式表示数据结构中的逻辑关系；（2）根据数据结构的二元组描述画出对应的结构关系图。2.实施过程一种数据结构Graph=（D，R）其中：D=｛A，B，C，D，E｝R=｛（A，B），（A，C），（B，C），（B，D），（B，E），（C，E）｝R中的（A，B）表示顶点A到顶点B之间的边是双向的，则上述的结构关系如图1-6所示。图1-6

结构关系图知行合一课堂检测

1、(单选题)学生成绩表中，每一行数据称为一条记录，其逻辑结构属于（）。A.集B.线性结构C.树形结构D.图形结构2、（单选题）数据结构发展“结构化阶段”的主要标志是（）。A.关系模型B.抽象数据类型（ADT）的提出C.面向对象思想D.分布式存储结构BB课堂小结

数据结构入门认知数据结构简介核心概念与术语任务1.2算法启航1.2.1什么是算法算法和数据结构的关系紧密，算法设计由数据的逻辑结构决定，而算法的实现则依赖于数据所采用的存储结构。1.算法的概念算法是解题方案的准确而完整的描述，是一系列解决问题的清晰指令，代表着用系统的方法描述解决问题的策略机制。简而言之，算法是对特定问题求解步骤的一种描述，它是指令的有限序列。1.2.1什么是算法2.算法的特性算法一般具有以下特性。（1）有穷性：算法必须保证在执行有限步骤，有限时间之后终止；（2）确定性：算法的每一个步骤都必须有确切定义，不能有歧义，即对于相同的输入，算法应产生相同的输出；（3）可行性：算法中描述的操作都应是能够由计算机实际执行的基本操作，即每一步都可以通过有限次已定义的基本运算来完成；（4）输入：算法有零个或多个输入，用于刻画运算对象的初始情况；（5）输出：算法有一个或多个输出，输出量与输入存在明确对应关系，是算法的最终结果。1.2.1什么是算法3.算法与程序的区别算法与程序的区别主要表现在以下3个方面。（1）定义：算法是解决问题的思路和方法，是一系列有序的指令集合，而程序则是为实现预期目的而进行操作的一系列语句和指令，是算法的具体实现；（2）书写规定：程序必须用规定的程序设计语言来写，而算法无强制要求，可以用自然语言、程序框图等方式来描述；（3）执行时间：算法所描述的步骤一定是有限的，而程序可以无限地执行下去。1.2.2算法设计的要求算法设计的要求正确性可读性健壮性效率与存储量需求可测试性1.2.3算法的描述算法可以用多种方式来描述，常见的描述方法包括以下4种。1.

自然语言（1）定义。自然语言是使用日常语言来描述算法的步骤和流程。（2）优缺点。优点：简单易懂，方便读者理解算法的基本思想和过程。它可以很直观地将算法的大致思路表达出来，不需要太多的专业知识就能初步把握算法的用途与流程。缺点：不够精确和严谨，容易产生歧义。对于复杂的算法，可能会出现理解上的偏差，导致实现过程中出现错误。（3）示例。描述一个简单的做饭算法：“首先，将米洗净放入锅中，加入适量的水，然后打开炉灶，煮至水沸腾后转小火，继续煮20分钟，最后关火焖几分钟，香喷喷的米饭就做好了。”1.2.3算法的描述2.

流程图（1）定义。流程图是使用各种图形符号（如矩形、菱形、箭头等）来表示算法的步骤、判断条件和流程走向。（2）优缺点。优点：直观形象，能够清晰地展示算法的流程结构和逻辑关系。通过流程图的方式，读者很容易看出算法的各个环节以及它们之间的先后顺序和判断条件，便于理解和分析算法。缺点：对于复杂的算法，绘制其流程图可能会比较复杂和烦琐，而且阅读流程图也需要读者有一定的理解能力。（3）示例。在判断一个数是奇数还是偶数的流程图中，用菱形表示判断条件“这个数除以2余数是否为0”，用矩形表示输出结果“偶数”或“奇数”,如图

1-7所示。图

1-7

流程图示例1.2.3算法的描述3.伪代码（1）定义。伪代码是一种介于自然语言和编程语言之间的描述方式，它使用类似编程语言的语法结构，但不依赖于具体的编程语言语法细节。（2）优缺点。优点：具有较好的可读性和可移植性。它能够比较精确地描述算法的逻辑，同时又不受限于特定编程语言的语法限制，方便程序员将伪代码转换为具体的编程语言代码。缺点：不同的人可能对伪代码的理解存在一定差异，因为它没有严格的语法规则，可能会导致一些误解。1.2.3算法的描述（3）示例。以下是用伪代码描述一个简单的求两个数最大值的算法：开始

输入两个数a和b

如果a>b则max=a

否则max=b

结束如果

输出max结束1.2.3算法的描述4.类Python语言（1）定义。类Python语言是使用类似于Python编程语言的语法来描述算法。Python语言以其简洁明了的语法和丰富的库而受到欢迎，使用类Python语言描述算法可以让熟悉Python的人更容易理解，同时也方便将描述转换为实际的Python代码实现。（2）示例。以下是用类Python语言描述一个简单的冒泡排序算法：1.2.4算法效率的评价1.

时间复杂度（TimeComplexity）一个算法的执行时间等于其所有语句执行时间的总和，而任一语句的执行时间为该语句的执行次数与该语句执行一次所需时间的乘积。但当算法转换成程序之后，每条语句的执行时间取决于机器的硬件速度、指令类型，以及编译的代码质量，而这些是很难确定的。因此

,我们只是将算法中基本操作重复执行的次数作为算法执行时间的量度。一般情况下，算法中基本操作重复执行的次数是问题规模n

的某个函数f（n），算法的时间量度记作：T（n）=

O（f（n））

（1-1）1.2.4算法效率的评价常数阶，表示算法的运行时间与输入数据大小无关，即不随着输入数据的变化而变化。线性阶，表示算法的运行时间随着输入规模n增加而以线性级别增长，通常出现在单层循环中。平方阶，表示算法的运行时间随着输入规模n增加而以平方级别增长，常出现在嵌套循环结构中。对数阶，表示算法的运行时间随着输入规模n增加而以对数级别增长，常出现在递归或二分查找等算法中。O（1）O（n）O（n2）O（logn）常见类型O（2n）指数阶，表示算法的运行时间随着输入规模n增加而以指数级别增长，通常出现在解决组合问题或递归深度较大的算法中。1.2.4算法效率的评价2.

空间复杂度（SpaceComplexity）空间复杂度是衡量算法在执行过程中占用内存空间大小的指标。它反映了算法在运行时所需的辅助存储空间（如临时变量、递归工作栈、动态分配的辅助数组等），而不包括输入数据本身和程序代码所占用的固定空间。类似于算法的时间复杂度，算法所需存储空间的量度记作：

S（n）=

O(ƒ（n））

（1-2）其中，n为问题的规模。评估空间复杂度时，通常考虑算法在运行过程中所需的最大额外空间，即除了输入数据和程序代码本身之外的额外存储空间需求。如果额外空间相对于输入数据量来说是常数，则称此算法为原地工作。知行合一任务描述：

通过任务1.1的学习可知数据结构以特定结构对数据进行存储，但是想要实现数据结构的高效性还需要使用算法对数据进行动态处理。本任务围绕算法的基本概念，算法设计的核心要求，算法的描述以及算法评价指标展开，旨在让读者初步了解算法。任务目标：

需区分算法与程序的本质区别（算法是解题思路，程序是实现载体）；需要明确算法的设计要求；需要掌握算法的描述方式；需要掌握算法的评价方法。任务实施：通过分析错误代码，识别算法的基本特性缺失问题。1.任务要求（1）根据算法编写简单程序；（2）学生分组讨论所写算法特性；（3）教师总结。2.实施过程（1）展示代码。知行合一知行合一（2）分组讨论。问题1：该算法是否满足“有穷性”？为什么？问题2：若输入数组为空，输出结果是否符合“确定性”？（3）教师总结。有穷性：循环需设置终止条件（如break语句）；确定性：需处理边界条件（如空数组返回None）。课堂检测

1、（单选题）以下哪项不是算法的特性（）。A.有穷性B.确定性

C.可行性D.无限性2、（单选题）算法分析的两个主要方面是（）。A.正确性和简单性B.时间复杂度和空间复杂度C.数据复杂性和程序复杂性D.可读性和文档性DB课堂小结

算法启航什么是算法算法设计的要求算法的描述算法效率的评价谢谢观看数据结构与算法（Python版）全课导航

初探数据结构与算法01

线性表与数组的应用02

栈与队列的应用03

树的结构与应用04

图算法与应用05

高效排序算法与应用实践06

高效查找算法设计与应用07项目二线性表与数组的应用项目导读本项目以“从问题建模到算法优化”为核心路径，结合线性表与数组的逻辑特性、存储实现方式及AI应用场景（如词频统计等），帮助读者掌握数据结构的核心操作、存储实现及算法设计方法，培养高效编程思维与工程实践能力，最终实现从理论到实战的转化。知识目标理解线性表/数组的定义、逻辑关系掌握顺序/链式存储结构的实现原理熟悉特殊矩阵的压缩存储方法理解稀疏矩阵的三元组与十字链表表示法项目目标能力目标用Python实现线性表的基本操作分析数组操作的时间复杂度设计稀疏矩阵的压缩存储方案实现矩阵转置等算法优化素养目标建立科技史观与绿色计算理念强化“时空权衡”决策意识培养团队协作与工程伦理意识全班学生以3～5人为一组进行分组，各组选出组长。组长组织组员观看“数据结构——线性表”视频/video/BV1j4x2zrEDw/，讨论并回答下列问题。问题1：想一想日常学习、生活中，哪些事物是按先后顺序依次排列的？举例说一说，这些有序排列的事物有什么共同特点。问题2：如果要记录全班同学的点名顺序、食堂排队队伍、手机通讯录，这类有序数据可以怎么管理？试着说说增、减其中某一个数据时，会出现哪些变化？项目准备项目导航任务2.3稀疏矩阵存储与转置任务2.4单链表的实现任务2.1了解线性表基础任务2.2搭建班级成绩管理系统任务2.1了解线性表基础2.1.1线性表概述线性表（linearlist）是具有相同数据类型的数据元素组成的有限序列。当线性表非空时，通常记为：(a1,a2,…,ai,ai+1,…,an)，其中n为线性表的长度，n≥1。a1称为表头元素，an称为表尾元素。特别地，当n=0时，线性表称为空表，此时表中不含任何元素。线性表中相邻元素之间存在顺序关系：除第一个元素外，每个元素有且只有一个直接前驱，ai-1称为ai的直接前驱结点；除最后一个元素外，每个元素有且只有一个直接后继，ai+1称为ai的直接后继结点。线性表中的元素既可以是一个数，也可以是由多个数据项组成的复杂信息，但其元素必须属于同一数据对象。例如，英文字母（A，B，…Y，Z）和如项目1中图1-1所示的学生成绩表。1.线性表的定义2.1.1线性表概述2.线性表的二元组表示线性表用二元组表示为：linear_list=（D，R）其中数据对象：D=｛ai

|1

≤

i

≤

n，n

≥

1，ai∈ElemType｝数据关系：R=｛r｝，r=｛<

ai，ai

+1>

|1

≤

i

≤

n-1｝，对应的逻辑结构图如图

2-1所示。2.1.2线性表的基本操作线性表的基本操作是数据结构的核心功能，主要用于管理元素的存储、访问和修改，常用操作有以下

5种。1.初始化与销毁（1）初始化。创建空表，分配存储空间（如数组或链表结点）。（2）销毁。释放线性表占用的全部内存、清除所有元素。2.1.2线性表的基本操作2.

元素操作（1）插入元素。1）功能：在指定位置插入新元素；2）参数：插入位置索引、元素值；3）示例：2.1.2线性表的基本操作（2）删除元素。1）功能：移除指定位置的元素；2）参数：删除位置索引；3）返回值：被删除的元素值（可选）；4）示例：2.1.2线性表的基本操作3.查找与访问（1）按位置查找。1）功能：获取指定位置的元素值；2）参数：位置索引；3）返回值：元素值；4）示例：2.1.2线性表的基本操作（2）按值查找。1）功能：找到元素第一次出现的位置；2）参数：目标值；3）返回值：位置索引（未找到则返回

-1）；4）示例：2.1.2线性表的基本操作4.

状态查询（1）判空操作。1）功能：检查表是否为空；2）返回值：布尔值（True/False）；。3）示例：2.1.2线性表的基本操作（2）获取长度。1）功能：返回表中元素个数；2）返回值：整数长度；3）示例：2.1.2线性表的基本操作5.遍历与输出（1）功能：顺序访问所有元素并处理（如打印）；（2）示例：知行合一任务描述：

线性表是数据结构的基础，元素间“一对一”的逻辑关系，可通过顺序结构或链式结构存储数据。本任务主要介绍线性表的逻辑结构，以及其基本操作的实现原理，旨在让读者对线性表有一个初步认识。任务目标：

能够区分线性表的逻辑结构（数据元素序列）；理解线性表中相邻元素的直接前驱/后继关系；掌握线性表的基本操作。任务实施：在现实场景中，理解线性表的逻辑结构（元素间顺序关系），掌握其基本操作（插入、删除、查找）的实现原理。1.任务要求（1）教师需要引导学生从实际生活中发现元素的顺序关系；（2）学生列举生活中符合线性表逻辑关系的实例，并分组讨论总结；（3）教师点评学生所举案例。2.实施过程（1）教师引导提问。1）“观察教室门外的同学排队打饭，谁能说说他们的顺序有什么特点？”→引出“线性表的元素按顺序排列”；2）“如果插队的人必须站在队尾，这说明线性表有什么规则？”→强调“元素间有严格的前后关系”。知行合一任务实施：（2）学生活动。1）头脑风暴举实例；2）分组讨论并填写下表，派代表分享。知行合一组别找到的生活场景对应的线性表内容是否符合线性表特征1

2

3

（3）教师点评。

合格案例：图书馆借阅记录（按借书时间排序）、月度考勤表等。×反例：班级座位分布（二维平面，非线性）。课堂检测

（单选题）线性表的逻辑结构特点不包括以下哪一项？()A.数据元素类型相同B.相邻元素存在顺序关系C.除首尾元素外，其他元素有唯一前驱和后继D.允许元素重复且无序排列D课堂小结

了解线性表基础线性表概述线性表的基本操作任务2.2搭建班级成绩管理系统2.2.1线性表的顺序存储结构

线性表的顺序存储结构是一种将逻辑上相邻的数据元素存储在物理位置相邻的存储单元里，数据元素间的逻辑关系由存储单元的邻接关系来体现。在这种存储结构中，每个存储单元的地址是连续的，通过计算可以确定表中任意一个数据元素的存储位置。2.2.1线性表的顺序存储结构如图

2-2所示，如果第1个数据元素存放的位置为b，每个元素占用的空间大小为L，则顺序表中第i个数据元素ai的存储位置为：Loc（ai）=

Loc（a1）+（i-1）*L

（1≤i≤n）其中，Loc（ai）表示顺序表中第i个数据元素的存储位置；Loc（a1）表示顺序表中第1个数据元素的存储位置（即基地址），Loc（a1）=b；L表示每个数据元素占用的存储单位大小；i表示位序。

Loc（ai）=b+（i-1）*L

（1≤i≤n）图2-2线性表的顺序存储结构示意图2.2.1线性表的顺序存储结构在Python

中，线性表的顺序存储结构可以通过列表（list）来实现。列表是Python

内置的数据类型，其底层基于动态数组的实现，可以方便地实现线性表的顺序存储。2.2.1线性表的顺序存储结构输出结果：在这个例子中，我们使用append()方法向线性表中添加元素，使用索引来访问和修改元素，使用del语句来删除元素。这些操作都体现了线性表的顺序存储特性。2.2.2线性表顺序存储的基本操作线性表的顺序存储结构通常使用数组来实现。在Python语言中，列表可以看作是动态数组的实现。下面详细介绍线性表顺序存储的基本操作，包括插入、删除、查找等，并给出相应的算法思想、代码实现及时间复杂度分析。2.2.2线性表顺序存储的基本操作1.插入操作算法思想：在指定位置插入一个新元素，需要将该位置及其后面的所有元素向后移动一位，然后将新元素放在指定位置。［算法

2-1］时间复杂度分析：-最好情况：O（1）（在末尾插入）；-最坏情况：O（n）（在开头插入）；-平均情况：O（n）。2.2.2线性表顺序存储的基本操作2.删除操作算法思想：删除指定位置的元素，需要将该位置后面的所有元素向前移动一位。

［算法

2-2］时间复杂度分析：-最好情况：O（1）（在末尾删除）；-最坏情况：O（n）（在开头删除）；-平均情况：O（n）。2.2.2线性表顺序存储的基本操作3.查找操作算法思想：遍历线性表，找到与目标值相等的元素并返回其索引。如果未找到，则返回

-1。

［算法

2-3］时间复杂度分析：-最好情况：O（1）（第一个元素就是目标值）；-最坏情况：O（n）（最后一个元素是目标值或不存在）；-平均情况：O（n）。2.2.2线性表顺序存储的基本操作4.更新操作算法思想：直接通过索引访问并修改指定位置的元素。

［算法

2-4］时间复杂度分析：-O（1）（直接通过索引访问和修改）。2.2.2线性表顺序存储的基本操作5.获取线性表长度操作算法思想：直接返回线性表的长度。［算法

2-5］deflength(linear_list):returnlen(linear_list)时间复杂度分析：-O（1）（直接获取长度属性）。

2.2.2线性表顺序存储的基本操作6.打印线性表操作算法思想：遍历线性表并打印每个元素。［算法

2-6］时间复杂度分析：-O（n）（需要遍历整个线性表）。以上内容介绍了线性表顺序存储的基本操作，包括插入、删除、查找、更新、获取线性表长度和打印线性表等操作。这些操作的时间复杂度主要取决于线性表的长度和操作的位置。对于顺序存储结构的线性表，插入和删除操作可能需要移动大量元素，因此在实际应用中，如果频繁进行插入和删除操作，可能需要考虑其他数据结构，如链表。知行合一任务描述：

线性表的顺序存储结构通过连续的物理内存空间存储数据，能够直接反映数据的逻辑关系。本任务主要介绍线性表的顺序存储结构概述以及其基本操作，并以班级成绩管理系统为例，旨在通过实例教学方式让读者更好地理解线性表的顺序存储结构。任务目标：

能够设计数据结构：采用列表嵌套字典的结构存储数据，以一个字典代表一个学生的信息。知行合一能够对核心功能进行分析（见表2-1）。

表2-1核心功能分析功能关键操作注意事项添加学生list.append()检查学号的唯一性查询学生遍历列表匹配条件支持按学号/姓名进行模糊查询修改成绩查找后直接修改字典值需验证学号是否存在删除信息for

循环按学号查找，找到后

dellist[i]需处理学号不存在的情况显示全部for循环遍历列表格式化表格输出任务实施：开发一个基于Python列表的班级成绩管理系统。1.任务要求（1）添加学生信息（学号、姓名、成绩）；（2）查询指定学生的成绩；（3）修改指定学生的成绩；（4）删除指定学生的信息；（5）显示所有学生的成绩；（6）退出系统。知行合一任务实施：2.实施过程（1）定义存储结构的全局变量；（2）创建功能函数：add_student()，query_student()，modify_score()，delete_student()，show_all()；（3）构建交互式菜单界面；（4）实现数据有效性验证（如学号格式、分数范围）；（5）添加异常处理机制。本任务的实现代码请扫描课本二维码查看。知行合一任务实施：3.测试用例（1）测试场景1：添加学生信息。1）输入合法学号（如2023001）、姓名（李四）、成绩（90）；2）尝试添加重复学号→应提示错误；3）输入非法成绩（abc）→应提示错误。（2）测试场景2：查询功能。1）按学号查询存在的学生信息；2）按姓名查询存在的多名学生信息；3）查询不存在的学生信息。（3）测试场景3：修改成绩。1）修改存在的学生成绩；2）修改不存在的学生成绩；3）输入非法成绩（-10）。知行合一课堂检测

（单选题）顺序表在Python中通常用什么数据结构实现？(

)A.字典B.列表C.元组D.集合（单选题）在顺序表中插入元素时，最坏情况下的时间复杂度为（

）。A.O（1）B.O（logn）C.O（n）D.O（n2）BC课堂小结

搭建班级成绩管理系统线性表的顺序存储结构线性表顺序存储的基本操作任务2.3稀疏矩阵存储与转置2.3.1数组的基本概念数组是由一组具有相同数据类型的元素组成的有序集合。这些元素按照一定的顺序排列，并且可以通过索引（通常是整数）直接访问。2.3.1数组的基本概念类型统一固定大小连续存储随机访问数组的特点数组中的所有元素必须是相同的数据类型，如整型数组、字符型数组等。这保证了数据的一致性和操作的简便性。一旦创建了数组，其大小就固定不变。这意味着在创建数组时需要预先指定数组的长度，即元素的个数。数组的元素在内存中是连续存放的。这种存储方式使得通过索引快速访问元素成为可能。可以直接通过索引访问任意位置的元素，时间复杂度为O（1）。这使得数组在需要频繁随机访问元素的场景下非常高效。2.3.1数组的基本概念2.数组的操作创建与初始化：在不同编程语言中，创建和初始化数组的方式有所不同。例如，在Java中，可以声明并初始化一个整数数组“int[]

numbers

={1,

2,

3,

4,

5};”。也可以先声明后赋值，如“int[]

numbers;numbers=newint[]

{1,2,3,

4,

5};”。访问元素：通过索引访问数组中的特定位置元素。索引从0开始计数，例如

numbers[0]表示访问第一个元素。修改元素值：可以直接通过索引修改数组中的元素值，如

numbers[0]

=10;意为将数组中的第一个元素值修改为10。遍历数组：可以使用循环结构遍历数组中的所有元素，并进行相应的操作。数组作为一种基础的数据结构，在编程中扮演着极其重要的角色。它以其高效的数据访问能力和简单直观的实现方式赢得了广泛的青睐。2.3.2数组的顺序存储结构在高级编程语言中，数组在计算机内是用一批连续的存储单元来表示的，这种存储方式称为数组的顺序存储结构。在二维数组中，每个元素都受行关系和列关系的约束。例如，在一个二维数组A[m][n]中，对于第i行第j列的元素A[i][j]，A[i][j+1]是该元素在行关系中的直接后继元素；而A[i+1][j]是该元素在列关系中的直接后继元素。大部分高级编程语言（如C语言，Pascal）采用行优先的存储方式，如图2-3（a）所示。有的编程语言（如Fortran）则采用列优先的存储方式，如图2-3（b）所示。2.3.2数组的顺序存储结构1.行优先的存储方式对于一维数组a[n]来说，数组的长度为

n，每个元素所需的存储空间

L

由数组元素的数据类型决定，即

L=sizeof（ElemType），数组的首地址为

LOC[a]（元素a[0]的地址），则数组

a[n]中任何一个元素a[i]的地址

LOC[i]可通过下面的公式进行计算：LOC[i]=LOC[a]+

i

*L

（2-1）2.3.2数组的顺序存储结构对于二维数组a[n][m]来说，先依次存放第一行的元素a00，a01，...，a0(m-1)；然后存放第二行元素a10，a11，...，a1(m-

1)，

…；最后存放第n行元素a(n-1)0，a(n-1)1，...，a(n-1)(m-1)；若每行的元素个数为

m

，每个元素所需存储单元为L，则二维数组按行存储的地址映像公式为：LOC[i,j]=LOC[0,0]+（m

*i+j）*L

（2-2）同理可知三维数组a[c1][c2][c3]按行存储方式下地址映像公式为：LOC[i,j,k］=LOC[0,0,0]+（c2

*c3

*i

+

c3

*j

+

k）*L

（2-3）2.3.2数组的顺序存储结构

分析上面的公式，c2

*c3为后两个维度所对应的二维数组的元素个数，c3

则是后一个维度所对应的一维数组的元素个数，以上规则可以推广到多维数组的情况。设n维数组的各维长度为c1

，c2，

…cn，每个元素所需存储单元为L个，各维数组元素的下标由0开始，则n维数组按行存储的地址映像公式为：

2.3.2数组的顺序存储结构例：2.1有如下数组定义：若数组a的首地址为500，数组b的首地址为

1000，且按行存储。求数组元素

a［5][6］，b[3][4][3]的地址。设int类型占2字节，float类型占4字节。解：（1）数组元素

a[5][6]的地址。将i=5，j=6，m=9

代入式（2-2）得：LOC［5

，6］=

500+（9*

5+

6）*

sizeof（int）=

500+

51*

2=602（2）数组元素

b[3][4][3]的地址。将i=3，j=4，k=3

，c2

=6

，c3

=4代入式（2-3）得：LOC［3，4

，3］=

1000+（3*

6*

4+

4*

4+

3）*

sizeof（float）=

1000+

91*

4=13642.3.2数组的顺序存储结构2.列优先的存储方式列优先存储是指首先存储数组第一列的元素，然后存储第二列的元素，……,最后存储第n列的元素。推广到一般情况，设n维数组的各维长度为c1，c2，…，cn，每个元素所需存储单元为L个，各维数组元素的下标由0开始，则n维数组按列存储的地址映像公式为：2.3.2数组的顺序存储结构例：2.2有如下数组定义：若数组a

的首地址为500，数组b

的首地址为

1000，且按列存储。求数组元素

a[5][6]，b[3][4][3]的地址。解：（1）数组元素

a[5][6]的地址。将j1=5，j2=6

，c1=9

，c2=9

代入式（2-5）得：LOC［5

，6］=

500+（9*6+5）*

sizeof（int）=

500+

59*

2

=

618（2）数组元素

b[3][4][3]

的地址。将j1=3，j2=4，j3=3，c1=

10，c2

=6

，c3=4代入式（2-5）得：LOC［3，4

，3］=

1000+（10*6*3+10*

4+3）*

sizeof（float）=

1000+

223

*

4=18922.3.3特殊矩阵的压缩存储矩阵是由数字或符号按行和列排列形成的矩形阵列，最早源于线性方程组的系数与常数构成的方阵。形式上，矩阵可表示为由m×n个元素组成的表格，其中每个元素的位置由其所在的行i和列j确定，记为aij，如A=［aij］m×n表示一个m行n列的矩阵。2.3.3特殊矩阵的压缩存储矩阵在科学与工程计算中有着广泛的应用。例如，在图像处理中，仿射变换可用仿射矩阵和原始图像相乘来实现旋转、缩放、平移等操作；在计算机图形学中，矩阵用于表示物体变换，实现从三维空间到二维屏幕的转换；在物理学和工程学中，力学问题、电路分析等都可由矩阵方程描述求解；在数据科学与机器学习中，算法里的线性代数操作依赖矩阵，如神经网络通过矩阵运算训练模型等；在经济学与金融学中，投资组合优化、投入产出分析等也借助矩阵来研究产业间的依存关系。但在数据结构中研究的不是矩阵本身，而是研究如何在计算机中高效地存储矩阵，实现矩阵的基本运算。在高级编程语言中，通常用二维数组来表示矩阵，从而利用前述的地址计算公式快速访问矩阵中的每一个元素。在实际应用中还会遇到一些特殊矩阵。2.3.3特殊矩阵的压缩存储

特殊矩阵是指具有大量相同元素或零元素，且这些元素按一定规律分布的矩阵。分析特殊矩阵中元素的分布规律，只存储其中必要的、有效的信息，可以对这些矩阵进行压缩存储以节省存储空间。由于特殊矩阵中元素的分布有明显的规律，因此可将其压缩存储到一个一维数组中，并找到每个非零元素在一维数组中的对应关系。常见的特殊矩阵有：对称矩阵、三角矩阵和三对角矩阵。2.3.3特殊矩阵的压缩存储1.对称矩阵若一个n阶矩阵A中的元素满足：aij=aji（1≤i≤n，1≤j≤n），则称A为n阶对称矩阵，即元素分布关于主对角线对称。对于对称矩阵进行压缩存储时，可以为每一对对称元素分配同一存储空间。因此，具有n*n个元素的对称矩阵采用一维数组可以压缩存储到n*（n+1）/2个元素空间中。例：2.3一个4*4对称矩阵M，存储映像为：2.3.3特殊矩阵的压缩存储按行序存储为：

用一维数组M［1，2，…,n（n+1）/2］作为n阶对称矩阵A的存储结构时，矩阵元素aij与数组元素M［k］存在一一对应的关系，则下标间的换算关系如下：2.3.3特殊矩阵的压缩存储2.三角矩阵当一个矩阵的主对角线以上或以下的所有元素皆为常数c或0时，该矩阵称为三角矩阵；三角矩阵有上三角矩阵和下三角矩阵，如图2-4所示为c=0的三角矩阵。

（a）下三角矩阵

（b）上三角矩阵

图2-4三角矩阵2.3.3特殊矩阵的压缩存储对于n阶上三角矩阵和下三角矩阵，以行序为主序，将矩阵的所有非常数部分压缩存储到一个一维数组M[1…，n(n+1)/2]中，则M[k]和矩阵中非常数部分aij之间存在一一对应的关系。下三角矩阵：k=i（i-1）/2+j（i>=j）上三角矩阵：k=(2n-i+2)(i-1)/2+（j-i+1）（i<=j）2.3.3特殊矩阵的压缩存储3.三对角矩阵三对角矩阵是指除了主对角线上和直接在对角线上下的对角线上的元素外，其他所有元素皆为零的矩阵，如图2-5所示。对于n阶的三对角矩阵，以行序为主序，将矩阵的所有非零元素压缩到一维数组M[1，2，…,3n-2]中，则M[k]和矩阵中非零元素aij之间存在一一对应关系：k=2i+j-2。如图2-6所示给出了三对角矩阵的压缩存储形式。图2-5三对角带状矩阵2.3.4稀疏矩阵的存储方式与转置稀疏矩阵指非零元素占比远小于零元素的矩阵。在具体定义中，当稀疏因子K(非零元素个数/矩阵总元素数)≤

20%时称为稀疏矩阵。例如，一个1000×1000的矩阵若有104个非零元素，则其稀疏因子K=1%，属于稀疏矩阵。如图2-7所示的6×7矩阵中，非零元素仅占

5/42≈11.9%，符合稀疏矩阵的特征。对于这样的矩阵，如果采用二维数组存储全部元素的话，显然会浪费大量的存储空间，因此一般采用压缩存储方式。稀疏矩阵进行压缩存储的方法通常有两类：三元组表示法和十字链表表示法。2.3.4稀疏矩阵的存储方式与转置1.稀疏矩阵的三元组表示法稀疏矩阵的非零元素呈现随机、无固定模式的分布特性，这与三对角矩阵、三角矩阵等具有规律性结构的特殊矩阵存在本质差异。由于这种无序性，稀疏矩阵无法像特殊矩阵那样通过数学公式或固定规则建立矩阵下标到存储地址的直接映射关系。因此，为精确描述每个非零元素的空间位置，必须额外记录其行号和列号，与元素值共同构成完整的定位信息。这种“坐标+数值”的双重存储机制，使得程序能够在忽略大量零元素的前提下，快速检索和操作稀疏矩阵中的有效数据。稀疏矩阵的三元组表示法就是存储三元组（行号，列号，值），并按行优先顺序排列。图

2-7矩阵的三元组表示为：[（0，4

，5），（

1，2

，3），（2

，5

，7），（4，

1，2），（5，4

，9）]矩阵的行数、列数以及非零元素的个数需要另外存储。2.3.4稀疏矩阵的存储方式与转置2.稀疏矩阵的十字链表表示法稀疏矩阵的三元组表示法与传统的二维数组相比节约了大量的存储空间，但是在进行某些运算，如矩阵相加，乘法运算时，非零个数和位置会发生很大的变化，采用三元组的顺序结构势必需要移动大量的元素。为了避免移动元素，可以采用链式存储结构——十字链表表示法。2.3.4稀疏矩阵的存储方式与转置在十字链表中，每一个非零元素用一个结点表示，结点中除了表示非零元素所在的行（row）、列（col）和值（val）的域外，还需增加两个链域：行指针域（right），用来指向本行中下一个非零元素；列指针域（down），用来指向本列中下一个非零元素。整个链表构成一个十字交叉的链表，我们称这样的存储结构为十字链表。十字链表可用两个分别存储行链表的头指针和列链表的头指针的一维数组表示。如图2-8所示为稀疏矩阵以及该矩阵的十字链表。图2-8稀疏矩阵的十字链表2.3.4稀疏矩阵的存储方式与转置用类Python语法描述的稀疏矩阵十字链表表示法如下：当稀疏矩阵用三元组表示法进行相加时，有可能出现非零元素的位置变动，这时不宜采用三元组表作存储结构，而应该采用十字链表。但因为每个非零元素的结点既在行链表中又在列链表中，所以在插入或删除结点时，既要在行链表中进行又要在相应的列链表中进行，因此指针的修改会复杂些。2.3.4稀疏矩阵的存储方式与转置3.稀疏矩阵的转置运算稀疏矩阵的转置运算就是一个m×n的矩阵A，它的转置矩阵B是一个n×m的矩阵，且A[i][j]=B[j][i]，1≤i≤m，1≤j≤n，即A的行是B的列，A的列是B的行。稀疏矩阵的核心存储方式是压缩稀疏行（CSR）或压缩稀疏列（CSC），两者分别优化行访问和列访问。转置操作的本质是将行优先存储转换为列优先存储，从而匹配不同场景的访问需求。2.3.4稀疏矩阵的存储方式与转置例：2.4

如图2-9所示的矩阵M和M′互为转置矩阵。图2-9稀疏矩阵M及其转置矩阵M′2.3.4稀疏矩阵的存储方式与转置在三元组表示法的存储方法下，求稀疏矩阵M的转置矩阵N，实际上就是由如图

2-9所示的M求得M′。三元组转置的方法有两种。（1）按照矩阵M的列序进行转置。该算法思想如下：1）统计列元素数：遍历原矩阵中的非零元素，统计每列的非零元素个数；2）计算起始存储位置：根据列元素数，确定转置后每行的起始存储位置；3）填充转置矩阵：将原矩阵元素按列顺序依次插入转置矩阵的正确位置。2.3.4稀疏矩阵的存储方式与转置具体的算法描述如下：［算法2-7］2.3.4稀疏矩阵的存储方式与转置2.3.4稀疏矩阵的存储方式与转置算法分析（见表2-2和表2-3）。2.3.4稀疏矩阵的存储方式与转置（2）按三元组顺序的稀疏矩阵转置算法（简单转置法）。算法思想：1）直接交换行列：遍历原矩阵的三元组列表，将每个元素的行和列交换，得到转置后的无序三元组；2）按行列排序：对转置后的三元组按行优先顺序（即先按行号升序，行号相同再按列号升序）排序，最终得到有序的转置矩阵。转置算法描述：［算法2-8］2.3.4稀疏矩阵的存储方式与转置2.3.4稀疏矩阵的存储方式与转置算法分析（见表2-4和表2-5）。知行合一任务描述：

在科学计算与数据处理中，许多实际场景涉及零元素占比极高的矩阵（称为“稀疏矩阵”）。直接存储这类矩阵会为重复元素或零元素分配内存资源从而导致资源浪费，因此需采用特殊的压缩存储方式以减少对矩阵中重复元素或零元素的存储，此外可通过转置进一步提高存储和计算效率。本任务以数组和特殊矩阵的压缩存储为基础，重点介绍稀疏矩阵存储与转置，旨在让读者了解稀疏矩阵的高效存储方式。任务目标：

能够理解数组作为顺序存储的基础，并使用三元组(row,col,value)存储稀疏矩阵；能够实现稀疏矩阵的转置功能；能够确保转置后的矩阵仍保持稀疏性且逻辑正确；能够提供可视化对比（原矩阵vs转置矩阵）。任务实施：本任务要求基于Python实现稀疏矩阵的转置操作，并通过实验验证其正确性和效率。1.任务要求（1）使用三元组（row，col，value）的形式存储稀疏矩阵；（2）实现稀疏矩阵的转置功能（即将原矩阵的行变为列，列变为行）；（3）确保转置后的矩阵仍保持稀疏性且逻辑正确；（4）提供可视化对比（原矩阵vs转置矩阵）。2.实施过程（1）总体流程。开始→初始化稀疏矩阵→执行转置算法→输出结果→验证正确性→结束。知行合一任务实施：（2）详细步骤。步骤1：定义稀疏矩阵类（可选）。可封装一个简单的SparseMatrix类，包含以下属性和方法：知行合一任务实施：步骤2：实现转置函数。核心逻辑是将每个三元组的行（row）和列（col）互换：知行合一任务实施：步骤3：构造测试用例。创建一个示例稀疏矩阵：知行合一任务实施：步骤4：执行转置并打印结果。调用transpose()函数获取转置矩阵，并分别打印原矩阵和转置矩阵的三元组：知行合一步骤5：验证正确性。人工计算预期结果并与程序输出对比：1）原矩阵：（0，1）=5，（1，0）=8，（2，3）=9；2）转置后应为：（1，0）=5，（0，1）=8，（3，2）=9课堂检测

（单选题）对称矩阵压缩存储后，若原矩阵为n阶，需存储的元素个数为（）。A.n2B.n（n+1）/2C.n（n-1）/2D.n/2（单选题）在稀疏矩阵的三元组表示法中，每个非零元素需记录的信息包括（）。A.行号、列号、值B.行号、值、索引C.列号、值、位置D.行号、列号、索引BA课堂小结

稀疏矩阵存储与转置数组的基本概念数组的顺序存储结构特殊矩阵的压缩存储稀疏矩阵的存储方式与转置任务2.4单链表的实现2.4.1单链表的结构定义单链表是一种线性数据结构，它由一系列结点组成，每个结点包含两个部分：数据域和指针域。数据域用于存储结点的数据信息，而指针域则用于指向下一个结点的位置。指向单链表第一个结点的指针称为头指针，最后一个结点的指针域为空（即None），表示链表的结束。图2-10直观展示了单链表的两种核心状态：图2-10（a）呈现了非空表的典型结构，头指针指向首个结点，后续结点通过各自的指针域顺序链接，每个结点均包含用于存储具体值的数据域和指向下一结点内存地址的指针域，且末尾结点的指针域明确指向NULL以标识链表结束，这种设计支持动态遍历与增删操作，同时可实现存储空间的动态分配。图2-10（b）则描绘了空表的情形，其中头指针（head）直接指向NULL，表明链表中不存在任何结点，因此既无数据域也无指针域，适用于初始化或清空操作。2.4.1单链表在Python中，可以使用自定义类来实现单链表。1.定义结点类2.定义单链表类2.4.2单链表的基本操作在Python语言环境下，单链表是一种常见的数据结构。以下是单链表的基本操作及其算法思想、算法步骤和代码实现。1.初始化单链表算法思想：创建一个空链表。头指针指向None，表示链表中尚无任何数据结点。算法步骤：1）定义一个

Node

类，包含数据域

data

和指针域

next；2）定义一个

LinkedList

类，包含头指针

head；3）在

LinkedList

类的构造函数中，将

head

初始化为

None。［算法

2-9］2.4.2单链表的基本操作2.插入结点（1）将新结点插入链表的头部或尾部。1）算法思想：将新结点插入链表的头部或尾部。2）当在头部插入时，创建新结点，将其next

指针指向当前的头结点，然后更新头结点为新结点。算法步骤：-

创建一个新结点；-

将新结点的next指针指向当前头指针指向的结点；-

更新头结点为新结点。［算法

2-10］2.4.2单链表的基本操作3）当在尾部插入时，遍历链表找到最后一个结点，将其next指针指向新结点。算法步骤：-创建一个新结点；-如果链表为空，则将头结点设置为新结点；-否则，遍历链表找到最后一个结点，将其next指针指向新结点。［算法2-11］2.4.2单链表的基本操作（2）在单链表的第i个位置插入一个新结点。1）算法思想：-边界检查：首先检查插入位置是否有效。如果位置小于0或者大于链表长度，则不进行插入操作；-特殊情况处理：如果插入位置是0，即在头部插入，则直接调用头部插入函数；-遍历链表：从头结点开始遍历链表，找到第i-1个结点（即插入位置的前一个结点）；-插入新结点：将新结点的next指针指向第i-1个结点的下一个结点，然后将第i-1个结点的next指针指向新结点。2.4.2单链表的基本操作例如，在长度为

8

的单链表的第3个位置插入一个新结点，操作示意图如图2-11所示。

在第3个位置插入元素6,i=3图2-11在第3个位置插入元素62.4.2单链表的基本操作2）算法步骤：-定义一个Node类，包含数据和指向下一个结点的指针；-定义一个LinkedList类，包含头结点和各种操作方法；-在LinkedList类中实现插入方法。2.4.2单链表的基本操作（3）在链表的x值前插入一个y值结点。1）算法思想：-创建一个新结点，其值为y；-遍历链表，寻找值为x的结点；-如果找到值为x的结点，则将新结点插入到该结点之前；-如果未找到值为x的结点，将新结点插入到链表的末尾。2）算法步骤：-初始化一个指针current，指向链表的头结点；-遍历链表，检查每个结点的值是否等于x；-如果找到值为x的结点，则使用指针current的前一个结点来插入新结点；-如果遍历完整个链表都没有找到值为x的结点，则将新结点添加到链表的末尾；-更新链表的头结点（如果需要）。2.4.2单链表的基本操作3.删除结点（1）算法思想：根据值删除链表中的结点。当删除特定值的结点时，遍历链表找到要删除的结点，并调整前一个结点的next指针。（2）算法步骤：1）检查头结点是否为要删除的结点。如果是，则更新头结点为下一个结点；2）否则，遍历链表找到要删除的结点，并调整前一个结点的next指针；（3）如果找不到该结点，则返回。2.4.2单链表的基本操作4.

搜索结点（1）算法思想：遍历链表查找特定值的结点。（2）算法步骤：1）从头结点开始遍历链表；2）如果找到目标值，则返回

True；3）如果遍历完链表后仍未找到目标值，则返回

False。

［算法

2-15］2.4.2单链表的基本操作5.

打印链表（1）算法思想：从头结点开始遍历链表，打印每个结点的数据。（2）算法步骤：1）从头结点开始遍历链表；2）打印每个结点的数据；3）直到遍历完链表。

［算法

2-16］2.4.2单链表的基本操作6.获取链表长度（1）算法思想：遍历链表并计数结点数量。（2）算法步骤：1）初始化计数器为

0；2）从头结点开始遍历链表，每遍历一个结点，计数器加

1；3）返回计数器的值。［算法

2-17］2.4.2单链表的基本操作7.清空链表（1）算法思想：将头指针设置为None，从而释放所有结点。（2）算法步骤：将头指针设置为None。［算法2-18］

以上是单链表的一些基本操作及其算法思想、算法步骤和代码实现。通过这些操作，可以对单链表进行各种常见的操作，如插入、删除、搜索、打印和获取长度等。2.4.3循环链表

循环链表是一种特殊的数据结构，它通过改变链表中最后一个结点的指针域，使其指向头结点，从而形成一个闭环结构。这种结构使得从链表中任意一个结点出发，都可以遍历整个链表，而不必像普通链表那样需要从头开始遍历。图

2-12呈现了单向循环链表的两种关键状态：在非空表状态下，链表由头结点及多个数据结点（a0至an-1）构成，每个结点均包含数据域与指针域，其中末尾数据结点的指针域回指头结点形成闭环，从而支持从任意结点出发完整遍历整个链表；在空表状态下，仅存在头结点且其指针域直接指向自身，通过此自循环结构明确标识链表为空，无须依赖额外标记，有效简化了空表判断逻辑。图2-12单向循环链表2.4.3循环链表循环单链表的操作与单链表类似，差别仅在于：当遍历链表时，判别当前指针p是否指向表尾结点的终止条件不同。在单链表中，判别条件为p

is

not

None或p.next

is

not

None，而循环单链表的判别条件为p!=self.head或p.next!=self.head。在循环链表结构中从表中任一结点出发均可找到表中的其他结点。如果从头指针出发，访问链表的最后一个结点，则必须扫描表中的所有结点。若把循环链表的表头指针改用尾指针代替，则从尾指针出发，不仅可以立即访问最后一个结点，而且可十分方便地找到第一个结点，如图

2-13所示。设rear为循环链表的尾指针，则开始结点a0的存储位置为self.rear.next。图2-13

尾指针的循环链2.4.3循环链表在实际应用中，经常采用尾指针描述的循环链表，例如，将两个循环链表合并为一个新的循环链表，具体步骤为：（1）找到第一个链表（A）的尾结点tailA和第二个链表（B）的尾结点tailB；（2）将tailA.next指向B的头结点，将tailB.next指向A的头结点，形成新的闭环。操作过程如图2-14所示，图2-14（a）为合并前的两个循环链表，图2-14（b）为合并后新的循环链表。图2-14

循环链表合并示意图2.4.4双向链表双向链表由一系列结点组成，每个结点除了存储数据元素外，还包含两个指针：一个指针指向前一个结点（通常称为前驱指针），另一个指针指向后一个结点（通常称为后继指针）。结点结构如图2-15（a）所示，双向链表也可以是循环链表，其结构如图2-15（b）所示。这使得双向链表可以在两个方向上进行遍历，既可以从表头到表尾，也可以从表尾到表头，相比单向链表，双向链表在某些操作上更具灵活性，如删除结点、插入结点等操作，无须像单向链表那样只有先找到前驱结点才能进行相关操作。图2-15双向循环链表示意图2.4.4双向链表在Python中，可以使用类来定义双向链表的结点结构。一个典型的双向链表结点包含三个属性：数据、指向前一个结点的指针和指向后一个结点的指针。以下是一个示例代码，展示了如何用Python类来描述双向链表的结点结构：2.4.4双向链表在这个示例中，我们定义了一个DoublyLinkedListNode类，其中包含三个属性：（1）data：用于存储结点的数据；（2）prev：指向前一个结点的指针，初始值为None；（3）next：指向后一个结点的指针，初始值为None。2.4.4双向链表双向链表可以从两个方向搜索某个结点，这使得链表的某些操作变得比较简单，下面主要介绍插入和删除两种操作。1.在指定结点前插入结点在双向链表中，插入一个新结点到指定结点p之前的过程涉及4个步骤，如图2-16所示。2.4.4双向链表（1）算法步骤：1）创建新结点：首先，创建一个包含数据的新结点s；2）更新新结点的指针：-将新结点s的next指针指向结点p；-将新结点s的prev指针指向结点p的前一个结点（即p.prev）。3）更新前一个结点的指针：如果结点p有前一个结点（即p.prev不为None），则将p.prev.next指向新结点s。4）更新结点p的指针：将结点p的prev指针指向新结点s2.4.4双向链表（2）算法描述：假设有一个双向链表，要在结点p前插入一个新结点s，具体步骤如下。1）创建新结点：s=DoublyLinkedListNode(data)其中，data是新结点的数据。2）更新新结点的指针：s.next=ps.prev=p.prev3）更新前一个结点的指针：ifp.previsnotNone:p.prev.next=s4）更新结点p的指针：p.prev=s2.4.4双向链表以下是完整的Python代码示例，展示了如何在双向链表中插入一个新结点。［算法2-20］2.4.4双向链表在这个示例中，我们在node2之前插入了一个数据为0的新结点，并打印了整个链表以验证插入操作是否正确。2.4.4双向链表2.删除指定结点删除双向链表中的某个结点

p，如图

2-17所示。图2-17

在双向链表中删除一个结点2.4.4双向链表可以通过以下步骤实现：（1）检查p是否为None。如果是，则直接返回，因为不存在要删除的结点。（2）检查p是否有前驱结点（即p.prev是否为None）。如果有，则更新前驱结点的next指针指向p的后继结点；如果没有，则说明p是头结点，需要更新链表的头指针。（3）检查p是否有后继结点（即p.next是否为None）。如果有，则更新后继结点的prev指针指向p的前驱结点；如果没有，则说明p是尾结点，需要更新链表的尾指针。（4）将p的prev指针和next指针设置为None，帮助存储资源回收。（5）如果需要，可以返回新的头结点或尾结点。2.4.4双向链表［算法

2-21］2.4.4双向链表2.4.4双向链表知行合一任务描述：

前面我们学习了线性表的顺序存储结构，采用顺序存储方式的线性表存储密度高，可以节约存储空间，并可以随机存取元素，但是在执行插入和删除操作时，往往需要移动大量的数据元素，时间效率较低且要预先分配空间，存储空间难以得到充分利用，空间利用率较低。因此，本节讨论线性表的另一种存储结构——链式存储结构，它能有效地克服顺序存储方式的不足，同时也能有效地实现线性表的动态扩充。本任务介绍了单链表、循环链表和双向链表，并以单链表作为任务实践对象，旨在让读者对线性表的链式存储结构和基本操作有一个初步的认识。任务目标：

能够创建链表；能够对链表进行插入、删除以及查询等操作。任务实施：在Python语言环境下，实现基于链式存储结构的线性表（单链表）的相关操作。