第2章线性表

第二章线性表课程简要说明数据结构是计算机学科的一门核心专业基础课程，是计算机程序设计的重要理论和实践基础。本课程讨论了软件设计中经常遇到的线性表、堆栈、队列、串、数组、二叉树、图等典型数据结构的设计方法以及各种典型排序和查找算法的性能和设计方法，并介绍了各种典型数据结构的应用。通过本课程的学习，学生对软件设计的基本要素和软件的基本结构有了深入理解，并通过算法设计方法学习和上机编程实践，编程能力有了进一步提高。课程要求掌握主要内容包括：线性表、堆栈、队列、串、数组、树、二叉树、图等典型数据结构问题的逻辑结构、存储结构和操作的实现方法，各种典型的排序和查找算法，以及递归算法的设计方法。通过本课程的学习，应使学生掌握各种数据结构的特点：存贮表示、运算方法以及在计算机科学中最基本的应用，培养、训练学生选用合适的数据结构和运用C语言编写质量高、风格好的应用程序及初步评价算法程序的能力；为编译技术、操作系统和数据库等后续课程的学习以及为应用软件特别是非数值应用软件的开发打下良好的理论基础和实践基础。要求结合实际问题，学会分析计算机加工的数据对象的特性，能够选择适当的数据结构和存储结构以及相应的算法，并初步掌握算法的简单时间复杂度分析方法，训练掌握各种数据结构的表示方法和实现的算法。(1)知识要求：学生通过学习该课程后主要应掌握以下内容：①掌握程序设计的基本原理和方法②了解对各种抽象数据类型的性质③掌握处理各种抽象数据类型的基本算法④初步掌握算法的简单时间复杂度分析方法(2)素质要求：学生通过学习该课程后能够运用数据结构的思想，针对不同数据对象的特性，能够选择适当的数据结构和存储结构以及相应的算法，解决实际的问题。(3)能力要求：学生通过学习该课程后能够应用一门程序设计语言进行各种应用系统的设计、开发及维护。【第三次（2学时）】教学主题或章、节第二章线性表授课类型理论课√实验课实习或课程设计练习课其他□教学过程前面章节复习5分钟，新课93分钟，布置作业2分钟教学方式讲授√讨论√阅读√示范操作练习提问√其他□教学资源多媒体课件√演示动画√相关软件音像其他√教学目的及要求（分掌握、理解、了解三个层次）：理解线性表的定义和抽象数据类型，掌握线性表的顺序存储结构，掌握线性表的顺序表示和操作实现并能灵活应用。教学内容提要：第一部分前面章节简要回顾（约5分钟）对C语言中的指针应用，指针作为参数使用的特点做简要回顾。第二部分新课（约93分钟）第2章线性表抽象数据类型及线性表的顺序表示和实现本章内容概述（约5分钟）简述本章基本要求、学习内容、重点、以及本章教学内容安排。课程导入：采用任务驱动的方法，提出要建立学生成绩管理系统，如何实现？引入线性结构的特点。线性结构的特点：–存在唯一一个被称做“第一个”的数据元素；–存在唯一一个被称做“最后一个”的数据元素；–除第一个数据元素之外，每个元素都只有一个前驱；–除最后一个数据元素之外，每个元素都只有一个后继。§2.1线性表的类型定义（约15分钟）（1）线性表定义：是n个数据元素的有限序列。介绍相关基本概念结合任务学生管理系统、分析系统所涉及数据的特点。（2）线性表的特征：有穷性、有序性、同一性。（3）线性表的抽象数据类型定义：(略讲)重点讲述基本操作部分，包括：结构初始化操作、结构销毁操作、引用型操作、加工型操作、复杂操作注：举算法实例讲解举例：利用线性表实现集合的并、集合的无重复并，线性表的合并§2.2线性表的顺序表示和实现——顺序映象（约70分钟）一、顺序表示和实现的基本概念和表示方式（约15分钟）（1）线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素。特点：是一种随即存取的存储结构，只要确定了起始位置，就可以访问表中的任何一个元素。用物理位置来表示逻辑结构地址的计算方法。LOC(ai+1)=LOC(ai)+l;LOC(ai)=LOC(a1)+(i-1)*l举例说明，其计算方式。（2）线性表顺序存储结构的——C语言定义（动态分配方式）#defineLIST_INT_SIZE100#defineLISTINCREAMENT10typedefstruct{ElemType*elem；/*线性表占用的数组空间。*/intlength；/*线性表的长度*/intlistsize；/*当前分配的存储容量(以sizeof(ElemType)为单位)/*}SeqList；同时对比其顺序存储结构的静态分配方式，二者运用的区别和不同。二、顺序存储结构的基本操作（约55分钟）顺序表容易实现访问操作，可随机存取元素。但插入和删除操作主要是移动元素。（1）初始化操作（约10分钟）算法思想：构造一个空表。设置表的起始位置、表长及可用空间。重点讲解初始化的作用，以及如何进行实现。（2）线性表的顺序表插入操作ListInsert(&L,i,e)（约17分钟）通过提问方式引入，针对原来提出的任务，建造一个学生管理系统，在管理过程中，如果新来一位同学的话，如何更新原来的系统，引出插入，算法的基本思想：检查i值是否超出所允许的范围（1≤i≤n+1），若超出，则进行“超出范围”错误处理；将线性表的第i个元素和它后面的所有元素均向后移动一个位置；将新元素写入到空出的第i个位置上；使线性表的长度增1。重点讲解如何插入的思想，如何把思想转化为语言进行实现，并分析插入操作的时间复杂度、以及在插入过程中平均移动元素的次数。在讲解过程中举例说明。并布置一定的任务，课下实现学生管理系统的插入算法。（3）线性表的顺序表删除操作ListDelete(&La,i,&e)（约17分钟）同样的方式提出，如果某个学生退学，应该如何更改原来的学生信息，简述删除算法的基本思想，检查i值是否超出所允许的范围（1≤i≤n），若超出，则进行“超出范围”错误处理；将线性表的第i个元素后面的所有元素均向前移动一个位置；使线性表的长度减1。重点讲解如何删除的思想，如何把思想转化为语言进行实现，并分析删除操作的时间复杂度、以及在插入过程中平均移动元素的次数。在讲解过程中举例说明。并布置一定的任务，课下实现学生管理系统的删除算法。（4）线性表的顺序表查找操作LocateElem_Sq(La,e)（约12分钟）同样的方式提出，如果要查询学生的新题，应该如何更改原来的学生信息，简述查找算法的基本思想。举例说明。分析其时间复杂度。三、顺序存储结构的优缺点（约3分钟）顺序存储结构的优点：逻辑相邻，物理相邻、可随机存取任一元素、存储空间使用紧凑。缺点：插入、删除操作需要移动大量的元素、预先分配空间需按最大空间分配，利用不充分、表容量难以扩充。§小结（约3分钟）内容回顾、重点、难点。第三部分布置作业（约2分钟）书面作业：完成学生管理系统中的查找算法、插入算法、删除算法。重点和难点：重点：顺序存储结构的四种基本操作实现、及其时间复杂度分析。难点：将具体算法思想转换成语言的实现过程。参考资料：《数据结构题集》严蔚敏等编著，清华大学出版社《数据结构学习指导与习题详解》张凤琴等编，清华大学出版社《数据结构（C语言篇）习题与解析》李春葆编，清华大学出版社注意事项及心得：线性表的抽象数据类型的定义要简略讲，注意把握时间。注：表中选项打“√”【第四次（2学时）】教学主题或章、节第2.3节线性表的链式表示与实现授课类型理论课√实验课实习或课程设计练习课其他□教学过程前面章节复习5分钟，新课93分钟，布置作业2分钟教学方式讲授√讨论√阅读√示范操作练习提问√其他□教学资源多媒体课件√演示动画√相关软件音像其他√教学目的及要求（分掌握、理解、了解三个层次）：本次课程要求学生理解线性表的链式存储结构、掌握线性表的链式存储结构定义方式、以及如何创建单链表、插入单链表、删除单链表等基本操作、掌握各种操作方法时间复杂度的分析方法教学内容提要：第一部分前面章节简要回顾（约3分钟）提问：线性表的顺序存储结构中如何表示数据元素之间的逻辑关系？本章前面2.2节“线性表的顺序表示和实现”的一些内容的简要回顾，引出2.3节“线性表的链式表示和实现”的基本思想。第二部分新课（约95分钟）§2.3线性表的链式表示与实现讲述线性表链式表示的基本思想（约5分钟）设问：线性表的链式存储结构中如何表示数据元素之间的逻辑关系？通过简单图示讲述线性表的链式表示的基本思想，使学生对线性表的链式存储结构中数据元素间逻辑关系的表示有个大概的认识。2.3.1单链表（线性链表）（约90分钟）一、单链表存储结构C语言的实现（约20分钟）定义：结点中只含一个指针域的链表。分析其特征。举例说明，分析头结点、头指针、首元结点的特点，进行比较说明。typedefstructLNode{ElemTypedata;structLNode*next;}LNode，*LinkList;生成一个LNode型新结点：p=(LinkList)malloc(sizeof(LNode));的方式。系统回收p结点：free(p)分析单链表的特点。二、单链表基本操作的实现（约70分钟）（1）查找操作的实现GetElem(L,i,&e)（约20分钟）算法思想：令p为指针变量，首先指向第一个结点，变量j为计数器；依次向后查找，循环结束的条件，p为空或者j=i。如果p为空并且ji，出错，则找到了，用e返回第i个元素。分析在查找过程中查找成功的和失败的条件示例说明，并分析算法的时间复杂度，举例说明。（2）单链表的插入操作ListInsert(&L,i,e)（约15分钟）分析：“插入元素”使线性表的逻辑结构和物理结构发生什么变化？假设在线性表的第i个元素之前插入一个元素e。通过示例说明其逻辑结构变化和物理结构的变化，分析物理结构变化的具体实现方式。通过动画演示插入过程中指针的变化过程，并分析要在第i个位置之前进行插入，需先查找到第i-1个元素。之后进行插入操作。分析其时间复杂度。（3）单链表的删除操作ListDelete(&L,i,&e)（约15分钟）分析：“删除元素”使线性表的物理结构发生什么变化？通过示例说明其逻辑结构变化和物理结构的变化，分析物理结构变化的具体实现方式。通过动画演示删除过程中指针的变化过程，并分析要删除第i个位置之前进行插入，需先查找到第i-1个元素。之后进行删除操作。分析其时间复杂度。（4）创建单链表CreateList_L(&L,n)（约20分钟）分析创建单链表的过程，演示头插法创建单链表的过程。通过演示分析其具体实现过程。主要讲解在创建过程中指针的变化过程。演示尾插法创建单链表的过程，通过演示，提出问题，如何实现尾插法创建链表？§小结（约3分钟）内容回顾、重点、难点。第三部分布置作业（约2分钟）分别将单链表的创建、插入、和删除、用C语言实现重点和难点：重点：链表的定义，单链表的创建、插入、和删除操作算法。难点：链表的创建、插入和删除算法的C语言实现参考资料：《数据结构题集》严蔚敏等编著，清华大学出版社《数据结构学习指导与习题详解》张凤琴等编，清华大学出版社《数据结构（C语言篇）习题与解析》李春葆编，清华大学出版社注意事项及心得：第4章的第3、第4小节要简略讲，注意把握时间。注：表中选项打“√”【第五次（2学时）】教学主题或章、节第2章2.2节“链表”简要回顾第2章2.3线性表的链式表示和实现授课类型理论课√实验课实习或课程设计练习课其他□教学过程前面章节复习3分钟，新课95分钟，布置作业2分钟教学方式讲授√讨论√阅读√示范操作练习提问√其他□教学资源多媒体课件√演示动画√相关软件音像其他√教学目的及要求（分掌握、理解、了解三个层次）：本次课程要求学生理解链表的扩充、静态链表、双向链表、循环链表以及的基本概念，对静态链表的概念及其相关算法要有一定的了解。掌握在双向链表中插入元素删除元素的操作，以及循环链表的特点。教学内容提要：第一部分前面章节简要回顾（约3分钟）提问：线性表的链式存储结构中如何表示数据元素之间的逻辑关系？本章前面2.2节单链表中的一些内容的简要回顾第二部分应用（约30分钟）针对在2.1节讲述的将两个有序表合并为一个有序表的基本