第一讲-数据结构基本概念

1、数据结构数据结构2022-2-25滨州学院信息工程系1数据结构概述数据结构概述数据结构基本概念数据结构基本概念22022-2-25 数据结构课程的地位数据结构课程的地位n它是计算机专业及相关专业的它是计算机专业及相关专业的核心课程核心课程之一，之一，是计算机及相关专业的是计算机及相关专业的重要骨干基础课程重要骨干基础课程。n它针对它针对非数值计算非数值计算的程序设计问题，研究的程序设计问题，研究计算计算机的操作对象以及它们之间的关系和操作机的操作对象以及它们之间的关系和操作。即。即其研究目的是研究有效地组织和处理非数值类其研究目的是研究有效地组织和处理非数值类型数据的理论、技术和方法。型数据的

2、理论、技术和方法。32022-2-25数据结构的核心研究内容数据结构的核心研究内容n数据的逻辑结构、存储结构及它们之间的关数据的逻辑结构、存储结构及它们之间的关系和相应的基本操作运算的定义和实现。系和相应的基本操作运算的定义和实现。n教材围绕数据结构的三种基本结构：线性结教材围绕数据结构的三种基本结构：线性结构（第构（第2-5章）、树形结构（第章）、树形结构（第6章）和图形章）和图形结构（第结构（第7章）展开讨论，研究解决如下问章）展开讨论，研究解决如下问题：题：一个具体问题的逻辑结构是什么？适宜一个具体问题的逻辑结构是什么？适宜选用什么样的存储结构？采用什么样的操作选用什么样的存储结构？采用

3、什么样的操作实现算法效率更高？实现算法效率更高？42022-2-25学时数：学时数：96（64学时授课学时授课32学时上机）学时上机） 教材：严蔚敏编著，数据结构（教材：严蔚敏编著，数据结构（C语言版），语言版），清华大学出版社清华大学出版社52022-2-25章内 容 学时 章 内 容 学时 1绪 论47图82线性表88查找83栈和队列89排序104串45数组与广义表6上机326树和二叉树 8合计96内容安排内容安排62022-2-25本节内容本节内容n数据结构讨论的范畴数据结构讨论的范畴n数据结构中的基本概念数据结构中的基本概念72022-2-25Niklaus Wirth： Algori

4、thm + Data Structures = Programs算法算法: 数据结构数据结构: 处理问题的策略处理问题的策略问题的数学模型问题的数学模型一、数据结构讨论的范畴一、数据结构讨论的范畴82022-2-25概括地说：概括地说： 数据结构是一门讨论数据结构是一门讨论“描述现实世界描述现实世界实体的数学模型实体的数学模型(非数值计算非数值计算)及其上的及其上的操作在计算机中如何表示和实现操作在计算机中如何表示和实现”的的学科。学科。92022-2-251、问题举例、问题举例 学生信息包括学号、姓名、性别、籍贯。建学生信息包括学号、姓名、性别、籍贯。建立一个学生档案，要求：查找立一个学生档

5、案，要求：查找“王红王红”是否存在。是否存在。如何记录所有学生记录（及选择何种逻辑数如何记录所有学生记录（及选择何种逻辑数据结构）？据结构）？选择何种存储结构？选择何种存储结构？v若把所有记录依次存储在一个数组中若把所有记录依次存储在一个数组中采采用顺序存储结构用顺序存储结构v若采用指针链表若采用指针链表采用链式存储结构采用链式存储结构102022-2-25学生信息管理系统学生信息管理系统n计算机处理的对象是表计算机处理的对象是表n元素间的关系是线性关系元素间的关系是线性关系n施加于对象上的操作常见有查询、插施加于对象上的操作常见有查询、插入、删除等入、删除等112022-2-25n皇后问题皇

