基本数据结构与算法.doc

基本数据结构与算法一、数据结构的基本概念 1、数据信息载体，能够被计算机识别、存储和加工处理。可以是数值数据（整数、实数），也可以是非数值数据（声音、图像等）。2、数据项是数据的具有独立含义的不可分割的最小标识单位，如成绩表中学号、姓名。3、数据元素（ 又称结点、记录）一个数据元素由若干数据项组成，是数据的基本单位，通常作为一个整体进行考虑和处理。 4、数据对象具有相同性质的数据元素的集合。是数据的一个子集。5、数据结构相互之间存在着一种或多种关系的数据元素的集合。（1）研究内容 数据的逻辑结构：各数据元素之间的逻辑关系。 数据的存储结构：各数据元素在计算机中的存储关系。 对各种数据结构进行的运算：添加、删除、排序等。（2）研究目的一是提高数据处理的速度；二是尽量节省在数据处理过程中所占用的计算机存储空间。（3）常见的数据结构类型 集合：元素间为松散的关系（属于关系）。 线性结构：元素间为一对一关系。 树形结构：元素间为一对多关系。特点：结点间具有分层次的连接关系。 图状结构：元素间为多对多关系。特点：结点间的连结是任意的，数据元素之间存在多个对多个关系。（4）包含信息 表示数据元素的信息。 表示各数据元素之间的前后件关系。（5）有关概念 结点：组成数据结构的数据元素称为一个结点。 前后件关系：数据元素之间的固有关系可以用前后件关系（前驱与后继关系）描述。 根节点：在数据结构中，没有前件的节点称为根结点。 叶子节点：没有后件的结点称为终端结点或叶子结点。6、数据结构的逻辑结构（1）数据的逻辑结构数据之间的相互关系，被称为数据的逻辑结构。（2）逻辑结构分类根据数据结构中各数据元素之间的前后件关系的复杂程度，一般将数据逻辑结构分为：线性结构与非线性结构。（3）线性结构数据元素之间存在一个对一个的前后次序关系。 特点：有且只有一个根结点每个结点最多有一个前件，也最多有一个后件。（4）非线性结构一个数据结构如果不是线性结构，则称之为非线性结构。 特点：数据元素的前后关系复杂，一个结点既可以有多个前件，也可以有多个后件，如集合、树型、图形结构属于非线性结构。 集合结构：数据元素间的关系是属于同一个集合 。 树型结构：数据元素之间存在一个对多个的关系。 图形结构：数据元素之间存在多个对多个的关系 。7、数据结构的存储结构数据的逻辑结构在计算机存储空间中的存放形式。数据存储结构中不仅存放各数据元素信息，还存放前后件关系的信息。（1）特点 存储结构研究的是逻辑结构用计算机语言实现，依赖于计算机语言。一种数据结构可以根据需要采用多种不同的存储结构，常用的存储结构有顺序、链接与索引等存储方式。数据的存储结构不同，解决问题的方法就有所不同，数据处理的效率也是不同的。（2）实现方式 顺序存储方式逻辑上相邻的元素存储在物理位置相邻的存储单元中；主要用于线性结构；通常借助于数组来实现。 链式存储方式对逻辑上相邻的元素不要求其物理地址相邻，元素间逻辑关系通过附加的指针字段来表示；通常借助于指针类型实现。 链式存储方式特点：每个结点由两部分组成，一部分存放数据，另一部分存储指向前件或后件结点的指针域；逻辑上相邻的结点物理上不必相连；数据运算（插入和删除等）灵活。 索引存储方法和散列存储方法8、数据的运算在数据的逻辑结构上定义的操作算法。 常见运算：插入、删除、查找、排序和更新等。 分类：加工型运算，运算改变了数据结构的值；引用型运算，不改变值，只查询或求得结构值。 注意：数据的运算定义在逻辑结构上，而具体的实现都要在数据的存储结构上即计算机内进行。9、数据类型及其分类数据类型是一个值的集合和定义在这个值集上的一组操作的总称。分类：（1）非结构的原子类型原子类型的值是不可分解的。如：程序设计语言中的基本类型（整型，实型，字符型，指针类型和空类型）。（2）结构类型结构类型的值是由若干成分按某种结构组成的，因此是可分解的，并且它的成分可以是非结构的，也可以是结构的。二、算法及算法分析 1、 算法的基本概念（1）定义为解决某个特定问题而采取的确定且有限的步骤。 用计算机解决一个具体问题时，大致需要经过下列几个步骤：首先要从具体问题抽象出一个适当的数学模型；然后设计一个解此数学模型的算法；最后采用一种计算机语言编出程序，调试、修改直至得到最终答案。（2）算法特性 有穷性： 一个算法应包含有限个操作步骤，而且每一步都应在有限时间内完成。 确定性：算法中每一条指令必须有确切的含义，确保不会产生二义性。 可行性：算法中指定的操作都是可以通过基本运算执行有限次后实现。 输入：一个算法有零个或多个的输入，这些输入取自于某个特定的对象集合。 输出：一个算法有一个或多个的输出，这些输出是同输入有着某些特定关系的量。2、算法的基本要素及描述（1）算法基本要素构成 对数据对象的运算和操作：算术运算，加、减、乘、除；逻辑运算，与、或、非等运算；关系运算，大于、小于、等于等；数据传输，赋值、输入、输出。 算法的控制结构：顺序、选择、循环（重复）。（2） 算法的描述自然语言、伪代码、流程图、 N-S图、类C。3、算法设计要求（评价算法标准）（1）正确性：执行结果应满足预先的功能和性能要求。（2）可读性：思路清晰、层次分明、简单明了、易读易懂。（3）健壮性：输入数据非法时，算法能作适当处理，不致于引起严重后果。（4）效率：有效使用存储空间和较高的时间效率。4、算法设计的基本方法（1）列举法：列举出所有可能情况，用给定条件检验哪些是需要的，哪些是不需要的（如用循环解决百元买百鸡问题）。（2）归纳法：列举少量简单而又特殊的情况，分析归纳出一般结论。 （3）递推法：从已知初始条件出发，逐步推出各种中间结果和最后结果（如猴子吃桃）。（4）递归法：解决复杂问题时，将问题逐层分解，归纳为一些简单问题，解决了最后简单问题后，再沿原来的逆过程逐步综合（如求某数的阶乘）。5、算法的分析（1）评价算法标准算法所占用计算机资源，即时间代价（算法所需要的时间）和空间代价（算法所需要的存储空间）。算法所需要的时间包括：源程序进行编译所需要的时间；计算机执行每条指令所需要的时间；程序中指令重复执行的次数，而本条正是讨论算法中的重点内容。（2）相关名词 问题规模：不同种类问题，问题规模含义不同。如矩阵运算取决于矩阵阶数，多项式运算取决于项数。 算法运行时间：大致等于其所有语句执行时间的总和。 语句频度：该语句在算法中重复执行的次数。（3）算法的时间复杂度即算法运行从开始到结束所需要的计算工作量。同一个算法使用不同的语言实现，或者用不同的编译程序进行编译，或者在不同的计算机上运行，效率均不同，这表明使用绝对的时间单位衡量算法的效率是不合适的，撇开这些与计算机硬件、软件有关的因素，可以认为一个特定算法“运行工作量”的大小，只依赖于问题的规模（通常用整数n表示），它是问题的规模函数，即：算法的工作量=f(n)。一个算法是由控制结构和原操作构成的，则算法时间取决于两者的的综合效果。为了便于比较同一个问题的不同算法，通常的做法是，从算法中选取一种对于所研究的问题（或算法类型）来说是基本操作的原操作，以该基本操作重复执行的次数作为算法的时间度量。（T (n)=O( f (n) ) ） 最优算法：随n的增大，T (n)增长较慢的算法。 平均时间复杂度：所有可能的输入实例均以等概率出现的情况下，算法的期