补全代码!
2024-09-16 14:37:31
发布于:广东
提示:这个项目是用链表模拟sort函数排序
#include <iostream>
#include <cstdio>
using namespace std;
struct node{
int val;
node *pre = nullptr, *next = nullptr;
}*head, *r;
struct heap{
int val = -1;
heap *pre = nullptr, *next = nullptr, *father = nullptr, *son1 = nullptr, *son2 = nullptr;
}*top, *bottom;
node *f(node *left, node *right){
int pivot = left -> val;
while(left != right){
while(left != right && (right -> val) >= pivot) right = right -> ___;
___ -> val = ___ -> val;
while(left != right && (___ -> val) <= pivot) ___ = ___ -> ___;
___ -> val = ___ -> val;
}
left -> val = pivot;
return left;
}
void f1(node *n){
if(top -> val == -1){
top -> val = n -> val;
return;
}
heap *p = new heap;
p -> val = n -> val;
bottom -> next = p, p -> pre = bottom;
if(top == bottom){
p -> father = top, top -> son1 = p;
}else{
if(bottom -> father -> son2 != nullptr){
p -> father = bottom -> father -> next;
bottom -> father -> next -> son1 = p;
}else{
p -> father = bottom -> father;
bottom -> father -> son2 = p;
}
}
bottom = p;
while(p != top && p -> ___ -> val >= p -> val){
swap(p -> val, p -> ___ -> val);
p = p -> ___;
}
}
int f2(){
int val = top -> val;
if(bottom == top){
top -> val = -1;
return val;
}
top -> val = bottom -> val;
if(bottom -> father -> son1 == bottom) bottom -> father -> son1 = nullptr;
else bottom -> father -> son2 = nullptr;
bottom = bottom -> pre;
delete bottom -> next;
bottom -> next = nullptr;
heap *p = top;
while(p -> son1 != nullptr){
heap *p2 = p -> son1;
if(p -> son2 != nullptr && p2 -> val > p -> ___ -> val) p2 = p -> ___;
if(p -> ___ <= p2 -> ___) return val;
swap(p -> ___, p2 -> ___);
p = p2;
}
return val;
}
void sort(node *left, node *right, int ct){
if(left == right || right -> next == left) return;
if(ct >= 30){
for(node *p = ___; p != ___; p = p -> next){//选填left,right
f1(p);
}f1(right);
for(node *p = ___; p != ___; p = p -> next){
p -> val = f2();
}right -> val = f2();
return;
}
node *i = f(left, right);
sort(left, i -> ___, ct + 1), sort(i -> ___, right, ct + 1);
}
int main(){
r = head = new node, bottom = top = new ___;
int n;
cin >> n;
for(int i = 1; i <= n; i++){
node *p = new node;
cin >> p -> val;
r -> next = p, p -> pre = r;
r = p;
}
sort(___ -> ___, r, 1);
node *p = head;
while(p -> next != nullptr){
p = p -> next;
cout << p -> ___ << ' ';
}
return 0;
}
全部评论 5
顶
2天前 来自 广东
0我有三不写
2天前 来自 上海
0啊?
2天前 来自 上海
0就改了十几个变量不算难把
2天前 来自 广东
0顶
2天前 来自 广东
0顶
2天前 来自 广东
0
有帮助,赞一个