公共基础数据结构

《公共基础数据结构》由会员分享，可在线阅读，更多相关《公共基础数据结构（46页珍藏版）》请在金锄头文库上搜索。

1、2003.11.,全国计算机等级考试 二级公共基础知识 数据结构,考试大纲,1.算法的基本概念；算法复杂度的概念和意义（时间复杂度与空间复杂度）。 2.数据结构的定义；数据的逻辑结构与存储结构；数据结构的图形表示；线性结构与非线性结构的概念。 3.线性表的定义；线性表的顺序存储结构及其插入与删除运算。 4.栈和队列的定义；栈和队列的顺序存储结构及其基本运算。 5.线性单链表、双向链表与循环链表的结构及其基本运算。 6.树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历。 7.顺序查找与二分法查找算法；基本排序算法（交换类排序，选择类排序，插入类排序）。,1.1算法,1.1.1

2、 算法的基本概念 算法：是指解题方案的准确而完整的描述。 算法不等于程序，也不等于计算机方法，程序的编制不可能优于算法的设计。 1、算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。,1.1算法,特征包括： （1）可行性； （2）确定性，算法中每一步骤都必须有明确定义，不允许有模棱两可的解释，不允许有多义性； （3）有穷性，算法必须能在有限的时间内做完，取能在执行有限个步骤后终止，包括合理的执行时间的含义； （4）拥有足够的情报。,1.1算法,2、算法的基本要素： 一是对数据对象的运算和操作； 二是算法的控制结构。 （1）算法中对数据的

3、运算和操作 指令系统：一个计算机系统能执行的所有指令的集合。 基本运算和操作包括：算术运算、逻辑运算、关系运算、数据传输。,1.1算法,（2）算法的控制结构： 一个算法的功能不仅取决于所选用的操作，而且还与各操作之间的执行顺序有关。算法中各操作之间的执行顺序称为算法的控制结构。 描述算法的工具通常有传统流程图、NS结构化流程图、算法描述语言等。 一个算法一般都可以用顺序、选择、循环三种基本控制结构组合而成。,1.1算法,1.1.2算法的复杂度 算法复杂度：算法时间复杂和算法空间复杂度。 1.算法的时间复杂度 算法时间复杂度是指执行算法所需要的计算工作量。 算法的工作量用算法所执行的基本运算次数

4、来度量，而算法所执行的基本运算次数是问题规模的函数，即算法的工作量=f(n),1.1算法,2.算法空间复杂度 算法空间复杂度是指执行这个算法所需要的内存空间。一个算法所占用的存储空间包括算法程序所占的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。,1.2数据结构的基本概念,数据结构研究的三个方面： （1）数据集合中和数元素之间所固有的逻辑关系，即数据的逻辑结构； （2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构； （3）对各种数据结构进行的运算。 讨论以上问题的主要目的是为了提高数据的效率。所谓提高数据处理的效率，主要包括两个方面：一是提高数据

5、处理的速度，二是尽量节省在数据处理过程中所占用的计算机存储空间。,1.2.1什么是数据结构 数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。 1、数据的逻辑结构 数据的逻辑结构是指数据元素之间的逻辑关系的描述。 （1）线性结构：线性表、栈、队、字符串、数组、广义表； （2）非线性结构：树、图。,2、数据的存储结构（又称物理结构）数据的存储结构是数据的逻辑结构在计算机存储空间中的存放形式（存储映像），包括数据元素的表示和关系的表示。,在复杂线性表中，线性表是N个类型相同的数据元素的有限序列，如由若干数据项组成的数据元素称为记录，而由多个记录构成的线性表又称为文件。 非空线性表的结构特

