1.数据类型

数据类型：是指一组性质相同的集合以及定义在此集合的一些操作的总称。

数据类型在C语言中可以分为2类：

  ·原子类型：是不可以在分解的基本数据类型，包含整型、浮点型、字符型等。

  ·结构类型: 由若⼲类型组合⽽成,是可以再分解的。

2.数据结构

基本数据单位

数据结构是带有结构特性的数据元素的集合，它研究的是数据的逻辑结构和数据的物理结构以及它们之间的相互关系，并对这种结构定义相适应的运算，设计出相应的算法，并确保经过这些运算以后所得到的新结构仍保持原来的结构类型。简而言之，数据结构是相互之间存在一种或多种特定关系的数据元素的集合，即带“结构”的数据元素的集合。“结构”就是指数据元素之间存在的关系，分为逻辑结构和存储结构。

数据结构

2.1逻辑结构

指反映数据元素之间的逻辑关系的数据结构，其中的逻辑关系是指数据元素之间的前后间关系，而与他们在计算机中的存储位置无关。

逻辑结构能简单的分为“线性结构”和“非线性结构”

2.2物理结构

指数据的逻辑结构在计算机存储空间的存放形式。

数据的物理结构是数据结构在计算机中的表示（又称映像），它包括数据元素的机内表示和关系的机内表示。由于具体实现的方法有顺序、链接、索引、散列等多种，所以，一种数据结构可表示成一种或多种存储结构。

3.算法

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

3.1数据结构与算法的关系

数据结构与算法的关系

3.2算法的特性

3.2.1输入输出

一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件。

一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的。

3.2.2有穷性

算法的有穷性是指算法必须能在执行有限个步骤之后终止。

3.2.3确定性

算法的每一步骤必须有确切的定义。

3.2.4可行性

算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步骤，即每个计算步骤都可以在有限时间内完成（也称之为有效性）。

3.3算法设计的要求

3.3.1正确性

算法的正确性是评价一个算法优劣的最重要的标准。

3.3.2可读性

算法的可读性是指一个算法可供人们阅读的容易程度。

3.3.3健壮性

健壮性是指一个算法对不合理数据输入的反应能力和处理能力，也称为容错性。

3.3.4时间效率高和储存量低

时间效率指的是算法的执行时间，对于同一个问题，如果有多个算法能够解决，执行时间短的算法效率高，执行时间长的效率低。

存储量需求指的是算法在执行过程中需要的最大存储空间，主要指算法程序运行时所占用的内存或外部硬盘存储空间。

3.4时间复杂度

时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，亦即考察输入值大小趋近无穷时的情况。

常见的时间复杂度

O(1) < O(log n) < O(n) < O(nlog n) < O(n2) < O(n3) < O(2n) < O(n!) < O(nn)

3.4空间复杂度

算法的空间复杂度通过计算算法所需的存储空间实现,算法空间复杂度的计算公式

记做: S(n) = n(f(n)),其中,n为问题的规模,f(n)为语句关于n所占存储空间的函数。

4.线性表

对于⾮空的线性表和线性结构,其特点如下：

• 存在唯⼀的⼀个被称作”第⼀个”的数据元素。

• 存在唯⼀的⼀个被称作”最后⼀个"的数据元素。

• 除了第⼀个之外，结构中的每个数据元素均有⼀个前驱。

• 除了最后⼀个之外，结构中的每个数据元素都有⼀个后继。

4.1单链表节点

单链表节点

4.2单链表逻辑状态

单链表逻辑状态 增加头节点的单链表逻辑状态

增加头节点便于首元节点处理，便于空表和非空表的统一处理。

4.3单链表的插入

假设要在单链表的两个数据元素A和B之间插⼊⼀个数据元素X，已知P为其单链表存储结构中指向结点A指针。如下图所示：

单链表的插入

4.4单链表的删除

要删除单链表中指定位置的元素,同插⼊元素⼀样; ⾸先应该找到该位置的前驱结点; 如下图所示

在单链表中删除元素B时,应该⾸先找到其前驱结点A. 为了在单链表中实现元素A，B，C之间的逻辑关系的变化,仅需修改结点A中的指针域即可。

假设P为指向结点A的指针

单链表的删除

4.5单链表的前插法

单链表的前插法

4.6单链表的后插法

单链表后插法