Реализация несвязанного множества C ++ с двусвязными списками

Может ли кто-нибудь помочь мне найти / сделать / направить меня в правильном направлении реализации несвязанного множества, использующей двусвязные списки? У меня есть некоторый дополнительный код, и я уже начал его редактировать, мне было интересно, может ли кто-нибудь помочь мне заполнить остальное или хотя бы дать мне несколько советов о том, как это сделать.

#pragma once

#include "TemplateDoublyLinkedList.h"#include <cstddef>
#include <iostream>
#include <vector>

using namespace std;

// Disjoint Set
template <typename T>
class DisjointSet {
private:
vector<DListNode<T>*> nodeLocator;
public:
~DisjointSet();
DisjointSet(int n) { nodeLocator.resize(n); }
vector<DListNode<T>*> getNodeLocator() const { return nodeLocator; }
DListNode<T>* MakeSet(int key, T node);
DListNode<T>* Union(DListNode<T> nodeI, DListNode<T> nodeJ);
DListNode<T>* FindSet(DListNode<T> node);
DListNode<T>* FindSet(int nodeKey);
};

template <typename T>
DListNode<T>* DisjointSet<T>::MakeSet(int key, T node)
{
DListNode<T> *temp = new DListNode(key, node);
nodeLocator.insert(nodeLocator.begin() + key - 1, temp);
return temp;
}template <typename T>
DListNode<T>* DisjointSet<T>::Union(DListNode<T> nodeI, DListNode<T> nodeJ){
if (nodeI.getListSize() >= nodeJ.getListSize())
{
nodeI.getTrailer()->setNext(nodeJ.getRepresentative());
nodeJ.getRepresentative()->setPrevious(nodeI.getTrailer());
nodeI.getRepresentative()->setTrailer(nodeJ.getTrailer());
nodeJ.getRepresentative()->setTrailer(NULL);
nodeJ.getRepresentative()->setRepresentative(nodeI.getRepresentative());
nodeI.setListSize(nodeI.getListSize()+nodeJ.getListSize());

return nodeI.getRepresentative();
}
else if (nodeI.getListSize() < nodeJ.getListSize())
{
nodeJ.getTrailer()->setNext(nodeI.getRepresentative());
nodeI.getRepresentative()->setPrevious(nodeJ.getTrailer());
nodeJ.getRepresentative()->setTrailer(nodeI.getTrailer());
nodeI.getRepresentative()->setTrailer(NULL);
nodeI.getRepresentative()->setRepresentative(nodeJ.getRepresentative());
nodeJ.setListSize(nodeI.getListSize() + nodeJ.getListSize());

return nodeJ.getRepresentative();
}
return NULL;
}

template <typename T>
DListNode<T>* DisjointSet<T>::FindSet(DListNode<T> node){

}

template <typename T>
DListNode<T>* DisjointSet<T>::FindSet(int nodeKey){
if (nodeLocator[nodeKey-1]) != NULL)
return nodeLocator[nodeKey-1];
else
return nullptr;
}

template <typename T>
ostream& DisjointSet<T>::operator<<(ostream& out, const DisjointSet<T>& ds){

}
#pragma once

#include <string>
#include <cstdlib>
#include <iostream>
#include <stdexcept>
using namespace std;

// list node
template <typename T>
class DListNode {
private:
friend class DisjointSet;
int key, listSize;
T obj;
DListNode *prev, *next, *representative;
DListNode *trailer; //just the representative node has this pointer assigned
public:
DListNode(int k, T e, DListNode *p = NULL, DListNode *n = NULL)
: key(k), obj(e), prev(p), next(n) { listSize = 1; }
T getElem() const { return obj; }
T& getElemt() { return obj; }
DListNode<T> * getNext() const { return next; }
DListNode<T> * getPrev() const { return prev; }
void setNext(DListNode* n) { this->next = n; }
void setPrevious(DListNode* p) { this->prev = p; }
DListNode<T>* insert_before(T d); // insert the int before this node
// return a pointer to the inserted node
DListNode<T>* insert_after(T d); // insert the int after this node
// return a pointer to the inserted node
void delete_before(); // delete the node before this node
void delete_after(); // delete the node after this node
int getKey() { return key; }
DListNode<T>* getRepresentative() const { return representative; }
DListNode<T>* getTrailer() const { return trailer; }
void setRepresentative(DListNode* rep);
void setTrailer(DListNode* trail);
int getListSize() { return this->getRepresentative()->listSize; }
void setListSize(int lSize)
{ this->listSize = lSize; if(this->next != NULL) this->next->setListSize(lSize); }
};

template <typename T>
void DListNode<T>::setRepresentative(DListNode* rep) {
this->representative = rep;
if (this->next != NULL)
{
this->next->setRepresentative(rep);
}
}

template <typename T>
void DListNode<T>::setTrailer(DListNode* trail) {
this->representative = trail;
}

template <typename T>
DListNode<T>* DListNode<T>::insert_before(T d) {
DListNode<T>* temp = new DListNode(d);  //temp pointer // 1 OPERATION

if(prev!= NULL){   //if previous is not null // 2 OPERATION
temp -> next = this;    //initialize next // 2 OPERATION
temp -> prev = prev;   //initialize previous // 2 OPERATION
prev -> next = temp;   // insert in the list  // 2 OPERATION
prev = temp;          // 1 OPERATION
}
else{       //if null than do a simple insert
temp -> next = this;  // 2 OPERATION
prev = temp;   // 1 OPERATION
}

return temp; // 1 OPERATION
}

template <typename T>
DListNode<T>* DListNode<T>::insert_after(T d) {
DListNode<T>* temp = new DListNode(d);   // 2 OPERATION
if(next != NULL){   //if next is not null do this // 2 OPERATION
temp -> next = next;      //initialize next and previous // 2 OPERATION
temp -> prev = this;     // 2 OPERATION
next -> prev = temp;   //make the connection to insert // 2 OPERATION
next = temp; // 1 OPERATION
}
else{ //if null than do a simple insert
temp -> prev = this;  // 2 OPERATION
next = temp; // 1 OPERATION
}

return temp;  // 1 OPERATION
}

template <typename T>
void DListNode<T>::delete_before() {
if(prev!= NULL){   //check if something is there  // 2 OPERATION
DListNode<T>* temp = prev;         // 1 OPERATION
temp -> prev-> next = temp-> next;    //change the interconnections  // 4 OPERATION
temp -> next -> prev = temp -> prev; // 4 OPERATION
delete temp;        //delete the element // 1 OPERATION
}
else{
cout << ">Error: Nothing is there :(" << endl;
}
}
template <typename T>
void DListNode<T>::delete_after() {
if(next != NULL){ //check if something is there
DListNode<T>* temp = next;  // 1 OPERATION
next -> prev = this; //change the interconnections // 2 OPERATION
next = next -> next; // 2 OPERATION
delete temp;  //delete the element // 1 OPERATION
}
else{
cout << ">Error: Nothing is there :(" << endl;
}

}

0

Решение

Задача ещё не решена.

Другие решения


По вопросам рекламы [email protected]