提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  Java

当前栏目

单链表的各种实现，绝对全（学习数据结构必看！）

2023-02-18 16:26:30 时间

上一个文章我们简单的了解的顺序存储与单链表的区别，相信大家和以前的我一样还不太会写单链表，因为本人是c++的，所以就用c++来实现一下简单的单链表基本操作，，都注意了：基操，勿6，新人需要点赞 上级链接::: 论链表和顺序储存的优缺点（干货）

#include"LinkList.h"

LinkList::LinkList()
{
    head = new Node;
    head->data=0;
    head->next=nullptr;
}
LinkList::~LinkList()//析构
{
    delete head;
}

int LinkList::GetLen()
{
    int size=0;
    Node * p = head->next;
    while (p!=nullptr)
    {
        size++;
        p=p->next;
    }
    return size;
}
bool LinkList::isEmpty()
{
    if(head->next==nullptr)
    {
        return true;
    }
    else
    {
        return false;
    }
}

void LinkList::CreateLinkList(int size)
{
    using namespace std;
    Node * pnew,* ptemp;
    ptemp = head;
    if (size<0)
    {
        cout<<"输入的节点有误"<<endl;
        exit(-1);
    }
    for (int i=0;i<size;i++)
    {
        //不断new新的指针，将当前指针的下一节点指向新的指针
        pnew = new Node;//开辟堆区
        cout<<"请输入第"<<i+1<<"个元素的值"<<endl;
        cin>>pnew->data;
        pnew->next=nullptr; //下一节点设为空指针
        ptemp->next = pnew; //当前节点的下一节点设为新的节点
        ptemp = pnew;   //当前节点节点设为新节点
    }

}

void LinkList::showLinkList()
{
    using namespace std;
    if(head==nullptr&&head->next==nullptr)
    {
        cout<<"链表为空表"<<endl;
    }
    Node * p =head;
    while (p->next!=nullptr)
    {
        p = p->next;
        cout<<p->data<<endl;
    }
}

//查找元素
Node * LinkList::Find(int data )
{
    using namespace std;
    Node * p = head;
    if (p==nullptr)
    {
        cout<<"链表为空表"<<endl;
        return nullptr;
    }
    else
    {
        while(p->next!= nullptr)
        {
            if(p->data == data)
            {
                return p;

            }
            p=p->next;
        }
    }
    if(p->data == data)
    {
        return p;
    }
    else
    {
        return nullptr;
    }

}
//在尾部插入指定的元素
void LinkList::InsertElemAtEnd(int data)
{
    Node * newNode = new Node;    //定义一个Node结点指针newNode
    newNode->next = nullptr;         //定义newNode的数据域和指针域
    newNode->data = data;
    Node * p = head;              //定义指针p指向头结点
    if (head == nullptr) {           //当头结点为空时，设置newNode为头结点
        head = newNode;
    }
    else                          //循环知道最后一个节点，将newNode放置在最后
    {
        while (p->next != nullptr)
        {
            p = p->next;
        }
        p->next = newNode;
    }
}
//在指定位置插入指定元素
void LinkList::InsertElemAtIndex(int data,int n)
{
    using namespace std;
    if (n<1 || n>GetLen())                   //输入有误报异常
        cout << "输入的值错误" << endl;
    else
    {
        Node * ptemp = new Node;        //创建一个新的节点
        ptemp->data = data;                     //定义数据域
        Node * p = head;                    //创建一个指针指向头结点
        int i = 1;
        while (n > i)                           //遍历到指定的位置
        {
            p = p->next;
            i++;
        }
        ptemp->next = p->next;                 //将新节点插入到指定位置
        p->next = ptemp;
    }
}
//在头部插入指定元素
void LinkList::InsertElemAtHead(int data)
{
    Node * newNode = new Node;    //定义一个Node结点指针newNode
    newNode->data = data;
    Node * p = head;              //定义指针p指向头结点
    if (head == nullptr) {           //当头结点为空时，设置newNode为头结点
        head = newNode;
    }
    newNode->next = p->next;          //将新节点插入到指定位置
    p->next = newNode;
}

