文档介绍：数据结构与算法
第1章数据结构与算法 算法 1 算法的基本概念 2 算法复杂度 数据结构的基本概念 1 什么是数据结构 2 数据结构的图形表示
3 线性结构与非线性结构 线性表及其顺序存储结构 1 线性表的基本概念 2 线性表的顺序存储结构 3 顺序表的插入运算 4 顺序表的删除运算 栈和队列 1 栈及其基本运算 2 队列及其基本运算 线性链表 1 线性链表的基本概念 2 线性链表的基本运算
3 循环链表及其基本运算 树与二叉树 1 树的基本概念 2 二叉树及其基本性质 3 二叉树的存储结构 4 二叉树的遍历 查找技术 1 顺序查找 2 二分法查找 排序技术 1 交换类排序法 2 插入类排序法 3 选择类排序法
1、算法
算法
算法是指为解决某个特定问题而采取的确定且有限的步骤的一种描述,它是有限的指令序列,在有限的时间内被求解。
算法的复杂度
可分为时间复杂度和空间复杂度,是衡量算法优劣的量度。
时间复杂度:是指执行算法所需要的计算工作量。
常见时间复杂度有:
空间复杂度:一般是指执行此算法所需要的内存空间量。
有穷性:一个算法应包含有限个操作步骤。
确定性:算法中每一条指令必须有确切的含义。
有效性(可行性) :算法中的每一步骤都应当能有效地执行,并得到结果。
有输入:执行算法时从外界取得的信息,有零个或多个输入。
有输出:算法得到的结果就是算法的输出,有一个或多个输出。
算法的基本特性
算法中对数据的运算和操作:对于所有算法都是按照要求从环境能够运行的所有操作中选择合适的操作所组成的一组指令序列。共四类
算术运算:主要包括加、减、乘、除等运算。
逻辑运算:主要包括“与”、“或”、“非”等运算。
关系运算:主要包括“大于”、“小于”、“等于”、和“不等于”等运算。
数据传输:主要包括赋值、输入和输出等操作。
算法的控制结构:算法中各操作之间的执行顺序。(顺序、选择、循环)
算法的基本要素
算法的描述方法
用自然语言表示用传统流程图表示
用N-S流程图表示用伪代码表示
算法设计的方法:
列举法
归纳法
递推
递归
回溯
正确性(Correctness):算法应满足具体问题的需求。
可读性(Readability):算法主要是为了人的阅读与交流,其次才是及其执行,可读性好有助于人对算法的理解。
健壮性(Robustness):当输入非法是,算法应能适当的作出反应或进行处理。
高效性:有效使用存储空间和有较高的时间效率。
算法设计的要求
举例
计算机算法指的是____。
算法的时间复杂度取决于____。
算法的空间复杂度是指_____。
。
。
。
。
描述算法的常用方法有____。自然语言、传统流程图、N-S流程图、伪代码描述语言
数据(Data)的概念
是对客观事物的符号表示,在计算机科学中是指能输入到计算机中并被计算机程序处理的符号的总称。
数据元素(Data Element)
是数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理。
2 数据结构
数据对象(Data Object)
是性质相同的数据元素的集合,是数据的一个子集。
数据结构(Data Structure)
是相互之间存在一种或多种特定关系的数据元素的集合,即带有结构的数据元素之间的前后件关系。
2 数据结构