(1)线性表的顺序存储中各运算的实现及其时间复杂性分析,尤其是插入和删除运 (2)线性表的链式存储中各运算的实现时间和空间复杂性分析,尤其是插入和删除 运算 5.授课提示 下面是线性表一章的重点和难点内容的讲授注意事项。 (1)线性表的基本概念 线性表是由称为元素的数据项组成的一种有限且有序的序列,这些元素也可称为结点 或表目。这些数据元素之间呈线性关系,且元素在不同情况下具有不同的含义 授课时需要强调的是,虽然概念上并不反对线性表具有不同类型的数据元素,诸如广义 表,但简单线性表中约定所有元素都具有相同的或简单或复合结构的数据类型,并须事先给 出其类型定义。 此外,在讲授线性表的存储结构时,需要强调顺序表和链表这两类存储方式分别针对定 长的和变长的线性表而设立,有各自不同的适用场景和局限 (2)线性表的顺序存储及实现 线性表的顺序存储结构,简称顺序表,是一种存储定长线性表的方法。其主要特点是 为线性表分配一块连续的存储空间,元素顺序地存储在这些地址连续的空间中,以“物理位 置相邻”来表示线性表中数据元素之间的关系。 顺序表是一种非常有用的数据结构,其优点体现在可以按位置对元素进行随机访问,但 其至少存在两方面的局限:(1)改变顺序表的大小需要重新创建一个新的顺序表并把原有的 数据都复制过去;(2)因为逻辑关系是通过物理位置的相邻来表示的,增删元素平均需要移 动一半的元素。 授课时在强调顺序表在访问元素时的便利性的同时,也须说明其缺点何在。需要重点介 绍如何在顺序表上实现元素的插入和删除运算,以及如何通过移动元素的数目来计算其时间 复杂性,最好辅以实例来说明。 (3)线性表的链式存储及实现 线性表的链式存储结构,简称链表,是用于存储变长线性表的存储方法。链接式存储结 构使用指针来表示元素之间的线性关系,利用线性表的前驱和后继关系将各个元素用指针链 接起来。 授课时须强调的是,链表可以看成一组既存储数据又存储相互连接信息的结点集合,由 由鉴于此,各结点就不必如顺序表那样存放在连续的存储空间中,而可以散放在存储空间的 各处,通过指针来按照线性表的前驱关系链接各结点。 还须强调的是,链表的特点是可以动态地申请内存空间,根据线性表元素的多少动态地 改变其所需要的存储空间。在插入元素时申请新的存储空间,删除元素释放其占有的存储空 间,插入和删除元素不必移动相邻元素。但其缺点是访问任何元素都得从链表头开始沿着链 进行,时间代价与链表的长度成正比。 (4)顺序表和链表的比较 顺序表是最简单的数据组织方法,因此大多数的程序设计语言都提供了数组这种机制来 实现顺序表。除具有易用、空间开销较小的特点之外,顺序表提供了对任意元素进行随机访 问的能力,适宜于诸如二分搜索及其快速排序等运算,是存储静态数据的理想选择。 除了适用于那些频繁插入或删除内部元素的线性表之外,链表适合于管理那些长度经常（1） 线性表的顺序存储中各运算的实现及其时间复杂性分析，尤其是插入和删除运 算； （2） 线性表的链式存储中各运算的实现时间和空间复杂性分析，尤其是插入和删除 运算。 5．授课提示 下面是线性表一章的重点和难点内容的讲授注意事项。 （1）线性表的基本概念 线性表是由称为元素的数据项组成的一种有限且有序的序列，这些元素也可称为结点 或表目。这些数据元素之间呈线性关系，且元素在不同情况下具有不同的含义。 授课时需要强调的是，虽然概念上并不反对线性表具有不同类型的数据元素，诸如广义 表，但简单线性表中约定所有元素都具有相同的或简单或复合结构的数据类型，并须事先给 出其类型定义。 此外，在讲授线性表的存储结构时，需要强调顺序表和链表这两类存储方式分别针对定 长的和变长的线性表而设立，有各自不同的适用场景和局限。 （2）线性表的顺序存储及实现 线性表的顺序存储结构，简称顺序表，是一种存储定长线性表的方法。其主要特点是 为线性表分配一块连续的存储空间，元素顺序地存储在这些地址连续的空间中，以“物理位 置相邻”来表示线性表中数据元素之间的关系。 顺序表是一种非常有用的数据结构，其优点体现在可以按位置对元素进行随机访问，但 其至少存在两方面的局限：(1) 改变顺序表的大小需要重新创建一个新的顺序表并把原有的 数据都复制过去；(2) 因为逻辑关系是通过物理位置的相邻来表示的，增删元素平均需要移 动一半的元素。 授课时在强调顺序表在访问元素时的便利性的同时，也须说明其缺点何在。需要重点介 绍如何在顺序表上实现元素的插入和删除运算，以及如何通过移动元素的数目来计算其时间 复杂性，最好辅以实例来说明。 （3）线性表的链式存储及实现 线性表的链式存储结构，简称链表，是用于存储变长线性表的存储方法。链接式存储结 构使用指针来表示元素之间的线性关系，利用线性表的前驱和后继关系将各个元素用指针链 接起来。 授课时须强调的是，链表可以看成一组既存储数据又存储相互连接信息的结点集合，由 由鉴于此，各结点就不必如顺序表那样存放在连续的存储空间中，而可以散放在存储空间的 各处，通过指针来按照线性表的前驱关系链接各结点。 还须强调的是，链表的特点是可以动态地申请内存空间，根据线性表元素的多少动态地 改变其所需要的存储空间。在插入元素时申请新的存储空间，删除元素释放其占有的存储空 间，插入和删除元素不必移动相邻元素。但其缺点是访问任何元素都得从链表头开始沿着链 进行，时间代价与链表的长度成正比。 （4）顺序表和链表的比较 顺序表是最简单的数据组织方法，因此大多数的程序设计语言都提供了数组这种机制来 实现顺序表。除具有易用、空间开销较小的特点之外，顺序表提供了对任意元素进行随机访 问的能力，适宜于诸如二分搜索及其快速排序等运算，是存储静态数据的理想选择。 除了适用于那些频繁插入或删除内部元素的线性表之外，链表适合于管理那些长度经常