数据结构基础概念及算法概念 -凯发k8官方网

1.数据：
数据是能输入计算机且能够被计算机处理的各种符号的集合。
（1）是信息的载体
（2）是对客观事物符号化的表示
（3）能被计算机识别，储存和加工
包括：
（1）数值型数据：整数实数等；
（2）非数值型：文字，图像，图行，声音等
2.数据元素：
是数据的基本单位，也称元素，记录，结点或者顶点（比如职工管理信息一个职工的所有信息，姓名职工号性别的集合）；
3.数据项：是数据元素的基本组成单位（姓名或者性别等）
4.数据对象：就是性质相同的数据元素的集合（性质相同就是数据元素具有相同数量和类型的数据项）
5.数据结构：是指相互之间存在一种或者多种特定关系的数据元素的集合
数据结构的内容：
（1）数据结构之间的逻辑关系也称逻辑结构（描述数据元素之间的逻辑关系与数据存储无关，独立于计算机）
（2）数据元素及其关系在计算机内存中的表示（又称为映像），称为数据的物理结构或数据的存储结构
（3）数据的运算和实现，对数据元素可以施加操作以及这些操作在相应的存储结构上的实现。

物理结构是逻辑关系的映像与元素本身的映像
逻辑结构是数据元素的抽象，物理结构是数据结构的实现
6.逻辑结构的种类：
第一种归类：
（1）线性结构：有且仅有一个开始和一个终端结点，并且最多有一个直接前驱和后继。
（列如线性表，栈，队列，串）
（2）非线性结构：一个结点可能有多个前驱和后继（树和图）
第二中归类：

7.数据的四种基本存储结构:
(1)顺序存储结构：用一段连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置决定。（c语言数组）
(2)链式存储结构：用任意的存储单元存储数据元素，数据元素之间的逻辑关系用指针表示（c语言链表）
(3)索引存储结构：
(4)散列存储结构：
8.数据类型的作用：
(1)约束变量或者常量的取值范围
(2)约束变量或者常量的操作
9.抽象数据类型（adt）：
抽象：是指抽取出事物具有的普遍性的本质



10.算法时间效率的度量（主要介绍事前分析估测的方法）：
首先算法五个基本特性：输入，输出，有穷性，确定性，可行性。
首先算法是一定要有输出的，可以没有输入。有穷指算法在执行有限的步骤后自动结束而不会出现无限循环，并且每个步骤都能在有限的时间内完成。确定性指每一步都有确定含义不会出现二义性。可行性是指算法的每一步都是可行的，每一步都能够通过执行有限次数完成。
算法的设计要求：
正确性，可读性（易懂），健壮性（在输入错误指令时算法能进行相应处理而不是报错或者莫名其妙的结果），高效率和低存储量需求

（1）算法的运行时间t(n)=每条语句的执行次数*该语句执行一次所需要的时间
（2）算法渐进时间复杂度：若有某个辅助函数发t(n)/f(n)的极限值等于不为0的常数，则二者是同数 量级函数记作t(n)=of(n)称of(n)为算法渐进时间复杂度（o）是数量级符号，简称时间复杂度
（3）算法的基本语句：执行次数最多的语句。对算法运行时间贡献最大的语句。算法中重复执行次数和算法的执行时间成正比的语句
11.分析算法时间复杂度的基本方法：
那么如何推导o阶
（1）用常数1取代运行时间中所有加法常数
（2）在修改后的运行次数函数中只保留最高阶项，舍去所有低阶项
（3）如果最高阶项存在且不是1，则去除与这个项相乘的常数得到的就是o阶（去除最高项系数）。
例1：

例二：
例三：

有些时候重复的次数会随着问题的不同而不同，比如从数组中查找某一个元素，最快一次就会查找到，最慢就是查不到或者刚好最后一个
一般计算所有情况的平均值，这种时间复杂度的计算方法称为平均时间复杂度，还有是最坏时间复杂度，一般再没说明的情况下都是指最坏情况复杂度
11.各空间复杂度的比较;

12.渐进空间复杂度（重点是时间复杂度问题）：
s(n)=of(n);
算法要占据的空间：
（1）算法本身要占据的空间（输入输出指令变量等）
（2）算法要使用的辅助空间（如果输入数据所占空间只取决于问题本身和算法无关，这样只需要分析该算法的辅助空间相对于输入的数据是不是一个常数，如果是那么称算法为原地工作，空间复杂度为o（1）
下面这个例子：

以上例子，在原有基础地数据外，要用一个辅助t进行交换值（只用到这一个空间），在原数组有n个元素地情况下，空间复杂度为1.但是对于第二种方法则是有一个辅助数组，那么原数组有多少个值，辅助数组也要有多少空间来存储，所以与原数组有多少值有关，在原数组有n个元素地情况下，那么
空间复杂度为n;
13.函数的渐近增长：

总结

以上是凯发k8官方网为你收集整理的数据结构基础概念及算法概念的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得凯发k8官方网网站内容还不错，欢迎将凯发k8官方网推荐给好友。