数据结构基础概念与术语等

以复习为目的记录复习内容吧…

整理课上的内容

案例导入

线性关系：图书管理系统按照序号排序的书本，每本书还有对应的名字，作者，编号…元素间按序号排序，n号(n不是首也不是尾)前是n-1，后是n+1，呈线性关系

图结构：最短路径问题（随便找了个图，就是得两点间最短距离的问题）

请添加图片描述

树结构：族谱，电脑文件夹…

基本概念

数据：客观的符号表示，是所有能输入到计算机中被计算机程序处理的符号的总称，如文本编辑中的字符串，多媒体处理的图形、声音…

数据元素：数据的基本单位，如图的一个顶点，图书管理系统的一本书的记录

数据项：组成数据元素的，含独立含义的，不可分割的最小单位，如图书管理系统中，书的作者/编号…都是数据项

数据对象：性质相同的数据元素的集合，是数据的子集，如整数集合…

数据结构

数据结构相互间存在一定关系的数据元素的集合

数据结构存在逻辑结构和存储结构两个层次。

逻辑结构：集合/线性/树/图结构（在集合中/一条线连起来的一对一/树状一对多/图状多对多）

请添加图片描述

存储结构：也成物理结构，有顺序存储和链式存储，可理解为地址连续方面，顺序的需要一系列连续的地址事先定义，而链式依靠指针（如每一个数据有下一个数据的地址的指针）可以不需连续，但是有时候的操作会比顺序复杂

关于数据类型和抽象数据类型：数据类型是一个值的集合和定义在这个值集上的一组操作的总成。抽象数据类型是用户用来解决问题的模型及定义其上的操作…

关于抽象数据类型应该还可以补充些啥…

算法分析

算法是解决某问题的，有限长的操作序列

算法的特性

算法具有五个重要特性：有穷性（有穷步，有穷时间），确定性（确切的规则设定使得使用者阅读者可明确含义），可行性（通过基本操作可实现），输入，输出

评判算法的几个标准

正确性，可读性，健壮性(可抵抗非法输入等)，高效性

老师您应该不会考这些点吧…

算法时间复杂度和空间复杂度（划重点）

咳，才不会说是只听了这块…

测定算法效率可以用：事后统计法和事前分析估算法，俩复杂度就是用来事前分析的

时间复杂度

百度扒拉一句：在计算机科学中，时间复杂性，又称时间复杂度，算法的时间复杂度是一个函数，它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，亦即考察输入值大小趋近无穷时的情况。

请添加图片描述

通过计算我们可以获取大多程序的时间复杂度O(n)，然后为啥最后都是一项了呢？因为例如a(n^m)+b(n(m-1))+c+d，我们低次幂，系数，于是O(n)=a(n^m)+b(n(m-1))+c+d=O(n^m)

以下为常见阶与案例案例

常数阶O(1)

与n增长无关的代码

for(i=0;i<10000;i++){x++;s=0;}
1

顺序表查值

printf("%%d",a[1]);
1

线性阶O(n)

for(i=0;i<=n;i++){
	x++;
}
1
2
3

代码x++执行频率是n，复杂度O(n)

平方阶O(n^2)

可以想到线性阶嵌套

for(i=0;i<=n;i++){
	for(j=0;j<=n;j++){
		x++;
	}
}
1
2
3
4
5

立方阶O(n^3)

…嵌套三次即可

for(i=0;i<=n;i++){
	for(j=0;j<=n;j++){
        for(k=0;k<=n;k++){
            x++;
        }
	}
}
1
2
3
4
5
6
7

但是题目在这里就有很有趣的点了，最基本是i<=n,j<=n,k<=n;可以改为j<=i这样，就要用点数学知识了

后来的补充：比如i从1到n，j从1到i，k从1到i的三层嵌套，最后就是三次数列求和就好了（应该可以说是求和吧）

对数阶O(logn)

准确来说是以2为底，n的对数

for(i=1;i<=n;i=2*i){
    x++;
}
1
2
3

这里最开始学觉得计算方法挺有意思的(莫名有意思)

计算如下：

假设执行x次

那么2^x <= n

x<=logn

所以是对数阶

其他

还有k次方阶，指数阶(但那就太复杂了~)

然后还会有最好最坏时间复杂度，平均时间复杂度，看好问题就好计算了

显然待补充

空间复杂度

运算空间相对充足所以重点还是时间复杂度

空间复杂度举例子，我们熟悉C语言数组排序，就逆序而言，如果用到t暂时存放值，呢么这个t使得算法空间复杂度为O(1)

如果用到一个新数组来存放这些逆序后的值，那就是O(n)

…

时间空间难以兼顾，看好问题就好计算了

显然待补充

数据结构基础概念与术语等