在这一章我们向大家介绍了线性表的抽象数据类型的定义以及它的两种存储结构的实现。 线性表是 n(n≥0) 个数据元素的序列,通常写成 ( , , …, ) 因此线性表中除了第一个和最后一个元素之外都只有一个前驱和一个后继。线性表中每个元素都有自己确定的位置,即"位序",因此线性表也可以看成是由 n 个 (i,) 构成的集合。 n=0时的线性表称为"空表",它是线性表的一种特殊状态,因此在写线性表的操作算法时一定要考虑你的算法对空表的情况是否也正确。 顺序表是线性表的顺序存储结构的一种别称。它的特点是以"存储位置相邻"表示两个元素之间的前驱后继关系。因此,顺序表的优点是可以随机存取表中任意一个元素,其缺点是每作一次插入或删除操作时,平均来说必须移动表中一半元素。常应用于主要是为查询而很少作插入和删除操作,表长变化不大的线性表。 链表是线性表的链式存储结构的别称。它的特点是以"指针"指示后继元素,因此线性表的元素可以存储在存储器中任意一组存储单元中。它的优点是便于进行插入和删除操作,但不能进行随机存取,每个元素的存储位置都存放在其前驱元素的指针域中,为取得表中任意一个数据元素都必须从第一个数据元素起查询。由于它是一种动态分配的结构,结点的存储空间可以随用随取,并在删除结点时随时释放,以便系统资源更有效地被利用。这对编制大型软件非常重要,作为一个程序员在编制程序时必须养成这种习惯。 由于线性表是一种应用很广的数据结构,链表的操作又很灵活,因此在C++等面向对象的程序设计语言中都已为程序员提供了链表类,读者在使用时应该首先充分了解它的操作接口。在自己实现链表类时,正如课程中所述,应该为链表结构设置合适的数据成员和恰当的操作接口,以便使每个基本操作的时间复杂度在尽可能低的级别上。 | 【本章小结】 |