文档介绍：数据结构 Office 公共基础( 一)韩磊宁师 VIP 速成班考点 1算法的基本概念?计算机解题的过程实际上是在实施某种算法,这种算法称为计算机算法。?:可行性、确定性、有穷性、拥有足够的情报。?: 一个算法由两种基本要素组成: 一是对数据对象的运算和操作; 二是算法的控制结构。?(1)算法中对数据的运算和操作在一般的计算机系统中,基本的运算和操作有以下 4类: 算术运算、逻辑运算、关系运算和数据传输。?(2)算法的控制结构:算法中各操作之间的执行顺序称为算法的控制结构。?描述算法的工具通常有传统流程图、 N-S 结构化流程图、算法描述语言(C语言,汇编,文字) 等。?一个算法一般都可以用顺序、选择、循环 3种基本控制结构组合而成。传统流程图 N-S 流程图考点 2算法复杂度?时间复杂度一个算法所需要时间一般不特别说明,讨论的时间复杂度均是最坏情况下的时间复杂度。这样做的原因是:最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界,这就保证了算法的运行时间不会比任何更长。?空间复杂度占用存储空间的大小考点 3数据结构的定义?数据结构作为计算机的一门学科,主要研究和讨论以下三个方面: (1)数据集合中个数据元素之间所固有的逻辑关系,即数据的逻辑结构; (2 )在对数据元素进行处理时,各数据元素在计算机中的存储关系,即数据的存储结构; (3)对各种数据结构进行的运算。考点 4线性结构与非线性结构?线性结构?对于数据结构课程而言,简单地说,线性结构是 n个数据元素的有序(次序) 集合。?它有四个基本特征: ?"第一个元素"; ?"最后的元素"; ?,其它数据元素均有唯一的"后继"; ?,其它数据元素均有唯一的"前驱"。?常用的线性结构有:线性表,栈,队列,双队列,数组,串。关于广义表,是一种非线性的数据结构。哈希表常见的非线性结构有:树(二叉树等),图(网等) 非线性结构考点 5栈和队列及其基本运算?1、栈的定义 栈( Stack )是限制仅在表的一端进行插入和删除运算的线性表。(1) 通常称插入、删除的这一端为栈顶( Top ),另一端称为栈底( Bottom )。(2) 当表中没有元素时称为空栈。(3) 栈为后进先出( Last In First Out )的线性表,简称为 LIFO 表。 栈的修改是按后进先出的原则进行。每次删除( 退栈)的总是当前栈中"最新"的元素,即最后插入( 进栈)的元素,而最先插入的是被放在栈的底部,要到最后才能删除。?栈的基本运算有:入栈,出栈(删除栈顶元素), 初始化、置空、判断栈是否为空或满、提取栈顶元素等,对栈的操作都是在栈顶进行的。?2、定义 队列( Queue )是只允许在一端进行插入,而在另一端进行删除的运算受限的线性表 ( 1)允许删除的一端称为队头( Front )。 ( 2)允许插入的一端称为队尾( Rear )。 ( 3)当队列中没有元素时称为空队列。 ( 4)队列亦称作先进先出( First In First Out )的线性表,简称为 FIFO 表。 队列的修改是依先进先出的原则进行的。新来的成员总是加入队尾(即不允许"加塞"), 每次离开的成员总是队列头上的(不允许中途离队),即当前"最老的"成员离队。【例】在队列中依次加入元素 a 1,a 2,…, a n之后, a 1是队头元素, a n是队尾元素。退出队列的次序只能是 a 1,a 2,…,a n。考点 6线性链表的基本概念?1、链接存储方法 链接方式存储的线性表简称为链表( Linked List )。 链表的具体存储表示为: ①用一组任意的存储单元来存放线性表的结点(这组存储单元既可以是连续的,也可以是不连续的) ②链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系,在存储每个结点值的同时,还必须存储指示其后继结点的地址(或位置)信息(称为指针( pointer )或链(link) ) 注意: 链式存储是最常用的存储方式之一,它不仅可用来表示线性表,而且可用来表示各种非线性的数据结构。