数据结构与算法

公共基础知识部分之第一章数据结构与算法1.1算法1.2数据结构的基本概念1.3线性表及其顺序存储结构1.4栈和队列1.5线性链表1.6树与二叉树1.7查找技术1.8排序技术1精选ppt课件1.1.1算法的基本概念

所谓算法是指解题方案的准确而完整的描述。1.1算法

1、算法的基本特征>可行性：算法原则上能够精确地执行，甚至人们只用笔和纸做有限次运算即可完成。>确定性：算法的每一步都必须有确切的定义>有穷性：一个算法必须在执行有穷步后结束，即算法必须能够终止>拥有足够的情报：我们要使算法有效就必须拥有足够的情报2精选ppt课件2、算法的基本要素>数据对象的运算和操作A.算术运算（+、-、*、/）B.逻辑运算（&、||、!）C.关系运算（>、<、=、#）D.数据传输（赋值、输入、输出）>算法的控制结构一个算法一般都可以用顺序、选择、循环三种基本控制结构组合而成。3精选ppt课件3、算法设计基本方法列举法：指针对待解决的问题，列举所有可能的情况，并用问题中给定的条件来检验。归纳法：特殊——一般的抽象过程递推：从已知初始条件出发，逐次推出所要求的各中间结构和最后结果递归：将复杂的问题逐层分解，最后归结为一个简单的问题，再沿原分解的逆过程逐步进行综合。分为直接递归和间接递归减半递推技术：把规模较大较复杂的问题，分成几个规模较小较简单的问题回溯法：通过对问题的分析，找出一个解决问题的线索，多次试探，若成功，则得出解，若失败，则回退，换别的路线再进行试探4精选ppt课件1.1.2算法复杂度算法的复杂度主要包括时间复杂度和空间复杂度。两者之间没有必然的联系。1、算法的时间复杂度

指执行算法所需要的计算工作量。工作量可以用算法在执行过程中所需基本运算的执行次数来度量。其中基本运算次数是问题规模的函数，即

算法的工作量=f(n)。>平均性态>最坏情况复杂性注意:算法程序执行的具体时间受使用计算机、程序设计语言以及算法实现过程中的许多细节的影响。而算法的时间复杂度与此无关5精选ppt课件2、算法的空间复杂度

指执行这个算法所需要的内存空间，包含：>算法程序所占的空间>输入的初始数据所占的空间>算法执行过程中所需要的额外空间6精选ppt课件1.2数据结构的基本概念

数据结构作为计算机的一门学科，主要研究以下三个方面的问题：（1）数据的逻辑结构（2）数据的存储结构(物理结构)（3）对各种数据结构进行的运算数据结构学科的研究目的：提高数据处理的效率。主要包括1、数据的处理速度2、尽量节省在数据处理过程中所占用的计算机存储空间

7精选ppt课件1.2.1数据结构的定义

数据处理：是指对数据集合中的各元素以各种形式进行运算。包括插入、删除、查找、更改等运算，也包括对数据元素进行分析。

数据元素：在数据处理领域中，每一个需要处理的对象都可以抽象为数据元素。

数据结构：是指反映数据元素之间关系的数据元素集合的表示。数据元素之间的任何关系都可以用前后件关系来描述。8精选ppt课件1、数据的逻辑结构

所谓逻辑结构实际上就是指数据元素之间的前后件关系。其中前后件关系是指它们的逻辑关系，而与他们在计算机中的存储位置无关。它包含两个要素：数据元素的集合，通常记为D；数据元素之间的关系（前后件关系），通常记为R。形式表示如下：

B=（D，R）其中B表示数据结构

9精选ppt课件2、数据的存储结构

数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构（即数据的物理结构）。常用的存储结构有顺序、链接、索引等存储结构。

10精选ppt课件1.2.2数据结构的图形表示

图形表示方法：对于数据集合D中的每一个数据元素用中间标有元素值的方框表示，一般称为数据结点，简称结点，对关系R中每一个二元组，用一条有向线段从前件指向后件结点，以表示数据之间的前后件关系。

春夏冬秋父亲儿子女儿图1.2一年四季数据结构的图形表示图1.3家庭成员辈分关系的数据结构的图形表示11精选ppt课件例1.2用图形表示数据结构B=(D,R),其中：D={di|1<=i<=6}={d1,d2,d3,d4,d5,d6}R={(d1,d2),(d1,d3),(d3,d4),(d5,d4),(d5,d6)}d1d3d5d2d6d4图1.4数据结构的图形表示12精选ppt课件1.2.3线性结构与非线性结构如果一个数据结构中一个数据元素都没有，则称为数据结构为空的数据结构。在一个空的数据结构中插入一个元素后就变成了非空。根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分为两大类：线性结构（又称为线性表）非线性结构线性结构满足如下两个条件：（1）、有且只有一个根结点；（2）、每一个结点最多有一个前件，也最对多有一个后件。在一个线性结构中插入或删除任何一个结点还是线性结构常见的线性结构：线性表、栈、队列、线性链表常见的非线性结构：树、二叉树、图

