数据结构总复习 第1章绪论 第6章树和二叉树 第2章线性表 第7章广义表 第3章栈和队列 第8章图 第4章串 第9章查找 第5章数组和稀疏矩阵第10章内排序
第1章 绪论 第2章 线性表 第3章 栈和队列 第4章 串 第5章 数组和稀疏矩阵 第6章 树和二叉树 第8章 图 数据结构总复习 第9章 查找 第10章 内排序 第7章 广义表
第1章绪论 数据结构的定义 数据->数据元素->数据项 数据结构是指数据以及相互之间的联系。包括 (1)数据的逻辑结构。 (2)数据的存储结构(物理结构)。 (3)施加在该数据上的运算
第1章 绪论 1.数据结构的定义 数据->数据元素 ->数据项 数据结构是指数据以及相互之间的联系。包括: (1)数据的逻辑结构。 (2)数据的存储结构(物理结构)。 (3)施加在该数据上的运算
数据的逻辑结构是从逻辑关系上描述数据,它与 数据的存储无关,是独立于计算机的。 数据的存储结构是逻辑结构用计算机语言的实现 (亦称为映象),它是依赖于计算机语言的。 数据的运算是定义在数据的逻辑结构上的,每种 逻辑结构都有一组相应的运算。但运算的实现与数 据的存储结构有关
数据的逻辑结构是从逻辑关系上描述数据,它与 数据的存储无关,是独立于计算机的。 数据的存储结构是逻辑结构用计算机语言的实现 (亦称为映象),它是依赖于计算机语言的。 数据的运算是定义在数据的逻辑结构上的,每种 逻辑结构都有一组相应的运算。但运算的实现与数 据的存储结构有关
逻辑结构主要有两大类: (1)线性结构 (2)非线性结构: 1)树形结构 2)图形结构
逻辑结构主要有两大类: (1)线性结构 (2)非线性结构: 1)树形结构 2)图形结构
存储结构分为如下四种: (1)顺序存储方法 (2)链式存储方法 (3)索引存储方法 (4)散列存储方法
存储结构分为如下四种: (1)顺序存储方法 (2)链式存储方法 (3)索引存储方法 (4)散列存储方法
2抽象数据类型 抽象数据类型( Abstract Data Type简写为 ADT)指的是用户进行软件系统设计时从向题的数 学模型中抽象岀来的逻辑数据结构和逻辑数据结构 上的运算,而不考虑计算机的具体存储结构和运算 的具体实现算法
2.抽象数据类型 抽象数据类型(Abstract Data Type简写为 ADT)指的是用户进行软件系统设计时从问题的数 学模型中抽象出来的逻辑数据结构和逻辑数据结构 上的运算,而不考虑计算机的具体存储结构和运算 的具体实现算法
3什么是算法 算法是对特定问题求解步骤的一种描述,它 是指令的有限序列。 算法的五个重要的特性: (1)有穷性 (2)确定性 (3)可行性 (4)有输入 (5)有输出
3.什么是算法 算法是对特定问题求解步骤的一种描述,它 是指令的有限序列 。 算法的五个重要的特性 : (1)有穷性 (2)确定性 (3)可行性 (4)有输入 (5)有输出
4算法分析 (1)算法的时间复杂度:是指其基本运算 在算法中重复执行的次数。 算法中基本运算次数T(m)是问题规模n的某 个函数f(m),记作 T(n =o((n)) 记号“O”读作“大0”,它表示随问题规 模n的增大算法执行时间的增长率和f(n)的增长 率相同
4.算法分析 (1)算法的时间复杂度:是指其基本运算 在算法中重复执行的次数。 算法中基本运算次数T(n)是问题规模n的某 个函数f(n),记作: T(n)=O(f(n)) 记号“O”读作“大O”,它表示随问题规 模n的增大算法执行时间的增长率和f(n)的增长 率相同
(2)算法空间复杂度:是对一个算法在运行过程 中临时占用的存储空间大小的量度 对于空间复杂度为0(1)的算法称为原地工 作或就地工作算法
(2)算法空间复杂度:是对一个算法在运行过程 中临时占用的存储空间大小的量度 。 对于空间复杂度为O(1)的算法称为原地工 作或就地工作算法
第2章线性表 1线性表的定义 线性表是具有相同特性的数据元素的一个有限 序列。该序列中所含元素的个数叫做线性表的长 度,用n表示,n≥0。当n=0时,表示线性表是一 个空表,即表中不包含任何元素
第2章 线性表 1.线性表的定义 线性表是具有相同特性的数据元素的一个有限 序列。该序列中所含元素的个数叫做线性表的长 度,用n表示,n≥0。当n=0时,表示线性表是一 个空表,即表中不包含任何元素