数据结构 链表

单链表：

1.节点（结点）：数据加指向下一个数据的地址（指向下一个数据的指针），组成了了一个节点 2.链表由若干节点组成 3.头指针：存储第一个节点的地址的指针，头指针可以标记一个链表

两个特殊节点： 1.首元节点：第一个存储真实数据的节点。（非空链表，一定有首元节点） 2.头节点：链表中第一个不存储真实数据的节点（头节点可有可无），如果头节点存在，那么头节点一定是链表的第一个节点

声明链表==声明节点

增强可读性，声明头指针 linklist l;

头节点作用： 1.当不带头节点时，对首元节点的操作需要涉及到头指针，非常特殊； 带头节点时，首元节点与其他节点无异 2.对空链表的操作：带头节点，空链表与非空链表均有节点，统一起来了

1.增： 不带头节点的链表：在首元节点前插入一个节点，需要改变头指针

初步代码实现如下： #define _CRT_SECURE_NO_WARNINGS

#include<iostream>

using namespace std;

template<class T>

class Node
{
public:
    T date;
    Node* next;
};
template<class T>
class LinkList
{
public:
    Node<T>* m_head;
public:
    LinkList()
    {
        m_head = new Node<T>;
        if (m_head == nullptr)
        {
            cout << "开辟失败" << endl;
        }
        else
        {
            m_head->next = nullptr;
        }
    }
    //查找函数
    LinkList* Find(LinkList* head, T k)
    {
        Node<T>* pt = head->m_head->next;
        while (pt->next != nullptr)
        {
            if (pt->date == k)
            {
                cout << "找到了" << endl;
                return head;
            }
            pt = pt->next;
        }
        if (pt->next == nullptr)
        {
            cout << "没找到" << endl;
        }
        return head;
    }
    //头插函数
    LinkList* head_insert(LinkList* head, T k)
    {
        Node<T>* s = new Node<T>;
        if (s == nullptr)
        {
            cout << "开辟失败" << endl;
        }
        else
        {
            s->date = k;
            s->next = head->m_head->next;
            head->m_head->next = s;
        }
        return head;
    }
    //尾插函数
    LinkList* tail_insert(LinkList* head, T k)
    {
        Node<T>* s = new Node<T>;
        if (s == nullptr)
        {
            cout << "开辟失败" << endl;
        }
        else
        {
            s->date = k;
            s->next = nullptr;
            //先找到最后一个节点
            Node<T>* pt = head->m_head;
            while (pt != nullptr)
            {
                if (pt->next == nullptr)
                {
                    break;
                }
                pt = pt->next;
            }
            pt->next = s;
        }
        return head;
    }
    //中间插入
    LinkList* mid_insert(LinkList* head, T x, T k)
    {
        Node<T>* s = new Node<T>;
        if (s == nullptr)
        {
            cout << "开辟失败" << endl;
        }
        else
        {
            s->date = k;
            //找x所在节点
            Node<T>* pt = head->m_head;
            while (pt->date != x)
            {
                pt = pt->next;
            }
            s->next = pt->next;
            pt->next = s;
        }
        return head;
    }
    //删除
    LinkList* del(LinkList* head, T k)
    {
        //查找k所在节点
        Node<T>* pt = head->m_head->next;//k
        Node<T>* pre = head->m_head;//pt前一个节点
        while (pt->date != k)
        {
            pt = pt->next;
            pre = pre->next;
        }
        pre->next = pt->next;
        pt->next = nullptr;
        delete pt;
        pt = nullptr;
        return head;
    }
    //修改
    LinkList* Change(LinkList* head, T x, T k)
    {
        //查找x所在节点
        Node<T>* pt = head->m_head->next;//x
        while (pt->date != x)
        {
            pt = pt->next;
        }
        pt->date = k;
        return head;
    }
    void My_print(LinkList* head)
    {
        Node<T>* pt = head->m_head->next;
        while (1)
        {
            cout << pt->date << endl;
            pt = pt->next;
            if (pt->next == nullptr)
            {
                cout << pt->date << endl;
                break;
            }
        }
    }
};


int main()
{
    LinkList<int> l;
    l.head_insert(&l, 1);
    l.head_insert(&l, 2);
    l.head_insert(&l, 3);
    l.tail_insert(&l, 4);
    l.tail_insert(&l, 5);
    l.tail_insert(&l, 6);
    l.mid_insert(&l, 5, 1111);
    l.Change(&l, 1111, 2222);
    l.Find(&l, 2222);
    l.del(&l, 2222);
    l.Find(&l, 2222);
    l.My_print(&l);
    return 0;
}