//在尾部删除元素
void LinkList::DeleteElemAtEnd()
{
    using namespace std;
    Node * p = head;          //创建一个指针指向头结点
    Node * ptemp = nullptr;      //创建一个占位节点
    if (p->next == nullptr) {        //判断链表是否为空
        cout << "单链表空" << endl;
    }
    else
    {
        while (p->next != nullptr)   //循环到尾部的前一个
        {
            ptemp = p;            //将ptemp指向尾部的前一个节点
            p = p->next;          //p指向最后一个节点
        }
        delete p;                //删除尾部节点
        p = nullptr;
        ptemp->next = nullptr;
    }
}

//删除所有数据
void LinkList::DeleteAll()
{
    Node * p = head->next;
    Node * ptemp = new Node;
    while (p != nullptr)                    //在头结点的下一个节点逐个删除节点
    {
        ptemp = p;
        p = p->next;
        head->next = p;
        ptemp->next = nullptr;
        delete ptemp;
    }
    head->next = nullptr;                 //头结点的下一个节点指向NULL
}

//删除指定的数据
void LinkList::DeleteElemAtPoint(int data)
{
    Node * ptemp = Find(data);    //查找到指定数据的节点位置
    if (ptemp == head->next) {        //判断是不是头结点的下一个节点，如果是就从头部删了它
        LinkList Link;
        Link.DeleteElemAtHead();
    }
    else
    {
        Node * p = head;          //p指向头结点
        while (p->next != ptemp)      //p循环到指定位置的前一个节点
        {
            p = p->next;
        }
        p->next = ptemp->next;         //删除指定位置的节点
        delete ptemp;
        ptemp = nullptr;
    }

}

//在头部删除节点
void LinkList::DeleteElemAtHead()
{
    using namespace std;
    Node * p = head;
    if (p == nullptr || p->next == nullptr)
    {   //判断是否为空表，报异常
        cout << "该链表为空表" << endl;
    }
    else
    {
        Node * ptemp = nullptr;      //创建一个占位节点
        p = p->next;
        ptemp = p->next;              //将头结点的下下个节点指向占位节点
        delete p;                     //删除头结点的下一个节点
        p = nullptr;
        head->next = ptemp;           //头结点的指针更换
    }
}

```cpp
//主函数：
#include <iostream>
#include"LinkList.h"
using namespace std;

int main()
{
    LinkList l;
        int i;
        cout << "1.创建单链表   2.遍历单链表   3.获取单链表的长度   4.判断单链表是否为空   5.获取节点\n";
        cout << "6.在尾部插入指定元素   7.在指定位置插入指定元素   8.在头部插入指定元素\n";
        cout<<"9.在尾部删除元素   10.删除所有元素   11.删除指定元素   12.在头部删除元素   0.退出" << endl;
        do
        {
            cout << "请输入要执行的操作: ";
            cin >> i;
            switch (i)
            {
            case 1:
                int n;
                cout << "请输入单链表的长度: ";
                cin >> n;
                l.CreateLinkList(n);
                break;
            case 2:
                l.showLinkList();
                break;
            case 3:
                cout << "该单链表的长度为" << l.GetLen() << endl;
                break;
            case 4:
                if (l.isEmpty() == 1)
                    cout << "该单链表是空表" << endl;
                else
                {
                    cout << "该单链表不是空表" << endl;
                }
                break;
            case 5:
                int data;
                cout << "请输入要获取节点的值: ";
                cin >> data;
                cout << "该节点的值为" << l.Find(data)->data << endl;
                break;
            case 6:
                int endData;
                cout << "请输入要在尾部插入的值: ";
                cin >> endData;
                l.InsertElemAtEnd(endData);
                break;
            case 7:
                int pointData;
                int index;
                cout << "请输入要插入的数据: ";
                cin >> pointData;
                cout << "请输入要插入数据的位置: ";
                cin >> index;
                l.InsertElemAtIndex(pointData, index);
                break;
            case 8:
                int headData;
                cout << "请输入要在头部插入的值: ";
                cin >> headData;
                l.InsertElemAtHead(headData);
                break;
            case 9:
                l.DeleteElemAtEnd();
                break;
            case 10:
                l.DeleteAll();
                break;
            case 11:
                int pointDeleteData;
                cout << "请输入要删除的数据: ";
                cin >> pointDeleteData;
                l.DeleteElemAtPoint(pointDeleteData);
                break;
            case 12:
                l.DeleteElemAtHead();
                break;
            default:
                break;
            }
        }while (i != 0);

        return 0;
}

相关文章