6、后问题oooxxxoooxooxx ooxxxooxoooxxooo xxoooxxxoox ooxoo122022-2-25N皇后问题皇后问题 n计算机处理的对象是树形结构计算机处理的对象是树形结构n元素间的关系是层次关系元素间的关系是层次关系n施加于对象上的操作有查询、插入、施加于对象上的操作有查询、插入、删除等删除等132022-2-25 胜利胜利 发生疫情的五个村子发生疫情的五个村子河源河源长利长利太华太华桦南桦南1275344123 村子联系网络图村子联系网络图v1v5v2v4v31275413432已知五个村子发生了疫情，由一人将疫已知五个村子发生了疫情，由一人将疫苗送达到苗送达到

7、5个村庄。目标是寻找一条耗个村庄。目标是寻找一条耗时最少的路线。时最少的路线。142022-2-25快速送达疫苗快速送达疫苗n计算机处理的对象是图计算机处理的对象是图n元素间的关系是复杂的图形或网状关元素间的关系是复杂的图形或网状关系系n施加于对象上的操作有查询、插入、施加于对象上的操作有查询、插入、删除等删除等152022-2-252、数据结构研究的范畴、数据结构研究的范畴n由以上三个例子可见，描述这类非数由以上三个例子可见，描述这类非数值计算问题的数学模型不再是数学方值计算问题的数学模型不再是数学方程，而是诸如表、树、图之类的数据程，而是诸如表、树、图之类的数据结构。结构。n因此，简单说来

8、，因此，简单说来，数据结构是一门研数据结构是一门研究究非数值计算非数值计算的程序设计问题中计算的程序设计问题中计算机的机的操作对象操作对象以及它们之间的以及它们之间的关系关系和和操作操作的学科。的学科。162022-2-253、数据结构课程的特点、数据结构课程的特点w数据结构是介于数据结构是介于数学、计算机硬件数学、计算机硬件和计算机软件和计算机软件之间的一门计算机科之间的一门计算机科学与技术专业的学与技术专业的核心核心课程，是编译课程，是编译原理、操作系统、数据库、人工智原理、操作系统、数据库、人工智能等课程的基础。能等课程的基础。w 同时，数据结构技术也广泛应用同时，数据结构技术也广泛应用

9、于信息科学、系统工程、应用数学于信息科学、系统工程、应用数学以及各种工程技术领域。以及各种工程技术领域。172022-2-25数据结构课程特点（续）数据结构课程特点（续）w数据结构课程集中讨论软件开发过程数据结构课程集中讨论软件开发过程中的中的设计阶段设计阶段、同时涉及、同时涉及编码和分析编码和分析阶段阶段的若干基本问题。此外，为了构的若干基本问题。此外，为了构造出好的数据结构及其实现，还需考造出好的数据结构及其实现，还需考虑虑数据结构及其实现的评价与选择数据结构及其实现的评价与选择。w因此，数据结构的内容包括三个层次因此，数据结构的内容包括三个层次的五个的五个“要素要素”，如下图所示：，如下

10、图所示：182022-2-25方面方面 层次层次 数据表示数据表示 数据处理数据处理 抽象抽象 逻辑结构逻辑结构基本运算基本运算 实现实现 存储结构存储结构 算法算法 评价评价不同结构的比较及算法分析不同结构的比较及算法分析数据结构课程内容体系数据结构课程内容体系192022-2-254、学习的目的、学习的目的n计算机内的数值问题依靠方程，而非计算机内的数值问题依靠方程，而非数值问题（如表、树、图等）则要依数值问题（如表、树、图等）则要依靠数据结构。靠数据结构。202022-2-255、学习目标、学习目标n对每个数据结构加强对存在代价与效益对每个数据结构加强对存在代价与效益的观念的观念n掌握常

11、用的数据结构掌握常用的数据结构将常用的数据将常用的数据结构放入你的工具包结构放入你的工具包n理解怎样去衡量一个数据结构或程序的理解怎样去衡量一个数据结构或程序的代价代价212022-2-25 重基础重基础( (牢固准确掌握牢固准确掌握) )讲实际讲实际( (实现、分析算法实现、分析算法) ) p上课认真听讲、适当做好笔记，认真独立完成上课认真听讲、适当做好笔记，认真独立完成作业作业p做好预习和及时复习；做好预习和及时复习；p课后需要多读教材和参考书，查看相关内容，课后需要多读教材和参考书，查看相关内容，在理解基本内容的基础上，勤思考多练习在理解基本内容的基础上，勤思考多练习p上机实验十分重要，

