1.2 数据的组织课件-2024-2025学年浙教版（2019）高中信息技术选修一

1.2 数据的组织 1 书架上的书 （查询操作） （修改操作） 思考:如何放书？如何找书？ 有两种基本操作： ①在书架上找到一本书 ②将一本书放到书架上 方法一：随便放 方法二：按照书名的拼音顺序依次插入 优点：修改快 缺点：查询慢 优点：查询快（有规律） 缺点：修改慢（要挪出空位置） 1.2 数据的组织 2 问题描述:若有一个多层书架，在书架上放置多个学科的教辅资料，需要频繁的放书找书，你会怎么规划设计？ 多层书架 数学 一 数学 二 数学 三 ...... 1.每层放一门学科教辅书 2.同层放书随意放 语文 一 语文 二 语文 三 ...... 英语 一 英语 二 英语 三 ...... 数据结构： ①数据结构是数据的一种组织形式 ②没有最好的数据结构， 只有最适合的数据结构。 3 图书馆新到一批图书，管理员要将图书的基本信息录入进计算机中，思考如下几个问题： 1.图书的基本信息包含哪些？ 书名、作者、定价、出版社...... 数据元素： 数据项： 数据的基本单位 具有独立含义的最小数据表示单位 4 2.存储在计算机中的数据分别有哪些数据类型？ 从左往右，依次为：整型、字符串型、字符串型、实型、字符串型、字符串型、日期型。 基本数据类型： 结构数据类型： 如Python编程语言中的整型、实型、布尔型等 数据类型：具有相同性质的计算机数据的集合以及这个数据集合上的一组操作 利用基本数据类型构造出的、复合的新类型，能较好地描述数据元素的数据项组成以及数据元素之间的逻辑关系。 5 3.图书数据按先后顺序录入计算机，如何组织这些图书数据？ 第一种：录入先后顺序就是图书存储位置的先后顺序 第1本 第2本 第3本 第4本 作家文丛—妙语连珠（上下） 中学生古诗文精读（初中卷） 中考英语经典阅读150篇 一分钟趣味推理（上下） 世纪灵魂的呼号与拷问（上下） 第5本 不仅描述数据（如图书信息）对象本身，还描述数据所处的位置或者数据之间前后顺序关系。 数组 优点：既可以快速地通过下标精确访问序列中某个数据元素，也可以通过下标按顺序依次访问。 a: a[1] a[2] a[3] a[4] a[5] 6 第二种：按类别顺序(A.B....I.G....)将图书数据组织起来,每本书只需知晓后面图书 作家文丛-妙语连珠（上下） I.文学 中学生古诗文精读（初中卷） I.文学 中考英语经典阅读150篇 G.文化、科学、教育 一分钟趣味推理（上下） I.文学 世纪灵魂的呼号与拷问（上下） G.文化、科学、教育 7 用箭头表示“后面是什么书籍”，抽象化后表示: 重新整理后的位置和链接关系 在组织、处理数据时，不关心数据实际所处具体位置，只需知道数据之间相互链接顺序。 链表 8 链表形式：单向链表、双向链表、循环链表 1.单向链表 head head head 2.双向链表 3.基于单向链表的循环链表 head 9 什么是数据结构？ 是数据之间的相互关系（数据的组织形式） ①逻辑结构 ②物理结构 ③操作 （逻辑上的先后顺序） （存储器中实际位置） （包括查询和修改操作） 数组 链表 10 下列数据在组织处理时，选用数组还是链表更合适？ 超市购物小票 电影票房榜 音乐播放列表 数组 数组 链表 11 洗碗问题：体现了怎样的数据组织？ 脏碗来一个洗一个 脏碗先堆积一些，洗碗时最上面的先洗 队列 栈 先到的碗就先洗 先到的碗后洗 12 排队是生活中一种常见的现象 机场有序排队安检 有序排队上车 对数据进行“先进先出”且中间不能“插队”的组织和操作。 队列 13 现场有6位客户已取号并处于等待状态，所取号码为0006到0011。如果接下来的时刻窗口2的客户办理结束，接着又有一位新客户在取号机上取了排队号（号码0012），则系统会让队首元素（0006号）出队并将号码传输到2号窗口的显示屏，同时将新客户刚取走的号码作为数据元素进行入队操作。 银行排队取号 队首出队 队尾入队 等待队列 0006 0007 0008 0009 0010 0011 0007 0008 0009 0010 0011 0007 0008 0009 0010 0011 0012 14 弹匣装子弹 弹匣出子弹 一种只能在一端进行插入和删除操作的数据结构，具有“先进后出”的特点。 栈 弹匣是一种具有栈结构和操作特征的装置 入栈 出栈 15 用户浏览网页 当用户由一个网页跳转到另一个网页浏览时，系统会将原先的网页进行入栈操作，而当用户单击浏览器的“后退”按钮时，系统又会将栈中最上方的网页数据出栈，用户即可看到刚才最后浏览过的网页内容。 “国内” 入栈 “社会” “科技” “生活” 出栈 16 数据结构：数组、链表、队列、栈 思考：若要对常见动物进行分类，数据要怎么组织？ 共同特点：除首尾数据元素外，中间任何一个数据元素的前面和后面都只有一个数据元素与它相邻。 线性表 17 树结构 一个元素前面（上面）只有一个元素，而后面（下面）却有多个（≥0）元素相邻，所有的数据元素之间的关系特征就像一棵倒放的树。 列举生活和信息系统中用树组织数据的例子。 中国国家图书馆图书分类法 常见动物分类图 18 瑞士计算机科学家沃斯（N.Wirth） 算法 + 数据结构 = 程序 数据的操作 数据的组织 对于同一问题，依据不同的数据结构设计算法，算法的处理效率，程序的实现效率不同。 19 某学校举行趣味运动会，高一开设了“滚铁圈”“打弹子”“拍纸板”“跳绳”“踢毽子”6个项目的比赛。比赛结束后需要根据每位选手各个项目的得分来统计每位选手的总分以及各班级的总分。 思考：需要收集的数据有哪些？数据之间存在怎样的关系？ 选手各项目的得分 每位选手均有6个项目得分 滚铁圈 打弹子 拍纸板 趣味运动会项目 20 各位选手在各个项目上的得分 数据之间是线性关系，选用数组存储，更有利于表达数据之间的关系。 基于数组去设计算法，解决问题。 1.设计算法解决问题离不开数据结构 21 各位选手在各个项目上的得分 每列都是一批相同性质和类型的数据，每一列可以用一个一维数组存储。 用9个一维数组来组织存储数据 用一维数组sum来表示每位选手的总得分 14 9 11 11 19 ... 一维数组bjdf存储各班总得分 22 用包含行号和列号两个位置信息的二维数组来组织、存储数据。 （4,3） 用二维数组组织学生成绩数据 14 9 11 11 19 ... 用a[i,8]来保存第i位选手的总得分 一维数组bjdf存储各班总得分 23 基于二维数组 基于一维数组 为了统计每位选手和各班的总得分，基于数组的总体算法都是通过遍历各位选手的相关数据进行。但是，用计算机程序设计语言描述算法时，相比于一维数组，二维数组在程序实现效率上要高于前者，特别在每位选手总分统计部分。如果数据项增加，两者相差会更大。 2.不同数据结构会导致处理效率的不同 24 总结 1.数据结构： 2.常见的数据结构及其特征： 3.数据结构的作用： 数据的组织形式：物理结构 + 逻辑结构+操作 线性：数组、链表、队列、栈 非线性：树 ①设计算法解决问题离不开数据结构 ②不同的数据结构导致处理效率不同 25 对自己和同伴的表现进行客观的评价，并思考后续完善的方向。（5=优秀，4=超出一般水平，3=满意，2=有待改进，1=不太理想） 学习评价 26 $$