数据结构基础-基本概念

这篇文章主要目的从基础开始说起，也算是本人的一个总结吧。如果当中有理解不到位的，欢迎大家随时批评。

主要有以下几个点：
 数据结构定义
 数据定义
 数据的构成
 数据结构分类
 逻辑结构
 存储结构
算法
 算法定义
 算法特性
 算法设计要求
 算法时间复杂度
 常见时间复杂度
 算法空间复杂度

数据结构

1.数据结构的定义
抽象来说，是计算机存储、组织数据的方式。大白话的理解是由数据元素的集合和集合中数据元素之间的关系组成的。

构成的集合，数据元素相互之间可以是一种关系，也可以是多种关系。

2.数据
是指对客观事物描述的符号。在计算机中，数据是指能输入到计算机并被计算机程序处理的符号的介质的总称，比如数字、字母等。

是由若干个性质相同数据元素构成的，若干个数据对象就会构成一个数据

是计算机科学术语，数数据的基本单位。数据元素也叫做记录或节点，它由若干个数据项组成。

是数据不可分割的最小单位

他们之间的关系如图：

image

举个例子，在图书馆里，所有的图书信息就是数据，图书信息就是数据对象，每一本图书就是数据元素，图书里面的书名、章节等就是数据项

3.数据结构分类
反应的是数据元素之间的关系。
：结构中的数据元素之间除了"同属于一个集合"关系外，别无其他关系

image

：结构中的数据元素之间存在一个对一个的关系

image

：结构中的数据元素之间存在一个对多个的关系

image

：结构中的数据元素之间存在多个对多个的关系

image

是数据在计算机中的存储形式，也可叫存储结构。它分为顺序存储、链式存储。
：在内存中找到一块空间，通过占位的方式，把一定内存空间给占了，然后把相同数据类型的数据元素依次存放在这块空间中。

image

：用一组任意的存储单元存储数据元素(这组存储单元可以是连续的,也可以是不连续的)

image

算法
1.算法定义
什么是算法? 算法就是解决特定问题求解步骤的描述,在计算机中表现为指令的有限序列, 并且每个指令表示一个或多个操作

2.算法特性
输入输入
有穷行
确定性
可行性

3.算法设计要求
正确性、可读性、健壮性、时间效率高和存储量低

4.时间复杂度
时间复杂度是描述算法的运行时间，常用大O符号表述。我们通常说的时间复杂度，是指在最坏的情况下的运行时间。如果要比较两个算法的好坏，使用平均时间复杂度。

大O表示法一般规则：
1）用常数1取代运行时间中所有常数 3->1 O(1)
2） 在修改运行次数函数中,只保留最高阶项 n³⁺²ⁿ2+5 -> O(n^3)
3.）如果在最高阶存在且不等于1,则去除与它相乘的常数 2n^3 -> n^3

常见的时间复杂度

image

注意：指数阶(不考虑) O(2^n)或者O(n!) 除非是非常小的n,否则会造成噩梦般的时间消耗. 这是一种不切实际的算法时间复杂度. 一般不考虑!

举例说明

//1+1+1 = 3 O(1) 常数阶
voidtestSum1(int n){
   intsum =0;               //执行1次
    sum = (1+n)*n/2;           //执行1次
   printf("testSum1:%d\n",sum);//执行1次
}

//x=x+1执行n次 O(n) 线性阶
voidadd2(int x,int n){
   for(inti =0; i < n; i++) {
        x = x+1;
    }
}

//2的x次方等于n x = log2n  ->O(logn) 对数阶
voidtestA(int n){
   intcount =1;        //执行1次
   //n = 10
   while(count < n) {
        count = count *2;
    }
}

//x=x+1执行n*n次 ->O(n^2) 平方阶
voidadd3(int x,int n){
   for(inti =0; i< n; i++) {
       for(intj =0; j < n ; j++) {
            x=x+1;
        }
    }
}

//立方阶
voidtestB(int n){
   intsum =1;                        //执行1次
   for(inti =0; i < n; i++) {       //执行n次
       for(intj =0; j < n; j++) {  //执行n*n次
           for(intk =0; k < n; k++) {//执行n*n*n次
                sum = sum *2;         //执行n*n*n次
            }
        }
    }
}

5.空间复杂度
空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。
注意：在考量算法的空间复杂度,主要考虑算法执行时所需要的辅助空间。