12、一定要在上机前做好充分上机实验十分重要，一定要在上机前做好充分准备，多采用不同的数据存储结构和不同的实准备，多采用不同的数据存储结构和不同的实现算法解决同一个问题。现算法解决同一个问题。6、怎样学习数据结构、怎样学习数据结构222022-2-25二、数据结构中的基本概念二、数据结构中的基本概念n数据与数据结构数据与数据结构n数据类型数据类型n抽象数据类型抽象数据类型232022-2-251、数据与数据结构、数据与数据结构n数据：数据是信息的载体，是描述客观事数据：数据是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机物的数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符

13、号的集中，被计算机程序识别和处理的符号的集合。合。是计算机操作的对象的总称。是计算机操作的对象的总称。 n数据元素：数据元素：是数据的基本单位，是数据的基本单位，具有完整具有完整确定的实际意义。在程序中常作为一个整确定的实际意义。在程序中常作为一个整体进行考虑和处理。一个数据元素可由若体进行考虑和处理。一个数据元素可由若干个数据项组成。干个数据项组成。242022-2-25n数据项：数据项：是数据不可分割的最小单是数据不可分割的最小单位位，是构成数据元素的项目。，是构成数据元素的项目。n数据对象：数据对象：数据的子集。具有相同数据的子集。具有相同性质的数据成员（数据元素）的集性质的数据成员（数

14、据元素）的集合。合。整数数据对象整数数据对象 N = 0, 1, 2, 字母字符数据对象字母字符数据对象C= A,B,Z252022-2-25n数据结构：是相互之间存在一种或多种数据结构：是相互之间存在一种或多种特定关系的数据元素的集合特定关系的数据元素的集合n 带带结构结构的数据元素的集合的数据元素的集合262022-2-25线性线性结构结构树形结构树形结构图状结构图状结构集合结构集合结构常见的数据结构常见的数据结构272022-2-25数据结构的表示数据结构的表示n二元组表示二元组表示Data_Structures = (D, S)其中其中: D 是数据元素的有限集数据元素的有限集， S

15、是 D上关系的有限集关系的有限集。282022-2-25 例：设计一数据结构表示复数，并给出例：设计一数据结构表示复数，并给出其二元组定义。其二元组定义。 复数由实部和虚部构成（构成元素），复数由实部和虚部构成（构成元素），两者之间存在着一种次序关系（逻辑关两者之间存在着一种次序关系（逻辑关系）。系）。 可以表示为：可以表示为： Complex = (C, R) 其中其中, C = c1, c2 、 R= 说明说明:表示有序数对，用图示法表示时表示有序数对，用图示法表示时画箭头；画箭头； ( )表示无序数对，用图示法表示表示无序数对，用图示法表示时画线段。时画线段。292022-2-25数据的

16、存储结构数据的存储结构n逻辑结构在存储器中的表示（映像）逻辑结构在存储器中的表示（映像）“元素元素”的映像的映像“关系关系”的映像的映像302022-2-25元素的映像方法元素的映像方法n用二进制位串存储数据元素用二进制位串存储数据元素312022-2-25关系的映像方法关系的映像方法n即如何表示即如何表示，习惯称为前驱后，习惯称为前驱后继关系继关系顺序映像：用存储位置的关系表示顺序映像：用存储位置的关系表示前驱后继关系前驱后继关系链式映像：用附加信息（指针）表链式映像：用附加信息（指针）表示前驱后继关系示前驱后继关系322022-2-25 当用某种高级程序设计语言进行编程时，通当用某种高级程

