有头链表实现(C++描述)

有头链表实现

#include <iostream>
#include <string>
#include <cstdlib>
using namespace std;

/****************有头链表****************/

//定义数据类型
struct student 
{
    string name;
    int age;
    int num;
};

//数据节点定义
template<typename T>
struct Node 
{
    T data;
    Node<T>* next;
    Node() 
    {
        this->next = nullptr;
    }
    Node(T data) 
    {
        this->data = data;
        this->next = nullptr;
    }
    Node(T data, Node<T>* nextNode)
    {
        this->data = data;
        this->next = nextNode;
    }
};

//链表定义
template<class T>
class myList
{
public:
    myList()
    {
        this->size = 0;
        this->headNode = new Node<T>();
    }
    void push_front(T data);
    void push_back(T data);
    void push_appoint(T data, int pos);
    void pop_front();
    void pop_back();
    void pop_appoint(T posData);
    void printList();
    int  listSize();
    bool empty();
    ~myList() 
    {
        delete headNode;
    }
protected:
private:
    int size;
    Node<T>* headNode;
public:
    Node<T>* begin()
    {
        return headNode->next;
    }
    Node<T>* end()
    {
        Node<T>* curNode = headNode->next;
        while (curNode != nullptr)
        {
            curNode = curNode->next;
        }
        return curNode;
    }
    class iterator
    {
    public:
        iterator(Node<T>* pMove = nullptr){}
        //实现对象到指针的赋值
        void operator=(Node<T>* pMove)
        {
            this->pMove = pMove;
        }
        bool operator!=(Node<T>* pMove)
        {
            return this->pMove != pMove;
        }
        //重载后置++
        iterator& operator++(int)
        {
            this->pMove = this->pMove->next;
            return (*this);
        }
        //实现取值操作
        T operator*()
        {
            return this->pMove->data;
        }
    protected:
    private:
        Node<T>* pMove;
    };
};

//头部插入
template <typename T>
void myList<T>::push_front(T data)
{
    //创建新节点
    Node<T>* newNode = new Node<T>(data,headNode->next);
    //newNode->next = headNode->next;
    headNode->next = newNode;
    size++;
}

//尾部插入
template <typename T>
void myList<T>::push_back(T data)
{
    //创建新节点
    Node<T>* newNode = new Node<T>(data);
    Node<T>* curNode = headNode;
    while (curNode->next != nullptr)
    {
        curNode = curNode->next;
    }
    curNode->next = newNode;
    size++;
}

//指定位置插入
template <typename T> 
void myList<T>::push_appoint(T data, int pos)
{
    Node<T>* curNode = headNode->next;
    Node<T>* preNode = headNode;
    while (curNode != nullptr && --pos)
    {
        preNode = curNode;
        curNode = curNode->next;
    }
    Node<T>* newNode = new Node<T>(data, curNode);
    preNode->next = newNode;
    size++;
}

//头部删除
template <typename T>
void myList<T>::pop_front()
{
    if (!empty()) {
        Node<T>* delNode = headNode->next;
        headNode->next = delNode->next;
        delete delNode;
        size--;
    }
    else 
    {
        cout << "表为空,节点删除失败!" << endl;
        return;
    }
}

//尾部删除
template <typename T>
void myList<T>::pop_back()
{
    if (!empty()) {
        Node<T>* preNode = headNode;
        Node<T>* delNode = headNode->next;
        while (delNode->next != nullptr)
        {
            preNode = delNode;
            delNode = delNode->next;
        }
        preNode->next = nullptr;
        delete delNode;
        size--;
    }
    else
    {
        cout << "表为空,节点删除失败!" << endl;
        return;
    }
}

//指定数据删除
template <typename T>
void myList<T>::pop_appoint(T posData)
{
    if (!empty()) {
        Node<T>* preNode = headNode;
        Node<T>* delNode = headNode->next;
        while (delNode != nullptr && delNode->data != posData)
        {
            preNode = delNode;
            delNode = delNode->next;
        }
        if (delNode != nullptr) 
        {
            preNode->next = delNode->next;
            delete delNode;
            size--;
        }
        else 
        {
            cout << "没有找到指定数据,删除失败!" << endl;
            return;
        }
    }
    else
    {
        cout << "表为空,节点删除失败!" << endl;
        return;
    }
}

//重载输出流
ostream& operator<<(ostream& out,student stu)
{
    cout << stu.name << "\t" 
        << stu.age << "\t" 
        << stu.num;
    cout << endl;
    return out;
}

//数据打印
template <typename T>
void myList<T>::printList() 
{
    Node<T>* curNode = headNode->next;
    while (nullptr != curNode) {
        cout << curNode->data << "\t";
        curNode = curNode->next;
    }
    cout << endl;
}
//返回链表大小
template <typename T>
int myList<T>::listSize()
{
    return size;
}
//判断链表是否为空
template <typename T>
bool myList<T>::empty()
{
    return size == 0;
}

int main()
{
    //操作基本数据类型
    myList<int> listInt;
    //头部插入
    for (int i = 0; i < 10; i++)
    {
        listInt.push_front(520 + i);
    }
    listInt.printList();
    //尾部插入
    listInt.push_back(1213);
    listInt.printList();
    //指定位置插入
    listInt.push_appoint(666, 2);
    listInt.printList();
    //头部删除
    listInt.pop_front();
    listInt.printList();
    //尾部删除
    listInt.pop_back();
    listInt.printList();
    //指定数据删除
    listInt.pop_appoint(524);
    listInt.pop_appoint(777);
    listInt.printList();

    //迭代器遍历
    myList<int>::iterator iter;
    for (iter = listInt.begin(); iter != listInt.end(); iter++)
    {
        cout << *iter << "\t";
    }
    cout << endl;


    //操作string类型
    //myList<string>* listStr = new myList<string>;
    //for (int i = 0; i < 10; i++)
    //{
    //    listStr->push_front("string");
    //}
    //listStr->printListData();
    //delete listStr;

    //操作自定义数据类型
    //myList<student>* listStu = new myList<student>;
    //student array[5] = { {"张三",18,1001},{"李四",19,1002},
    //    {"王二",20,1003},{"吕布",21,1004},{"刘备",22,1005} };
    //for (int i = 0; i < 5; i++)
    //{
    //    listStu->push_front(array[i]);
    //}
    //listStu->printListData();
    //delete listStu;

    system("pause");
    return 0;
}

        

          
        
        
        

          

          AI 代码解读