数据结构与算法“线性表”教学设计 北京大学信息科学技术学院赵海燕 1.线性表在课程中的定位和前测知识点 作为构成“数据结构与算法”课程的基石,线性结构是应用最为广泛的一种数据结构 不仅成为很多应用直接选用的数据结构,也是构成其他复杂数据结构的基本单元。例如操作 系统的存储管理本质上就是利用线性表管理可利用空间,而散列方法则是把顺序表和链表结 合起来的一种数据结构 线性结构的基本特点是结构中的元素之间满足线性关系,按这个关系可以把所有元素排 成一个线性序列。线性表、栈和队列都属于线性结构,它们之间的主要区别在于实施于数据 元素上的操作有所不同。线性表一章主要介绍线性表的概念、存储表示、基本运算的实现以 及一些应用实例。 线性表是由若干数据元素组成的有限序列,常用的存储方式有顺序和链式两种 前测知识点要求如下,可以根据需要给学生补充: (1)概率的基本概念和计算; (2)指针的概念和运用 (3)动态存储分配的概念及其常用的CC++函数。 2.学习目标 (1)理解线性结构的基本概念; (2)熟练掌握线性表上的常用运算 (3)掌握线性表的顺序实现和链式实现,并能够分析各运算的顺序实现和链式实现 的复杂度; (4)了解顺序表和链表各自的优缺点和适用场景,并能够根据实际情况,进行合理 的选择 3.知识点和学时分配 理论授课2学时,建议安排实验4学时。 以下内容是本课程要求的基本教学内容,在授课中必须完全涵盖,各知识点建议授课时 间如下: 线性表的基本概念 20分钟 线性表的顺序存储及实现 40分钟 线性表的链式存储及实现 40分钟 顺序表和链表的比较 20分钟 此外,可视学生的状况和程度,适当补充与动态存储分配和指针的相关内容。 4.重点和难点 线性表的重点包括: (1)线性结构的概念及其特点 (2)线性表的顺序存储实现 (3)线性表的链式存储实现 其中,难点在于
数据结构与算法“线性表”教学设计 北京大学信息科学技术学院 赵海燕 1. 线性表在课程中的定位和前测知识点 作为构成“数据结构与算法”课程的基石，线性结构是应用最为广泛的一种数据结构。 不仅成为很多应用直接选用的数据结构，也是构成其他复杂数据结构的基本单元。例如操作 系统的存储管理本质上就是利用线性表管理可利用空间，而散列方法则是把顺序表和链表结 合起来的一种数据结构。 线性结构的基本特点是结构中的元素之间满足线性关系，按这个关系可以把所有元素排 成一个线性序列。线性表、栈和队列都属于线性结构，它们之间的主要区别在于实施于数据 元素上的操作有所不同。线性表一章主要介绍线性表的概念、存储表示、基本运算的实现以 及一些应用实例。 线性表是由若干数据元素组成的有限序列，常用的存储方式有顺序和链式两种。 前测知识点要求如下，可以根据需要给学生补充： （1） 概率的基本概念和计算； （2） 指针的概念和运用； （3） 动态存储分配的概念及其常用的 C/C++函数。 2．学习目标 （1） 理解线性结构的基本概念； （2） 熟练掌握线性表上的常用运算； （3） 掌握线性表的顺序实现和链式实现，并能够分析各运算的顺序实现和链式实现 的复杂度； （4） 了解顺序表和链表各自的优缺点和适用场景，并能够根据实际情况，进行合理 的选择。 3. 知识点和学时分配 理论授课 2 学时，建议安排实验 4 学时。 以下内容是本课程要求的基本教学内容，在授课中必须完全涵盖，各知识点建议授课时 间如下： 线性表的基本概念 20 分钟 线性表的顺序存储及实现 40 分钟 线性表的链式存储及实现 40 分钟 顺序表和链表的比较 20 分钟 此外，可视学生的状况和程度，适当补充与动态存储分配和指针的相关内容。 4．重点和难点 线性表的重点包括： （1） 线性结构的概念及其特点； （2） 线性表的顺序存储实现； （3） 线性表的链式存储实现。 其中，难点在于
(1)线性表的顺序存储中各运算的实现及其时间复杂性分析,尤其是插入和删除运 (2)线性表的链式存储中各运算的实现时间和空间复杂性分析,尤其是插入和删除 运算 5.授课提示 下面是线性表一章的重点和难点内容的讲授注意事项。 (1)线性表的基本概念 线性表是由称为元素的数据项组成的一种有限且有序的序列,这些元素也可称为结点 或表目。这些数据元素之间呈线性关系,且元素在不同情况下具有不同的含义 授课时需要强调的是,虽然概念上并不反对线性表具有不同类型的数据元素,诸如广义 表,但简单线性表中约定所有元素都具有相同的或简单或复合结构的数据类型,并须事先给 出其类型定义。 此外,在讲授线性表的存储结构时,需要强调顺序表和链表这两类存储方式分别针对定 长的和变长的线性表而设立,有各自不同的适用场景和局限 (2)线性表的顺序存储及实现 线性表的顺序存储结构,简称顺序表,是一种存储定长线性表的方法。其主要特点是 为线性表分配一块连续的存储空间,元素顺序地存储在这些地址连续的空间中,以“物理位 置相邻”来表示线性表中数据元素之间的关系。 顺序表是一种非常有用的数据结构,其优点体现在可以按位置对元素进行随机访问,但 其至少存在两方面的局限:(1)改变顺序表的大小需要重新创建一个新的顺序表并把原有的 数据都复制过去;(2)因为逻辑关系是通过物理位置的相邻来表示的,增删元素平均需要移 动一半的元素。 授课时在强调顺序表在访问元素时的便利性的同时,也须说明其缺点何在。需要重点介 绍如何在顺序表上实现元素的插入和删除运算,以及如何通过移动元素的数目来计算其时间 复杂性,最好辅以实例来说明。 (3)线性表的链式存储及实现 线性表的链式存储结构,简称链表,是用于存储变长线性表的存储方法。链接式存储结 构使用指针来表示元素之间的线性关系,利用线性表的前驱和后继关系将各个元素用指针链 接起来。 授课时须强调的是,链表可以看成一组既存储数据又存储相互连接信息的结点集合,由 由鉴于此,各结点就不必如顺序表那样存放在连续的存储空间中,而可以散放在存储空间的 各处,通过指针来按照线性表的前驱关系链接各结点。 还须强调的是,链表的特点是可以动态地申请内存空间,根据线性表元素的多少动态地 改变其所需要的存储空间。在插入元素时申请新的存储空间,删除元素释放其占有的存储空 间,插入和删除元素不必移动相邻元素。但其缺点是访问任何元素都得从链表头开始沿着链 进行,时间代价与链表的长度成正比。 (4)顺序表和链表的比较 顺序表是最简单的数据组织方法,因此大多数的程序设计语言都提供了数组这种机制来 实现顺序表。除具有易用、空间开销较小的特点之外,顺序表提供了对任意元素进行随机访 问的能力,适宜于诸如二分搜索及其快速排序等运算,是存储静态数据的理想选择。 除了适用于那些频繁插入或删除内部元素的线性表之外,链表适合于管理那些长度经常
（1） 线性表的顺序存储中各运算的实现及其时间复杂性分析，尤其是插入和删除运 算； （2） 线性表的链式存储中各运算的实现时间和空间复杂性分析，尤其是插入和删除 运算。 5．授课提示 下面是线性表一章的重点和难点内容的讲授注意事项。 （1）线性表的基本概念 线性表是由称为元素的数据项组成的一种有限且有序的序列，这些元素也可称为结点 或表目。这些数据元素之间呈线性关系，且元素在不同情况下具有不同的含义。 授课时需要强调的是，虽然概念上并不反对线性表具有不同类型的数据元素，诸如广义 表，但简单线性表中约定所有元素都具有相同的或简单或复合结构的数据类型，并须事先给 出其类型定义。 此外，在讲授线性表的存储结构时，需要强调顺序表和链表这两类存储方式分别针对定 长的和变长的线性表而设立，有各自不同的适用场景和局限。 （2）线性表的顺序存储及实现 线性表的顺序存储结构，简称顺序表，是一种存储定长线性表的方法。其主要特点是 为线性表分配一块连续的存储空间，元素顺序地存储在这些地址连续的空间中，以“物理位 置相邻”来表示线性表中数据元素之间的关系。 顺序表是一种非常有用的数据结构，其优点体现在可以按位置对元素进行随机访问，但 其至少存在两方面的局限：(1) 改变顺序表的大小需要重新创建一个新的顺序表并把原有的 数据都复制过去；(2) 因为逻辑关系是通过物理位置的相邻来表示的，增删元素平均需要移 动一半的元素。 授课时在强调顺序表在访问元素时的便利性的同时，也须说明其缺点何在。需要重点介 绍如何在顺序表上实现元素的插入和删除运算，以及如何通过移动元素的数目来计算其时间 复杂性，最好辅以实例来说明。 （3）线性表的链式存储及实现 线性表的链式存储结构，简称链表，是用于存储变长线性表的存储方法。链接式存储结 构使用指针来表示元素之间的线性关系，利用线性表的前驱和后继关系将各个元素用指针链 接起来。 授课时须强调的是，链表可以看成一组既存储数据又存储相互连接信息的结点集合，由 由鉴于此，各结点就不必如顺序表那样存放在连续的存储空间中，而可以散放在存储空间的 各处，通过指针来按照线性表的前驱关系链接各结点。 还须强调的是，链表的特点是可以动态地申请内存空间，根据线性表元素的多少动态地 改变其所需要的存储空间。在插入元素时申请新的存储空间，删除元素释放其占有的存储空 间，插入和删除元素不必移动相邻元素。但其缺点是访问任何元素都得从链表头开始沿着链 进行，时间代价与链表的长度成正比。 （4）顺序表和链表的比较 顺序表是最简单的数据组织方法，因此大多数的程序设计语言都提供了数组这种机制来 实现顺序表。除具有易用、空间开销较小的特点之外，顺序表提供了对任意元素进行随机访 问的能力，适宜于诸如二分搜索及其快速排序等运算，是存储静态数据的理想选择。 除了适用于那些频繁插入或删除内部元素的线性表之外，链表适合于管理那些长度经常
波动或事先无法确定长度的线性表。 授课时须强调线性表应用的广泛性。建议多举后续课程上将要学到的内容为例。例如, 存储管理本质上就是利用线性表管理可利用空间:程序设计语言编译器中的符号表也是典型 的线性表:散列方法则是把顺序表和链表结合起来的一种数据结构。 6.课后练习和实习 作为教学的重要一环,课后练习和上机实习帮助学生巩固课堂所学理论知识,训练学生 创新思维能力训练、工程实践能力。 线性表部分可以安排3-4道书面作业,也可采用 ACM/ICPC程序竞赛题库POJ系统安 排1-2道的实习题来巩固线性表部分的知识。例如,下面的ACM题目 http://acm.pku.edu.cn/judgeoNline/problem?Id=1012(Joseph) htt/ acm.pku.edu. cn/Judge Online/problem?id=1153(内存分配) 7.教学案例 以单链表删除元素及其复杂性分析为例 下面的算法给出了删除单链表第i个结点的代码,相应的操作过程参见下面的图示 bool InkList: delete(int,∥假定线性表的元素类型为T template ∥p是第i个结点的前驱 if(p= NULL)i ∥待删结点不存在,即给定的i大于当前链中元素个数 coutnext =q->next, return true “时 a)删除前指针情况 b)删除后指针情况 授课时根据情况可能需要补充动态存储管理的问题。删除单链表中的结点,可以使用 delete命令释放被删结点所占用的空间,否则这些占用空间会变成存储空间中无法利用的垃 圾,影响随后的再使用。 delete是C++程序语言为动态存储管理提供的两个重要命令,与C 语言标准函数库中提供的free函数具有同样的功能。 授课时上面的图示最好改用动画为好。此外,需要强调的是在链表的位置i进行删除操 作时,需要先定位到位置i-1的结点,这也是某些应用中需要在抽象数据类型中增加一个表 示当前位置的成员的原因,具体到用单链表方式实现时,通常保持当前位置的前一个指针以 方便操作。否则在插入和删除前均需一个时间代价为O)的定位操作。 8.总结
波动或事先无法确定长度的线性表。 授课时须强调线性表应用的广泛性。建议多举后续课程上将要学到的内容为例。例如， 存储管理本质上就是利用线性表管理可利用空间；程序设计语言编译器中的符号表也是典型 的线性表；散列方法则是把顺序表和链表结合起来的一种数据结构。 6．课后练习和实习 作为教学的重要一环，课后练习和上机实习帮助学生巩固课堂所学理论知识，训练学生 创新思维能力训练、工程实践能力。 线性表部分可以安排 3-4 道书面作业，也可采用 ACM/ICPC 程序竞赛题库 POJ 系统安 排 1-2 道的实习题来巩固线性表部分的知识。例如，下面的 ACM 题目： http://acm.pku.edu.cn/JudgeOnline/problem?id=1012 （Joseph） http://acm.pku.edu.cn/JudgeOnline/problem?id=1153（内存分配） 7．教学案例 以单链表删除元素及其复杂性分析为例。 下面的算法给出了删除单链表第 i 个结点的代码，相应的操作过程参见下面的图示。 template // 假定线性表的元素类型为 T bool lnkList:: delete (int i) { Link *p, *q; p = setPos(i-1); // p 是第 i 个结点的前驱 if (p == NULL ) { // 待删结点不存在，即给定的 i 大于当前链中元素个数 cout next; // q 是真正待删结点 if (q == tail) // 待删结点为尾结点，则修改尾指针 tail = p; if (q != NULL) { // 删除结点 q 并修改链指针 p->next = q->next; delete q; } return true; } a) 删除前指针情况 b) 删除后指针情况 授课时根据情况可能需要补充动态存储管理的问题。删除单链表中的结点，可以使用 delete 命令释放被删结点所占用的空间，否则这些占用空间会变成存储空间中无法利用的垃 圾，影响随后的再使用。delete 是 C++程序语言为动态存储管理提供的两个重要命令，与 C 语言标准函数库中提供的 free 函数具有同样的功能。 授课时上面的图示最好改用动画为好。此外，需要强调的是在链表的位置 i 进行删除操 作时，需要先定位到位置 i-1 的结点，这也是某些应用中需要在抽象数据类型中增加一个表 示当前位置的成员的原因，具体到用单链表方式实现时，通常保持当前位置的前一个指针以 方便操作。否则在插入和删除前均需一个时间代价为 O(n)的定位操作。 8．总结
线性表是最基本的数据结构,是帮助学生开启数据结构与算法学习的钥匙,尽管简单却 很重要的一章。 除了上述教学注意事项之外。还需要提醒学生注意实际应用,需要根据应用的具体情况, 选择顺序表或链表。 参考文献 1.张铭,王腾蛟,赵海燕,《数据结构与算法》,高等教育出版社,2008年6月。——普 通高等教育“十一五”国家级规划教材 2.张铭、赵海燕、王腾蛟、宋国杰、高军,北京大学“数据结构与算法”教学设计,《计 算机教育》2008第20期。获得“英特尔杯2008年全国计算机教育优秀论文评比”一等 奖 3.北京大学《数据结构与算法》精品课程网站(2008年北京市“精品课程”暨国家“精品 课程),http://www.jpk.pkueducn/pkujpk/course/sjjg/
线性表是最基本的数据结构，是帮助学生开启数据结构与算法学习的钥匙，尽管简单却 很重要的一章。 除了上述教学注意事项之外。还需要提醒学生注意实际应用，需要根据应用的具体情况， 选择顺序表或链表。 参考文献： 1. 张铭，王腾蛟，赵海燕，《数据结构与算法》，高等教育出版社，2008 年 6 月。——普 通高等教育“十一五”国家级规划教材。 2. 张铭、赵海燕、王腾蛟、宋国杰 、高军，北京大学“数据结构与算法”教学设计，《计 算机教育》2008 第 20 期。获得“英特尔杯 2008 年全国计算机教育优秀论文评比”一等 奖。 3. 北京大学《数据结构与算法》精品课程网站（2008 年北京市“精品课程”暨国家“精品 课程”）， http://www.jpk.pku.edu.cn/pkujpk/course/sjjg/