【数据结构】单向链表SinglyLinkedList

SinglyLinkedList.h

#include<stdlib.h> 
#include<iostream>
class node{
    public:
        int data;//结点的值 
        node *next;//保存后继结点的地址 
        node(){
            data = -1;
            next = NULL;
        }
        //构造方法，方便快速创建结点 
        node(int data,node *next){
            this->data = data;
            this->next = next;
        }
};

class List{
    private:
        node* head;//指向表头(表头恒为空) 
        int lenth;//单链表当前最大下标值 
        bool check(int index);//工具方法，检测index合法性 
    public:
        int size(){return lenth+1;}//返回链表长度 
        List();//构造函数
        List(const List& temp);//拷贝构造函数 
        ~List();//析构函数
        
        void append(const int num);//添加到表尾 
        void insert(int index,int num);//在index处添加元素num
        void delnum(int index);//删除index处元素
        void clear();//清除操作 
        void combine(int index,const List& temp);//index后面插入另一个链表 
        
        int& operator[](int index);//重载[]运算符 
        int search(int aim);//搜索aim元素 
        void show();//显示链表的全部元素
};
//检查边界 
bool List::check(int index){
    if(index<0||index>lenth){
        std::cout << "INDEX_ERROR" << std::endl;
        return false;
    }
    return true;
}
//构造函数
List::List(){
    head = new node;
    lenth = -1;
}
//拷贝构造函数
List::List(const List& copy){
    node* p1 = head;
    node* p2 = copy.head->next;
    while(p2!=NULL){
        p1->next = new node(p2->data,NULL);
        p1 = p1->next;
        lenth++;
        p2 = p2->next;
    }
} 
//析构函数 
List::~List(){
    node* p1;//p1在p2的前面，p1负责指向待删除结点，p2负责向后遍历 
    node* p2 = head;
    while(p2->next!=NULL){
        p1 = p2;
        p2 = p2->next;
        delete p1;
    }
    delete p2;
}
//附加操作 
void List::append(const int num){
    node* p = head;//p用来遍历链表 
    while(p->next!=NULL) p=p->next;//向后遍历直到结尾 
    p->next = new node(num,NULL);//在结尾创建一个新的结点 
    lenth++;//最长下标+1
}
//插入操作 
void List::insert(int index,int num){
    if(index<0||index>lenth+1){
        std::cout << "INDEX_ERROR" << std::endl;
        return;
    }
    node* p1 = head;//p1负责指向被插入结点的前继(index-1)位置 
    node* p2 = new node(num,NULL);//p2存储新结点 
    for(int i=0;i<index;i++) p1 = p1->next;//p1向后遍历寻找index-1的位置 
    p2->next = p1->next;//新结点(p2)指向p1的后继结点 
    p1->next = p2;//p1指向新结点(p2) 
    lenth++;
}
//删除操作
void List::delnum(int index){
    if(!check(index)) return;
    node* p1 = head;
    node* p2;
    for(int i=0;i<index;i++) p1 = p1->next;
    p2 = p1->next;
    p1->next = p2->next;
    delete p2;
    lenth--;
} 
//清除操作 
void List::clear(){
    node* p1;
    node* p2 = head->next;
    while(p2->next!=NULL){
        p1 = p2;
        p2 = p2->next;
        delete p1;
    }
    delete p2;
    head->next = NULL;
    lenth = 0;
}
//插入另一链表 
void List::combine(int index,const List& inserted){
    if(!check(index)) return;
    node* p1 = head;
    node* p2 = inserted.head->next;
    for(int i=0;i<index;i++) p1 = p1->next;
    while(p2!=NULL){
        node* temp = new node(p2->data,p1->next);
        p1->next = temp;
        p2 = p2->next;
        lenth++;
    }
}
//重载[] 
int& List::operator[](int index){
    if(!check(index)) return this->head->data;
    node* p = this->head;
    for(int i=0;i<=index;i++) p=p->next;
    return p->data;
}
//搜索操作
int List::search(int aim){
    node* p = head->next;
    int ans = 0;
    while(p!=NULL && p->data!=aim){
        p = p->next;
        ans++;
    }
    if(p==NULL) return -1; 
    return ans;
} 
//显示操作 
void List::show(){
    node* p = head->next;
    while(p!=NULL){
        std::cout << p->data << " ";
        p = p->next;
    }
    std::cout << std::endl;
}