线性表

PS：笔试中用链表方式去实现，机试中用静态链表的方式去实现，不然会TLE（new的时候太慢）。日期问题在题解中。

1.定义：

将具有线性关系的数据存储到计算机中所使用的存储结构称为线性表。

2. 前驱和后继

对于线性表中的数据来说，位于当前数据之前的数据统称为“前趋元素”，前边紧挨着的数据称为“直接前趋”；
同样，后边的数据统称为“后继元素”，后边紧挨着的数据称为“直接后继”。

3. 线性表的分类

1.  数据元素在内存中集中存储，采用顺序表示结构，简称“顺序存储”；
    例如：数组
2.  数据元素在内存中分散存储，采用链式表示结构，简称“链式存储”。
    例如：单链表、双链表、循环单（双）链表

4. 不同实现方式的时间复杂度（不要硬背结论、要从实现方式入手分情况讨论，下述为特定情况下的时间复杂度）

1. 数组：随机索引O(1)、插入O(n)、删除O(n)
（插入和删除分析的是最坏的情况下时间复杂度）

2. 单链表：查找某一元素O(n)、插入O(1)、删除O(n)
   对于删除的情况（注意甄别）：
    a. 如果是删除当前点，最坏情况就是O(n)，因为需要查找到当前点，才能进行删除。
    b. 如果是删除当前点的下一个点，那就是0（1），因为当前点已知，那么只需要一次遍历就可知下一个点的
       位置从而进行删除。


3. 双链表：查找某一元素O(n)、插入O(1)、删除O(1)
   相比较单链表而言，可以O(1)时间删除

总结：凡是需要遍历的都是O(n)的时间复杂度，不需要遍历的就是O(1)的时间复杂度。

5.考题：

2016-1、2016-2、2012-42、2015-41、2019-41
真题部分讲解部分由于时间原因来不及，不写了。见谅
PS：综合题链表题一般需要给出结点定义。

1. 2012-42 两个链表的第一个公共结点
2. 2015-41 筛选链表
3. 2019-41 重拍链表

6. 押题：

1. AcWing 34
2. AcWing 1451

7.代码实现：

链表的创建，插入结点、删除结点。
（建议不要死记硬背，理解记忆，以下提供参考）

7.1单链表

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

//单链表:结构体定义
struct Node {
    int val ; //数值域
    Node* next; //存放下一个结点的地址

    //下面定义两个构造函数，便于写代码。与单链表的定义无关，可忽略
    Node(): next(NULL) {}  //空构造函数，初始化一下next即可 
    Node(int val): val(val) , next(NULL)  {}  //初始化，为结点赋值
};

//输出链表
void print(Node* head){
    /*循坏遍历，用p指针从头开始遍历，p不空的时候，不断指向下一个结点，
    每到一个结点就输出当前点的val值
    */
    for(auto p = head ; p ; p = p->next)
        cout << p->val << ' ';
    cout << endl;
}



int main(){
    //head指针指向第一个结点的地址，他不是一个结点。初始链表为空，所以head指向null
    //Node* head = NULL; 

    //创造一个长度为1的链表, 同时head指针指向开头（1）
    Node* head =  new Node(1);

    /*1
    尾插法：每次在链表的最后面插入
    新建一个2的结点，插在1的后面。定义一个新结点的时候，因为构造函数使next为null，
    所以不需要再操作。
    */
    auto a = new Node(2); 
    head->next = a;

    //1->2
    //类似的新建一个3，插在最后面
    auto b = new Node(3);
    a->next = b;

    /*1->2->3
    头插法：
    每次在head指针的后面插入。注意指针修改的顺序，不然可能会造成断链。建议写的时候
    画个图再去操作。
    */
    auto c = new Node(4);
    c->next = head->next; //这样写，和下面是不能交换的
    head->next = c;

    /*这样子写就可以交换，具体情况具体分析
    c->next = a;
    head->next = c;
    */

    /*1->4->2->3
    删除结点2
    */
    c->next = a->next;
    delete(a);

    /*1->4->3
    删除头结点：先用一个指针存下head，在改变head指向*/
    auto p = head;
    head = head->next;
    delete(p);

    //4->3
    print(head);  //输出链表

    return 0;
}

7.2双链表

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

//双链表:结构体定义，比单链表多一个向前指的指针
struct Node {
    int val ; //数值域
    Node* prev; //存放上一个结点的地址
    Node* next; //存放下一个结点的地址

