数据结构第一章

数据结构课件第一章第一页，共五十一页，编辑于2023年，星期三第一章绪论第二页，共五十一页，编辑于2023年，星期三1.1数据结构讨论的范畴1.2基本概念1.3算法和算法的量度第三页，共五十一页，编辑于2023年，星期三1.1

数据结构讨论的范畴NiklausWirth：

Algorithm

+DataStructures=Programs程序设计:算法:数据结构:为计算机处理问题编制一组指令集

处理问题的策略问题的数学模型第四页，共五十一页，编辑于2023年，星期三求一组(n个)整数中的最大值算法:?模型：？基本操作是“比较两个数的大小”取决于整数值的范围第五页，共五十一页，编辑于2023年，星期三非数值计算的程序设计问题例一:求一组(n个)整数中的最大值算法:?模型：？基本操作是“比较两个数的大小”取决于整数值的范围第六页，共五十一页，编辑于2023年，星期三0-技能1-火系2-冰系3-烈焰光环4-冰锥5-寒冰盾6-火焰弹根节点叶节点0123654(1)(3)(5)(4)(2)(7)(6)游戏设计中的数据结构应用示例树结构在游戏设计中的应用算法:?模型：？游戏规则树型结构第七页，共五十一页，编辑于2023年，星期三概括地说：

数据结构是一门讨论“描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现”的学科。第八页，共五十一页，编辑于2023年，星期三1.2基本概念一、数据与数据结构二、数据类型三、抽象数据类型第九页，共五十一页，编辑于2023年，星期三一、数据与数据结构所有能被输入到计算机中，且能被计算机处理的符号的集合。数据:是计算机操作的对象的总称是计算机处理的信息的某种特定的符号表示形式。是计算机化的信息。第十页，共五十一页，编辑于2023年，星期三是数据（集合）中的一个“个体”数据元素:是数据结构中讨论的基本单位第十一页，共五十一页，编辑于2023年，星期三

数据项：是数据结构中讨论的最小单位数据元素可以是数据项的集合例如：描述一个运动员的数据元素可以是称之为组合项数据项第十二页，共五十一页，编辑于2023年，星期三

数据对象：性质相同的数据元素的集合。是数据的一个子集。整数数据对象是集合N={0，±1，±2，…}，字母字符数据对象是集合C={′A′，′B′，…，′Z′}学号姓名性别籍贯出生年月住址101赵红玲女河北1983.11北京………………学籍表

数据项学籍表也可看作一个数据对象。由此可看出，不论数据元素集合是无限集（如整数集）、有限集（如字符集），还是由多个数据项组成的复合数据元素（如学籍表），只要性质相同，都是同一个数据对象。第十三页，共五十一页，编辑于2023年，星期三综上所述，再分析数据概念：

一、数据特点：1.可放入机器（与机器的关联性）2.可被加工（能被处理）二、数据构成：1.数据元素：组成数据的基本单位（与数据的关系是集合与个体）2.数据对象：性质相同的数据元素的集合（与数据的关系是集合与子集）第十四页，共五十一页，编辑于2023年，星期三数据结构：相互之间存在一种或多种特定关系的数据元素的集合。结构：数据元素不是孤立存在的，它们之间存在着某种关系，这种数据元素相互之间的关系称为结构。学校组织层次结构图第十五页，共五十一页，编辑于2023年，星期三数据结构：带结构的数据元素的集合假设用三个4位的十进制数表示一个含

12位数的十进制数。3214,6587,9345

─

a1(3214),a2(6587),a3(9345)则在数据元素a1、a2和a3之间存在着“次序”关系

a1,a2、a2,a33214，6587，9345a1a2a36587，3214，9345a2a1a3≠例如:第十六页，共五十一页，编辑于2023年，星期三

或者说，数据结构是相互之间存在着某种逻辑关系的数据元素的集合。可见，不同的“关系”构成不同的“结构”第十七页，共五十一页，编辑于2023年，星期三

数据结构一般包括以下三个方面的内容：数据的逻辑结构：数据元素之间的逻辑关系。数据的存储结构：数据元素及其关系在计算机存储器内的表示。数据的运算：对数据施加的操作。