6、征： （1）有且只有一个根结点a1，它无前件； （2）有且只有一个终端结点an，它无后件； （3）除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。结点个数n称为线性表的长度，当n=0时，称为空表。,13 线性表及其顺序存储结构,线性表的顺序存储结构具有以下两个基本特点： （1）线性表中所有元素的所占的存储空间是连续的； （2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。 ai的存储地址为：ADR(ai)=ADR(a1)+(i-1)k,，ADR(a1)为第一个元素的地址，k代表每个元素占的字节数。,线性表的顺序存储结构,顺序表的基础要点,1、线性表是具有n个数据

7、元素的有限序列。 2、线性表的顺序存储结构具有三个弱点： 在插入和删除时，需移动大量元素 由于难以估计，必须预先分配较大的空间 表的容量难以扩充 (如何解决？） 3、顺序存储结构通过元素的相对存储地址来表示元素之间的关系 4、线性表顺序存储的优点是可随机存取元素。 5、顺序表中逻辑上相邻的元素的物理位置必定紧邻。 6、顺序表是一种随机存取的存储结构。 7、在顺序表中插入或删除一个元素时，需要平均移动表的一半元素，具有移动的元素个数与该元素的位置有关。 8、在长度为n的顺序表中插入一个元素的时间复杂度为O(n)，删除一个元素的时间复杂度为O(n)。,栈,是一种特殊的线性表。其特殊性在于限定插入和

8、删除数据元素的操作只能在线性表的表尾端进行。如下所示：进行插入和删除的表尾端是浮动端，通常被称为栈顶， an 为栈顶元素， 并用一个“栈顶指针”指示；而表头端是固定端，通常被称为栈底， a1 为栈底元素，。我们经常将栈用下图的形式描述：,a1, a2, a3, ., an 插入和删除端,栈的基本运算,栈的基本运算： （1）插入元素称为入栈运算； （2）删除元素称为退栈运算； （3）读栈顶元素是将栈顶元素赋给一个指定的变量，此时指针无变化,栈顶指针和栈中元素之间的关系,A,A,B,C,D,E,base=top 空栈,top 指向栈顶元素的下一个位置,当base= 时，表明栈结构不存在。,队列及其

9、基本运算,队列(Queue)也是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为队头(front)，允许插入的一端称为队尾(rear)。例如：排队购物。操作系统中的作业排队。先进入队列的成员总是先离开队列。因此队列亦称作先进先出(First In First Out)的线性表，简称FIFO表。当队列中没有元素时称为空队列。在空队列中依次加入元素a1,a2,an之后，a1是队头元素，an是队尾元素。显然退出队列的次序也只能是a1,a2,an ，也就是说队列的修改是依先进先出的原则进行的。,下图是队列的示意图：a1 a2 an插入端和删除端都是浮动的。通常我

10、们将插入端称为队尾，用一个“队尾指针”指示；而删除端被称为队头，用一个“队头指针”指示。结论：先进先出（First In First Out），简称为FIFO线性表。,出队,入队,队列是指允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表。Rear指针指向队尾，front指针指向队头。 队列是“先进行出”（FIFO）或“后进后出”（LILO）的线性表。 队列运算包括（1）入队运算：从队尾插入一个元素；（2）退队运算：从队头删除一个元素。 循环队列：s=0表示队列空，s=1且front=rear表示队列满,链式存储结构的特点（1）线性表中的数据元素在存储单元中的存放顺序与逻辑顺序不一

11、定一致； （2）在对线性表操作时，只能通过头指针进入链表，并通过每个结点的指针域向后扫描其余结点，这样就会造成寻找第一个结点和寻找最后一个结点所花费的时间不等，具有这种特点的存取方式被称为顺序存取方式。,树与二叉树,树是一种简单的非线性结构，所有元素之间具有明显的层次特性。在树结构中，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称树的根。每一个结点可以有多个后件，称为该结点的子结点。没有后件的结点称为叶子结点。在树结构中，一个结点所拥有的后件的个数称为该结点的度，所有结点中最大的度称为树的度。树的最大层次称为树的深度。,(C)是有13个结点的树，其中A是根，其

12、余结点分成3个子集： T1 、T2 、T3 。都是根A的子树，且本身也是一棵树。例如： T1 其根为B，两棵子树为 T11 = F T12 = E, K, L ， T12 又是一棵子树，树根为F，K 和 L是E的两个互不相交的子集。,树的有关术语,结点：包含一个数据元素及若干指向其他结点的分支信息 结点的度：一个结点的子树的个数 叶结点：度为0的结点，即无后继的结点 分支结点：度不为0的结点 结点的层次：从根结点开始定义，根结点的层次为1 结点的层序编号：将树中的结点按从上层到下层、同层从左到右的次序排列，依次给他吗编以连续的自然数 树的度：树中所有结点的度的最大值 树的高度（深度）：树中所有

13、结点的层次的最大值 有序树：在树T中，如果各子树Ti之间是有先后次序的，则称为有序树 森林：m棵互不相交的树的集合。,二叉数,每个结点的度都不大于2 每个结点的孩子结点次序不能任意颠倒，且分别称为该结点的左子树与右子树。 二叉树的五种基本形态,G H,D E F,B C,A,二叉树的基本性质：,（1）在二叉树的第k层上，最多有2k-1(k1)个结点； （2）深度为m的二叉树最多有2m-1个结点； （3）度为0的结点（即叶子结点）总是比度为2的结点多一个； （4）具有n个结点的二叉树，其深度至少为log2n+1,其中log2n表示取log2n的整数部分； （5）具有n个结点的完全二叉树的深度为l

14、og2n+1；,满二叉树是指除最后一层外，每一层上的所有结点有两个子结点，则k层上有2k-1个结点深度为m的满二叉树有2m-1个结点。完全二叉树是指除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。,一棵满二叉树一定是一棵完全二叉树，而一棵完全二叉树不一定是满二叉树。,完全二叉树的特点：（1）叶子结点只可能在层次最大的两层上出现（2）对任意结点，若其右分支下的子孙的最大层次是l ，则其左分支下的子孙的最大层次必是l 或l+1,2i +2,2i 2i+1 2i+2 2i+3 i+1 2i 2i+1,i,i i+1,（6）设完全二叉树共有n个结点。如果从根结点开始，按层

15、序（每一层从左到右）用自然数1，2，.n给结点进行编号（k=1,2.n），有以下结论：若k=1，则该结点为根结点，它没有父结点；若k1，则该结点的父结点编号为INT(k/2)；若2kn，则编号为k的结点的左子结点编号为2k；否则该结点无左子结点（也无右子结点）；若2k+1n，则编号为k的结点的右子结点编号为2k+1；否则该结点无右子结点。,a,b,c,d,e,f,g,h,i,j,k,l,完全二叉树,1 2 3 4 5 6 7 8 9 10 11 12,二叉的遍历二叉树是一种非线性的数据结构，在对它进行操作时，总是需要逐一对每个数据元素实施操作，这样就存在一个操作顺序问题，由此提出了二叉树的遍历

16、操作。所谓遍历二叉树就是按某种顺序访问二叉树中的每个结点一次且仅一次的过程。这里的访问可以是输出、比较、更新、查看元素内容等等各种操作。 二叉树的遍历方式分为两大类：一类按根、左子树和右子树三个部分进行访问；另一类按层次访问。下面我们将分别进行讨论。,1. 按根、左子树和右子树三部分进行遍历遍历二叉树的顺序存在下面6种可能：TLR（根左右）, TRL（根右左） LTR（左根右）, RTL（右根左）LRT（左右根）, RLT（右左根）其中，TRL、RTL和RLT三种顺序在左右子树之间均是先右子树后左子树，这与人们先左后右的习惯不同，因此，往往不予采用。余下的三种顺序TLR、LTR和LRT根据根访问的位置不同分别被称为先序遍历、中序遍历和后序遍历。,