算法與数据基本结构的笔记整理.docVIP

算法与基本数据结构的笔记整理 知识点1算法的复杂度 〈一〉算法的定义： 算法是对具体问题求解过程和步骤的一种描述，简单地说，就是解决问题的操作步骤。 〈二〉算法四个基本特征： ①有穷性：算法在特定的执行环境中执行应当能够得出 满意的结果，即必须有一个或多个输出。 ②确定性：对算法中的每一步的描述是明确的，无歧义 ③可行性：算法中的操作步骤为有限个，且每个步骤都能在有限时间内完成。 ④拥有足够的情报：算法在拥有足够的输入信息和初始化信息时，才是有效的；当提供的情报不够时，算法可能无效。 〈三〉算法通常由两个基本要素组成： ①对数据对象的运算和操作 ②算法的控制结构 〈四〉算法复杂度包括： 1、时间复杂度：指执行算法时所需要的计算工作量，通常是用算法所执行的基本运算次数来度量。 注：算法程序执行的具体时间和算法的时间复杂度并不是一致的。 2、空间复杂度：指执行这个算法所需要的内存空间。 〈五〉算法的描述 ①用自然语言表示算法 ②用流程图表示算法 ③用程序设计语言表示算法 〈六〉算法的设计要求 ①正确性 ②可读性 ③健壮性 ④效率高与低存储需求 知识点2逻辑结构和存储结构 〈一〉一些基本概念 ①数据：是对客观事物的符号表示，在计算机科学中是指能输入到计算机中并被计算机存储、加工的符号总称。 ②数据元素：是数据的基本单位，由若干个数据项组成，在程序中作为一个整体而加以考虑和处理。数据元素具有完整确定的实际意义，有时也称为元素、结点、顶点或记录 ③结构：是数据元素之间的关联关系 ④数据结构：数据结构带有结构的同性质数据元素的集合 〈二〉数据结构包括以下三方面内容： 逻辑结构、存储结构和对数据结构的操作 (Ⅰ)逻辑结构：数据元素之间逻辑上的关系，它是数据的组织形式。通常将数据的逻辑结构简称为数据结构，数据的逻辑结构分两大类：线性结构和非线性结构。具体可分为四类： ① 集合 ② 线性结构 ③ 树型结构 ④ 图状结构 (Ⅱ)存储结构：数据元素以及数据元素之间的逻辑关系在计算机内存中的表示。一般地，一个存储结构包括以下两个主要部分： ① 存储结点(简称结点),每个结点存放一个数据元素 ② 数据元素之间关系的表示，也就是逻辑结构的计算机内部表示 常用的数据存储结构： 顺序存储方法 链式存储方法 索引存储方法 散列存储方法 数据的运算如查找、排序、增加、修改、删除 注意：各数据元素在计算机存储空间中的位置关系与它们的逻辑关系不一定是相同的。 ⅰ)顺序存储结构 ⅱ)链式存储结构 链式存储结构是在每个结点中至少包含一个指针域，用指针来体现数据元素之间逻辑上的联系 知识点3 线性结构和非线性结构 〈一〉根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分为两大类型：线性结构与非线性结构。如果一个非空数据结构满足下列两个条件：① 有且只有一个根结点； ② 每一个结点最多有一个前件，也最多有一个后件。 则称该数据结构为线性结构。线性结构又称线性表。特别需要说明的是，在一个线性结构中插入或删除任何一个结点后还应该是线性结构。根据这一点，如果一个数据结构满足上述两个条件，但当在此数据结构中插入或删除任何一个结点后就不满足这两个条件了，则该数据结构不能称为线性结构。 〈二〉线性表是n(n≥O)个同类型数据元素(结点)的有穷序列。其中数据元素的个数n称为线性表的长度(简称表长)。表长为O的线性表称为空表。表示成：(a1，a2 …，an) 〈三〉线性表逻辑结构的基本特征: ① 存在惟一的一个被称为“第一个”的数据元素和惟一的一个被称为“最后一个”的数据元素； ② 除第一个数据元素外，其他数据元素有且仅有一个直接前趋元素； ③ 除最后一个数据元素外，其他数据元素有且仅有一个直接后继元素。 〈四〉顺序表是用一组地址连续的存储单元依次存储线性表的各个数据元素。 特点：逻辑结构中相邻的结点在存储结构中仍相邻 应用范围：适合于小线性表或者建立之后其中元素不常变动的线性表，而不适合用于需要经常进行插入和删除运算的线性表和长度较大的线性表。 在顺序表上实现插入和删除运算必须移动结点才能够反映出结点间逻辑关系的变化。 知识点4栈 〈一〉栈的逻辑结构和线性表相同，但是，栈(Stack)是仅限在表的一端进行插入和删除运算的线性表，通常称插入、删除这一端为栈顶，另一端称为栈底,表中无元素时为空栈 〈二〉栈的运算原则是“先进后出” 插入运算称为进栈(或入栈) 删除运算称为退栈(或出栈) 〈三〉基本运算为： 入栈、出栈、取栈顶元素 顺序栈的进栈运算 将入栈元素放入到栈顶下标所指的位置上,栈顶下标加l 顺序栈的退栈运算 退栈先将栈顶下标减1，