数据结构基础概念与术语等
以复习为目的记录复习内容吧…
整理课上的内容
案例导入
线性关系：图书管理系统按照序号排序的书本，每本书还有对应的名字，作者，编号…元素间按序号排序，n号(n不是首也不是尾)前是n-1，后是n+1，呈线性关系
图结构：最短路径问题（随便找了个图，就是得两点间最短距离的问题）
树结构：族谱，电脑文件夹…
基本概念
数据：客观的符号表示，是所有能输入到计算机中被计算机程序处理的符号的总称，如文本编辑中的字符串，多媒体处理的图形、声音…
数据元素：数据的基本单位，如图的一个顶点，图书管理系统的一本书的记录
数据项：组成数据元素的，含独立含义的，不可分割的最小单位，如图书管理系统中，书的作者/编号…都是数据项
数据对象：性质相同的数据元素的集合，是数据的子集，如整数集合…
数据结构
数据结构相互间存在一定关系的数据元素的集合
数据结构存在逻辑结构和存储结构两个层次。
逻辑结构：集合/线性/树/图结构（在集合中/一条线连起来的一对一/树状一对多/图状多对多）
存储结构：也成物理结构，有顺序存储和链式存储，可理解为地址连续方面，顺序的需要一系列连续的地址事先定义，而链式依靠指针（如每一个数据有下一个数据的地址的指针）可以不需连续，但是有时候的操作会比顺序复杂
关于数据类型和抽象数据类型：数据类型是一个值的集合和定义在这个值集上的一组操作的总成。抽象数据类型是用户用来解决问题的模型及定义其上的操作…
关于抽象数据类型应该还可以补充些啥…
算法分析
算法是解决某问题的，有限长的操作序列
算法的特性
算法具有五个重要特性：有穷性（有穷步，有穷时间），确定性（确切的规则设定使得使用者阅读者可明确含义），可行性（通过基本操作可实现），输入，输出
评判算法的几个标准
正确性，可读性，健壮性(可抵抗非法输入等)，高效性
老师您应该不会考这些点吧…
算法时间复杂度和空间复杂度（划重点）
咳，才不会说是只听了这块…
测定算法效率可以用：事后统计法和事前分析估算法，俩复杂度就是用来事前分析的
时间复杂度
百度扒拉一句：在计算机科学中，时间复杂性，又称时间复杂度，算法的时间复杂度是一个函数，它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，亦即考察输入值大小趋近无穷时的情况。
通过计算我们可以获取大多程序的时间复杂度O(n)，然后为啥最后都是一项了呢？因为例如a(nm)+b(n(m-1))+c+d，我们低次幂，系数，于是O(n)=a(nm)+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)
…
时间空间难以兼顾，看好问题就好计算了
显然待补充