17、序设计语言进行编程时，通常可用该语言中提供的数据类型描述之。常可用该语言中提供的数据类型描述之。两种常见存储方法比较两种常见存储方法比较n顺序映像：占用最少的存储空间，但顺序映像：占用最少的存储空间，但易产生较多碎片易产生较多碎片n链式映像：不会产生碎片，但占用空链式映像：不会产生碎片，但占用空间较多（包含线索信息）间较多（包含线索信息）332022-2-25集合结构：集合结构： 仅同属一个集合仅同属一个集合线性结构线性结构: 一对一（一对一（1:1) 树树 结结 构构: 一对多（一对多（1:n) 图图 结结 构构: 多对多多对多 (m:n)非线性非线性线线 性性重点概念分析重点概念分析n解释

18、解释1： 什么叫数据的逻辑结构？什么叫数据的逻辑结构？答：指数据元素之间的逻辑关系。即从逻答：指数据元素之间的逻辑关系。即从逻辑关系上描述数据，它辑关系上描述数据，它与数据的存储无与数据的存储无关，是独立于计算机关，是独立于计算机的。的。342022-2-25（1） S=(D, R) D= a, b, c, d, e, f R=(a,e), (b,c), (c,a), (e,f), (f,d)解：解： 上述表达式可用图形表示为：上述表达式可用图形表示为：b c a e f d此结构为此结构为线性线性的。的。 用图形表示下列数据结构，并指出它们用图形表示下列数据结构，并指出它们是属于线性结构还是

19、非线性结构。是属于线性结构还是非线性结构。举例举例352022-2-25 d1 d5 d2 d4 d3该结构该结构是非线性（图状）是非线性（图状）的。的。解：上述表达式可用图形表示为：解：上述表达式可用图形表示为：（2） S=(D, R) D=di | 1i5 R=(di , dj ), ij362022-2-25n解释解释2 2：什么叫数据的物理结构？：什么叫数据的物理结构？答：物理结构亦称答：物理结构亦称存储结构存储结构，是数据的，是数据的逻辑结构在计算机存储器内的表示（或逻辑结构在计算机存储器内的表示（或映像），它映像），它依赖于计算机依赖于计算机。 存储结构可分为存储结构可分为4 4大

20、类：大类：顺序、链式、索引、顺序、链式、索引、散列。散列。重点概念分析重点概念分析372022-2-25 不同类型的变量，其取值范围不同，所能不同类型的变量，其取值范围不同，所能进行的操作（运算）不同。进行的操作（运算）不同。2、数据类型、数据类型n 在用高级程序语言编写的程序中，必在用高级程序语言编写的程序中，必须对程序中出现的每个变量、常量或表须对程序中出现的每个变量、常量或表达式，明确说明它们所属的数据类型。达式，明确说明它们所属的数据类型。定义：定义：一组性质相同的值的集合一组性质相同的值的集合, , 以以及定义于这个值集合上的一组操作的总及定义于这个值集合上的一组操作的总称称. .3

21、82022-2-25答：在数据的逻辑结构上定义的操作算法。答：在数据的逻辑结构上定义的操作算法。它它在数据的存储结构上实现在数据的存储结构上实现。最常用的数据运算有最常用的数据运算有 5 种：种：插入、删除、修改、查找、排序插入、删除、修改、查找、排序解释解释3：什么是数据的运算？：什么是数据的运算？392022-2-25 数据结构涵盖的内容数据结构涵盖的内容402022-2-253、抽象数据类型、抽象数据类型n抽象数据类型抽象数据类型（Abstract Data Type ADT ）是一个数学模型以及定义在该）是一个数学模型以及定义在该模型上的一组操作。模型上的一组操作。 n 抽象数据类型的

22、定义取决于它的一组抽象数据类型的定义取决于它的一组逻辑特性，而逻辑特性，而与其在计算机内部如何与其在计算机内部如何表示和实现无关表示和实现无关。即不论其内部结构。即不论其内部结构如何变化，只要它的数学特性不变，如何变化，只要它的数学特性不变，都不影响其外部的使用。都不影响其外部的使用。412022-2-25(1) 抽象数据类型的特点抽象数据类型的特点由用户定义，用以表示应用问题的数由用户定义，用以表示应用问题的数据模型据模型基本的数据类型基本的数据类型组成组成, , 并包括并包括一组一组相关的服务（或称操作）相关的服务（或称操作）n 信息隐蔽信息隐蔽和和数据封装数据封装使用与实现相使用与实现相

