一、基础知识
-
数据结构常用术语：
数据结构中最基本的5个概念: 数据,数据元素,数据项,数据对象,数据结构;
数据结构@2x.png
1.1 数据
数据: “是描述客观事物的符号，是计算机中可以操作的对象，是能被计算机识别，并输入给计算机处理的符号集合。数据不仅仅包括整型、实型等数值类型，还包括字符及声音、图像、视频等非数值类型。”
1.2 数据元素
数据元素: 是组成数据的,且有一定意义的基本单位,在计算机中通常作为整体处理.
1.3 数据项
数据项: 一个数据元素可以由若干数据项组成,数据项是数据不可分割的最小单位.
1.4 数据对象
数据对象: 是性质相同的数据元素的集合,是数据的子集.
1.5 数据结构
结构,简单理解就是关系. 比如分子结构,就是说组成分子原子的排列方式. 不同数据元素之间不是独立的,而是存在特定的关系.我们将这些关系成为结构. 那么数据结构是什么? 数据结构是相互之间存在一种或多种特定关系的数据元素的集合.
下面从一个列子来了解一下以上概念：
//声明一个结构体类型
struct Model{ //一种数据结构
char *name; //数据项--名字
int age; //数据项--年龄
};
int main(int argc, const char * argv[]) {
struct Model model; //数据元素;
struct Model array[10]; //数据对象;
model.name = "数据项"; //数据项
model.age = 18; //数据项
return 0;
}
- 数据结构的不同表示
根据视角不同,我们将数据结构分为2种: 逻辑结构与物理结构;
2.1 逻辑结构
指的是数据对象中的数据元素之间的相互关系. 逻辑结构分为四种: 集合结构,线性结构,树形结构,图形结构.
2.1.1 集合结构
集合结构中的数据元素除了同属于一个集合外,它们之间没有其他关系.
2.1.2 线性结构
线性结构: 线性结构中的数据元素之间是一对一的关系.
2.1.3 树形结构
树形结构: 重要的非线性数据结构。树形数据结构可以表示数据表素之间一对多的关系.常见的树形结构: 二叉树,B树,哈夫曼树,红黑树等.
2.1.4 图形结构
图形结构: 图形结构的数据元素是多对多的关系. 常见的图形结构: 邻近矩阵,邻接表.
2.2 物理结构
别称"存储结构". 指的是数据的逻辑结构在计算机的存储形式.数据的存储方式分两种：顺序存储和链式存储。
2.2.1 顺序存储结构
顺序存储结构: 是指把数据元素存放在地址连续的存储单元里,其数据间的逻辑关系和物理关系是一致的.
2.2.2 链式存储结构
链式存储结构：是把数据元素放在任意的存储单元里,这组存储单元可以是连续的,也可以是不连续的. 数据元素的存储关系并不能反映逻辑关系,因此需要用一个指针存放数据元素的地址,这样通过地址就可以找到相关关联数据元素的位置.
二、算法
定义：算法就是解决特定问题求解步骤的描述,在计算机中表现为指令的有限序列列, 并且每个指令表示⼀一个或多个操作.
算法特性
- 输⼊入输出:算法可以具有零个或多个输入, 但是算法至少有一个或多个输出
- 有穷性:算法在执行有限的步骤之后,自动结束而不会出现无限循环,且每一个步骤在可接受的时间内完成.
- 确定性:算法的每一个步骤都具有确定的含义,算法在一定条件下,只有一条执行路径,相同的输入只能有唯一的输出结果.
- 可⾏性:算法的每一步都必须是可行的.
3.算法设计要求
- 正确性
- 可读性
- 健壮性
- 时间效率⾼高和储存量量低
-
时间复杂度
时间复杂度@2x.png
4.1 时间复杂度使用大O表示法，大O表示法有以下准则
- 用常数1取代运行时间中所有常数 3->1 O(1)
- 在修改运行次数函数中,只保留最高阶项 n3+2n2+5 -> O(n^3)
- 如果在最高阶存在且不等于1,则去除这个项目相乘的常数 2n^3 -> n^3
4.2 时间复杂度术语
4.2.1 常数阶
/* 1. 常数阶时间复杂度计算 O(1)
2. 每次运行执行的次数固定
*/
//1+1+1 = 3 O(1)
void testSum1(int n){
int sum = 0; //执行1次
sum = (1+n)*n/2; //执行1次
printf("testSum1:%d\n",sum);//执行1次
}
4.2.2 线性阶
//x=x+1; 执行n次 O(n)
//执行次数和参数n成线性关系
void add2(int x,int n){
for (int i = 0; i < n; i++) {
x = x+1;
}
}
4.2.3 对数阶
/*2的x次方等于n x = log2n ->O(logn)
执行的次数和n的对数有关
*/
void testA(int n){
int count = 1; //执行1次
//n = 10
while (count < n) {
count = count * 2;
}
}
4.2.4 平方阶
//执行次数与参数n的平方相关
//n+(n-1)+(n-2)+...+1 = n(n-1)/2 = n^2/2 + n/2 = O(n^2)
void add3(int x,int n){
for (int i = 0; i< n; i++) {
for (int j = 0; j < n ; j++) {
x=x+1;
}
}
}
//1+(n+1)+n(n+1)+n^2+n^2 = 2+3n^2+2n -> O(n^2)
void testSum5(int n){
int i,j,x=0,sum = 0; //执行1次
for (i = 1; i <= n; i++) { //执行n+1次
for (j = 1; j <= n; j++) { //执行n(n+1)
x++; //执行n*n次
sum = sum + x; //执行n*n次
}
}
printf("testSum5:%d\n",sum);
}
4.2.5 立方阶
//执行次数与参数n的平方相关
//1+n+n*n+n*n*n+n*n*n -> O(n^3)
void testB(int n){
int sum = 1; //执行1次
for (int i = 0; i < n; i++) { //执行n次
for (int j = 0 ; j < n; j++) { //执行n*n次
for (int k = 0; k < n; k++) {//执行n*n*n次
sum = sum * 2; //执行n*n*n次
}
}
}
}
- 空间复杂度
算法的空间复杂度指的并不是整个算法在内存占用空间,而是指的是该算法在实现时所需要的辅助空间就可以.
int n = 5;
int a[10] = {1,2,3,4,5,6,7,8,9,10};
//算法实现(1)
//使用1个中间变量 复杂度为O(1)
int temp;
for(int i = 0; i < n/2 ; i++){
temp = a[i];
a[i] = a[n-i-1];
a[n-i-1] = temp;
}
for(int i = 0;i < 10;i++)
{
printf("%d\n",a[i]);
}
//算法实现(2)
//中间使用了n个中间变量，为O(n)
int b[10] = {0};
for(int i = 0; i < n;i++){
b[i] = a[n-i-1];
}
for(int i = 0; i < n; i++){
a[i] = b[i];
}
for(int i = 0;i < 10;i++)
{
printf("%d\n",a[i]);
}
以上是对数据结构一些基本概念的总结，如有错误，烦请指正！
