数据结构总结.docVIP

第一章 用计算机处理的实际问题可分为两大类问题：数值计算 非数值计算 现实中对象之间的关系 ： 线性关系 ，层次关系 ， 网状关系 数据结构定义: 是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科 简单定义为：相互之间存在一种或多种特定关系的数据元素的集合。 基本概念和术语 数据（data)—所有能输入到计算机中去的描述客观事物的符号 数据元素（data element）—数据的基本单位，也称节点（node）或记录（record） 数据项（data item）—有独立含义的数据最小单位，也称域(field) 数据结构（data structure)—数据元素和数据元素关系的集合 根据数据元素间关系的基本特性，有四种基本数据结构 集合——数据元素间除“同属于一个集合”外，无其它关系 线性结构—— 一个对一个，如线性表、栈、队列 树形结构—— 一个对多个，如树 图状结构或网状结构—— 多个对多个，如图； 数据的逻辑结构—指抽象反映数据元素的逻辑关系。。数据的逻辑结构有两大类： 线性结构：线性表 非线性结构：树和图 数据的 存储（物理）结构—数据的逻辑结构在计算机存储器中的实现。存储结构分为： 顺序存储结构——借助元素在存储器中的相对位置来表示数据元素间的逻辑关系 链式存储结构——借助指示元素存储地址的指针表示数据元素间的逻辑关系 索引存储方法 散列存储方法 数据的逻辑结构与存储结构密切相关 算法设计 逻辑结构 算法实现 存储结构 数据结构的研究内容 研究数据之间的相互关系，即数据的组织形式，包括： 数据元素之间的逻辑关系，也称为数据的逻辑结构(Logical structure)。 数据元素及其关系在计算机存储器内的表示，称为数据的存储结构。 数据的运算，即基于某种存储结构对数据施加的操作或运算。 算法：通俗地讲，一个算法就是一种解题方法 更严格地说，算法是由若干条指令组成的有穷序列 算法必须满足下述准则：重要特性 输入：具有0个或多个输入的外界量。 输出：至少产生一个输出。 有穷性：每一条指令的执行次数必须是有限的。 确定性：每条指令的含义都必须明确，无二义性。 可行性：每条指令的执行时间都是有限的。 算法的描述 自然语言 伪高级语言 数据结构与算法的关系 给定了数据的逻辑结构后，对同一逻辑结构而言，由于存储结构的不同，定义的运算也是不同的。 如线性表是一种逻辑结构，若采用顺序存储方法表示，则称为顺序表；若采用链式存储方法表示，则称为链表。 相同的运算在顺序表和链表上的实现方法是不同的。 算法设计要求： 1）正确性 2）可读性 3）健壮性 4）效率与低存储量的要求 如何分析算法的优劣？ 主要考虑如下三点： 执行算法所耗费的时间 执行算法所耗费的存储空间，其中主要考虑辅助存储空间； 算法应易于理解，易于编码，易于调试等等。 时间复杂度 空间复杂度 程序的执行时间取决于以下相关因素： 1．算法选用的策略 2．问题的规模3．编写程序的语言4．编译程序产生的机器代码的质量5．计算机执行指令的速度 时间复杂度： 指某个算法的时间耗费，它是该算法所求解问题规模n的函数。 计算方法：有1，n，n2. 渐进时间复杂度： 指当问题规模趋向无穷大时，该算法时间复杂度的数量级。 评价一个算法的时间性能，主要标准就是算法的渐进时间复杂度。在算法分析时，往往对二者不予区分，经常是将渐进时间复杂度T(n)=O(f(n))简称为时间复杂度，其中的f(n)一般是算法中频度最大的语句频度。 此外，算法中语句的频度不仅与问题的规模有关，还与输入实例中各元素的取值有关。 总是考虑在最坏情况下的时间复杂度，以保证算法的运行时间不会比它更长。 算法的存储空间需求 算法在运行过程中所占用的存储空间的大小被定义为算法的空间复杂性。记作： S(n)=O(f(n)) 表示随着问题规模 n 的增大，算法运行所需存储量的增长率与 f(n) 的增长率相同。 第二章 线性表 1.线性表的定义： 是由n(n=0)个数据元素组成的有限序列。 2.线性链表： 定义：用一组任意的存储单元存放线性表的数据元素。 *任意---可以是连续的，也可以是不连续。 数据域——存储数据元素信息。 结点——将两部分的信息组成数据元素ai的存储映像 指针域（链域）——存储直接后继元素的存储位置。 通过链域，可将n个结点按其逻辑顺序链接在一起（不论其物理次序如何），称为链表,即为线性表的链式存储结构。因为每个节点中只包含一个指针域，因此又称为线性链表或单链表。 3. 线性链表的特点： 链表中结点的逻辑次序和物理次序不一定相同。即：逻辑上相邻未必在物理上相邻。 数据