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

2023/7/20滨州学院信息工程系1数据结构概述数据结构基本概念22023/7/20

数据结构课程的地位它是计算机专业及相关专业的核心课程之一，是计算机及相关专业的重要骨干基础课程。它针对非数值计算的程序设计问题，研究计算机的操作对象以及它们之间的关系和操作。即其研究目的是研究有效地组织和处理非数值类型数据的理论、技术和方法。32023/7/20数据结构的核心研究内容数据的逻辑结构、存储结构及它们之间的关系和相应的基本操作运算的定义和实现。教材围绕数据结构的三种基本结构：线性结构（第2-5章）、树形结构（第6章）和图形结构（第7章）展开讨论，研究解决如下问题：一个具体问题的逻辑结构是什么？适宜选用什么样的存储结构？采用什么样的操作实现算法效率更高？42023/7/20学时数：96（64学时授课＋32学时上机）教材：严蔚敏编著，数据结构（C语言版），清华大学出版社52023/7/20章内容学时

章内容学时

1绪论47图82线性表88查找83栈和队列89排序104串45数组与广义表6上机326树和二叉树8合计96内容安排62023/7/20本节内容数据结构讨论的范畴数据结构中的基本概念72023/7/20NiklausWirth：

Algorithm

+DataStructures=Programs算法:数据结构:处理问题的策略问题的数学模型一、数据结构讨论的范畴82023/7/20概括地说：

数据结构是一门讨论“描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现”的学科。92023/7/201、问题举例

学生信息包括学号、姓名、性别、籍贯。建立一个学生档案，要求：查找“王红”是否存在。如何记录所有学生记录（及选择何种逻辑数据结构）？选择何种存储结构？若把所有记录依次存储在一个数组中——采用顺序存储结构若采用指针链表——采用链式存储结构102023/7/20学生信息管理系统计算机处理的对象是表元素间的关系是线性关系施加于对象上的操作常见有查询、插入、删除等112023/7/20n皇后问题oooxxxoooxooxxooxxxooxoooxxoooxxoooxxxooxooxoo122023/7/20N皇后问题

计算机处理的对象是树形结构元素间的关系是层次关系施加于对象上的操作有查询、插入、删除等132023/7/20

胜利

发生疫情的五个村子河源长利太华桦南1275344123

村子联系网络图v1v5v2v4v31275413432已知五个村子发生了疫情，由一人将疫苗送达到5个村庄。目标是寻找一条耗时最少的路线。142023/7/20快速送达疫苗计算机处理的对象是图元素间的关系是复杂的图形或网状关系施加于对象上的操作有查询、插入、删除等152023/7/202、数据结构研究的范畴由以上三个例子可见，描述这类非数值计算问题的数学模型不再是数学方程，而是诸如表、树、图之类的数据结构。因此，简单说来，数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科。162023/7/203、数据结构课程的特点数据结构是介于数学、计算机硬件和计算机软件之间的一门计算机科学与技术专业的核心课程，是编译原理、操作系统、数据库、人工智能等课程的基础。同时，数据结构技术也广泛应用于信息科学、系统工程、应用数学以及各种工程技术领域。172023/7/20数据结构课程特点（续）数据结构课程集中讨论软件开发过程中的设计阶段、同时涉及编码和分析阶段的若干基本问题。此外，为了构造出好的数据结构及其实现，还需考虑数据结构及其实现的评价与选择。因此，数据结构的内容包括三个层次的五个“要素”，如下图所示：182023/7/20方面层次

数据表示数据处理

抽象

逻辑结构基本运算

实现

存储结构

算法

评价不同结构的比较及算法分析数据结构课程内容体系192023/7/204、学习的目的程序设计＝好算法＋好结构计算机内的数值问题依靠方程，而非数值问题（如表、树、图等）则要依靠数据结构。202023/7/205、学习目标对每个数据结构加强对存在代价与效益的观念掌握常用的数据结构——将常用的数据结构放入你的工具包理解怎样去衡量一个数据结构或程序的代价212023/7/20

重基础(牢固准确掌握)讲实际(实现、分析算法)

上课认真听讲、适当做好笔记，认真独立完成作业做好预习和及时复习；课后需要多读教材和参考书，查看相关内容，在理解基本内容的基础上，勤思考多练习上机实验十分重要，一定要在上机前做好充分准备，多采用不同的数据存储结构和不同的实现算法解决同一个问题。6、怎样学习数据结构222023/7/20二、数据结构中的基本概念数据与数据结构数据类型抽象数据类型232023/7/201、数据与数据结构数据：数据是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合。是计算机操作的对象的总称。数据元素：是数据的基本单位，具有完整确定的实际意义。在程序中常作为一个整体进行考虑和处理。一个数据元素可由若干个数据项组成。242023/7/20数据项：是数据不可分割的最小单位，是构成数据元素的项目。数据对象：数据的子集。具有相同性质的数据成员（数据元素）的集合。整数数据对象N={0,1,2,…}字母字符数据对象C={‘A’,’B’,……‘Z’}252023/7/20数据结构：是相互之间存在一种或多种特定关系的数据元素的集合带结构的数据元素的集合262023/7/20线性结构树形结构图状结构集合结构常见的数据结构272023/7/20数据结构的表示二元组表示Data_Structures=(D,S)其中:D是数据元素的有限集，

S是D上关系的有限集。282023/7/20

例：设计一数据结构表示复数，并给出其二元组定义。

复数由实部和虚部构成（构成元素），两者之间存在着一种次序关系（逻辑关系）。可以表示为：

