第3章 数据结构及运算

1、第3章 数据结构及其运算电气工程学院3.1数据结构的基本概念一、基本概念1. 数据数据(data) 数据是指能存于计算机、并被计算机处理的符号的集合。它是客观事物的符号表示。2. 数据元素数据元素(data element) 数据元素是数据的基本单位，即数据集合中的一个个体。数据元素可由若干个数据项组成(data item)。数据项是数据的最小单位。3. 数据对象数据对象(data object) 数据对象：是指具有相同特性的数据元素的集合。它是数据的一个子集。4. 数据结构数据结构(data structure) 数据结构：是指数据元素之间的相互关系和这种关系在计算机中的存储表示。 数据的逻

2、辑结构(logical structure)：是指数据之间的逻辑关系，是用户按使用需要建立的。 数据的物理结构(physical structure)：是指数据在计算机内的实际存储形式。5. 线性数据结构线性数据结构 有且仅有一个起始点和一个终端结点，除第一个结点和最后一个结点外，其余结点都有一个直接前驱和一个直接后继。6. 非线性数据结构非线性数据结构 一个结点可能有多个直接前驱和多个直接后继。7. 数据类型数据类型(data type) 指程序设计语言中所允许的变量种类。 在C语言中，提供了实型、整型、字符型和指针型等基本数据类型。二、数据结构数据结构研究的内容: 数据结构作为计算机的一门

3、学科，主要研究和讨论以下三个方面的问题 数据的逻辑结构数据的逻辑结构 数据的物理结构数据的物理结构 对数据的操作对数据的操作 研究数据结构的目的: 提高数据处理的效率提高数据处理的效率 提高数据处理的速度提高数据处理的速度 尽量节省计算机存储空间尽量节省计算机存储空间 在具有相同特征的数据元素集合中，各个元素之间存在某种关系(联系)，这种关系反映了该集合中的数据元素具有的一种结构：前、后件关系，或直接前驱与直接后继。 例如，描述一年四季的季节名“春，夏，秋，冬”可以作为季节的数据元素。在考虑一年四季的顺序关系时，则“春”是“夏”的前件(直接前驱)，而“夏” 是“春”的后件(直接后继) ，前后件

4、关系是数据元素之间的一种基本关系，但前后件关系所表示的实际意义是随具体对象的不同而不同。一般来说，数据元素之间的任何关系都可以用前后件关系来描述。1、数据的逻辑结构：、数据的逻辑结构：是指反映数据元素之间逻辑关系的数据结构。 数据的逻辑结构有两个要素： 1). 数据元素的集合D； 2). 反映D中各数据元素之间的前后件关系R。 数据结构的表示形式：B(D，R)，其中B表示数据结构 为了反映D中各数据元素之间的前后件关系，一般用二元组来表示。 设a与b是D中的两个数据，则二元组（a，b）表示a是b的前件，b是a的后件。例：一年四季数据结构 B=（D，R），D=春，夏，秋，冬 ; R=(春，夏)，

5、(夏，秋)，(秋，冬)。 家庭成员数据结构：B=（D，R），D=父亲，儿子，女儿 R=(父亲，儿子)，(父亲，女儿)。2、数据的存储结构：、数据的存储结构：又称为数据的物理结构， 是指数据的逻辑结构在计算机存储空间中的存放形式。 四种基本存储结构：顺序存储结构：逻辑上相邻的元素存储到物理上相邻的存储单元中。链式存储结构：为每一个结点附加一个指针字段，用于指向其后继结点。p索引存储结构：用结点的索引号确定结点的存储地址。p散列存储结构：根据结点的值确定存储地址。 采用不同的存储结构，其数据处理的效率是不同的，因此，在进行数据处理时，选择合适的存储结构是很重要的。3、数据的运算、数据的运算 定义在

