Visual FoxPro程序设计 高巍巍 第11章 数据结构与算法新.ppt

第11章 数据结构与算法 本章知识结构 11.1 算法 11.1.1算法的基本概念 算法的五个特征 有穷性、确切性、输入、输出、可行性 算法设计的基本方法 递推法、递归、列举法、归纳法、减半递归 技术、回溯法 算法的描述 11.1 算法 11.1.2 时间复杂度和空间复杂度 时间复杂度是指算法运行所需要的时间。 空间复杂度是程序运行从开始到结束所需要的存储空间。 11.2数据结构 11.2.1数据结构的定义 数据结构的概念 数据结构是由数据元素依据某种逻辑联系组 织以来的，是指相互有关联的数据元素的集 合。 数据的逻辑结构和存储结构 数据的逻辑结构反映了数据元素之间的逻辑关系。 数据的存储结构是指数据的逻辑结构在计算机存储空间中的存放形式，也称为数据的物理结构。 11.2数据结构 11.2.2线性结构和非线性结构 线性结构是指有且仅有一个根结点，每个结点最多有一个前件，也最多有一个后件，这种结构也称为线性表。如数据结构春、夏、秋、冬。 非线性结构是指在该类结构中至少存在一个数据元素，而该数据元素具有一个或多个前件或后件 11.3线性表 11.3.1线性表的基本概念 线性表是由n(n≥0)个元素组成的有限序列，记为（）。其中，n是线性表中元素的个数，也就是线性表的长度。当n=0时，线性表为空表。线性表中每一个数据元素称为一个结点。 11.3线性表 11.3.2线性表的存储结构 线性表的存储表示方式有顺序表示和链式表示两种。 1、线性表的顺序表示 线性表的顺序表示也称为顺序表，即指用一组地址连续的存储单元一次存储数据元素的数据结构。 11.3线性表 11.3.2线性表的存储结构 2、线性表的链式表示 （1）单链表的链式结构 线性表的链式存储表示的特点是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。 11.3线性表 11.3.2线性表的存储结构 2、线性表的链式表示 （2）循环链表的链式结构 单循环链表是将单链表中最后一个结点的指针指向第一个结点的地址，不再是指向Null，这样就可以从表中的任意结点出发，访问表中的所有结点 11.3线性表 11.3.2线性表的存储结构 2、线性表的链式表示 （3）双向链表的链式结构 双向链表中每个结点包含三个域：data、Llink和Rlink。其中data为数据元素，Llink为指向前驱结点的指针，Rlink为指向后继结点的指针 11.3线性表 11.3.2线性表的存储结构 2、线性表的链式表示 (4)带头结点的链表 在线性链表中，各数据元素之间前后继关系是由各个节点的来表示的，指向线性表中第一个结点的指针head称为头指针，当head=NULL或为0时，称该线性链表为空表。对于线性链表，可以从头指针开始，沿着各个节点的指针扫描到链表中的所有结点。 11.3线性表 11.3.2线性表的存储结构 3、两种存储表示的比较 线性表的两种存储表示中顺序表的优点在于可以随机存取元素，查找指定位置的元素，但在插入和删除操作上需要移动大量元素，效率不高。另外，顺序表所用空间必须预先分配，难以临时扩大。而采用链式方式实现的线性表，可以动态的申请结点空间，线性表的长度只受内存大小的限制。 11.3线性表 11.3.3线性表的运算 1、顺序表的运算 （1）插入运算 11.3线性表 11.3.3线性表的运算 1、顺序表的运算 （2）删除运算 11.3线性表 11.3.3线性表的运算 2、线性链表的运算 （1）单链表的查找 在对线性链表进行插入或删除运算前，要先找到要插入或删除的位置，这就要求我们先要在线性链表中查找进行操作的值的前一个结点。当找到包含指定元素的前一个结点后，就可以在该结点后插入新结点或删除该结点后的一个结点。 （2）单链表的插入 11.3线性表 11.3.3线性表的运算 2、线性链表的运算 （3）单链表的删除 11.4栈和队列 11.4.1栈的基本概念和运算 1、栈的基本概念 栈是限定仅在表尾进行插入或删除操作的线性表。允许插入和删除元素的一端称为栈顶，另一端称为栈底。如果栈中没有任何元素的话，该栈称为空栈。 11.4栈和队列 2、栈的顺序存储 用一维数组存储的栈称为顺序栈。当栈为空时，栈顶指针top=-1 3、栈的运算 （1）入栈 11.4栈和队列 3、栈的运算 （2）出栈 11.4栈和队列 3、栈的运算 （3）读栈顶元素 读栈顶元素是指将栈顶元素赋给一个指定的变量。这个运算不删除栈顶元素。 11.4栈和队列 11.4.2队列的基本概念和运算 1、队列的基本概念 队列是限定只能在表的一端插入元素，在表的另一端删除元素的线性数据结构。允许插入元素的一端称为队尾（rea