单链表（C++版本）

数据结构上机实验题目要求

实现代码

//SLList.h

#ifndef SLLIST_H_INCLUDED
#define SLLIST_H_INCLUDED
template<class T>

//单链表结点结构
struct SLNode
{
    T data;//数据域
    SLNode<T> * next;//指针域
    SLNode(SLNode * nextNode=nullptr)
    {
        next=nextNode;
    }//构造函数
    SLNode(const T&item,SLNode * nextNode=nullptr)
    {
        data=item;
        next=nextNode;
    }//构造函数
};

//单链表类
template<class T>
class SLList
{
private:
    SLNode<T> * head;//头指针
    SLNode<T> * tail;//尾指针
    SLNode<T> * currptr;//当前指针
    int listsize;

public:
    SLList()
    {
        head=tail=currptr=new SLNode<T>();
        listsize = 0;
    }//构造函数，构造一个只有哨位结点的空表

    SLList(T &item)
    {
        tail=currptr=new SLNode<T>(item);
        head=new SLNode<T>(currptr);
        listsize=1;
    }

    ~SLList()
    {
        while(!IsEmpty())
        {
            currptr=head->next;
            head->next=currptr->next;
            delete currptr;
        }
        delete head;
    }//析构函数

    bool IsEmpty()const{return head->next==nullptr;}//判断链表是否为空

    int length()const;//翻回链表的长度

    void Find(int k)const;//存取，返回链表中第k个结点的字段值
    int FindNow()const;//存取当前结点的值

    void Search(int x)const;//查找，在链表中查找字段值为x的结点并返回其表中的位置

    void Delete();//删除当前结点的后继结点
    void DeleteHead();//删除表头结点
    void DeleteTail();//删除表尾结点

    void Insert(const T& item);//在当前结点前插入一个data为item的结点
    void InsertHead(const T& item);//在表头插入一个结点
    void InsertTail(const T& item);//在表尾插入一个结点

    void Print();//按格式输出链表

};

#endif // SLLIST_H_INCLUDED

SLList.cpp

#include "SLList.h"
#include<iostream>
using namespace std;
template<class T>
int SLList<T>::length()const
{
    return listsize;
}

template<class T>
void SLList<T>::Insert(const T& item)
{
    currptr->next=new SLNode<T>(item,currptr->next);
    if (tail==currptr)
        tail=currptr->next;
    listsize++;
}

template<class T>
void SLList<T>::InsertHead(const T& item)
{
    if (IsEmpty())
    {
        head->next=new SLNode<T>(item,head->next);
        tail=head->next;
    }
    else{
        head->next=new SLNode<T>(item,head->next);
    }
    listsize++;
}

template<class T>
void SLList<T>::InsertTail(const T& item)
{
    tail->next=new SLNode<T>(item,nullptr);
    tail=tail->next;
    listsize++;
}

template<class T>
void SLList<T>::Delete()
{
    if (currptr==tail||IsEmpty())
    {
        cout<<"No next node or empty list!";
    }
    SLNode<T> * temp=currptr->next;
    currptr->next=temp->next;
    listsize--;
    if(temp==tail) tail=currptr;
    delete temp;
}

template<class T>
void SLList<T>::DeleteHead()
{
    if (IsEmpty())
    {
        cout<<"Empty list!";
    }
    SLNode<T> * temp=head->next;
    head->next=temp->next;
    listsize--;
    if (temp==tail) tail=head;
    delete temp;
}

template<class T>
void SLList<T>::DeleteTail()
{
    if (IsEmpty())
    {
        cout<<"Empty list!";
    }
    while(currptr->next!=tail)
    {
        currptr=currptr->next;
    }
    currptr->next=nullptr;
    listsize--;
    delete tail;
    tail=currptr;
}

template<class T>
void SLList<T>::Find(int k)const
{
    SLNode<T>*temp=head->next;
    int i=1;
    if (k>listsize)
        cout<<"The number k is wrong!"<<endl;
    else
    {
        while(temp!=nullptr && i<k)
        {
                temp=temp->next;
                i++;
        }
        cout<<"The "<<k<<"th item is "<<temp->data<<endl;
    }

}

template<class T>
int SLList<T>::FindNow()const
{
    return currptr->data;
}

template<class T>
void SLList<T>::Search(int x)const
{
    SLNode<T> * temp=head;
    int position=0;
    for (int i = 1;i<=listsize;++i)
    {
        temp=temp->next;
        if (temp->data==x)
        {
            position = i;
            break;
        }
    }
    if(position==0)
    {
        cout<<"There isn't a "<<x<<" in the list!"<<endl;
    }
    else cout<<"The "<<x<<"\'s position is "<<position<<"!"<<endl;
}

template<class T>
void SLList<T>::Print()
{
    for(SLNode<T>*temp=head->next;temp;temp=temp->next)
    {
        cout<<"["<<temp->data<<"]";
        if(temp->next!=nullptr)
            cout<<"->";
    }
    cout<<endl<<"The listsize is "<<listsize<<endl;
}

Test.cpp

#include "SLList.h"
#include<iostream>
#include"SLList.cpp"
using namespace std;

int main(int argc, char const *argv[])
{
    SLList<int> list; //创建一个空表
    while(true)
    {
        int i;
        cout<<"What do you want to do?"<<endl;
        cout<<"1.insert  2.delete  3.find  4.search"<<endl;
        cin>>i;
        if (i==1)
        {
            cout<<"1.insertnow  2.insertHead  3.insertTail  4.back"<<endl;
            cin>>i;
            if (i==1)
            {
                cin>>i;
                list.Insert(i);
            }
            else if(i==2)
            {
                cin>>i;
                list.InsertHead(i);
            }
            else if (i==3)
            {
                cin>>i;
                list.InsertTail(i);
            }
            else
            {
                i=0;
                continue;
            }
            list.Print();
        }
        else if (i==2)
        {
            cout<<"1.deletenow  2.deleteHead  3.deleteTail  4.back"<<endl;
            cin>>i;
            if (i==1)
            {
                list.Delete();

            }
            else if(i==2)
            {
                list.DeleteHead();
            }
            else if (i==3)
            {
                list.DeleteTail();
            }
            else
            {
                i=0;
                continue;
            }
            list.Print();
        }
        else if (i==3)
        {
            cout<<"1.find k  2.findnow  3.back"<<endl;
            cin>>i;
            if (i==1)
            {
                cin>>i;
                list.Find(i);
            }
            else if(i==2)
            {
                cout<<list.FindNow()<<endl;
            }
            else
            {
                i=0;
                continue;
            }
        }
        else
        {
            cin>>i;
            list.Search(i);
        }
    }
    return 0;
}