13精选ppt课件1.3线性表及其顺序存储结构

1.3.1线性表的基本概念

线性表是n个元素的有限序列，它们之间的关系可以排成一个线性序列：a1，a2，……，ai，……，an其中n称作表的长度，当n=0时，称作空表。n(n>=0)，表中的每一个数据元素，除了第一个外，有且只有一个前件，除了最后一个外，有且只有一个后件。14精选ppt课件

1.3.2线性表的顺序存储结构

线性表的顺序存储结构有以下两个基本特点：（1）线性表中所有元素所占的存储空间是连续的；（2）线性表中各数据元素在存储空间中是按逻辑顺序依

次存放的。逻辑上相邻的结点，物理位置上也相邻在程序设计语言中，通常定义一个一维数组来表示线性表的顺序存储空间，该一维数组的长度通常要定义得比线性表的实际长度大一些，以便对线性表进行各种运算，特别是插入运算。

线性表的主要操作有：

（1）插入、（2）删除、（3）查找、（4）排序、（5）分解、（6）合并、（7）复制、（8）逆转。15精选ppt课件元素an……..元素ai……..元素a2元素a1bb+mb+(i-1)*mb+(maxlen-1)*m存储地址内存状态Loc(元素i)=b+（i-1)*m顺序存储结构示意图(顺序表)：首地址起始地址基地址每个元素所占用的存储单元个数16精选ppt课件1.4栈和队列

1.4.1栈及其基本运算

1、栈（stack）的定义栈是限定在一端进行插入和删除的线性表。性质：a.按照“先进后出”（FILO–firstinlastout)或“后进先出”（LIFO—lastinfirstout)的原则组织数据。b.通常用指针top来指示栈顶的位置，用指针bottom指向栈底。c.当表中没有元素时称栈为空栈d.栈具有记忆功能e.往栈中插入一个元素称为入栈运算，从栈中删除一个元素（即删除栈顶元素）称为退栈运算。Top栈顶指针反映了栈中元素的变化17精选ppt课件2、栈的顺序存储及其运算在程序设计语言中，一般用一维数组S(1:m)作为栈的顺序存储空间，其中m为栈的最大容量。在S(1:m)中，S(bottom)通常为栈底元素（在栈非空的情况下），S(top)为栈顶元素。top=0表示栈空；top=m表示栈满。栈的基本运算有3种：入栈运算退栈运算读栈顶元素栈中的运算：1.设置空栈；2.插入一个新的栈顶元素3.删除栈顶元素；4.读取栈顶元素。18精选ppt课件

1.4.2队列及其基本运算

1、队列（queue）的定义

队列是允许在一端(队尾rear)进行插入、而在另一端(队头front)进行删除的线性表。它按照“先进先出”（FIFO–firstinfirstout)或“后进后出”（LILO—lastinlastout)的原则组织数据。

a1,

a2,

a3,

a4,…………

an-1,

an队列示意图队头队尾frontrear19精选ppt课件

举例1：到医院看病，首先需要到挂号处挂号，然后，按号码顺序救诊。举例2：乘坐公共汽车，应该在车站排队，车来后，按顺序上车。

20精选ppt课件队列是指允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表。Rear指针指向队尾，front指针指向队头。队列是“先进先出”（FIFO）或“后进后出”（LILO）的线性表。队列运算包括（1）入队运算：从队尾插入一个元素；（2）退队运算：从队头删除一个元素。循环队列:在循环队列中，用队尾指针r指向队尾，用排头指针f指向队头的前一个位置

*循环对队中的元素的个数=rear-front(r>f)=rear-front+容量(r<f)m=50r=20f=3521精选ppt课件线性表的链式存储结构简称线性链表

线性表的链式存储结构是指用一组任意的存储单元（可以连续，也可以不连续）存储线性表中的数据元素。因此，链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示数据元素间的逻辑关系，对于每个数据元素不仅要表示它的具体内容，还要附加一个表示它的直接后继元素存储位置的信息。这个信息称为指针(pointer)或链(link)。这两部分组成了链表中的结点结构：

datalink指针域，用来存放结点的直接后继的地址数据域，用来存放结点的值

将线性表的元素放到一个具有头指针的链表中，链表中每个结点包含数据域和指针域。

数据域存放数据，指针域存放后继结点的地址，最后一个结点的指针域为空。逻辑上相邻的数据元素在内存中的物理存储空间不一定相邻。1.5线性链表

22精选ppt课件例如：线性表（a,b,c,d)23精选ppt课件

术语表示每个数据元素的两部分信息组合在一起被称为结点；其中表示数据元素内容的部分被称为数据域（data）；表示直接后继元素存储地址的部分被称为指针或指针域（next）。

headd^

