单向链表

链表介绍

• 一个节点示意图

  
  Node 示意

• 一个单向链表示意图

  
  List 示意

代码

• 结点类

template<typename T>class MyList;
template<typename T>class Node
{
    friend class MyList<T>;
private:
    T data;
    Node* Link;
    Node<T>(T k):data(k),Link(nullptr) {};//私有构造函数 初始化data 与 Link 
};

• 链表类

template<typename T>class MyList
{
public:
    MyList() { _First = nullptr; };
    void Insert(T);//插入 从链表头插入
    void LookAll();
    void Remove(T);//删除
    void Inverse();//翻转
private:
    Node<T> *_First;
};

• 整体代码

#pragma once
#ifndef _MYLIST_H_
#define _MYLIST_H_
#include<iostream>

template<typename T>class MyList;
template<typename T>class Node
{
    friend class MyList<T>;
private:
    T data;
    Node* Link;
    Node<T>(T k):data(k),Link(nullptr) {};//私有构造函数 初始化data 与 Link 
};

template<typename T>class MyList
{
public:
    MyList() { _First = nullptr; };
    void Insert(T);//插入 从链表头插入
    void LookAll();
    void Remove(T);//删除
    void Inverse();//翻转
private:
    Node<T> *_First;

};
template<typename T>void MyList<T>::Insert(T k)
{/* 表头存放数据的 
    或者说没有表头
*/
    Node<T>* NewNode = new Node<T>(k);
    NewNode->Link = _First;//插入的节点指针域指向表头
    _First = NewNode;//插入的节点成为新的表头
}
template<typename T>void MyList<T>::LookAll()
{
    for (Node<T> *i = _First; i; i=i->Link)
    {
        std::cout << i->data;
        if (i->Link)
        {
            std::cout << "->";
        }
    }
    std::cout << std::endl;
}
template<typename T>void MyList<T>::Remove(T k)
{
    Node<T> *NowNode ;
    Node<T> *Previous = nullptr;
    for (NowNode= _First;
        NowNode&&NowNode->data!=k;
        Previous=NowNode,NowNode=NowNode->Link)
    {
        ;
    }
    if (NowNode)
    {
        if (Previous)Previous->Link = NowNode->Link;
        else _First = _First->Link;
        delete NowNode;
    }
}
template<typename T>void MyList<T>::Inverse()
{
    Node<T>*p=_First, *q=nullptr;
    while (p)//p跳到链表末尾 nullptr就结束循环
    {
        Node<T> *r = q;//取出原q的内容
        q = p;//q被p覆盖
        p = p->Link;//p++
        q->Link = r;//q+1=原q
    }
    _First = q;
}
#endif // !_MYLIST_H_

反转成员函数的实现

• 代码

template<typename T>void MyList<T>::Inverse()
{
    Node<T>*p=_First, *q=nullptr;
    while (p)//p跳到链表末尾 nullptr就结束循环
    {
        Node<T> *r = q;//取出原q的内容
        q = p;//q被p覆盖
        p = p->Link;//p++
        q->Link = r;//q+1=原q
    }
    _First = q;
}

• 步骤图解

  
  Inverse 示意