C/C++教程

C++的链表实现

本文主要是介绍C++的链表实现,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

初学数据结构与算法,半参考半自写的写出了C++的链表实现。

节点结构体代码:

template<class ElemType>
struct Node {
    ElemType data;
    Node< ElemType>* next;
    Node() {
        next = NULL;
    }
    Node(const ElemType& e, Node< ElemType>* link = NULL) {
        data = e;
        next = link;
    }
};

链表:

#include"node.h"
template<class ElemType>
class SimpleLinkList {
protected:
    Node< ElemType>* head;
    Node< ElemType>* GetElemPtr(int position)const;
public:
    SimpleLinkList();
    virtual ~SimpleLinkList();
    int Length()const;
    bool Empty()const;
    void Clear();
    void Traverse(void(*visit)(const ElemType&))const;
    bool GetElem(int position, ElemType& e)const;
    bool SetElem(int position, ElemType& e);
    bool Delete(int position);
    bool Delete(int position, const ElemType& e);
    bool Insert(int position, const ElemType& e);
    SimpleLinkList(const SimpleLinkList<ElemType>& source);
    SimpleLinkList<ElemType>& operator=(const SimpleLinkList<ElemType>& source);
};
template<class ElemType>
void SimpleLinkList<ElemType>::Clear() {
    while (!Empty()) {
        Delete(1);
    }
}
template<class ElemType>
bool SimpleLinkList<ElemType>::Empty()const {
    return head->next == NULL;
}
template<class ElemType>
int SimpleLinkList<ElemType>::Length()const {
    int count = 0;
    for (Node<ElemType>* temptr = head->next; temptr != NULL; temptr = temptr->next) {
        count++;
    }
    return count;
}
template<class ElemType>
SimpleLinkList<ElemType>::SimpleLinkList() {
    head = new Node<ElemType>;
}
template<class ElemType>
SimpleLinkList<ElemType>::~SimpleLinkList()
{
    Clear();
    delete head;
}
template<class ElemType>
void SimpleLinkList<ElemType>::Traverse(void(*visit)(const ElemType&))const {
    for (Node<ElemType>* temptr = head->next; temptr != NULL; temptr = temptr->next) {
        (*visit)(temptr->data);
    }
}
template<class ElemType>
Node<ElemType>* SimpleLinkList<ElemType>::GetElemPtr(int position)const {

    Node<ElemType>*temptr = head;
    int tempos = 0;
    while (temptr != NULL && tempos < position) {
        temptr = temptr->next;
        tempos++;
    }
    if (temptr != NULL && tempos == position) {
        return temptr;
    }
    else {
        return NULL;
    }
}
template<class ElemType>
bool SimpleLinkList<ElemType>::GetElem(int position, ElemType& e)const {
    if (position<1 || position>Length()) {
        return false;
    }
    else {
        Node<ElemType>* temptr = GetElemPtr(position);
        e = temptr->data;
        return true;
    }
}
template<class ElemType>
bool SimpleLinkList<ElemType>::Insert(int position, const ElemType& e) {
    if (position<1 || position>Length() + 1) {
        return false;
    }
    else {
        Node<ElemType>* temptr = GetElemPtr(position - 1);
        Node<ElemType>* newptr = new Node<ElemType>(e, temptr->next);
        temptr->next = newptr;
        return true;
    }
}
template<class ElemType>
SimpleLinkList<ElemType>::SimpleLinkList(const SimpleLinkList<ElemType>& source)
{
    head = source.head;
}
template<class ElemType>
bool SimpleLinkList<ElemType>::Delete(int position, const ElemType& e) {
    if (position<1 || position>Length()) {
        return false;
    }
    else {
        Node<ElemType>* temptr = GetElemPtr(position - 1);
        Node<ElemType>* nextptr = temptr->next;
        e = nextptr->data;
        temptr->next = nextptr->next;
        delete nextptr;
        return true;
    }
}
template<class ElemType>
bool SimpleLinkList<ElemType>::Delete(int position) {
    if (position<1 || position>Length()) {
        return false;
    }
    else {
        Node<ElemType>* temptr = GetElemPtr(position - 1);
        Node<ElemType>* nextptr = temptr->next;
        temptr->next = nextptr->next;
        delete nextptr;
        return true;
    }
}
template<class ElemType>
SimpleLinkList<ElemType>& SimpleLinkList<ElemType>::operator=(const SimpleLinkList<ElemType>& source) {
    if (source->head == NULL) {
        head = NULL;
    }
    else {
        SimpleLinkList<ElemType>* nextptr(source->head);
        while (nextptr != NULL) {
            head->next = nextptr;
            nextptr = nextptr->next;
        }
    }
}
template<class ElemType>
bool SimpleLinkList<ElemType>::SetElem(int position, ElemType& e) {
    if (position<1 || position>Length()) {
        return false;
    }
    else {
        Node<ElemType>* temptr = GetElemPtr(position);
        temptr->data = e;
        return true;
    }

}

这篇关于C++的链表实现的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!