数据结构[Python 语言描述]全套教学课件.pptx

数据结构[Python语言描述]全套可编辑PPT课件

第1章绪论第2章线性表第3章栈和队列第4章串目录第5章数组和广义表第6章树和二叉树第7章图第8章查找第9章排序

第1章绪论

绪 论本章导读早期的计算机主要用于数值计算，到20世纪中叶后，逐渐扩展到对非数值的计算，它所处理的对象越来越多，包括图像、视频、表格等具有一定结构的数据。如何合理地组织这些数据，并对它们进行高效的处理，就是“数据结构”主要研究的内容。本章首先介绍数据结构的基本概念和术语，然后介绍数据的逻辑结构和存储结构，接着介绍抽象数据类型的概念，最后介绍算法和算法分析的相关知识。第1章

绪 论知识目标第1章 熟悉数据结构的基本概念和术语。 理解数据的逻辑结构、存储结构和抽象数据类型等概念。 了解算法的定义、特性、描述方法和设计要求。 了解算法性能评价的重要指标。

绪 论技能目标第1章 能针对实际问题设计出较高质量的算法，并使用多种方法进行描述。 能分析简单算法的时间复杂度和空间复杂度。

绪 论素质目标第1章 学习楷模事迹，汲取开拓创新、无私奉献的榜样力量。 通过对算法的改进，培养科学严谨、精益求精的工匠精神。

Content第1章逻辑结构和存储结构基本概念和术语抽象数据类型算法和算法分析

1.1基本概念和术语第1章数据分析入门

1.1基本概念和术语1．数据数据（data）是客观事物的符号表示，在计算机科学中，是指所有能被计算机程序识别、存储、加工和处理的符号的总称，它是计算机程序加工的“原料”。对计算机科学而言，数据的含义极为广泛，如图像、声音等都可以通过编码而归之于数据的范畴。例如，一个利用数值分析方法求解代数方程的程序，其处理的整数和实数都是数据；一个编译程序或文字处理程序，其处理的字符串也是数据。2．数据元素数据元素（dataelement）是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。数据元素又称为元素或记录，如表1-1（详见教材）所示的学生基本信息表中，每个学生的信息就是一个数据元素。

为便于理解数据结构中基本概念和术语的含义，下面以表1-1中的数据为例，进一步描述数据元素、数据项及数据对象之间的关系，如下图所示。高手点拨1.1基本概念和术语

1.1基本概念和术语3．数据项数据项（dataitem）是组成数据元素的、有独立含义的、不可再分的最小单位，如学生基本信息表中的学号、姓名等。4．数据对象数据对象（dataobject）是性质相同的有限个数据元素的集合，是数据的一个子集。例如，集合N={2,4,6,8,10}是整数的一个数据对象，集合C={a,b,c,d,e}是小写字母的一个数据对象。5．数据结构数据结构（datastructure）是相互之间存在一种或多种关系的数据元素的集合。结构就是指数据元素之间的相互关系，因此，可以将数据结构看作带结构的数据元素的集合，如下图所示。

1.2逻辑结构和存储结构第1章数据分析入门

1.2逻辑结构和存储结构数据的逻辑结构是指数据元素之间逻辑关系的描述，它与数据的存储无关，独立于计算机，是从具体问题抽象出来的数学模型。根据数据元素之间关系的不同，可分为4种不同的逻辑结构，如下图所示。1.2.1逻辑结构

1.2逻辑结构和存储结构（1）集合结构的数据元素之间只有属于同一个集合的关系。例如，判断一个数字是否为整数，可以将所有整数看作一个集合结构。（2）线性结构的数据元素之间是一对一的关系。此时每个数据元素都有唯一的前驱元素（第一个元素除外）和唯一的后继元素（最后一个元素除外）。例如，由多节车厢组成的列车、排队买票人员、一叠盘子等都可以看作线性结构。（3）树形结构的数据元素之间是一对多的关系。例如，学校的组织结构、家族关系等都可以看作树形结构。（4）图形结构（也称网状结构）的数据元素之间是多对多的关系。此时每个数据元素都可以有多个前驱元素或后继元素。例如，城市公共交通网、计算机网络等都可以看作图形结构。

1.2逻辑结构和存储结构数据的存储结构（也称物理结构）是指数据元素在计算机中的存储表示，是逻辑结构在计算机中的实现。将数据元素存储到计算机时，通常既要存储各数据元素的数据项，又要存储数据元素之间的逻辑关系。根据数据元素之间的逻辑关系在计算机中的不同表示，可分为两种不同的存储结构，分别是顺序存储结构和链式存储结构。1.2.2存储结构

1.2逻辑结构和存储结构1．顺序存储结构顺序存储结构是指逻辑上相邻的数据元素，其物理位置（内存中的位置）也相邻，数据元素间的逻辑关系由存储单元的邻接关系体现。顺序存储结构是一种最基本的存储方法，通常借助程序设计语言中的数组来实现。假设表1-1中每