数据结构根本概念和术语
概论1.1 根本概念和术语
1.1.1 根本概念
计算机处理惩罚的的是数值性数据，当计算机处理惩罚用户信息表中的数据的时候，需要弄清3个题目
1.数据的逻辑结构
数据之间存在怎样的内在联系，数据中，有且只有一个是首节点/尾结点，其他节点有且只有一个相邻的位于它之前和之后的结点
2.数据的存储结构
数据在计算机的存储方式称为存储结构。在C语言中，最常见的是用结构数组来存储整个用户的信息表，每一个结构数组元素也是一个结构，用于表示信息用户的一个结点。用户信息表中相邻的结点，对应结构数组中的元素也是一连的，在这种存储方式下，逻辑相邻的结点就必须是物理相邻，被称为顺序存储，另有其他存储方式。
3.数据的运算合集
对数据的存储肯定会涉及到相关的运算。在用户的信息表中，可以举行删除一个用户、增加有一个用户、查找某个用户。应该明确指出这些利用的含义。为一批数据界说的所有运算（或称利用）构成一个运算（利用）集合。
数据结构就是按照肯定的逻辑结构构成的一批数据，利用某种存储方式将数据存储在计算机中，并在这些数据上界说了一个运算集合
1.1.2数据的逻辑结构（数据结构）
数据的逻辑结构是数据与数据之间存在的逻辑关系，用一个二元组来表示
$$
B=(K,R)\K代表数据（结点的有限集合），R是集合K上关系的有限集合
$$
例如：5个人，a，b，c，d，e，a是b的父亲，b是c的父亲，c是d的父亲，d是e的父亲，讨论它们之间的父子关系，可以表达为B=（K，R），其中K={a,b,c,d,e},R={r},r={,,,}.
也可以用图形表示
https://img2024.cnblogs.com/blog/3500431/202408/3500431-20240815231109819-494238001.png
ki∈K,Kj∈K，∈r,ki是kj的前驱，kj是ki的后继。
若某个结点没有前驱，就是开始结点；没有后继结点，就是终端结点；既不是开始也不是终端的为内部结点。
线性结构:一个前驱，一个后继
树型结构：一个前驱，多个后继
图型结构：多个前驱，多个后继
1.1.3数据的存储结构
数据的逻辑结构是独立于计算机的，与在计算机中的存储是无关的，要对数据举行处理惩罚，就必须对数据举行存储，数据的存储结构主要有4种存储方式
（1）顺序存储
通常存储线性结构的数据，使逻辑相邻的结点肯定是物理位置相邻
https://img2024.cnblogs.com/blog/3500431/202408/3500431-20240815231213052-443149251.png
（2）链式存储
给每一个结点附加一个指针段，指的是该结点的后继存储地点，一个结点可以有一个后继，也可以有多个后继，所以可以有一个指针域，也可以有多个指针，逻辑相邻的结点在存储区域中可以不是物理相邻。
https://img2024.cnblogs.com/blog/3500431/202408/3500431-20240815231159451-985346545.png
（3）索引存储
在线性结构中，以开始结点为索引号1，其他结点的索引号依次加1，每个结点都有唯一的索引号，根据索引号确定存储地点。
（4）散列存储
构造一个从集合K到存储区域M的函数h，界说域为K，值域为M，存储地点由h（Ki）决定
一个数据结构存储在计算机中，整个数据所占的存储空间不肯定小于数据本身所占的存储空间，通常把数据本身所占的存储空间和整个数据结构所占的存储空间的大小的比值叫做存储密度，显然，数据结构的存储密度不大于1，线性结构存储密度为1，链式结构小于1。
1.2 数据类型和抽象数据类型
1.2.1数据类型
数据类型（简称类型）反映了数据的取值范围以及这类数据可以施加的运算。一个数据类型就是同一类数据的全体，是数据的一种属性，规定了数据的可变革范围，
1.2.2抽象数据类型
这是一种和表示无关的数据类型，是一个数据模子及界说在该模子的一组运算，界说一个抽象数据类型时，必须给出它的名字及运算符名，及函数名，并规定参数性质。（c++中的类支持抽象数据类型）
简言阐明，就是自界说类型。
1.3算法和算法分析
解决某个题目的方法和步调就叫做算法
特性
（1）有穷性：算法执行要在有限步内举行
（2）确定性：每个步调是确定的，无二义性
（3）输入：可以有0个或多个输入
（4）输出：肯定有输出效果
（5）可行性：每一个步调都是可行的
1.3.1时间复杂度和空间复杂度
一个算法和优劣是从算法的执行时间和所用的存储空间两个方面衡量的。
(1)时间复杂度
由于算法在不同呆板上执行时间不同，资源占用情况也不一样。所以时间复杂度利用算法执行过程中的根本利用次数来衡量的，利用大O渐进表示（O（）），在评价算法的时间复杂度时，只关系算法的本质区别，不考虑细小区别。
常数阶 31 O（1）
线性阶 2*n+17 O（n）
平方阶 n^2+10 O(n^2)
立方阶 2*n^3 O(n^3)
常见的算法时间复杂度
O（1）
页:
[1]