美文网首页
单链表(C++版本)

单链表(C++版本)

作者: ZayAlan | 来源:发表于2017-10-19 22:42 被阅读0次
数据结构上机实验题目要求

实现代码

//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;
}

相关文章

  • 单链表(C++版本)

    实现代码 //SLList.h SLList.cpp Test.cpp

  • 单链表 C++

    单链表 C++ 题目 1、创建单链表2、初始化单链表3、释放单链表4、获取单链表中元素的数量5、输出单链表中的所有...

  • 线性表的链式存储结构2.0

    这篇文章开启线性表的大版本更新2.0----循环链表 单循环链表 由前面关于单链表的介绍我们知道,在单链表中每个结...

  • 第2篇 C++ 数据结构-单链表(多图杀猫)

    如果你对链表《第2篇 C++ 数据结构-链表概述》请先阅读前文,我们前一篇已经罗列单链表的类接口清单,本篇会依据接...

  • 前缀树 LC208

    前缀树就是一个拥有26个指针的链表打算实现C++和python 版本。C++版本这里表示26个指针有两种方法一个拥...

  • 线性表:顺序表和链表

    顺序表(数组)优缺点 链表优点 单链表使用 单链表结构 单链表初始化 单链表初始化 单链表建立: 头插法 尾插法 ...

  • 单向链表算法

    单向链表 反转单向链表 单链表查找倒数第k个节点 单链表递归倒序打印 单链表排序 单链表删除重复节点

  • 链表基本操作

    1、删除单链表节点 2、插入单链表结点 单链表具体实现

  • 25_静态单链表的实现

    关键词: 单链表的一个缺点、静态单链表设计思路、静态单链表的继承层次结构、静态单链表的实现思路、静态单链表的实现 ...

  • 线性表的链式存储-单链表

    单链表操作 [x] 单链表的创建(尾插法、头插法) [x] 单链表的查找操作 [x] 单链表的删除操作 [x] 单...

网友评论

      本文标题:单链表(C++版本)

      本文链接:https://www.haomeiwen.com/subject/meapuxtx.html