数据基础结构 9

教案纸（首页）第1页第次课学时授课时间___________教学主题线性表2.1线性表的基本概念；2.2线性表的顺序存储结构教学要求1、掌握线性表的逻辑结构特点，线性表抽象数据类型的描述方法。2、掌握线性表的顺序存储结构的优缺点。教学重点线性表的逻辑结构特点；线性表的顺序存储结构特点及其实现。教学难点线性表的顺序存储结构的特点及其实现教学方法讲授教学手段多媒体+板书讲授要点1、线性表的概念及其逻辑结构特点。2、线性表抽象数据类型的描述方法。3、线性表的顺序存储结构。作业完成学习通上第二章中有关顺序表的作业。参考资料教材：数据结构教程（第5版），清华大学出版社，李春葆等2017。参考资料：数据结构（C语言），清华大学出版社，严蔚敏吴伟民编著。注：本页为每次课教案首页教案纸（续页）第3页教学内容备注与后记2.1线性表的基本概念1、线性表的定义线性表是一个具有相同特性的数据元素的有限序列。三个特性：一致性；有穷性；序列性。线性表的逻辑表示：(a1，a2，…，ai，ai+1，…，an)ai（1≤i≤n）表示第i（i表示逻辑位序）个元素。举实例说明，加深学生对线性表的认识。2、线性表的基本运算初始化线性表InitList(&L)：构造一个空的线性表L。销毁线性表DestroyList(&L)：释放线性表L占用的内存空间。判线性表是否为空表ListEmpty(L)：若L为空表，则返回真，否则返回假。求线性表的长度ListLength(L)：返回L中元素个数n。输出线性表DispList(L)：线性表L不为空时，顺序显示L中各结点的值域。求线性表L中指定位置的某个数据元素GetElem(L，i，&e)：用e返回L中第i（1≤i≤n）个元素的值。定位查找LocateElem(L，e)：返回L中第一个值域与e相等的逻辑位序。若这样的元素不存在，则返回值为0。插入一个数据元素ListInsert(&L，i，e)：在L的第i（1≤i≤n）个元素位置插入新的元素e，L的长度增1。删除数据元素ListDelete(&L，i，&e)：删除L的第i（1≤i≤n）个元素，并用e返回其值，L的长度减1。3、线性表的抽象数据类型ADTList{数据对象：D={ai|1≤i≤n，n≥0，ai为ElemType类型}//ElemType是自定义类型标识符数据关系：R={<ai，ai+1>|ai、ai+1∈D，i=1，…，n-1}基本运算：9个运算}2.2线性表的顺序存储结构1、线性表的顺序存储——顺序表线性表的顺序存储结构：把线性表中的所有元素按照顺序存储方法进行存储。按逻辑顺序依次存储到存储器中一片连续的存储空间中。2、顺序表的运算的实现InitList(&L)//结构初始化DestroyList(&L)//销毁线性表ListEmpty(&L)//判定是否为空表ListLength(L)//线性表的长度DispList(L)//输出线性表GetElem(L，i，e)//求某个数据元素值LocateElem(L,e)//查找ListInsert(&L,i,e)//插入元素ListDelete(&L,i，e)//删除元素重点讲解以下操作：ListInsert(&L,i,e)的实现：首先分析插入元素时，线性表的逻辑结构发生什么变化？ListDelete(&L,i,&e)的实现：首先分析：删除元素时，线性表的逻辑结构发生什么变化？线性表类型的实现3、顺序表的应用示例删除线性表中所有值为x的数据元素教学总结：本节课给大家介绍了线性表的基本定义，线性表的逻辑结构特点以及线性表的顺序存储结构，以上知识点是数据结构中的非常重要的，大家必须要掌握。

第次课学时授课时间_________教学主题线性表线性表的链式存储结构教学要求通过本章节的学习，学生应达到如下基本要求：1、掌握线性表链式存储结构设计方法及其优缺点。2、掌握单链表、双链表和循环链表算法设计方法。教学重点单链表的查找、插入和删除操作过程及其实现；双链表的查找、插入和删除操作过程及其实现。双链表的查找、插入和删除操作过程及其实现。教学难点单链表的查找、插入和删除操作过程及其实现。教学方法讲授、练习教学手段多媒体、板书、上机实操讲授要点1、线性表的链式存储结构。2、单链表的算法设计方法。3、双链表的算法设计方法。4、循环链表的算法设计方法。作业完成学习通上第二章作业中有关链表的练习题。参考资料教材：数据结构教程（第5版），清华大学出版社，李春葆等2017。参考资料：数据结构（C语言），清华大学出版社，严蔚敏吴伟民编著。注：本页为每次课教案首页教案纸（续页）第3页教学内容备注与后记2.3线性表的链式存储结构1、线性表的链式存储结构——链表特点：线性表中每个结点有唯一的前驱结点和后继结点。设计链式存储结构时，每个逻辑结点存储单独存储，为了表示逻辑关系，增加指针域。头结点：单链表中增加一个头结点的优点如下：第一个结点的操作和表中其他结点的操作相一致，无需进行特殊处理；无论链表是否为空，都有一个头结点，因此空表和非空表的处理也就统一了。存储密度是指结点数据本身所占的存储量和整个结点结构中所占的存储量之比。2、单链表单链表结点的定义typedefstructLNode//定义单链表结点类型{ElemTypedata;structLNode*next;//指向后继结点}LinkNode;单链表的特点：当访问过一个结点后，只能接着访问它的后继结点，而无法访问它的前驱结点。插入结点：只需修改相关结点的指针域，不需要移动结点。s->next=p->next;p->next=s;删除结点：只需修改相关结点的指针域，不需要移动结点p->next=p->next->next;线性表的9种基本操作在单链表中的实现，重点讲解插入和删除一个结点的操作实现。3、双链表双链表的结点定义：typedefstructDNode //双链表结点类型{ElemTypedata;structDNode*prior; //指向前驱结点structDNode*next; //指向后继结点}DLinkNode;双链表的特点：从任一结点出发可以快速找到其前驱结点和后继结点；从任一结点出发可以访问其他结点。双链表的插入操作操作语句：s->next=p->nextp->next->prior=ss->prior=pp->next=s双链表的插入操作p->next->next->prior=pp->next=p->next->next4、循环链表循环单链表：将表中尾结点的指针域改为指向表头结点，整个链表形成一个环。由此从表中任一结点出发均可找到链表中其他结点。循环双链表：形成两个环。教学总结：本章节主要介绍了线性表的链式存储结构特点，单链表、双链表和循环链表的特点和基本操作的实现，其中单链表的内容是需要大家重点掌握的。

第次课学时授课时间_____教学主题线性表线性表的应用、有序表教学要求通过本章节的学习，学生应达到如下基本要求：1、掌握掌握顺序表、单链表的算法设计方法。2、掌握有序表的特点和有序表的归并算法设计方法。教学重点顺序表、单链表的应用算法设计；有序表的特点。双链表的查找、插入和删除操作过程及其实现。教学难点线性表的应用算法设计实现；有序表的特点。教学方法讲授、练习教学手段多媒体、板书、上机实操讲授要点1、利用线性表求解复杂问题的方法。2、有序表的特点和归并算法设计。作业完成学习通上第二章作业中线性表的练习题。参考资料教材：数据结构教程（第5版），清华大学出版社，李春葆等2017。参考资料：数据结构（C语言），清华大学出版社，严蔚敏吴伟民编著。注：本页为每次课教案首页教案纸（续页）教学内容备注与后记2.4线性表的应用1、基于顺序表基本操作的算法设计查找元素插入元素删除元素例子：将整数顺序表L以第一个元素为分界线（基准）进行划分在顺序表L中删除所有值为x的元素……2、单链表算法设计查找结点插入结点删除结点基于两个建表方法的单链表算法设计：头插法：相对次序相反尾插法：相对次序相同例子：设计一个算法，删除一个单链表L中元素值最大的结点（假设最大值结点是唯一的）；有一个带头结点的单链表L（至少有一个数据结点），设计一个算法使其元素递增有序排列。2.5有序表所谓有序表，是指这样的线性表，其