文档介绍：(DataStructure)是指数据元素的组织形式和相互关系。数据结构一般包括以下三方面的内容:数据的逻辑结构数据的物理结构数据的运算数据的逻辑结构1数据的逻辑结构从逻辑上抽象地反映数据元素间的结构关系,它与数据在计算机中的存储表示方式无关。因此,数据的逻辑结构可以看做是从具体问题抽象出来的数学模型。数据的逻辑结构有两大类:线性结构——线性结构的逻辑特征是:有且仅有一个始端结点和一个终端结点,并且除两个端点结点外的所有结点都有且仅有一个前趋结点和一个后继结点。线性表、堆栈、队列、数组、串等都是线性结构。非线性结构——非线性结构的逻辑特征是:一个结点可以有多个前趋结点和后继结点。如树形结构、图等是非线性结构。数据的物理结构2数据的物理结构是逻辑结构在计算机存储器里的映像,也称为存储结构。数据的存储结构可用以下四种基本存储方法:顺序存储方法——把逻辑上相邻的结点存储在物理位置上相邻的存储单元里,结点之间的逻辑关系由存储单元的邻接关系来体现。链式存储方法——不要求逻辑上相邻的结点在物理位置上也相邻,结点之间的逻辑关系是由附加的指针字段表示的。索引存储方法——在存储结点信息的同时,还建立附加的索引表。索引表中的每一项称为索引项。索引项由关键字和地址组成,关键字是能唯一标识一个结点的那些数据项,而地址一般是指示结点所在存储位置的记录号。散列存储方法——根据结点的关键字直接计算出该结点的存储地址。数据的运算3数据的运算是指对数据施加的操作,数据的每种逻辑结构都有一个运算的集合,常用的运算有检索、插入、删除、更新、排序等。算法4算法的特点(1)有穷性——一个算法的执行步骤必须是有限的。确定性——算法中的每一个操作步骤的含义必须明确。可行性——算法中的每一个操作步骤都是可以执行的。输入——一个算法一般都要求有一个或多个输入量(个别的算法不要求输入量)。这些输入量是算法所需的初始数据。输出——一个算法至少产生一个输出量,它是算法对输入量的执行结果。算法的描述(2)自然语言——用人的语言描述,该方法易于理解,但容易出现歧义。流程图——用一组特定的几何图形来表示算法,这是最早的算法描述工具。N-S图——用矩形框描述算法,一个算法就是一个矩形框。伪代码——用介于高级语言和人的自然语言之间的文字、符号来描述算法,可以十分容易地转化为高级语言程序。PAD图——全称为问题分析图,使用树形结构描述算法。算法性能分析(3)衡量一个算法的好坏主要考虑算法的时间特性,一般将语句的重复执行次数作为算法的时间变量。设算法解决的问题的规模为n,例如学生总数等。将一条语句重复执行的次数称为该语句的执行频度,一个算法中所有语句执行频度之和就称为该算法的运行时间。很多情况下无法准确也无必要精确计算出运行时间,而只需求出它关于问题规模n的一个相对的数量级即可,该数量级就称为该算法的时间复杂度,记为O(1),O(n),O(n2)……一般地,常用的时间复杂度有如下关系:O(1)<=O(log2n)<=O(n)<=O(nlog2n)<=O(n2)<=O(an)(a>1)。其基本特点是:数据元素有序并有限。线性结构的数据元素可排成一个线性队列当线性表采用顺序存储结构时称之为顺序表。在顺序表中,数据元素按逻辑次序依次放在一组地址连续的存储单元里。由于逻辑上相邻的元素存放在内存的相邻单元里,所以顺序表的逻辑关系蕴含在存储单元的邻接关系中。插入运算(1)(2)删除运算顺序表的插入运算是指在表的第i个(1≤i≤n+1)位置上,插入一个新结点y。若插入位置i=n+1,即插入到表的末尾,那么只要在表的末尾增加一个结点即可;但是若1≤i≤n,则必须将表中第i个到第n个结点向后移动一个位置,共需移动ni+1个结点。顺序表上插入运算的平均时间复杂度是O(n)。顺序表的删除运算是指将表的第i个(1≤i≤n)结点删去。当i=n时,即删除表尾结点时,操作较为简单;但1<i≤n-l时,则必须将表中第i+1个到第n个共ni个结点向前移动一个位置。顺序表上删除运算的平均时间复杂度是O(n)