工业和信息化部网站备案系统查询,wordpress调整行间距,网站备案找回,建设网站思路小王开始专业课的复习一、数据结构是什么二、数据结构中基本概念和术语2.1数据结构的概念2.2按照不同功能划分逻辑结构2.3存储结构中重点顺序存储举例链式存储举例三、抽象数据类型的表示与实现3.1数据类型3.2抽象数据类型 #xff08;ADTs: AbstractData Types#xff09;3.…
小王开始专业课的复习一、数据结构是什么二、数据结构中基本概念和术语2.1数据结构的概念2.2按照不同功能划分逻辑结构2.3存储结构中重点顺序存储举例链式存储举例三、抽象数据类型的表示与实现3.1数据类型3.2抽象数据类型 ADTs: AbstractData Types3.3算法分析重点1. 时间复杂度2. 空间复杂度复习数据结构正式开始
一、数据结构是什么
数据结构是介于数学、计算机软件与计算机硬件的一门核心课程。程序算法数据结构N.沃斯提出
二、数据结构中基本概念和术语
数据data—所有能输入到计算机中去的描述客观事物的符号 —数值性数据 —非数值性数据多媒体信息处理例如视频、图形等数据元素data element—数据的基本单位也称结点node或记录record数据项data item—有独立含义的数据最小单位也称域field数据对象**Data Object相同特性数据元素的集合是数据的一个子集
2.1数据结构的概念
数据结构Data Structure是相互之间存在一种或多种特定关系的数据元素的集合。数据结构是带“结构”的数据元素的集合“结构”就是指数据元素之间存在的关系。
数据结构包括 21两个层次和一个操作 逻辑结构唯一数据元素间抽象化的相互关系与数据的存储无关独立于计算机它是从具体问题抽象出来的数学模型。如集合、线性、树形、图形 存储结构物理结构不唯一数据元素及其关系在计算机存储器中的存储方式。如顺序关键词连续、链式关键词指针、索引关键词逻辑指针清单、散列/哈希关键词地址 一般来说效率最高 操作运算、行为执行不同功能的算法 2.2按照不同功能划分逻辑结构
划分方法一 线性结构---- 有且仅有一个开始和一个终端结点并且所有结点都最多只有一个直接前趋和一个后 继。 例如线性表、栈、队列、串 非线性结构---- 一个结点可能有多个直接前趋和直接后继。 例如树、图划分方法二 集合——数据元素间除“同属于一个集合”外无其它关系换言之数据与数据之间没有关系 线性结构—— 一个对一个如线性表、栈、队列 树形结构—— 一个对多个如树 图形结构—— 多个对多个如图
2.3存储结构中重点
顺序存储举例 链式存储举例 欢迎关注https://blog.csdn.net/hanhanwanghaha 这个可爱的宝藏女孩 三、抽象数据类型的表示与实现
3.1数据类型
定义在一种程序设计语言中变量所具有的数据种类
例如C 语言 基本数据类型 char int float double void 构造数据类型数组、结构体、共用体、文件 数据类型是一组性质相同的值的集合 以及定义于这个集合上的一组运算的总称
3.2抽象数据类型 ADTs: AbstractData Types
也称增广数据类型
—更高层次的数据抽象 —由用户定义用以表示应用问题的数据模型 —由基本的数据类型组成 并包括一组相关的操作
常用格式
3.3算法分析重点
算法定义
一个有穷的指令集这些指令为解决某一特定任务规定了一个运算序列 注意提到指令集、序列集、描述集都是算法的定义
算法的特性 输入有 0 个或多个输入可以不输入系统自动生成 输出有一个或多个输出处理结果 确定性每步定义都是确切、无歧义的 有穷性算法应在执行有穷步后结束 有效性可执行性每一条运算应足够基本
算法设计的评价及要求 正确性 可读性 健壮性不能稍微碰下就不能运行了 高效性时间和空间
算法的度量
1. 时间复杂度
一般情况下算法中基本操作重复执行的时间是问题规模 n 的某个函数 fn算法 执行的时间的增长率和 fn的增长率相同称渐近时间复杂度。 时间复杂度的表示方法有两种 方法 1大 O 法 Tn Ofn 它表示随问题规模 n 的增大算法执行时间的增长率和 fn的增长率相同称作算 法的渐进时间复杂度简称时间复杂度。 方法 2语句频度法 计算该语句重复执行的次数又叫频度统计法。
n*n阶矩阵加法
for i 0; i n; ifor j 0; j n; jc[i][j] a[i][j] b[i][j];
语句的频度Frequency Count : 重复执行的次数n*n;Tn On^2
即矩阵加法的运算量和问题的规模 n 的平方是同一个量级分析算法时间复杂度的基本方法 找出语句频度最大的那条语句作为基本语句 计算基本语句的频度得到问题规模 n 的某个函数 fn 取其数量级用符号“O”表示
for int i 0; i n; i for int j 0; j n; j y ;
fnn2Tn On2时间复杂度是由嵌套最深层语句的频度决定的
void exam float x[ ][ ]int mint n{float sum [ ];for int i 0; i m; i {sum[i] 0.0;for int j 0; j n; j fnm*nsum[i] x[i][j];
}
for i 0; i m; i cout i “ : ” sum [i] endl;
}Tn Om*nO1Ologn On Onlogn On^2 On^3 On^5 O2^n On! 随着 n 值的增大增长速度各不相同n 足够大时存在下列关系 对数函数幂函数指数函数阶乘
so 尽量少用指数阶的算法
关于时间复杂度的运用记得我以前发过相关的文章(用python写的)https://blog.csdn.net/hanhanwanghaha/article/details/107886355
2. 空间复杂度
三个组成部分
存储算法本身所占用的空间算法在运行过程中临时占用的辅助空间算法的输入/输出数据占用的空间
原地工作算法在执行过程中辅助空间是不变的叫原地工作。
数据结构已经走了第一步明天再复习。干高数去 https://blog.csdn.net/hanhanwanghaha宝藏女孩的成长日记 欢迎您的关注 欢迎关注微信公众号宝藏女孩的成长日记 让这个可爱的宝藏女孩在努力的道路上与你一起同行 如有转载请注明出处如不注明盗者必究
