计算机二级数据结构与算法

数据结构与算法1本章主要内容7.1算法7.2数据结构的基本概念7.3线性表7.4栈和队列7.5线性表的链式存储结构7.6树7.7查找技术7.8排序技术2学习这章之前需要掌握的基本术语1.数据是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。

2.数据元素数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

3.数据项数据项是数据的不可分割的最小单位。3学习这章之前需要掌握的基本术语4.数据对象数据对象是性质相同的数据元素的集合，是数据的一个子集。例如，整数数据对象是集合N={0,±1，±2，……}

字母字符数据对象是集合C={'A','B',……,'Z'}47.1算法7.1.1算法的基本概念⑴算法的基本特征⑵算法的基本要素⑶算法设计基本方法7.1.2算法复杂度⑴算法的时间复杂度⑵算法的空间复杂度5算法的基本概念算法是指解决方案的准确而完整的描述。它是指令的有限序列，其中每一条指令表示一个或多个操作。

6⑴算法的基本特征可行性确定性有穷性拥有足够的情报考虑计算工具明确定义，不允许多义有限时间内完成输入数据有效7（2）算法的基本要素1、对数据的运算和操作2、算法的控制结构算术运算逻辑运算关系运算数据传输顺序选择循环8（3）算法设计的基本方法列举法归纳法递推法递归法减半递推回溯法97.1.2算法复杂度它是指执行算法所需要的计算工作量。

算法的时间复杂度算法的工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模的函数，即 算法的工作量=f(n)其中，n是问题的规模。例如，两个n阶矩阵相乘所需要的基本运算次数为n3，即计算工作量为n3，也就是时间复杂度为n3。

10算法的空间复杂度，一般是指执行这个算法所需要的内存空间。

7.1.2算法复杂度算法程序所占的空间输入的初始数据所占的存储空间算法执行过程中所需要的额外空间++算法的空间复杂度11信息社会，在工作中经常要处理大量数据，那么当面对大量的数据元素时又该如何提高数据处理的效率呢？两方面提高数据处理的速度节省计算机存储空间12下列叙述中正确的是A．算法的效率只与问题的规模有关，而与数据的存储结构无关B．算法的时间复杂度是指执行算法所需要的计算工作量C．数据的逻辑结构与存储结构是一一对应的D．算法的时间复杂度与空间复杂度一定相关B13算法的有穷性是指

A．算法程序的运行时间是有限的

B．算法程序所处理的数据量是有限的

C．算法程序的长度是有限的

D．算法只能被有限的用户使用A14数据结构这门课程研究的内容①数据的逻辑结构

数据关系之间的逻辑关系

②数据的存储结构

数据的逻辑结构在计算机中的表示③操作算法

插入、删除、修改、查询、排序等15数据结构这门课程研究的内容集合线性结构-----表、栈、队列非线性结构-----树、图

逻辑结构存储结构顺序存储结构-----数组

链式存储结构-----指针

167.2.1数据结构的定义春夏秋冬父亲女儿儿子171.数据的逻辑结构概念是指反映数据元素之间逻辑关系的数据结构

B=(D,R)一个数据结构可以表示为元素的集合元素的关系要素DR182.数据的存储结构

数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构（也称数据的物理结构）。概念常用存储结构顺序链接索引不同的存储结构，数据处理的效率不同!197.2.2数据结构的图形表示集合线性树图20数据结构一般分为：线性结构与非线性结构217.2.3线性结构满足条件特点（1）有且只有一个根结点；（2）每一个结点最多有一个前件，最多有一个后件。（1）在数据元素的非空有限集中存在唯一的一个被称做“第一个”的数据元素（即首结点）。（2）存在唯一的一个被称做“最后一个”的数据元素（即尾结点）。（3）除第一个之外，集合中的每个数据元素均只有一个前驱（在某元素之前的元素称之为前驱）。（4）除最后一个之外，集合中每个数据元素均只有一个后继（在某元素之后的元素称之为后继）。

227.3线性表7.3.1线性表的定义7.3.2线性表的顺序存储结构1.定义2.顺序表的插入操作3.顺序表的删除操作237.3.1线性表的定义一个线性表是n个数据元素的有限序列。线性表是一种线性结构。数据元素在线性表中的位置只取决于其自身的序号，即数据元素之间的相对位置是线性的。(1)有且只有一个根结点，它无前件；(2)有且只有一个终端结点，它无后件；(3)除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。线性表中结点的个数ｎ称为线性表的长度。当n=0时，称为空表。结构特征247.3.2线性表的顺序存储结构在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素，称做线性表的顺序存储结构，简称顺序表。定义257.3.2线性表的顺序存储结构顺序表的插入操作267.3.2线性表的顺序存储结构顺序表的删除操作277.4栈和队列7.4.1栈7.4.2队列287.4.1栈栈（Stack）是一种只允许在一端进行插入和删除的线性表，它是一种操作受限的线性表。

