1.2 数据的组织（教学设计）信息技术浙教版2019选择性必修1

1.2 数据的组织 3课时（教学设计） 年级 高二年级 授课时间 3课时 课题 1.2 数据的组织 教学 目标 1.初步理解数据结构的概念及其作用。 2..体会不同数据结构的区别。 3.通过完成数据合并任务，体会数据结构的作用。 教学 重难点 重点：1.数据的结构的概念。 2.数据结构的作用。 难点：对不同的数据，选择正确的数据结构。 教学 准备 多媒体课件、多媒体教室 教学过程 教师活动 学生活动 新 课 导 入 一、课堂导入 1.提问：同学们，程序是什么样子的呢？ 通过提问，引出本堂课的主题。 展示瑞士计算机科学家：尼古拉斯·沃斯 算法+数据结构=程序 在计算机程序设计中，根据问题求解的需要，对数据进行有效的整理和组织，并以一定的形式加以存储和表示的过程称为数据结构的设计。 学生听到老师的提问，思考并观看教师的PPT课件上的图片提示，从而引出本堂课的主题。 新 知 讲 授 2、 数据结构的概念 现实问题中的数据往往具有多样性和复杂性的特点，为了有效组织数据，必须对各种数字数据加以分类，对互相有关联的数据进行合理重组，在此基础上，才能较好地选择、设计数据结构。 1.数据元素 数据元素是数据的基本单位。数据元素也称为元素、节点、顶点、记录等。有时一个数据元素可以由若干个数据项(也称为字段、域)组成，数据项是具有独立含义的最小数据表示单位。 图中所示：每一行实际内容(也称为一条记录)就是数据元素，而每个 元素又由5个数据项(“代码”“名称”“最新价格”“动态市盈”“流通股本”)组成。 提问： 这张表一共有多少个数据元素? 第四个数据元素的第五个数据项的名称为什么?值为什么? 2.数字类型 数据类型指的是具有相同性质的计算机数据的集合及在这个数据集合上的一组操作。 数据类型可以分为基本数据类型(也称为原子数据类型)和结构数据类型。 3.数据结构 数据结构指的是数据之间的相互关系，即数据的组织形式。 数据结构包括以下三个方面的内容： ①数据元素之间的逻辑关系，也称为数据的逻辑结构。 ②数据元素及其关系在计算机存储器内的表示，也称为数据的存储结构或物理结构。 ③数据的运算，即对数据施加的操作。 4.课堂练习 （1）关于数据项与数据元素的描述,下面说法不正确的是( B ) A.数据元素可由若干数据项组成 B.同一数据元素中各数据项的数据类型必须相同 C.数据项是数据的最小单位,通常用来描述实体的某种属性 D.数据元素是数据的基本单位,在计算机中通常作为一个整体来处理 （2）数据元素及其关系在计算机存储器内的表示,也称为数据的( B ) A.线性结构 B.物理结构 C.逻辑结构 D.空间结构 三、常见的数据结构 数据结构设计是为了解决实际问题而出现的科学，选择合适的数据结构来组织与存储数据，可以达到高效处理数据的目的。 1.数组 表示一批数据，不仅可以描述数据本身，还可以描述数据所处的位置或数据之间的前后顺序关系。可以迅速地通过下标精确访问序列中的某个数据元素，又可以通过下标按顺序遍历序列中的每个元素。 通过列举一列纵队排队的人来进行实例讲解，当一队人依次排队时，为了描述他们之间的前后关系，可以用“第1个是李彤”“第2个是张强”“第3个是胡洁”“第4个是杜刚”这种方式表达。 如果将上述表达进一步抽象，那么这批数据序列可用“a[1]="李彤"、a[2]="张强"、a[3]="胡洁"、a[4]="杜刚"”来表达。在这种表达方式中，a[1]、a[2]、a[3]、a[4]就组成了数组a。其中，变量名a说明这是一批类型相同的数据，下标1、2、3、4表示了数据元素所处的位置顺序。例如，“a[3]="胡洁"”说明“胡洁”处于第3个位置上，她的前面是第2个位置上的“张强”，后面是第4个位置上的“杜刚”。 拓展链接：遍历 2.链表 同样是对一批人员数据进行组织，有时只需知道相邻人员之间的前后顺序关系，而对每个人员的位置信息并不作要求。 通过实例：整队前的位置和链接关系的讲解，吴坚知道自己排在首位，王林知道排在自己前面的是吴坚，黄刚知道排在自己前面的是王林，李丰知道排在自己前面的是黄刚。有了这些相邻人员之间的链接关系，即使休息时大家分散在各处，一旦需要集合，大家可以根据链接关系快速地按照原顺序排成队伍。虽然整队前后每个人员的站位地点发生改变，但相互之间排队的顺序关系是不变的。 再对抽象化后的排队链接关系进行讲解，组织、处理一批数据时， 若不关心数据实际所处的具体位置，而只需知道数据之间相互链接的顺序时，可以借鉴上面的方法。在计算机科学中,这种方法的具体实现形式就是链表。 在计算机科学中，这种方法的具体实现形式就是链表。根据解决问题的需要，链表可以有多种存在形式，常用的有单向链表、双向链表、循环链表。具体操作时，为了记录、识别各个链表，需要在链表首部设立一个头节点，同时用一个变量head记住这个头节点，这样就可以从head指向的头节点开始(head在这里也可称为指针)依次逐个遍历链表中的每个节点，链表中的指针可以指向前面，也可以指向后面。 探讨与讨论： （1）数组的特点？ 不仅需要描述数据对象本身，还需要描述数据所处的位置或者数据之间的前后顺序关系 （2）链表的特点？ 只需知道数据之间相互链接的顺序 （3）在数组中插入元素和在链表中插入元素的差别? 数组:整体后移空出位置插入 链表:改变指针 拓展链接：指针 3.队列 通过列举：展示有序排队上车的乘客和有序排队接客的出租车的图片，让同学直观的观看和理解：乘客排队时先到的总是从队伍的头部出去(出队)上车，而后到的乘客则必须在队伍的尾部加入(入队)。同时，为了确保有序，人们总是规定不能从队伍的中间部位插队。 再次列举：银行叫号系统和银行叫号系统经过一次出队和入队操作后的状态对比，直观的引出队列的实际价值，用计算机程序处理数据时，有时也需要将数据进行“排队”，并遵循现实中排队的规律，对数据进行“先进先出”FIFO(First In First Out)且中间不能“插队”的组织和操作，计算机科学家由此发明了“队列”这种数据结构。 4.栈 通过例举栈的实例：弹匣的装弹过程，弹匣是一种典型的具有栈结构和操作特征的装置，即只能在连接枪体的一端进行子弹压装、弹出操作，所以弹匣是一个“栈”。在这个装置中，子弹被装入弹匣称为“入栈”，子弹被弹出弹匣称为“出栈”。 总结出栈的特点： ①整个装置只有一端开放(最上端)，而且进、出只能在这一端进行。 ②弹匣中的子弹成一纵队排列。 ③任何子弹进出弹匣的规律是“先进后出、后进先出”，即最先装入弹匣的子弹最后才能被弹出，而最后装入弹匣的子弹则最先被弹出。 小组讨论：在文字处理软件Word中输入若干文字，然后删除其中部分文字，再输入若干文字。然后进行“撤消”操作(按Ctrl+Z键，或者单击撤消操作快捷按钮 5.树 通过列举常见动物分类图和图书馆图书分类法，得出一个元素前面(或上面)只有一个元素，而后面(或下面)却有多个(0个或多个)元素相邻，所有的数据元素之间的特征就像一棵倒放的树。 树的概念：树是由n (n≧0) 个节点构成的一个有限集合以及在该集合上定义的一种节点关系。 探讨与讨论：分小组讨论，举出在生活和信息系统中用树组织数据的例子，并用树结构描述数据之间的关系特征。 6.重点提示与课堂练习 四、 数据结构的作用 每个实际问题中的数据之间存在着一定的关系，用计算机程序解决问题时，需要将数据之间的这些关系映射到程序的数据表示中，这样才能有效地用计算机程序解决问题。 对于同一个问题的解决，当依据不同的数据结构来设计算法时，算法的处理效率、程序的实现效率也是不同的。 1.设计算法解决问题离不开数据结构 通过举例，某学校举行趣味运动会，高一开设了“滚铁圈”“打弹子”“拍纸板”“竹蜻蜓”“跳绳”“踢毽子”6个项目的比赛。比赛结束后需要根据每位选手各个项目的得分来统计每位选手的总分以及各班级的总分。 统计出给位选手的得分，用一张表格来组织数据并表示数据之间的逻辑关系。根据本问题中数据之间的线性关系特点，可基于数组来设计算法并解决问题。如果不针对数据之间的关系特点设计数据结构，而是直接用一个个简单变量来存储所有学生姓名和各项得分，在此基础上设计算法及编写程序的工作量将变得非常巨大，用计算机处理这些数据就变得毫无意义。 2.不同的数据结构会导致处理效率的不同 （1）用一维数组组织数据 通过一段Python程序来统计每个班的总分，当完成对所有选手的遍历时，每位选手的总得分就保存到数组sum中，而每个班级的总分则保存到数组bjdf中。 （2）用二维数组组织数据 通过一段Python程序来统计每个班的总分，面对的是一组二维数组组织的数据，通过两段程序来进行直观的对比，一维数组程序实现 和二维数组程序实现的直观对比。但在用计算机程序设计语言描述算法(编写程序)时，相比于一维数组，二维数组在程序实现效率上要高于前者，特别在每位选手总分统计部分。如果数据项数量增加，那么两者相差会更大。 讨论实例：数据合并：生产厂家总会根据各地产品销量的数据分析来预估市场情况，并为后续调整生产规数据合并划、完善营销策略提供依据。 由于数据量巨大，为了充分运用分布式处理的优势，总部会要求各下属地区上报数据时，按各产品销量进行从大到小的排序。总部收到数据后的第一件事是将所有数据合并并按照销量进行降序排序(从大到小)，为了完成数据合并和整理工作，总部数据分析员小刚需要设计合适的数据结构和算法。 分析：小刚可以用一个二维数组存储所有下属地区的产品销量数据，然后直接运用排序算法进行降序排序。如果利用既有数据已是分块有序的特点，设计新的数据结构和算法，则处理效率可以得到相应的提升。 各个地区的数据合并问题可以简化为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)。请完成解决该问题的数据结构和算法的设计。 第二步设计、描述算法 ①基于数组的算法设计与描述 A.将数组a中所有元素存储到数组c的前n个位置中; B.将数组c右边的m个元素赋值为-1 (c(n+1)直到c(n+m))； C.变量p赋值为0，将表示数组c中有效元素总个数的变量tot赋值为n； D.将数组b中元素b(i)逐个插入到数组c中(1≤ism)； ②基于链表的算法设计与描述 对比链表的初始状态和实施1次插入后的链表状态 五、课堂小结 通过列举教材中数据元素及其包含的数据项，引导学生经历自主思考，通过自学，认识数据结构的相关概念，能用数据结构相关的概念名词对问题进行解答。(意图:体现先学后教的理念。） 通过课堂练习，加深同学们对数据结构的理解，本问题讨论的目的一是引导学生进一步理解数据结构的概念。 结合现实事例开展教学，既能促进学生的学习兴趣，又能使学生对数据结构在社会中的作用产生鸟瞰式的认知。 通过列举一列纵队排队的人来进行实例讲解，让学生感受数组在当今生产生活的运用。 同样通过实例：整队前的位置和链接关系的讲解，然后再将排队链接关系进行抽象化的展示，让学生理解单向链表、双向链表、基于单向链表的循环链表。 通过探讨与讨论，加深同学们对数据结构的理解，本问题讨论的目的一是引导学生进一步理解数据结构的类型。 通过例举栈的实例：弹匣的装弹过程，让学生直观的了解栈这种数据结构。 通过列举常见动物分类图和图书馆图书分类法，了解树的结构。 课 堂 练 习 （有题有答案有解析） 1.常见的数据结构包括： 、 、 、 、 、 等。 2.数组的特点？ 3.链表的特点？ 4.在数组中插入元素和在链表中插入元素的差别? 5.队列的特点? 6.栈的特点? 7.队列和栈有什么共同点? 8.关于数据项与数据元素的描述,下面说法不正确的是( ) A.数据元素可由若干数据项组成 B.同一数据元素中各数据项的数据类型必须相同 C.数据项是数据的最小单位,通常用来描述实体的某种属性 D.数据元素是数据的基本单位,在计算机中通常作为一个整体来处理 9.以下关于数据结构的描述，不正确的是( ) A.数据的逻辑结构是指数据元素之间的逻辑排列和对应关系 B.数据的存储结构包括数据元素的存储及数据元素之间关系的存储 C.数据的运算是指对数据施加的操作，包括删除、查找、插入数据等 D.数据结构设计时不需要考虑编程实现和数据处理的效率 10.在日常幻灯片(如PowerPoint演示文稿)的放映中,可以通过超链接的方式进行幻灯片之间的任意跳转。与这种页面之间相互链接的表现形式相似的数据结构是( ) A.树 B.链表 C.队列 D.栈 11.半结构化数据包括（） A. Excel 表格 B.银行账户上的消费记录 C.检查身体后得到的体检报告 D.HTML文档 12.下列选择中数据结构不是图结构的是（） A.城市交通网 B.电话网 C.公司组织架构 D.互联网 答案： 1.数组、链表、队列、栈、树和图等。 2.不仅需要描述数据对象本身，还需要描述数据所处的位置或者数据之间的前后顺序关系 3.只需知道数据之间相互链接的顺序 4.数组:整体后移空出位置插入 链表:改变指针 5.先进先出，不能插队 6.先进后出，后进先出 7.都是线性关系 8.[解析]同一数据元素中各数据项的数据类型并不需要完全相同，所以选项B同一数据元素中各数据项的数据类型必须相同说法错误。 答案：B。 9.[解析]数据结构设计的目的是使数据元素间的相互关系能准确地反映现实问题中的事物逻辑，既确保数据处理的正确性，又提高编程实现和数据处理的效率。在设计数据结构时，就需要考虑效率问题。 答案：D 10.[解析]本题考查常见的数据结构。链表可通过指针在节点之间跳转,符合题意。 答案：B 11.[解析]本题考查的是数据相关知识。半结构化数据是指介于结构化数据和非结构化数据之间的数据，具有一定的结构性。HTML文档属于半结构化数据。 答案：D 12.[解析]图结构是多对多的关系，城市交通图、电话网、互联网均属于图结构，公司组织架构图是一对多的关系。 答案：C 课 堂 小 结 课堂小结 1.数据结构的概念 (1) 数据元素:数据的基本单位，可由若干数据项组成。数据项是具有独立含义的最小数据表示单位。 (2)数据类型:具有相同性质的计算机数据的集合及在这个数据集合上的一组操作。数据类型可分为基本数据类型和结构数据类型。 (3) 数据结构:数据之间的相互关系，即数据的组织形式。主要包含数据的逻辑结构、数据的存储结构和数据的运算。 2.常见的数据结构 常见的数据结构有数组、链表、队列、栈、树和图等。数组、 链表、队列、栈都是线性表的特殊形式。 3.数组的优缺点 数组的优点 (1)随机访问性强 (2)查找速度快 数组的缺点 (1)插入和删除效率低 (2)可能浪费内存 (3)内存空间要求高，必须有充足的连续内存空间 (4)数组大小固定，不能动态拓展 4.链表的优缺点 链表的优点 (1)插入删除速度快 (2)内存利用率高，不会浪费内存 (3)大小没有固定，拓展灵活 链表的缺点 不能随意查找，必须从第一个开始遍历，查找效率低 作 业 设 计 1.数据元素及其关系在计算机存储器内的表示,也称为数据的( ) A.线性结构 B.物理结构 C.逻辑结构 D.空间结构 2.用一个带盖(另一端封闭)的透明塑料筒来放取乒乓球，且筒的直径只允许一个乒乓球进出，如图，若放入球的编号序列为1、2、3、4，则取出球的编号序列可能的是( ) A.1、2、3、4 B.3、1、2、4 C.4、2、3、1 D.2、4、1、3 3.小陈同学高一结束后需要换寝室,他将全部物品打包成6个箱子并编号叠放在一起(如图1-10所示)。为了搬运物品方便,他借了一辆手推车,该手推车一次最多能叠放3个箱子(如图1-11所示)。箱子从上往下依次叠放在小推车上(假定每次只放一个箱子),小推车每次可以叠放1、2或3个箱子,小推车上的箱子也是从上往下依次拿取(假定每次只取一个箱子),搬运后的箱子仍旧叠放在一起。 (1)在搬运中,与手推车上箱子叠放和拿取的过程相似的数据结构是 。 (2)若搬运完毕后箱子的叠放顺序是2、1、3、4、6、5(从下往上),则每趟手推车至多需要搬运的箱子数是 个。 4.诸葛亮家族的部分家谱如图1-6所示。和家谱图结构相似的数据结构是( ) A.链表 B.队列 C.树 D.栈 5.在日常幻灯片(如PowerPoint演示文稿)的放映中,可以通过超链接的方式进行幻灯片之间的任意跳转。与这种页面之间相互链接的表现形式相似的数据结构是( ) A.树 B.链表 C.队列 D.栈 6.在生活中,我们常常可以看到事物以矩阵的形式进行摆放,如超市商品的货架摆放,货架有n层,每层有m列(如图1-7所示)。如果要用程序来实现对货架不同位置的商品编号进行存储,可借用的数据结构是 。 7.图中配送快递方式是属于 的 关系。（） A. 线性结构，多对多 B.树结构，一对多 B. 图结构，多对多 D.集合，一对多 8.下图中的数据属于（） A.结构化数据 B.半结构化数据 C.非结构化数据 D.准结构化数据 9.树的递归定义如下:树是由n(n（）)个节点组成的（）集合。若n（），则称为（）。任何一个非空树均满足以下二个条件:(1)仅有一个（）。(2)当n>0时，其余节点可分为m(m>=0)个互不相交的有限集合，其中每个集合又是一棵树，并称为（）。 A.>0;有限;=0;空树;根节点;根的子树 B.>=0;有限;>0:空树;根节点;根的子树 C.>=0;有限;=0;空树;根的子树;根节点 D.>=0;有限;=0;空树;根节点;根的子树 答案： 1.[解析]本题考查的是数据结构。数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。数据结构反映数据的内部构成，即数据由那部分构成。 答案：B。 2.[解析]透明塑料筒一端封闭，乒乓球的放入和取出过程，与数据结构中栈的入栈和出栈过程相似。 答案：A 3.栈、2 4.[解析]家谱图中有根节点(诸葛珪)和子节点(诸葛瑾、诸葛亮等),符合树结构特征。 答案：C 5.[解析]本题考查常见的数据结构。链表可通过指针在节点之间跳转,符合题意。 答案：B 6.[解析]摆放排列有行、列,可以看成是二维数组。也可以将每一行作为一个数据元素,使用一维数组存储,整行作为数组元素。 答案：数组 7.[解析]本题考查的是数据结构的相关知识。线性结构是一个有序数据元素的集合。常用的线性结构 有:线性表、栈、队列、双队列、串(一维数组)。关于广义表、数组(高维)，是一种非线性的数据结构。常见的非线性结构有:二维数组、多维数组、广义表、树(二叉树等)、图。通过观察上图可得，配送快递方式是，属于树结构的一对多关系。 答案：B 8.A 9.[解析]本题考查数据结构相关知识。树的递归定义如下:树是由n树的递归定义如下:树是由n(n>=0)个节点组成的有限集合。若n=0，则称为空树。任何一个非空树均满足以下二个条件:(1)仅有一个根节点。(2)当n>0时，其余节点可分为m(m>=0)个互不相交的有限集合，其中每个集合又是一棵树，并称为根 的子树。 答案：D 反 思 评 价 本堂课讲解的是理论方面的知识，比较枯燥，只有通过大量的举例来充实课堂。通过列举实例，分析数据结构的概念、常见的数据结构及其作用，让学生们初步理解数据结构的概念及其作用。体会不同数据结构的区别。.通过完成数据合并任务，体会数据结构的作用。 原创精品资源学科网独家享有版权，侵权必究！ 学科网（北京）股份有限公司 学科网（北京）股份有限公司 $$