数据结构cpp实现——单链表

单链表

        采用链接存储方式的线性表称之为线性链表，最简单的线性链表结构为单链表。单链表的每一个元素用一个结点存储。data域用来存放数据，next域用来存放指向下一个元素的地址。

            一般规定^表示指针指向空。利用单链表存储数据，在删减或增加元素时不需要移动元素，相比于顺序表，可以更高效地实现插入和删除操作。            对于不带头结点的单链表，在第i个节点前插入数据可以分为三种情况

            1)在i=1时，表示在单链表最前面插入元素，即原来第一个元素之前。

            2)在1<i≤n时，新结点插入在原链表的a(i-1)和ai之间。            3)在i=n+1时，新节点插入在原链表表尾。

            删除操作：相比于顺序表的移动前后元素，单链表的删除操作相当简单。删除当前结点后，把前一个结点的指针指向赋值为下一个即可。

如果删除的结点为头结点，则需要修改头指针指向。            单链表的结点类模版定义和实现template<class T>

struct Node

{

    T data;//数据域

    Node<T> *next;//指针域

    Node(){next= nullptr;};//默认无参构造函数

    Node(T e,Node<T> *link= nullptr){data=e;next= link;};//有参构造函数

};            单链表的类模版定义和实现template<class T>

class LinkList {

private:

    Node<T> *head;//头结点指针

    int length;//元素个数长度

public:

    LinkList(){head= new Node<T>;length=0;};//无参构造器

    LinkList(T arr[],int n);//第一个参数为初始化数据的数组，第二个参数为对应的长度

    ~LinkList();//析构函数

    int GetLength() const{return length;};//返回单链表长度

    bool IsEmpty() const{return length==0;};//单链表是否为空

    void clear();//清空线性表

    void traverse() const;//遍历打印线性表

    int LocateElem(const T &e);//求e元素在线性表中的位置

    bool GetElem(int i, T &e) const;//获取第i个结点的数据赋值给e返回true，若失败则返回false

    bool SetElem(int i, const T &e);//修改第i个结点的值

    bool DeleteElem(int i, const T &e);//删除第i个结点，并将数据域返回给e

    bool insert(int i, const T &e);//在原链表的第i个结点之前插入e

    bool insert(const T&e);//在链表尾部插入结点

};

template<class T>

LinkList<T>::LinkList(T *arr, int n) {

    Node<T> *p;

    p=head=new Node<T>;

    assert(head);//头结点构造失败则终止程序

    for(int i=0;i<n;i++)

    {

        p->next=new Node<T>(arr[i], nullptr);

        assert(p->next);

        p=p->next;//逐级向下遍历

    }

    this->length=n;

}

template<class T>

LinkList<T>::~LinkList() {

    clear();

    delete head;

}

template<class T>

void LinkList<T>::clear() {

    Node<T> *p=head->next;

    while(p!= nullptr)

    {

        head->next=p->next;

        delete p;

        p=head->next;

    }

    length=0;

}

template<class T>

void LinkList<T>::traverse() const {

    Node<T> *p=head->next;

    while(p!= nullptr)

    {

        std::cout<<p->data<<" ";

        p=p->next;

    }

}

template<class T>

int LinkList<T>::LocateElem(const T &e) {

    Node<T> *p=head->next;

    int position=1;

    while(p!= nullptr)

    {

        if(p->data==e)

            return position;

        position++;

        p=p->next;

    }

    return 0;

}

template<class T>

bool LinkList<T>::GetElem(int i, T &e) const {

    if(i<1||i>length)

        return false;//元素取值位置非法

    else

    {

        Node<T> *p=head->next;

        for(int count=1;count<i;count++)

            p=p->next;

        e=p->data;

        return true;

    }

}

template<class T>

bool LinkList<T>::SetElem(int i, const T &e) {

    if(i<1||i>length)

        return false;

    else

    {

        Node<T> *p=head->next;

        for(int count=1;count<i;count++)

            p=p->next;

        p->data=e;

        return true;

    }

}

template<class T>

bool LinkList<T>::DeleteElem(int i, const T &e) {

    if(i<1||i>length)

        return false;

    else

    {

        Node<T> *p=head,*q;

        for(int count=1;count<i;count++)

            p=p->next;//p实际指到了要删除的元素的前一个结点

        e=p->next->data;//将第i个元素返回给e

        q=p->next;

        p->next=q->next;//将第i-1个节点的next指针指向下下个结点

        delete q;

        length--;

        return true;

    }

}

template<class T>

bool LinkList<T>::insert(int i, const T &e) {

    if(i<1||i>length+1)

        return false;

    else

    {

        Node<T> *p=head,*q;

        for(int count=1;count<i;count++)

            p=p->next;//定位到第i-1个结点

        q=new Node<T>(e, p->next);

        assert(q);

        p->next=q;

        length++;

        return true;

    }

}

template<class T>

bool LinkList<T>::insert(const T &e) {

    Node<T> *p,*q;

    q=new Node<T> (e, nullptr);

    for(p=head;p->next!= nullptr;p=p->next);

    p->next=q;//表尾指针指向新加入的结点q

    length++;

    return true;

}单链表相比于顺序表更加节省内存空间，并且在删除和插入操作方面，明显优于顺序表。缺点是不支持随机访问(像数组一样直接定位元素位置)，必须通过头结点，依次遍历到所需要的结点。