list - 如何为双向链表编写堆排序?C++
问题描述
我需要为双向链表编写堆排序,但我无法实现该算法。你能帮助我吗?
解决方案
谢谢大家 - 有这样一个工作代码用于双向链表的堆排序 - 工作。也许以后有人会需要它
void List::heap_sort(int n) {
Node* temp = Head;
for (int i = n / 2 - 1; i >= 0; i--)
heapify(temp, n, i);
//По очереди извлекаем элементы из кучи
for (int i = n - 1; i >= 0; i--)
{
swap(0, i, temp);
heapify(temp, i, 0);
}
}
void List::heapify(Node* temp, int n, int i) {
// Инициализация большего элемента, как корня
int largest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
Node* largesti = temp;
for (int k = 0; k < largest; k++) {
largesti = largesti->Next;
}
Node* li = temp;
for (int k = 0; k < l; k++) {
if (li == NULL)
break;
li = li->Next;
}
Node* ri = NULL;
if (li != NULL) ri = li->Next;
// Если правый потомок больше корня
if (li != NULL)
if (l < n && li->x > largesti->x) {
largest = l;
largesti = li;
}
// Если правый потомок до сих пор самый большой
if (ri != NULL)
if (r < n && ri->x > largesti->x)
largest = r;
// Если largest не является корнем
if (largest != i)
{
swap(i, largest, temp);
// Формируем дерево
heapify(temp, n, largest);
}
}
void List::swap(int i, int k, Node* swapList) {
Node* temp1 = swapList, * temp2 = swapList;
for (int j = 0; j < i; j++) {
temp1 = temp1->Next;
}
for (int j = 0; j < k; j++) {
temp2 = temp2->Next;
}
int number = temp1->x;
temp1->x = temp2->x;
temp2->x = number;
}
完整代码:
#include <iostream>
#include <fstream>
using namespace std;
struct Node
{
int x;
Node* Next, * Prev;
};
class List
{
//Указатели на адреса начала списка и его конца
Node* Head, * Tail;
public:
//Инициализируем адреса как пустые
List() :Head(NULL), Tail(NULL) {};
~List();
void show();
void output_to_file(int c);
void add(double x);
void bubble_sort();
void heap_sort(int n);
void swap(int i, int k, Node* swapList);
void heapify(Node* temp, int n, int i);
};
void List::add(double x)
{
//Выделение памяти под новый элемент структуры
Node* temp = new Node;
//Указываем, что изначально по следующему адресу пусто
temp->Next = NULL;
temp->x = x;
if (Head != NULL)
{
temp->Prev = Tail;
Tail->Next = temp;
Tail = temp;
}
else
{
temp->Prev = NULL;
Head = Tail = temp;
}
}
void List::show()
{
//Временно указываем на адрес первого элемента
Node* temp = Head;
//Пока не встретим пустое значение
while (temp != NULL)
{
cout << temp->x << " ";
temp = temp->Next;
}
}
void List::output_to_file(int c)
{
ofstream fout;
fout.open("output.txt");
if (fout.is_open()) {
Node* temp = Head;
fout << c << " ";
while (temp != Tail)
{
fout << temp->x << " ";
temp = temp->Next;
}
fout << temp->x;
}
else
cout << "Output file doesnt exist";
}
void List::bubble_sort() {
//Первый элемент — это пусть будет голова
Node* left = Head;
//Второй элемент — это пусть будет следующий за головой элемент
Node* right = Head->Next;
Node* temp = new Node;
while (left->Next) {
while (right) {
if ((left->x) > (right->x)) {
temp->x = left->x;
left->x = right->x;
right->x = temp->x;
}
right = right->Next;
}
left = left->Next;
right = left->Next;
}
}
void List::heap_sort(int n) {
Node* temp = Head;
for (int i = n / 2 - 1; i >= 0; i--)
heapify(temp, n, i);
//По очереди извлекаем элементы из кучи
for (int i = n - 1; i >= 0; i--)
{
swap(0, i, temp);
heapify(temp, i, 0);
}
}
void List::heapify(Node* temp, int n, int i) {
// Инициализация большего элемента, как корня
int largest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
Node* largesti = temp;
for (int k = 0; k < largest; k++) {
largesti = largesti->Next;
}
Node* li = temp;
for (int k = 0; k < l; k++) {
if (li == NULL)
break;
li = li->Next;
}
Node* ri = NULL;
if (li != NULL) ri = li->Next;
// Если правый потомок больше корня
if (li != NULL)
if (l < n && li->x > largesti->x) {
largest = l;
largesti = li;
}
// Если правый потомок до сих пор самый большой
if (ri != NULL)
if (r < n && ri->x > largesti->x)
largest = r;
// Если largest не является корнем
if (largest != i)
{
swap(i, largest, temp);
// Формируем дерево
heapify(temp, n, largest);
}
}
void List::swap(int i, int k, Node* swapList) {
Node* temp1 = swapList, * temp2 = swapList;
for (int j = 0; j < i; j++) {
temp1 = temp1->Next;
}
for (int j = 0; j < k; j++) {
temp2 = temp2->Next;
}
int number = temp1->x;
temp1->x = temp2->x;
temp2->x = number;
}
List::~List()
{
while (Head)
{
Tail = Head->Next;
delete Head;
Head = Tail;
}
}
void adder(List &lst,int &b) {
ifstream fin("input.txt");
double k;
fin >> b;
while (fin >> k) {
lst.add(k);
}
}
int main()
{
ifstream fin;
List lst;
int b;
double k;
int c = 0;
fin.open("input.txt");
if (fin.is_open()) {
//counting the numbers of elements in file
while (fin >> k) {
c++;
}
fin.close();
fin.open("input.txt");
if (fin.is_open()) {
adder(lst, b);
lst.show();
if (b == 0)
lst.heap_sort(c - 1);
else
lst.bubble_sort();
cout << endl;
lst.show();
lst.output_to_file(c - 1);
}
else
cout << "Input file doesnt exist";
}
else
cout << "Input file doesnt exist";
return 0;
}
推荐阅读
- python - VS Code 未注册已安装 ipykernel
- git - 带有 Github 操作模式的 Terraform
- if-statement - 关于如何创建这个 if 公式的问题
- typescript - 错误:类可分配给类型“T”的约束,但可以使用约束类的不同子类型来实例化“T”
- ios - 无法调试。在 react native 中找不到 plist 文件来配置调试?
- python - Django:@login_required 装饰器不会重定向到“下一个”
- mysql - 有条件地从一对多关系中选择一行
- python - 如何在保持帧尺寸标签的同时将训练数据集帧转换为 5d 张量?
- php - 为什么我的网站上没有设置 cookie
- python - Pip 没有缓存所有已安装的包