class qListNode {
public:
int data;
qListNode* pred, * succ, * above, * below;
qListNode() { data = 0; pred = succ = above = below = nullptr; }
qListNode(int d, qListNode* p, qListNode* s, qListNode* a = nullptr, qListNode* b = nullptr) {
data = d;
pred = p; succ = s; above = a; below = b;
}
qListNode* q_insertAferAbove(int d, qListNode* pred, qListNode* below = nullptr);
};
class qList {
public:
int _size;
qList();
qListNode* header, * trailer;
qList* last, * next;
void print();
qListNode* ql_insertAsFirst(int d);
qListNode* ql_first();
bool ql_valid(qListNode* p);
bool ql_empty();
bool ql_remove(qListNode* p);
};
class List :public qList {
public:
int _size;
List();
qList* header, * trailer;
qList* first();
bool valid(qList* p);
bool empty();
bool remove(qList* qlist);
bool insertAsFirst(qList* qlist);
void find(qList*& qlist, qListNode*& p, int target);
};
qListNode* qListNode::q_insertAferAbove(int d, qListNode* pred, qListNode* below)
{
qListNode* x = new qListNode(d, this, this->succ, nullptr, below);
succ->pred = x;
succ = x;
if (below)below->above = x;
return x;
}
qList::qList()
{
_size = 0;
header = new qListNode(); trailer = new qListNode();
header->succ = trailer; trailer->succ = nullptr;
header->pred = nullptr; trailer->pred = header;
last = next = nullptr;
}
void qList::print()
{
qListNode* x = header->succ;
while (x->succ) { cout << x->data << " "; x = x->succ; }
}
qListNode* qList::ql_insertAsFirst(int d)
{
++_size;
qListNode* x = new qListNode(d, header, header->succ);
header->succ = x; x->succ->pred = x;
return x;
}
qListNode* qList::ql_first()
{
return header->succ;
}
bool qList::ql_valid(qListNode* p)
{
return p && (p->pred) && (p->succ);
}
bool qList::ql_empty()
{
return _size <= 0;
}
bool qList::ql_remove(qListNode* p)
{
if (!ql_valid(p))return false;
p->pred->succ = p->succ;
p->succ->pred = p->pred;
delete p;
return true;
}
List::List()
{
header = new qList; trailer = new qList;
header->next = trailer; trailer->next = nullptr;
header->last = nullptr; trailer->last = header;
_size = 0;
}
qList* List::first()
{
if (valid(header->next))
return header->next;
return nullptr;
}
bool List::valid(qList* p)
{
return p && (p != header) && (p != trailer);
}
bool List::empty()
{
return _size <= 0;
}
bool List::remove(qList* qlist)
{
if (!qlist)return false;
--_size;
qlist->last->next = qlist->next;
qlist->next->last = qlist->last;
delete qlist;
return true;
}
bool List::insertAsFirst(qList* qlist)
{
if (!qlist)return false;
qlist->next = header->next;
header->next = qlist;
qlist->last = header;
qlist->next->last = qlist;
++_size;
return true;
}
void List::find(qList*& qlist, qListNode*& p, int target)
{
while (1)
{
while (ql_valid(p) && p->data <= target)p = p->succ;
p = p->pred;
if (ql_valid(p) && p->data == target)return;
qlist = qlist->next;
if (!(qlist->next))
{
qlist = qlist->last;
return;
}
p = ql_valid(p) ? p->below : qlist->ql_first();
}
}
class Skiplist :public List {
public:
Skiplist() {
};
bool add(int num);
bool erase(int num);
bool search(int num);
};
bool Skiplist::add(int num)
{
if (empty()) {
qList* temp = new qList;
insertAsFirst(temp);
}
qList* qlist = first();
qListNode* p = qlist->ql_first();
find(qlist, p, num);
if (qlist->ql_valid(p)&&p->data == num)
while (p->below)p = p->below;
qlist = trailer->last;
qListNode* b = p->q_insertAferAbove(num, p);
while (rand() &1 ) {
while (p->pred&&!(p->above))p = p->pred;
if (!ql_valid(p)) {
if (qlist == first()) {
qList* temp = new qList;
insertAsFirst(temp);
}
p = qlist->last->ql_first();
}
else p = p->above;
qlist = qlist->last;
if (!(qlist->ql_valid(p)))
{
qListNode* temp=qlist->ql_insertAsFirst(num);
temp->below=b;
b = temp;
}
else b=p->q_insertAferAbove(num, p, b);
}
return true;
}
bool Skiplist::erase(int num)
{
if (empty())return true;
qList* qlist = first();
qListNode* p = qlist->ql_first();
find(qlist, p, num);
if (!ql_valid(p) || p->data != num)return false;
do {
qListNode* temp = p->below;
qlist->ql_remove(p);
p = temp; qlist = qlist->next;
} while (qlist->next);
while (!empty() && first()->ql_empty())
remove(first());
return true;
}
bool Skiplist::search(int num)
{
qList* qlist = first();
qListNode* p = qlist->ql_first();
find(qlist, p, num);
if (!ql_valid(p))return false;
if (p->data == num)return true;
return false;
}
测试用例
["Skiplist","add","add","add","add","add","add","add","add","add","erase","search","add","erase","erase","erase","add","search","search","search","erase","search","add","add","add","erase","search","add","search","erase","search","search","erase","erase","add","erase","search","erase","erase","search","add","add","erase","erase","erase","add","erase","add","erase","erase","add","add","add","search","search","add","erase","search","add","add","search","add","search","erase","erase","search","search","erase","search","add","erase","search","erase","search","erase","erase","search","search","add","add","add","add","search","search","search","search","search","search","search","search","search"]
[[],[16],[5],[14],[13],[0],[3],[12],[9],[12],[3],[6],[7],[0],[1],[10],[5],[12],[7],[16],[7],[0],[9],[16],[3],[2],[17],[2],[17],[0],[9],[14],[1],[6],[1],[16],[9],[10],[9],[2],[3],[16],[15],[12],[7],[4],[3],[2],[1],[14],[13],[12],[3],[6],[17],[2],[3],[14],[11],[0],[13],[2],[1],[10],[17],[0],[5],[8],[9],[8],[11],[10],[11],[10],[9],[8],[15],[14],[1],[6],[17],[16],[13],[4],[5],[4],[17],[16],[7],[14],[1]]
结果是正确的
但是提交以后报错
=================================================================
==42==ERROR: AddressSanitizer: heap-use-after-free on address 0x604000003418 at pc 0x00000034e472 bp 0x7ffe72c4ee00 sp 0x7ffe72c4edf8