Complex=(C,R)

其中,C={c1,c2}、R={<c1,c2>}说明:<>表示有序数对，用图示法表示时画箭头；()表示无序数对，用图示法表示时画线段。292023/7/20数据的存储结构逻辑结构在存储器中的表示（映像）“元素”的映像“关系”的映像302023/7/20元素的映像方法用二进制位串存储数据元素312023/7/20关系的映像方法即如何表示<x,y>，习惯称为前驱后继关系顺序映像：用存储位置的关系表示前驱后继关系链式映像：用附加信息（指针）表示前驱后继关系322023/7/20

当用某种高级程序设计语言进行编程时，通常可用该语言中提供的数据类型描述之。两种常见存储方法比较顺序映像：占用最少的存储空间，但易产生较多碎片链式映像：不会产生碎片，但占用空间较多（包含线索信息）332023/7/20集合结构：仅同属一个集合线性结构:一对一（1:1)

树结构:一对多（1:n)

图结构:多对多(m:n)非线性线性重点概念分析解释1：什么叫数据的逻辑结构？答：指数据元素之间的逻辑关系。即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。342023/7/20（1）S=(D,R)D={a,b,c,d,e,f}R={(a,e),(b,c),(c,a),(e,f),(f,d)}解：上述表达式可用图形表示为：bcaefd此结构为线性的。

用图形表示下列数据结构，并指出它们是属于线性结构还是非线性结构。举例352023/7/20

d1d5d2d4d3该结构是非线性（图状）的。解：上述表达式可用图形表示为：（2）S=(D,R)

D={di|1≤i≤5}

R={(di,dj),i<j}362023/7/20解释2：什么叫数据的物理结构？答：物理结构亦称存储结构，是数据的逻辑结构在计算机存储器内的表示（或映像），它依赖于计算机。

存储结构可分为4大类：顺序、链式、索引、散列。重点概念分析372023/7/20

不同类型的变量，其取值范围不同，所能进行的操作（运算）不同。2、数据类型

在用高级程序语言编写的程序中，必须对程序中出现的每个变量、常量或表达式，明确说明它们所属的数据类型。

定义：一组性质相同的值的集合,以及定义于这个值集合上的一组操作的总称.382023/7/20答：在数据的逻辑结构上定义的操作算法。它在数据的存储结构上实现。最常用的数据运算有5种：插入、删除、修改、查找、排序解释3：什么是数据的运算？392023/7/20

数据结构涵盖的内容402023/7/203、抽象数据类型抽象数据类型（AbstractDataTypeADT）是一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部的使用。412023/7/20(1)抽象数据类型的特点

由用户定义，用以表示应用问题的数据模型由基本的数据类型组成,并包括一组相关的服务（或称操作）信息隐蔽和数据封装，使用与实现相分离422023/7/20(2)抽象数据类型的表示抽象数据类型可用（D，S，P）三元组表示。其中：D是数据对象；

S是D上的关系集；

P是对D的基本操作集432023/7/20其中基本操作的定义格式为:基本操作名（参数表）初始条件：〈初始条件描述〉

操作结果：〈操作结果描述〉

一般定义格式ADT抽象数据类型名{

数据对象：〈数据对象的定义〉

数据关系：〈数据关系的定义〉

基本操作：〈基本操作的定义〉}ADT抽象数据类型名442023/7/20说明赋值参数

只为操作提供输入值。引用参数

以&打头，除可提供输入值外，还将返回操作结果。初始条件

描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。操作结果

说明了操作正常完成之后，数据结构的变化状况和应返回的结果。若初始条件为空，则省略之。452023/7/20

数据对象：

D＝{e1,e2｜e1,e2∈RealSet}

数据关系：

R1＝{<e1,e2>|e1是复数的实数部分

|e2是复数的虚数部分}ADTComplex{ADT定义举例例如，抽象数据类型复数的定义：462023/7/20基本操作：

AssignComplex(&Z,v1,v2)操作结果：构造复数Z,其实部和虚部分别被赋以参数v1和v2的值。

DestroyComplex(&Z)操作结果：复数Z被销毁。

GetReal(Z,&realPart)初始条件：复数已存在。操作结果：用realPart返回复数Z的实部值。472023/7/20

GetImag(Z,&ImagPart)初始条件：复数已存在。操作结果：用ImagPart返回复数Z的虚部值。

Add(z1,z2,&sum)初始条件：z1,z2是复数。操作结果：用sum返回两个复数z1,z2的和。

}ADTComplex482023/7/20则Add(z1,z2,z3)操作的结果即为用户企求的结果，即z3=是z1和z2的和假设:z1和z2是上述定义的复数492023/7/20抽象数据类型与数据类型的区别

它与数据类型实质上是一个概念，但其特征是使用与实现分离，实行封装和信息隐蔽（独立于计算机）502023/7/20

例如，对以上定义的Complex，可有如下实现：(3)抽象数据类型的实现抽象数据类型需要通过固有数据类型(高级编程语言中已实现的数据类型)来实现。512023/7/20typedefstruct{

floatrealpart；

floatimagpart；}complex；//-----存储结构的定义//-----基本操作的函数原型说明void

Assign(complex&Z,floatrealval,floatimagval)；//

构造复数Z,其实部和虚部分别被赋以参数//realval

和imagval

的值522023/7/20floatGetReal(cpmplexZ)；

//返回复数Z的实部值float

Getimag(cpmplexZ)；

//返回复数Z的虚部值voidadd(co