单链表

1.单链表##

对数据结构一直比较欠缺，所以准备i从头学习一下数据结构。
从单链表开始，链表的介绍和定义就省略了，我觉得学习单链表最重要的是掌握结点类和链表类的用法。掌握了这两个东西以后链表对象的各种方法都很容易实现。刚开始以为很难，后来研究之后发现仔细按照数据结构来写也不是很难。
实际上，下面的链表对象方法的框架记下来之后基本上就可以实现链表对象的所有方法了：

void List::method(int data)
{
    Node *p=head;
    if(p==NULL)
    {
        // do something...
    }
    while(p!=NULL && p->data!=data)
    {
        // do something...
    }
    if(p==NULL)
    {
        // do something...
    }
    else
    {
        // do something...
    }
    return;
}

直接上干货：

1. 链表结点类定义

class Node
{
public:
    int data;  //结点元素值
    Node *next;   //结点后继
    Node(int data=0,Node *next= NULL)  //构造函数，默认新结点值为null
    {
        this->data = data;
        this->next = next;
    }
};

2. 链表类的定义

class List
{
private:
    Node *head,*tail;  //链表对象需要定义头结点和尾结点
    int position;     
public:
    List(){head = tail = NULL;};  //构造函数，默认头尾结点都为空
    ~List(){delete head; delete tail;};  //析构函数，删除头结点和尾结点
    // void print();
    // 各种List对象的方法
};

3. 链表的ADT方法

void print();  //打印链表
void Insert(int data=0);  //在链表尾部插入数据
void Delete(int data=0);  //按照元素值删除结点
void Search(int data=0);  //按照元素值搜索，并打印索引
int getvalue(int position);   //按照索引返回元素值
void setvalue(int position,int data);  //按照索引更改结点的值
void Insertwithindex(int index,int data);  //按照索引插入结点
void Deletewithindex(int index);  //按照索引删除结点
int getindexofnumber(int data);   //按照元素值查找，返回索引
void Clearlist();   //清空链表
int Getlength();   //返回链表的长度

4. C++代码

#include <iostream>