    //下面定义两个构造函数，便于写代码。与单链表的定义无关，可忽略
    Node(): prev(NULL) , next(NULL) {}  //空构造函数，初始化prev , next即可 
    Node(int val): val(val) , prev(NULL) , next(NULL)  {}  //初始化，为结点赋值
};

//输出链表
void print(Node* head){
    /*循坏遍历，用p指针从头开始遍历，p不空的时候，不断指向下一个结点，
    每到一个结点就输出当前点的val值
    */
    for(auto p = head ; p ; p = p->next)
        cout << p->val << ' ';
    cout << endl;
}



int main(){
    //head指针指向第一个结点的地址，他不是一个结点。初始链表为空，所以head指向null
    //Node* head = NULL; 

    //创造一个双链表, 同时head指针指向开头，tail指向末尾。
    Node* head =  new Node() , *tail = new Node();
    head->next = tail , tail->prev = head;  //初始化前后指针指向

    cout<<"初始情况：" ;
    print(head); //初始情况：0->0

    /*0->1->0
    头插法：
    每次在head指针的后面插入。注意指针修改的顺序，不然可能会造成断链。建议写的时候
    画个图再去操作。
    */
    auto a = new Node(1); 
    a->next = head->next , a->prev = head;
    head->next->prev = a , head->next = a;

    //0->2->1->0
    //类似的新建一个2，插在head后面
    auto b = new Node(2);
    b->next = head->next , b->prev = head;
    head->next->prev = b , head->next = b;


    //0->2->1->3->0
    //插在1结点后面插入3也是一样
    auto c = new Node(3);
    c->next = a->next , c->prev = a;
    a->next = c , a->next->prev = c;

    cout<<"插入bac：";
    print(head);

    //删除结点b（2）： 0->1->3->0   
    b->prev->next = b->next ; //修改b前面结点后指指针
    b->next->prev = b->prev ; //修改b后面结点前指指针
    delete(b);
    cout<<"最后："; 
    print(head);  //输出链表

    return 0;
}

7.3循环双链表

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

//循环双链表:结构体定义，比单链表多一个向前指的指针，同时最后一个和第一个也有指针互指
struct Node {
    int val ; //数值域
    Node* prev; //存放上一个结点的地址
    Node* next; //存放下一个结点的地址

    //下面定义两个构造函数，便于写代码。与单链表的定义无关，可忽略
    Node(): prev(NULL) , next(NULL) {}  //空构造函数，初始化prev , next即可 
    Node(int val): val(val) , prev(NULL) , next(NULL)  {}  //初始化，为结点赋值
};

//输出链表,跟之前单、双链表有点不一样
void print(Node* head){
    /*循坏遍历，用p指针从头开始遍历，p不是指向头结点的时候（因为对于循环双链表而言，没有
    空的节点），不断指向下一个结点，
    每到一个结点就输出当前点的val值
    */
    for(auto p = head->next ; p != head ; p = p->next)
        cout << p->val << ' ';
    cout << endl;
}


/*下面的代码只修改了tail指向head，其余跟双链表一样。*/
int main(){
    //head指针指向第一个结点的地址，他不是一个结点。初始链表为空，所以head指向null
    //Node* head = NULL; 

    //创造一个双链表, 同时head指针指向开头，tail指向head，头尾是同一个结点（循环）。
    Node* head =  new Node() , *tail = head;
    head->next = tail , tail->prev = head;  //初始化前后指针指向

    cout<<"初始情况(空)：" ;
    print(head); //初始情况：0->0

    /*0->1->0
    头插法：
    每次在head指针的后面插入。注意指针修改的顺序，不然可能会造成断链。建议写的时候
    画个图再去操作。
    */
    auto a = new Node(1); 
    a->next = head->next , a->prev = head;
    head->next->prev = a , head->next = a;

    //0->2->1->0
    //类似的新建一个2，插在head后面
    auto b = new Node(2);
    b->next = head->next , b->prev = head;
    head->next->prev = b , head->next = b;


    //0->2->1->3->0
    //插在1结点后面插入3也是一样
    auto c = new Node(3);
    c->next = a->next , c->prev = a;
    a->next = c , a->next->prev = c;

    cout<<"插入bac：";
    print(head);

    //删除结点b（2）： 0->1->3->0   
    b->prev->next = b->next ; //修改b前面结点后指指针
    b->next->prev = b->prev ; //修改b后面结点前指指针
    delete(b);
    cout<<"最后："; 
    print(head);  //输出链表

    return 0;
}