栈的定义栈顶和栈底在表中只允许进行插入和删除的这一端称为栈顶（top），另一端称为栈底（bottom）。

入栈和出栈栈的插入操作叫入栈（push）；栈的删除操作叫出栈（pop）。29栈在生活中的例子举例1家里吃饭的碗，通常在洗干净后一个一个地落在一起存放，在使用时，若一个一个地拿，一定最先拿走最上面的那只碗，而最后拿出最下面的那只碗。举例2在建筑工地上，使用的砖块从底往上一层一层地码放，在使用时，将从最上面一层一层地拿取。

307.4.1栈利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。栈底的位置通常设置成数组的0单元栈顶的当前位置是动态的，随着插入与删除而变化对栈顶当前位置的标记称为栈顶指针栈的顺序存储结构顺序栈31栈为后进先出（LastInFirstOut）的线性表，简称为LIFO表。

栈的修改是按后进先出的原则进行。每次删除（退栈）的总是当前栈中"最新"的元素，即最后插入（进栈）的元素，而最先插入的是被放在栈的底部，要到最后才能删除。7.4.1栈32顺序栈插入删除操作示意图空栈插入元素A插入BCDE删除E,D栈顶栈底337.4.2队列定义队列（Queue）是一种只允许在一端进行插入，而在另一端进行删除的线性表，它也是一种操作受限的线性表。

队尾队头34队列在生活中的例子举例1到医院看病，首先需要到挂号处挂号，然后，按号码顺序救诊。举例2乘坐公共汽车，应该在车站排队，车来后，按顺序上车举例3在Windows这类多任务的操作系统环境中，每个应用程序响应一系列的"消息"，像用户点击鼠标；拖动窗口这些操作都会导致向应用程序发送消息。为此，系统将为每个应用程序创建一个队列，用来存放发送给该应用程序的所有消息，应用程序的处理过程就是不断地从队列中读取消息，并依次给予响应。357.4.2队列（1）允许删除的一端称为队头（Front）。（2）允许插入的一端称为队尾（Rear）。（3）当队列中没有元素时称为空队列。（4）队列亦称作先进先出（FirstInFirstOut）的线性表，简称为FIFO表。（5）队列的修改是依先进先出的原则进行的。

新来的成员总是加入队尾（即不允许"加塞"），每次离开的成员总是队列头上的（不允许中途离队），即当前"最老的"成员离队。

36顺序队列37下列叙述中正确的是A栈是“先进先出”的线性表

B队列是“先进后出”的线性表

C循环队列是非线性结构

D有序线性表既可以采用顺序存储结构,也可以采用链式存储结构D38下列叙述中正确的是A．队列属于非线性表B．队列按“先进后出”原则组织数据C．队列在队尾删除数据D．队列按“先进先出”原则组织数据D39B40D41下列关于栈的叙述正确的是

A．栈按“先进先出”组织数据

B．栈按“先进后出”组织数据

C．只能在栈底插入数据

D．不能删除数据B42假设用一个长度为50的数组(数组元素的下标从0到49)作为栈的存储空间，栈底指针bottom指向栈底元素，栈顶指针top指向栈顶元素，如果bottom=49，top=30(数组下标)，则栈中具有()个元素。1943设某循环队列的容量为50，头指针front=5(指向队头元素的前一位置)，尾指针rear=29(指向对尾元素)，则该循环队列中共有__个元素。24447.5线性表的链式存储结构链接方式存储的线性表简称为链表（LinkedList）链式存储方法①用一组任意的存储单元来存放线性表的结点

（这组存储单元既可以是连续的，也可以是不连续的）②链表中结点的逻辑次序和物理次序不一定相同。

为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息（称为指针（pointer））不仅可用来表示线性表，而且可用来表示各种非线性的数据结构。457.5.1线性单链表线性链表是线性表的链式存储结构，是一种物理存储单元上非连续、非顺序的存储结构。数据元素的逻辑顺序是通过链表中的指针链接次序实现的。将每一个存储结点分为两部分：一部分用于存储数据元素的值，称为数据域；另一部分用于存放下一个数据元素的存储结点的地址，即指向后继结点，称为指针域。

467.5.1线性单链表（1）空线性链表

（2）非空线性链表

指针域为空

对于链表的各种操作必须从头指针开始

477.5.2循环链表循环链表是将单链表的表中最后一个结点指针指向链表的表头结点，整个链表形成一个环，这样从表中任一结点出发都可找到表中其他的结点。

