1.线性表

线性表"/>

1.线性表

主要考查知识点

1、线性表，

2、树和二叉树

3、图

4、排序算法

6、hash

6、查找算法

基本数据结构

线性表

按存储结构分类分为两类，顺序表以及链表

顺序表在内存中按顺序存储

链表是离散的，单独的一个个点，即物理上是离散的，但是逻辑上是一个整体

链表的类别：

单链表:单向的，有两个域，前面的叫数据域，后面的叫指针域，存放的是指针，用于指向另一个节点，即下一个结点的地址，最后一个指针域为空，即表示后面没有后继结点

循环链表：与单链表相似，但是最后一个的下一个结点是头结点，这样就构成了一个循环

双链表：即不只一个指针，有两个指针域，前后各一个，从两个不同方向将链表连接起来，这样就构成了双向链表

双链表的灵活性会大于单链表，但是开支会更多，因为有两个指针域

链表的操作

单链表的删除：将要删除的结点的前驱结点next域指向它的后继结点，并释放该结点

单链表的结点插入，将要插入位置新建一个结点，将该节点指向要插入位置的下一结点，并将其前驱结点指向该结点

双链表的结点删除

双链表的结点插入

顺序表与链表的比较：

顺序表与链表的比较

栈：

并非实际存在，先进后出

队列：先进先出

循环队列会形成一个环，每进入一个元素后，堆头指针不动，队尾指针向后移一位，当head=tail值队列可能为空或可能为满

解决方法：牺牲队列的最后一个空间不用来存数据，当尾指针指向最后一个空间时即队满，tail+1=head队满

mod运算是求余

做队列之类的题的时候画一个图再进行解答