资源简介 (共97张PPT)信息技术浙教版七年级下第13课初识数据结构新知导入同学们是不是有这样的经历,到图书馆去借阅、归还图书,通过电脑扫描能准确的知道图书的所在位置;学校学籍管理员通过电脑可准确查询每个学生的学籍信息。面对海量的数据,计算机是什么形式存贮的呢?这节课我们就一块来学习数据结构。新知讲解利用计算机程序解决问题时,与问题有关的数据往往不仅数量庞大,而且存在着错综复杂的关系。为了使计算机更加高效地处理数据,需要对数据进行有效的组织和管理,并以一定的形式加以存储和表示。新知讲解一、数据结构的概念数据结构是计算机学科特有的概念,指数据之间的相互关系,即数据的组织形式。新知讲解并建立索引目录,从而提供快速借阅的服务。合理的数据组织方式有利于提高解决问题的效率如图书馆对书的存放与管理,根据图书分类法对图书进行分区、分类存放(如图所示)新知讲解新知讲解如音频播放器用“排队”方式组织播放列表中的歌曲,可以让先加入播放列表的歌曲先播放。计算机为了快速而高效地处理数据,也需要根据问题解决的特点对数据进行有效的组织与管理。新知讲解新知讲解计算机操作系统采用多级树型目录结构对文件进行组织与管理(如图所示)可以实现文件的分类存放和高效检索。新知讲解在日常生活中还有哪些常见的数据组织管理形式?开动脑筋新知讲解在本班同学通讯录中,试着利用数据之间的关系设计出能快速找到家长电话号码的方法。亲身体验新知讲解二、常见的数据结构在算法和程序设计中,需要结合数据和数据处理的特点,运用合适的数据结构组织数据、存储数据,才能高效地完成对数据的处理。常见的数据结构有数组、栈、队列等。新知讲解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.什么是数据结构?作业布置板书设计一、数据结构的概念二、常见的数据结构谢谢21世纪教育网(www.21cnjy.com)中小学教育资源网站有大把高质量资料?一线教师?一线教研员?欢迎加入21世纪教育网教师合作团队!!月薪过万不是梦!!详情请看:https://www.21cnjy.com/help/help_extract.php新知导入同学们都知道“田忌赛马”的故事,那么“田忌赛马”的故事说明了什么问题?我们可以想到,不同的方法会有不同的效率,所以在完成一项任务的时候,一定要开动脑筋,多想一想,尽量找到最优的方法。现实生活中,我们也经常遇到这样的问题,如何解决呢?今天我们来学习解决方法。新知讲解新知讲解新知讲解交换变量X、Y值的步骤,用自然语言描述如下:①定义三个变量X、Y、T。②把1赋值给变量X,把2赋值给变量Y(赋初值)。③把X中的值传递给T,再把Y中的值传递给X,最后把T中的值传递给Y。(2)确定算法。④结束程序员可以轻松的使用VB提供的组件快速建立一个应用程序。步骤1:将衣物放入洗衣机;新知讲解算法的描述方法很多,有自然语言、流程图、计算机语言等,其中流程图是算法设计时常用的一种描述方法新知讲解自然语言是人们在日常生活中交流使用的语言,如汉语、英语、德语等语言。通过自然语言描述的算法,往往通俗易懂一、算法的自然语言描述新知讲解用自然语言表示一个“登录程序”,实现:输入账号和密码,校验是否正确。开动脑筋新知讲解步骤1:将衣物放入洗衣机;例如,对于洗衣机洗涤过程的算法,自然语言表示如下:步骤2:加水并放入洗涤剂;步骤3:洗涤衣物;步骤4:若洗涤时间到了,则结束,否则继续执行步骤3。新知讲解在本班同学通讯录中,试着利用数据之间的关系设计出能快速找到家长电话号码的方法。亲身体验新知讲解“登录程序”算法用自然语言可以描述如下:(1)输入账号和密码。(2)判断输入的账号和密码是否正确。(3)若账号和密码均正确,则输出“登录成功!”,否则输出“账号或密码有误!”。新知讲解二、算法的流程图表示流程图是常用的算法表示方法。用流程图表示算法,步骤显得直观、明确并易于理解。新知讲解1.认识流程图流程图是一种以图解方式表示算法的描述方法,常用符号及含义如下所示:图形名称含义开始或结束框流程的开始或结束处理框对数据进行处理新知讲解图形名称含义输入或输出框数据的输入或输出判断框根据条件判断,选择其中一个分支流程线表示流程的走向新知讲解例如,“洗衣机洗涤过程”算法的流程图,如图所示。新知讲解新知讲解1.认识流程图绘制流程图的常见软件有很多,如OfficeWord流程图绘制工具、OfficeVisio、Raptor等。其中,OficeVisio使用比较方便,Raptor是基于流程图的编程环境。新知讲解(1)启动OfficeVisio2010,选择“文件”→“新建”→“基本流程图”,如图所示。新知讲解接下来绘制“求两个数中较大的数”的流程图。新知讲解(2)添加形状和文本。在形状窗口中将所需的形状拖动到绘制页面,并调整大小和位置,然后在形状中添加文本,如图所示。新知讲解(3)、添加流程线。移动端点,连接形状,如图所示。新知讲解用流程图表示一个“登录程序”,实现:输入账号和密码,校验是否正确。开动脑筋新知讲解随堂练习1.流程图常用符号及含义是什么?课堂小结总结本节课所学内容1.用流程图表示“输入三个数,输出其中最大的数”的算法。作业布置板书设计一、生活中的算法二、计算机解决问题的一般过程三、计算机语言谢谢21世纪教育网(www.21cnjy.com)中小学教育资源网站有大把高质量资料?一线教师?一线教研员?欢迎加入21世纪教育网教师合作团队!!月薪过万不是梦!!详情请看:https://www.21cnjy.com/help/help_extract.php新知导入同学们都知道“田忌赛马”的故事,那么“田忌赛马”的故事说明了什么问题?我们可以想到,不同的方法会有不同的效率,所以在完成一项任务的时候,一定要开动脑筋,多想一想,尽量找到最优的方法。现实生活中,我们也经常遇到这样的问题,如何解决呢?今天我们来学习解决方法。新知讲解新知讲解在日常的生活学习中,经常会遇到各种各样的问题。面对这些问题,人们总会寻找合理的解决方法和步骤。新知讲解一、生活中的算法生活中处处都有算法,如有两瓶不同的液体(如图所示)新知讲解需要进行互换,可以采取以下方法和步骤:(1)问题分析。甲瓶和乙瓶分别装有不同的液体,现要将两种液体互换容器,可引进第三个空瓶丙来解决,如图所示。新知讲解(2)确定算法。具体的交换步骤如下:①先将甲瓶中的液体倒入丙瓶。②再将乙瓶中的液体倒入甲瓶。③最后将丙瓶中的液体倒入乙瓶。新知讲解算法就是解决问题的方法和步骤。知识链接新知讲解算法步骤1步骤1……步骤N解决问题新知讲解解决问题的过程就是实现算法的过程。新知讲解确定性有限性算法的特征一个算法的步骤序列是有限的,它应该在有限步骤之后停止,而不能是无限的算法的每一个步骤必须是明确定义的。新知讲解不唯一性顺序性算法从初始步骤开始,分为若干明确的步骤,每一个步骤只能有一个确定的后继步骤,前一步是后一步的前提,只有执行完前一步才能进行下一步,并且每一步都要准确无误,才能完成该算法。求解某一个问题的算法不一定是唯一的,对于一个问题可以有不同的算法。新知讲解很多具体问题都可以通过设计合理的算法来解决,如计算器计算要经过事先设计好的有限步骤来加以解决。普遍性新知讲解有三瓶不同的液体,如何两两交换?开动脑筋新知讲解二、计算机解决问题的一般过程使用计算机解决各种不同的问题时,首先需要对问题进行分析,确定算法再编写一组计算机能够执行的指令,即程序,让计算机按人们指定的步骤有序地工作。新知讲解若上述问题用计算机解决,大致需经过以下过程:(1)问题分析、建立数学模型。用变量X、Y、T分别表示甲瓶、乙瓶、丙瓶,用两个不同的数值(如1和2)分别表示两种液体。现在,问题转化为:要把变量X、Y中的两个数值进行交换,如图所示。新知讲解新知讲解交换变量X、Y值的步骤,用自然语言描述如下:①定义三个变量X、Y、T。②把1赋值给变量X,把2赋值给变量Y(赋初值)。③把X中的值传递给T,再把Y中的值传递给X,最后把T中的值传递给Y。(2)确定算法。④结束新知讲解选择一种计算机语言,将算法转换成程序。(3)编写程序。新知讲解运行程序,反复调试。(4)调试程序。新知讲解变量是指数据的存储单元,其中存储的数据在程序执行过程中是可变的。例如,变量X赋初值1后,在程序执行过程中再次赋值2,变量X的值就变为2。知识链接新知讲解用自然语言描述三个瓶子相互交换液体的算法。亲身体验新知讲解三、计算机语言自从1946年出现第一台电子计算机以来,计算机技术便以惊人的速度在发展。计算机语言是人与计算机之间传递信息的媒介。从计算机发明以来,计算机语言从机器语言发展到高级语言(如图所示)。汇编语言机器语言高级语言低级高级新知讲解高级语言种类很多,如C语言、Java、VisualBasic、Python等程序设计语言。新知讲解新知讲解C语言的设计目标是提供一种能以简易的方式编译、处理低级存储器、仅产生少量的机器码以及不需要任何运行环境支持便能运行的编程语言。C语言描述问题比汇编语言迅速、工作量小、可读性好、易于调试、修改和移植,而代码质量与汇编语言相当C语言一般只比汇编语言代码生成的目标程序效率低10%-20%。因此,C语言可以编写系统软件。C语言新知讲解Java可以编写桌面应用程序、Web应用程序、分布式系统和嵌入式系统应用程序等。Java语言作为静态面向对象编程语言的代表,极好地实现了面向对象理论,允许程序员以优雅的思维方式进行复杂的编程。Java具有简单性、面向对象、分布式、健壮性、安全性、平台独立与可移植性、多线程、动态性等特点。Java新知讲解VisualBasic(简称VB)是Microsoft公司开发的一种通用的基于对象的程序设计语言,为结构化的、模块化的、面向对象的、包含协助开发环境的事件驱动为机制的可视化程序设计语言VB拥有图形用户界面(GUI)和快速应用程序开发(RAD)系统,可以轻易的使用DAO、RDO、ADO连接数据库,或者轻松的创建ActiveX控件,用于高效生成类型安全和面向对象的应用程序。程序员可以轻松的使用VB提供的组件快速建立一个应用程序。VisualBasic新知讲解Python是一种计算机程序设计语言pythonPython提供了高效的高级数据结构,还能简单有效地面向对象编程。其解释器易于扩展,可以使用C或C++扩展新的功能和数据类型,也可用于可定制化软件中的扩展程序语言。新知讲解知识链接二进制二进制是计算机技术中一种被广泛采用的数制。二进制数据是用0和1两个数码来表示的数。它的基数为2,进位规则是“逢二进一”,借位规则是“借一当二”。新知讲解ASCII编码中二进制数与英文字母的对应关系随堂练习1.什么是算法?什么是变量?课堂小结总结本节课所学内容1.用没有刻度的3毫升量杯和5毫升量杯如何量出1毫升的水?请写出算法。作业布置板书设计一、生活中的算法二、计算机解决问题的一般过程三、计算机语言谢谢21世纪教育网(www.21cnjy.com)中小学教育资源网站有大把高质量资料?一线教师?一线教研员?欢迎加入21世纪教育网教师合作团队!!月薪过万不是梦!!详情请看:https://www.21cnjy.com/help/help_extract.php中小学教育资源及组卷应用平台浙教版信息技术七年级下册第13课初识数据结构教学设计课题初识数据结构单元第二单元学科信息技术年级七年级学习目标知识目标:了解数据结构的概念及种类。技能目标:理解计算机编程中数据的组织、存储和运算方法。重点数据结构的概念及种类;理解计算机编程中数据的组织、存储和运算方法。难点理解计算机编程中数据的组织、存储和运算方法。教学过程教学环节教师活动学生活动设计意图导入新课同学们是不是有这样的经历,到图书馆去借阅、归还图书,通过电脑扫描能准确的知道图书的所在位置;学校学籍管理员通过电脑可准确查询每个学生的学籍信息。面对海量的数据,计算机是什么形式存贮的呢?这节课我们就一块来学习数据结构。思考激发学生学习兴趣并快速进入学习状态讲授新课利用计算机程序解决问题时,与问题有关的数据往往不仅数量庞大,而且存在着错综复杂的关系。为了使计算机更加高效地处理数据,需要对数据进行有效的组织和管理,并以一定的形式加以存储和表示。一、数据结构的概念数据结构是计算机学科特有的概念,指数据之间的相互关系,即数据的组织形式。合理的数据组织方式有利于提高解决问题的效率如图书馆对书的存放与管理,根据图书分类法对图书进行分区、分类存放(如图所示)并建立索引目录,从而提供快速借阅的服务。计算机为了快速而高效地处理数据,也需要根据问题解决的特点对数据进行有效的组织与管理。如音频播放器用“排队”方式组织播放列表中的歌曲,可以让先加入播放列表的歌曲先播放。计算机操作系统采用多级树型目录结构对文件进行组织与管理(如图所示)可以实现文件的分类存放和高效检索。开动脑筋在日常生活中还有哪些常见的数据组织管理形式?亲身体验在本班同学通讯录中,试着利用数据之间的关系设计出能快速找到家长电话号码的方法。二、常见的数据结构在算法和程序设计中,需要结合数据和数据处理的特点,运用合适的数据结构组织数据、存储数据,才能高效地完成对数据的处理。常见的数据结构有数组、栈、队列等。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.什么是数据结构?板书一、数据结构的概念二、常见的数据结构21世纪教育网www.21cnjy.com精品试卷·第2页(共2页)HYPERLINK"http://www.21cnjy.com/"21世纪教育网(www.21cnjy.com) 展开更多...... 收起↑ 资源列表 第13课 初识数据结构.doc 第13课 初识数据结构.pptx