（1）带头结点的循环单链表的空表形式（2）带头结点的循环单链表的一般形式487.5.3双向链表在双向链表中，每一个结点除了数据域外，还包含两个指针域，一个指针（prior）指向该结点的后继结点，另一个指针（next）指向它的前驱结点。双向链表也可以有循环表。让表头结点的前驱指针指向链表的最后的一个结点，让最后一个结点的后继指针指向头结点。

（1）空双向链表

（2）非空双向循环链表

49A507.6树7.6.1树的基本概念7.6.2二叉树7.6.3遍历二叉树517.6.1树的基本概念树形结构是一类重要的非线性数据结构。族谱和各种社会组织结构都可以用树形结构表示。527.6.1树的基本概念1．定义

树是由n（n≥0）个结点组成的有限集合。若n=0，称为空树；若n>0，则：

（1）有一个特定的称为根（root）的结点。它只有直接后继，但没有直接前驱；

（2）除根结点以外的其它结点可以划分为m（m≥0）个互不相交的有限集合T0，T1，…，Tm-1，每个集合Ti（i=0,1,…,m-1）又是一棵树，称为根的子树，每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。

53树的示意图54树的根结点为A，该树还可以分为三个互不相交子集T0，T1，T2T0={B，E，F，J，K，L}T1={C，G}T2={D，H，I，M}T0子树T1子树T2子树如T0可以分为：T00,T01T00={E，J，K，L}T01={F}55树的常用术语1.结点

指树中的一个数据元素，包含数据项及若干指向其子树的分支，一般用一个字母表示。2.结点的度

一个结点包含子树的数目，称为该结点的度。3.树的度

树内各结点的度的最大值。4.树叶（叶子）

度为0的结点，称为叶子结点或树叶，也叫终端结点。5.分支结点度不为0的结点，又称非终端结点。6.孩子结点的子树的根称为该结点的孩子

56树的常用术语7.双亲孩子结点的上层结点即为这些结点的双亲。8.兄弟同一双亲的孩子之间互为兄弟。9.堂兄弟其双亲在同一层的结点互为堂兄弟。10.结点的祖先 从根到该结点所经分支上的所有结点。11.结点的子孙 以某结点为根的子树中的任一结点都称为该结点的子孙。57树的常用术语12.结点的层次 从根开始定义，根为第一层，根的孩子为第二层；若某结点在m层，则该结点的子树的根在m+1层。13.深度树中结点的最大层次数。14.森林是m(m>0)棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林。15.有序树和无序树 如果各子树依次从左到右排列，不可对换，则称该子树为有序树，且把各子树分别称为第一子树，第二子树……；反之，称为无序树。587.6.2二叉树1.定义二叉树是一种度不大于2的有序树。每个结点至多只有两棵子树（即二叉树中不存在度大于2的结点），并且二叉树的子树有左右之分，其次序不能任意颠倒。递归定义

二叉树是n(n0)个结点的有限集，它或者为空树(n=0)，或者由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树所构成。

59完全二叉树除叶子结点外，所有的结点的度都为2的二叉树称为完全二叉树非完全二叉树完全二叉树60满二叉树满二叉树是完全二叉树的特例。每层的结点数都满足2n-1。满二叉树61二叉树的存储将一棵二叉树按完全二叉树顺序存放到一个一维数组中，若该二叉树为非完全二叉树，则必须将相应位置空出来，使存放的结果符合完全二叉树形状。顺序存储结构浪费了大量的存储空间62二叉树的存储树形结构是非线性结构，采用顺序存储有一定的困难。

(浪费了大量的存储空间)通常用具有两个指针域的链表作为二叉树的存储结构，其中，每个结点由数据域Data、左指针域LChild和右指针域RChild组成。两个指针域分别指向该结点的左、右孩子。若某结点没有左孩子或右孩子，则对应的指针域为空。

637.6.3遍历二叉树

遍历（Traversing）是指循着某条搜索路线查找某数据结构中的结点，而且每个结点只被访问一次。遍历操作让二叉树中各结点按指定的顺序线性排列，使得非线性的二叉树线性化。遍历647.6.3遍历二叉树表示访问根结点

DLR表示遍历左子树

表示遍历右子树

DLR、LDR、LRD、DRL、RDL、RLD

若规定先左后右，则可归并为以下三种形式。DLR：前序（根）遍历。LDR：中序（根）遍历。LRD：后序（根）遍历。65⑴前序遍历1）访问根结点；2）按前序遍历规则遍历左子树；3）按前序遍历规则遍历右子树。规则:ABDECFG

66⑵中序遍历1）按中序遍历规则遍历左子树；2）访问根结点；3）按中序遍历规则遍历右子树。规则:DBEAFGC67⑶后序遍历1）按后序遍历规则遍历左子树；2）按后序遍历规则遍历右子树；3）访问根结点。规则:DEBGFCA

