大学计算机基础 第4章.ppt

大学计算机基础 第4章.ppt

ID:51604896

大小:838.31 KB

页数:35页

时间:2020-03-25

大学计算机基础 第4章.ppt_第1页
大学计算机基础 第4章.ppt_第2页
大学计算机基础 第4章.ppt_第3页
大学计算机基础 第4章.ppt_第4页
大学计算机基础 第4章.ppt_第5页
资源描述:

《大学计算机基础 第4章.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

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

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

3、增加、修改、删除算法:算法是对具体问题求解过程和步骤的一种描述基本概念算法算法的5个特性:①有穷性②确定性③可行性④零个或多个的输入⑤有1个或多个的输出算法设计的要求:①正确性②可读性③健壮性④效率与低存储量需求效率是指一个算法在计算机上运行所花费的时间,以时间复杂度来衡量。所谓时间复杂度是指算法中所包含简单操作的执行次数。存储量需求指算法执行过程中所需要占用存储器的存储空间,以空间复杂度来衡量。时间复杂度:T(n)=O(f(n))其中的f(n)一般是算法中频度最大的语句频度,与问题的规模n有关。常见的时间复杂度,按数量

4、级递增排列依次为:O(1)O(log2n)O(n)O(nlog2n)O(n^2)O(n^3)O(n^k)O(2^n)基本概念算法算法的描述用自然语言表示算法:就是用人们所熟悉的自然语言把算法的各个步骤依次表示出来。用流程图表示算法:就是用一些大家共识的专用图形符号和带有箭头的流程线来表示算法。用程序设计语言表示算法:用计算机能理解和执行的程序设计语言把算法表示出来,然后把程序输入计算机并执行,计算机才能按照预定的算法去解决问题。基本概念算法基本数据结构线性表:是n(n≥O)个同类型数据元素(结点)的有穷序

5、列。其中数据元素的个数n称为线性表的长度(简称表长)。表长为O的线性表称为空表。表示成:(a1,a2…,an)线性表的定义和基本特征线性表线性表逻辑结构的基本特征:①存在惟一的一个被称为“第一个”的数据元素和惟一的一个被称为“最后一个”的数据元素;②除第一个数据元素外,其他数据元素有且仅有一个直接前趋元素;③除最后一个数据元素外,其他数据元素有且仅有一个直接后继元素。顺序表是用一组地址连续的存储单元依次存储线性表的各个数据元素。元素a1a2a3……ai-1aiai+1……an相对地址012……i-2i-1i……n-1特点

6、:逻辑结构中相邻的结点在存储结构中仍相邻基本数据结构线性表的顺序存储结构线性表顺序表在顺序表上实现插入和删除运算必须移动结点才能够反映出结点间逻辑关系的变化(1)插入:在表的第i(1≤i≤n+1)个位置上,插入一个新结点x,使线性表的长度加1。基本步骤为:①将结点ai…an各后移一个位置,以便空出第i个位置;②将新结点x置入第i个位置;③表长加l元素a1a2a3……ai-1aiai+1……an相对地址012……i-2i-1i……n-1基本数据结构插入、删除运算在顺序表上的实现线性表(2)删除:将表的第i(1≤i≤n)

7、个结点删去,使线性表的长度减1。基本步骤为:①结点ai+1…an依次前移一个位置(覆盖被删结点ai);②表长减1元素a1a2a3……ai-1aiai+1……an相对地址012……i-2i-1i……n-1基本数据结构插入、删除运算在顺序表上的实现线性表单链表是用一组任意的存储单元来存放线性表的结点。单链表的结点(每个存储单元)由数据域(data)和指针域(next)两部分组成;数据域用于存储线性表一个数据元素;指针域用于存放一个指针,该指针指向其直接后继结点。这样,所有结点通过指针链接起来,因此链表中结点的逻辑次序和物理次

8、序不一定相同a1an…^head特点:指针为数据元素之间的逻辑关系的映像基本数据结构线性表的链式存储结构线性表单链表循环链表是一种首尾相接的链表双向链表,就是在单链表的每个结点里再增加一个指向其直接前趋的指针域prior,这样形成的链表就有两条不同方向的链。双(向)循环链表:头尾相链接的双向链表a1

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。