算法与基本数据结构.jsp.ppt

《算法与基本数据结构.jsp.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法与基本数据结构1.算法的基本概念；算法复杂度的概念和意义（时间复杂度与空间复杂度）。2.数据结构的定义；数据的逻辑结构与存储结构；数据结构的图形表示；线性结构与非线性结构的概念。3.线性表的定义；线性表的顺序存储结构及其插入与删除运算。4.栈和队列的定义；栈和队列的顺序存储结构及其基本运算。5.线性单链表、双向链表与循环链表的结构及其基本运算。6.树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历。7.顺序查找与二分法查找算法；基本排序算法（交换类排序，选择类排序，插入类排序）。算法与基本数据结构基本概念基本

2、数据结构查找与排序基本概念数据：是对客观事物的符号表示，在计算机科学中是指能输入到计算机中并被计算机存储、加工的符号总称。数据结构的定义数据元素：是数据的基本单位，由若干个数据项组成，在程序中作为一个整体而加以考虑和处理。数据元素具有完整确定的实际意义，有时也称为元素、结点、顶点或记录结构：是数据元素之间的关联关系数据结构：数据结构带有结构的同性质数据元素的集合数据结构包括以下三方面内容：逻辑结构、存储结构和对数据结构的操作逻辑结构：数据元素之间逻辑上的关系，它是数据的组织形式。通常将数据的逻辑结构简称为数据结构，数据的逻辑结构

3、分两大类：线性结构和非线性结构。具体可分为四类：①集合②线性结构③树型结构④图状结构其中③、④为非线性结构集合线性结构树型结构图状结构基本概念数据结构的内容存储结构：数据元素以及数据元素之间的逻辑关系在计算机内存中的表示。一般地，一个存储结构包括以下两个主要部分：基本概念数据结构的内容①存储结点(简称结点),每个结点存放一个数据元素②数据元素之间关系的表示，也就是逻辑结构的计算机内部表示常用的数据存储结构：顺序存储方法链式存储方法索引存储方法散列存储方法数据的运算如查找、排序、增加、修改、删除各数据元素在计算机存储空间中的位置

4、关系与它们的逻辑关系不一定是相同的数据的存储结构数据的存储结构链式存储结构是在每个结点中至少包含一个指针域，用指针来体现数据元素之间逻辑上的联系算法：算法是对具体问题求解过程和步骤的一种描述，简单地说，就是解决问题的操作步骤。基本概念算法算法四个基本特征：①有穷性：算法在特定的执行环境中执行应当能够得出满意的结果，即必须有一个或多个输出。②确定性：对算法中的每一步的描述是明确的，无歧义③可行性：算法中的操作步骤为有限个，且每个步骤都能在有限时间内完成。④拥有足够的情报：算法在拥有足够的输入信息和初始化信息时，才是有效的；当提供的

5、情报不够时，算法可能无效。算法通常由两个基本要素组成：对数据对象的运算和操作算法的控制结构基本概念算法算法复杂度包括：时间复杂度：指执行算法时所需要的计算工作量，通常是用算法所执行的基本运算次数来度量。注：算法程序执行的具体时间和算法的时间复杂度并不是一致的。空间复杂度：指执行这个算法所需要的内存空间。算法的描述用自然语言表示算法：就是用人们所熟悉的自然语言把算法的各个步骤依次表示出来。用流程图表示算法：就是用一些大家共识的专用图形符号和带有箭头的流程线来表示算法。用程序设计语言表示算法：用计算机能理解和执行的程序设计语言把算法

6、表示出来，然后把程序输入计算机并执行，计算机才能按照预定的算法去解决问题。基本概念算法算法设计要求：正确性可读性健壮性效率高与低存储需求基本概念算法基本数据结构线性表:是n(n≥O)个同类型数据元素(结点)的有穷序列。其中数据元素的个数n称为线性表的长度(简称表长)。表长为O的线性表称为空表。表示成：(a1，a2…，an)线性表的定义和基本特征线性表线性表逻辑结构的基本特征:①存在惟一的一个被称为“第一个”的数据元素和惟一的一个被称为“最后一个”的数据元素；②除第一个数据元素外，其他数据元素有且仅有一个直接前趋元素；③除最后

7、一个数据元素外，其他数据元素有且仅有一个直接后继元素。顺序表是用一组地址连续的存储单元依次存储线性表的各个数据元素。元素a1a2a3……ai-1aiai+1……an相对地址012……i-2i-1i……n-1特点：逻辑结构中相邻的结点在存储结构中仍相邻基本数据结构线性表的顺序存储结构线性表顺序表应用范围：适合于小线性表或者建立之后其中元素不常变动的线性表，而不适合用于需要经常进行插入和删除运算的线性表和长度较大的线性表。在顺序表上实现插入和删除运算必须移动结点才能够反映出结点间逻辑关系的变化(1)插入：在表的第i(1≤i≤n+1

8、)个位置上，插入一个新结点x，使线性表的长度加1。基本步骤为：①将结点ai…an各后移一个位置,以便空出第i个位置；②将新结点x置入第i个位置；③表长加l元素a1a2a3……ai-1aiai+1……an相对地址012……i-2i-1i……n-1基本