6、数据的逻辑结构上的，其运算的具体实现是在数据的存储结构上进行的。 常用运算：建立（create）、）、访问（access）、）、消毁（destroy）、）、修改（modify）、）、删除（delete）、）、排序（sort）、）、插入（instert）、）、查找（search）。）。三、数据结构的图形表示1. 数据结构的图形表示的基本概念数据结构的图形表示的基本概念 数据结点：简称为结点，是指在数据结构的图形表示中，对于数据集合D中的每一个数据元素用中间标有元素值的方框表示。 为了表示各数据元素之间的前后件关系，对于关系R中的每一个二元组，用一条有向线段从前件结点指向后件结点。 一年四季数据结

7、构的图形表示： 家庭成员间辈份关系数据结的图形表示：例：用图形表示数据结构B=(D，R)，其中D=di|1i7=d1,d2,d3,d4,d5,d6,d7；R=(d1,d3),(d1,d7),(d2,d4),(d3,d6),(d4,d5)。这个数据结构的图形表示如下图所示： 数据结构中的元素结点可能是在动态变化的。根据需要或在处理过程中，可以在一个数据结构中增加一个新结点(称为插入运算)，也可以删除数据结构中的某个结点(称为删除运算)。插入与删除是对数据结构的两种基本运算。除此之外，对数据结构的运算还有查找、分类、合并、分解、复制和修改等。 如果在一个数据结构中一个数据元素都没有，则称该数据结构

8、为空的数据结构。在一个空的数据结构中插入一个新的元素后就变为非空。四、线性数据结构与非线性数据结构 根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分为两大类型：线性结构与非线性结构。1. 线性数据结构线性数据结构 如果一个非空的数据结构满足下列两个条件： (1) 有且只有一个根结点。有且只有一个根结点。 (2) 每一个结点最多有一个前件，也最多有一个后件。每一个结点最多有一个前件，也最多有一个后件。 则称该数据结构为线性结构，线性结构又称线性表。在线性结构中，各数据元素之间的前后件关系是很简单的。2. 非线性数据结构非线性数据结构 如果一个数据结构不是线性结构，则称之为非线性

9、结构。在非线性结构中，各数据元素之间的前后件关系要比线性结构复杂，因此，对非线性结构的存储与处理比线性结构复杂得多。 线性结构与非线性结构都可以是空的数据结构。一个空的数据结构究竟是属于线性结构还是属于非线性结构，这要根据具体情况来确定。如果对该数据结构的运算按线性结构的规则来处理，则属于线性结构；否则属于非线性结构。3.2线性表及其顺序存储结构一、线性表及其运算一、线性表及其运算 1. 线性表线性表 线性表(linearlist)是最简单、最常用的一种数据结构。 线性表的特征： 开始结点：没有前驱；终端结点：没有后继；其余结点都只有一个直接前驱和一个直接后继。 线性表的表示：(a1，a2，a

10、3，ai-1，ai，ai+1，an-1，an) 线性表中结点的个数n称为线性表的长度，当n=0时，称为空表。2.线性表的顺序存储结构线性表的顺序存储结构顺序存储：也称为顺序分配，是一种最简单的计算机中存放线性表的方法。 线性表的顺序存储结构的基本特点：p线性表中所有元素所占的存储空间是连续的。线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。 线性表的存储地址：假设线性表中的第一个数据元素的存储地址(指第一个字节的地址，即首地址)为ADR(a1)，每一个数据元素占k个字节，则线性表中第i个元素ai在计算机存储空间中的存储地址为 即在顺序存储结构中，线性表中每一个数据元素在计算机存储空间中的

11、存储地址由该元素在线性表中的位置序号唯一确定。 长度为n的线性表(a1，a2，a3，ai-1，ai，ai+1，an-1，an)在计算机中的顺序存储结构如下图所示。线性表的主要运算插入：在指定位置插入新的元素。元素后移，预留空间，修改表长。删除：删除指定的元素。元素前移，修改表长。查找：查找某个特点的元素。修改：对某个元素的值进行修改 。排序：按元素值大小进行排序分解：将一个线性表分解成多个线性表。合并：将多个线性表合并成一个线性表。复制：复制一个线性表。逆转：逆转一个线性表。3.线性表在顺序存储下的插入运算线性表在顺序存储下的插入运算 算法1 在长度为n的线性表中的第i个元素之前插入新元素b