23、分离分离422022-2-25(2) 抽象数据类型的表示抽象数据类型的表示n抽象数据类型可用（抽象数据类型可用（D，S，P）三元）三元组表示组表示。n其中：其中：D 是数据对象；是数据对象； S 是是 D 上的关系集；上的关系集； P 是对是对 D 的基本操作集的基本操作集432022-2-25n其中其中基本操作基本操作的定义格式为的定义格式为: :基本操作名（参数表）基本操作名（参数表） 初始条件：初始条件：初始条件描述初始条件描述 操作结果：操作结果：操作结果描述操作结果描述 一般定义格式一般定义格式ADT 抽象数据类型名抽象数据类型名 数据对象：数据对象：数据对象的定义数据对象的定义 数

24、据关系：数据关系：数据关系的定义数据关系的定义 基本操作：基本操作：基本操作的定义基本操作的定义 ADT 抽象数据类型名抽象数据类型名442022-2-25说明说明n赋值参数赋值参数 只为操作提供输入值。只为操作提供输入值。n引用参数引用参数 以以&打头，除可提供输入值外，还打头，除可提供输入值外，还将返回操作结果。将返回操作结果。n初始条件初始条件 描述了操作执行之前数据结构和参描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，数应满足的条件，若不满足，则操作失败，并返回相应出错信息。并返回相应出错信息。n操作结果操作结果 说明了操作正常完成之后，数据结说明了操作正

25、常完成之后，数据结构的变化状况和应返回的结果。若初始条件构的变化状况和应返回的结果。若初始条件为空，则省略之。为空，则省略之。452022-2-25 数据对象：数据对象： De1,e2e1,e2RealSet 数据关系：数据关系： R1 | e1是复数的实数部分是复数的实数部分 | e2 是复数的虚数部分是复数的虚数部分 ADT Complex ADT定义举例定义举例n例如，抽象数据类型复数的定义：例如，抽象数据类型复数的定义：462022-2-25基本操作：基本操作： AssignComplex( &Z, v1, v2 )操作结果：构造复数操作结果：构造复数 Z,Z,其实部和虚部其实

26、部和虚部 分别被赋以参数分别被赋以参数 v1 v1 和和 v2 v2 的值。的值。 DestroyComplex( &Z)操作结果：复数操作结果：复数Z Z被销毁。被销毁。 GetReal( Z, &realPart )初始条件：复数已存在。初始条件：复数已存在。操作结果：用操作结果：用realPart返回复数返回复数Z Z的实部值。的实部值。472022-2-25 GetImag( Z, &ImagPart )初始条件：复数已存在。初始条件：复数已存在。操作结果：用操作结果：用ImagPart返回复数返回复数Z Z的虚部值。的虚部值。 Add( z1,z2, &

27、;sum )初始条件：初始条件：z1, z2是复数。是复数。操作结果：用操作结果：用sum返回两个复数返回两个复数z1, z2 的和。的和。 ADT Complex482022-2-25则则 Add(z1, z2, z3) 操作的结果操作的结果即为用户企求的结果，即即为用户企求的结果，即z3 =是是z1 和和 z2的和的和假设假设: z1和和z2是上述定义的复数是上述定义的复数492022-2-25抽象数据类型与数据类型的区别抽象数据类型与数据类型的区别 它与数据类型实质上是一个概它与数据类型实质上是一个概念，但其特征是念，但其特征是与与，实行实行和和（独立于计算（独立于计算机）机）502022-2-25 例如，对以上定义的例如，对以上定义的Complex，可有，可有如下实现：如下实现：(3) 抽象数据类型的实现抽象数据类型的实现n抽象数据类型需要通过固有数据类型抽象数据类型需要通过固有数据类型( (高级编程语言中已实现的数据类型高级编程语言中已实现的数据类型) )来实现。来实现。512022-2-25typedef struct float realpart； float imagpart；complex；/ -存储结构的定义存储结构的