数据结构笔记基础：数据结构与算法（―）数据结构基本概念数据（data）:是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号总称数据元素（dataelement）:是数据的基本单位，在计算机中通常被当做一个整体进行考虑和处理数据对象（dataobject）:性质相同的数据元素的集合，是数据的一个子集数据结构（datastructure）:相互之间存在一种或多种特定关系的数据元素的集合4类基本结构:集合、线性结构、树形结构、图形（网状）结构数据结构的形式定义为数据结构是一个二元组DataStructure=（D,S），其中D是数据元素的有限集，S是D上关系的有限集数据结构定义中的“关系”描述的是数据元素之间的逻辑关系，因此又称为数据的逻辑结构数据结构在计算机中的表示（映像）称为物理结构（存储结构）计算机中表示信息的最小单位是二进制中的一位，叫做位（bit），一到若干位组成一个位串表示一个数据元素，这个位串称为元素或结点数据结构之间关系在计算机中的表示有两种:顺序映像、非顺序映像，并由此得到两种存储结构:顺序存储、链式存储，前者运用相对位置表示数据元素间的逻辑结构，后者借助指针任何一个算法的设计取决于数据（逻辑）结构，而实现依赖于存储结构数据类型是一个值的集合和定义在这个值集上的一组操作的总称数据类型分两种:原子类型、结构类型，前者不可分解（例如int、char、float、void），后者结构类型由若干成分按某种结构组成，可分解，成分既可以是非结构的也可以是结构的（例:数组）抽象数据类型（AbstractDataType）:是指一个数学模型及定义在该模型上的一组操作（P8）抽象数据类型格式如下：ADT抽象数据类型名{数据对象：＜数据对象的定义＞数据关系：＜数据关系的定义＞数据操作：＜数据操作的定义＞}ADT抽象数据类型名基本操作格式如下：基本操作名（参数表）初始条件：＜初始条件描述＞操作结果：＜操作结果描述＞多形数据类型（polymorphicdatatype）:是指其值得成分不确定的数据类型（P9）抽象数据类型可由固有数据类型来表示和实现二)算法(概念)和算法分析(时、空性能)算法(algorithm):对特定问题求解步骤的一种描述算法5特性：有穷、确定、可行、输入、输出1、有穷性:算法必须在可接受的时间内执行有穷步后结束2、确定性:每条指令必须要有确切含义，无二义性，并且只有唯一执行路径，即对相同的输入只能得相同输出3、可行性:算法中的操作都可通过已实现的基本运算执行有限次来完成4、输入:一个算法有一到多个输入，并取自某个特定对象合集5、输出:一个算法有一到多个输出，这些输出与输入有着某些特定关系的量算法设计要求(好算法)：正确性、可读性、健壮性、效率与低存储需求健壮性是指对于规范要求以外的输入能够判断出这个输入不符合规范要求，并能有合理的处理方式。算法效率的度量：(1)事后统计：程序运行结束后借助计算机内部计时功能，缺点一是必须先运行依据算法编制的程序，二是受限于计算机软硬件，导致掩盖了算法本身的优劣(2)事前分析估计：消耗时间影响因素：算法策略、问题规模、编程语言、编译程序产生的机器码质量、机器执行指令的速度撇开各种影响因素只考虑问题的规模(通常用整数量n表示)，记为问题规模的函数算法时间取决于控制结构(顺序，分支，循环)和固有数据类型操作的综合效果书写格式：T(n)=O(f(n))f(n)为n的某个函数时间复杂度：算法的渐近时间复杂度(asymptotictimecomplexity),它表示随问题规模的增大，算法执行时间的增长率和f(n)的增长率相同以循环最深层原操作为度量基准频度：该语句重复执行的次数算法的存储空间需求：空间复杂度(spacecomplexity):算法所需存储空间度量，记作S(n)=0(f(n)),其中n为问题规模的大小排序方法时间复杂度空闻复杂度平均情况最坏荷迟况O(n)0(1?)O(n)Off)简羊拾尔排序<')(iklag2i0<'>(iilogaii}O⑴冒泡排序O(n)oa?)O(n)OCl)简羊怏逸椰序0C>(111心窪归井扌非序O(nlog2ii)O(nlog2ii)0(1110OdO基筋扌非序ccicscn.cc较更杂mAvhuslei—、线性表（一）线性表基本概念线性表（l...