using namespace std;
class Node
{
public:
    int data;
    Node *next;
    Node(int data=0,Node *next= NULL)
    {
        this->data = data;
        this->next = next;
    }
};
class List
{
private:
    Node *head,*tail;
    int possition;
public:
    List(){head = tail = NULL;};
    ~List(){delete head; delete tail;};
    void print();
    void Insert(int data=0);
    void Delete(int data=0);
    void Search(int data=0);
    int getvalue(int position);
    void setvalue(int position,int data);
    void Insertwithindex(int index,int data);
    void Deletewithindex(int index);
    int getindexofnumber(int data);
    void Clearlist();
    int Getlength();
};
//打印链表
void List::print()
{
    Node *p=head;
    cout << "List print: ";
    while(p!=NULL)
    {
        cout << p->data <<" " ;
        p=p->next;
    }
    cout <<endl;
}
//在尾部插入数据
void List::Insert(int data)
{
    if(head == NULL )
    {
        head=tail=new Node(data);
        head->next = NULL;
        tail->next = NULL;
    }
    else
    {
        Node *p=new Node(data);
        tail->next = p;
        tail=p;
        tail->next=NULL;
    }
}
//按照数据删除
void List::Delete(int data)
{
    Node *p=head,*pre;
    if(p==NULL)
    {   cout << "The LIST is empty!" <<endl;return;}
    while(p!=NULL && p->data!=data)
    {
        pre=p;
        p=p->next;
    }
    if(p==NULL)
    {cout << "There is no value "<<data<< " in this list." <<endl;}
    else
    {
        pre->next=p->next;
        delete(p);
    }
    return;
}
//按数据查找
void List::Search(int data)
{
    Node *p=head;
    if(p==NULL)
    {   cout << "The LIST is empty!" <<endl;return;}
    int count=0;
    while(p!=NULL && p->data!=data)
    {
        p=p->next;
        count++;
    }
    cout << "the value searched is at position " << count << endl;

}
//get某个位置的值
int List::getvalue(int postion)
{
    Node *p=head;
    if(p==NULL)
    {   cout << "The LIST is empty!" <<endl;}
    else
    {
        int pos =1;
        while(p!=NULL && pos!=postion)
        {   pos++;
            p=p->next;
        }
        if(p==NULL)
        {cout << "There is no value of this position!"<<endl;}
        else
        {cout << "In this position, the value is " << p->data<< endl;}
    }
    return p->data;
}
//set某个位置的值
void List::setvalue(int position, int data)
{
    Node *p=head;
    if(p==NULL)
    {cout << "The list is empty!"<< endl;}
    else
    {
        int pos=1;
        while(p!=NULL && pos!=position)
        {
            pos++;
            p=p->next;
        }
        if(p==NULL)
        {cout << "There is no position in this list!"<<endl;}
        else
        {
            p->data=data;
            cout << "The value in this position has been changed!" <<endl;
        }
    }
}
//按照索引插入数据
void List::Insertwithindex(int index, int data)
{
    Node *p=head,*pre;
    int count=1;
    while(p!=NULL && count!=index)
    {
        count++;
        pre=p;
        p=p->next;
    }
    if(p!=NULL)
    {
        Node *s=new Node;
        s->data=data;
        pre->next=s;
        s->next=p;
    }
    else
    {cout<< "the list has no index " <<index<<endl;return;}
}
//按照索引删除数据
void List::Deletewithindex(int index)
{
    Node *p=head,*pre;
    int count=1;
    while(p!=NULL && count!=index)
    {
        count++;
        pre=p;
        p=p->next;
    }
    if(p!=NULL)
    {
        pre->next=p->next;
        delete(p);
    }
    else
    {cout<< "the list has no index " <<index<<endl;return;}
    return;
}
//查找元素，返回索引
int List::getindexofnumber(int data)
{
    Node *p=head;
    int pos=1;
    while(p!=NULL && p->data!=data)
    {
        pos++;
        p=p->next;
    }
    if(p!=NULL)
    {
        cout << "the index of the data "  << pos << endl;
        return pos;
    }
    else
    {cout<< "the list has no data " <<data<<endl;return -1;}

}
//清空链表
void List::Clearlist()
{
    Node *p=head,*pre;
    while(p!=NULL)
    {
        pre=p;
        p=p->next;
        delete(pre);
    }
    head=NULL;
    tail=NULL;
}
//链表长度
int List::Getlength()
{
    Node *p=head;
    int count=1;
    while(p!=NULL)
    {
        count++;
        p=p->next;
    }
    cout << "the length of list is " << count << endl;
    return count;
}
//主函数
int main()
{
    List mylist;
    for(int i=1;i<10;++i)
    {
        mylist.Insert(i);
    }
    cout <<endl<< "********mylist.print();*********"<<endl;
    mylist.print();
    cout <<endl<< "********mylist.getvalue(3);*********"<<endl;
    mylist.getvalue(3);
    cout <<endl<< "********mylist.setvalue(3,9);*********"<<endl;
    mylist.setvalue(3,9);
    mylist.print();
    cout <<endl<< "********mylist.Delete(2);*********"<<endl;
    mylist.Delete(2);
    mylist.print();
    cout << endl<<"********mylist.Insertwithindex(3,999);*********"<<endl;
    mylist.Insertwithindex(3,999);
    mylist.print();
    cout << endl<<"********mylist.Deletewithindex(3);*********"<<endl;
    mylist.Deletewithindex(3);
    mylist.print();
    cout << endl<<"********mylist.getindexofnumber(4);*********"<<endl;
    mylist.getindexofnumber(4);
    mylist.print();
    cout << endl<<"********mylist.Getlength();*********"<<endl;
    mylist.Getlength();
    cout << endl<<"********mylist.Clearlist();*********"<<endl;
    mylist.Clearlist();
    mylist.print();
}