初中信息技术浙教版 (2020)七年级下册第13课 初识数据结构教案设计

这是一份初中信息技术浙教版 (2020)七年级下册第13课 初识数据结构教案设计，共6页。教案主要包含了数据结构的概念， 常见的数据结构等内容，欢迎下载使用。

课题
初识数据结构
单元
第二单元
学科
信息技术
年级
七年级
学习
目标
知识目标：了解数据结构的概念及种类。
技能目标：理解计算机编程中数据的组织、存储和运算方法。
重点
数据结构的概念及种类；理解计算机编程中数据的组织、存储和运算方法。
难点
理解计算机编程中数据的组织、存储和运算方法。
教学过程
教学环节
教师活动
学生活动
设计意图
导入新课
同学们是不是有这样的经历，到图书馆去借阅、归还图书，通过电脑扫描能准确的知道图书的所在位置；学校学籍管理员通过电脑可准确查询每个学生的学籍信息。面对海量的数据，计算机是什么形式存贮的呢？这节课我们就一块来学习数据结构。
思考
激发学生学习兴趣并快速进入学习状态
讲授新课
利用计算机程序解决问题时，与问题有关的数据往往不仅数量庞大，而且存在着错综复杂的关系。
为了使计算机更加高效地处理数据，需要对数据进行有效的组织和管理，并以一定的形式加以存储和表示。
一、数据结构的概念
数据结构是计算机学科特有的概念，指数据之间的相互关系，即数据的组织形式。
合理的数据组织方式有利于提高解决问题的效率
如图书馆对书的存放与管理，根据图书分类法对图书进行分区、分类存放(如图所示)
并建立索引目录，从而提供快速借阅的服务。
计算机为了快速而高效地处理数据，也需要根据问题解决的特点对数据进行有效的组织与管理。
如音频播放器用“排队”方式组织播放列表中的歌曲，可以让先加入播放列表的歌曲先播放。
计算机操作系统采用多级树型目录结构对文件进行组织与管理(如图所示)
可以实现文件的分类存放和高效检索。
开动脑筋
在日常生活中还有哪些常见的数据组织管理形式?
亲身体验
在本班同学通讯录中，试着利用数据之间的关系设计出能快速找到家长电话号码的方法。
二、 常见的数据结构
在算法和程序设计中，需要结合数据和数据处理的特点，运用合适的数据结构组织数据、存储数据，才能高效地完成对数据的处理。
常见的数据结构有数组、栈、队列等。
1.数组
现实中表示一批数据，有时不仅需要描述数据的值，还需要描述数据所处的位置或数据之间的前后顺序关系
对于这类数据集合的组织，可以用数组这种数据结构来实现，如图所示。
用数组来组织数据时，既可以通过下标快速地访问序列中的某个数据元素，如果数组a中的第一个元素保存于a[0]
那么a[3]就表示数组中的第4个元素，也可以方便地按下标顺序遍历序列中的每个元素。
2.栈
栈是具有“后进入的数据先出去”特点的数据结构，采用的是一种数据进入顺序与数据出去顺序相反的数据管理方式，如图所示。
类似于在桌上堆放书，放书的时候是从下往上放(入栈)，最后放的书在最上面
而取书时则从最上面的一本书开始取走(出栈)，相当于后进入的数据(书)先出去(被取走)。
网页浏览器对用户浏览网页的管理，就采用了栈对网页数据进行组织。
当用户由一个网页跳转到另一个网页浏览时，系统将原先的网页数据进行入栈操作
而当用户单击浏览器“后退”按钮时，系统又将栈中最上方的网页数据出栈
户即可看到刚才浏览过的网页内容。
3.队列
队列是一种具有“先进入的数据先出去”特点的数据结构，采用的是数据进入顺序与出去顺序相一致的数据管理方式，如图所示
运用队列进行事物处理的例子
如食堂买饭时的排队、超市收银台付款时的排队、高铁站的出租车接站排队等。
在计算机中，打印管理程序就是用队列来组织发送给打印机一系列打印任务的。
打印机会根据收到的打印指令顺序，按照“先收到先打印”的原则组织打印任务的队列，再逐个打印文档，直到所有文档打印完毕。
日积月累
现实中要用计算机程序解决的问题是多种多样，各类问题中数据的相互关系也是多种多样的。
为了高效地解决这些问题，计算机科学家还发明了链表、树、图等数据结构。
链表
链表是物理存储单元上非连续的、非顺序的存储结构
数据元素的逻辑顺序是通过链表的指针地址实现，每个元素包含两个结点，一个是存储元素的数据域 (内存空间)，另一个是指向下一个结点地址的指针域。
根据指针的指向，链表能形成不同的结构，例如单链表，双向链表，循环链表等。
链表的优点：
链表是很常用的一种数据结构，不需要初始化容量，可以任意加减元素;
添加或者删除元素时只需要改变前后两个元素结点的指针域指向地址即可，所以添加，删除很快;
适用场景：
数据量较小，需要频繁增加，删除操作的场景
树
树是一种数据结构，它是由n(n>=1)个有限节点组成一个具有层次关系的集合。
把它叫做 “树” 是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。
树的特点：
每个节点有零个或多个子节点;
没有父节点的节点称为根节点;
每一个非根节点有且只有一个父节点;
除了根节点外，每个子节点可以分为多个不相交的子树;
图
图是由结点的有穷集合V和边的集合E组成。
其中，为了与树形结构加以区别，在图结构中常常将结点称为顶点，边是顶点的有序偶对，若两个顶点之间存在一条边，就表示这两个顶点具有相邻关系。
按照顶点指向的方向可分为无向图和有向图。
栈和队列的应用——回文数
一个自然数如果顺读和倒读都相同，那么该数就称为回文数。例如，22，383，5445，12321等都是回文数。
可以借助栈和队列来判断一个数是否为回文数。
先将该数除10取余得到个位上的数，然后同时入栈和队列，再将该数除10取整得到新数……如此循环，直到整除后商为0为止。
此时，该数各个数位(从低位到高位)上的数都已依次入栈和入队，如图所示的是123454321入栈和入队的过程。
入栈示意图
人队列示意图
再利用栈(后进先出)和队列(先进先出)操作的特点，比较每次出栈、出队的元素是否相同，即an与b1是否相同，an-1与b2是否相同……即可判断该数是否为回文数。
数学界有一些关于回文数的猜想。
例如，人们迄今未找到自然数(除0和1)的五次方，以及更高次幂的回文数，于是数学家们猜想：不存在nk(n≥2，k≥5；n、k均是自然数)形式的回文数。
人们发现，一个自然数与它的倒序数相加，所得的和再与和的倒序数相加……如此反复进行下去，经过有限次步骤，最后能得到一个回文数，但有些数并不“驯服”，
如196这个数，按照上述变换规则重复数十万次，仍未能得到回文数，但是人们既不能肯定运算下去永远得不到回文数，也不知道需要再运算多少步才能得到回文数。
随堂练习
1. 结合所学的几种数据结构，试着列举在生活中或使用计算机时还有哪些类似的数据结构应用。
通过教师的讲解，以小组合作的方式，开展探讨交流，完成任务。
学生小组间讨论，共同完成任务。
通过教师的讲解，以小组合作的方式，开展探讨交流，完成任务。
通过教师的讲解，以小组合作的方式，开展探讨交流，完成任务。
通过教师的讲解，以小组合作的方式，开展探讨交流，完成任务。
通过教师的讲解，以小组合作的方式，开展探讨交流，完成任务。
通过教师的讲解，以小组合作的方式，开展探讨交流，完成任务。
学生小组间讨论，共同完成任务，并分组汇报。
通过小组合作，加强学生组内团结、共同完成任务
养学生组间合作能力
通过小组合作，加强学生组内团结、共同完成任务
通过小组合作，加强学生组内团结、共同完成任务
通过小组合作，加强学生组内团结、共同完成任务
通过小组合作，加强学生组内团结、共同完成任务
通过小组合作，加强学生组内团结、共同完成任务
培养学生独立完成练习的能力。
课堂小结
分小组总结归纳，教师补充。
各组汇报总结，其他小组成员做补充。
锻炼学生的总结能力，逻辑思维、语言表达能力。
布置作业
1. 什么是数据结构?
板书
一、数据结构的概念
二、 常见的数据结构