资源简介

(共48张PPT)
信息技术
字符串、列表、栈
数组、链表
树、二叉树
排序、查找、迭代、递归
处理不同类型数据的方式
ONTENT
目 录
C
第一章 数据与数据的组织
数据与信息
数据
数据的组织
数据结构的概念
常见的数据结构
数据结构的作用
数据的表现形式
数据的价值与意义
内容总览
数字本身无意义，没有量的含义，数字只有在具体的情境中才具有实际的意义。
数据的表现形式：数字、数值、文字、图形、图像、音频、视频等
1.数字
1.1 数据
2.数值
由数字符号组成的、具有量的意义、可以进行算数运算的数据。
在数字化时代，数据更多的指计算机进行符号表示的总称。
在编程中，确定具体的量的意义，由设定数据类型能实现。
3.其他表现形式
VR
AR(增强现实)：将虚拟技术与现实世界巧妙融合的技术，两种信息互相补充，从而实现对真实世界的 “增强”。
“实景红包”：用户在发、收红包时，需要同时满足地理位置和实景红包扫描两个条件，相比既有的红包形式，增强了互动性和趣味性。
数据的价值和意义
肢体计数、石子和贝壳计数、结绳记事、筹码计数、计算机编码，帮人们实现了信息交流和意义建构。
密码编译，计算机巨人（Colossus）,ENIAC电子计算机
1.数据促进了人类社会的发展
制药厂根据药品的销售库存数规划下一年各种药品的生产量，以确保满足患者需求又不产生过多库存。
根据当前学校学生人数和未来人口增长趋势，教育管理部门判断是否需要增设新学校。
2.大数据推动人类进入崭新时代
“4V”特征：
数量（volume）: 数据体量大；
高速（velocity）: 数据产生快，数据处理速度快；
多样（variety） : 数据类型多；
价值（value） : 价值密度低。
医疗
分析病人特征数据和疗效数据，找到针对特定病人的最佳治疗途径，以减少过度治疗、避免治疗不足。
传输疫苗途中的温度检测与控制；
智能挂号，提高医院运作效率；
中草药园的气象站以及自动化控制设施；
电子处方，远程会诊
根据手机信号在真实地理空间上的覆盖情况，完整、客观地还原出手机用户的现实活动轨迹，从而挖掘得到人口生活空间分布与工作空间分布等特征信息，为城市规划提供可靠的参考信息。
大数据推动人类进入一个崭新的时代

