1.1、1.2初识数据与数据结构课件-2025-2026学年高二上学期选择性必修一

数据与数据的组织（一） 汇报人： 1 人口数据变化告诉我们哪些信息？ 数据？ 数据是客观事物的符号表示 1.1数据 Information system and society 数据结构 数组 链表 数据 文字 图形 图像 视频 音频 …… 数字 144 数据的表现形式 4 数据结构 数组 链表 数据 数据的表现形式——数字 …… 144 数字本身没有意义，没有量的含义，数字只有在具体的情境中才具有实际的意义。 Information system and society 数据结构 数组 链表 数据 5 数据的表现形式——数值 数值指的是由数字符号组成的、具有量的意义的、可以进行算术运算的数据。 甲 乙 144KM t 速度=144KM/t Information system and society 数据结构 数组 链表 数据 6 数据的表现形式——其他表现形式 随着微电子技术及数据处理技术的发展，计算机能处理的数据已经扩展到图形、图像、视频、音频等形式，并能在快速处理这些数据的基础上作出即时的互动反应，甚至能做出一些人类特有的智能化行为。 Information system and society 数据结构 数组 链表 数据 7 数据结构 数组 链表 数据 思考 为什么现实中我们很少会关注“数字”和“数值”的差别，但在信息技术课上却必须严格地区分并且在编程时还要定义各种数据类型？ 8 数据结构 数组 链表 数据 计算机面对孤立的符号144时，无法判别这个符号所处的具体情境，或者说计算机不知道这个144是符号还是数值，这就需要人类事先给予界定并以某种方式告诉计算机。在编程时，给变量和常量设定数据类型就能实现这样的目标。 数字化时代中，数据更多地指用计算机进行处理的符号表示的总称。 Information system and society 数据结构 数组 链表 数据  人类一直以来都在尝试对客观世界进行数据表示。  数据是人类与客观世界进行对话的接口，对人类有着极其重要的价值和意义。 古代劳动人民发明的记数方法和工具 数据表示帮助人们实现了信息交流和意义建构。 1.数据促进了人类的发展  人类社会是在数据的表示和分析中不断发展和前进的。 结绳计数 筹码计数 劳伦兹SZ密码机 肢体计数 石子贝壳计数 结绳计数 筹码计数 1.数据促进了人类的发展 大数据不单指数据的海量，而是针对具有“4V”特征的数据 体量 Volume 大数据 “4V”特征 多样化Variety 价值密度 Value 速度Velocity 2.大数据推动人类进入一个崭新的时代 数据结构的概念 数据元素是数据的基本单位。 每一行实际内容（也称为一条记录）就是数据元素 1. 数据元素（Data Element） 数据元素 14 数据结构 数组 链表 数据 数据结构的概念 在Excel表或DataFrame中的数据元素是由若干个数据项（也称为字段、域）组成。数据项是具有独立含义的最小数据表示单位。 图中每个元素由5个数据项组成 1. 数据元素 数据项 15 数据结构 数组 链表 数据 数据结构的概念 2. 数据类型（Data Type） 数据类型指的是具有相同性质的计算机数据的集合及在这个数据集合上的一组操作。数据类型可以分为基本数据类型（也称为原子数据类型）和结构数据类型。 基本数据类型由计算机编程环境提供，编程者可以在编程时直接用系统提供的标识符进行定义，如Python编程语言中的整型、实型、布尔型等。 基本数据类型 结构数据类型是在程序设计时利用基本数据类型构造出的、复合的新类型，这种新类型由用户根据实际需要定义 结构数据类型 16 数据结构 数组 链表 数据 结构 结构--各个元素之间的关系 息 沙 曼 左右结构 上下结构 上中下结构 17 数据结构 数组 链表 数据 数据结构的概念 3. 数据结构（Data Structure） 数据结构指的是数据之间的相互关系，即数据的组织形式。 它包括了以下三个方面的内容： ①数据元素之间的逻辑关系，也称为数据的逻辑结构。 ②数据元素及其关系在计算机存储器内的表示，也称为数据的存储结构或物理结构。 ③数据的运算，即对数据施加的操作。 常见的数据结构：数组、链表、队列、栈、树 18 常见的数据结构 二 队列 链表 树 图 栈 数组 常见的 数据结构 数据结构设计是为了解决实际问题而出现的科学，选择合适的数据结构来组织与存储数据，可以达到高效处理数据的目的。 数组 表示一批数据，不仅可以描述数据本身，还可以描述数据所处的位置或数据之间的前后顺序关系。 所处的位置 数据本身 成一列纵队排队的人 常见的数据结构 二 常见的数据结构 二 成一列纵队排队的人 1 2 3 4 李彤 张强 胡洁 杜刚 这批数据序列可用数组“a(1)="李彤"、a(2)="张强"、a(3)="胡洁"、a(4)="杜刚"”来表达。 链表 同样是对一批人员数据进行组织，有时只需知道相邻人员之间的前后顺序关系，而对每个人员的位置信息并不作要求。 整队前的位置和链接关系 常见的数据结构 二 我排队首 吴坚 王林 黄刚 李丰 抽象化后的排队链接关系 组织、处理一批数据时， 若不关心数据实际所处的具体位置，而只需知道数据之间相互链接的顺序时，可以借鉴上面的方法。在计算机科学中,这种方法的具体实现形式就是链表。 常见的数据结构 二 常见的数据结构 二 吴坚 王林 黄刚 李丰 ∧ head 链表内存存放方式： head头节点 数据域 指针域 tail None 每个节点有两个部分，左边称为数值域，存放用户数据;右边部分称为指针 域，用来存放指向下一个元素的指针(地址)。 head节点永远指向第一个节点 常见的数据结构 二 吴坚 王林 黄刚 李丰 ∧ head 单向链表 吴坚 head 双向链表 王林 黄刚 李丰 ∧ 吴坚 head 基于单向链表的循环链表 王林 黄刚 李丰 ∧ 常见的数据结构 二 队列 有序排队上车的乘客 有序排队接客的出租车 乘客排队时先到的总是从队伍的头部出去(出队)上车，而后到的乘客则必须在队伍的尾部加入(入队)。同时，为了确保有序，人们总是规定不能从队伍的中间部位插队。 常见的数据结构 二 用计算机程序处理数据时，有时也需要将数据进行“排队”，并遵循现实中排队的规律，对数据进行“先进先出”FIFO(First In First Out)且中间不能“插队”的组织和操作，计算机科学家由此发明了“队列”这种数据结构。 银行叫号系统 常见的数据结构 二 栈 子弹进出弹匣的过程具有下列特点: ①整个装置只有一端开放(最上端)，而且进出只能在这一端进行。 ②弹匣中的子弹成一纵队排列。 ③任何子弹进出弹匣的规律是“先进后出、后进先出”，即最先装入弹匣的子弹最后才能被弹出，而最后装入弹匣的子弹则最先被弹出。 栈的示例——弹匣 树 一个元素前面(或上面)只有一个元素，而后面(或下面)却有多个(0个或多个)元素相邻，所有的数据元素之间的特征就像一棵倒放的树。 常见动物分类图 常见的数据结构 二 常见的数据结构 二 子树:树中某个节点下面的所有节点所构成的树。 空树:n=0的树。 节点:集合中的元素。 概念：树是由n个节点构成的一个有限集合以及在该集合上定义的一种节点关系。 用一个带盖(另一端封闭)的透明塑料筒来放取乒乓球，且筒的直径只允许一个乒乓球进出，如图，若放入球的编号序列为1、2、 3、4，则取出球的编号序列可能的是( ) A.1、2、3、4 B.3、1、2、4 C.4、2、3、1 D.2、4、1、3 常见的数据结构 二 数据结构的作用 三 （一） 设计算法解决问题离不开数据结构 数据统计前，需要先收集数据并将数据按照既有的逻辑关系进行结构化组织，可以用一张表格来组织数据并表示数据之间的逻辑关系。 数据结构的作用 三 各位选手在各个项目上的得分 根据本问题中数据之间的线性关系特点，可基于数组来设计算法并解决问题。如果不针对数据之间的关系特点设计数据结构，而是直接用一个个简单变量来存储所有学生姓名和各项得分，在此基础上设计算法及编写程序的工作量将变得非常巨大，用计算机处理这些数据就变得毫无意义。 数据结构的作用 三 （二） 不同的数据结构会导致处理效率的不同 1.用一维数组组织数据 程序代码 其中的bjdf(j)表示第j班的总分 当完成对所有选手的遍历时，每位选手的总得分就保存到数组sum中，而每个班级的总分则保存到数组bjdf中 数据结构的作用 三 2.用二维数组组织数据 程序代码 其中的bjdf(j)表示第j班的总分 为了统计每位选手和各班的总得分，基于二维数组的总体算法同样可通过遍历每位选手的相关数据进行，但在用计算机程序设计语言描述算法(编写程序)时，相比于一维数组，二维数组在程序实现效率上要高于前者，特别在每位选手总分统计部分。如果数据项数量增加，那么两者相差会更大。 数据结构的作用 三 数据合并：生产厂家总会根据各地产品销量的数据分析来预估市场情况，并为后续调整生产规数据合并划、完善营销策略提供依据。 由于数据量巨大，为了充分运用分布式处理的优势，总部会要求各下属地区上报数据时，按各产品销量进行从大到小的排序。总部收到数据后的第一件事是将所有数据合并并按照销量进行降序排序(从大到小)，为了完成数据合并和整理工作，总部数据分析员小刚需要设计合适的数据结构和算法。 分析：小刚可以用一个二维数组存储所有下属地区的产品销量数据，然后直接运用排序算法进行降序排序。如果利用既有数据已是分块有序的特点，设计新的数据结构和算法，则处理效率可以得到相应的提升。 各个地区的数据合并问题可以简化为2个地区的数据合并问题，当2个地区的数据合并完成后，剩余各地区的数据合并就可以按照同样方式完成。因此，接下来着重分析2个地区的数据合并问题。 数据结构的作用 三 设第1个地区共有n个产品销量数据，第2个地区共有m个产品销量数据。为了简化描述，突出核心部分的分析，考虑将问题抽象为n个有序整数和m个有序整数的合并问题，具体的问题模型如下: 已知一个降序排列的整数数列A:a1，a2，a3，…，an以及一个降序排列的整数数列B:b1，b2，b3，…，bm，将两个数列合并形成一个新的有序数列C，使新数列仍按降序排列，即c1≥c2≥c3≥…≥ck≥ck+1≥.…≥cn+m(其中ck∈A或者ck∈B)。请完成解决该问题的数据结构和算法的设计。 第一步抽象与建模 数据结构的作用 三 第二步设计、描述算法 (1)将数组a中所有元素存储到数组c的前n个位置中; 基于数组的算法设计与描述 1 数据结构的作用 三 (2)将数组c右边的m个元素赋值为-1 (c(n+1)直到c(n+m))； 基于数组的算法设计与描述 1 数据结构的作用 三 (3)变量p赋值为0，将表示数组c中有效元素总个数的变量tot赋值为n； 基于数组的算法设计与描述 1 数据结构的作用 三 (4)将数组b中元素b(i)逐个插入到数组c中(1≤ism)； p值增加1; 如果c(p)> b(i)，那么使p值增加1; 如果c(p)=-1，那么直接将b(i)存储到c(p)中，同时tot值增加1; 如果c(p)≤b(i)，那么依次将c(tot)，c(tot-1)，...，c(p)向右移动一个位置，然后将b(i)存储到c(p)中，同时tot值增加1。 数据结构的作用 三 (4)将数组b中元素b(i)逐个插入到数组c中(1≤ism)； p值增加1; 如果c(p)> b(i)，那么使p值增加1; 如果c(p)=-1，那么直接将b(i)存储到c(p)中，同时tot值增加1; 如果c(p)≤b(i)，那么依次将 c(tot)，c(tot-1)，...，c(p) 向右移动一个位置，然后将b(i) 存储到c(p)中，同时tot值增加1。 数据结构的作用 三 (4)将数组b中元素b(i)逐个插入到数组c中(1≤ism)； p值增加1; 如果c(p)> b(i)，那么使p值增加1; 如果c(p)=-1，那么直接将b(i)存储到c(p)中，同时tot值增加1; 如果c(p)≤b(i)，那么依次将 c(tot)，c(tot-1)，...，c(p) 向右移动一个位置，然后将b(i) 存储到c(p)中，同时tot值增加1。 数据结构的作用 三 (4)将数组b中元素b(i)逐个插入到数组c中(1≤ism)； p值增加1; 如果c(p)> b(i)，那么使p值增加1; 如果c(p)=-1，那么直接将b(i)存储到c(p)中，同时tot值增加1; 如果c(p)≤b(i)，那么依次将 c(tot)，c(tot-1)，...，c(p) 向右移动一个位置，然后将b(i) 存储到c(p)中，同时tot值增加1。 p p p tot 数据结构的作用 三 基于链表的算法设计与描述 2 上图 链表的初始状态 数据结构的作用 三 基于链表的算法设计与描述 2 上图 实施1次插入后的链表状态 小 结 数组的优点 (1)随机访问性强 (2)查找速度快 数组的缺点 (1)插入和删除效率低 (2)可能浪费内存 (3)内存空间要求高， 必须有充足的连续内存空间 (4)数组大小固定，不能动态拓展 链表的优点 (1)插入删除速度快 (2)内存利用率高，不会浪费内存 (3)大小没有固定，拓展灵活 链表的缺点 不能随意查找，必须从第一个开始遍历，查找效率低 常见的数据结构 二 Lavf58.29.100 Packed by Bilibili XCoder v2.0.2 $