WHCSRL 技术网

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

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

整理课上的内容

案例导入

线性关系:图书管理系统按照序号排序的书本,每本书还有对应的名字,作者,编号…元素间按序号排序,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)

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

显然待补充