按某种逻辑关系组织起来的一批数据，按一定的映象方式把它存放在计算机的存储器中，并在这些数据上定义了一个运算的集合，就叫做数据结构。第十八页，共五十一页，编辑于2023年，星期三数据的逻辑结构从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。分为两大类：线性结构：若结构是非空集，则有且仅有一个开始节点和一个终端节点，并且所有节点最多只有一个直接前驱和直接后继。如线性表是一个线性结构。非线性结构：一个节点可能有多个直接前驱和直接后继。如树和图都是非线性结构。第十九页，共五十一页，编辑于2023年，星期三数据的逻辑结构可归结为以下四类基本结构:线性结构树形结构图状结构集合结构第二十页，共五十一页，编辑于2023年，星期三

(1)集合结构：结构中的数据元素之间除了同属于一个集合的关系外，无任何其它关系。(2)线性结构：结构中的数据元素之间存在着一对一的线性关系。(3)树形结构：结构中的数据元素之间存在着一对多的层次关系。(4)图状结构或网状结构：结构中的数据元素之间存在着多对多的任意关系。

逻辑结构线性结构——线性表、栈、队、字符串、数组、广义表非线性结构——树、图第二十一页，共五十一页，编辑于2023年，星期三数据结构的形式定义为:数据结构是一个二元组Data_Structures=(D,S)其中:D是数据元素的有限集，

S是D上关系的有限集。第二十二页，共五十一页，编辑于2023年，星期三数据的存储结构（物理结构）

——

逻辑结构在计算机存储器中的映象（表示），是逻辑结构在计算机中的实现，它包括数据元素的表示和关系的表示。逻辑结构与存储结构的关系为：存储结构是逻辑关系的映象与元素本身的映象。逻辑结构是数据结构的抽象，存储结构是数据结构的实现，两者综合起来建立了数据元素之间的结构关系。第二十三页，共五十一页，编辑于2023年，星期三数据元素的映象方法：用二进制位(bit)的位串表示数据元素(321)10=(501)8=(101000001)2A=(101)8=(001000001)2位：计算机中表示信息的最小单位是二进制数的一位。位串：由若干位组合起来形成位串，用来表示数据元素。用一个字长的位串表示一个整数，用8位二进制数表示一个字符。第二十四页，共五十一页，编辑于2023年，星期三数据元素的映象数据元素在计算机中用位串来表示，称该位串为元素或结点，即元素或结点是数据元素在计算机中的映象。数据元素由若干个数据项组成时，位串中对应于各个数据项的子位串称为数据域。第二十五页，共五十一页，编辑于2023年，星期三关系的映象方法：（表示x,y的方法）顺序映象：以数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。整个存储结构中只含数据元素本身的信息xy第二十六页，共五十一页，编辑于2023年，星期三链式映象以附加信息(指针)表示数据元素之间的逻辑关系需要用一个和x在一起的附加信息指示y的存储位置yx指针：指示元素的存储地址。第二十七页，共五十一页，编辑于2023年，星期三二、数据类型在用高级程序语言编写的程序中，必须对程序中出现的每个变量、常量或表达式，明确说明它们所

属的数据类型。第二十八页，共五十一页，编辑于2023年，星期三例如，C语言中提供的基本数据类型有:整型int浮点型float字符型char逻辑型bool（C++语言）双精度型double实型（C++语言）第二十九页，共五十一页，编辑于2023年，星期三数据类型这个概念最早出现在高级程序设计语言中。高级程序设计语言引入整数、浮点数、双精度数、字符等，对计算机硬件来说是一种新的数据结构。计算机硬件系统不能直接处理如整数、浮点数、双精度数、字符等，需按一定规则把它们转换成二进制码来表示和处理。计算机能处理的数据类型只包括位、字节和字。计算机硬件对这些数据类型的操作通过编译器转化为机器语言的位、字节和字这些能接受的数据类型来实现操作。从高级程序设计语言使用者的角度看，数据类型实现了信息的屏蔽，将一切使用者不必了解的实现细节都封装在数据类型之中，实现了数据的抽象。第三十页，共五十一页，编辑于2023年，星期三

