初识数据结构与算法篇

前言

数据结构是程序设计的重要基础。数据结构：是指元素的集合与元素之间的相互关系和构造方法。元素之间的相互关系是数据的逻辑节后，数据元素以及元素之间关系的存储称为存储结构或者物理结构。数据结构存储⽅式总的来说就两种数组:（顺序存储）和链表（链式存储）,也可以称为线性结构与非线性结构。，
散列表、栈、队列、堆、树、图等等各种数据结构都是基于数据和链表实现的。

1.线性结构

线性结构是一种基本的数据结构，主要描述客观世界中具有单一前驱和后继的数据关系，特点是描述元素之间的线性关系，一个元素接着一个元素。

1.1 线性表

线性表：一个线性表是n(n>=0)个元素的有限序列，通常表示(a1,a2…an)。非空线性表的特点：
1.存在第一个元素
2.存在最后一个元素
3.除了第一个元素外，序列中的每个元素均只有一个前驱。
4.除了最后一个元素，序列中的每个元素均只有一个直接后继。

1.2 线性表的顺序存储

线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的元素，逻辑上相邻的的两个元素位置相邻。两个元素之间的关系不需要额外的空间来存储。

a1
a2
…
an-1
an

1.3 线性表优缺点：

优点：1.查找元素比较快，节省存储空间
缺点：1.插入与更新元素较慢。

1.4 线性表的链式存储

线性表的链式存储是通过指针链接起来节点来存储数据元素。基本的结构：

数据域	指针域

数据域用于存储数据元素的值，指针域存储当前元素的直接前驱或直接后继的位置信息，指针域的信息称为指针(或者域)。

单链表的定义：

typedef struct node{
  int data; //节点的数据域，定义数据的类型
  struct node *next ;//指针域
}node,*LinkList;

双向链表

typedef struct node{
  int data; //节点的数据域，定义数据的类型
  struct node *next,*pre ;//指针域
}node,* DoubleLinkList;

1.5 线性表的链式存储的优缺点

优点：插入和更新与删除元素比较快
缺点：查询比较慢，需要额外的空间来存储节点之间的关系。

2.栈和队列

2.1 栈

栈是只能通过它的一端来实现数据存储和检索的一种线性数据结构，栈的修改是先进后出的原则。
栈的基本运算
1.初始化栈:创建一个空栈S
2.判栈空：栈为空返回true,否则返回false.
3.入栈Push,将元素加入栈顶，并更新栈顶的指针。
4.出栈Pop,将元素从栈顶中删除，并更新栈顶指针。
5.读取栈顶元素：返回栈顶的元素的值。

2.2 队列

队列是一种先进先出 (FirstIn FirstOut，FIFO)的线性表，它只允许在表的一端插入元素,而在表的另一端删除元素。在队列中,允许插入元素的一端称为队尾(Rear)，允许删除元素的一端称为队头 (Front)。
队列的基本运算。
1.初始化队列InitQueue(Q): 创建一个空的队列Q。
2.判队空isEmpty(Q):当队列为空时返回“真”，否则返回“假”
3.入队 EnQueue(Q,x): 将元素x 加入到队列Q 的队尾，并更新队尾指针。
4.出队 DelQueue(Q): 将队头元素从队列Q 中删除，并更新队头指针。
5.读队头元素 FrontQue(Q): 返回队头元素的值，但不更新队头指针