初中信息技术浙教版 (2020)七年级下册第13课 初识数据结构课文内容ppt课件

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