数据结构与算法--基本概念⼀、数据结构的研究内容
1.通常⽤计算机解决⼀个问题的步骤:
具体问题抽象为数学模型-->设计算法-->编程、调试、运⾏
2.具体问题抽象为数学模型过程为:
分析问题-->提取操作对象-->出操作对象之间的关系-->⽤数学语⾔描述
3.描述⾮数值计算问题的数学模型不是数学⽅程，⽽是诸如表、树、图之类的具有逻辑关系的数据
4.数据结构研究⾮数值计算程序设计中计算机的操作对象以及操作对象之间的关系及操作
⼆、基本概念和定义
1.数据
1) 数据是能输⼊计算机且能被计算机处理的各种符号的集合
2) 数据是信息的载体，是对客观事物符号化的表⽰，能够被计算机识别、存储和加⼯
3) 数据包括数值型数据(整数，实数等)和⾮数值型数据(⽂字、图像、图形、声⾳等)
2.数据元素
1) 数据元素是数据的基本单位，在计算机程序中通常作为⼀个整体进⾏考虑和处理
2) 数据元素也简称元素，或称为记录、结点或顶点
3) ⼀个数据元素可由若⼲个数据项组成
3.数据项
1) 数据项构成数据元素的不可分割的最⼩单位
4.数据、数据元素、数据项三者之间的关系:
数据 > 数据元素 > 数据项
例:  学⽣信息表 > 某位学⽣信息记录 > 学⽣姓名、学号、成绩等
5.数据对象
1) 数据对象是性质相同的数据元素的集合，是数据的⼀个⼦集
例:  整数数据对象是集合N = {0，±1，±2，...}
字母字符数据对象是集合C = {'A'、'B'、'C’、...}
学⽣信息表也可看作⼀个数据对象
6.数据结构
1) 数据元素不是孤⽴存在的，它们之间存在着某种关系，数据元素相互之间的关系称为结构
2) 数据结构是指相互之间存在⼀种或多种特定关系的数据元素集合(或带结构的数据元素的集合)
3) 数据元素之间的逻辑关系，也称为逻辑结构
//与数据的存储⽆关，独⽴于计算机，是从具体问题抽象出来数学模型
4) 数据元素及其关系在计算机内存中的表⽰(⼜称为映像)，称为数据的物理结构或数据的存储结构
5) 数据的运算和实现，即对数据元素可以施加的操作以及这些操作在相应的存储结构上的实现
6) 逻辑结构与存储结构的关系:
* 存储结构是逻辑关系的映像与元素本⾝的映像
* 逻辑结构是数据结构的抽象，存储结构是数据结构的实现
* 两者综合起来建⽴了数据元素之间的结构关系
7.逻辑结构的种类
1) 划分⽅法⼀: 线性结构和⾮线性结构
* 线性结构: 有且仅有⼀个开始和⼀个终端结点，并且所有结点都最多只有⼀个直接前驱和⼀个直接后继
//例: 线性表、栈、队列、串
* ⾮线性结构: ⼀个结点可能有多个直接前驱和直接后继
//例: 树、图
2) 划分⽅法⼆ (四种基本逻辑结构)：集合、线性、树、图
* 集合:  结构中的数据元素之间除了同属于⼀个集合的关系外，⽆任何其他关系
* 线性结构: 结构中的数据元素之间存在着⼀对⼀的线性关系
* 树形结构: 结构中的数据元素之间存在着⼀对多的层次关系
* 图形结构或⽹状结构: 结构中的数据元素之间存在着多对多的任意关系
8.存储结构的种类
顺序存储结构(数组): ⽤⼀组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置来表⽰                  链式存储结构(指针): ⽤⼀组任意的存储单元存储数据元素，数据元素之间的逻辑关系⽤指针来表⽰
索引存储结构: 在存储结点信息的同时，还建⽴附加的索引表
// 索引表的每⼀项称为⼀个索引项，索引项的⼀般形式是: (关键字，地址)
// 关键字是能唯⼀标识⼀个结点的那些数据项
//若每个结点在索引表中都有⼀个索引项，则该索引表称之为稠密索引
// 若⼀组节点在索引表中只对应⼀个索引项，则该索引表称之为稀疏索引
散列存储结构: 根据结点的关键字直接计算出该结点的存储地址
9.数据类型
1) 数据类型是⼀组性质相同的值的集合以及定义于这个值集合上的⼀组操作的总称
//数据类型 = 值的集合 + 值集合上的⼀组操作
2) 抽象数据类型是指⼀个数学模型以及定义在此数学模型上的⼀组操作
* 由⽤户定义，从问题抽象出数据模型(逻辑结构)
* 还包括定义在数据模型上的⼀组抽象运算(相关操作)
* 不考虑计算机内的具体存储结构与运算的具体实现算法
3) 抽象数据类型的形式定义:
抽象数据类型可⽤(D,S,P)三元组表⽰                //D是数据对象；S是D上的关系集；P是对D的基本操作集
4) 抽象数据类型的定义格式:
ADT 抽象数据类型名{
数据对象:<；数据对象的定义>                    //数据对象、数据关系的定义⽤伪代码描述
数据关系:<；数据关系的定义>
基本操作:<；基本操作的定义>                  //基本操作名(参数表)、初始条件(初始条件描述)、操作结果(操作结果描述)              }ADT 抽象数据类型名
基本操作定义格式说明:
* 参数表: 赋值参数只为操作提供输⼊值；引⽤参数以&打头，除可提供输⼊值外，还将返回操作结果
* 初始条件: 描述操作执⾏之前的数据结构和参数应满⾜的条件，若不满⾜，则操作失败，返回出错信息；若初始条件为空，则省略之          * 操作结果: 说明操作正常完成之后，数据结构的变化状况和应返回的结果
三、算法和算法分析
1.算法的定义
1) 算法是对特定问题求解⽅法和步骤的⼀种描述，它是指令的有限序列，其中每个指令表⽰⼀个或多个操作
2) 算法是解决问题的⼀种⽅法或⼀个过程，考虑如何将输⼊转换成输出，⼀个问题可以有多种算法
3) 程序是⽤某种程序设计语⾔对算法的具体实现
4) 程序 = 数据结构 + 算法
//数据结构通过算法实现操作，算法根据数据结构设计程序
2.算法的描述
* ⾃然语⾔: 英语、中⽂
* 流程图: 传统流程图、NS流程图
* 伪代码/类语⾔: 类C语⾔
* 程序代码: C语⾔程序...等等
3.算法的特性
* 有穷性: ⼀个算法必须总是在执⾏有穷步之后结束，且每⼀步都在有穷时间内完成
* 确定性: 算法的每⼀条指定必须有确切的含义，在任何条件下只有唯⼀的⼀条执⾏路径，对于相同的
输⼊只能得到相同的输出        * 可⾏性: 算法是可执⾏的，算法描述的操作可以通过已经实现的基本操作执⾏有限次来实现
* 输⼊: ⼀个算法有零个或多个输⼊
* 输出: ⼀个算法有⼀个或多个输出
4.算法设计的要求
* 正确性: 算法满⾜问题要求，能正确解决问题
* 可读性: 算法主要是为了⼈的阅读和交流，其次才是为计算机执⾏，因此算法应该易于⼈的理解
// 晦涩难读的算法易于隐藏较多错误⽽难以调试
* 健壮性: 指当输⼊⾮法数据时，算法恰当的做出反应或进⾏相应处理，⽽不是产⽣莫名其妙的输出结果
// 处理出错的⽅法，不应是中断程序的执⾏，⽽应是返回⼀个表⽰错误或错误性质的值
* ⾼效性: 要求花费尽量少的时间和尽量低的存储需求
5.算法分析
1) 通过算法的效率⾼低来评判不同算法的优劣程度
流程图转换为ns图2) 算法效率依据以下两个⽅⾯来考虑:
(1).时间效率: 指的是算法所耗费的时间
(2).空间效率: 指的是算法执⾏过程中所耗费的存储空间
6.算法时间效率的度量
1) 算法时间效率可以⽤依据该算法编制的程序在计算机上执⾏所消耗的时间来度量
2) 两种度量⽅法
事后统计: 将算法实现，测算其时间和空间开销
//缺点: 编写程序实现算法将花费较多的时间和精⼒；所得实验结果依赖于计算机的软硬件等环境因素，掩盖算法本⾝的优劣            事前分析: 对算法所消耗资源的⼀种估算⽅法
3) 事前分析⽅法:
* ⼀个算法的运⾏时间是指⼀个算法在计算机上运⾏所消耗的时间
* ⼤致等于计算机执⾏⼀种简单操作(赋值、⽐较、移动等)所需的时间与算法中进⾏的简单操作次数乘积
//  算法运⾏时间 = ⼀个简单操作所需的时间*简单操作次数
等同于算法中每条语句的执⾏时间之和:    算法运⾏时间 = ∑每条语句的执⾏次数*该语句执⾏⼀次所需的时间
4) 每条语句执⾏⼀次所需的时间，⼀般是随机器⽽异的
// 取决于机器的指令性能、速度以及编译的代码质量，是由机器本⾝软硬件环境决定的，与算法⽆关
5) 假设每条语句所需的时间均为单位时间，我们把算法所耗费的是时间定义为该算法中每条语句的频度之和
for(int i=0;i<n;i++)          //执⾏n+1次
{
for(int j=0;i<n;j++)        //执⾏n(n+1)次
{
c[i][j] = 0;            //执⾏n*n次
for(int k = 0;k<n;k++)    //执⾏n*n*(n+1)次
c[i][j] = c[i][j]+a[i][k]*b[k][j];  //执⾏n*n*n次
}
}                                //时间消耗T(n) = 3n^3+3n^2+2n+1      T(n) = O(n^3)
7.时间复杂度
1) 如有某个辅助函数f(n)，使得当n趋近于⽆穷⼤时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数
记作T(n)=O(f(n))，称O(f(n))为算法的渐进时间复杂度，简称时间复杂度
2) ⼀般情况下，不必计算所有操作的执⾏次数，⽽只考虑算法中基本操作的执⾏的次数，它是问题规模n的某个函数，⽤T(n)表⽰
3) 算法中基本语句重复执⾏的次数是问题规模n的某个函数f(n)，算法的时间量度记作:T(n) = O(f(n))
// 表⽰随着n的增⼤，算法执⾏的时间的增长率和f(n)的增长率相同，称渐进时间复杂度
4) 若 是m次多项式，则T(n) = O()
// 忽略所有低次幂项和最⾼次幂系数，体现出增长率的含义
5) 分析算法时间复杂度的基本⽅法:
1.出语句频度最⼤的那条语句作为基本语句
2.计算基本语句的频度得到问题规模n的某个函数f(n)
3.取其数量级⽤符号"O"表⽰
例:

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。