退队 A B C D E F+ 入队 ↑ front rear 图1-3列队的入队和退对运算 2、循环队列及其运算 在实际应用中，队列的顺序存储结构一般采用循环队列的形式。所谓循环队列，就是将 队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间。 在循环队列中，用队尾指针rear指向队列中的队尾元素，用排头指针front指向排头 元素的前一个位置。因此，从排头指针红oat指向的后一个位置直到队尾指针ar指向的 位置之间所有的元素封 为队列中的元素 可以将向量空间想象为一个首尾相接的圆环，如图1一4所示 rear front 图1-4循环队列 并称这种向量为循环向量，存储在其中的队列称为循环队列(Cireular Queue)。在 循环队列中进行出队、入队操作时，头尾指针仍要加1，朝前移动。只不过当头尾指针指向 向量上界(Queuesize-l)时，其加1操作的结果是指向向量的下界0。 由于入队时尾指针向前追赶头指针，出队时头指针向前追赶尾指针，故队空和队满时头 尾指针均相等。因此，我们无法通过front=rear来判断队列“空”还是“满”。 在实际使用循环队列时，为了能区分队列满还是队列空，通常还需增加一个标志S,S 值的定义如下：当s=0时表示队列空：当s=1时表示队列非空。 ()入队运算 入队运算是指在循环队列的队尾加入一个新元素。首先将队尾指针进一（即 rear=rear+1),并当rear=m+1时置rear=1;然后将新元素插入到队尾指针指向的位置。当 循环队列非空(s=1)且队尾指针等于队头指针时，说明循环队列已满，不能进行入队运算， 文种情况称为“上溢 (2②退队运算 退队运算是指在循环队列的队头位置退出一个元素并赋给指定的变量。首先将队头指针 一进一（即from=front+1),并当front=时1时，置front=1然后将排头指针指向的 元素赋给指定的变量。当循环队列为空(s=0)时，不能进行退队运算，这种情况称为“下
11 图 1-3 列队的入队和退对运算 2、 循环队列及其运算 在实际应用中，队列的顺序存储结构一般采用循环队列的形式。所谓循环队列，就是将 队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间。 在循环队列中，用队尾指针 rear 指向队列中的队尾元素，用排头指针 front 指向排头 元素的前一个位置。因此，从排头指针 front 指向的后一个位置直到队尾指针 rear 指向的 位置之间所有的元素均为队列中的元素。 可以将向量空间想象为一个首尾相接的圆环，如图 1-4 所示 图 1-4 循环队列 并称这种向量为循环向量，存储在其中的队列称为循环队列( Cireular Queue)。在 循环队列中进行出队、入队操作时，头尾指针仍要加 1，朝前移动。只不过当头尾指针指向 向量上界(Queuesize-l)时，其加 1 操作的结果是指向向量的下界 0。 由于入队时尾指针向前追赶头指针，出队时头指针向前追赶尾指针，故队空和队满时头 尾指针均相等。因此，我们无法通过 front=rear 来判断队列“空”还是“满”。 在实际使用循环队列时，为了能区分队列满还是队列空，通常还需增加一个标志 s,s 值的定义如下：当 s=0 时表示队列空；当 s=1 时表示队列非空。 (l)入队运算 入队运算是指在循环队列的队尾加入一个新元素。首先将队尾指针进一(即 rear=rear+1)，并当 rear=m+l 时置 rear=1；然后将新元素插入到队尾指针指向的位置。当 循环队列非空(s=l)且队尾指针等于队头指针时，说明循环队列已满，不能进行入队运算， 这种情况称为“上溢”。 (2) 退队运算 退队运算是指在循环队列的队头位置退出一个元素并赋给指定的变量。首先将队头指针 一进一(即 from=front +1)，并当 front = m+1 时，置 front=1 然后将排头指针指向的 元素赋给指定的变量。当循环队列为空(s =0)时，不能进行退队运算，这种情况称为“下 . rear front m 2 1 退队 A B C D E F 入队 front rear
溢” 1.5线性链表 1.5.1线性单链表的结构及其基本运算 1、什么是线性链表 (1)线性表顺序存储的缺点 ①在一般情况下，要在顺序存储的线性表中插入一个新元素或别除一个元素时，为了保 证插入或删除后的线性表仍然为顺序存储，则在插入或别除过程中需要移动大量的数据元 素。因此采用顺序存储结构进行插入或别除的运算效率很低： ②当为一个线性表分配顺序存储空间后，如果出现线性表的存储空间已满，但还需要捕 入新的元素时栈会发生“上溢”错误： ③计算机空间得不到充分利用，并且不便于对存储空间的动态分配。 (③)线性表链式的基本概念 在定义的链表中，若只含有一个指针域来存放下一个元素地址，称这样的链表为单链表 或线性结表 在链式存储方式中，要求每个结点由两部分组成：一部分用于存放数据元素值，称为数 据域：另一部分用于存放指针，称为指针域。其中指针用于指向该结点的前一个或后一个结 点（即前件或后件）。如图1-5所示。 存储序号 数据域 指针域 m 图1-5链式存储方式 2、线性单鞋表的存储结构 用一组任意的存储单元来依次存放线性表的结点，这组存储单元既可以是连续的，也可 以是不连续的，甚至是零散分布在内存中的任意位置上的。因此，链表中结点的逻辑次序和 物理次序不一定相同。为了能正确表示结点间的罗辑关系，在存储每个结点值的同时，还必 须存储指示其后件结点的地址（或位置）信息，这个信息称为指针(pointer)或链(Iink)。这 两部分组成了链表 的结点结构 链表正是通过每个结点的链域将线性表的个结点按其逻辑次序链接在一起。由于上述 链表的每一个结点只有一个链域，故将这种链表称为单链表(Single Linked)。 显然，单链表中每个结点的存储地址是存放在其前驱结点Nxt域中，而开始结点无前 驱，故应设头指针ED指向开始结点。同时，由于终端结点无后件，故终端结点的指针域
12 溢”。 1.5 线性链表 1.5.1 线性单链表的结构及其基本运算 1、 什么是线性链表 (l)线性表顺序存储的缺点 ①在一般情况下，要在顺序存储的线性表中插入一个新元素或删除一个元素时，为了保 证插入或删除后的线性表仍然为顺序存储，则在插入或删除过程中需要移动大量的数据元 素。因此采用顺序存储结构进行插入或删除的运算效率很低； ②当为一个线性表分配顺序存储空间后，如果出现线性表的存储空间已满，但还需要插 入新的元素时栈会发生“上溢”错误； ③计算机空间得不到充分利用，并且不便于对存储空间的动态分配。 (3) 线性表链式的基本概念 在定义的链表中，若只含有一个指针域来存放下一个元素地址，称这样的链表为单链表 或线性链表。 在链式存储方式中，要求每个结点由两部分组成：一部分用于存放数据元素值，称为数 据域；另一部分用于存放指针，称为指针域。其中指针用于指向该结点的前一个或后一个结 点(即前件或后件)。如图 1-5 所示。 图 1-5 链式存储方式 2、 线性单链表的存储结构 用一组任意的存储单元来依次存放线性表的结点，这组存储单元既可以是连续的，也可 以是不连续的，甚至是零散分布在内存中的任意位置上的。因此，链表中结点的逻辑次序和 物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必 须存储指示其后件结点的地址(或位置)信息，这个信息称为指针(pointer)或链(link)。这 两部分组成了链表中的结点结构， 链表正是通过每个结点的链域将线性表的 n 个结点按其逻辑次序链接在一起。由于上述 链表的每一个结点只有一个链域，故将这种链表称为单链表(Single Linked)。 显然，单链表中每个结点的存储地址是存放在其前驱结点 Next 域中，而开始结点无前 驱，故应设头指针 HEAD 指向开始结点。同时，由于终端结点无后件，故终端结点的指针域 . 存储序号 i m 2 1 . 数据域 指针域
为空，即NLL。如图1-6所示。 HEAD 数据1 数据2 数据n NULL 图1-6单链表 3、带链的栈与队列 ()栈也是线性表，也可以采用链式存储结构。在实际应用中，带链的栈可以用来 十算机存储空间中所有空闲的存储结点，这种带链的栈称为可利用栈 (2)队列也是线性表，也可以采用链式存储结构， 1.5.2线性链表的基本运算 线性链表的运算主要有以下几个： (1)在线性链表中包含指定元素的结点之前插入一个新元素： (2)在线性链表中删除包含指定元素的结点： (③)将两个线性链表书 要求合并成 个线性表 (4)将 一个线性链表按要求进行分解： (5)逆转线性链表： (6)复制线性链表： (7)线性链表的排序 (⑧)线性链表的查找 下面介绍 下线性列表的几个操作： 1、在线性链表中查找指定元素 在对线性链表进行插入或剧除的运算中，总是首先需要找到插入或删除的位置，这 就需要对线性链表进行扫描查找，在线性链表中寻找包含指定元素的前一个结点。 1访问结点 在线性链表中，即使知道被访问结点的序号a,也不能像顺序表中郑样直接按序号 而只能从链表的头指针出发 顺链域N©xt逐个结点往下搜素，直到搜索到第 个结点为止。因此，链表不是随机存取结构。 在链表中，查找是否有结点值等于给定值x的结点，若有的话，则返回首次找到的 其值为x的结点的存储位置：否则返回NL。查找过程从开始结点出发，顺着链表逐个将 结点的值和给定值x作比较。 2 性链 的插入 性链表的插入是指在链式存储结构下的线性链表中插入一个新元素。 插入运算是将值为X的新结点插入到表的第i个结点的位置上，即插入到与a 之间。因此，我们必须首先找到-，的存储位置p,然后生成一个数据域为x的新结点和， 并令结点p的指针域指向新结点，新结点的指针域指向结点 由线性链表的插入过程可以看出，由于插入的新结点取自于可利用栈，因此，只要 可利用栈不空，在线性链表插入时总能取到存储插入元素的新结点，不会发生 上溢”的情 况。而且，由于可利用栈是公用的，多个线性链表可以共享它，从而很方便地实现了存储空 间的动态分配。另外，线性链表在插入过程中不发生数据元素移动的现象，只要改变有关结 点的指针即可，从而提高了插入的效率。 3、多线性链表的除 线性链表的删除是指在链式存储结构下的线性链表中删除包含指定元素的结点。 3
13 为空，即 NULL。如图 1-6 所示。 图 1-6 单链表 3、 带链的栈与队列 (1) 栈也是线性表，也可以采用链式存储结构。在实际应用中，带链的栈可以用来 收集计算机存储空间中所有空闲的存储结点，这种带链的栈称为可利用栈 (2)队列也是线性表，也可以采用链式存储结构， 1.5.2 线性链表的基本运算 线性链表的运算主要有以下几个： (l)在线性链表中包含指定元素的结点之前插入一个新元素； (2)在线性链表中删除包含指定元素的结点； (3)将两个线性链表按要求合并成一个线性表； (4)将一个线性链表按要求进行分解； (5)逆转线性链表； (6)复制线性链表； (7)线性链表的排序； (8)线性链表的查找。 下面介绍一下线性列表的几个操作： 1、在线性链表中查找指定元素 在对线性链表进行插入或删除的运算中，总是首先需要找到插入或删除的位置，这 就需要对线性链表进行扫描查找，在线性链表中寻找包含指定元素的前一个结点。 在线性链表中，即使知道被访问结点的序号 a，也不能像顺序表中那样直接按序号 i 访问结点，而只能从链表的头指针出发，顺链域 Next 逐个结点往下搜索，直到搜索到第 i 个结点为止。因此，链表不是随机存取结构。 在链表中，查找是否有结点值等于给定值 x 的结点，若有的话，则返回首次找到的 其值为 x 的结点的存储位置；否则返回 NULL。查找过程从开始结点出发，顺着链表逐个将 结点的值和给定值 x 作比较。 2、线性链表的插入 线性链表的插入是指在链式存储结构下的线性链表中插入一个新元素。 插入运算是将值为 X 的新结点插入到表的第 i 个结点的位置上，即插入到 ai-1 与 ai 之间。因此，我们必须首先找到 ai-1 的存储位置 p，然后生成一个数据域为 x 的新结点*p， 并令结点 p 的指针域指向新结点，新结点的指针域指向结点 ai 。 由线性链表的插入过程可以看出，由于插入的新结点取自于可利用栈，因此，只要 可利用栈不空，在线性链表插入时总能取到存储插入元素的新结点，不会发生“上溢”的情 况。而且，由于可利用栈是公用的，多个线性链表可以共享它，从而很方便地实现了存储空 间的动态分配。另外，线性链表在插入过程中不发生数据元素移动的现象，只要改变有关结 点的指针即可，从而提高了插入的效率。 3、多线性链表的删除 线性链表的删除是指在链式存储结构下的线性链表中删除包含指定元素的结点。 HEAD 数据 1 数据 2 ``````` 数据 n NULL
删除运算是将表的第个结点刑去，因为在单链表中结点a的存储地址是在其直接 前趋结点a-的指针域Next中，所以我们必须首先找到a-的存储位置p。然后令p>水eX 指向：的直接后件结点，即把从链上摘下。最后释放结点a的空间 从线性链表的别除过程可以看出，从线性链表中别除一个元素后，不需要移动表中 的数据元素，只要改变被删除元素所在结点的前一个结点的指针域即可。另外，由于可利用 栈是用于收集计算机中所有的空闲结点，因此，当从线性链表中删除一个元素后，该元素的 存储结点就变为空闲，应将空闲结点送回到可利用栈。 1.5.3线性双向链表的结构及其基本运算 1、什么是双向链表 在单链表中，从某个结点出发可以直接找到它的直接后件，时间复杂度为0()，但无 法直接找到它的互接前件：在单循环链表中，从某个结点出发可以直接找到它的直接后件， 时间复杂度仍为0(1)，直接找到它的直接前件，时间复杂度为0()。有时，希望能快速找 到一个结占的直接前件，这时，可以在单链表中的结占中增加一个指针域指向它的直接前件 这样的链表，就称为双向链表（一个结点中含有两个指针）。如果每条链构成一个循环链表 则会得到双向循环链表 2、双向链表的基本运算 (I)插入：在EAD为头指针的双向链表中，在值为X的结点之前插入值为b的结点，插 入结点的指针变化。如图1-7所示。 TOP HEAD 一.子一x→.一0 (a)原来的可利用栈与线性涟表 TOP 一.0 HEAD ，.一0 (b)从可利用栈取得结点p,在线性链表中找到包含元素x的前一个结点q TOP b 0 HEAD .0 (C)p插入到g之后 图1-7插入云算 (2)删除：在以HEAD为头指针的双向链表中除值为X的结点
14 删除运算是将表的第 i 个结点删去。因为在单链表中结点 a 的存储地址是在其直接 前趋结点 ai-1 的指针域 Next 中，所以我们必须首先找到 ai-1 的存储位置 p。然后令 p->Next 指向 ai 的直接后件结点，即把 ai 从链上摘下。最后释放结点 a 的空间。 从线性链表的删除过程可以看出，从线性链表中删除一个元素后，不需要移动表中 的数据元素，只要改变被删除元素所在结点的前一个结点的指针域即可。另外，由于可利用 栈是用于收集计算机中所有的空闲结点，因此，当从线性链表中删除一个元素后，该元素的 存储结点就变为空闲，应将空闲结点送回到可利用栈。 1.5.3 线性双向链表的结构及其基本运算 1、什么是双向链表 在单链表中，从某个结点出发可以直接找到它的直接后件，时间复杂度为 O(1)，但无 法直接找到它的互接前件；在单循环链表中，从某个结点出发可以直接找到它的直接后件， 时间复杂度仍为 O(1)，直接找到它的直接前件，时间复杂度为 O(n)。有时，希望能快速找 到一个结点的直接前件，这时，可以在单链表中的结点中增加一个指针域指向它的直接前件， 这样的链表，就称为双向链表(一个结点中含有两个指针)。如果每条链构成一个循环链表， 则会得到双向循环链表 2、双向链表的基本运算 (l)插入：在 HEAD 为头指针的双向链表中，在值为 X 的结点之前插入值为 b 的结点，插 入结点的指针变化。如图 1-7 所示。 图 1-7 插入运算 (2)删除：在以 HEAD 为头指针的双向链表中删除值为 X 的结点。 TOP HEAD . . . TOP HEAD 0 . x 0 b 0 p (a)原来的可利用栈与线性涟表 . q . 0 (b)从可利用栈取得结点 p,在线性链表中找到包含元素 x 的前一个结点 q x TOP . b p 0 HEAD . q . x 0 (c) p 插入到 q 之后
1.5.4循环链表的结构及其基本运算 在前面所讨论的线性链表中，其插入与删除的运算虽然比较方便，但还存在一个问题， 在运算过程中对于空表和对第一个结点的处理必须单独考虑，使空表与非空表的运算不统 因此，我们可以考虑建立这样的链表，具有单链表的特征，但又不需要增加额外的存储 空间，仅对表的链接方式精做改变，使得对表的处 理更加方便灵活。从单链表可 个结点的指针域为L,表示单链表已经结束。如果将单链表最后一个结点的指针域改为 存放链表中头结点（或第一个结点）的地址，就使得整个链表构成一个环，又没有增加额外的 存储空间循环链表具有以下两个特点： (①)在循环链表中增加了一个表头结点，其数据域为任意或者根据需要来设置，指针域 指向线性表的第 元素的结点。循环链表的头指针指向表头结点 (②)循环链表中最后一个结点的指针域不是空，而是指向表头结点。即在循环链表中， 所有结点的指针构成了一个环状链。 在循环链表中，只要指出表中任何一个结点的位置，就可以从它出发访问到表中其他所 有的结点，而线性单链表做不到这一点。 由于在循环链表中设置了一个表头结点，因此，在任何情况下，循环链表中至少有一个 结点存在，从而使空表的运算统一。 1.6树与二叉树 1.6.1树的基本概念 树是一种简单的非线性结构。在树这种结构中，所有元素之间的关系具有明显的层次关 系。用图形表示树这种数据结构时，就象自然界中的倒长的树，这种结构就用“树”来命名。 如图1-8所示 K D AE 图1-8树的数据结构
15 1.5.4 循环链表的结构及其基本运算 单链表上的访问是一种顺序访问，从其中的某一个结点出发，可以找到它的直接后件， 但无法找到它的直接前件。 在前面所讨论的线性链表中，其插入与删除的运算虽然比较方便，但还存在一个问题， 在运算过程中对于空表和对第一个结点的处理必须单独考虑，使空表与非空表的运算不统 一。 因此，我们可以考虑建立这样的链表，具有单链表的特征，但又不需要增加额外的存储 空间，仅对表的链接方式稍做改变，使得对表的处理更加方便灵活。从单链表可知，最后一 个结点的指针域为 NULL，表示单链表已经结束。如果将单链表最后一个结点的指针域改为 存放链表中头结点(或第一个结点)的地址，就使得整个链表构成一个环，又没有增加额外的 存储空间循环链表具有以下两个特点： (1)在循环链表中增加了一个表头结点，其数据域为任意或者根据需要来设置，指针域 指向线性表的第一个元素的结点。循环链表的头指针指向表头结点； (2)循环链表中最后一个结点的指针域不是空，而是指向表头结点。即在循环链表中， 所有结点的指针构成了一个环状链。 在循环链表中，只要指出表中任何一个结点的位置，就可以从它出发访问到表中其他所 有的结点，而线性单链表做不到这一点。 由于在循环链表中设置了一个表头结点，因此，在任何情况下，循环链表中至少有一个 结点存在，从而使空表的运算统一。 1.6 树与二叉树 1.6.1 树的基本概念 树是一种简单的非线性结构。在树这种结构中，所有元素之间的关系具有明显的层次关 系。用图形表示树这种数据结构时，就象自然界中的倒长的树，这种结构就用“树”来命名。 如图 1-8 所示。 图 1-8 树的数据结构 R K P Q D B E N O T C H X W Z A L