《初识数据结构》教学建议

    刘丽颖 张博

    

    

    

    在深入认识数据内涵和价值的基础上认识数据结构，是为基本数据结构的学习奠定基础，也是从数据到数据结构的过渡。建议教师精选典型的精巧案例，由浅入深，将数据进行结构化，体现不同结构数据的不同含义，让学生充分理解数据结构是以数据为基础的集合，集合中的数据存在某种特定关系，这种关系就称之为集合中的数据的结构。

    厘清概念，梳理结构

    1.《初识数据结构》概念图（如下页图1）

    2.概念辨析

    （1）数据结构与数据类型

    ①数据结构是相互之间存在的一种或多种特定关系的数据元素的集合。概念讲解中强调“数据结构”一般通过“数据对象”和“数据关系”两个维度进行定义，因此，即使“数据对象”相同，但数据对象之间的“数据关系”不同，它们也是不同的数据结构。尝试让学生举一反三体会相同数据对象、不同数据关系对应不同数据结构（参考教材相应例子），让学生认识到数据结构可以根据自己的需求进行合理构造。构造数据结构是解决问题的重要方法，要从待解决的问题中抽象出数据对象，继而合理定义数据对象之间的特定关系，就可以定义属于自己的数据结构了。

    ②数据类型是一组相同的值的集合以及定义在这个集合上的一组操作的总称。概念讲解时可以从学生既有经验入手，如今的高中生在小学和初中阶段都接触过程序设计，无论哪种语言在使用时对数据类型的理解都是相通的。简言之，数据类型学生早就接触过、使用过，现在是从理论的角度重新认识数据类型。数据类型讲解强调取值范围和对应操作，练习时可以直接将所用版本教科书中的语言作为练习对象，进一步熟悉该语言数据类型，以便为后续学习打下基础。

    在理解数据结构和数据类型的基础上理解抽象数据类型的概念，一般由数据对象、数据对象上的关系以及对数据对象的一组基本操作三个要素来定义。一般的计算机语言中已经为用户提供了部分数据类型，如数值型、字符型、逻辑型等，当这些基础类型不能满足解决问题的需求时，就要以抽象数据类型三要素为依据构造自己需要的数据类型，以便于计算机处理，有效解决问题。

    （2）逻辑结构和物理结构

    ①逻辑结构是指结构定义中的“关系”，描述的是数据元素之间的逻辑关系，通常分为线性结构（线性表、栈、队列、串）和非线性结构（图、树）。

    讲解时可以用数据元素之间一对一、一对多、多对多的关系帮助学生理解逻辑结构，线性结构对应一对一的关系，非线性结构对应一对多或多对多的关系。

    ②物理结构（存储结构）是数据的逻辑结构在计算机中的表示。通常可以分为顺序存储和链式存储两种。

    在讲解数据在计算中的存储时，建议结合存储单元将常见数据类型的存储进行讲解，明确不同的数据类型在计算中占据不同字节的存储空间，有利于学生应对存储空间的计算题目和更好地理解顺序存储与链式存储这两种存储结构的区别和优缺点。强调逻辑关系相邻的数据在物理存储上也相邻就是顺序存储，需要较大的连续的存储空间;逻辑上相邻物理上不相邻的存储就是链接存储，可以有效利用零散的内存空间，但是由于需要记录链接信息，可以引入指针来实现，则每个数据元素比顺序存储时需要更多的存储空间存放数据元素本身和指针信息。

    （3）数组和链表

    ①数组是一组具有相同数据类型的数据元素的集合，占用一段连续的存储空间，常用来实现数据的顺序存储。数组的定义和操作需要精讲，可以结合所用的语言设计多个小程序，让学生体会数组的初始化、赋值、查找元素、插入/删除元素等操作，为后续学习打下坚实的基础。

    ②链表是指多个结点（由数据域和指针域组成）链接成的序列。链表的特点是可以通过指针将内存中不连续的存储空间有效利用，因此指针中存放的是链表中下一个结点的地址，是链接存储方式的索引。授课时要从“原理→示意图→语句表达”三个阶段进行教学，夯实每一个阶段的学习要求，从原理上明确链式存储的优缺点，通过会画示意图检验学生是否掌握基本操作（定义、初始化、查找、插入、删除等）时数据域和指针域的变化，最后再用程序实现简单操作。

    顺序存储可通过数组实现，链式存储可通过链表实现，建议教师可以引导学生利用思维导图等工具将数组、链表、存储方式等知识进行总结归纳，以此作为项目学习的一个重要考核内容。

    学科核心素养要求

    ①结合生活实际，理解数据结构的概念，认识数据结构在解决问题过程中的重要作用。（信息意识）

    ②理解抽象数据类型的概念，能够对特定生活情境中的关系进行抽象，认识抽象数据类型对数据处理的重要性。（信息意识）

    ③通过案例分析，理解数组、链表等基本数据结构的概念，并能编程实现其相关操作。（计算思维）

    ④比较数组、链表的区别，明确上述两种数据结构在存储不同类型数据时的应用，能根据不同的应用场景选择合适的存储方式。（数字化学习与创新）

    上述核心素養只是重点提炼，教师可以根据具体情况具体分析，在学科教学中充分落实学科核心素养，举例时必须采用更多生活中的具象问题与抽象的数据结构建立联系，才能将抽象内容具象化，帮助学生理解数据结构的重要作用，从学科核心素养的培养上升到学生数字素养的养成。

    项目学习举例

    1.项目活动设计思路

    每个图书馆都有自己独特的管理系统，每天都要处理若干条图书信息，实现对图书的查询、借阅和更新等操作。以学校读书月活动的开展为契机，高二年级各班都储备了大量书籍，结合本章主题学习项目，以班为单位开展本次项目活动设计，各班针对不同的特点选择适合的数据结构进行书目管理，在读书月闭幕阶段进行年级展示。

    2.主题学习项目：我的图书馆

    （1）项目目标

    学生通过亲自参与项目活动，体验实现图书管理的各个过程，感受不同的存储结构对图书管理呈现不同的操作结果。研究图书管理程序各项功能的基本操作，形成自己的理解并进行深入学习，最终实现比较完善的图书管理程序。

    （2）项目准备

    ①分组：每班按照不同的存储方式进行分组，3～5人一组，明确分工，制订项目规划。

    ②分配任务，确定主题，学习数据结构的基本概念。

    ③复习Python的基础知识。

    ④运用不同的数据结构存储方式实现图书管理程序，并测试程序功能，减少运行错误。

    （3）项目过程

    ①小组讨论并制订项目规划目标、实施方法，用思维导图记录规划结果。

    项目主题：我的图书馆。

    实施方法：整理本班书目，包括书籍名称、分类、册数、捐赠者姓名等，结合本组特点，运用一种存储方式进行管理，在计算机上形成程序运行。

    成员分工：小组成员共计5人，分别为A、B、C、D、E。A为组长。第一周B负责整理数据对象，小组成员学习数据结构基本概念。第二周C、D负责运用Python实现图书管理存储程序。第三周E负责测试程序功能，减少运行错误，全体完成项目报告撰写。

    预期成果：在第三周能够实现图书管理存储程序的基本功能操作。

    ②学习数据结构的基本概念。通过教师准备的微课进行学习。

    小组成员根据整理出来的书目（如上页表1），按照逻辑结构进行绘制。通常将逻辑结构分为四种，即集合结构、线性结构、树形结构和图状结构。以下逻辑结构图均以“序号”来标识每一本书的基本信息。

    所有书籍同属于班级整体书目，所有书籍构成一个集合，数据元素之间并无其他关系，成为集合结构，如图2所示。

    将表1中书籍按照序号顺序排列，数据元素之间为一对一的关系，构成一个线性结构，如图3所示。

    书籍之间的分类也是分层的，有文艺和人文社科两个大类，树形结构中，没有父节点的数据元素称作根节点，没有子节点的数据元素称作叶节点，构成树形结构，如图4所示。

    每位学生都可以阅读自己和别人的书籍，相互之间的关系为多对多，彼此之间可以形成一个图状结构，如图5所示。

    在对数据结构有了基本的了解之后，小组成员继续根据本组特点，分别对表1进行了顺序存储和链式存储示意图的绘制，如下页表2及下页图6所示。

    ③结合教材实例，用Python语言实现图书管理存储程序，完成不同存储方式的基本操作，如增加、删除等，突破教学难点。

    以顺序存储为例，先初始化一个具有6个元素一维数组a，并将书籍名称存入数组a中。主要程序如下页图7所示。

    除此之外，还可以在顺序结构中进行增加书籍名称和删除书籍名称的操作，但是需要挪动部分数组中的元素，存在一定的不便之处。

    小组若以链式存储为例，将书籍名称存到链表当中，首先对链表进行初始化。主要程序如下页图8所示。

    同理，在链表中也可以实现对数据元素的插入、删除、查找，甚至整个链表的长度也可以计算，并且不影响其他元素的位置，但是每次查找操作都要从头开始。

    通过两种不同的存储方式，展示了对书目的不同操作要求，也意味着在这个过程中不同小组成员之间可以通过沟通进一步区别顺序存储和链式存储的不同点，以及各自的特点，以便在今后的项目活动中选择更加合适的存储方式来解决问题。

    ④梳理并总结程序实现过程，撰写项目报告。在对程序功能进行调试、减少错误率之后，全组成员集体根据整个项目活动的参与过程，按照项目报告的书写规范，及时进行总结，并参考相关辅助资料。

    设想：通过改进程序，今后不仅可以在程序中增加或删除书目，还可以实现图书与师生的借阅功能，并形成相应记录。待系统更完善，可以和学校的图书馆联合制订相应的图书管理制度，实现班级、年级乃至学校图书馆图书信息的整体操作运行。

    （4）项目总结

    以“我的图书馆”为项目主题，在高二年级展开以班级为单位的图书管理存储程序的设计活动。通过充分的项目活动准备，小组成员与教师密切配合，在项目实施过程中认真学习相关知识体系，从认识数据结构与数据类型到数组与链表的基本概念和操作，根据已有基础，完成Python程序设计，实现相应存储功能，最终完成既定的项目目标。

    （5）学生成果展示，项目活动评价与学生自主学习评价

    项目活动评价表3及学生自主学习评价设计略。

    教学评价建议

    本模块是选择性必修模块，本单元又是概念性比较突出的一个单元，教学评价一定要和教師的教学方式有效结合才能起到评价的助力作用，帮助学生及时纠正学习中的问题，提高学习效率，增强学习兴趣和自信心，使评价成为教师与学生沟通的有效途径。

    建议评价可以通过课堂参与、课后关注、项目贡献三个维度进行，采用等级制用自评、组间评价、教师评价综合完成。

    ①课堂参与可以利用相关软件统计学生的参与度以及提交课堂作业的次数和准确率进行合理采样，通过数据分析支持评价。

    ②课后关注则要成立相关学习交流群，教师定期发送数据结构相关知识让学生学习反馈、讨论交流，统计反馈情况和学生互动情况;学生个体、学习小组也可以在群内提供学习资源，发表学习心得，教师根据学生表现进行评价。

    ③项目贡献是教师根据学生以小组为单位提交的项目学习成果进行评价，通过项目分工及成果反馈评定学生在该项目中的贡献度，这样可以有效避免组内个别学生学习过程不积极、全靠其他成员支撑的问题，客观评价学生的付出，把评价落到实处。