基本概念和术语.ppt

《基本概念和术语.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第一章绪论1.1什么是数据结构1.2基本概念和术语1.4算法和算法分析1.3抽象数据类型的表示与实现1.2基本概念和术语一、数据、数据元素三、数据类型四、抽象数据类型二、数据对象、数据结构数据:是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中且能被计算机程序处理的符号(数值、字符等)的总称。例如，一个利用数值分析方法解代数方程的程序，其处理对象是整数和实数；一个编译程序或文字处理程序的处理对象是字符串。因此，对计算机科学而言，数据的含义极为广泛，如图象、声音等都可以通过编码而归之于数据的范畴。一、数据、数据元素数值性数据非数值性数据数据元素:是数据的基本单位，在计算

2、机中通常作为一个整体进行考虑和处理。例如，例1－2中的“树”中的一个棋盘格局，例1－3中的“图”中的一个圆圈都被称为一个数据元素。有时，一个数据元素可由若干个数据项组成，例如，例1－1中一本书的书目信息中的每一项（如书名、作者名等）为一个数据项，数据项是数据的不可分割的最小单位。如:整数“5”,字符“N”等。----是不可分割的“原子”其中每个款项称为一个“数据项”它是数据结构中讨论的最小单位数据元素也可以由若干款项构成。例如：描述一个学生的数据元素称之为组合项年月日姓名学号班号性别出生日期入学成绩原子项数据对象是性质相同的数据元素的集合，是数据的一个子集。例如，整数数据对象是集

3、合N={0，+/-1，+/-2，……}，字母字符数据对象是集合C={‘A’，‘B’，……，‘Z’}。数据结构是相互之间存在的一种或多种特定的关系的数据元素的集合。从上面中三个例子可以知道，在任何问题中，数据元素之间都不是孤立存在的，而是在它们之间存在着某种关系，这种数据元素相互之间关系称为结构。例如，当用三个4位的十进制数表示一个含12位数的十进制数时，3214,6587,9345─a1(3214),a2(6587),a3(9345)则在数据元素a1、a2和a3之间存在着“次序”关系a1,a2、a2,a33214，6587，93456587，3214，9345例如:a1a

4、2a3a2a1a3又例，在2行3列的二维数组中六个元素{a1,a2,a3,a4,a5,a6}之间存在两个关系:行的次序关系:row={,,,}col={,,}a1a2a3a4a5a6列的次序关系:若在6个数据元素{a1,a2,a3,a4,a5,a6}之间存在如下的次序关系:{

5、i=1,2,3,4,5}数据结构是相互之间存在着某种逻辑关系的数据元素的集合。可见，不同的“关系”构成不同的“结构”则构成一维数组的定义。从关系或结构分，数据结构可归结为以下四类:线性结构树形

6、结构图状结构集合结构①集合：结构中的数据元素之间除了“同属于一个集合”的关系外，别无其他关系。②线性结构：结构中的数据元素之间存在一个对一个的关系。③树形结构：结构中的数据元素之间存在一个对多个的关系。④图状结构或网状结构：结构中的数据元素之间存在多个对多个的关系。6）数据的物理结构（又称存储结构）：是数据结构在计算机中的表示。它包括数据元素的表示和关系的表示。数据元素之间的关系在计算机中又有两种不同的表示方法：①顺序映像特点：借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。②非顺序映像特点：借助指示元素存储地址的指针表示数据元素之间的逻辑关系。例如：假设用两个字长的位

7、串表示一个实数，则可以用地址相邻的4个字长的位串表示一个复数，如图1.3（a）为表示复数z1＝3.0－2.3i和z2＝－0.7+4.8i的顺序存储结构。图1.3（b）为表示复数z1的链式存储结构，其中实部和虚部之间的关系用值为“0415”的指针来表示（0415是虚部的存储地址）。(a)顺序存储结构(b)链式存储结构图1.3复数存储结构示意图0300030206320634041506110613…3.0-2.3…-0.74.8……-2.3…3.00415…数据的逻辑结构和物理结构是密切相关的两个方面。在任何一个算法的设计取决于选定的数据（逻辑）结构，而算法的实现依赖于采用的存储结

8、构。7）数据类型：是一个值的集合和定义在这个值集上的一组操作的总称。按“值”的不同特性，在高级程序语言中可分为：①原子类型：其值不可分解。例如，C语音中的基本类型（整型、实型、字符型和枚举类型）、指针类型和空类型。②结构类型：其值是由若干成分按某种结构组成的，故可分解，并且其成分可以是非结构的，也可以是结构的。例如，数组的值由若干分量组成，每个分量可以是整数，也可以是数组等。8）抽象数据类型（ADT）：是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义仅取决于它的一