资源简介

(共17张PPT)
1.3 认识数据结构
第一章 认识数据和数据结构
实践探究
利用表格的形式为下面生活用品分一个类：
毛巾、洗衣粉、方便面、食用油、大米、洗发水、牙刷、牙膏、面包
1.3.1 数据结构
编号 商品
001 毛巾
002 洗衣粉
003 方便面
004 食用油
… …
102 洗发水
103 牙刷
… …
127 牙膏
… …
种类 分类号
洗漱用品 01
食品 02
洗洁用品 03
编号 商品
01001 毛巾
01002 洗衣粉
01003 方便面
01004 食用油
… …
02001 洗发水
02002 牙刷
… …
03001 牙膏
… …
（a）随机排列数据
（b）分类组织数据
数据以及数据的“结构”，与加工和处理这些数据的方法密切相关。为了描述和处理越来越复杂的数据关系，人们需要研究数据结构。数据结构是信息技术学科的核心内容之一、对培养信息意识与计算思维、深入理解及掌握信息技术学科知识与实践方法、形成学科核心素养，具有非常重要的作用。
前 言
CONTENTS
目 录
1.3.1 数据结构
1.3.2 数据类型
1.3.3 数据结构的重要作用
1.3.1 数据结构
通过以上探究活动可知，当数据组织的方式、数据之间的关系不同时，实现同一功能的数据处理的过程就不同，数据处理的效率也不同。也就是说，在用计算机程序解决问题时，数据之间的关系会影响解决问题的步骤设计和程序执行效率。为了描述和处理越来越复杂的数据关系，人们需要研究数据结构。
1、数据的组织方式
1.3.1 数据结构
在计算机世界中，把数据元素以及数据元素之间的关系构成的集合称为数据结构(Data Structure)。
数据元素之间的关系包括：
(1)数据元素之间的逻辑关系，即数据的逻辑结构(Logical Structure)。
(2)数据元素及其关系在计算机存储器中的存储方式，即数据的存储结构(StorageStructure)，也称为数据的物理结构。
1.3.1 数据结构
2.数据的逻辑结构
根据数据元素之间逻辑关系的不同，数据结构有以下四种基本结构，如图1-14所示。
(1)集合结构：数据元素除同属于一个集合之外，没有其他关系。
(2)线性结构：数据元素之间存在前后有序的一对一的关系。
(3)树形结构：数据元素之间存在一对多的关系。
(4)图形结构：数据元素之间存在多对多的关系
因为数据的逻辑结构是由事物本身的逻辑关系确定的，与计算机存储器中具体如何存储这些数据无关，所以，我们所说的数据结构，一般指的就是数据的逻辑结构。
1.3.1 数据结构
3.数据的存储结构
1.3.1 数据结构
3.数据的存储结构
数据结构在计算机存储器中的存储方式称为数据的存储结构，又称物理结构。它包括数据元素的存储和数据元素之间关系的存储。
二进制的一位是计算机存储器的最小单位，数据在计算机中的存储形式都是二进制位串。可以把这些位串看成数据元素在计算机中的存储形式。
1.3.2 数据类型
计算机通过执行程序进行数据处理。对于不同的数据，能执行的操作不尽相同。对于大多数编写程序的人来说，只需要关心数据的取值范围、数据元素间的关系、施加在数据上的操作规则。至于某种操作在计算机中如何实现，对程序员来说并不重要。例如，对于求和操作，程序员注重的仅仅是其“数学上求和”的抽象特性，而不是其在计算机硬件上究竟如何实现。于是，封装了数据操作的数据类型就被引入程序设计语言中。
1.3.2 数据类型
数据类型是与数据结构密切相关的一个概念，是对数据的取值范围、数据元素之间的结构以及允许施加操作的一种总体描述。
与数据结构相比，数据类型增加了对施加在数据元素上的操作的定义，即对数据的运算规则的定义。常用的运算有检索、插入、删除、更新、排序等，这些 运算实质上是在抽象的数据上所施加的一系列的抽象的操作。
每种程序设计语言都会定义自己的数据类型，用于表示常用的数据结构以及在其上的操作。在用高级程序语言编写的程序中，每个变量、常量或表达式都有一个确定的数据类型。当我们定义某种类型的变量时，就是规定了这个变量的取值范围以及确定的操作(运算)规则。
如图1-17所示的为C++语言中的短整型数据类型。短整型数据类型的值集为整数的一个子集(取值范围为-32768-32767)，可进行的操作有加、减、乘、除和取模等算术运算。
1.数据类型
1.3.2 数据类型
一种确定的数据类型有以下特点：
(1)所有数据元素都具有相同的取值范围。
(2)所有数据之间都具有相同的关系。
(3)一般地，数据元素经过元素运算、操作之后所得的结果，其值依然落在原来的取值范围内；这个结果与其他数据元素之间的关系也必须与原有数据元素之间的关系一致。
例如，整型变量之间的除法运算，结果也只能是整数。因此，整型变量的除法运算实际上是整除运算。如果整型变量的取值范围为-32767～32767，则两个整型变量的值分别为300和500，做加法运算，结果为800，在整型变量的取值范围内，正确；但是，如果是30000和30000做加法，则会发生错误——结果60000超出了整型变量的取值范围，发生出错误。
不同的程序设计语言和不同的计算机系统对于数据类型的定义和实现可能稍有不同。
1.数据类型
1.3.2 数据类型
2.数据类型的分类
按数据类型“值”的不同特性，高级程序设计语言中的数据类型可分为两类：简单类型和结构类型。
简单类型中的每个数据都是不可再分割的整体。例如C++语言中的基本类型(整型、实型、字符型和枚举型)、指针类型和空类型。
结构类型是由简单类型按照一定的规则构造的。而且，结构类型内部还可以再包含结构类型。所以，每一种结构类型的值都是可以再分解为若干个简单类型或结构类型的值。
图1-18为简单数据类型和结构数据类型数据表。图中两个数据表均由若干行组成，(a)中每一行只有一个数据项，而(b)中每行可以看成一个两列的数据表，而每个数据表包含两个数据项，是可以分解的结构。
(a)简单数据类型
(b)结构数据类型
1.3.3 数据结构的重要作用
从20世纪60年代末开始，程序设计已从技巧发展成一门科学。与程序设计联系非常密切的课程有数据结构、算法分析与设计、程序设计方法。瑞士的计算机科学家尼古拉斯·沃斯曾经提出：“算法+数据结构程序”(Aleonithms+Data Structures=Programs)。这句话简洁明了地概括了算法、数据结构、程序三者之间的关系。
算法是解决问题的有限步骤的序列，是一系列解决问题的清晰指令。
数据结构是数据元素以及数据元素之间的关系的集合。
程序是为实现特定目标或解决特定问题而用计算机语言编写的命令序列的集合。
本质上，数据是客观事物表示的一种抽象结果，而数据结构这门课程就是研究如何把客观世界待处理的信息逐层抽象成计算机可以接受的某种形式。通俗地说，数据结构就是研究数据之间的相互关系，也就是数据的组织形式的一门科学。
1.3.3 数据结构的重要作用
分析
姓名 号码
张达 13712345678
熊二 13523456789
李三 13012345678
…… ……
数据结构在解决问题的过程中有重要作用
如在以下通讯录中查找对应的姓名，获得其电话号码。
最简单的方法就是将生活中的通讯录直接转化存储：构造一张号码表，表中每个元素包含两个数据项：（姓名，号码）
但是数据量大的时候，这种方法就不实用了。如在100000条通讯录中查找对应姓名的电话号码
姓氏 号码
李 0000
…… ……
熊 4206
…… ……
张 99023
…… ……
地址 姓名 号码
0000 李三 13012345678
……. …… ……
4206 熊一 17955557890
…… …… ……
4212 熊二 13523456789
……. …… ……
99023 张博 15289077655
……. …… ……
99045 张达 13712345678
解决办法是：建立一张姓氏索引表
1.3.3 数据结构的重要作用
分析
数据结构在解决问题的过程中有重要作用
程序员通过定义数据结构来描述数据以及数据之间的关系。算法的设计取决于选定的数据结构(逻辑结构)，而算法的实现依赖于采用的存储结构。选择什么样的逻辑结构决定了处理数据的步骤和方法，选择何种存储结构则决定了如何编写程序语句。如果数据结构选择不好，除影响程序开发速度之外，更重要的是影响设计出来的程序的运行效率。所以，学好数据结构是学好程序设计的基础。

展开更多......

收起↑