链表相关操作集

2020-10-09

循环双向链表

本次数据结构进行了双向链表的学习，并在链表中增加了哑元节点，哑元节点的加入使得链表的插入和删除得到了简化，不用再去判断删除或插入的是否在链首。
并在问题中，运用了双向循环列表解决约瑟夫问题，N个人围成一圈，从第一个开始报数，第3个将被杀掉，最后剩下一个，其余人都将被杀掉,直到找到最后一个。
push函数实现了链表的循环，每增加一个元素，将其的prev与前元素相连，next与first相连，实现循环。

#include <iostream>
using namespace std;
class dnode//结点的定义
{
public:
    int nodeValue;
    dnode* prev;
    dnode* next;
    dnode() {
        next = this;
        prev = this;
    }
    dnode(const int& value) : nodeValue(value) {
        next = this;
        prev = this;
    }
};
class list {//双向链表的定义
public:
    dnode* first = new dnode();
    list() ;
    ~list();
    void clear(dnode* p);//删除一个结点
    void push(int i);//将元素添加到链表
    void insert(int i, int x);//插入操作
    void erase(int i);//删除操作
};
list::list() {
    first->next = first;
    first->prev = first;
}
void list::clear(dnode* p) {//删除节点
    dnode* t = p->prev;
    t->next = p->next;
    p->next->prev = t;//将两个结点前后相连
    delete p;
}
list::~list() {
dnode* p = first;
while (p->next != p)
{
    p = p->next;
    dnode* f = p->prev;
    clear(f);//删除节点
}
delete p;
}
void list::push(int i) {
    dnode* n = new dnode(i);
    dnode* p = first->prev;
    n->prev = p;
    n->next = first;
    p->next = n;
    first->prev = n;
}//双向循环链表
void list::insert(int i, int x) {
    dnode n(x);
    dnode* p = first;
    for (int j = 0; j < i; j++) {//找到第i个元素
        if (p->next == first)p = p->next;
        p = p->next;
    }
    dnode* t = p->prev;
    n.next = p;
    n.prev = t;
    t->next = &n;
    p->prev = &n;//前后链接
}
void list::erase(int i) {
    dnode* p = first;
    for (int j = 0; j < i; j++) {//找到第i个元素
        if (p->next == first)p = p->next;
        p = p->next;
    }
    dnode* t = p->prev;
    t->next = p->next;
    p->next->prev = t;//将第i个元素前后的元素链接
    delete p;
}
int main() {
    list l;
    dnode* p = l.first;
    l.push(12);
    l.push(38);
    l.push(42);
    l.push(21);
    l.erase(3);
    for (int i = 0; i < 3; i++) {
        p = p->next;
        cout << p->nodeValue << endl;
    }
    cout<<"约瑟夫环问题求解："<<endl;
    list l1;
    for (int i = 1; i <= 41; i++) {
        l1.push(i);
    }
    dnode* d = l1.first->next;//从链表有元素的位置开始
    while (l1.first->next->next!=l1.first) {//只剩下一个元素的时候停止循环
        for (int i = 0; i < 3; i++) {
            if (d->next == l1.first)d = d->next;//循环回去之后要走两格
            d = d->next;
        }
        dnode* n = d->prev;
        if (n == l1.first) {
            n = n->prev;
        }//转达最末尾的元素
        dnode* p1 = n->prev;
        dnode* p2 = n->next;
        p2->prev = p1;
        p1->next = p2;
        delete n;
    }
    cout << "the last one is:" << d->nodeValue << endl;
}