数据结构笔记.doc

数据结构笔记基础:数据结构与算法数据结构基本概念数据(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、输出:一个算法有一到多个输出,这些输出与输入有着某些特定关系得量算法设计要求(好算法):正确性、可读性、健壮性、效率与低存储需求健壮性就是指对于规范要求以外得输入能够判断出这个输入不符合规范要求,并能有合理得处理方式。算法效率得度量:事后统计:程序运行结束后借助计算机内部计时功能,缺点一就是必须先运行依据算法编制得程序,二就是受限于计算机软硬件,导致掩盖了算法本身得优劣事前分析估计:消耗时间影响因素:算法策略、问题规模、编程语言、编译程序产生得机器码质量、机器执行指令得速度撇开各种影响因素只考虑问题得规模(通常用整数量n表示),记为问题规模得函数算法时间取决于控制结构(顺序,分支,循环)与固有数据类型操作得综合效果书写格式:T(n)=O(f(n))f(n)为n得某个函数时间复杂度:算法得渐近时间复杂度(asymptotictimeplexity),它表示随问题规模得增大,算法执行时间得增长率与f(n)得增长率相同以循环最深层原操作为度量基准频度:该语句重复执行得次数算法得存储空间需求:空间复杂度(spaceplexity):算法所需存储空间度量,记作S(n)=O(f(n)),其中n为问题规模得大小一、线性表线性表基本概念线性表(linear_list):n个数据元素得有限序列结构特点:存在唯一得被称作“第一个”、“最后一个”得数据元素,且除了第一个以外每个元素都有唯一前驱,除最后一个以外都有唯一后继在复杂线性表中存在:数据项->记录->文件,例如每个学生情况为一个记录,它由学号、性别、、、、、、数据项组成,多个学生记录组成一个文件在形如(a1,、、、,ai-1,ai,ai+1,、、、,an)中,ai-1领先于ai,ai领先于ai+1,且形成直接前驱元素,直接后继元素关系元素个数n定义为线性表长度,n=0为空表相关操作算法见书(P20)线性表顺序存储结构与链式存储结构(1)线性表顺序表示与实现线性表顺序存储在一组连续得存储单元中,链式存储则不要求;顺序结构可以随机访问,链式结构可以无限扩容确定存储位置(计算公式):第i个元素:LOC(ai)=