1二级公共基础知识第一章数据结构基础2内容提要•算法:算法的基本概念、算法复杂度•数据结构的基本概念：什么是数据结构、数据结构的图形表示、线性结构与非线性结构•线性表及其顺序存储结构：线性表的基本概念、顺序存储结构、插入运算、删除运算•栈和队列：栈及其基本运算、队列及其基本运算•线性链表：基本概念、基本运算、循环链表及其基本运算•树与二叉树：树的基本概念、二叉树及其基本性质、二叉树的存储结构、二叉树的遍历•查找技术：顺序查找、二分法查找•排序技术：交换类排序法、插入类排序法、选择类排序法31.1算法41.1.1算法的基本概念•算法是解题方案的准确而完整的描述，它不等于程序，也不等计算方法。•1．算法的基本特征–可行性(effectiveness)–确定性(definiteness)–有穷性(finiteness)–拥有足够的情报•2．算法的基本要素–算法中对数据的运算和操作•算术运算:包括加、减、乘、除等）•逻辑运算:包括“与”、“或”、“非”等运算）•关系运算:包括“大于”、“小于”、“等于”、“不等于”等）•数据传输:包括赋值、输入、输出等操作–算法的控制结构51.1.1算法的基本概念•3．算法设计的基本方法–列举法–归纳法–递推–递归–减半递推技术–回溯法61.1.2算法复杂度•算法复杂度：时间复杂度、空间复杂度•1．算法的时间复杂度–执行算法所需要的计算工作量–与下列因素有关：•书写算法的程序设计语言•编译产生的机器语言，代码质量•机器执行指令的速度•问题的规模71.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)：平方阶–O(n3)：立方阶O(logn)：对数阶O(2n)：指数阶81.1.2算法复杂度•n×n矩阵相乘算法：•时间复杂度为O(n3)。91.1.2算法复杂度•分析算法的工作量两种方法：–平均性态–最坏情况复杂性101.1.2算法复杂度•2．算法的空间复杂度–算法执行过程中所需的最大存储空间–存储量包括以下三部分•算法程序所占的空间•输入的初始数据所占的存储空间•算法执行过程中所要的额外空间–算法空间复杂度可定义为：S(n)=O(f(n))–原地工作(inplace)的算法：记作O(1)–压缩存储技术111.2数据结构的基本概念121.2.1什么是数据结构•1．数据结构研究的主要内容–数据的逻辑结构–数据的存储结构–对各种数据结构进行的运算•2．研究数据结构目的–提高数据处理的速度–尽量节省在数据处理过程中所占用的计算机存储空间131.2.1什么是数据结构•1．数据结构研究的主要内容–数据的逻辑结构–数据的存储结构–对各种数据结构进行的运算•2．研究数据结构目的–提高数据处理的速度–尽量节省在数据处理过程中所占用的计算机存储空间141.2.1什么是数据结构1．数据的逻辑结构2、数据的存储结构3、数据的运算：检索、排序、插入、删除、修改等。A．线性结构B．非线性结构A顺序存储B链式存储线性表栈队树形结构图形结构数据结构的三个方面151.2.1什么是数据结构•3．数据结构的定义–相互有关联的数据元素的集合–数据元素之间的关系可以用前后件关系来描述–一个数据结构应包含以下两方面信息：•表示数据元素的信息•表示各数据元素之间的前后件关系161.2.1什么是数据结构•4．数据的逻辑结构–对数据元素之间的逻辑关系的描述–只抽象地反映数据元素之间的逻辑关系，与计算机中的存储无关–两个要素：•数据元素的集合，通常记为D；•前后件关系，通常记为R–一个数据结构B可以表示为：B=（D，R）171.2.1什么是数据结构•5．数据的存储结构–数据的逻辑结构在计算机存储空间中的存放形式，它包括数据元素的存储方式和关系的存储方式。–常用的存储结构：•顺序•链式•索引–一种数据结构可根据需要采用不同的存储结构。采用不同的存储结构，其数据处理的效率是不同181.2.2数据结构的图形表示•数据结点：用方框表示–根结点、终端结点•前后件关系：用有向线段表示•基本运算：–插入运算–删除运算–查找...
