资源简介

(共19张PPT)
第一章 数据与数据的组织
选修1《数据与数据结构》
学习目标
数据
数据
数据的组织
数据
数字、数值、文字、图形、图像、音频、视频等
数字：阿拉伯数字0~9或其他含义相同的符号表示。
其本身没有意义，没有量的含义。数字只是一个符号。
数值：由数字符号组成，具有量的意义、可进行算术运算的数据。
在数字化时代中，数据是指用计算机进行处理的符号表示的总称。
数据
·数据的表现形式
数据
1、数据促进了人类社会的发展。
人类社会是在数据的表示和分析中不断发展前进的。
2、大数据推动人类进入一个崭新的时代。
大数据不单指数据的海量，而是针对具有“4V”特征的数据。
大数据技术是指提高对这些数据的“加工能力”，通过“加工”实现数据“增值”的一系列硬件和软件技术的综合。
数据
·数据的价值与意义
数据的组织
1、数据元素
它是数据的基本单位。
在Excel表或DataFrame中的数据元素是由若干个数据项（也称为字段、域）组成。数据项是具有独立含义的最小数据表示单位。数据项包括数据项名称和数据项的值。
2、数据类型
指具有相同性质的计算机数据的集合以及在这个数据集合上的一组操作。
数据
·数据结构的概念
基本数据类型：
结构数据类型：
整型、实型、布尔型、字符串、列表、字典
自定义的类
数据的组织
3、数据结构
它是指数据之间的相互关系，即数据的组织形式。
包括三个方面：（数据结构一般指向的是逻辑结构）
①数据元素之间的逻辑关系，也称为数据的逻辑结构。
②数据元素及其关系在计算机存储器内的表示，也称为数据的存储结构或物理结构。
③数据的运算，即对数据施加的操作。
目的：使数据元素间的相互关系能准确地反应现实问题中的事物逻辑，既确保数据处理的正确性，又提高编程实现和数据处理的效率。
数据
·数据结构的概念
数据的组织
1、数组
·它是指存储一个固定大小的相同类型元素的顺序集合。
·内存存放方式：
数据
·常见的数据结构
a b c d e
0 1 2 3 4
元素
索引
由上图可知：所有的数组都是由连续的内存位置组成。
最低地址
最高地址
数据的组织
1、数组
·Python语言中，没有数组这种数据结构，但是列表可以完成数组的功能。
·内存存放方式：例如 sname = [‘a’, ’b’, ’c’, ’d’, ’e’]
数据
·常见的数据结构
a b c d e
0 1 2 3 4
-5 -4 -3 -2 -1
元素
顺序索引
·访问列表元素：
sname[0] = sname[-5] = ‘a’
逆序索引
数据的组织
2、链表
·定义：
它是一组数据项的集合，其中每个数据项都是一个节点的一部分，每个节点还包含指向下一个节点的链接。
·节点结构：
data为自定义的数据，next为下一个节点的地址
数据
·常见的数据结构
data next
一个链表节点
数据的组织
2、链表
数据
·常见的数据结构
链表内存存放方式：
head
(头节点)
tail
None
数据域
指针域
My_list
基本元素：
（1）节点：每个节点有两个部分，左边称为数值域，存放用户数据；右边部分称为指针域，用来存放指向下一个元素的指针（地址）。
（2）head：head节点永远指向第一个节点
（3）tail：tail永远指向最后一个节点
（4）None：链表中最后一个节点的指针域为None值
数据的组织
2、链表
·链表种类：
数据
·常见的数据结构
（1）单向链表：
（2）双向链表：
（3）循环链表：
数据的组织
3、队列
·概念：
队列是一种先进先出的线性表，允许插入的一端称为队尾，允许删除的一端称为队首。
队列元素：队列中的数据元素。
入队：在队列中插入一个元素的过程。
出队：从队列中删除一个元素的过程。
数据
·常见的数据结构
出队
入队
队首元素
队尾元素
数据的组织
4、栈
·概念：
栈是一种先进后出的操作受限的线性表，仅允许在表的一端进行插入或删除。
栈顶：进行插入或删除操作的一端。
栈顶元素：位于栈顶位置的元素。
栈底：不进行操作的一端。
栈底元素：位于栈底位置的元素。
数据
·常见的数据结构
栈底元素
栈顶元素
数据的组织
5、树
·概念：
树是由n（n≧0）个节点构成的一个有限集合以及在该集合上定义的一种节点关系。
节点：集合中的元素。
空树：n=0的树。
子树：树中某个节点下面的所有节点
所构成的树。
数据
·常见的数据结构
第1层
第2层
第3层
第4层
数据的组织
1、设计算法解决问题离不开数据结构
2、不同数据结构会导致处理效率的不同
·用一维数组组织数据：
数据
·数据结构的作用
a[0] a[1] a[2] ...... a[n-1]
1 2 3 ...... n
数组a：
各个元素表示的形式
各个元素值
在Python语言中，列表可以实现数组的功能。
例如：a=[1, 2, 3, 4, 5]
访问列表元素也和数组一致。
数据的组织
2、不同数据结构会导致处理效率的不同
·用二维数组组织数据：
数据
·数据结构的作用
数组a：
元素访问：a[n-1, 2] = x2
0 1 2 ...... n
0 a0 a1 a2 ...... an
1 b0 b1 b2 ...... bn
. . . . . . . . . . . . . . . .
.
.
n-1 x0 x1 x2 ...... xn
i
j
i：行坐标
j：列坐标
在Python中，用列表的形式表示。
例如：a=[[1,2,3],[2,4,6],[3,6,9]]
访问元素：
a[2][2]=9 a[0][2]=3
数据的组织
2、不同数据结构会导致处理效率的不同
·用数组合并两个数组元素：
数据
·数据结构的作用
a[1] a[2] a[3] a[4] a[5]
19 16 12 8 5
b[1] b[2] b[3] b[4] b[5]
20 15 14 10 4
c[1] c[2] c[3] c[4] c[5] c[6] c[7] c[8] c[9] c[10]
19 16 12 8 5 -1 -1 -1 -1 -1
20 19 16 12 8 5 -1 -1 -1 -1
20 19 16 15 12 8 5 -1 -1 -1
20 19 16 15 14 12 8 5 -1 -1
20 19 16 15 14 12 10 8 5 -1
20 19 16 15 14 12 10 8 5 4
第1步：
第2步：
第3步：
第4步：
第5步：
第6步：
数组a：
数组b：
合并
数组c：
数据的组织
2、不同数据结构会导致处理效率的不同
·用链表合并两个链表元素：
数据
·数据结构的作用
19
16
12
8
5 ^
链表a:
head_a
20
15
14
10
4 ^
链表b:
head_b
19
16
12
8
5 ^
链表a:
head_a
20
15
14
10
4 ^
链表b:
head_b
数据的组织
2、不同数据结构会导致处理效率的不同
·数组的优点
(1)随机访问性强
(2)查找速度快
·数组的缺点
(1)插入和删除效率低
(2)可能浪费内存
(3)内存空间要求高，必须有充足
的连续内存空间
(4)数组大小固定，不能动态拓展
数据
·数据结构的作用
·链表的优点
(1)插入删除速度快
(2)内存利用率高，不会浪费内存
(3)大小没有固定，拓展灵活
·链表的缺点
不能随意查找，必须从第一个开始遍历，查找效率低

展开更多......

收起↑