数据结构与算法教案.doc

软件技术系 课程名称：数据结构和算法 文件编号：SJ1K-001 版本号:1.0 二一年四月六日 教案2009年2010学年第二学期课程名称数据结构和算法任课教师 杨勇 授课对象系 别软件技术系本次课学时2学时年级班次章节题目第一章 数据结构和算法概述目的要求(含技能要求)了解数据结构的相关概念和掌握、 算法的基本概念和性质、算法的性能分析和评价本节重点数据结构基本概念、算法基本概念、算法特性以及算法分析本节难点算法的时间复杂度分析教学方法讲解+案例教学教学用具多媒体教室、机房问题引入从学生所了解的生活常识，引出数据结构的不同类型。如从学生信息检索系统数据库中，学生信息表引出线性结构；人机对弈引出树形结构；教学计划安排问题引出图形结构。难点与重点讲解方法采用讲解+案例教学，讲述数据结构的基本概念以及相关的术语，算法的含义特征以及算法的分析评价方法。本次课小节课程小节1、数据结构定义、相关术语2、算法的定义、要素、性质3、算法及其复杂度分析教后札记1、什么是数据结构2、什么是算法3、算法复杂度评定方法讨论、思考题、作业(含实训作业)见后：第一章 数据结构和算法概述【学习目标】 能力目标：（1）初步掌握数据结构和算法的基本概念和应用能力（2）算法时间复杂度分析的能力2知识目标：（1）数据结构的概念和用语；（2）算法的定义，算法性质、地位和特征；（3）算法分析与评价；3职业素质目标： 算法时间复杂度分析逻辑思维能力 算法时间复杂度独立思考应用能力【课前准备】 环境要求：PC电脑Visual Studio 2005 、SQL Server 2000、MyEclipse 学生要求：具备SQL Server 数据库理论知识和操作能力。具备面向对象程序设计C/S结构开发能力 教师要求：能够进行三层结构的C/S项目开发能力。能够正确分析算法时间复杂度的能力。具备一定的数据库设计和分析能力。能够正确、及时处理学生操作过程中出现的问题及错误。【主要内容】1了解数据结构的相关概念和术语数据：计算机操作对象的总称，它是计算机处理的符号的集合，集合中的个体为一个数据元素。数据结构：是由若干特性相同的数据元素构成的集合，且在集合上存在一种或多种关系。由关系不同可将数据结构分为四类：线性结构、树形结构、图状结构和集合结构。逻辑结构：数据元素和数据元素之间的逻辑关系称为数据的逻辑结构。存储结构：数据在计算机中的存储表示称为数据的存储结构。数据处理：数据处理是指对数据进行查找、插入、删除、合并、排序、统计以及简单计算等的操作过程。数据类型：数据类型是指程序设计语言中各变量可取的数据种类。数据类型是高级程序设计语言中的一个基本概念，它和数据结构的概念密切相关。2了解算法的概念、性质、地位和特性算法：进行程序设计的另一不可缺少的要素。算法是对问题求解的一种描述，是为解决一个或一类问题给出的一种确定规则的描述。一个完整的算法应该具有下列五个要素：有穷性、确定性、可行性、有输入和有输出。一个正确的算法应对苛刻且带有刁难性的输入数据也能得出正确的结果，并且对不正确的输入也能作出正确的反映。3能够对简单的算法进行时间复杂度的分析。评价一个算法的好坏，通常用时间复杂度和空间复杂度进行评价。算法的时间复杂度：比较不同算法效率的一种准则，算法时间复杂度的估算基于算法中基本操作的重复执行次数，或处于最深层循环内的语句的频度。算法的时间复杂度：比较不同算法效率的一种准则，算法时间复杂度的估算基于算法中基本操作的重复执行次数，或处于最深层循环内的语句的频度。算法空间复杂度：可作为算法所需存储量的一种量度，它主要取决于算法的输入量和辅助变量所占空间，若算法的输入仅取决于问题本身而和算法无关，则算法空间复杂度的估算只需考察算法中所用辅助变量所占空间，若算法的空间复杂度为常量级，则称该算法为原地工作的算法。【学习方法】自主学习、教师讲解、课后习题练习【教学方法】 多媒体教学讲解+案例教学【教学实施】1. 本门课程的总体安排和学习的要求：（10分钟）2. 数据结构的概念和术语的讲解：（20分钟）3. 算法的概念、要素和特征：（15分钟）4. 算法的分析和评价（包括：案例分析）：（40分钟）5. 本章小结和习题安排：（5分钟）。【习题要求】1、学生独立完成，不允许抄袭。对抄袭者记0分或倒扣分处罚。 2、严格按照考核内容进行评判。 3、本次作业的成绩，记录学生期末总成绩的2%【实验要求】本章无上机实验授课对象系 别软件技术系本次课学时4学时年级班次章节题目第二章 学生信息管理系统设计目的要求(含技能要求)了解三层结构进行系统设计和开发的思想，并进行通用模块层类的封装和实现。 算法的基本概念和性质 算法的性能分析和评价本节重点简易学生信息系统设计、数据库设计、公用模块设计本节难点公用模块设计与实现教学方法讲解+案例教学 +任务驱动法，“教学做”三位一体法教学用具多媒体教室、机房问题引入从学生所熟悉的简易学生信息管理系统的功能讲解入手，进行本课程教学的引入。难点与重点讲解方法采用讲解、案例教学以及模仿训练，讲述公用模块层类封装和开发的要点。本次课小节课程小节1、 学生分组、选取项目，以及简要功能设计和数据库设计。2、 公用模块层类的封装和实现。教后札记1、 初步能应用三层结构开发思想，进行公用模块层类的设计与开发。2、 组建学生项目开发小组，为培养学生团队意识和后面的课程设计奠定基础。讨论、思考题、作业(含实训作业)见后第二章 学生信息管理设计【学习目标】1.能力目标：（1）简单数据库设计的能力（2）通用模块类封装的能力（3）与数据库连接获取的能力（4）制作主界面的能力2知识目标：（1）三层结构的思想；（2）简易学生信息管理系统模块设计；（3）简易学生信息管理系统数据库设计。（4）简易学生信息管理系统通用模块层实现。【课前准备】 环境要求：PC电脑Visual Studio 2005 、SQL Server 2000、MyEclipse 学生要求：具备SQL Server 数据库理论知识和操作能力。具备面向对象程序设计C/S结构开发能力 教师要求：能够进行三层结构的C/S项目开发能力。能够正确分析算法时间复杂度的能力。具备一定的数据库设计和分析能力。能够正确、及时处理学生操作过程中出现的问题及错误。【主要内容】 系统设计以简易的学生信息管理系统的开发来讲述数据结构和算法。重在常用的数据结构和算法的讲解，通过项目实作和可视化界面来展现数据结构和算法的结果。为了让教师教学和学生自学带来方便，在书中尽量使业务简化，功能简洁，突出数据结构和算法的实践。本书的功能结构模块图如下： 数据库设计在本书中，主要目标是进行常用的数据结构和算法的学习，为了使教师和学生不陷于复杂的业务处理中，我们只用一张学生信息表student_info来实现。其表结构设计如下：字段名称描述数据类型是否主键备注St_id学生idint主键自动增长St_name学生姓名Varchar(20)St_num学号Varchar(20)St_sex性别intSt_age年龄intSt_address家庭地址Varchaer(100)St_phone电话号码intSt_banji班级编号intSt_yw_cj语文成绩intSt_sx_cj数学成绩intSt_yy_cj英语成绩intSt_ty_cj体育成绩intSt_zz_cj政治成绩int 公用模块设计在本书的后续各个模块功能的实现，采用三层结构的思想来进行开发。即通用模块层，业务层和表现层。在本书的第二部分业务层，主要是通过数据结构和算法来讲述学生信息管理系统的业务处理，第三部分表现层，通过调用业务层类的有关方法来展现相关的信息。在本节讲述通用模块层的实现,包括：学生信息实体类的实现，数据库访问类的实现、学生信息数据控制类的实现，具体如下：1）实体类实现用以实现学生信息对象的封装，主要内容包括：与数据库学信息表字段对应的属性和构造函数的重载。2）数据库访问类实现该类主要用以完成与数据库的访问，包括：与数据库的连接，从数据库中提取数据放入数据集中，将进行改动的数据集保存到数据库中，以及执行给定标准的SQL语句。3） 学生信息控制类的实现： 该类主要实现的功能如下：l 将数据库中的学生信息通过数据库访问对象的方法调用，放入数据集对象ds中。l 通过数据集对象ds为学生信息数组base_info分配空间，并对每个成员进行初始化，为业务层提供学生信息的准备。l 在业务层发生对学生信息进行改动后，传入新的学生信息数组，调用数据库访问层的方法，将学生信息更新到数据库中去。【学习方法】自主学习、教师讲解、课题模仿练习【教学方法】媒体教学讲解+案例教学【教学实施】1、 学生信息管理系统设计和功能介绍：（10分钟）2、 学生信息管理系统数据库设计介绍（5分钟）3、 学生分组，选定一个简易项目，进行数据库设计（30分钟）4、 学生分组进行数据库实现，每个学生确定一个实体表（20分钟）5、 学生基本信息实体类的讲解。（5分钟）6、 学生模仿学生基本信息实体类，进行各自所设计的实体类的实现（20分钟）7、 数据库访问类封装讲解（15分钟）8、 学生模仿进行数据库访问层类的封装实现（30分钟）9、 学生基本信息控制类的封装与实现（15分钟）10、 学生模仿实现所设计的实体信息控制类的封装（25分钟）11、 本次课程小结（5分钟）【习题要求】 本章暂无【实验要求】1、学生独立完成实验1的内容，不允许抄袭。对抄袭者记0分或倒扣分处罚。 2、严格按照考核内容进行评判。 3、本次实验作业的成绩，记录学生期末总成绩的2% 4、实验附加思考题，可以列入本次实验的总成绩中，并记录到学生期末总成绩中。授课对象系 别软件技术系本次课学时6学时年级班次章节题目第三章 学生基本信息管理（顺序表）目的要求(含技能要求)掌握线性表、顺序表的概念和性质，利用顺序表的思想进行学生基本信息的管理 本节重点线性表的概念和性质，顺序表概念和性质，学生信息管理顺序表实现本节难点用顺序表的思想进行学生基本信息管理教学方法项目教学法，任务驱动法，“教学做”三位一体法教学用具多媒体教室+机房问题引入从学生基本信息管理功能界面的讲述入手，引入学生信息管理业务实现。难点与重点讲解方法以项目为引领，学生基本信息管理为任务驱动，将课堂讲解、案例解学、模仿实作融为一体，进行教学。本次课小节课程小节1、 线性表的基本概念和性质2、 顺序表的基本概念和性质3、 利用顺序表的思想进行学生基本信息的增、删、改、查以及保存的功能实现4、 顺序表操作的算法时间复杂度分析教后札记1、 掌握线性表和顺序表的基本概念和性质。2、 利用顺序表思想进行业务类封装。3、 通过用户界面实现业务类方法调用，显示数据。初步实现简单三层结构项目开发。讨论、思考题、作业(含实训作业)见后第三章 学生基本信息管理（顺序表）【学习目标】1 能力目标：（1）面向对象编程能力。（2）顺序表思想进行业务封装能力（3）用顺序表对数据进行增、删、改、查操作的能力（4）通过界面进行业务类调用实现的能力2知识目标：（1）线性表的概念和性质；（2）顺序表的概念、性质和操作；（3）利用顺序表实现学生基本信息增、删、改、查操作；（4）应用可视化界面实现学生基本信息管理；3职业素质目标： 顺序表操作的逻辑思维能力 独立进行顺序表操作思考解决问题能力 分小组进行小模块开发的团队协作能力 创新能力【课前准备】 环境要求：PC电脑Visual Studio 2005 、SQL Server 2000、MyEclipse 学生要求：具备SQL Server 数据库理论知识和操作能力。具备面向对象程序设计C/S结构开发能力。数据结构和算法的基本概念和性质。 教师要求：能够进行三层结构的C/S项目开发能力。具备一定的数据库设计和分析能力。能够正确、及时处理学生操作过程中出现的问题及错误。具有顺序表的理论知识和编程能力。【主要内容】1、线性表的定义和性质1）线性表（Linear List）含义：定义：线性表是具有相同的物理含义，同一数据类型的n（n>=0）个数据元素的有限序列。理解： 它解决元素之间存在“一对一”的逻辑关系。通常记为：其中，是第一个数据元素，又称为起始结点；是最后一个数据元素，又称为终端结点；n为数据元素的个数，即线性表的长度，称为表长，当n0时称为空表。在线性表中相邻元素之间存在着顺序关系。对于元素而言，称为的直接前驱，称为的直接后继。2）线性表的特性：l 有且仅有一个开始结点，它没有直接前驱。l 有且仅有一个终端结点，它没有直接后继。l 除了开始结点和终端结点外，其余结点都有且仅有一个直接前驱和一个直接后继。2、顺序表的定义和性质1）顺序表（Sequential List）的含义：定义：在计算机中，按顺序存储结构存储的线性表简称为顺序表。2）顺序表的特征：存储单元地址连续（需要一段连续空间）。逻辑上相邻的数据元素其物理地址也相邻。随机存储。存储密度大（100%）3、学生信息管理业务实现：学生基本信息管理模块，主要实现学生基本信息的增、删、改、查以及保存的功能。整个模块的设计和实现的思路如下：l 创建顺序表类，用以实现学生基本信息顺序表的管理。l 创建学生基本信息管理业务类，用以实现学生信息顺序表的增、删、改等的业务处理。具体的步骤如下：ü 从通用模块层中，获取学生基本信息，并初始化学生基本信息顺序表。ü 在学生信息查询方法中，给定学生的id，找到对应的学生信息并进行返回。ü 在增加学生信息方法中，在学生基本信息顺序表指定位置i，添加学生的信息elem。ü 在删除学生信息方法中，在学生基本信息顺序表中，删除指定位置i的学生信息。ü 在修改学生信息方法中，在学生基本信息顺序表中，修改指定学生id的信息。ü 在保存方法中，实现对学生基本信息顺序表发生增、删、改后的信息保存。1）学生基本信息顺序表的构建创建学生基本信息顺序表类，用以实现学生信息数据在顺序表中的增、删、改的操作。该类的主要成员包括：Student_info Data：一维无界数组，用以构建学生基本信息顺序表Length：用以记录顺序表中，实际的学生信息个数。2）学生基本信息管理业务类的定义学生基本信息管理业务类，是通过顺序表的思想，用来实现学生信息的增、删、改的操作。3）学生基本信息管理业务类的初始化该方法用以初始化学生基本信息顺序表，具体步骤如下：l 通过学生数据控制层对象 StudentManger 获取学生的基本信息。l 初始化顺序表的空间大小，以及初始顺序表长度。l 从数据库中提取的学生信息，逐个初始化顺序表的元素。4）查找学生基本信息查找实现本方法是指给定学生的学生id号，查找对应学生的基本信息，并返回学生在顺序表中对应对应位置和相关基本信息。基本思路为：l 对顺序表中每个元素进行循环。l 逐个查找每个学生元素的id与给定学生的id是否相同，若相同则找到返回相关信息，否则继续循环查找。l 如果循环完仍然未找到，返回null。5）新增学生基本信息业务实现具体的实现步骤如下：l 获取现有顺序表的长度n，判断插入位置i是否合法，不合法返回false。l 判断i是否超越所定义顺序表的最大值，若越界返回false。l 如是在顺序表末尾插入学生信息，直接将信息插入，顺序表长度自加，返回true。l 将之间的所有结点依次后移，为新元素让出第i个位置。将新结点elem插入到第i个位置。表长Length自加，返回true。6）删除学生基本信息业务实现删除学生基本信息的步骤如下：l 获取学生基本信息表的长度，判断所要删除结点位置是否合法，不合法，返回false。l 获取所要删除的学生基本信息。l 将第i个学生后面的学生信息之间的结点顺序依次向上移动。并使表长length自减。7）修改学生基本信息业务实现修改学生的基本信息是指：对特定学生id的基本信息发生修改，在顺序表中作相应的变化，具体的实现步骤如下：l 从学生顺序表中，进行循环，逐个提取学生基本信息中的学生id。l 判断所提取的学生id与所要修改的学生id是否一致。l 如果一致，进行学生信息的修改，并返回true。l 若不一致，继续循环，循环完毕仍未找到，返回false。8）学生基本信息保存业务实现学生基本信息的保存是指：通过界面调用上面的增、删、改等方法，对学生基本信息顺序表的信息发生改变后，将改变后的结果保存到数据库中，在这里直接调用学生数据控制层对象 StudentManger 的Save_info（）方法即可。【学法】自主学习、教师讲解、课题模仿练习，课后习题和上机实验【教学方法】项目教学+媒体教学讲解+案例教学【教学实施】1、 学生基本信息管理功能描述（5分钟）2、 线性表的定义和性质：（5分钟）3、 顺序表的定义和性质（5分钟）4、 学生基本信息顺序表节点类创建实现讲解（5分钟）5、 学生根据所设计的实体，模仿创建对应的节点类（10分钟）6、 学生基本信息管理业务类的定义和初始化（15分钟）7、 学生根据所设计的实体，模仿实现业务类的定义和顺序表的初始化（20分钟）8、 学生基本信息查找讲解（10分钟）9、 学生根据所设计的实体，模仿实现顺序表信息的查找（15分钟）10、 在顺序表中实现学生基本信息的增加。（10分钟）11、 学生根据所设计的实体，模仿实现顺序表节点详细的增加（20分钟）12、 在顺序表中实现学生基本信息的删除。（10分钟）13、 学生根据所设计的实体，模仿实现顺序表节点详细的删除（15分钟）14、 在顺序表中实现学生信息的修改。（5分钟）15、 学生根据所设计的实体，模仿实现顺序表节点详细的修改（10分钟）16、 实现学生信息的保存。（5分钟）17、 学生根据所设计的实体，模仿实现实体详细的保存（5分钟）18、 本次课程小结（5分钟）19、 通过表现层调用业务类进行界面功能实现以及调试（90分钟）【习题要求】1、学生独立完成本章习题内容，不允许抄袭。对抄袭者记0分或倒扣分处罚。 2、严格按照考核内容进行评判。 3、本次作业的成绩，记录学生期末总成绩的2% 4、附加思考题，可以列入本次作业的加分项，并记录到学生期末总成绩中。【实验要求】1、学生独立完成实验2的内容，不允许抄袭。对抄袭者记0分或倒扣分处罚。 2、严格按照考核内容进行评判。 3、本次实验作业的成绩，记录学生期末总成绩的2% 4、实验附加思考题，可以列入本次实验的总成绩中，并记录到学生期末总成绩中。授课对象系 别软件技术系本次课学时8学时年级班次章节题目第4章 学生成绩信息管理（链表）目的要求(含技能要求)掌握链表的基本功能和存储方式，利用单向链表实现学生成绩信息的管理。了解循环链表和双向链表的功能和简单的操作。本节重点链表和单向链表的基本功能和操作。本节难点用单向链表的思想实现学生成绩信息的管理教学方法项目教学法，任务驱动法，模仿学习法，“教学做”三位一体法教学用具多媒体教室、机房问题引入从学生成绩信息管理功能界面的讲述入手，引入学生成绩信息管理业务实现难点与重点讲解方法以项目为引领，学生成绩信息管理为任务驱动，将课堂讲解、案例解学、模仿实作融为一体，进行教学。本次课小节课程小节1、 链表的基本概念和存储方式。2、 单向链表的基本概念以及操作。3、 利用单向链表的思想进行学生成绩信息的增、删、改、查以及保存的功能实现。4、 单向循环链表的基本概念和操作。5、 双向链表和双向循环链表的基本功能和操作。教后札记1、 掌握单向链表的基本概念和性质。2、 利用单向链表思想进行学生成绩信息业务类封装。3、 通过用户界面实现业务类方法调用，显示数据。初步实现简单三层结构项目开发。讨论、思考题、作业(含实训作业)见后第四章 学生成绩信息管理（链表）【学习目标】1 能力目标：（1）面向对象编程能力。（2）链表思想进行业务封装能力（3）应用链表对学生成绩信息进行增、删、改、查操作的能力（4）通过界面进行业务类调用实现能力2知识目标：（1）链表的概念和存储方式；（2）单向链表的概念性质和操作；（3）利用单向链表实现学生成绩信息增、删、改、查操作；（4）应用可视化界面实现学生成绩信息管理；（5）双向链表的基本概念和操作；（6）循环链表的基本概念和操作；3职业素质目标： 链表操作的逻辑思维能力 应用单向链表独立思考解决问题能力 小组项目团队协作开发能力 创新能力【课前准备】 环境要求：PC电脑Visual Studio 2005 、SQL Server 2000、MyEclipse 学生要求：具备SQL Server 数据库理论知识和操作能力。具备面向对象程序设计C/S结构开发能力。线性表的基本概念和性质。顺序表基本概念、性质和操作应用能力。 教师要求：能够进行三层结构的C/S项目开发能力。具备一定的数据库设计和分析能力。能够正确、及时处理学生操作过程中出现的问题及错误。能够应用各种常用链表实现数据增、删、改、查的能力。【主要内容】1、链表的基本概念和存储方式在线性表的顺序存储结构中，其特点是逻辑关系上相邻的两个结点在物理位置上也相邻，因此可以随机存取表中的任一结点，并且结点的存储位置可用一个简单直观的公式来表示。但也正是这个特点造成顺序存储的一些缺点。例如，存储空间空闲、存储容量难以扩充、当进行插入和删除运算时需移动大量的结点、效率较低等。1）链表的定义：链表是线性表的一种，是通过链式存储方式来保存数据的线性表。2）链表的存储方式：在计算机内存中利用存储单元（不要求连续）来存放结点的值及它在内存中的地址，各个结点的存放顺序及位置可以以任意顺序进行，原来相邻的结点在计算机内存中的存储位置不一定相邻，从一个元素查找下一个元素必须通过地址（指针）才能实现，因此它不能像顺序表那样随机访问，而只能按顺序访问。2、单向链表含义单向链表（Single linked list）是最简单的链表，每个结点包含一个数据域和一个指针域，结点之间的关系是通过指针域来访问的，最后一个结点的指针域为空。3、应用单向链表思想进行学生成绩信息管理业务实现：学生成绩信息管理模块，主要实现学生成绩信息的增、删、改、查以及保存的功能。整个模块的设计和实现的思路如下：Ø 创建学生成绩单向链表类，用以实现单个学生成绩信息的记录。Ø 创建学生成绩信息管理业务类，用以实现学生成绩信息单向链表的增、删、改等的业务处理。具体的步骤如下：l 从通用模块层中，获取学生成绩信息，并初始化学生成绩单向链表对象。l 在学生成绩查询方法中，给定学生的id，找到对应的学生成绩信息进行返回。l 在增加学生成绩方法中，在学生成绩单向链表中指定位置i，添加学生成绩信息elem。l 在删除学生成绩方法中，在学生成绩单向链表中，删除指定位置i的学生成绩信息。l 在修改学生成绩方法中，在学生成绩单向链表中，修改指定学生id成绩信息。l 在保存方法中，实现对学生成绩单向链表发生增、删、改后的信息保存。1）学生成绩单向链表结点类构建创建学生成绩信息单向链表结点类，用以实现学生成绩信息数据在单向链表中的增、删、改的管理。该类的主要成员包括：Student_info Data：数据域，学生信息对象，用以记录学生的基本信息和成绩信息node Next：指针域，用以指向下一个学生的结点。2）学生成绩信息管理业务类构建学生成绩信息业务类，是应用单向链表的思想，用以实现学生成绩信息的增、删、改、查等操作，主要的成员和方法如下所示：3）学生成绩信息单向链表创建该方法用以实现学生成绩单向链表的初始化。主要的思路是从数据控制对象中得到已有的所有学生成绩，分别创建结点，初始化各个学生的成绩，并添加到对象链表中。具体步骤如下：（1）、为链表对象L，分配内存空间，并使指针域为空，带头结点的空单向链表创建好。（2）、定义局部单向链表对象p，用以创建链表其他学生成绩信息结点。（3）、利用数据控制层对象的学生信息数组，逐个读取，初始化单向链表结点，并添加到单向链表中，具体作法如下：逐个循环，为局部学生成绩链表对象p，分配新空间。从数据控制层学生信息数组获取信息，为对象p的数据域赋值。修改局部对象p和成员单向链表对象L的指针域。4）学生成绩信息的查询该方法是根据所输入的学生id信息，在单向链表中进行查找，返回学生在链表中的位置和该学生的所有信息。具体思路如下：（1）、调用该方法之前，先创建学生信息对象elem，并把所要查找的学生id赋值到elem对象的学生id属性st_id。（在C#中应用引用传值，在Java中用对象传值）。（2）、声明局部变量 int place=0；用以记录所找id在链表中的位置。（3）、声明局部学生成绩信息链表结点p=L；通过p=p.next操作，来实现从链表头到链表尾的搜索。（4）、对链表的各个结点进行搜索，判断各个结点的学生id与输入对象elem的学生id是否相等，若相等，表示找到。返回所找学生信息和所在的位置。（5）、若循环完毕仍未找到，返回位置null。5）学生成绩信息链表中插入学生成绩信息在单向链表插入结点的基本思路如下：将学生成绩信息x的新结点插入到表的第i个位置上，即插入到与之间。为此，必须首先找到结点的存储位置（用p表示），然后建立一个数据域为x的新结点（用s表示），并令结点的指针域指向新结点，而新结点的指针域则指向结点，从而实现了三个结点，x，之间逻辑关系的变化。单链表插入运算的示意图如图4.5所示。图4.5 在单链表中插入结点x学生成绩信息单向链表插入的流程图如下：6）学生成绩信息的删除该方法的功能是，删除单向链表中第i个结点的信息，并返回是否删除成功和所删除的学生成绩信息。具体步骤为：首先，使指针p指向要删除结点的直接前驱；然后，将要删除的学生信息赋值给要返回的对象。最后，将p的指针域指向要删除结点的直接后继。图4.7反映了删除结点时指针的变化。图4.7 删除单链表中值为x的结点7）学生成绩信息的修改该方法用以修改指定学生id的学生成绩信息，实现的思想与学生成绩信息查找相似。8）学生成绩信息的保存学生成绩信息的保存是指：在单向链表中进行了增、删、改后，要将学生成绩信息保存到数据库中。在这里我们通过调用数据控制层的save_info（）来实现。4、 单向循环链表：单链表结点之间是用一个指针域链接，其终端结点的指针域的值为NULL，表示单链表的结束。若将单链表的终端结点的指针域指向头结点，则整个链表头尾结点相链形成一个环，从而就构成了循环链表（circular linked list）。如图4.9所示： a1anhead图4.9 单循环链表循环链表的主要优点是从表中任一结点出发，都能通过后移操作来扫描整个链表（对单链表而言，则只能从头结点开始）。单向循环链表上的操作与前面讨论的单链表的操作基本一致，差别仅仅在于算法中控制循环中止的条件不是判断指针是否为空，而是判断指针是否指向头指针。在单向循环链表的其他操作方法，与单向链表操作类似，只是终止条件由p!=NULL改为p!= L即可。5、 双向链表和双向循环链表在循环链表中，虽然从任一结点出发都可以找到其前驱结点，但时间复杂度为O(n)，原因在于其每个结点只含有一个指向其直接后继的指针域，这对于寻找后继结点是很方便的。若想快速确定一个结点的直接前驱，则可以在单链表的基础上，每个结点再加上一个指针域存储其直接前驱的地址，这样就构成了双向链表（Double linked lists）。其结点形式如图4.10所示。图4.10 双向链表的结点结构其中，prior域指向其前驱结点，next指向其后继结点，data域存放结点本身的信息。1）双向链表插入操作由于双向链表是一种对称结构，每个结点既有指向其直接前驱的指针域，又有指向其直接后继的指针域，因此与单链表相比，要在双向链表中查找一个已知结点的直接前驱和直接后继要方便得多。以下算法实现在双向链表中第i个结点前插入值为x的新结点。图4.11反映了双向链表中插入结点时指针的变化情况。图4.11 双向链表的插入运算2）双向链表的删除操作以下算法实现在双向链表中删除第i个结点。图4.12反映了双向链表中删除结点时指针的变化情况。图4.12 双向链表的删除运算【学法】自主学习、教师讲解、课题模仿练习、课外探讨学习、课后习题和上机实验【教学方法】项目教学+媒体教学讲解+案例教学【教学实施】1) 学生成绩信息管理功能描述（5分钟）2) 链表的基本功能和存储方式：（5分钟）3) 单向链表的定义和理解（10分钟）4) 学生成绩信息单向链表节点类创建实现讲解（3分钟）5) 学生根据所设计的实体，模仿创建对应的节点类（7分钟）6) 学生成绩信息管理业务类的定义和初始化（15分钟）7) 学生根据所设计的实体，模仿实现业务类的定义和单向链表的初始化（20分钟）8) 学生成绩信息查找讲解（10分钟）9) 学生根据所设计的实体，模仿实现链表信息的查找（15分钟）10) 在单向链表中实现学生成绩信息的增加。（15分钟）11) 学生根据所设计的实体，模仿实现单向链表节点详细的增加（30分钟）12) 在单向链表中实现学生成绩信息的删除。（15分钟）13) 学生根据所设计的实体，模仿实现单向链表节点详细的删除（30分钟）14) 在单向链表中实现学生信息的修改。（5分钟）15) 学生根据所设计的实体，模仿实现单向链表节点详细的修改（10分钟）16) 实现学生成绩信息的保存。（5分钟）17) 学生根据所设计的实体，模仿实现实体详细的保存（5分钟）18) 单向循环链表的概念和操作。（20分钟）19) 双向链表的概念和操作。（30分钟）20) 双向循环链表的概念和操作。（10分钟）21) 本次课程小结（5分钟）22) 通过表现层调用业务类进行界面功能实现以及调试（90分钟）【习题要求】1、学生独立完成本章习题内容，不允许抄袭。对抄袭者记0分或倒扣分处罚。 2、严格按照考核内容进行评判。 3、本次作业的成绩，记录学生期末总成绩的2% 4、附加思考题，可以列入本次作业的加分项，并记录到学生期末总成绩中。【实验要求】1、学生独立完成实验3的内容，不允许抄袭。对抄袭者记0分或倒扣分处罚。 2、严格按照考核内容进行评判。 3、本次实验作业的成绩，记录学生期末总成绩的2%4、实验附加思考题，可以列入本次实验的总成绩中，并记录到学生期末总成绩中。授课对象系 别软件技术系本次课学时4学时年级班次章节题目第5章 学生基本信息审核（栈）目的要求(含技能要求)掌握栈的基本概念、性质和操作、利用栈的思想思想学生基本信息审核本节重点栈的基本概念和操作，以及栈的应用本节难点应用栈的思想实现学生基本信息的审核教学方法项目教学法，任务驱动法，模仿学习法，“教学做”三位一体法教学用具多媒体教室、机房问题引入从学生基本信息审核管理功能界面的讲述入手，介绍简单的学生基本信息审核的流程，以及实现的步骤。难点与重点讲解方法以项目为引领，学生基本信息审核管理为任务驱动，将课堂讲解、案例解学、模仿实作融为一体，进行教学。本次课小节课程小节1、 栈的基本概念、性质和操作2、 栈的存储方式和分类3、 利用顺序栈实现学生基本信息的审核4、 栈的其它应用教后札记1、 掌握栈的基本概念、性质、操作、分类。2、 利用顺序栈实现学生基本信息审核业务类的封装。3、 通过用户界面实现业务类方法的调用，显示数据，实现审核的功能。讨论、思考题、作业(含实训作业)见后第五章 学生基本信息审核（栈）【学习目标】1 能力目标：（1）面向对象编程能力。（2）栈的基本概念和编程能力。（3）应用栈的思想实现学生基本信息审核的业务类封装编程能力。（4）通过界面进行业务类调用显示的能力2知识目标：（1）栈的基本概念、类型和存储方式；（2）顺序栈的概念和操作；（3）利用顺序栈实现学生基本信息的审核；（4）应用可视化界面实现学生基本信息审核管理；（5）了解链栈的基本概念和操作；（6）了解栈编程思想的其它应用。 3职业素质目标： 顺序栈进行编程的逻辑思维能力 利用顺序栈独立思考解决问题能力 分小组进行团队开发能力 创新能力【课前准备】 环境要求：PC电脑Visual Studio 2005 、SQL Server 2000、MyEclipse 学生要求：具备SQL Server 数据库理论知识和操作能力。具备面向对象程序设计C/S结构开发能力具备顺序表、链表的理论知识和操作能力。 教师要求：能够进行三层结构的C/S项目开