教学视频是清华大学邓俊辉数据结构与算法
浙江大学数据结构 陈越
注意：信通院的计算机基础只有数据结构与算法导论 并非数据结构与算法 注意甄别
在学习前 确保熟练掌握C/C++、Python、Java等某一主流语言使用或学习能力
该笔记以C++为例才不是只学了C++
结合徐雅静老师主编的《数据结构与算法》与邓俊辉老师主编的《数据结构》

前言：
为什么要学习数据结构和算法？
引用runoob的一句话

随着应用程序变得越来越复杂和数据越来越丰富，几百万、几十亿甚至几百亿的数据就会出现，而对这么大对数据进行搜索、插入或者排序等的操作就越来越慢，数据结构就是用来解决这些问题的。

想象一所图书馆，无数的新书（数据）入馆，如何合理摆放（数据存储），同时需要和旧书（旧数据）一起陈列（优化数据结构），读者（计算机、用户）如何更快更方便的查找需要的书籍。老破旧损的书籍怎么处理。将它抽象化，就是数据结构和算法这门课程所教的知识。

但其实我觉得学校排的课有点不太合理，我个人更喜欢先学数据结构再去实践C语言编程。不过按刘老师的意思大概是先去知道这玩意操作起来是什么效果再去理解背后的原理。
whatever，这门课程多又杂，笔记纯属是辅助我个人理解的，如有错误，请务必指出！！谢谢！！

鸽了一阵 今天补一下

零、导论

4节

2.2 静态单链表

1

一、绪论

概念引入

数据是信息的载体，能够被计算机识别、存储和加工处理。分为数值数据与非数值型数据。

数据元素是数据的基本单位。

数据项（字段、域）是构成数据元素的不可分割的最小单位。每个数据元素可以包含多个不同的数据项，每个数据项具有独立的含义。

数据类型是具有相同性质的计算机数据的集合以及在这个数据集合上的一组操作。数据类型可以分为简单类型(或称为原子类型)和构造类型（或称为结构类型）。例如C++中int、float、double等。

数据结构是指按照某种逻辑关系组织起来的一组数据,按一定的存储方式存储在计算机的存储器中，并在这些数据上定义了一组运算的集合。
其中，数据结构包含以下三个方面：

1. 数据元素之间的逻辑关系,也称为数据的逻辑结构。
2. 数据元素及其关系在计算机存储器内的存储形式,称为数据的存储结构或物理结构。
3. 对数据的操作或运算。

解释说明：数据元素存储在数据域中，数据类型是给数据分类，数据结构是阐释数据是如何摆放查找的的。

常见的逻辑结构有4 种，分别是集合、线性结构、树和图。

邓给出这样一个例子：欧几里得的尺规作图将线段三等分

过A作任意射线ρ，在ρ上取一点D，用圆规取AC’=C’D’=D’B’，连接B’B，过D’、C’作BB’的平行线，交AB于点C、D。此时AC=CD=DB。

将该过程描述成算法形式，即：

1
2
3
4
5
6
7
8

tripartition(AB)
输入：线段AB
输出：将AB三等分的两个点C和D
从A发出一条与AB不重合的射线ρ
任取上三点C'、D'和B'，使|AC'| = |C'D'| = |D'B'|
连接B'B
过D'做B'B的平行线，交AB于D
过C'做B'B的平行线，交AB于C

个人理解这个过程为 线段→尺规作图→三等分点。
而尺规作图这个环节就是计算机计算的过程。
作图步骤与规则即为算法。

在此给出算法定义：
算法是指基于特定的计算模型，旨在解决某一信息处理问题而设计的一个指令序列。

其中有穷性是判别程序与算法的重要性质

例：冒泡算法（邓数据结构）

1
2
3
4
5
6
7
8
9
10
11
12
13
14

void bubblesort1A(int A[], int n) { //冒泡排序算法：0 ≤ n
bool sorted = false; //整体排序标志，首先假定尚未排序
    while (!sorted) { //在尚未确定已全局排序之前，逐趟进行扫描交换
    sorted = true; //假定已经排序
        for (int i = 1; i < n; i++) { //自左向右逐对检查当前范围A[0, n)内的各相邻元素
            if (A[i - 1] > A[i]) { //一旦A[i - 1]与A[i]逆序，则
            swap(A[i - 1], A[i]); //交换
            sorted = false; //因整体排序不能保证，需要清除排序标志
            }
        }
    n--; //至此末元素必然就位，故可以缩短待排序序列的有效长度
    }
} //借助布尔型标志位sorted，可及时提前退出，而不致总是蛮力地做n - 1趟扫描交换

最好时间复杂度：T(n)=Ω(g(n))
//增速下界
最坏时间复杂度：T(n)=O(f(n))
//增速上界
平均时间复杂度：T(n)=Σnp
//数学期望

一般来说最坏已经够用了 三种情况无太大差别

复杂度计算；
多种算法同时使用时 复杂度取最大值
即
多种算法嵌套使用时 复杂度计算乘积
即
for循环时间复杂度等于循环次数乘以循环体代码复杂度
即 i*o(f(n))
if-else结构复杂度取决于 判断条件、分支的复杂度的最大值
即

空间复杂度；程序运行时占用内存的大小
S(n)=O(f(n))

一、线性表
定义：由同类型数据元素构成有序序列的线性结构
/一类形似只需要换数或字符的数据按顺序排列的表
例如12x²+1x、-6666x²+457x可以抽象为ax²+bx 这就算同类型了/

线性表有两种储存方式：顺序与链式
顺序表类似于数组 优缺点一致
链式表 可动态分配内存 方便插入删除 查找只能顺序遍历

顺序表用数组实现就行了 重点写一下链式表

链式表的示例

1
2
3
4
5
6

typedef struct Node *NewData  //结构体定义指针 可以用NewData来指向下一个数据元素
struct Node{     //自定义数据类型 看不懂的话再学一下上学期的c++
    int a;          //数据域 设置任意的同类型数据不同的地方
    int b;          //同
    NewData link;   //指针域 指向下一个数据节点
}