12、算法分析：要在第i(1in)个元素之前插入一个新元素时，首先要将从最后一个(即第n个)元素开始，直到第i个元素之间的共n-i+1个元素，依次向后移动一个位置；移动结束后，第i个位置将被空出；然后将新元素插入到第i项。插入结束后，线性表的长度就增加了1。 算法中的异常情况处理：当存储空间已满(即n=m)时为“上溢”错误，不能进行插入。当in时，认为在最后一个元素之后(即第n+1个元素之前)插入。当i1时，认为在第1个元素之前插入。 算法的C语言描述： 输入：线性表的存储空间V(1：m)；线性表的长度n（nm）；插入的位置i（i表示在第i个元素之前插入）；插入的新元素b ； 输出：插入后的线性表存

13、储空间V(1：m)及线性表的长度n。 例2 下图中(a)为一个长度为8的线性表顺序存储在长度为10的存储空间中。现在要求在第2个元素(即18)之前插入一个新元素87。 过程分析：首先从最后一个元素开始直到第2个元素，将其中的每一个元素均依次往后移动一个位置；然后将新元素87插入到第2个位置。插入一个新元素后，线性表的长度变成了9，如图(b)所示。4.线性表在顺序存储下的删除运算线性表在顺序存储下的删除运算线性表在顺序存储下的删除算法 在长度为n的线性表中的删除第i个元素。 要删除第i(1in)个元素时，需要从第i+1个元素开始，将直到第n个元素之间的总共n-i个元素，依次向前移动一个位置。删除

14、结束后，线性表的长度将减去1 。 算法中的异常情况处理： 当线性表为空(即n=0)时为下溢错误，不能进行删除。 当in时，则认为在表中没有这个元素，也不能进行删除。算法的C语言描述：输入：线性表的存储空间V(1：m)；线性表的长度n(nm)；删除的位置i(表示删除第i个元素)。输出：删除后的线性表存储空间V(1:m)及线性表的长度n。二、栈及其运算二、栈及其运算1. 栈的特性：栈具有记忆作用；栈是按照“先进后出” (FILOFirst In Last Out)或“后进先出” (LIFOLast In First Out)的原则组织数据的，因此栈也被称为“先进后出”表或“后进先出”表。2. 栈的

15、顺序存储及其运算 在程序设计语言中，用一维数组S(1：m)作为栈的顺序存储空间，其中m为栈的最大容量。通常，栈底指针指向栈空间的低地址一端(即数组的起始地址这一端)。 在栈的顺序存储空间S(1：m)中，S(bottom)通常为栈底元素(在栈非空的情况下)，S(top)为栈顶元素。top = 0表示栈空；top = m表示栈满。 栈的基本运算初始化IniStack(S)：其作用是建立一个空栈，准备存放数据。进栈Push(S，x)：其作用是将数据元素x插入栈S，使x成为S的栈顶元素。出栈Pop(S)：其作用是当栈不空时返回栈顶元素为该函数的值，然后删去栈顶元素。读栈顶Get Top(S)：其作用是

16、当栈不空时返回栈顶元素为该函数的值，但是栈顶保持不变。初始化运算 栈的初始化是用于建立一个空栈的顺序存储空间。 栈的初始化的C语言描述为：入栈运算 入栈运算有两个基本操作：首先，将栈顶指针进一(即top加1)，然后，将新元素插入到栈顶指针指向的位置。 在容量为m的栈S中插入一个元素x(入栈运算)。 算法中的异常情况处理：当栈顶指针已经指向存储空间的最后一个位置时，说明栈空间己满，不可能再进行入栈操作。这种情况称为栈上溢“错误。退栈运算 退栈运算有两个基本操作：首先，将栈顶元素(栈顶指针指向的元素)赋给一个指定的变量，然后，将栈顶的指针退一(即top-1)。 在容量为m的栈S中删除栈顶元素(退栈

17、运算)。算法中的异常情况处理：当栈顶指针为0时，说明栈空，不可能进行退栈操作。这种情况称为栈下溢错误。3.栈的应用栈的应用表达式的计算表达式的计算 在计算机软件设计中，栈的应用很广泛。栈除了用于子程序嵌套调用外，还用于实现递归调用过程、表达式的处理和中断的处理等。栈的所有应用本质上是利用了栈的记忆作用。 利用栈来处理表达式的计算问题时，为简单起见，主要以算术表达式为例，并且假设在表达式中只有加、减、乘、除四个四则运算符，所有的运算对象均为单变量，在表达式的最后有一个结束符“;。 计算机系统在具体处理表达式前，首先设置以下两个栈： 一是运算符栈，用于在表达式处理过程中存放运算符。在开始时，运算符

