[数据结构与算法]C++实现写一个单向链表

1、头文件head.h

#ifndef HEAD_H_
#define HEAD_H_
#include<iostream>
struct node
{
    node():data(-1),next(static_cast<struct node*>(NULL)){}
    node(int x, struct node* p = static_cast<struct node*>(NULL)):data(x),next(p){}
    int data;  //节点的数据
    struct node* next;  //节点的指向下一个节点的指针
};

class LIST
{
public:
    LIST(); //构造函数
    void push_back(int x);  //末尾添加
    void push_front(int x);  //头部添加
    void Insert(int i, int x);  //插入一个x到第i个元素
    int Delete(int i);  //删除第i个元素
    int GetData(int i);
    int Search(int x);
    int Size();
    void Display();

private:
    node* head; //链表的信息只有头节点head
    int num;
};

#endif

2、库文件head.cpp

#include"head.h"
using namespace std;

LIST::LIST():num(0),head(new node)
{}

void LIST::push_back(int x)
{
    node* it = head;
    while(it->next!=NULL)
    {
        it=it->next;  //最后一个节点
    }
    it->next = new node(x);
    num++;
}

void LIST::push_front(int x)
{
    node *p = new node(x);
    p->next = head->next;
    head->next = p;
    num++;
}

void LIST::Insert(int i, int x)
{
    if(i>num)
    {
        cout<<"插入位置超出界限"<<endl;
        return;
    }

    node* it=head;
    for(int j=0; j<i-1; j++)
    {
        it=it->next;//第i-1个节点
    }
    node* p = new node(x);
    p->next = it->next;  //原本的第i个
    it->next = p;
    num++;
}

int LIST::Delete(int i)
{
    if(i>num)
    {
        cout<<"删除超出范围"<<endl;
        return -1;
    }
    else
    {
        node *it = head;
        for(int j =0;j<i-1;j++)
        {
            it=it->next;  //第i-1个
        }
        node *p = it->next; //第i个
        int shuchu = p->data;
        it->next = p->next;
        delete p;
        num--;
        return shuchu;
    }
}

int LIST::GetData(int i)
{
    if(i>num)
    {
        cout<<"超出范围"<<endl;
        return -1;
    }
    else
    {
        node* it=head;
        for(int j=0;j<i;j++)
        {
            it=it->next;
        }
        return it->data;
    }
}

int LIST::Search(int x)
{
    node* it = head;
    int result=0;
    while(it->next!=NULL)
    {
        it=it->next;
        if(it->data==x)
        {
            break;
        }
        result++;
    }
    if(result<num)
    {
        result++;
    }
    else
    {
        result=-1;
        cout<<"没有元素"<<"x"<<endl;
    }
    return result;
}

int LIST::Size()
{
    int i=0;
    node* it=head;
    while(it->next!=NULL)
    {
        it=it->next;
        i++;
    }
    return i;
}

void LIST::Display()
{
    node* it=head;
    while(it->next!=NULL)
    {
        it=it->next;
        cout<<it->data<<"\t";
    }
    cout<<endl;
}

3、主程序main1.cpp

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

int main(int argc, char** argv)
{
    LIST list;
    for(int i=0;i<5;i++)
    {
        list.push_back(i);
    }
    list.Display();  //0 1 2 3 4

    list.push_front(22); // 22 0 1 2 3 4
    list.Display();

    list.push_front(33);// 33 22 0 1 2 3 4
    list.Display();

    list.push_front(44);  // 44 33 22 0 1 2 3 4
    list.Display();

    list.Delete(3);  //44 33 0 1 2 3 4
    list.Display();

    list.Insert(3,44);  // 44 33 44 0 1 2 3 4
    list.Display();
    cout<<list.Size()<<endl;  //8

    cout<<"2在第 "<<list.Search(2)<<"个"<<endl;  //6

    return 0;
}