教科版必修1 数据与计算第3单元 认识数据3.2 数据与结构获奖第2课时2课时教案

第三单元　认识数据

3.2 数据与结构 (第2课时)

通过活动1，了解快递派送线路，领会可将快递运送线路抽象为“树”的结构，“透过现象看本质”。通过活动2，了解物流网络，领会将物流网络抽象为“图”结构，认识|“多对多”的关系。

★     通过了解快递派送线路和物流网络，理解“树”结构和“图”结构，为利用数据、实现数据的价值做准备。

1．  重点：数据结构中的树结构和图结构

2．  难点：数据结构中的树结构和图结构

教师准备：打开微机，课件、投影仪等。

学生准备：结合课本提前预习。

【导入新课】

学生预习，阅读教材第59页和第6页任务二“探究快递配送过程”的活动1了解快递派送线路，完成第60页的连点成树。

【教师活动1：树结构】

树的递归定义如下。

树是由n（n>=0）个节点组成的有限集合。若n=0,则称为空树。任何一个非空树均满足以下二个条件:

 (1)仅有一个根节点。

（2）当n>0时，其余节点可分为m(m>=0)个互不相交的有限集合，其中每个集合又是一棵树，并称为根的子树。

【了解物流网络】

请同学们阅读教材第61页至62页，完成图3.2.6的连线。

【图结构】

图结构是由一组节点（称为顶点）和一组节点间的连线（称为边或弧），构成的一种数据结构。

图结构中的每个顶点都可以与其他顶点有边相连，数据元素之间是多对多的关系。

【规划取快递最快路线】 

                       1

【数据结构】

数据结构：存在特定关系的数据元素的组合体

数据结构按逻辑结构分类：  集合结构、线性结构、树结构、图结构

队列的计算机实现：

在Python中，队列一般用列表(list)实现，常用操作：

q=[]          #定义空列表q

q.append(x)   #元素x入队

q.pop(0)      #返回队首元素,队首元素出队(删除)
len(q)        #返回队列q的长度(元素个数)

q[i]          #返回列表q中索引(index)为i的元素. 索引有2套编号方式：
              正编号(从左到右编号依次为0,1,2,…)和负编号(从右到左编
              号依次为-1,-2,-3,…)

【课堂小结】

1.队列是一种线性数据结构，本质特征是FIFO

2.队列在Python中，用列表实现

    队列的创建；

    队列的基本操作：入队，出队，求队长，判队空

3、树结构和图结构是两种比较难的数据结构，我们应领会其本质特征，
   会用树结构和图结构对工作、学习、生活中的具体问题进行抽象和分析，
   解决一些简单问题。

【巩固练习：数据结构的比较】

End