cba单链表结构示意图datalink24精选ppt课件其中，head是头指针，它指向单链表中的第一个结点，这是单链表操作的入口点。由于最后一个结点没有直接后继结点，所以，它的指针域放入一个特殊的值NULL。NULL值在图示中常用（^）符号表示。带头结点的单链表为了简化对链表的操作，人们经常在链表的第一个结点之前附加一个结点，并称为头结点。这样可以免去对链表第一个结点的特殊处理。如下图所示：带头结点的单链表结构示意图head^空表headd^

cba25精选ppt课件110hat200130cat135135eat170160matnil165bat130170fat110200jat205205lat160165head头指针数据域指针域例如：线性表（bat,cat,eat,fat,hat,jat,lat,mat）单链表只注重结点的逻辑顺序，不关心每个结点的实际存储位置，因此用箭头来表示链域中的指针。batcateatmat∧head26精选ppt课件1.6树和二叉树

1.6.1树的基本概念

树是一种简单的非线性结构，由一个或多个结点组成的有限集合。仅有一个根结点，结点间有明显的层次结构关系。现实世界中，能用树的结构表示的例子：学校的行政关系、书的层次结构、人类的家族血缘关系等。27精选ppt课件树形结构全校学生档案管理的组织方式28精选ppt课件(C)是有13个结点的树，其中A是根，其余结点分成3个子集：T1

、T2、T3。都是根A的子树，且本身也是一棵树。例如：T1其根为B，两棵子树为T11={F}T12={E,K,L}，T12又是一棵子树，树根为F，{K}和{L}是E的两个互不相交的子集。29精选ppt课件结点：数据元素的内容及其指向其子树根的分支统称为结点。结点的度（Degree):结点的分支数，即结点拥有的子树数。终端结点（叶子leaf）:度为0的结点。非终端结点:度不为0的结点。结点的层次:树中根结点的层次为1，根结点子树的根为第2层，以此类推。树的度:树中所有结点度的最大值。树的深度:树中所有结点层次的最大值。有序树、无序树:如果树中每棵子树从左向右的排列拥有一定的顺序，不得互换，则称为有序树，否则称为无序树。术语30精选ppt课件

相关概念：父结点、根结点、子结点、叶子结点、结点的度、树的度、树的深度、子树。

A

C

GT2D

HIT3J

M

BEL

KT1F31精选ppt课件

1.6.2二叉树及其基本性质1、什么是二叉树

二叉树具有以下两个特点：（1）非空二叉树只有一个根结点；（2）每一个根结点最多只有两棵子树，且分别为该结点的左子树和右子树。（子树有左右之分，左右树不能互换）32精选ppt课件二叉树的五种基本形态空二叉树仅有根结点右子树为空左子树为空左右子树均非空两棵不同的二叉树33精选ppt课件2、二叉树的基本性质

（1）在二叉树的K层上，最多有2k-1(k>=1)个结点；（2）深度为m的二叉树最多有2m-1个结点；（3）在任意一棵二叉树中，度为0的结点（即叶子结点）总是比度为2的结点数多一个；（4）具有n个结点的二叉树，其深度至少为[log2n]+1，其中[log2n]表示取不大于log2n的最大整数。[2007.9.8]题：一棵二叉树中共有70个叶子结点和80个度为1的结点，则二叉树中总结点数为：A.219B.221C.229D.23134精选ppt课件3、满二叉树和完全二叉树

（1）满二叉树除最后一层外，每一层上的所有结点都有两个子结点。即在第K层上有2k-1个结点。深度为m的满二叉树有2m-1个结点423167891011121314155特点：每一层上都含有最大结点数。35精选ppt课件（2）完全二叉树除最后一层外，每一层上的结点数都达到最大值；在最后一层上只缺少右边的若干结点。423167891011125

非完全二叉树423167891011125

完全二叉树特点：除最后一层外，每一层都取最大结点数，最后一层结点都集中在该层最左边的若干位置。36精选ppt课件891011124567231789456231

456231一棵满二叉树一定是一棵完全二叉树，而一棵完全二叉树不一定是满二叉树。37精选ppt课件2i+2

2i2i+12i+22i+3i+12i2i+1i

i

i+1另：性质：完全二叉树中度为1的结点数为0或1完全二叉树总数为奇数时，度为1的结点数为0为偶数时，度为1的结点数为138精选ppt课件

1.6.4二叉树的遍历所谓遍历二叉树就是按某种顺序访问二叉树中的每个结点一次且仅一次的过程。这里的访问可以是输出、比较、更新、查看元素内容等等各种操作。1、前序遍历（DLR）若二叉树为空，则结束遍历操作；否则访问根结点，按前序遍历左子树，按前序遍历右子树。2、中序遍历（LDR）若二叉树为空，则结束遍历操作；否则按中序遍历左子树，访问根结点，按中序遍历右子树。3、后序遍历（LRD）若二叉树为空，则结束遍历操作；否则按后序遍历左子树，按后序遍历右子树，访问根结点。39精选ppt课件GHBCADEF先序序列： ABDGCEFH 中序序列： DGBAECHF 后序序列： GDBEHFCA 先序：DLR中序：LDR后序：LRD40精选ppt课件ACEFGBH