线性结构与非线性结构VIP免费

线性结构与非线性结构线性结构的特点:数据元素｛…,a,b,c,…｝之间存在前后次序，排在某个数据元素b前面的数据元素a称为b的直接前驱元素，而数据元素b则称为数据元素a的直接后继元素，对于某个数据元素，如果存在直接前驱元素或直接后继元素，则都是唯一的。线性结构中数据元素之间的正逆关系都是“一对一”的。非线性结构的特点：数据元素不一定存在确定的前后次序，甚至是无序的，数据元素之间存在从属、或互为从属、或离散关系。树型结构中，数据元素之间存在着“一对多”的从属关系。图或网状结构中，数据元素之间存在着“多对多”的互为从属关系。在纯集合结构中，数据元素具有“同属于一个集合”的关系。算法和程序1.算法算法：是指解决问题的一种方法或一个过程。算法可以理解为函数的另一种表述，所以，一个给定的算法解决一个特定的问题。算法也可以描述为：算法是非空的、有限的指令序列，遵循它就可以完成某一确定的任务。它有五大特征：有穷性：一个算法在执行有限步骤之后必须终止。如果步骤是无限地，并无法全部写出不是算法。确定性：一个算法所给出的每一个计算步骤（精确定义的，无二义性。确定性说明的是，算法中所执行下一步是确定的。可行性：算法中要执行的每一个步骤都可以在有限时间内完成。输入：算法有一组作为加工对象的量值，就是一组输入变量。输出：算法有一个或多个信息输出，它是算法对输入量的执行结果。算法与程序差异程序：是使用某种程序设计语言对一个算法或多个算法的具体实现。算法只是程序在的一部分，算法是程序解决问题的核心。同一个算法，由于使用不同的设计语言实现，所以，可能有许多程序对应于同一算法。算法必须提供足够的细节才能转化为程序。算法是可终止的，但程序不一定，程序可在无外来干涉情况下一直执行下去；程序可以既无输入数据，又无输出信息。空间复杂性1）指令空间：指令空间是指用来存储经过编译之后的程序指令所需的空间。指令空间一般不是数据结构所讨论的问题。2）数据空间：存储数据元素的空间及程序中工作变量，包括：存储常量和简单变量所需要的空间存储复合变量所需要的空间数据元素值占用的空间（重要）3）环境栈空间：环境栈用来保存函数调用和返回时需要的信息。包括返回地址、局部变量的值、参数的值。调用或递归的层次越深，所需有环境栈空间就越大，这一部分的空间是可变部分。（重要）时间复杂性一个程序在计算机上运算所消耗的时间主要取决下述因素：①程序运行时所需要输入的数据总量消耗的时间。②对源程序进行编译所需要的时间。③计算机执行每条机器指令所需要的时间。④程序中关键指令重复执行的次数。第四因素主要可从两个方面估算：找出一个或多个关键操作确定这些关键操作所需要的执行时间线性表的逻辑结构线性表是有限元素（e0,e1,...,ei,...,en-1）的有序序列的集合。其中n是有穷自然数，表中的每个元素ei具有相同的特性，表中元素占用空间大小相同,记为：size，n是表的长度。当n=0时，表为空；当n>0时，e0是第一个元素，en-1是最后一个元素。“有序”是指线性元素间的相互位置关系。ei-1是ei的直接前驱元素，而元素ei一定在元素ei+1之前，称ei+1是ei的直接后继元素。而且，每个元素只有一个直接前驱元素（除第一个元素），也仅有一个直接后继元素（除最后一个元素）线性表的抽象数据类型线性表顺序存储1.线性表顺序存储概念线性表顺序存储方式，是将线性表中的数据元素连续顺序地存放于存储器中相邻的单元。线性表顺序存储结构由三部分组成：①所有数据元素可用于存储的空间element，element又是由若干个数据元素空间组成。②记录线性表中已存放的数据元素个数的空间length，这个值小于等于可用的元素空间数。③线性表可用元素空间总数存放的空间MaxSpaceSize。线性表的连续顺序存储结构具有很高的存取效率，它是一种高效的直接存取存储结构。线性表顺序存储结构定义线性表结构：学生信息的情况数据元素结构类型（EType）及线性表structSTUDENT{unsignednumber[10];charname[8];charsex[2];intage;charplace[20];};private:STUDENT*element;//数据元素存放空间intlen...