1、认识数据和数据结构认识数据和数据结构1.1 数据及其价值1数字数字（Number）是一种用来表示数的书写符号。数字在不同的记数系统中表示的形式各不相同，阿拉伯数字是最普遍的一种。（二进制）2数值量是事物在同一种属性上的差别，通常用数字和单位来表示。一个量用数字表示时，这个数字叫作这个量的数值（Numerical Value）。例如，对于“质量”这种属性，一个大苹果质量约150克，一个小苹果质量约100克；对于“长度”这种属性，一张A4纸的两条边长分别为29.7厘米、21厘米3数据数据（Data）是指对现实世界客观事物进行记录并可以鉴别的符号。数据是事实或观察的结果，是对客观事物的逻辑归纳，是用
2、于表示客观事物的未经加工的原始素材数据是信息的载体，是计算机程序加工的“原材料”。可用于表示这个苹果“相片中、画中描述的、近似球形的、红色的、香甜的、质量为150克的物品”。当然，数据越详细越准确，对于“苹果”这个事物的表示就越准确。1.下列描述正确的是()。A.“200”和“两百”是相同的数值在不同的记数系统中的写法 B.人体的正常体温是37.9C,“37.9C 是数据 C.小明的英语考试成绩是90分，“90”是数字 D.信息是数据的载体，是有意义的数据1.2 对实际问题的数据抽象计算机越来越多地用于控制、管理及数据处理等非数值计算的工作，这些工作的操作对象及其关系是一些具有一定结构的数据，
3、无法用数学方程进行描述。因此，我们必须对实际问题进行数据抽象，分析待处理对象的特性以及各处理对象之间存在的关系，建立问题的数据模型。1.2 对实际问题的数据抽象2.收集资料，进行分析，探究问题的解。研究表明，对超市经营有影响的各种因素中，人的因素起重要作用。“人”的属性众多，“超市客户”的属性则需要筛选，可以从超市客户管理需要的角度进行筛选。1.2 对实际问题的数据抽象1.2 对实际问题的数据抽象1.2.2 分析数据之间的关系1.2.2 分析数据之间的关系1.2.2 分析数据之间的关系在图1-11中，数据间的联系是多对多的：每个数据既有多个前驱，也有多个后继。这种数据间的多对多联系称为网状关系
4、。例如，学校教育教学活动中涉及的人员之间的关系就是网状关系：一个教师同时教多个学生，一个学生也同时有多个教师授课。综合以上三个例子可见，描述这类非数值计算问题的数学模型不再是数学方程，而是用诸如表、树、图之类的数据模型进行描述。数据模型是客观事物及其关系的数据描述，是对客观事物进行数据抽象的结果。1.2.3 建立数据模型线性关系是计算机中最常见的数据关系，表是计算机中最常见的数据模型。在本教科书的后续章节中将要学习到的链表、队列、栈、字符串，其数据模型都是表。具有层次关系的数据，其数据模型是树如家族成员树（如图1-10所示）、班级成员树、学校机构树等。具有网状关系的数据，其数据模型是图如城市交
5、通图（如图1-11所示）、学校人员图、（师生）教学图等。数据对象（Data Object）是性质相同的数据元素的集合，是数据的一个子集。例如，整数数据对象是集合N=0，1，-1，2，-2，3，-3，1.3认识数据结构假设超市商品数据是随机排列的查找的方法最简单：从头开始逐个比较，顺序查对，直到找到目标为止。查找操作必须对所有数据进行，所以虽然方法简单却效率低下。假设超市商品数据是有组织的可按照商品所属类别进行分类，同类商品数据放在一起，则商品查找效率将大大提高：先找到商品所属类别，再从该类别下的首个数据开始进行逐个比较查对即可，无须对所有数据进行查找。（1）对于商品数据，除了图中所列组织方式，
6、还有其他方式吗？（2）对应图中数据的不同的组织方式，如果增加新的商品数据，其操作效率如何？删除商品呢？通过以上探究活动可知，当数据组织的方式、数据之间的关系不同时，实现同一功能的数据处理的过程就不同，数据处理的效率也不同。也就是说，在用计算机程序解决问题时，数据之间的关系会影响解决问题的步骤设计和程序执行效率。为了描述和处理越来越复杂的数据关系，人们需要研究数据结构。在计算机世界中，把数据元素以及数据元素之间的关系构成的集合称为数据结构（Data Structure）数据元素之间的关系包括：（1）数据元素之间的逻辑关系，即数据的逻辑结构（Logical Structure）。（2）数据元素及其
7、关系在计算机存储器中的存储方式，即数据的存储结构（Storage Structure），也称为数据的物理结构。2数据的逻辑结构根据数据元素之间逻辑关系的不同，数据结构有以下四种基本结构，如图1-14所示。（1）集合结构：数据元素除同属于一个集合之外，没有其他关系。（2）线性结构：数据元素之间存在前后有序的一对一的关系。（3）树形结构：数据元素之间存在一对多的关系。（4）图形结构：数据元素之间存在多对多的关系。3数据的存储结构数据结构在计算机存储器中的存储方式称为数据的存储结构，又称物理结构。它包括数据元素的存储和数据元素之间关系的存储。二进制的一位是计算机存储器的最小单位，数据在计算机中的存储
8、形式都是二进制位串。可以把这些位串看成数据元素在计算机中的存储形式。数据元素之间的关系在计算机中有两种不同的表示方法：顺序存储和非顺序存储。因此，可以得到两种不同的存储结构：顺序存储结构和链式存储结构。顺序存储结构是把逻辑上相邻的数据元素存储在物理位置也相邻的单元中，这是最基本的存储方法。链式存储结构对逻辑上相邻的元素不要求其在物理位置上也相邻。这种存储结构就像链条一样一环扣一环，存入每一数据元素的同时，也存入其下一元素的存储地址。图1-13（b）中的数据表的顺序存储结构和链式存储结构如图1-15所示。数据的存储结构不同，对数据进行同一操作的实现方法也不同1.在顺序存储结构中：（1）查找到“洗
9、发水”的位置。（2）“洗发水”后的数据逐个后移，空出一个位置。（3）“沐浴露”存放进空出的位置中。2.在链式存储结构中：（1）找到空间存放“沐浴露”数据，记住这个位置的地址。（2）“沐浴露”数据的下一地址指向原“洗发水”的下一地址，即指向“牙刷”数据。（3）查找到数据“洗发水”，并使其下一地址指向“沐浴露”数据。毛巾洗发水牙刷1.3.2 数据类型计算机通过执行程序进行数据处理。对于不同的数据，能执行的操作不尽相同。对于大多数编写程序的人来说，只需要关心数据的取值范围、数据元素间的关系、施加在数据上的操作规则。至于某种操作在计算机中如何实现，对程序员来说并不重要。例如，对于求和操作，程序员注重的
10、仅仅是其“数学上求和”的抽象特性，而不是其在计算机硬件上究竟如何实现。于是，封装了数据操作的数据类型就被引入程序设计语言中。与数据结构相比，数据类型增加了对施加在数据元素上的操作的定义，即对数据的运算规则的定义。常用的运算有检索、插入、删除、更新、排序等，这些运算实质上是在抽象的数据上所施加的一系列的抽象的操作。例如，整型变量之间的除法运算，结果也只能是整数。因此，整型变量的除法运算实际上是整除运算。如果整型变量的取值范围为-3276732767，则两个整型变量的值分别为300和500，做加法运算，结果为800，在整型变量的取值范围内，正确；但是，如果是30 000和30 000做加法，则会发
11、生错误结果60 000超出了整型变量的取值范围，发生溢出错误。不同的程序设计语言和不同的计算机系统对于数据类型的定义和实现可能稍有不同。2数据类型的分类 按数据类型“值”的不同特性，高级程序设计语言中的数据类型可分为两类：简单类型和结构类型。简单类型中的每个数据都是不可再分割的整体。例如C+语言中的基本类型（整型、实型、字符型和枚举型）、指针类型和空类型。结构类型是由简单类型按照一定的规则构造的。而且，结构类型内部还可以再包含结构类型。所以，每一种结构类型的值都是可以再分解为若干个简单类型或结构类型的值。1.3.3 数据结构的重要作用 用计算机解决此问题，首先要对数据进行组织，设计数据结构。最
12、简单的方法就是将生活中的通信录直接转化存储，构造一张号码表，表中每个数据元素包含两个数据项：姓名和号码。将表中的数据元素顺序存储在计算机中，查找时从头开始依次查对姓名，直到找到目标或找完整张表为止。当数据量大的时候，这种方法就不实用了。要提高查找速度，就要改进数据表的结构和存储方式1.3.3 数据结构的重要作用 要提高查找速度，就要改进数据表的结构和存储方式。可通过以下方法改进数据结构的设计：（1）号码表中的数据元素按姓氏排列。（2）设计一张姓氏索引表，采用如图1-19所示的存储结构。1.3.3 数据结构的重要作用算法是解决问题的有限步骤的序列，是一系列解决问题的清晰指令。数据结构是数据元素以
13、及数据元素之间的关系的集合。程序是为实现特定目标或解决特定问题而用计算机语言编写的命令序列的集合。本质上，数据是客观事物表示的一种抽象结果，而数据结构这门课程就是研究如何把客观世界待处理的信息逐层抽象成计算机可以接受的某种形式。通俗地说，数据结构就是研究数据之间的相互关系，也就是数据的组织形式的一门科学。程序员通过定义数据结构来描述数据以及数据之间的关系。算法的设计取决于选定的数据结构（逻辑结构），而算法的实现依赖于采用的存储结构。选择什么样的逻辑结构决定了处理数据的步骤和方法，选择何种存储结构则决定了如何编写程序语句。如果数据结构选择不好，除影响程序开发速度之外，更重要的是影响设计出来的程序
14、的运行效率。所以，学好数据结构是学好程序设计的基础。1单选题（1）对数字、数值、数据，以下描述正确的是（）。A.“一个苹果重150克”“150克”是数值B.“观察一幅画获得了美的感受”“美的感受”是数据C.“100读作一百”同一个数在不同记数系统中的写法不同D.“计算机擅长计算”计算机只能处理数值数据（2）关于大数据的描述，下列说法错误的是（）。A.当今社会注重隐私，只要人们不愿意，人们在社会生活中生成的数据就不会被收集B.大数据计算可以给人们的社会活动提供参考C.大数据计算的结果，能够调节、影响人们的活动D.自然界中的事物也能提供数据（3）数据结构在解决问题的过程中有重要作用。下列对数据结构的描述中正确的是（）。A.对同一事物，只能构造出一种数据结构B.选择的数据结构不同，解决问题的步骤也不同C.数据逻辑结构中相邻的数据，其存储位置也一定相邻D.对同一操作如插入、删除等，不同数据存储结构的实现方法相同
