高中信息技术 第1章 数据结构课件 沪教版选修1

《高中信息技术 第1章 数据结构课件 沪教版选修1》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、二级公共基础知识第一章数据结构基础1内容提要算法:算法的基本概念、算法复杂度数据结构的基本概念：什么是数据结构、数据结构的图形表示、线性结构与非线性结构线性表及其顺序存储结构：线性表的基本概念、顺序存储结构、插入运算、删除运算栈和队列：栈及其基本运算、队列及其基本运算线性链表：基本概念、基本运算、循环链表及其基本运算树与二叉树：树的基本概念、二叉树及其基本性质、二叉树的存储结构、二叉树的遍历查找技术：顺序查找、二分法查找排序技术：交换类排序法、插入类排序法、选择类排序法21.1算法31.1.1算法的基本

2、概念算法是解题方案的准确而完整的描述，它不等于程序，也不等计算方法。1．算法的基本特征可行性(effectiveness)确定性(definiteness)有穷性(finiteness)拥有足够的情报2．算法的基本要素算法中对数据的运算和操作算术运算:包括加、减、乘、除等）逻辑运算:包括“与”、“或”、“非”等运算）关系运算:包括“大于”、“小于”、“等于”、“不等于”等）数据传输:包括赋值、输入、输出等操作算法的控制结构41.1.1算法的基本概念3．算法设计的基本方法列举法归纳法递推递归减半递推技术回

3、溯法51.1.2算法复杂度算法复杂度：时间复杂度、空间复杂度1．算法的时间复杂度执行算法所需要的计算工作量与下列因素有关：书写算法的程序设计语言编译产生的机器语言，代码质量机器执行指令的速度问题的规模61.1.2算法复杂度问题的规模函数算法的工作量=f(n)算法中基本操作重复执行的频率T(n)，是问题规模n的某个函数f(n)，记作：T(n)=O(f(n))记号“O”读作“大O”。表示随问题规模n的增加，算法执行时间的增长率和f(n)相应增加。常见算法复杂度：O(1)：常数阶O(n)：作线性阶O(n2)：

4、平方阶O(n3)：立方阶O(logn)：对数阶O(2n)：指数阶71.1.2算法复杂度n×n矩阵相乘算法：时间复杂度为O(n3)。81.1.2算法复杂度分析算法的工作量两种方法：平均性态最坏情况复杂性91.1.2算法复杂度2．算法的空间复杂度算法执行过程中所需的最大存储空间存储量包括以下三部分算法程序所占的空间输入的初始数据所占的存储空间算法执行过程中所要的额外空间算法空间复杂度可定义为：S(n)=O(f(n))原地工作(inplace)的算法：记作O(1)压缩存储技术101.2数据结构的基本概念111

5、.2.1什么是数据结构1．数据结构研究的主要内容数据的逻辑结构数据的存储结构对各种数据结构进行的运算2．研究数据结构目的提高数据处理的速度尽量节省在数据处理过程中所占用的计算机存储空间121.2.1什么是数据结构1．数据结构研究的主要内容数据的逻辑结构数据的存储结构对各种数据结构进行的运算2．研究数据结构目的提高数据处理的速度尽量节省在数据处理过程中所占用的计算机存储空间131.2.1什么是数据结构1．数据的逻辑结构2、数据的存储结构3、数据的运算：检索、排序、插入、删除、修改等。A．线性结构B．非线性

6、结构A顺序存储B链式存储线性表栈队树形结构图形结构数据结构的三个方面141.2.1什么是数据结构3．数据结构的定义相互有关联的数据元素的集合数据元素之间的关系可以用前后件关系来描述一个数据结构应包含以下两方面信息：表示数据元素的信息表示各数据元素之间的前后件关系151.2.1什么是数据结构4．数据的逻辑结构对数据元素之间的逻辑关系的描述只抽象地反映数据元素之间的逻辑关系，与计算机中的存储无关两个要素：数据元素的集合，通常记为D；前后件关系，通常记为R一个数据结构B可以表示为：B=（D，R）161.2.1

7、什么是数据结构5．数据的存储结构数据的逻辑结构在计算机存储空间中的存放形式，它包括数据元素的存储方式和关系的存储方式。常用的存储结构：顺序链式索引一种数据结构可根据需要采用不同的存储结构。采用不同的存储结构，其数据处理的效率是不同171.2.2数据结构的图形表示数据结点：用方框表示根结点、终端结点前后件关系：用有向线段表示基本运算：插入运算删除运算查找、分类、合并、分解、复制、修改、……181.2.3线性结构与非线性结构空的数据结构：一个数据元素都没有线性结构如果一个非空数据结构满足下列两个条件：有且只

8、有一个根结点；每一个结点最多有一个前件，也最多有一个后件。常见的线性结构有：线性表、栈与队列、线性链表非线性结构如果一个数据结构不是线性结构常见的非线性结构有：树、二叉树、图191.3线性表及其顺序存储结构201.3.1线性表的基本概念线性表：由n(n≥0)个相同类型数据元素构成的有限序列：n定义为线性表的表长；n=0时的线性表被称为空表。称i为在线性表中的位序。例如：英文大写字母表（A，B，C，D，E，F，…X，Y，Z）同一花色的13张扑