数据结构A教学实施方案(参考)

1201~201学年第学期《数据结构A》课程教学实施方案（计算机科学与技术、软件工程专业教学班号：001）任课教师：乐晓波一、课程概况【课程名称】数据结构A。【课程性质】本课程属于计算机科学与技术、软件专业的专业基础课，必修课。【教学对象】计算机软件工程专业（14-1、2班），教学班号：001。【教学总学时】56学时。其中：理论教学40学时，实验：16学时。【学分】3.5学分。【先修课程】C语言程序设计（或C++语言程序设计）。【后修课程】操作系统、编译原理、程序设计方法。二、教学地位与作用及主要教学目的数据结构是计算机软件专业的一门重要的专业理论基础课，它不2仅是计算机科学的核心课程，而且也是其他理工专业的热门选修课程。数据结构课程是操作系统、编译原理、程序设计方法、人工智能原理等后续课程的重要基础课程，同时，其所涉及的内容也是程序设计技术的必备知识。通过学习该课程使学生学会分析和研究计算机进行数据加工的数据结构特性，掌握算法的复杂度分析技术，并初步具有对实际应用问题的认识和分析能力，对于实际应用问题能选择适当的数据结构和存储结构以及相应的算法编制出高效率的程序，同时为后续专业课程打下基础。数据结构课程的主要内容包括：算法分析、线性表及其应用、栈和队列、串及其应用、数组和广义表、树和二叉树及其应用、图的表示及其应用、查找方法及其分析、排序算法及其分析技术等。三、课程选用教材【使用教材】1．教材：陈倩怡等编著.《数据结构》（C语言版）.武昌:华中科技大学出版社,2013年1月出版。2．教材选用依据：该教材在总结我校计算机类二十多年教学的实践经验，兼顾本学科的广度与深度的基础上，集我校计算机与通信工程学院计算机科学与技术教研室全体教师的集体智慧而编写出来的一本适合我校计算机类本科学生的实用教材。该教材概念表述严谨，逻辑推理严密，语言精练，是计算机类一本极好的教科书。3【参考教材】1.王红梅．数据结构（C++版）[M]．北京：清华大学出版社，2007年7月出版。2.李根强主编.《数据结构》（C++版）[M].北京:中国水利电力出版社,2005年1月出版3.朱战立编著．《数据结构》（C++语言描述）[M].北京:高等教育出版社,2004年２月出版4.教材：严蔚敏，吴伟民编著.《数据结构》（C语言版）.北京:清华大学出版社,2010年3月修订版。在讲授过程中，考虑到该课程理论性逻辑性强、难度大等特点，任课教师应采取深入浅出的原则，对每个教学内容结合实际应用问题以更加生动的方式讲述该课程的全部内容。对概念、原理的解释和描述应尽可能地以日常生活所接触到的实际例子和图示加以对比说明（如线性表的应用、图的遍历的应用、最短路径和关键路径的应用等），引导学生逐步理解概念与原理之间、原理与应用之间的联系。四、本课程的特点及教学手段和方法1．课程特点：《数据结构》以严谨的数学和C或C++语言为基础，既有抽象的数据类型的定义，又有严格的C语言类型定义和算法描述，既有直观的图形表示，又有丰富的系统描述手段和算法的分析技术，为计算机4科学及计算机的应用提供坚实的理论基础和应用分析工具，是一门集理论和实践为一体的综合性课程。其特点是基础理论性强，既有逻辑思维、抽象思维的训练，又有联系实际的物理形象思维的锻炼，且所涉及的应用面较广。2．课程重点和难点：重点：线性表、栈和队列、树与二叉树、图、查找、内部排序。难点：结构体数据类型的应用、指针数据类型的应用、数组、线索化二叉树、算法的递归与非递归实现。3．教学方法与手段：讲授时要遵循由浅入深的原则，对易混淆的概念加以详细说明，对每章的重点及各类不同类型的数据结构要作详细的分类介绍，并着重培养学生对实际应用问题进行形式化描述及构造算法的能力以及在此基础上进行算法分析的能力。为帮助学生理解较抽象的内容，力争在较少的学时数中讲授体系完整的教学内容，拟采用我室自制的完全符合教学大纲的电子教学课件。同时，利用“学宝”教学教学软件采用云环境下新的教学模式，推进教学方法的改革，使教学达到事半功倍的效果。五、教学进度该课程教学总学时为56（含实验16学时）学时，3.5学分。教学安排按照一学期14周进行，平均每周4学时。其中实验共安排8次，每次2学时，共16学时。具体教学进度安排详见表1所示。5表1教学进度计划表教学内容总学时其中课外辅导/课外实践备注课堂上机实验绪论222线性表8626栈4222队列4222串4222数组与广义表444树与二叉树8626图8828查找8626内部排序4222总计56401640六、教学内容重点与难点及解决办法1．绪论（讲授：2学时）教学重点：（1）数据结构、逻辑结构、物理结构、数据类型、抽象数据类型、算法、算法的时间复杂度和空间复杂度及其计算。（2）算法的五要素、算法的书写规范。教学难点：抽象数据类型。解决办法：通过联系实际，举例说明抽象数据类型的内涵，如：复数的抽象性及其在C或C++中的描述与实现。2．线性表（讲授：6学时）教学重点：（1）线性表的逻辑定义机器各种存储结构的描述方法。6（2）线性表基于各种存储结构之上的基本操作的实现方法。（3）利用线性表表示一元多项式并实现多项式的相关运算。教学难点：线性表的链式存储结构的实现。解决办法：利用电子课件详细、动态地讲解链式结构的物理形式，并通过第一次实验上机练习加深对该存储结构的理解。3．栈和队列（讲授：4学时）教学重点：（1）栈和队列的逻辑结构。（2）栈和队列的基本操作在静态存储结构和动态存储结构上的实现方法。（3）栈和队列在程序设计中的应用（如表达式的求值、递归程序设计）。教学难点：栈的链式存储结构的实现；队列的顺序存储结构（循环队列）的实现。解决办法：①首先结合实际例子帮助学生充分理解逻辑栈的特点，如：手枪的子弹夹等。然后利用对线性表的链式存储结构的理解进一步加深学生理解链式存储结构下的栈的实现方法。配合安排相应的验证性实验以加深理解。②首先结合实际例子帮助学生充分理解逻辑队列的特点，如：装羽毛球的圆筒盒子等。然后在利用电子课件形象地描述物理结构的实现。配合安排相应的验证性实验上机一次以加深理解。74．串（讲授：2学时）教学重点：（1）串的逻辑结构及其三种存储结构。（2）串的基本操作在静态存储结构和堆结构下的实现方法。教学难点：串的模式匹配算法的理解与实现。解决办法：先利用比较简单的串的顺序存储结构来讨论最简单的模式匹配算法的原理及其实现，然后再由浅入深地讨论其他效率较高的算法。可以要求一般同学仅掌握基本算法。利用课余时间组织学生讨论改进算法。5．数组与广义表（讲授：4学时）教学重点：（1）数组的逻辑结构及存储结构。（2）特殊矩阵和稀疏矩阵的压缩存储及其矩阵运算的实现。（3）广义表的逻辑结构及其存储结构。教学难点：特殊矩阵和稀疏矩阵的压缩存储的理解与实现。解决办法：制作直观而形象的电子课件，利用动画效果讲解物理存储结构的原理，然后在用C或C++语言进行物理结构的描述。6．树和二叉树（讲授：6学时）教学重点：（1）树的逻辑结构与基本操作。（2）二叉树的定义、性质与存储结构。8（3）遍历二叉树与线索二叉树。（4）树的存储结构与树的遍历。（5）哈夫曼树及其应用。教学难点：三种不同的遍历二叉树的递归和非递归算法。解决办法：重点讲述一种（如中序遍历）算法的递归算法思想和非递归算法思想，并引导学生编写相应程序。然后举一反三地讲解其他两种遍历算法。配合安排验证性实验上机一次。7．图（讲授：8学时）教学重点：（1）图的定义与存储结构。（2）图的两种遍历策略。（3）无向图的边通分量及最小生成树。（4）拓扑排序与关键路径。（5）求网络中的最短路径。教学难点：图的定义与存储结构；图的两种遍历策略。解决办法：先重点讲述图的顺序（数组）存储方法的实现思想，然后再讲述图的邻接表法的存储方法；精讲深度优先遍历算法思想及其实现方法；课后组织学生讨论广度优先遍历算法，并引导学生编写相应程序，利用课余时间上机实现之。8．查找（讲授：6学时）教学重点：9（1）顺序查找。（2）折半查找。（3）索引查找。（4）二叉排序树和二叉平衡树的查找方法。（5）哈希表的建立及其查找方法。（6）各种查找方法的查找效率的分析。教学难点：哈希表的建立及其查找方法。解决办法：结合实际例子先讲述哈希表的存储结构及其冲突的一般解决方法。然后再展开更深入的解决冲突问题的常用算法。9．内部排序（讲授：2学时）教学重点：（1）插入排序。（2）快速排序。（3）选择排序。（4）归并排序。（5）各种排序算法的时间复杂度分析与比较。教学难点：各种排序算法的时间复杂度分析与比较。解决办法：以两个较简单的排序算法为例（如：插入排序和选择排序）说明排序算法效率分析及其比较的一般方法。并配合安排设计性实验一次。要求学生能根据一批数据建立几种不同的数据结构，采用不同的搜索或排序算法对这些数据进行查找或排序，并对其进行分析与比较。10七、实验教学实验教学共16学时，实验内容及学时分配安排详见表2所示。表2实验教学安排表序号实验项目名称实验类型学时分配必开/选开分组要求1线性表设计性实验2H必开1人/组2栈设计性实验2H必开1人/组3队列设计性实验2H必开1人/组4串验证性实验2H必开1人/组5二叉树设计性实验2H必开1人/组6图验证性实验2H必开1人/组7查找验证性实验2H必开1人/组8排序验证性实验2H必开1人/组具体实验内容与要求详见《201-201第学期计算机软件工程专业数据结构A教学日历》。八、教学辅导、作业、考试关于教学辅导：每周安排一次课外答疑，答疑地点与时间另行通知。关于作业：作业分两部分。第一部分主要是在每次上实验课的时候根据具体的实验内容对学生进行考核，学生以上机实验报告的形式提交《上机实验报告》；第二部分主要是针对每次理论课授课的内容在课堂上布置的作业，教师每次授课时将利用课堂的最后5分钟针对本次授课内容布置作业，学生在课后利用课余时间完成作业。11关于考试：本课程属考试课程。考试方式采取闭卷笔试的形式，其考试成绩占学期总成绩的80%；平时成绩（作业与上机）占学期总成绩的20%。九、作业的提交与教学意见反馈1．学生可登陆学校数字化教学平台进入数据结构的网络教学界面后下载教学课件与教学大纲、观看教学视频内容、提交作业、询问疑难问题、查询教学通知、在线水平测试等。2．学生还可通过“学宝”下载教学资源，与老师进行互动，提交作业、提交实验报告等。3．学生还可以直接将教学反馈意见以电子邮件的形式发到任课教师的私人邮箱中：4.学生还可通过手机或QQ与任课教师联系：任课教师QQ号：任课教师手机号：二零一年月日制定