(
课件网) 专题一 数据与数据的组织、大数据时代 数据的组织 选择性必修1 数据与数据结构 思维导图 归纳提炼 一、数据 1.数据的表现形式 数据的表现形式有数字、数值、文字、图形、图像、音频、视频等。 (1)数字 数字是指由阿拉伯数字“0,1,2,3,4,5,6,7,8,9”或其他含义相同的符号表示。 数字本身是没有意义的,没有量的含义,只有在具体的情境中才有实际意义。 重难点剖析 (2)数值 数值是指由数字符号组成的、具有量的意义的、可以进行算术运算的数据。 (3)其他表现形式 数据的其他表现形式有:在快速处理图形、图像、音频、视频等数据的基础上做出即时的互动反应(如利用虚拟现实技术的活动或游戏中),甚至能做出一些人类特有的智能化行为(如无人驾驶汽车等)。 2.数据的价值与意义 (1)数据促进了人类社会的发展。 (2)大数据推动人类进入一个崭新的时代。 二、数据的组织 1.数据结构的概念 (1)数据元素 ①数据元素是数据的基本单位,可由若干个数据项组成。 ②数据项是具有独立含义的最小数据表示单位。 (2)数据类型 ①数据类型是指具有相同性质的计算机数据的集合及在这个数据集合上的一组操作。 ②数据类型可以分为基本数据类型和结构数据类型。 (3)数据结构 ①数据结构是指数据之间的相互关系,即数据的组织形式。 ②数据结构主要包括数据的逻辑结构、数据的存储结构或物理结构和数据的运算。 2.常见的数据结构 (1)数组 ①数组用于存储一批数据,除可以描述数据对象本身之外,还可描述数据所处的位置或数据之间的前后顺序关系。 ②可通过下标精确地访问序列中的某个数据元素,又可通过下标依次按顺序遍历序列中的每个数据元素。 (2)链表 ①表示一批数据,这类数据之间具有明确的相互链接的前后顺序,但对数据对象本身的位置信息不作要求。 ②常用的链表有单向链表、双向链表和循环链表。 (3)队列 ①数据具有“先进先出”且中间不能“插队”的组织和操作的性质。 ②在队列的头部(队首)进行数据的读取(即出队),在数据序列的尾部(队尾)进行数据的插入(入队)操作。 (4)栈 ①数据具有“先进后出”且所有操作只能在一端(栈顶)进行的性质。 ②仅可在一端进行数据的读取(出栈)和插入(入栈)操作。 (5)树 数据元素前面只有一个元素,后面可以有0个或多个元素相邻,所有数据元素之间的关系特征像一棵倒放的树。 三、大数据时代数据的组织 (一)实时查询系统中数据的组织 大数据背景下的数据组织和存储方式采用分布式存储系统。分布式存储系统利用分布在不同物理位置的服务器来分担系统存储任务,既能提高数据存储的安全性,又能提升系统数据访问的速度,同时也具有较好的可扩展性。 1.实时查询系统中的数据业务特点 (1)能实现上千个请求的实时响应。 (2)支持后续商品信息的更改。 2.实时查询系统中的数据结构和算法设计 (1)基于数据间线性关系的数据结构设计 读取数据库中的数据并保存到内存中,可采用数组或链表结构来组织和存储。 数据结构 查找操作 插入操作 数组 采用二分查找算法,时间复杂度为O(log2n),查找速度快,效率高 数据移动较多,时间复杂度O(n),效率较低 链表 需从链表的一端依次遍历查找,时间复杂度为O(n),效率较低 不需要数据移动,时间复杂度为O(1),效率较高 使用数组和链表的方式进行数据查找和插入的特点如下表所示。 (2)基于链表的数据结构和算法优化设计 ■优化方法 ①减少查找插入位置过程中的比较次数。 ②借鉴二分查找算法的思想。 ■跳跃表 跳跃表,是一种立足链表,借鉴二分查找的思想而形成的数据结构。跳跃表是在原有的有序链表上增加了多级索引,通过索引来实现快速查询。 “跳跃表”以空间换时间,时间复杂度为O(log2n)。 缺点:维护成本高,增加删除都需要更新索引。 解 ... ...
