第1章数据结构与算法 除线性表中的第1个元素(即删除元素29)。其删除过程如下: 从第2个元素开始直到最后一个元素,将其中的每一个元素均依次往前移动一个位置。此 时,线性表的长度变成了7,如图18(b)所示 如果再要删除线性表中的第6个元素,则采用类似的方法:将第7个元素往前移动一个位 置。此时,线性表的长度变成了6,如图1.8(c)所示。 V(1:10) V(1:1 V(1:10) 18 56 47 (a)长度为8的线性表(b)删除元素29后的线性表(c)删除元素31后的线性表 图1.8线性表在顺序存储结构下的删除 一般来说,设长度为n的线性表为 a 现要删除第i个元素,删除后得到长度为n-1的线性表为 则删除前后的两线性表中的元素满足如下关系: 1≤j≤i-1 n-1 在一般情况下,要删除第i(1≤i≤n)个元素时,则要从第计1个元素开始,直到第n个元素 之间共n-i个元素依次向前移动一个位置。删除结束后,线性表的长度就减小了1。 显然,在线性表采用顺序存储结构时,如果删除运算在线性表的末尾进行,即删除第n个 元素,则不需要移动表中的元素:如果要删除线性表中的第1个元素,则需要移动表中所有的 元素。在一般情况下,如果要删除第i1≤i≤n个元素,则原来第i个元素之后的所有元素都必 须依次往前移动一个位置。在平均情况下,要在线性表中删除一个元素,需要移动表中一半的 元素。因此,在线性表顺序存储的情况下,要删除一个元素,其效率也是很低的,特别是在线 性表比较大的情况下更为突出,由于数据元素的移动而消耗较多的处理时间。 由线性表在顺序存储结构下的插入与删除运算可以看出,线性表的顺序存储结构对于小线 性表或者其中元素不常变动的线性表来说是合适的,因为顺序存储的结构比较简单。但这种顺 序存储的方式对于元素经常需要变动的大线性表就不太合适了,因为插入与删除的效率比较低
第 1 章 数据结构与算法 18 除线性表中的第 1 个元素(即删除元素 29)。其删除过程如下： 从第 2 个元素开始直到最后一个元素，将其中的每一个元素均依次往前移动一个位置。此 时，线性表的长度变成了 7，如图 1.8(b)所示。 如果再要删除线性表中的第 6 个元素，则采用类似的方法：将第 7 个元素往前移动一个位 置。此时，线性表的长度变成了 6，如图 1.8(c)所示。 29 18 56 63 35 24 31 47 (a)长度为8的线性表 V(1:10) 1 2 3 4 5 6 7 8 9 10 18 56 63 35 24 31 47 (b)删除元素29后的线性表 V(1:10) 1 2 3 4 5 6 7 8 9 10 (c)删除元素31后的线性表 图1.8 线性表在顺序存储结构下的删除 18 56 63 35 24 47 V(1:10) 1 2 3 4 5 6 7 8 9 10 一般来说，设长度为 n 的线性表为 (a ,a , ,a , ,a ) l 2 i n 现要删除第 i 个元素，删除后得到长度为 n-1 的线性表为 (a ,a , ,a ,a ) l 2 j n−1 则删除前后的两线性表中的元素满足如下关系： − − = + 1 1 1 a 1 i j n a j i a j j j 在一般情况下，要删除第 i(1≤i≤n)个元素时，则要从第 i+1 个元素开始，直到第 n 个元素 之间共 n-i 个元素依次向前移动一个位置。删除结束后，线性表的长度就减小了 1。 显然，在线性表采用顺序存储结构时，如果删除运算在线性表的末尾进行，即删除第 n 个 元素，则不需要移动表中的元素；如果要删除线性表中的第 1 个元素，则需要移动表中所有的 元素。在一般情况下，如果要删除第 i(1≤i≤n)个元素，则原来第 i 个元素之后的所有元素都必 须依次往前移动一个位置。在平均情况下，要在线性表中删除一个元素，需要移动表中一半的 元素。因此，在线性表顺序存储的情况下，要删除一个元素，其效率也是很低的，特别是在线 性表比较大的情况下更为突出，由于数据元素的移动而消耗较多的处理时间。 由线性表在顺序存储结构下的插入与删除运算可以看出，线性表的顺序存储结构对于小线 性表或者其中元素不常变动的线性表来说是合适的，因为顺序存储的结构比较简单。但这种顺 序存储的方式对于元素经常需要变动的大线性表就不太合适了，因为插入与删除的效率比较低
第1章数据结枃与算法 14栈和队列 14.1栈及其基本运算 1什么是栈 栈实际上也是线性表,只不过是一种特殊的线性表。在这种特殊的线性表中,其插入与删 除运算都只在线性表的一端进行。即在这种线性表的结构中,一端是封闭的,不允许进行插入 与删除元素:另一端是开口的,允许插入与删除元素。在顺序存储结构下,对这种类型线性表 的插入与删除运算是不需要移动表中其他数据元素的。这种线性表称为栈 栈( stack)是限定在一端进行插入与删除的线性表。 在栈中,允许插入与删除的一端称为栈顶,而不允许插入与删除的另一端称为栈底。栈顶 元素总是最后被插入的元素,从而也是最先能被删除的元素:栈底元素总是最先被插入的元素 从而也是最后才能被删除的元素。即栈是按照“先进后出”(FO- First in last out)或“后进 先出”( LIFO-Last in first out)的原则组织数据的,因 此,栈也被称为“先进后出”表或“后进先出”表。由 入栈出栈 此可以看出,栈具有记忆作用。 通常用指针top来指示栈顶的位置,用指针boto 指向栈底。 栈顶top→ 往栈中插入一个元素称为入栈运算,从栈中删除 个元素(即删除栈顶元素)称为退栈运算。栈顶指针top 动态反映了栈中元素的变化情况 图19是栈的示意图。 栈低 botton→ 栈这种数据结构在日常生活中也是常见的。例如, 子弹夹是一种栈的结构,最后压入的子弹总是最先被弹 图1.9栈示意图 出,而最先压入的子弹最后才能被弹出。又如,在用 端为封闭另一端为开口的容器装物品时,也是遵循“先进后出”或“后进先出”原则的。 2栈的顺序存储及其运算 S(1:10) S(1:10) S(1:10) E B ttom一1 bot tom一1 bot tom- 1 (a)有6个元素的栈 (b)插入X与Y后的栈 (c)退出一个元素后的栈 图1.10栈在顺序存储结构下的运算 与一般的线性表一样,在程序设计语言中,用一维数组S(1:m)作为栈的顺序存储空间
第 1 章 数据结构与算法 19 1.4 栈和队列 1.4.1 栈及其基本运算 1.什么是栈 栈实际上也是线性表，只不过是一种特殊的线性表。在这种特殊的线性表中，其插入与删 除运算都只在线性表的一端进行。即在这种线性表的结构中，一端是封闭的，不允许进行插入 与删除元素；另一端是开口的，允许插入与删除元素。在顺序存储结构下，对这种类型线性表 的插入与删除运算是不需要移动表中其他数据元素的。这种线性表称为栈。 栈(stack)是限定在一端进行插入与删除的线性表。 在栈中，允许插入与删除的一端称为栈顶，而不允许插入与删除的另一端称为栈底。栈顶 元素总是最后被插入的元素，从而也是最先能被删除的元素；栈底元素总是最先被插入的元素， 从而也是最后才能被删除的元素。即栈是按照“先进后出”(FILO－First In Last Out)或“后进 先出”(LIFO—Last In First Out)的原则组织数据的，因 此，栈也被称为“先进后出”表或“后进先出”表。由 此可以看出，栈具有记忆作用。 通常用指针 top 来指示栈顶的位置，用指针 bottom 指向栈底。 往栈中插入一个元素称为入栈运算，从栈中删除一 个元素(即删除栈顶元素)称为退栈运算。栈顶指针 top 动态反映了栈中元素的变化情况。 图 1.9 是栈的示意图。 栈这种数据结构在日常生活中也是常见的。例如， 子弹夹是一种栈的结构，最后压入的子弹总是最先被弹 出，而最先压入的子弹最后才能被弹出。又如，在用一 端为封闭另一端为开口的容器装物品时，也是遵循“先进后出”或“后进先出”原则的。 2.栈的顺序存储及其运算 F E D C B A (a)有6个元素的栈 S(1:10) 10 9 8 7 6 5 4 3 2 1 B A Y X F E D C (b)插入X与Y后的栈 S(1:10) 10 9 8 7 6 5 4 3 2 1 (c)退出一个元素后的栈 图1.10 栈在顺序存储结构下的运算 B A X F E D C S(1:10) 10 9 8 7 6 5 4 3 2 1 bottom top bottom top bottom top 6 与一般的线性表一样，在程序设计语言中，用一维数组 S(1：m)作为栈的顺序存储空间， an ┇ a2 a1 栈顶 top → 栈低 bottom→ 图 1.9 栈示意图 入栈 ↓ 出栈 ↑
第1章数据结构与算法 其中m为栈的最大容量。通常,栈底指针指向栈空间的低地址一端(即数组的起始地址这一端 图1.10a)是容量为10的栈顺序存储空间,栈中已有6个元素:图1.10(b)与图1.10c)分别为入 栈与退栈后的状态 在栈的顺序存储空间S(1:m)中,S( bottom)通常为栈底元素(在栈非空的情况下),stop)为 栈顶元素。top=0表示栈空;top=m表示栈满。 栈的基本运算有三种:入栈、退栈与读栈顶元素。下面分别介绍在顺序存储结构下栈的这 三种运算。 (1)入栈运算 入栈运算是指在栈顶位置插入一个新元素。这个运算有两个基本操作:首先将栈顶指针进 (即top加1),然后将新元素插入到栈顶指针指向的位置。 当栈顶指针已经指向存储空间的最后一个位置时,说明栈空间已满,不可能再进行入栈操 作。这种情况称为栈“上溢”错误。 (2)退栈运算 退栈运算是指取出栈顶元素并赋给一个指定的变量。这个运算有两个基本操作:首先将栈 顶元素(栈顶指针指向的元素)赋给一个指定的变量,然后将栈顶指针退-(即top减1) 当栈顶指针为θ时,说明栈空,不可能进行退栈操作。这种情况称为栈“下溢”错误。 (3)读栈顶元素 读栈顶元素是指将栈顶元素赋给一个指定的变量。必须注意,这个运算不删除栈项元素 只是将它的值赋给一个变量,因此,在这个运算中,栈项指针不会改变。 当栈顶指针为0时,说明栈空,读不到栈顶元素。 142队列及其基本运算 1什么是队列 在计算机系统中,如果一次只能执行一个用户程序,则在多个用户程序需要执行时,这些 用户程序必须先按照到来的顺序进行排队等待。这通常是由计算机操作系统来进行管理的。 在操作系统中,用一个线性表来组织管理用户程序的排队执行,原则是 ①初始时线性表为空; ②当有用户程序来到时,将该用户程序加入到线性表的末尾进行等待: ③当计算机系统执行完当前的用户程序后,就从线性表的头部取出一个用户程序执行。 由这个例子可以看出,在这种线性表中,需要加入的元素总是插入到线性表的末尾,并且 又总是从线性表的头部取出(删除)元素。这种线性表称为队列。 队列(qμueue)是指允许在一端进行插入、而在另~端进行删除的线性表。允许插入的一端称 为队尾,通常用一个称为尾指针(rear)的指针指向队尾元素,即尾指针总是指向最后被插入的元 素:允许删除的一端称为排头(也称为队头),通常也用一个排头指针(fron指向排头元素的前- 个位置。显然,在队列这种数据结构中,最先插入的元素将最先能够被删除,反之,最后插入 的元素将最后才能被删除。因此,队列又称为“先进先出”(FIFO— First in first ou或“后 进后出”( LILO--Last in last out)的线性表,它体现了“先来先服务”的原则。在队列中,队 尾指针rear与排头指针 front共同反映了队列中元素动态变化的情况。图1.11是具有6个元素 的队列示意图
第 1 章 数据结构与算法 20 其中 m 为栈的最大容量。通常，栈底指针指向栈空间的低地址一端(即数组的起始地址这一端)。 图 1.10(a)是容量为 10 的栈顺序存储空间，栈中已有 6 个元素；图 1.10(b)与图 1.10(c)分别为入 栈与退栈后的状态。 在栈的顺序存储空间 S(1：m)中，S(bottom)通常为栈底元素(在栈非空的情况下)，s(top)为 栈顶元素。top=0 表示栈空；top=m 表示栈满。 栈的基本运算有三种：入栈、退栈与读栈顶元素。下面分别介绍在顺序存储结构下栈的这 三种运算。 (1)入栈运算 入栈运算是指在栈顶位置插入一个新元素。这个运算有两个基本操作：首先将栈顶指针进 一(即 top 加 1)，然后将新元素插入到栈顶指针指向的位置。 当栈顶指针已经指向存储空间的最后一个位置时，说明栈空间已满，不可能再进行入栈操 作。这种情况称为栈“上溢”错误。 (2)退栈运算 退栈运算是指取出栈顶元素并赋给一个指定的变量。这个运算有两个基本操作：首先将栈 顶元素(栈顶指针指向的元素)赋给一个指定的变量，然后将栈顶指针退一(即 top 减 1)。 当栈顶指针为 0 时，说明栈空，不可能进行退栈操作。这种情况称为栈“下溢”错误。 (3)读栈顶元素 读栈顶元素是指将栈顶元素赋给一个指定的变量。必须注意，这个运算不删除栈项元素， 只是将它的值赋给一个变量，因此，在这个运算中，栈项指针不会改变。 当栈顶指针为 0 时，说明栈空，读不到栈顶元素。 1.4.2 队列及其基本运算 1.什么是队列 在计算机系统中，如果一次只能执行一个用户程序，则在多个用户程序需要执行时，这些 用户程序必须先按照到来的顺序进行排队等待。这通常是由计算机操作系统来进行管理的。 在操作系统中，用一个线性表来组织管理用户程序的排队执行，原则是： ①初始时线性表为空； ②当有用户程序来到时，将该用户程序加入到线性表的末尾进行等待； ③当计算机系统执行完当前的用户程序后，就从线性表的头部取出一个用户程序执行。 由这个例子可以看出，在这种线性表中，需要加入的元素总是插入到线性表的末尾，并且 又总是从线性表的头部取出(删除)元素。这种线性表称为队列。 队列(queue)是指允许在一端进行插入、而在另～端进行删除的线性表。允许插入的一端称 为队尾，通常用一个称为尾指针(rear)的指针指向队尾元素，即尾指针总是指向最后被插入的元 素；允许删除的一端称为排头(也称为队头)，通常也用一个排头指针(front)指向排头元素的前一 个位置。显然，在队列这种数据结构中，最先插入的元素将最先能够被删除，反之，最后插入 的元素将最后才能被删除。因此，队列又称为“先进先出”(FIFO——First In First Out)或“后 进后出”(LILO——Last In Last Out)的线性表，它体现了“先来先服务”的原则。在队列中，队 尾指针 rear 与排头指针 front 共同反映了队列中元素动态变化的情况。图 1.11 是具有 6 个元素 的队列示意图
第1章数据结构与算法 rear 图1.11具有6个元素的队列示意图 往队列的队尾插入一个元素称为入队运算,从队列的排头删除一个元素称为退队运算。 图1.12是在队列中进行插入与删除的示意图。由图1.12可以看出,在队列的末尾插入一个 元素(入队运算)只涉及队尾指针rea的变化,而要删除队列中的排头元素(退队运算)只涉及排头 指针 front的变化 与栈类似,在程序设计语言中,用一维数组作为队列的顺序存储空间 front一 front front一 BCD B rear CDE (a)一个队列 (b)删除一个元素后的队列 (c)插入元素E后的队列 图1.12队列运算示意图 2循环队列及其运算 在实际应用中,队列的顺序存储结构一般采用循环队列的形式。 所谓循环队列,就是将队列存储空间的最后一个位置绕到第一个位置,形成逻辑上的环状 空间,供队列循环使用,如图1.13所示。在循环队列结构中,当存储空间的最后一个位置已被 使用而再要进行入队运算时,只要存储空间的第一个位置 空闲,便可将元素加入到第一个位置,即将存储空间的第 Q(1:m) 个位置作为队尾 rear→m 在循环队列中,用队尾指针rea指向队列中的队尾元 素,用排头指针frot指向排头元素的前一个位置,因此, front→> 从排头指针 front指向的后一个位置直到队尾指针rear指向 的位置之间所有的元素均为队列中的元素。 循环队列的初始状态为空,即rear= front=m,如图1.13 所示 循环队列主要有两种基本运算:入队运算与退队运算。 每进行一次入队运算,队尾指针就进一。当队尾指针图1.13循环队列存储空间示意图 rear=m+1时,则置rear= 每进行一次退队运算,排头指针就进一。当排头指针 front=m+1时,则置 front=。 图1.14(a)是一个容量为8的循环队列存储空间,且其中已有6个元素。图1.14(b)是在图 1.14(a)的循环队列中又加入了2个元素后的状态。图1.14(c)是在1.14b)的循环队列中退出了1 个元素后的状态
第 1 章 数据结构与算法 21 退对 A B C D E F 入对 front rear 图1.11 具有6个元素的队列示意图 往队列的队尾插入一个元素称为入队运算，从队列的排头删除一个元素称为退队运算。 图 1.12 是在队列中进行插入与删除的示意图。由图 1.12 可以看出，在队列的末尾插入一个 元素(入队运算)只涉及队尾指针 rear 的变化，而要删除队列中的排头元素(退队运算)只涉及排头 指针 front 的变化。 与栈类似，在程序设计语言中，用一维数组作为队列的顺序存储空间。 A B C D (a) 一个队列 (b) 删除一个元素后的队列 (c) 插入元素E后的队列 图1.12 队列运算示意图 rear front B rear D front B C D rear E front C 2.循环队列及其运算 在实际应用中，队列的顺序存储结构一般采用循环队列的形式。 所谓循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状 空间，供队列循环使用，如图 1.13 所示。在循环队列结构中，当存储空间的最后一个位置已被 使用而再要进行入队运算时，只要存储空间的第一个位置 空闲，便可将元素加入到第一个位置，即将存储空间的第 一个位置作为队尾。 在循环队列中，用队尾指针 real 指向队列中的队尾元 素，用排头指针 front 指向排头元素的前一个位置，因此， 从排头指针front指向的后一个位置直到队尾指针rear 指向 的位置之间所有的元素均为队列中的元素。 循环队列的初始状态为空，即 rear=front=m，如图 1.13 所示。 循环队列主要有两种基本运算：入队运算与退队运算。 每进行一次入队运算，队尾指针就进一。当队尾指针 rear=m+1 时，则置 rear=l。 每进行一次退队运算，排头指针就进一。当排头指针 front=m+1 时，则置 front=l。 图 1.14(a)是一个容量为 8 的循环队列存储空间，且其中已有 6 个元素。图 1.14(b)是在图 1.14(a)的循环队列中又加入了 2 个元素后的状态。图 1.14(c)是在 1.14(b)的循环队列中退出了 1 个元素后的状态。 ┇ rear front m 2 1 Q（1:m） 图 1.13 循环队列存储空间示意图
第1章数据结构与算法 Q(1:8) 87654 XFEDCBAY E EDCBA 5432 front一1 front一 rear一 (a)具有6个元素的循环队列(b)加入X、Y后的循环队列(c)退出一个元素后的循环队列 图1.14循环队列运算例 由图1.14中循环队列动态变化的过程可以看出,当循环队列满时有 front=ear,而当循环 队列空时也有 front=rear。即在循环队列中,当 front=rear时,不能确定是队列满还是队列空。 在实际使用循环队列时,为了能区分队列满还是队列空,通常还需増加一个标志s,s值的定义 如下: SJ0表示队列空 1表示队列非空 由此可以得出队列空与队列满的条件如下: 队列空的条件为s=0 队列满的条件为s=1且 front=rear 下面具体介绍循环队列入队与退队的运算 假设循环队列的初始状态为空,即:s=0,且 front=rear=m。 (1)入队运算 入队运算是指在循环队列的队尾加入一个新元素。这个运算有两个基本操作:首先将队尾 指针进-(即rear=rear+1),并当rear=m+时置 rear-=1:然后将新元素插入到队尾指针指向的位 置 当循环队列非空(s=1)且队尾指针等于排头指针时,说明循环队列已满,不能进行入队运算, 这种情况称为“上溢”。 (2)退队运算 退队运算是指在循环队列的排头位置退出一个元素并赋给指定的变量。这个运算有两个基 本操作:首先将排头指针进一(即font=font+1),并当font=m+时置 front=:然后将排头指针 指向的元素赋给指定的变量。 当循环队列为空(s=0)时,不能进行退队运算,这种情况称为“下溢”。 1.5线性链表 151线性链表的基本概念 前面主要讨论了线性表的顺序存储结构以及在顺序存储结构下的运算。线性表的顺序存储 结构具有简单、运算方便等优点,特别是对于小线性表或长度固定的线性表,采用顺序存储结 构的优越性更为突出
第 1 章 数据结构与算法 22 F E D C B A (a) 具有6个元素的循环队列 Q(1:8) 8 7 6 5 4 3 2 1 A Y X F E D C B (b) 加入X、Y后的循环队列 Q(1:8) 8 7 6 5 4 3 2 1 (c) 退出一个元素后的循环队列 图1.14 循环队列运算例 Y X F E D C B Q(1:8) 8 7 6 5 4 3 2 1 front rear front rear front rear 6 由图 1.14 中循环队列动态变化的过程可以看出，当循环队列满时有 front=rear，而当循环 队列空时也有 front=rear。即在循环队列中，当 front=rear 时，不能确定是队列满还是队列空。 在实际使用循环队列时，为了能区分队列满还是队列空，通常还需增加一个标志 s，s 值的定义 如下： = 表示队列非空 表示队列空 1 0 S 由此可以得出队列空与队列满的条件如下： 队列空的条件为 s=0； 队列满的条件为 s=l 且 front=rear。 下面具体介绍循环队列入队与退队的运算。 假设循环队列的初始状态为空，即：s=0，且 front=rear=m。 (1)入队运算 入队运算是指在循环队列的队尾加入一个新元素。这个运算有两个基本操作：首先将队尾 指针进一(即 rear=rear+1)，并当 rear=m+l 时置 rear=1；然后将新元素插入到队尾指针指向的位 置。 当循环队列非空(s=1)且队尾指针等于排头指针时，说明循环队列已满，不能进行入队运算， 这种情况称为“上溢”。 (2)退队运算 退队运算是指在循环队列的排头位置退出一个元素并赋给指定的变量。这个运算有两个基 本操作：首先将排头指针进一(即 front=front+1)，并当 front=m+l 时置 front=l；然后将排头指针 指向的元素赋给指定的变量。 当循环队列为空(s=0)时，不能进行退队运算，这种情况称为“下溢”。 1.5 线性链表 1.5.1 线性链表的基本概念 前面主要讨论了线性表的顺序存储结构以及在顺序存储结构下的运算。线性表的顺序存储 结构具有简单、运算方便等优点，特别是对于小线性表或长度固定的线性表，采用顺序存储结 构的优越性更为突出