基础篇

2020-09-16 本文已影响0人 AlexChou

1.基础

1.1 数据结构基本术语

数据程序的操作对象，用于描述客观事物
· 可以输入到计算机
· 可以被计算机处理
数据对象：是性质相同的数据元素的集合，是数据的子集。如数组、集合等。
数据元素：组成数据的对象的基本单位。例如，结构体、类等。
数据项：一个数据元素由若干数据项组成。

//声明一个结构体类型
struct Teacher {     //一种数据结构
    char *name;     //数据项--名字
    char *title;    //数据项--职称
    int  age;       //数据项--年龄
};

struct Teacher t1;     //数据元素;
struct Teacher tArray[10]; //数据对象;

结构：数据元素之间不是独立的，存在特定的关系。这些关系即是结构。
数据结构：指的数据对象中的数据元素之间的关系。

1.2 逻辑结构与物理结构

根据逻辑和存储关系，我们将数据结构分为2种：逻辑结构与物理结构。

1.2.1 逻辑结构

逻辑结构：是数据对象中的数据元素之间的相互关系。逻辑结构分为四种：

集合结构
集合结构中的数据元素除了同属于一个集合外，它们之间没有其他关系。各个数据元素是"平等"的。
线性结构
线性结构中的数据元素之间是一对一的关系。
常用的线性结构有：线性表、栈、队列、双队列、数组、串。
树形结构
树型结构中的数据元素之间存在一种一对多的层次关系。
常见的树形结构：二叉树、B树、哈夫曼树、红黑树等。
图形结构
图形结构的数据元素是多对多的关系。
常见的图形结构：邻近矩阵、邻接表。

具体采用什么的数据结构，是需要根据实际业务需求来进行合理的设计。

1.2.2 物理结构

物理结构：又称“存储结构”，指的是数据的逻辑结构在计算机的存储形式。

数据存储结构应该正确反映数据元素之间的逻辑关系。如何存储数据元素之间的逻辑关系，是实现物理结构的重点和难点。

数据元素的存储结构形式有2种：

顺序存储：把数据元素放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的。
链式存储：把数据元素放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的。
数据元素的存储关系并不能直接反映逻辑关系，因此需要用一个指针存放数据元素的地址，通过地址找到相关关联数据元素的位置。

2. 算法基础

算法：解决特定问题求解步骤的描述。在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。

算法与数据结构的关系：数据结构如果脱离算法，或者算法脱离数据结构都是无法进行的。

算法的特性：

输入输出：输入提供已知条件，输出产生结果。
有穷性：执行有限的步骤之后，会自动结束。不会死循环。
确定性：相同输入执行后，只有对应唯一的结果，不能有二义性。
可行性：每一步都是可行的。每一步都能通过有限次数完成。

算法设计要求：

正确性：能够得到正确答案。错误答案对于解决问题是没有意义的。
- 没有语法错误。
- 对于非法的输入数据能够正确报错。
- 对于所有合法输入数据都应有正确的输出结果，包括边界情况等。
健壮性：能对输入数据的不合法的情况做出合适的处理。
时间效率高和存储量低：花最少的时间，用最少的存储空间，得到相同的结果。

2.1 复杂度

2.1.1 时间复杂度

时间复杂度：算法的时间复杂度是一个函数，它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，亦即考察输入值大小趋近无穷时的情况。
在考虑复杂度时，想象n 趋近无穷大的情况，只保留n的最高阶，并移除常数项。

执行次数	函数接	术语
$12$	$O(1)$	常数阶
$2n+3$	$O(n)$	线性阶
$3n^2+5n+4$	$O(n^2)$	平方阶
$6n^3+3n^2+5n+1$	$O(n^3)$	立方阶
$2n+3nlog_2n+13$	$O(nlogn)$	nlog阶
$2^n$	$O(2^n)$	指数阶

$O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)$

对于算法的分析：

平均时间复杂度：计算所有情况的平均值。
最坏时间复杂度：计算最坏的情况下时间复杂度。
注意：一般没有特殊情况下，都是指最坏时间复杂度。

2.2 空间复杂度

空间复杂度：通过计算算法所需的存储空间实现，算法空间复杂度的计算公式记做： $S(n)=n(f(n))$ .
其中 $n$ 为问题的规模， $f(n)$ 为关于 $n$ 所占存储空间的函数。

除了需要寄存本身所用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的辅助存储空间。
考量空间复杂度是，主要考虑算法执行时所需要的辅助空间。

举例：数组逆序，将一维数组a中的n个数逆序存放在原数组中。

int n = 5;
int a[10] = {1,2,3,4,5,6,7,8,9,10};
/*
算法(1)，仅仅通过借助一个临时变量temp，与问题规模n大小无关。
空间复杂度为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的辅助数组b。
空间复杂度为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]);

基础篇