C++ 类模版:带表头链表的实现

链表的概念

链表是常用的基本数据结构之一,属于线性表。同属于线性表的还有顺序表,我们常说的数组就是顺序表。

带表头链表

链表的实现有带表头和不带表头两种方式。最原始的方式,也就是不带表头的实现方式,是用一个指向头结点的指针变量来记录链表的起始位置,当我们要进行插入或删除结点的操作时,必须要针对第一个结点和其它结点做出不同判断,然后用不同的代码来分别处理这两种情况。

所谓带表头的实现方式,就是用一个空的结点来作为头结点,其data域不放数据,其next指针指向第一个存有数据的结点。这样的好处是:每一个数据结点都有相同类型的前驱结点,不管在哪个位置实现操作,都能用统一的形式来表述,即可以用同样的代码来实现,而无需判断是在链表的起始位置、中间位置或者尾部位置。

实现思路

我们将实现链表类的几个基本方法:

  • 添加结点(至链表末尾)
  • 插入结点(至任意位置)
  • 删除结点
  • 查找结点
  • 获取链表长度
  • 获取结点数据
  • 排序

链表类Linklist的定义部分

template <typename ElemType>
class Linklist {
    private:
        struct Node{
            ElemType data;
            Node* next;
            Node():next(nullptr){};
            Node(ElemType data, Node* next = nullptr):
                data(data), next(next){};
        };
        Node Head;

    public:
        Linklist() {};
        ~Linklist();

        void append(ElemType data);
        void insert(ElemType data, int pos = 0);
        bool del(int pos);
        int  search(ElemType data);
        int  getLength();
        ElemType getData(int pos);
        void sort(int(*compare)(ElemType& a, ElemType& b));
};

Linklist的实现部分

template <typename ElemType>
Linklist<ElemType>::~Linklist() {
    Node *ptr = &Head;
    Node *t = nullptr;

    while(ptr->next != nullptr) {
        t = ptr->next;
        ptr->next = t->next;
        delete t;
    }
}

template <typename ElemType>
void Linklist<ElemType>::append(ElemType data) {
    Node *ptr = &Head;

    while(ptr->next != nullptr) {
        ptr = ptr->next;
    }
    ptr->next = new Node(data);
}

/* 当插入位置大于链表长度时,将元素插到链表末尾 */
template <typename ElemType>
void Linklist<ElemType>::insert(ElemType data, int pos) {
    Node *ptr = &Head;
    int p = 0;

    while(ptr->next != nullptr)
    {
        if(p == pos) break;
        p++;
        ptr = ptr->next;
    }
    ptr->next = new Node(data, ptr->next);
}

template <typename ElemType>
bool Linklist<ElemType>::del(int pos) {
    Node *ptr = &Head;
    Node *t = nullptr;
    int p = 0;

    while(ptr->next != nullptr) {
        if(p == pos) break;
        p++;
        ptr = ptr->next;
    }

    if(p == pos) {
        t = ptr->next;
        ptr->next = t->next;
        delete t;
        return true;
    } else {
        return false;
    }

}

/* 成功找到元素则返回索引,否则返回-1 */
template <typename ElemType>
int Linklist<ElemType>::search(ElemType data) {
    Node *ptr = &Head;
    int p = 0;

    while(ptr->next != nullptr) {
        if(ptr->next->data == data) {
            return p;
        }
        p++;
        ptr = ptr->next;
    }
    return -1;
}

template <typename ElemType>
int Linklist<ElemType>::getLength() {
    Node *ptr = &Head;
    int p = 0;

    while(ptr->next != nullptr) {
        p++;
        ptr = ptr->next;
    }

    return p;
}

template <typename ElemType>
ElemType Linklist<ElemType>::getData(int pos) {
    Node *ptr = &Head;
    int p = 0;

    while(ptr->next != nullptr) {
        if(p == pos) break;
        p++;
        ptr = ptr->next;
    }

    return ptr->next->data;
}

/* 排序函数需要一个返回值为int型的比较函数作为参数
*  升序排列:当a>b时,令compare(a, b)的返回值大于0
*  降序排列:当a<b时,令compare(a, b)的返回值大于0
*  注意:当a=b时,compare(a, b)的返回值必须小于或等于0。
*/
template <typename ElemType>
void Linklist<ElemType>::sort(int(*compare)(ElemType& a, ElemType& b)) {
    Node *ptr;
    Node *t;
    int tmp;
    bool sorted = false;

    while(!sorted) {
        sorted = true;
        ptr = &Head;
        t = ptr->next;
        while(ptr->next != nullptr && t->next != nullptr) {
            tmp = compare(t->data, t->next->data);
            if(tmp > 0) {
                ptr->next = t->next;
                t->next = ptr->next->next;
                ptr->next->next = t;
                sorted = false;
            }
            ptr = t;
            t = t->next;
        }
    }
}

相关文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注