第2章线性表.docVIP

第二章 线性表 课程简要说明 数据结构是计算机学科的一门核心专业基础课程，是计算机程序设计的重要理论和实践基础。本课程讨论了软件设计中经常遇到的线性表、堆栈、队列、串、数组、二叉树、图等典型数据结构的设计方法以及各种典型排序和查找算法的性能和设计方法，并介绍了各种典型数据结构的应用。通过本课程的学习，学生对软件设计的基本要素和软件的基本结构有了深入理解，并通过算法设计方法学习和上机编程实践，编程能力有了进一步提高。课程要求掌握主要内容包括：线性表、堆栈、队列、串、数组、树、二叉树、图等典型数据结构问题的逻辑结构、存储结构和操作的实现方法，各种典型的排序和查找算法，以及递归算法的设计方法。 通过本课程的学习，应使学生掌握各种数据结构的特点：存贮表示、运算方法以及在计算机科学中最基本的应用，培养、训练学生选用合适的数据结构和运用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语言定义（动态分配方式） #define??? LIST_INT_SIZE 100 #define???? LISTINCREAMENT 10 typedef? struct ?? { ??? ??ElemType? *elem； /* 线性表占用的数组空间。*/ ? ?? ??int??????? length；???? /*线性表的长度*/ ????