搜索
哈尔滨金融学院教案课程名称：＿＿数据结构＿＿＿教师姓名：＿＿李俭＿_____＿所在系部：计算机系系统教研室_编制时间：＿＿2012年9月____教学课程的基本信息教学单位计算机系授课单位系统教研室主讲教师李俭职称副教授专业信息管理年级2011班级1、2学生人数70基本教材数据结构（C语言描述）主要参考书数据结构习题与实训教程（C语言描述）周学时4总学时68理论教学学时50实验教学学时18授课时间周一5、6；周五3、4授课地点X209；S712备注线性表第一次课章节题目第2章线性表教学目标掌握线性表的逻辑定义；熟悉线性表的基本操作种类；了解一些较为复杂的线性表基本操作；掌握线性表的顺序存储结构的特点。重点、难点重点：线性表的定义及顺序存储结构的实现；难点：使用C语言描述顺序表；强调：数据元素从下标为0的数组元素开始存放。授课内容时间安排复习数据结构的定义、基本概念（约5分钟）2．1线性表的逻辑结构2.1.1线性表的引例（约15分钟）座位、单行路上的汽车、糖葫芦等。2.1.2线性表的定义（约15分钟）一个线性表是由零个或多个具有相同类型的数据元素组成的一个有序集合。通常把线性表记作：L：（a1，a2，a3，…，ai，…，an）称n为线性表的表长;n=0时的线性表为空表。举例说明：易：手机号码簿难：学生基本信息表2.1.3线性表的基本操作（约10分钟）表的初始化、求表长、取表中的结点、查找结点、插入结点和删除结点等。书上总结了8种，可以再加以扩充到10种以上（两个线性表的并集、线性表的输出、线性表的逆置、两个线性表的交集等）。重申数据结构的定义及内容启发学生自己寻找实际生活中线性表的例子。通过先易后难、先简单后复杂的结构加以说明。让学生成为用户，进行分析，如果你要用一个线性表，你希望系统提供给你什么操作？注意每个操作的已知条件，它将作为该函数的形参。2．2线性表的顺序存储结构2.2.1顺序表结构（约15分钟）线性表的顺序表示：指的是用一组地址连续的存储单元依次存储线性表的数据元素。用物理位置来表示逻辑结构。LOC(ai+1)=LOC(ai)+lLOC(ai)=LOC(a1)+(i-1)*l注意数据元素在顺序表中的位置和数据下标差1。用C语言建立顺序表（约20分钟）方法一：程序中即确定顺序表长度方法二：让用户输入顺序表长度方法三：让用户直接输入数据元素，以特殊输入作为顺序表数据元素输入结束的标志。顺序表的输出（约10分钟）注意数据元素和数组下标的引用。注意复习一下数组的相关重要知识。注意灵活建立（尽量不要在程序当中就确定顺序表的长度）。可以在主函数中实现，也可以通过功能函数实现。教学方法辅助手段多媒体、黑板讲授、启发、分析，通过实例让学生自己总结线性表的特点。小结、作业线性表的逻辑结构及顺序存储结构作业：编写C程序创建一个顺序表并输出；复习对数组的操作。教学反思线性表第二次课章节题目第2章线性表教学目标掌握线性表的顺序存储结构；熟练掌握顺序表基本操作中的关键语句；重点、难点重点：顺序表的插入、删除、取元素、定位操作；如何通过一个完整的程序实现具体操作；如何引用顺序表中的相关内容。难点：通过函数对顺序表进行操作时使用的形参应为指针类型的；顺序表的插入、删除操作（需要移动数据元素）；如何通过函数调用完成对顺序表的相关操作（编写一个完整的程序）授课内容时间安排复习线性表的定义、顺序表的特点。（约5分钟）2.2.2顺序表的基本操作1．初始化操作（约5分钟）注意顺序表中数据元素和表长的引用方法。2．求表长度操作（约5分钟）注意len和MAXSIZE的区别。3．定位操作（约10分钟）注意算法的健壮性，正确操作和越界操作的情况都要涉及到。4．取元素操作（约10分钟）注意学会函数的形参如何设置。前四个基本操作总结（约10分钟）例：建立一个顺序表，实现顺序表的初始化、求表长、取元素及定位操作。（相关操作需要的数据由用户通过键盘提供）5．插入操作（约20分钟）注意：插入操作导致线性表逻辑结构的变化保证插入操作能够正确进行的前提移动数据元素时的注意事项函数形参必须要用顺序表指针6．删除操作（约15分钟）注意：删除操作导致线性表逻辑结构的变化保证删除操作能够正确进行的前提移动数据元素时的注意事项函数形参必须要用顺序表指针插入和删除操作总结（约10分钟）重点讲明白为什么在函数的形参中用的是顺序表指针，什么时候可以不用（顺序表内容没有改变时），什么时候必须用（顺序表内容发生改变）！通过一个程序将1~4的基本操作和顺序表的建立、输出整合成一个程序进行整体讲解。移动数据元素时通过最先操作和最后操作，讲解如何编写循环实现数据元素移动的技巧。通过一个程序将插入和删除操作以及顺序表的建立、输出整合成一个程序进行整体讲解。讨论：其他的实现方法教学方法讲授、启发、分析、讨论辅助手段多媒体、黑板小结、作业如何利用所学基本操作来实现对顺序表的一系列操作作业：习题与实训中的和顺序表有关的典型题例2.1、2.2教学反思线性表第三次课章节题目第2章线性表教学目标掌握线性表的顺序存储结构；熟练掌握顺序表基本操作中的关键语句；掌握顺序表的应用；重点、难点重点：如何通过一个完整的程序实现具体操作；如何引用顺序表中的相关内容。针对要进行的操作如何进行分析难点：对有序的顺序表和一个以上的顺序表进行操作时需要注意的问题授课内容时间安排复习顺序表中插入操作和删除操作的主要注意事项（约5分钟）2.2.2顺序表的基本操作7．判断表空操作（约5分钟）8．表置空操作（约5分钟）说明置空操作与初始化操作的实现方法一样，但是从用户角度说，这是两个操作。总结顺序表的基本操作（约5分钟）顺序表的应用例1：顺序表中数据元素的逆置（约25分钟）引导学生思考：解决问题的方法是什么？思路：将第一个数据元素和最后一个数据元素交换，第2个数据元素和倒数第2个数据元素交换，以此类推，交换到中间为止。不能用一个顺序表作辅助空间，否则将导致空间复杂度太高。重点说明数据元素移动方法的不同各个基本操作之间在需要的情况下可以互相调用。每种方法分别通过画图和多媒体加以说明。分别讲解解决问题的两种方法例2：顺序表中元素值非递减有序排列，写一算法删除表中值相同的多余元素。（约15分钟）思路：因为已有序，所以前后相邻的数据元素依次比较即可。注意：若存在两个以上的值相同的数据元素，算法是否能保证结果正确。例3：已知两个顺序表LA和LB，同一表中无重复元素，现求两个顺序表的合集，结果放在LA表中。（约15分钟）思路：将LB表中的每一个元素作为给定值在LA表中查找，若给定值在LA表中存在，则不作任何操作，否则将此元素追加到LA表中。例4：已知两个顺序表LA和LB，同一表中无重复元素，现求两个顺序表的交集，结果放在LA表中。（约10分钟）思路：将LA表中的每一个元素作为给定值在LB表中查找，若给定值在LB表中存在，则该元素保留在LA表中，否则将此元素删除。总结：无论实现什么操作，都离不开顺序表的基本操作的影子，最常见的就是插入和删除，只不过是具体问题具体分析，思路找准，大致的解决方法类似。如何建立有序顺序表：（1）用户输入时即按有序输入；（2）用户输入时无序，分别插入时保证有序。主函数中需要实现两个顺序表的建立，最后将存放结果的顺序表输出。教学方法辅助手段辩论：如果程序中不存在你所调用的函数，会出现什么情况？如何才能保证程序正确运行？研究：利用顺序表的特点，如何逆置顺序表中的数据元素？可以采用哪种方法？还有没有其他方法？小结、作业小结：如何利用所学基本操作来实现对顺序表的一系列操作作业：（1）已知有序顺序表，插入一数据元素，使表仍有序。（2）习题与实训中的和顺序表有关的典型题例2.3、2.4教学反思