线性结构与非线性结构

《线性结构与非线性结构》由会员分享，可在线阅读，更多相关《线性结构与非线性结构（25页珍藏版）》请在金锄头文库上搜索。

1、线性结构与非线性结构线性结构的特点:数据元素,a,b,c,之间存在前后次序，排在某个数据元素b前面的数据元素a称为b的直接前驱元素，而数据元素b则称为数据元素a的直接后继元素，对于某个数据元素，如果存在直接前驱元素或直接后继元素，则都是唯一的。线性结构中数据元素之间的正逆关系都是“一对一”的。非线性结构的特点：数据元素不一定存在确定的前后次序，甚至是无序的，数据元素之间存在从属、或互为从属、或离散关系。树型结构中，数据元素之间存在着“一对多”的从属关系。 图或网状结构中，数据元素之间存在着“多对多”的互为从属关系。 在纯集合结构中，数据元素具有“同属于一个集合”的关系。算法和程序 1. 算法算

2、法：是指解决问题的一种方法或一个过程。算法可以理解为函数的另一种表述，所以，一个给定的算法解决一个特定的问题。 算法也可以描述为：算法是非空的、有限的指令序列，遵循它就可以完成某一确定的任务。它有五大特征：v 有穷性：一个算法在执行有限步骤之后必须终止。 如果步骤是无限地，并无法全部写出不是算法。v 确定性：一个算法所给出的每一个计算步骤（精确定义的，无二义性。 确定性说明的是，算法中所执行下一步是确定的。v 可行性：算法中要执行的每一个步骤都可以在有限时间内完成。v 输入：算法有一组作为加工对象的量值，就是一组输入变量。v 输出：算法有一个或多个信息输出，它是算法对输入量的执行结果。算法与程

3、序差异程序：是使用某种程序设计语言对一个算法或多个算法的具体实现。v 算法只是程序在的一部分，算法是程序解决问题的核心。 v 同一个算法，由于使用不同的设计语言实现，所以，可能有许多程序对应于同一算法。v 算法必须提供足够的细节才能转化为程序。v 算法是可终止的，但程序不一定，程序可在无外来干涉情况下一直执行下去；程序可以既无输入数据，又无输出信息。空间复杂性1）指令空间 ：指令空间是指用来存储经过编译之后的程序指令所需的空间。指令空间一般不是数据结构所讨论的问题。 2）数据空间：存储数据元素的空间及程序中工作变量，包括：存储常量和简单变量所需要的空间 存储复合变量所需要的空间数据元素值占用的

4、空间（重要） 3）环境栈空间 ：环境栈用来保存函数调用和返回时需要的信息。包括返回地址、局部变量的值、参数的值。调用或递归的层次越深，所需有环境栈空间就越大，这一部分的空间是可变部分。（重要） 时间复杂性一个程序在计算机上运算所消耗的时间主要取决下述因素： 程序运行时所需要输入的数据总量消耗的时间。 对源程序进行编译所需要的时间。 计算机执行每条机器指令所需要的时间。 程序中关键指令重复执行的次数。第四因素主要可从两个方面估算：v 找出一个或多个关键操作确定这些关键操作所需要的执行时间线性表的逻辑结构线性表是有限元素（e0,e1, .,ei,.,en-1）的有序序列的集合。其中n是有穷自然数，

5、表中的每个元素ei具有相同的特性，表中元素占用空间大小相同,记为：size，n是表的长度。当n=0时，表为空；当n0时，e0是第一个元素，en-1 是最后一个元素。 “有序”是指线性元素间的相互位置关系。ei-1是 ei的直接前驱元素，而元素ei一定在元素ei+1之前，称ei+1是ei的直接后继元素。 而且，每个元素只有一个直接前驱元素（除第一个元素），也仅有一个直接后继元素（除最后一个元素）线性表的抽象数据类型线性表顺序存储1. 线性表顺序存储概念线性表顺序存储方式，是将线性表中的数据元素连续顺序地存放于存储器中相邻的单元 。线性表顺序存储结构由三部分组成： 所有数据元素可用于存储的空间el

6、ement，element又是由若干个数据元素空间组成。 记录线性表中已存放的数据元素个数的空间length，这个值小于等于可用的元素空间数。 线性表可用元素空间总数存放的空间MaxSpaceSize。线性表的连续顺序存储结构具有很高的存取效率，它是一种高效的直接存取存储结构。 线性表顺序存储结构定义线性表结构： 学生信息的情况数据元素结构类型（EType）及线性表 struct STUDENTunsignednumber10;charname8;charsex2;intage;charplace20;private: STUDENT *element;/数据元素存放空间intlength;/

7、数据元素的个数intMaxSpaceSize;/线性表存放元素的最大空间个数构造空线性表输出线性表L中的所有数据元素displayelementslinearlist:templatevoid LinearList:DisplayElementsLinearList ()/ 逐个地输出线性表L中的数据元素for (int i = 0; i length; i+) cout elementi link=current-link的操作就可以删除结点current。实际上，它是将current的直接前驱结点q的链接指针直指current的直接后继元素结点。链表中的被删除结点从链表中断开后，还要将结点

8、空间释放。 简单链表的实现还有一种结构，简单链表中没有表头结点，只有数据元素构成的一种结点，如图2.11所示。不带表头的简单链表中的数据元素的结点结构与带表头的简单链表中数据元素结点结构没有区别。由于没有表头结点，所以，类中定义的指向结点的指针是指向数据元素结点的指针，并定义指向简单链表中的第一个结点的指针first，初值为NULL。SimpleChainList模板类定义（不带表头结点） templateclass SimpleChainList/线性表链式存储结构-简单链表模板类 SimpleChainList的定义public: SimpleChainList()first=NULL;/

9、构造函数：first初值为空，不再申请表头结点 SimpleChainList();/析构函数 int LengthSimpleChainList() const/求简单链表的长度 SimpleChainNode * GetHeadPtrSimpleChainList()return first;/返回链表的头指针firstprivate: SimpleChainNode*first;/这里指针的类型不是表头结点，而是数据元素结点;堆栈的逻辑结构定义：堆栈（也简称栈）是一个线性表，其数据元素只能从这个有序集合的同一端插入或删除，这一端称为堆栈的栈顶（top），而另一端称为堆栈的栈底（botto

10、m）。 堆栈是限定只能在表头（或表尾）进行插入和删除运算的线性表。表头（或表尾）是开放运算的栈顶，另一端是封闭运算的栈底。 栈为后进先出表或先进后出表，简称LIFO（Last in first out）或FILO（First in last out）表。 堆栈顺序存储概念v 堆栈占用的第一个存储单元的地址，就是堆栈的首地址，也是堆栈中栈底元素（e0）存放的位置。v 假设堆栈中每个数据元素占用size字节空间，top指向（top=n-1）堆栈中进栈元素的栈顶元素，即栈顶元素的地址，MaxSize表示堆栈可以存储元素的最大空间。一般约定下标为0的元素空间就是栈底，这样就不再另设一变量再来记录栈底指针bottom。1.构造空堆栈空堆栈是指堆栈中没有一个数据元素，但数据元素的空间和堆栈结构已产生 空堆栈产生后，就存在一个元素类型的数组，表中只有存放数据元素的空间，堆栈栈顶指针设为-1（用户约定），即堆栈为空时，栈顶指针“指向”栈底空间的前面。 2.判断堆栈是否为空所谓堆栈为空，是指堆栈中没有一个数据元素，即栈顶指针top指向数据空间的第一个位置（0下标的空间）的前面。如堆栈不空，top总是指