前端之家收集整理的这篇文章主要介绍了
【数据结构】基本概念,
前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。
【1】数据结构的概念
数据和数据之间的关系,本质上说主要研究的是关系
【2】数据(Data)
数据即信息的载体,是能够输入到计算机中并且能被计算机识别、存储和处理的符号总称。
一般数据可以理解为研究对
【3】数据元素(Data Element)
数据元素是数据的基本单位,又称之为记录(Record)。
【4】数据项
数据元素由若干基本项(或称字段、域、属性)组成,称之为数据项,数据项是数据的最小单位
【5】数据类型(Data Type)
数据类型是对数据元素取值范围与运算的限定。
为了实现代码的多用性,在写在写代码之前最好重定义数据类型
【6】数据结构指的是数据的逻辑结构和存储结构及其操作
逻辑结构
表示数据运算之间的抽象关系(如邻接关系、从属关系等),按每个元素可能具有的直接
前趋数和直接后继数将逻辑结构分为“线性结构”和“非线性结构”两大类。
线性关系:数据和数据之间是一对一的关系,如线性表、栈、队列
满足线性关系的数据,每一个数据只有一个前驱和后继,并且首元素没有前驱,尾元素没有后继
树形关系(层次关系):一个对多个,如树
图形关系(网状关系):多个对多个,如图
存储结构
逻辑结构在计算机中的具体实现方法,分为顺序存储方法、链接存储方法、索引存储方法、散列存储方法。
顺序存储
将数据存储在一块连续的内存空间当中,使用malloc在内存开辟空间,使用数组开辟连续的空间,为了
操作方便,引入数组下标指向每一个数据的位置
链式存储
不需要在内存当中开辟一块连续的空间,使用指针将数据联系起来,每一个数据称之为一个结点,由数
据域和指针域构成,指针指向下一个结点
数据运算
对数据进行的操作,增、删、改、查
【7】算法的定义
算法(Algorithm)是一个有穷规则(或语句、指令)的有序集合。
算法就是函数实现的过程
【8】算法的特性
(1)有穷性 —— 算法执行的步骤(或规则)是有限的;
(2)确定性 —— 每个计算步骤无二义性;
(3)可行性 —— 每个计算步骤能够在有限的时间内完成;
(4)输入 —— 算法有一个或多个外部输入;
(5)输出 —— 算法有一个或多个输出。
【9】数据结构 + 算法 = 程序
【10】语句的频度(Frequency Count)
语句频度定义为可执行语句在算法(或程序)中重复执行的次数。
代码执行的次数
【11】算法的时间复杂度(Time Complexity)
算法的时间复杂度定义为算法中可执行语句的频度之和,
void MATRIXM(A,B,C)
{
float A[n][n],B[n][n],C[n][n];
{
int i,j,k;
for (i=0; i<n; i++)
for (j=0; j<n; j++)
{
C[i][j] = 0;
for (k=0; k<n; k++)
C[i][j] = C[i][j]+A[i][k] * B[k][j];
}
}
}
T(n)=(n+1)+n(n+1)+n~2+n~2(n+1)+n~3=2n~3+3n~2+2n+1
T(n) = O(n~3)