《二级公共基础知识》由会员分享，可在线阅读，更多相关《二级公共基础知识（117页珍藏版）》请在金锄头文库上搜索。
1、1,二级公共基础知识,第一章 数据结构基础,2,内容提要,算法:算法的基本概念、算法复杂度数据结构的基本概念：什么是数据结构、 数据结构的图形表示、 线性结构与非线性结构线性表及其顺序存储结构：线性表的基本概念、 顺序存储结构、插入运算、删除运算栈和队列：栈及其基本运算、队列及其基本运算线性链表：基本概念、基本运算、循环链表及其基本运算树与二叉树：树的基本概念、二叉树及其基本性质、 二叉树的存储结构、二叉树的遍历查找技术： 顺序查找、二分法查找排序技术：交换类排序法、 插入类排序法、选择类排序法,3,1.1 算法,4,1.1.1 算法的基本概念,算法是解题方案的准确而完整的描述，它不等于程序，
2、也不等计算方法。1算法的基本特征可行性(effectiveness)确定性(definiteness)有穷性(finiteness)拥有足够的情报2算法的基本要素算法中对数据的运算和操作算术运算:包括加、减、乘、除等）逻辑运算:包括“与”、“或”、“非”等运算）关系运算:包括“大于”、“小于”、“等于”、“不等于”等）数据传输:包括赋值、输入、输出等操作算法的控制结构,5,1.1.1 算法的基本概念,3算法设计的基本方法列举法归纳法递推递归减半递推技术回溯法,6,1.1.2 算法复杂度,算法复杂度：时间复杂度、空间复杂度1算法的时间复杂度执行算法所需要的计算工作量与下列因素有关：书写算法的程序
3、设计语言编译产生的机器语言，代码质量机器执行指令的速度问题的规模,7,1.1.2 算法复杂度,问题的规模函数算法的工作量=f(n)算法中基本操作重复执行的频率T(n)，是问题规模n的某个函数f(n)，记作：T(n)=O(f(n)记号“O”读作“大O”。表示随问题规模n的增加，算法执行时间的增长率和f(n)相应增加。常见算法复杂度：O(1)：常数阶 O(n)：作线性阶 O(n2)：平方阶O(n3)：立方阶 O(logn)：对数阶 O(2n)：指数阶,8,1.1.2 算法复杂度,nn矩阵相乘算法：时间复杂度为O(n3)。,9,1.1.2 算法复杂度,分析算法的工作量两种方法：平均性态最坏情况复杂性
4、,10,1.1.2 算法复杂度,2算法的空间复杂度算法执行过程中所需的最大存储空间存储量包括以下三部分算法程序所占的空间输入的初始数据所占的存储空间算法执行过程中所要的额外空间算法空间复杂度可定义为：S(n)=O(f(n)原地工作(in place)的算法：记作O(1)压缩存储技术,11,1.2 数据结构的基本概念,12,1.2.1 什么是数据结构,1数据结构研究的主要内容数据的逻辑结构数据的存储结构对各种数据结构进行的运算2研究数据结构目的提高数据处理的速度尽量节省在数据处理过程中所占用的计算机存储空间,13,1.2.1 什么是数据结构,1数据结构研究的主要内容数据的逻辑结构数据的存储结构对
5、各种数据结构进行的运算2研究数据结构目的提高数据处理的速度尽量节省在数据处理过程中所占用的计算机存储空间,14,1.2.1 什么是数据结构,15,1.2.1 什么是数据结构,3数据结构的定义相互有关联的数据元素的集合数据元素之间的关系可以用前后件关系来描述一个数据结构应包含以下两方面信息：表示数据元素的信息 表示各数据元素之间的前后件关系,16,1.2.1 什么是数据结构,4数据的逻辑结构对数据元素之间的逻辑关系的描述只抽象地反映数据元素之间的逻辑关系，与计算机中的存储无关两个要素：数据元素的集合，通常记为D；前后件关系，通常记为R一个数据结构B可以表示为：B=（D，R）,17,1.2.1 什
6、么是数据结构,5数据的存储结构数据的逻辑结构在计算机存储空间中的存放形式，它包括数据元素的存储方式和关系的存储方式。常用的存储结构：顺序链式索引一种数据结构可根据需要采用不同的存储结构。采用不同的存储结构，其数据处理的效率是不同,18,1.2.2 数据结构的图形表示,数据结点：用方框表示根结点、终端结点前后件关系：用有向线段表示基本运算：插入运算删除运算查找、分类、合并、分解、复制、修改、,19,1.2.3 线性结构与非线性结构,空的数据结构：一个数据元素都没有线性结构如果一个非空数据结构满足下列两个条件：有且只有一个根结点；每一个结点最多有一个前件，也最多有一个后件。常见的线性结构有：线性表
7、、栈与队列、线性链表非线性结构如果一个数据结构不是线性结构常见的非线性结构有：树、二叉树、图,20,1.3 线性表及其顺序存储结构,21,1.3.1 线性表的基本概念,线性表：由n(n0)个相同类型数据元素构成的有限序列：n定义为线性表的表长；n=0 时的线性表被称为空表。称i为在线性表中的位序。例如：英文大写字母表（A，B，C，D，E，F，X，Y，Z）同一花色的13张扑克牌 (2,3,4,5,6,7,8,9,10,J,Q,K,A),22,1.3.1 线性表的基本概念,线性表的结构特征数据元素在表中的位置由序号决定，数据元素之间的相对位置是线性的；对于一个非空线性表，有且只有一个根结点a1，它
8、无前件，有且只有一个终端结点an，它无后件，除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。线性表的存储结构顺序存储链式存储,23,1.3.2 线性表的顺序存储结构,两个基本特点：线性表中所有元素所占的存储空间是连续的。线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。存储示意图,24,1.3.3 顺序表的插入运算,25,1.3.4 顺序表的删除运算,26,顺序表的插入和删除分析,插入算法的分析假设线性表中含有n个数据元素，在进行插入操作时，若假定在n+1个位置上插入元素的可能性均等，则平均移动元素的个数为：删除算法的分析在进行删除操作时，若假定删除每个元素的可能性
9、均等，则平均移动元素的个数为：分析结论顺序存储结构表示的线性表，在做插入或删除操作时，平均需要移动大约一半的数据元素。当线性表的数据元素量较大，并且经常要对其做插入或删除操作时，这一点需要值得考虑,27,1.4 线性链表,28,1.4.1 线性链表的基本概念,1线性表顺序存储的缺点插入或删除的运算效率很低。在顺序存储的线性表中，插入或删除数据元素时需要移动大量的数据元素。线性表的顺序存储结构下，线性表的存储空间不便于扩充。线性表的顺序存储结构不便于对存储空间的动态分配。,29,1.4.1 线性链表的基本概念,2线性链表线性表的链式存储结构物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺
10、序是通过链表中的指针链接来实现的每个结点由两部分组成：数据域和指针域,30,1.4.1 线性链表的基本概念,双向链表：每个结点设置两个指针左指针：指向其前件结点右指针：指向其后件结点,31,1.4.2 线性链表的基本运算,插入删除合并分解逆转复制排序查找,32,1.4.2 线性链表的基本运算,1在线性链表中查找指定元素链表不是随机存取结构从链表的头指针出发，顺着链域next逐个结点往下搜索，直至搜索到第i个结点为止2线性链表的插入,33,1.4.2 线性链表的基本运算,3线性链表的删除与顺序存储相比，链表的优点有：插入和删除元素时，不需要移动数据元素，只需要修改指针即可,34,1.4.3 双向
11、链表,双向链表：每个结点设置两个指针左指针：指向其前件结点右指针：指向其后件结点,35,1.4.4 循环链表及其基本运算,循环链表特点：在链表中增加了一个表头结点最后一个结点的指针域指向表头结点，构成了一个环状链循环链表优点：从任一结点出发来访问表中其他所有结点空表与非空表的运算的统一,36,1.5 栈和队列,37,1.5.1 栈及其基本运算,1栈的定义栈（stack）：一种只允许在表的一端进行插入或删除操作的特殊的线性表栈顶(top) ：允许进行插入与删除操作的一端栈底(bottom)：不允许插入与删除操作的另一端先进后出（FILO）或后进先出(LIFO)的线性表,38,1.5.1 栈及其基
12、本运算,2栈的顺序存储及其运算top=0：栈空 top=m：栈满栈的基本运算 入栈运算退栈运算读栈顶元素,39,1.5.1 栈及其基本运算,3栈的链式存储结构链栈,40,1.5.2 队列及其基本运算,1队列的定义限定只能在表的一端进行插入和在另一端进行删除操作的线性表队尾(rear)：允许插入的一端队头(front)：允许删除的另一端先进先出（FIFO）表或后进后出（LILO）线性表基本操作入队运算：往队列的队尾插入一个元素，队尾指针rear的变化退队运算：从队列的排头删除一个元素，队头指针front的变化,41,1.5.2 队列及其基本运算,2循环队列及其运算队列存储空间的最后一个位置绕到第
13、一个位置，形成逻辑上的环状空间，供队列循环使用 入队运算 ：队尾指针加1，并当rear=m+1时置rear=1出队运算：队头指针加1，并当front=m+1时置front=1,42,1.5.2 队列及其基本运算,3队列链式存储结构链队列,43,1.6 树与二叉树,44,1.6 树与二叉树,1树的定义树(Tree)是n(n0)个结点的有限集T，T为空时称为空树，否则它满足如下两个条件：（1）有且仅有一个特定的称为根(Root)的结点；（2）其余的结点可分为m(m0)个互不相交的子集T1，T2，T3，Tm，其中每个子集又是一棵树，并称其为子树。,45,1.6 树与二叉树,2树中的基本概念父结点与树
14、的根：每个结点最多只允许有一个前件，称为该结点的父结点。没有前件的结点中有一个，称为树的根结点。子结点与叶子结点：在树结构中，每一个结点可以有多个后件，它们都称为该结点的子结点。没有后件的结点称为叶子结点。结点的度和树的度：一个结点所拥有后件个数称为该结点的度。一棵树中各个结点度数的最大值叫做这棵树的度。层和树的深度：树结构是一种层次结构，根结点为第一层，根的子结点为第二层，其余各结点的层数逐层由上而下计算。一棵树中结点的最大层数叫做此树的深度。,46,1.6.1 树的基本概念,树的特点（1）树中只有根结点没有前件；（2）除根外，其余结点都有且仅一个前件；（3）树的结点，可以有零个或多个后件；
15、（4）除根外的其他结点，都存在唯一条从根到该结点的路径；（5）树是一种分支结构（除根的结点外）每个元素都有且仅有一个直接前件，有且仅有零个或多个直接后件。树的存储用多重链表来表示,47,1.6.2 二叉树及其基本性质,1二叉树的定义一个二叉树是n个结点的有限集合（n0），此集合或者是空集（n=0），或者是由一个根结点及两棵互不相交的、分别称为左子树和右子树的二叉树组成，并且左右子树都是二叉树。特点：非空二叉树只有一个根结点；每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。,48,1.6.2 二叉树及其基本性质,2二叉树的性质性质1 在二叉树的第k层上，最多有 个结点。性质2 深度为m的二叉树最多有个 结点。性质3 在任意一棵二叉树中，度数为0的结点（即叶子结点）总比度为2的结点多一个。即： 其中，n0表示度数为0的结点数，n2表示度数为2的结点数。性质4 具有n个结点的二叉树的深度至少为 ，其中 表示取 的整数部分。,49,1.6.2 二叉树及其基本性质,
