链表

双链表

双链表的定义

由于在单链表的使用中，对于某些操作需要取到元素的前驱，实现这个功能对于单链表来说非常麻烦，可能需要遍历整个表

因此，为了解决这个问题，双链表应运而生

双链表的结构为：数据域和前驱指针和后继指针

链表结构如下：

typedef struct DNode { 
    int data;
    struct DNode *prior, *next;
} DNode, *DLinkList; // 这里和之前一样，都 Node 是为了强调节点，DLinkList 是为了强调双链表，是链表的指针

队列的定义

队列（Queue）是一种特殊的线性表，特殊之处在于它只允许在表的前端(front)进行删除操作，而在表的后端(rear)进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。

队列的特点是先进先出（FIFO），即先存入队列的数据，要先取出。

队列的基本操作

需要实现的基本功能有这些：

栈的定义

栈（Stack）是一种特殊的线性表，仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

没有元素时称为空栈。栈的特点是：先进后出，或者说是后进先出（LIFO），从栈顶放入元素的操作叫进栈，取出元素叫出栈。

关于指针

typedef 的使用

// 我们可以定义某种类型的别名，称之为类型定义(typedef)，也可以对某种类型的指针进行定义
// 定义后，在之后的使用中就可以直接使用其别名

int p = 1;
int *i = &p;

// 使用typedef定义后

typedef int newP;
typedef int *newPp;

newP p = 1;
newPp i = &p;

线性表的定义

线性表是具有相同数据类型的 n 个数据元素的有限序列，其中 n 为表长，当 n=0 时，称为空表，若用 L 表示线性表，则其一般表示为 $L = (a_1, a_2, \cdots , a_i, a_{i+1}, \cdots , a_n)$

算法的基本概念

程序 = 数据结构 + 算法

数据结构解决如何正确地描述现实世界的问题，并存入计算机

算法则关注如何高效的处理这些数据以解决实际问题（求解问题的步骤）

算法的定义

算法是对特定问题求解步骤的一种描述，他是指令的有限序列，其中的每条指令表示一个或多个操作

算法的特性

有穷性

一个算法必须总在执行有穷步之后结束，且每一步都可在有穷时间内完成

算法必须有穷，程序可以是无穷的

数据结构和数据对象的区别

在于，数据结构不仅包含各个数据元素，还包含数据元素之间的关系，而数据对象仅包含所有数据元素，是一个集合

数据结构的三要素

逻辑结构

集合 （基本不讨论）

各个数据元素同属一个集合，元素间没有任何关系

线性结构

数据元素之间是一对一关系，除第一个元素之外，每个元素都有唯一一个前驱；除最后一个元素之外，每个元素都有唯一一个后继

树形结构

树形元素间是一对多关系