68某二叉树有5个度为2的结点,则该二叉树中的叶子结点是()A10B8C6D4C69某二叉树中有n个度为2的结点，则该二叉树中的叶子结点为()A．n+1B．n-1C．2nD．n/2A70对下列二叉树进行前序遍历的结果为

()A．DYBEAFCZX

B．YDEBFZXCA

C．ABDYECFXZ

D．ABCDEFXYZC71对下列二叉树进行中序遍历的结果为

()DBXEAYFZC72在深度为7的满二叉树中，度为2的结点个数为_________63737.7查找技术所谓查找是指在一个给定的数据结构中查找某个指定的元素。不同的数据结构采用不同的查找方法。本节课，我们讨论最常用的两种查找方式:

1)顺序查找

2)二分法查找747.7.1顺序查找从线性表的第一个元素开始，依次将线性表中的元素与被查元素进行比较。若相等则表示找到（即查找成功);若线性表中所有的元素都与被查元素进行了比较但都不相等，则表示线性表中没有要找的元素（即查找失败）。

基本原理757.7.1顺序查找两种情况下也只能采用顺序查找：1)如果线性表为无序表（即表中元素的排列是无序的)，则不管是顺序存储结构还是链式存储结构，都只能用顺序查找。2)即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。767.7.2二分法查找二分法查找只适用于顺序存储的有序表。基本原理设有序线性表的长度为n，被查元素为x,查找步骤如下:1)将x与线性表的中间项进行比较；若中间项的值等于x，则说明查到，查找结束；2)若x小于中间项的值，则在线性表的前半部分（即中间项以前的部分）以相同的方法进行查找；3)若x大于中间项的值，则在线性表的后半部分（即中间项以后的部分）以相同的方法进行查找。4)这个过程一直进行到查找成功或子表长度为0（说明线性表中没有这个元素）为止。77C78深度为5的满二叉树有__个叶子结点16797.8排序技术1.交换类排序2.插入类排序3.选择类排序冒泡排序法快速排序法简单插入排序法希尔排序法简单选择排序法堆排序法807.8.1交换类排序法所谓交换类排序法是指借助数据元素之间的互相交换进行排序的一种方法。本门课介绍冒泡排序法和快速排序法

811.冒泡排序法基本原理5个数7、5、6、3、2的排序过程如下：第1轮比较4次第2轮比较3次第3轮比较2次第4轮比较1次822.快速排序法从线性表中选取一个元素设为T，将线性表后面小于T的元素移到前面，而前面大于T的元素移到后面，结果就将线性表分成了两部分（称为两个子表），T插入到其分界线的位置处，这个过程称为线性表的分割。如果对分割后的各子表再按上述原则进行分割，并且，这种分割过程可以一直做下去，直到所有子表为空为止，则此时的线性表就变成了有序表。在表的第一，中间和最后一个元素取中项，设为P（K）并把它移动到表的第一个位置上。832.快速排序法无序线性表分割分割分割≥T≤TT图示842.快速排序法用快速排序法为以下7个数排序：49，38，65，97，76，13，27（1）令P（K）=49852.快速排序法49，38，65，97，76，13，2727，38，65，97，76，13，49

i=1，j=71227，38，49，97，76，13，65

i=3，j=734i=1j=7原27，38，13，97，76，49，65

i=3，j=627，38，13，49，76，97，65

i=4，j=6862.快速排序法经过几次交换，此时i=j，交换结束。此时，比P(k)小的数（27，38，13）都在它的前面，而比P(k)大的数（76，97，65）都在它的后面。与此同时，第一次分割结束。下面应该进行的是子表1（27，38，13）和子表2（76，97，65）的分割，方法同上。27，38，13，49，76，97，65

i=5，j=5无变化

877.8.2插入类排序假设线性表中前j-1个元素已经有序，现在要将第j个元素插入到前面的有序子表中的方法如下：①将第j个元素放到一个变量T中

②从有序子表的最后一个元素（即线性表中第j-1个元素）开始，往前逐个与T进行比较，将大于T的元素均依次向后移动一个位置，直到发现一个元素不大于T为止将T（即原线性表中的第j个元素）插入到刚移出的空位置上

此时有序子表的长度就变为j了。1.简单插入排序88简单插入排序举例3581015192438495722358101519222438495719<22897.8.2插入类排序先取一个小于n的整数h1作为第一个增量，把文件的全部记录分成h1个组。所有距离为h1的倍数的记录放在同一个组中。先在各组内进行直接插人排序取第二个增量h2<h1重复上述的分组和排序，直至所取的增量ht=1(dt<dt-l<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。增量序列一般取ht=n/2k(k=1，2，…，[1og2n])，其中n为待排序序列的长度。2.希尔排序90希尔排序举例092025153010911843670328原123