高级程序设计语言使用者在使用整数时，不需要了解整数在计算机内部是如何表示，整数运算是如何实现的。如intx=5,y=6,z;z=x+y;高级程序设计语言使用者只需要了解数学上整数求和的抽象操作含义，不需要了解其硬件的“位”操作如何进行。第三十一页，共五十一页，编辑于2023年，星期三一种数据类型显式或隐式地规定了这种数据类型变量、常量或表达式的取值范围和它们允许进行的操作集合。如C语言中的整型变量，有int，shortint，longint三种类型，各类型的取值范围不同，且视具体的计算机系统而定。在微机上，int和short都是16位，long是32位；在VAX750上，short16位，int和long都是32位。数据类型不同，在其上的操作也各不相同。第三十二页，共五十一页，编辑于2023年，星期三三、抽象数据类型

(AbstractDataType简称ADT)是指一个数学模型以及定义在此数学模型上的一组操作。第三十三页，共五十一页，编辑于2023年，星期三抽象数据类型抽象数据类型（ADT）是用户在数据类型基础上自己定义和实现的数据类型。类似于在计算机机器语言的位、字节和字的基础上引入整数、浮点数、双精度数、字符等数据类型，高级程序设计语言使用者可以在高级程序设计语言整数、浮点数、双精度数、字符等数据类型的基础上引入各种新的数据类型供自己或他人使用，从而使自己或他人的程序编制达到更高一级的数据抽象。由用户自己定义和实现的新的数据类型称为抽象数据类型。每种抽象数据类型都要有确切的数据元素集合的定义和所允许的操作集合的定义。第三十四页，共五十一页，编辑于2023年，星期三ADT有两个重要特征:数据抽象

用ADT描述程序处理的实体时，强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口（即外界使用它的方法）。数据封装

将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节。第三十五页，共五十一页，编辑于2023年，星期三抽象数据类型的描述方法抽象数据类型可用（D，S，P）三元组表示。其中：D是数据对象；

S是D上的关系集；P是对D的基本操作集。第三十六页，共五十一页，编辑于2023年，星期三ADT

抽象数据类型名{数据对象：〈数据对象的定义〉

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

基本操作：〈基本操作的定义〉}ADT抽象数据类型名其中基本操作的定义格式为:基本操作名（参数表）

初始条件：〈初始条件描述〉

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

第三十七页，共五十一页，编辑于2023年，星期三赋值参数只为操作提供输入值。引用参数以&打头，除可提供输入值外，还将返回操作结果。初始条件描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。操作结果说明了操作正常完成之后，数据结构的变化状况和应返回的结果。若初始条件为空，则省略之。第三十八页，共五十一页，编辑于2023年，星期三例如，抽象数据类型复数的定义：

数据对象：

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

数据关系：

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

|e2是复数的虚数部分}ADTComplex{第三十九页，共五十一页，编辑于2023年，星期三基本操作：

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

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

GetReal(Z,&realPart)初始条件：复数已存在。操作结果：用realPart返回复数Z的实部值。第四十页，共五十一页，编辑于2023年，星期三

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

Add(z1,z2,&sum)初始条件：z1,z2是复数。操作结果：用sum返回两个复数z1,z2的和值。}ADTComplex第四十一页，共五十一页，编辑于2023年，星期三假设:z1和z2是上述定义的复数则Add(z1,z2,z3)操作的结果z3=z1+z2即为用户求的结果第四十二页，共五十一页，编辑于2023年，星期三抽象数据类型的表示和实现抽象数据类型需要通过固有数据类型(高级编程语言中已实现的数据类型)来实现。例如，以下为复数的表示和实现。第四十三页，共五十一页，编辑于2023年，星期三typedefstruct{

floatrealpart；

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

Assign(complex&Z,

floatrealval,floatimagval)；//构造复数Z,其实部和虚部分别被赋以参数//realval和imagval的值第四十四页，共五十一页，编辑于2023年，星期三float

GetReal(cpmplexZ)；//返回复数Z的实部值float

Getimag(cpmplexZ)；//返回复数Z的虚部值voidadd(complexz1,complexz2,complex&sum)；

//以sum返回两个复数z1,z2的和第四十五页，共五十一页，编辑于2023年，星期三//-----基本操作的实现voidadd(complexz1