二级vfp 算法与数据结构基础.ppt

《二级vfp 算法与数据结构基础.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、二级教程－计算机公共基础全国计算机等级考试（新大纲）应试用书全国计算机等级考试管群主编第1章算法与数据结构基础1.1算法的基本概念1.2数据结构基础1.3线性表1.4栈和队列1.5树1.6排序1.7查找1.1算法的基本概念算法的定义：一个有穷的指令集，这些指令为解决某一特定问题规定了一个运算序列，即方法和步骤，在计算机学科中，算法就是计算机解决问题的过程或步骤。结构化程序算法的特性如下。（1）输入（2）输出（3）确定性（4）有穷性（5）有效性算法复杂度通常采用由德国数学家PaulBachmann在1892年提出的“大O表达式”表述，该符号以大写字

2、母O带一对小括号括起的一个表达式构成。一般描述算法复杂度时括号里用N的简单函数表示，如O(N2)（读作：ON大平方）。算法的时间复杂度指算法的时间耗费，算法时间是由控制结构和原操作的决定的。算法中基本操作重复执行的次数是问题规模n的某个函数f(n)，记作：T(n)=O(f(n))它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同。算法的空间复杂度描述算法的存储空间需求，运行完一个程序所需要的内存大小是问题规模n的某个函数g(n)，记作：S(n)=O(g(n))它表示随着问题规模n的增大，算法运行所需存储空间的增长率S(n)与g(

3、n)的增长率相同。1.2数据结构基础数据：数据是信息的载体，是描述客观事物的数、字符，以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合。数据包括数值性数据和非数值性数据。数据元素（也称为元素、接点、顶点、记录）：数据元素是数据的基本单位。一个数据元素可以由若干个数据项组成。数据项：数据项是具有独立含义的最小标识单位。数据对象：数据的子集，是具有相同性质的数据成员（数据元素）的集合。数据结构的定义：数据结构是指数据之间的相互关系，即数据的组织形式，由某一数据对象及该对象中所有数据成员之间的关系组成，记为：Data_Structure={

4、D,R}，其中D是某一数据对象，R是该对象中所有数据成员之间的关系的有限集合。它包括逻辑结构、存储结构和数据的运算3个方面的内容。数据的逻辑结构：用来描述数据元素之间的逻辑关系。数据的存储结构：用来描述数据元素及数据元素之间的关系在存储器中的存储形式。数据的运算：即对数据元素施加的操作。数据结构的图形表示：用图形来直观地表示数据及其之间的关系。图1-1数据结构的图形表示数据的逻辑结构分为线性结构和非线性结构两类：线性结构：数据元素之间构成一种顺序的线性关系，如图1-2所示。线性结构包括线性表、堆栈、队列和串。图1-2数据元素的线性关系线性结构的特

5、征有：（1）集合中必存在惟一的一个“第一元素”；（2）集合中必存在惟一的一个“最后元素”；（3）除最后的元素之外，均有惟一的后继；（4）除第一元素之外，均有惟一的前驱。非线性结构是指不满足以上条件的存储结构。非线性结构包括树、二叉树、图（或网络）和广义表。1.3线性表1.3.1线性表的顺序存储结构线性表是最常用且最简单的一种数据结构。采用顺序存储结构的线性表也叫做顺序表，如n个元素的线性表可以记为：L=（a1，a2，…，an）。图1-3顺序表顺序表有插入和删除两种基本操作。图1-4顺序表的插入1.3.2线性表的链式存储结构链式存储是指用一组地址任

6、意的存储单元存放线性表中的数据元素。链式存储采用结点来表示数据元素。一个结点由两个部分构成：数据域和指针域。（1）单链表及其基本操作图1-5单链表图1-6单链表的插入图1-7单链表的删除（2）双向链表及其基本操作图1-8双向链表的插入1.4栈和队列1.4.1栈及其基本操作栈是规定只能在表的一端进行插入和删除的线性表。允许插入和删除的一端称为栈顶，另一端称为栈底。当表中没有元素时称为空栈。由于栈的插入和删除运算仅在栈顶一端进行，后进栈的元素必定先被删除，所以又把栈称为后进先出（Last_In_First_Out，简称LIFO）表。栈有插入（即进栈）

7、和删除（即出栈）两种基本操作。插入也叫入栈或进栈。1.4.2队列及其基本操作队列可以看作是插入在一端进行，删除在另一端进行的线性表。允许插入的一端称为队尾，允许删除的一端称为队头。队列又称为先进先出（First_In_First_Out,FIFO）表。队列的基本操作有插入（即入队）和删除（即出队）两种。图1-10顺序队列图1-11循环队列的插入和删除1.5树1.5.1树的基本概念树是由n(n≥0)个结点组成的有限集合。如果n=0，称为空树；如果n＞0，则有一个特定的称之为根（root）的结点，根结点只有直接后继，没有直接前驱；除根以外的其他结点划

8、分为m(m≥0)个互不相交的有限集合T0，T1，…，Tm−1，每个集合又是一棵树，并且称之为根的子树（subTree）。每棵子树的根结点