导航如何预估时间
车载导航？
手机导航？
车载导航的信息不全面，更新的速度又很慢，一般会买个手机支架用手机导航，要么就把手机导航投到大屏上。
只要你设定了目的地，导航就会计算出预计抵达的时间，即使中途会有一点堵车，软件也会不断调整达到时间。
手机导航实际上在我们的城市道路中，会看到很多摄像头，这些摄像头不只是记录车辆的违章情况，还会检测道路上的车流量。由于手机接收信号很及时，这些车流量的数据就会进入到导航平台，就相当于是数据共享。因此导航可以接收到实时的最新道路情况，有发生拥堵的地方会提示车主绕行。（拥堵情况与行驶路线的颜色）
1.2 数据的组织
1.2.1数据元素的概念
1.数据元素
数据元素是数据的基本单位。有些情况下，数据元素也称为元素、节点、顶点、记录等。一个元素有若干个数据项组成（也称为字段、域）组成，数据项是具有独立含义的最小数据表示单位。
某天A股物联网部分股价表现一览
代码 名称 最新价格（元/股)| 动态市盈 流通股本(万股)
300155 安居宝 15.62 48.55 5775.62
000988 华工科技 7.78 35.61 89111.65
002104 恒宝股份 9,92 40.83 34032.05
300168 万达信息 18.4 88.06 17006.35
000997 新大陆 9.7 52.81 50870.62
300078 中瑞思创 11.83 26.47 6269.87
002121 科陆电子 7.68 26.96 26762.09
600718 东软集团 9.09 30.9 122227.59
002161 远望谷 7.96 41.15 52082.6
002073 软控股份 9.8 38.66 61659.73
数据元素（记录）
5个数据项
数据元素的第一个数据项的值
2.数据类型
具有相同性质的计算机数据的集合及在这个数据集合上的一组操作。
数据类型可以分为基本数据类型（也称为原子数据类型）和结构数据类型。
基本数据类型由计算机编程环境提供，编程者可以在编程时直接用系统提供的标识符进行定义，如Python编程语言中的整型、实型、布尔型等。
结构数据类型是在程序设计时利用基本数据类型构造出的、复合的新类型，这种新类型由用户根据实际需要定义，能较好地描述数据元素的数据项组成以及数据元素之间的逻辑关系，方便用户根据数据之间逻辑关系的特点进行数据处理，如很多编程语言中提供的记录类型、集合等。
3.数据结构
数据结构指的是数据之间的相互关系，即数据的组织形式。
包括以下三个方面内容：
数据元素之间的逻辑关系【逻辑结构】；
数据元素及其在计算机中内存表示【存储结构 or 物理结构 】；
数据的运算（对数据施加的操作）。
本书中无特殊说明一般指此
举例：对一批身高数据升序操作
在计算机中，既能表示各位置身高数据，又能体现位置之间的线性关系的数组来组织数据。数组就是一种数据结构。
1.2.2 常见的数据结构
数组、链表、队列、栈、树和图等
1.数组（排队）
语言描述：
“第1个是李彤” “第2个是张强” “第3个胡杰” “第4个是杜刚”
数据序列：
a[1]=“李彤” a[2]=“张强”
a[3]=“胡杰” a[4]=“杜刚”
a[1]、a[2] 、a[3]、 a[4]组成了数组a；
说明这是一批类型相同的数据
下标1、2、3、4表示数据元素所处的位置顺序。
总结： 快速通过下标精准访问序列中的某个元素（第100个元素：a[99]，第1个元素：a[0]）
通过下标依次顺序遍历序列中的每个数据元素
遍 历
遍历指的是根据数据之间的逻辑结构,遵循一定的顺序依次对所有数据元素做一次且仅做一次访问。访问某个数据元素时,需要进行的操作依赖于具体实际问题。例如，当需要计算满足条件的元素之和时,访问每个元素时首先判断元素是否符合条件,若满足则将其累加。
2.链表
只需知道相邻人员之间的前后顺序关系，而对每个人的位置信息并不作要求。
军训时，重新整队的时候，只需要记住排在自己前面的人是谁，而对集合地点不做要求。
一旦集合，本来分散的人员可以根据链表关系，快速按照原顺序排成队伍。
虽然整队前后每个人员的站位发生变化，但相互之间的顺序关系是不变的。
整队后
吴坚
王林
黄刚
李丰
常用表现形式：
单向链表、双向链表、循环链表
头结点head（指针）：
为了记录、识别各个链表，在链表头部设立一个头结点；
遍历时，可从head指向的头节点开始依次逐个遍历链表的每个节点
链表指针可以指向前面，也可以指向后面。
吴坚
王林
黄刚
李丰 ^
head
空指针
图1.2.6 单项链表
指 针
在计算机科学中，指针(Pointer)是用来指示一个数据存储地址（内存或者寄存器）的变量。如图1.2.6所示的head，该变量存储的是头节点所在的内存地址，或者说存储的地址指向了头节点,所以形象地称为“指针"。
为了满足链表在两个方向都能进行遍历，会在单项链表增加一个前驱节点的链接，转换为双向链表。
若在链表首尾之间增加链接，就形成了循环链表。
吴坚
王林
黄刚
李丰
吴坚
王林
黄刚
李丰 ^
head
吴坚
head
王林
黄刚
李丰 ^
吴坚
head
王林
黄刚
李丰
前驱节点
双向链表
循环链表
单向链表（指针向前）
单向链表（指针向后）
作业本 （双色版）
10.22 作业：
《1.2 初识数据结构》周一早上交
3.队列
乘客排队，先到的总是从队伍的头部出去上车，而后到的必须在队伍的尾部加入。
为确保有序，规定不能从中间的位置插队。
入队
出队
先进先出
不能插队
银行叫号系统：
基于队列的FIFO（First In First Out），解决CPU和主存储器（RAM)数据存取之间的速度差问题，会在CPU中安装速度远快于RAM的高速缓存(Cache )。
网络平台瞬间收到很多服务请求，系统会按照服务请求到达的先后顺序，用队列来依次保存各个请求，然后按照入队顺序逐个出队并处理。
入队
出队
4.栈
只有一端是开放的，所有操作只能在开放的一端进行。
弹匣[典型栈结构]
只能在连接枪体的一端进行子弹压装、弹出操作;
子弹被装入弹匣称为“入栈”，子弹被弹出弹匣称为“出栈”。
子弹进出弹匣的过程具有下列特点:
①整个装置只有一端开放（最上端)，而且进、出只能在这一端进行。
②弹匣中的子弹成一纵队排列。
③任何子弹进出弹匣的规律是“先进后出、后进先出”，即最先装入弹匣的子弹最后 才能被弹出，而最后装入弹匣的子弹则最先被弹出。
计算机科学家就发明了“栈”这种数据结构，用来支持符合此种数据操作规律的数据。
如网页浏览器对用户浏览网页的管理，内部就采用了栈进行网页数据的组织。
当用户由一个网页跳转到另一个网页浏览时，系统会将原先的网页数据进行入栈操作，而当用户单击浏览器的“后退”按钮时，系统又会将栈中最上方的网页数据出栈，用户即可看到刚才最后浏览过的网页内容。
“先进后出”
“后进先出”
问题与讨论
在文字处理软件Word中进行“撤消”操作(按CtrH+Z键，或者单击撤消操作快捷按钮“ ”)。 根据“撤消”操作所产生的结果，说明Word中符号输入及撤消操作中，内部所依托的数据结构是哪种数据结构 为什么
举例：
5.树
无论是队列还是栈,其中的数据元素之间都呈现出一种线性关系，即除首尾两端的元素外，其他数据元素的前面和后面都只有一个相邻的元素，所有元素都成“一条线”排列。
但现实世界中有些数据之间的关系并非是线性关系，如生物学中的动物分类图、中国图书馆分类法、行政部门组织结构图等。
这些数据元素之间的关系都呈现出一个共同的特点，即一个元素前面(或上面)只有一个元素，而后面(或下面)却有多个（0个或多个)元素相邻，所有数据元素之间的关系特征就像一棵倒放的树，所以称之为树结构。
树结构
线性表
线性表是由零个或多个数据元素组成的有限序列,数据元素之间的关系是一对一的关系,即除了第一个和最后一个数据元素以外，中间任何一个数据元素的前面和后面都只有一个数据元素与它相邻。线性表是一种基本的、常见的数据结构,可以根据需要向线性表增加元素，或者删除表中的元素。数组、队列、栈、链表都是线性表的特殊形式。
例 2
数据的逻辑结构是指数据元素之间的逻辑结构
数据的存储结构包括数据元素的存储及数据元素之间关系的存储
数据的运算是指对数据施加的操作，包括删除、查找、插入数据等
数据结构设计时不需要考虑编程的实现和数据处理的效率
例 1
以下关于数据结构的描述，不正确的是 ( )
用一带盖的玻璃筒来放取乒乓球，放、取球只能在带盖的一端进行(另一端为封闭状态)，且桶的直径只允许一个乒乓球进出。若放入球的编号序列为1、2、3、4，则取出球的编号序列不可能的是 （ ）
1、2、3、4
2、3、4、1
4、2、3、1
3、2、1、4
D
C
1.2.3 数据结构的作用
每个实际问题中的数据之间存在着一定的关系，用计算机程序解决问题时，需要将数据之间的这些关系映射到程序的数据表示中，这样才能有效地用计算机程序解决问题。
对于同一个问题的解决，当依据不同的数据结构来设计算法时，算法的处理效率、程序的实现效率也是不同的。
1.设计算法解决问题离不开数据结构
数据统计前，需要先收集数据并将数据按照既有的逻辑关系进行结构化组织，可以用一张表格来组织数据并表示数据之间的逻辑关系，如表1.2.1所示。
趣味运动会
姓名 班级 滚铁圈 打弹子 拍纸板 竹蜻蜓 跳绳 踢键子
陈涛 9 3 2
杨琼 3 5 1
金凯 2 4 5
吴敏 1 6 1 3
朱刚强 6 5 1 7
…. …… …… …… …. …… …… ……
根据本问题中数据之间的线性关系特点，可基于数组来设计算法并解决问题。
如果不针对数据之间的关系特点设计数据结构，而是直接用一个个简单变量来存储所有学生姓名和各项得分，在此基础上设计算法及编写程序的工作量将变得非常巨大，用计算机处理这些数据就变得毫无意义。
列方向：
性质和类型都相同
每一列用一个一维数组存储
2.不同数据结构会导致处理效率的不同
xm[i] bj[i] d1[i] d2[i] d3[i] d[4i] d5[i] d6[i] sum[i]
陈涛 9 3 0 2 0 0 0
杨琼 3 0 0 0 0 5 1
金凯 2 0 4 5 0 0 0
吴敏 1 6 1 0 3 0 0
朱刚强 6 5 0 1 0 7 0
…. …… …… …… …. …… …… ……
姓名 班级 滚铁圈 打弹子 拍纸板 竹蜻蜓 跳绳 踢键子
一维数组
某个选手各个项目总得分sum
每位选手总分保存到sum[i]中，然后将sum[i]的值累加到bjdf[bj[i]]中，每个班级总分保存在数组bjdf中。
bjdf[bj[i]]=bjdf[bj[i]]+sum[i]
二维数组
xm[i] a[i,1] a[i,2] a[i,3] a[i,4] a[i,5] a[i,6] a[i,7] a[i,8]
陈涛 9 3 0 2 0 0 0
杨琼 3 0 0 0 0 5 1
金凯 2 0 4 5 0 0 0
吴敏 1 6 1 0 3 0 0
朱刚强 6 5 0 1 0 7 0
…. …… …… …… …. …… …… ……
第i位选手的班级
第i位选手在6个项目上的得分
第i位选手的总得分
为了统计每位学生和各班的总得分，基于二维数组的总体算法同样可通过遍历每位选手的相关数据进行，但在用计算机程序语言描述算法（编写程序）时，相比于一维数组，二维数组在程序实现上效率要高于前者，特别在每位选手统计部分。如果数据项数量增加，那么两者相差会更大。
作业本 （双色版）
10.26 作业：
《1.2 初识数据结构》周三早上交
数据合并
1.生产厂家对各地产品销量的数据进行归纳整合（按各产品销量进行从大到小排序）降序！
各个地区的数据合并问题可以简化为2个地区的数据合并问题，当2个地区的数据合并完成后，剩余各地区的数据合并就可以按照同样方式完成。因此，接下来着重分析2个地区的数据合并问题。
第一步 抽象与建模
设第1个地区共有n个产品销量数据，第2个地区共有m个产品销量数据。为了简化描述，突出核心部分的分析，考虑将问题抽象为n个有序整数和m个有序整数的合并问题，具体的问题模型如下:
已知一个降序排列的非负整数数列A: ，以及一个降序排列的非负整数数列B: ，将两个数列合并形成一个新的有序数列C，使新数列仍按降序排列，即≥ ≥ ≥ …≥ ≥ ≥… (其中∈A或者∈B)。请完成解决该问题的数据结构和算法的设计。
不同数据结构会导致处理效率的不同
第二步 设计、描述算法
1. 基于数组的算法设计与描述
（1）将数组a中所有元素存储到数组c的前n个位置中；
1 2 3 4 5
19 16 12 8 5
a
19
16
12
8
5
1 2 3 4 5
19 16 12 8 5
b
20
15
14
10
4
1 2 3 4 5 6 7 8 9 10
c
1 2 3 4 5 6 7 8 9 10
不同数据结构会导致处理效率的不同
第二步 设计、描述算法
1. 基于数组的算法设计与描述
（2）将数组c右边的m个元素赋值为–1（c(n+1)直到c(n+m)）；
1 2 3 4 5
19 16 12 8 5
a
19
16
12
8
5
1 2 3 4 5
19 16 12 8 5
b
20
15
14
10
4
c
-1
-1
-1
-1
-1
1 2 3 4 5 6 7 8 9 10
不同数据结构会导致处理效率的不同
第二步 设计、描述算法
1. 基于数组的算法设计与描述
（3）变量p赋值为0，将表示数组c中有效元素总个数的变量tot赋值为n ；
1 2 3 4 5
19 16 12 8 5
a
19
16
12
8
5
1 2 3 4 5
19 16 12 8 5
b
20
15
14
10
4
c
-1
-1
-1
-1
-1
0
i
p
tot
1 2 3 4 5 6 7 8 9 10
不同数据结构会导致处理效率的不同
（4）将数组b中元素b(i)逐个插入到数组c中（1≤i≤m）：
19
16
12
8
5
1 2 3 4 5
20 15 14 10 4
b
20
15
14
10
4
c
-1
-1
-1
-1
-1
0
i
p
tot
①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。
1 2 3 4 5 6 7 8 9 10
不同数据结构会导致处理效率的不同
（4）将数组b中元素b(i)逐个插入到数组c中（1≤i≤m）：
19
16
12
8
5
1 2 3 4 5
20 15 14 10 4
b
20
15
14
10
4
c
-1
-1
-1
-1
0
i
p
tot
①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
②如果c(p)＞b(i)，那么使p值增加1；
1 2 3 4 5 6 7 8 9 10
不同数据结构会导致处理效率的不同
（4）将数组b中元素b(i)逐个插入到数组c中（1≤i≤m）：
19
16
12
8
5
1 2 3 4 5
20 15 14 10 4
b
20
15
14
10
4
c
-1
-1
-1
0
i
tot
①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
1 2 3 4 5 6 7 8 9 10
不同数据结构会导致处理效率的不同
（4）将数组b中元素b(i)逐个插入到数组c中（1≤i≤m）：
19
16
12
8
5
1 2 3 4 5
20 15 14 10 4
b
20
15
14
10
4
c
-1
-1
0
i
tot
①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
1 2 3 4 5 6 7 8 9 10
不同数据结构会导致处理效率的不同
（4）将数组b中元素b(i)逐个插入到数组c中（1≤i≤m）：
19
16
12
8
5
1 2 3 4 5
20 15 14 10 4
b
20
15
14
10
4
c
-1
0
i
tot
①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
2.基于链表的算法设计与描述
用链表a存储数列A，且从头节点开始链表中每个元素成降序排列。用同样的方法将数列B存储到链表b中。两个链表的初始状态如图1.2.19所示，其中指针p、q分别指向每个链表的当前节点，指针p1指向链表a当前节点的前驱节点，指针q1指向链表b当前节点的前驱节点。
19
16
12
5 ^
8
head_a
指针p1
指针p
链表a:
20
15
14
4 ^
10
链表b:
head_b
指针q1
指针q
两个数列的合并=两个链表的合并
题目要求，将链表b中q指针所指节点插人到链表a中
只需将q所指元素与p所指元素比较;
如果p所指元素大于q所指元素，那么使p指针后移到下一个节点(同时指针p1也移到下一个节点)，直到p所指元素小于或等于q所指元素。
此时，不必像数组中那样移动数列C中的元素，而只需调整指针的指向，即可将q所指元素插人到链表a中p所指元素之前。
19
16
12
5 ^
8
head_a
指针p1
指针p
链表a:
20
15
14
4 ^
10
链表b:
head_b
指针q1
指针q
19
16
12
5 ^
8
head_a
指针p1
指针p
链表a:
20
15
14
4 ^
10
链表b:
head_b
指针q1
指针q
当将链表b中第一个元素20插入链表a时:
只需将链表a中p1所指节点的后继指针指向q所指元素;
链表b中q1所指节点的后继指针指向q所指节点的后继节点(元素15所在节点);
q所指节点的后继指针指向p所指节点;
最后将指针q指向q1所指节点的后继节点。
19
16
12
5 ^
8
head_a
指针p1
指针p
20
15
14
4 ^
10
head_b
指针q1
指针q
当将链表b中第一个元素20插入链表a时:
只需将链表a中p1所指节点的后继指针指向q所指元素;
链表b中q1所指节点的后继指针指向q所指节点的后继节点(元素15所在节点);
q所指节点的后继指针指向p所指节点;
最后将指针q指向q1所指节点的后继节点。
从用上述两种数据结构分别来解决同一个问题的过程可知，不同的数据结构会导致算法的不同，而且解决问题的效率也不同。
例如，用数组实现时需要将插入位置后面的所有元素逐个右移一位，当数列B中元素全部大于数列A中第一个元素时，将数列B中m个元素全部插入到数列A共需要移动n×m次;
当两个数列的元素大小比较均匀时，如A数列元素为20，18，16，12，6，而B数列元素为21，19，17，15，8时，共需要移动的次数也达到n+(n-1)+…+2+1= 次。
用链表实现时，向链表a中插入一个节点，最多需要5次指针操作，所以最多需要5m次指针操作，要比基于数组的处理低一个数量级。
链表 VS 数组
在插入元素中，
链表：动态存储、无需移动位置，只需找到头结点head
数组：静态存储、需要移动位置
1.2作业：
《创新设计》作业本 课时2
教学案 P6-P7

展开更多......

收起↑