第1章数据结构与算法 但是,线性表的顺序存储结构在某些情况下就显得不那么方便,运算效率不那么高。实阿 上,线性表的顺序存储结构存在以下几方面的缺点: ①在一般情况下,要在顺序存储的线性表中插入一个新元素或删除一个元素时,为了保证 插入或删除后的线性表仍然为顺序存储,则在插入或删除过程中需要移动大量的数据元素。在 平均情况下,为了在顺序存储的线性表中插入或删除一个元素,需要移动线性表中约一半的元 素;在最坏情况下,则需要移动线性表中所有的元素。因此,对于大的线性表,特别是元素的 插入或删除很频繁的情况下,采用顺序存储结构是很不方便的,插入与删除运算的效率都很低。 ②当为一个线性表分配顺序存储空间后,如果出现线性表的存储空间已满,但还需要插入 新的元素时,就会发生“上溢”错误。在这种情况下,如果在原线性表的存储空间后找不到与 连续的可用空间,则会导致运算的失败或中断。显然,这种情况的出现对运算是很不利的 也就是说,在顺序存储结构下,线性表的存储空间不便于扩充。 ③在实际应用中,往往是同时有多个线性表共享计算机的存储空间,例如,在一个处理中, 可能要用到若干个线性表(包括栈与队列)。在这种情况下,存储空间的分配将是一个难题。如 果将存储空间平均分配给各线性表,则有可能造成有的线性表的空间不够用,而有的线性表的 空间根本用不着或用不满,这就使得在有的线性表空间无用而处于空闲的情况下,另外一些线 性表的操作由于“上溢”而无法进行。这种情况实际上是计算机的存储空间得不到充分利用。 如果多个线性表共享存储空间,对每一个线性表的存储空间进行动态分配,则为了保证每一 线性表的存储空间连续且顺序分配,会导致在对某个线性表进行动态分配存储空间时,必须要 移动其他线性表中的数据元素。这就是说,线性表的顺序存储结构不便于对存储空间的动态分 由于线性表的顺序存储结构存在以上这些缺点,因此,对于大的线性表,特别是元素变动 频繁的大线性表不宜采用顺序存储结构,而是采用下面要介绍的链式存储结构。 假设数据结构中的每一个数据结点对应于一个存储单元,这种存储单元称为存储结点,简 称结点。 在链式存储方式中,要求每个结点由两部分组成:一部分用于存放数据元素值,称为数据 域;另一部分用于存放指针,称为指针域。其中指针用于指向该结点的前一个或后一个结点(即 前件或后件)。 在链式存储结构中,存储数据结构的存储空间可以不连续,各数据结点的存储顺序与数据 元素之间的逻辑关系可以不一致,而数据元素之间的逻辑关系是由指针域来确定的 链式存储方式既可用于表示线性结构,也可用于表示非线性结构。在用链式结构表示较复 杂的非线性结构时,其指针域的个数要多一些。 1线性链表 线性表的链式存储结构称为线性链表。 为了适应线性表的链式存储结构,计算机存储空间被划分为一个一个小块,每一小块占若 干字节,通常称这些小块为存储结点 为了存储线性表中的每一个元素,一方面要存储数据元素的值,另一方面要存储各数据元 素之间的前后件关系。为此目的,将存储空间中的每一个存储结点分为两部分:一部分用于存 储数据元素的值,称为数据域;另一部分用于存放下一个数据元素的存储序号(即存储结点的地 址),即指向后件结点,称为指针域。由此可知,在线性链表中,存储空间的结构如图1.15所 在线性链表中,用一个专门的指针HEAD指向线性链表中第一个数据元素的结点(即存放
第 1 章 数据结构与算法 23 但是，线性表的顺序存储结构在某些情况下就显得不那么方便，运算效率不那么高。实际 上，线性表的顺序存储结构存在以下几方面的缺点： ①在一般情况下，要在顺序存储的线性表中插入一个新元素或删除一个元素时，为了保证 插入或删除后的线性表仍然为顺序存储，则在插入或删除过程中需要移动大量的数据元素。在 平均情况下，为了在顺序存储的线性表中插入或删除一个元素，需要移动线性表中约一半的元 素；在最坏情况下，则需要移动线性表中所有的元素。因此，对于大的线性表，特别是元素的 插入或删除很频繁的情况下，采用顺序存储结构是很不方便的，插入与删除运算的效率都很低。 ②当为一个线性表分配顺序存储空间后，如果出现线性表的存储空间已满，但还需要插入 新的元素时，就会发生“上溢”错误。在这种情况下，如果在原线性表的存储空间后找不到与 之连续的可用空间，则会导致运算的失败或中断。显然，这种情况的出现对运算是很不利的。 也就是说，在顺序存储结构下，线性表的存储空间不便于扩充。 ③在实际应用中，往往是同时有多个线性表共享计算机的存储空间，例如，在一个处理中， 可能要用到若干个线性表(包括栈与队列)。在这种情况下，存储空间的分配将是一个难题。如 果将存储空间平均分配给各线性表，则有可能造成有的线性表的空间不够用，而有的线性表的 空间根本用不着或用不满，这就使得在有的线性表空间无用而处于空闲的情况下，另外一些线 性表的操作由于“上溢”而无法进行。这种情况实际上是计算机的存储空间得不到充分利用。 如果多个线性表共享存储空间，对每一个线性表的存储空间进行动态分配，则为了保证每一个 线性表的存储空间连续且顺序分配，会导致在对某个线性表进行动态分配存储空间时，必须要 移动其他线性表中的数据元素。这就是说，线性表的顺序存储结构不便于对存储空间的动态分 配。 由于线性表的顺序存储结构存在以上这些缺点，因此，对于大的线性表，特别是元素变动 频繁的大线性表不宜采用顺序存储结构，而是采用下面要介绍的链式存储结构。 假设数据结构中的每一个数据结点对应于一个存储单元，这种存储单元称为存储结点，简 称结点。 在链式存储方式中，要求每个结点由两部分组成：一部分用于存放数据元素值，称为数据 域；另一部分用于存放指针，称为指针域。其中指针用于指向该结点的前一个或后一个结点(即 前件或后件)。 在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据 元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。 链式存储方式既可用于表示线性结构，也可用于表示非线性结构。在用链式结构表示较复 杂的非线性结构时，其指针域的个数要多一些。 1.线性链表 线性表的链式存储结构称为线性链表。 为了适应线性表的链式存储结构，计算机存储空间被划分为一个一个小块，每一小块占若 干字节，通常称这些小块为存储结点。 为了存储线性表中的每一个元素，一方面要存储数据元素的值，另一方面要存储各数据元 素之间的前后件关系。为此目的，将存储空间中的每一个存储结点分为两部分：一部分用于存 储数据元素的值，称为数据域；另一部分用于存放下一个数据元素的存储序号(即存储结点的地 址)，即指向后件结点，称为指针域。由此可知，在线性链表中，存储空间的结构如图 1.15 所 示。 在线性链表中，用一个专门的指针 HEAD 指向线性链表中第一个数据元素的结点(即存放
第1章数据结构与算法 线性表中第一个数据元素的存储结点的序号)。线性表中最后一个元素没有后件,因此,线性链 表中最后一个结点的指针域为空(用NULL或0表示),表示链表终止。线性链表的逻辑结构如 图1.17所示 线性链表中存储结点的结构如图1.16所示。 存储序号 数据域 指针域 存储序号数据域 NEXT 图1.15线性链表的存储空间 图1.16线性链表的一个存储结点 HEAD 数 心数据2 →…→数据nM 图1.17线性链表的逻辑结构 下面举一个例子来说明线性链表的存储结构。 设线性表为a1,a2,a3,a4,as),存储空间具有10个存储结点,该线性表在存储空间中的 存储情况如图1.18(a)所示。为了直观地表示该线性链表中各元素之间的前后件关系,还可以用 如图1.18b)所示的逻辑状态来表示,其中每一个结点上面的数字表示该结点的存储序号(简称结 neXT(i) HEAD 2 3456789 5 (a)线性链表的物理状态 HEAD→a (b)线性链表的逻辑状 图1.18线性链表例 一般来说,在线性表的链式存储结构中,各数据结点的存储序号是不连续的,并且各结点 在存储空间中的位置关系与逻辑关系也不一致。在线性链表中,各数据元素之间的前后件关系 是由各结点的指针域来指示的,指向线性表中第一个结点的指针HEAD称为头指针,当 HEAD=NULL(或0时称为空表 对于线性链表,可以从头指针开始,沿各结点的指针扫描到链表中的所有结点。下面的算 法是从头指针开始,依次输出各结点值
第 1 章 数据结构与算法 24 线性表中第一个数据元素的存储结点的序号)。线性表中最后一个元素没有后件，因此，线性链 表中最后一个结点的指针域为空(用 NULL 或 0 表示)，表示链表终止。线性链表的逻辑结构如 图 1.17 所示。 线性链表中存储结点的结构如图 1.16 所示。 数据域 指针域 1 存储序号 2 ┆ i ┆ m 图1.15 线性链表的存储空间 V(i) NEXT(i) 数据域 指针域 i 存储序号 图1.16 线性链表的一个存储结点 HEAD 数据1 数据2 … 数据n NULL 图1.17 线性链表的逻辑结构 下面举一个例子来说明线性链表的存储结构。 设线性表为(a1，a2，a3，a4，a5)，存储空间具有 10 个存储结点，该线性表在存储空间中的 存储情况如图 1.18(a)所示。为了直观地表示该线性链表中各元素之间的前后件关系，还可以用 如图 1.18(b)所示的逻辑状态来表示，其中每一个结点上面的数字表示该结点的存储序号(简称结 点号)。 a2 9 a1 1 a4 10 V(i) NEXT(i) 1 i 2 3 4 5 图1.18 线性链表例 a3 5 a5 0 6 7 8 9 10 HEAD 3 (a) 线性链表的物理状态 HEAD a1 a2 a3 a4 a5 0 3 1 9 5 10 (b) 线性链表的逻辑状态 一般来说，在线性表的链式存储结构中，各数据结点的存储序号是不连续的，并且各结点 在存储空间中的位置关系与逻辑关系也不一致。在线性链表中，各数据元素之间的前后件关系 是由各结点的指针域来指示的，指向线性表中第一个结点的指针 HEAD 称为头指针，当 HEAD=NULL(或 0)时称为空表。 对于线性链表，可以从头指针开始，沿各结点的指针扫描到链表中的所有结点。下面的算 法是从头指针开始，依次输出各结点值
第1章数据结构与算法 上面讨论的线性链表又称为线性单链表。在这种链表中,每一个结点只有一个指针域,由 这个指针只能找到后件结点,但不能找到前件结点。因此,在这种线性链表中,只能顺指针向 链尾方向进行扫描,这对于某些问题的处理会带来不便,因为在这种链接方式下,由某一个结 点出发,只能找到它的后件,而为了找出它的前件,必须从头指针开始重新寻找 为了弥补线性单链表的这个缺点,在某些应用中,对线性链表中的每个结点设置两个指针 个称为左指针Link),用以指向其前件结点:另一个称为右指针( Rlink),用以指向其后件结 点。这样的线性链幕称为双向链表,其逻辑状态如图1.19所示 HEAD -斗- 图1.19双向链表示意图 2带链的栈 栈也是线性表,也可以采用链式存储结构。图1.20是栈在链式存储时的逻辑状态示意图。 在实际应用中,带链的栈可以用来收集计算机存储空间中所有空闲的存储结点,这种带链 的栈称为可利用栈。由于可利用栈链接了计算机存储空间中所有的空闲结点,因此,当计算机 系统或用户程序需要存储结点时,就可以从中取出栈项结点,如图1.21(b)所示:当计算机系统 或用户程序释放一个存储结点(该元素从表中删除)时,则要将该结点放回到可利用栈的栈顶 如图1.21(a)所示。由此可知,计算机中的所有可利用空间都可以以结点为单位链接在可利用栈 中。随着其他线性链表中结点的插入与删除,可利用栈处于动态变化之中,即可利用栈经常要 进行退栈与入栈操作。 彐→…a0 图1.20带链的栈 p (a)将结点p送回可利用栈 (b)在从可利用栈取得一个结点p 图1.21可利用栈及其运算 3带链的队列 与栈类似,队列也是线性表,也可以采用链式存储结构。图1.2a)是队列在链式存储时的 逻辑状态示意图。图1.2(b)是将新结点p插入队列的示意图。图122c)是将排头结点p退出队 列的示意图
第 1 章 数据结构与算法 25 上面讨论的线性链表又称为线性单链表。在这种链表中，每一个结点只有一个指针域，由 这个指针只能找到后件结点，但不能找到前件结点。因此，在这种线性链表中，只能顺指针向 链尾方向进行扫描，这对于某些问题的处理会带来不便，因为在这种链接方式下，由某一个结 点出发，只能找到它的后件，而为了找出它的前件，必须从头指针开始重新寻找。 为了弥补线性单链表的这个缺点，在某些应用中，对线性链表中的每个结点设置两个指针， 一个称为左指针(Llink)，用以指向其前件结点；另一个称为右指针(Rlink)，用以指向其后件结 点。这样的线性链幕称为双向链表，其逻辑状态如图 1.19 所示。 2.带链的栈 栈也是线性表，也可以采用链式存储结构。图 1.20 是栈在链式存储时的逻辑状态示意图。 在实际应用中，带链的栈可以用来收集计算机存储空间中所有空闲的存储结点，这种带链 的栈称为可利用栈。由于可利用栈链接了计算机存储空间中所有的空闲结点，因此，当计算机 系统或用户程序需要存储结点时，就可以从中取出栈项结点，如图 1.21(b)所示；当计算机系统 或用户程序释放一个存储结点(该元素从表中删除)时，则要将该结点放回到可利用栈的栈顶， 如图 1.21(a)所示。由此可知，计算机中的所有可利用空间都可以以结点为单位链接在可利用栈 中。随着其他线性链表中结点的插入与删除，可利用栈处于动态变化之中，即可利用栈经常要 进行退栈与入栈操作。 a n a n-1 a1 Top … 0 图1.20 带链的栈 0 Top … 图1.21 可利用栈及其运算 an (a) 将结点p送回可利用栈 P … 0 (b) 在从可利用栈取得一个结点p P Top 3.带链的队列 与栈类似，队列也是线性表，也可以采用链式存储结构。图 1.22(a)是队列在链式存储时的 逻辑状态示意图。图 1.22(b)是将新结点 p 插入队列的示意图。图 1.22(c)是将排头结点 p 退出队 列的示意图。 0 0 图 1.19 双向链表示意图 HEAD
第1章数据结构与算法 (a)带链的队列 →“+ front (b)在带链的队列中插入一个新结点 front rear (c)在带链的队列中删除一个结点 图1.22带链的队列及其运算 152线性链表的基本运算 线性链表的运算主要有以下几个 ①在线性链表中包含指定元素的结点之前插入一个新元素 ②在线性链表中删除包含指定元素的结点 ③将两个线性链表按要求合并成一个线性链表 ④将一个线性链表按要求进行分解 ⑤逆转线性链表 ⑥复制线性链表 ⑦线性链表的排序 ⑧线性链表的查找。 本小节主要讨论线性链表的插入与删除 1在线性链表中查找指定元素 在对线性链表进行插入或删除的运算中,总是首先需要找到插入或删除的位置,这就需要 对线性链表进行扫描查找,在线性链表中寻找包含指定元素值的前一个结点。当找到包含指定 元素的前一个结点后,就可以在该结点后插入新结点或删除该结点后的一个结点 在非空线性链表中寻找包含指定元素值x的前一个结点p的基本方法如下: 从头指针指向的结点开始往后沿指针进行扫描,直到后面已没有结点或下一个结点的数据 域为x为止。因此,由这种方法找到的结点p有两种可能:当线性链表中存在包含元素x的结 点时,则找到的p为第一次遇到的包含元素x的前一个结点序号;当线性链表中不存在包含元 素x的结点时,则找到的p为线性链表中的最后一个结点号 2线性链表的插入 线性链表的插入是指在链式存储结构下的线性表中插入一个新元素。 为了要在线性链表中插入一个新元素,首先要给该元素分配一个新结点,以便用于存储该 元素的值。新结点可以从可利用栈中取得。然后将存放新元素值的结点链接到线性链表中指定 的位置。 假设可利用栈与线性链表如图123(a)所示。现在要在线性链表中包含元素x的结点之前插
第 1 章 数据结构与算法 26 a1 a2 an 0 front … 图1.22 带链的队列及其运算 rear a1 a2 an front … rear (a) 带链的队列 p an 0 p (b) 在带链的队列中插入一个新结点 a1 a2 an 0 front … rear (c) 在带链的队列中删除一个结点 p 1.5.2 线性链表的基本运算 线性链表的运算主要有以下几个： ①在线性链表中包含指定元素的结点之前插入一个新元素。 ②在线性链表中删除包含指定元素的结点。 ③将两个线性链表按要求合并成一个线性链表。 ④将一个线性链表按要求进行分解。 ⑤逆转线性链表。 ⑥复制线性链表。 ⑦线性链表的排序。 ⑧线性链表的查找。 本小节主要讨论线性链表的插入与删除。 1.在线性链表中查找指定元素 在对线性链表进行插入或删除的运算中，总是首先需要找到插入或删除的位置，这就需要 对线性链表进行扫描查找，在线性链表中寻找包含指定元素值的前一个结点。当找到包含指定 元素的前一个结点后，就可以在该结点后插入新结点或删除该结点后的一个结点。 在非空线性链表中寻找包含指定元素值 x 的前一个结点 p 的基本方法如下： 从头指针指向的结点开始往后沿指针进行扫描，直到后面已没有结点或下一个结点的数据 域为 x 为止。因此，由这种方法找到的结点 p 有两种可能：当线性链表中存在包含元素 x 的结 点时，则找到的 p 为第一次遇到的包含元素 x 的前一个结点序号；当线性链表中不存在包含元 素 x 的结点时，则找到的 p 为线性链表中的最后一个结点号。 2.线性链表的插入 线性链表的插入是指在链式存储结构下的线性表中插入一个新元素。 为了要在线性链表中插入一个新元素，首先要给该元素分配一个新结点，以便用于存储该 元素的值。新结点可以从可利用栈中取得。然后将存放新元素值的结点链接到线性链表中指定 的位置。 假设可利用栈与线性链表如图 1.23(a)所示。现在要在线性链表中包含元素 x 的结点之前插
第1章数据结构与算法 入一个新元素b。其插入过程如下: (1)从可利用栈取得一个结点,设该结点号为p(即取得结点的存储序号存放在变量p中), 并置结点p的数据域为插入的元素值b。经过这一步后,可利用栈的状态如图1.23(b)所示 (2)在线性链表中寻找包含元素x的前一个结点,设该结点的存储序号为q。线性链表如图 1.23(b所示 (3)最后将结点p插入到结点q之后。为了实现这一步,只要改变以下两个结点的指针域内 ①使结点p指向包含元素x的结点(即结点q的后件结点 ②使结点q的指针域内容改为指向结点p 这一步的结果如图1.23(c)所示。此时插入就完成 TOP HEAD (a)原来的可利用栈与线性链表 HEAD b)从可利用栈取得结点p,在线性链表中找到包括元素x的前一个结点q 工子→ 0 HEAD (c)p插入到q之后 图1.23线性链表的插入 由线性链表的插入过程可以看出,由于插入的新结点取自于可利用栈,因此,只要可利用 栈不空,在线性链表插入时总能取到存储插入元素的新结点,不会发生“上溢”的情况。而且, 由于可利用栈是公用的,多个线性链表可以共享它,从而很方便地实现了存储空间的动态分配 另外,线性链表在插入过程中不发生数据元素移动的现象,只需改变有关结点的指针即可,从 而提高了插入的效率 3线性链表的删除 线性链表的删除是指在链式存储结构下的线性表中删除包含指定元素的结点。 为了在线性链表中删除包含指定元素的结点,首先要在线性链表中找到这个结点,然后将 要删除结点放回到可利用栈 假设可利用栈与线性链表如图1.24(a)所示。现在要在线性链表中删除包含元素x的结点 其删除过程如下 (1)在线性链表中寻找包含元素x的前一个结点,设该结点序号为q (2)将结点q后的结点p从线性链表中删除,即让结点q的指针指向包含元素x的结点p的 指针指向的结点
第 1 章 数据结构与算法 27 入一个新元素 b。其插入过程如下： (1)从可利用栈取得一个结点，设该结点号为 p(即取得结点的存储序号存放在变量 p 中)， 并置结点 p 的数据域为插入的元素值 b。经过这一步后，可利用栈的状态如图 1.23(b)所示。 (2)在线性链表中寻找包含元素 x 的前一个结点，设该结点的存储序号为 q。线性链表如图 1.23(b)所示。 (3)最后将结点 p 插入到结点 q 之后。为了实现这一步，只要改变以下两个结点的指针域内 容： ①使结点 p 指向包含元素 x 的结点(即结点 q 的后件结点)。 ②使结点 q 的指针域内容改为指向结点 p。 这一步的结果如图 1.23(c)所示。此时插入就完成。 图1.23 线性链表的插入 HEAD x 0 (a) 原来的可利用栈与线性链表 TOP … 0 … … HEAD x 0 TOP b … 0 … … p q (b) 从可利用栈取得结点p，在线性链表中找到包括元素x的前一个结点q HEAD x 0 TOP b … 0 … … p q (c) p插入到q之后 由线性链表的插入过程可以看出，由于插入的新结点取自于可利用栈，因此，只要可利用 栈不空，在线性链表插入时总能取到存储插入元素的新结点，不会发生“上溢”的情况。而且， 由于可利用栈是公用的，多个线性链表可以共享它，从而很方便地实现了存储空间的动态分配。 另外，线性链表在插入过程中不发生数据元素移动的现象，只需改变有关结点的指针即可，从 而提高了插入的效率。 3.线性链表的删除 线性链表的删除是指在链式存储结构下的线性表中删除包含指定元素的结点。 为了在线性链表中删除包含指定元素的结点，首先要在线性链表中找到这个结点，然后将 要删除结点放回到可利用栈。 假设可利用栈与线性链表如图 1.24(a)所示。现在要在线性链表中删除包含元素 x 的结点， 其删除过程如下： (1)在线性链表中寻找包含元素 x 的前一个结点，设该结点序号为 q。 (2)将结点 q 后的结点 p 从线性链表中删除，即让结点 q 的指针指向包含元素 x 的结点 p 的 指针指向的结点