18、栈中先压入一个表达式结束符“;”。 二是操作数栈，用于在表达式处理过程中存放操作数。 表达式计算过程： 从左到右依次读出表达式中的各个符号：若是操作数，则压入操作数栈，依次读下一个符号。若是运算符，则作进一步判断：若读出运算符的优先级大于运算符栈栈顶运算符的优先级，则将读出的运算符压入运算符栈，并依次读下一个符号。若读出的是表达式结束符“;”，且运算符栈栈顶的运算符也是表达式结束符“;”，则表达式处理结束，最后的计算结果在操作数栈的栈顶位置。若读出运算符的优先级不大于运算符栈栈顶运算符的优先级，则从操作数栈连续退出两个操作数，并从运算符栈退出一个运算符，然后作相应的运算(运算符为刚从运算符栈退

19、出的运算符，运算对象为刚从操作数栈退出的两个操作数)，并将运算结果压入操作数栈。在这种情况下，当前读出的运算符下次将重新考虑(即不再读下一个符号)。表达式计算应用实例计算表达式“A+B*C-D/E”的值。三、队列及其运算1. 队列 队列是另一种特殊的线性表。是限定只能在队尾插入、只能在队列的头删除的线性表。 队列(Queue)是只能在一端进行插入，而在另一端删除线性表。能进行插入的一端称为队列的尾，能进行删除的一端称为队列的头。 先进入队列中的元素称为队列的头元素(队列的头)，用排头指针(front)指向队列的头元素的前一个位置；最后进入队列中的元素称为队列的尾元素(队列的尾)，用尾指针(re

20、ar)指向队尾元素。队列称为先进先出表(First In First Out)，简称FIFO。 往队列的队尾插入一个元素称为入队运算，从队列的排头删除一个元素称为退队运算。 在队列中进行插入与删除的操作如下图所示。在队列的末尾插入一个元素(入队运算)只涉及队尾指针rear的变化，删除队列中的排头元素(退队运算)只涉及排头指针front的变化。2. 循环队列及其运算 在实际应用中，队列的顺序存 储结构一般采用循环队列的形式。 循环队列：是指将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。如图右所示。 在循环队列结构中，当存储空间的最后一个位置已被使用而再要进行人

21、队运算时，只要存储空间的第一个位置空闲，便可将元素加入到第一个位置，即将存储空间的第一个位置作为队尾。 一个容量为8的循环队列存储空间，且其中已有6个元素。图(b)是在图(a)的循环队列中又加入了2个元素后的状态。图(c)是在(b)的循环队列中退出了1个元素后的状态。 当循环队列满时有front=rear，而当循环队列空时front=rear。在循环队列中，当front=rear时，不能确定是队列满还是队列空。在实际使用循环队列时，为了能区分队列满还是队列空，通常还需增加一个标志s，s值的定义如下： 队列空的条件：s0 队列满的条件：s1，且，且frontrear 循环队列的基本运算初始化init_queue()：其作用是建立一个空队列Q，准备存 放数据。入队运算addcq ()：其作用是将数据x插入到队列Q的队尾 ，队列的长度加1。退队运算delcq()：其作用是当队列非空时，将队列头元素 的值赋给指定的变量，删除队列头元素。初始化