Как я могу решить ошибку «неопределенная ссылка» при реализации B_TREE (красное черное дерево) в качестве шаблона? ⇐ C++

Программы на C++. Форум разработчиков
Ответить
Anonymous
 Как я могу решить ошибку «неопределенная ссылка» при реализации B_TREE (красное черное дерево) в качестве шаблона?

Сообщение Anonymous »

Я реализую шаблон B_TREE (AKA Red Black, в следующем тексту будет использован класс B_TREE) с ISO C ++ 17. Вся программа содержит четыре файла: < /p>

Код: Выделить всё

B_tree.h

Код: Выделить всё

B_tree_main.cpp

Код: Выделить всё

B_tree_util.cpp

Код: Выделить всё

B_tree_debug.cpp
(не имеет значения к этой проблеме, просто игнорируйте ее) В b_tree_main.cpp программа будет вызовать функции, определенные и используемые в предыдущих, используя тип int , чтобы заменить тип шаблона. Команда компиляции следующим образом. < /P>

Код: Выделить всё

g++ B_tree_main.cpp B_tree_util.cpp -o output
< /code>
или < /p>
g++ -c B_tree_main.cpp
g++ -c B_tree_util.cpp
g++ B_tree_main.o B_tree_util.o -o output
Ошибки следующие. B_tree :: remove (int)
/usr/bin/ld: b_tree_main.cpp :(. Текст+0xda): неопределенная ссылка на b_tree :: get_rank (int)
/usr/bin/ld: b_tree_main.cpp :(. />/usr/bin/ld: b_tree_main.cpp :(. Текст+0x15c): неопределенная ссылка на b_tree :: lower_bound (int)
/usr/bin/ld: b_tree_main.cpp :(. /> < /blockquote>
В конце я предоставлю полные коды.

Код: Выделить всё

#ifndef _B_TREE_H_
#define _B_TREE_H_

#include
#include
#include

//#define __B_TREE_DEBUG

#define bro(x) (((x)->ftr->lc == (x)) ? ((x)->ftr->rc) : ((x)->ftr->lc))
#define islc(x) ((x) != NULL && (x)->ftr->lc == (x))
#define isrc(x) ((x) != NULL && (x)->ftr->rc == (x))

template
class B_tree{
protected:
struct Node;

Node* _root;
Node* _hot;

void init(T);
void connect34(Node*, Node*, Node*, Node*, Node*, Node*, Node*);
void solve_double_red(Node*);
void solve_double_black(Node*);
Node* find(T, const int);
Node* rfind(T, const int);
Node* findkth(int, Node*);
int find_rank(T, Node*);
#ifdef __B_TREE_DEBUG
void checkconnect(Node*);
void previs(Node*, int);
void invis(Node*, int);
void postvis(Node*, int);
#endif

public:
struct iterator;

B_tree(): _root(NULL), _hot(NULL) {}

int get_rank(T);
iterator insert(T);
bool remove(T);
int size();
bool empty();
iterator kth(int);
iterator lower_bound(T);
iterator upper_bound(T);

#ifdef __B_TREE_DEBUG
void vis();
void correctly_connected();
#endif
};

template
struct B_tree::Node{
T val;
bool rb_color;
Node* ftr;
Node* lc;
Node* rc;
int s;

Node(T v = T(), bool rb = true, Node* f = NULL, Node* l = NULL, Node* r = NULL, int ss = 1)
: val(v), rb_color(rb), ftr(f), lc(l), rc(r), s(ss) {}

Node* successor(){
Node* ptn = rc;
while(ptn->lc != NULL){
--(ptn->s);
ptn = ptn->lc;
}
return ptn;
}

Node* left_node(){
Node* ptn = this;
if(!lc){
while(ptn->ftr && ptn->ftr->lc == ptn)
ptn = ptn->ftr;
ptn = ptn->ftr;
}
else{
ptn = ptn->lc;
while(ptn->rc){
ptn = ptn->lc;
while(ptn->lc){
ptn = ptn->rc;
}
}
}
return ptn;
}

Node* right_node(){
Node* ptn = this;
if(!rc) {
while(ptn->ftr && ptn->ftr->rc == ptn)
ptn = ptn->ftr;
ptn = ptn->ftr;
} else {
ptn = ptn->rc;
while(ptn->lc) {
ptn = ptn->lc;
}
}
return ptn;
}

void maintain(){
s = 1;
if(lc) s += lc->s;
if(rc) s += rc->s;
}
};

template
struct B_tree::iterator{
private:
Node* _real__node;

public:
iterator& operator++(){
_real__node = _real__node->right_node();
return *this;
}

iterator& operator--(){
_real__node = _real__node->left_node();
return *this;
}

T operator*(){
return _real__node->val;
}

iterator(Node* node_nn = NULL):
_real__node(node_nn) {}
iterator(T const& val_vv):
_real__node(rfind(val_vv, 0)) {}
iterator(iterator const&  iter):
_real__node(iter._real__node) {}
};

#endif
b_tree_util.cpp

Код: Выделить всё

#include "B_tree.h"

#ifdef __B_TREE_DEBUG
extern int black_height;
#endif

template
typename B_tree::iterator
B_tree::insert(T v){
Node* ptn = find(v, 1);
if(_hot == NULL){
init(v);
return iterator(_root);
}
ptn = new Node(v, true, _hot, NULL, NULL, 1);
if(_hot->val rc = ptn;
else
_hot->lc = ptn;
solve_double_red(ptn);
return iterator(ptn);
}

template
void B_tree::init(T v){
_root = new Node(v, false, NULL, NULL, NULL, 1);
#ifdef __B_TREE_DEBUG
++black_height;
#endif
}

template
typename B_tree::Node*
B_tree::find(T v, const int op){
Node* ptn = _root;
_hot = NULL;
while(ptn != NULL){
_hot = ptn;
ptn->s += op;
if(ptn->val > v){
ptn = ptn->lc;
}
else
ptn = ptn->rc;
}
return ptn;
}

template
typename B_tree::Node*
B_tree::rfind(T v, const int op){
Node* ptn = _root;
_hot = NULL;
while(ptn != NULL && ptn->val != v){
_hot = ptn;
ptn->s += op;
if(ptn->val > v)
ptn = ptn->lc;
else
ptn = ptn->rc;
}
return ptn;
}

template
void B_tree::solve_double_red(Node* nn){
while((!(nn->ftr)) || nn->ftr->rb_color){
if(nn == _root){
_root->rb_color = false;
#ifdef __B_TREE_DEBUG
++black_height;
#endif
return;
}
Node* pftr = nn->ftr;
if(!(pftr->rb_color))
return;
Node* uncle = bro(nn->ftr);
Node* grdftr = nn->ftr->ftr;
if(uncle != NULL &&  uncle->rb_color){
grdftr->rb_color = true;
uncle->rb_color = false;
pftr->rb_color = false;
nn = grdftr;
}
else{
if(islc(pftr)){
if(islc(nn)){
pftr->ftr = grdftr->ftr;
if(grdftr == _root) _root = pftr;
else if(grdftr->ftr->lc == grdftr) grdftr->ftr->lc = pftr;
else grdftr->ftr->lc = pftr;
connect34(pftr, nn, grdftr, nn->lc, nn->rc, pftr->rc, uncle);
pftr->rb_color = false;
}
else{
nn->ftr = grdftr->ftr;
if(grdftr == _root) _root = nn;
else if(grdftr->ftr->lc == grdftr) grdftr->ftr->lc = nn;
else grdftr->ftr->rc = nn;
connect34(nn, pftr, grdftr, pftr->lc, nn->lc, nn->rc, uncle);
nn->rb_color = false;
grdftr->rb_color = true;
}
}
else{
if(islc(nn)) {
nn->ftr = grdftr->ftr;
if(grdftr == _root) _root = nn;
else if(grdftr->ftr->lc == grdftr) grdftr->ftr->lc = nn;
else grdftr->ftr->rc = nn;
connect34(nn, grdftr, pftr, uncle, nn->lc, nn->rc, pftr->rc);
nn->rb_color = false;
grdftr->rb_color = true;
} else {
pftr->ftr = grdftr->ftr;
if(grdftr == _root) _root = pftr;
else if(grdftr->ftr->lc == grdftr) grdftr->ftr->lc = pftr;
else grdftr->ftr->rc = pftr;
connect34(pftr, grdftr, nn, uncle, pftr->lc, nn->lc, nn->rc);
pftr->rb_color = false;
grdftr->rb_color = true;
}
}
return;
}
}
}

/*
Function: connect34
Description: Unified re-balance rotate function
Param:

*/
template
void B_tree::connect34(Node* nroot, Node* nlc, Node* nrc,
Node* ntree1, Node* ntree2, Node* ntree3, Node* ntree4){
nlc->lc = ntree1;
if(ntree1 != NULL) ntree1->ftr = nlc;
nlc->rc = ntree2;
if(ntree2 != NULL) ntree2->ftr = nlc;
nrc->lc = ntree3;
if(ntree3 != NULL) ntree3->ftr = nrc;
nrc->rc = ntree4;
if(ntree4 != NULL) ntree4->ftr = nrc;
nroot->lc = nlc;
nlc->ftr = nroot;
nroot->rc = nrc;
nrc->ftr = nroot;
nlc->maintain();
nrc->maintain();
nroot->maintain();
}

template
typename B_tree::iterator
B_tree::lower_bound(T v){
Node* ptn = _root;
while(ptn){
_hot = ptn;
if(ptn->val < v){
ptn = ptn->rc;
}
else{
ptn = ptn->lc;
}
}
if(_hot->val < v){
ptn = _hot;
}
else{
ptn = _hot->left_node();
}
return iterator(ptn);
}

template
typename B_tree::iterator
B_tree::upper_bound(T v){
Node* ptn = _root;
while(ptn){
_hot = ptn;
if(ptn->val > v){
ptn = ptn->lc;
}
else{
ptn = ptn->rc;
}
}
if(_hot->val >  v){
ptn = _hot;
}
else{
ptn = _hot->right_node();
}
return iterator(ptn);
}

template
typename B_tree::iterator
B_tree::kth(int rank){
return iterator(findkth(rank, _root));
}

template
typename B_tree::Node* B_tree::findkth(int rank, Node* ptn){
if(!(ptn->lc)){
if(rank == 1){
return ptn;
}
else{
return findkth(rank - 1, ptn->rc);
}
}
else{
if(ptn->lc->s == rank - 1) return ptn;
else if(ptn->lc->s >= rank) return findkth(rank, ptn->lc);
else return findkth(rank - (ptn->lc->s) - 1, ptn->rc);
}
}

template
int B_tree::get_rank(T v){
return find_rank(v, _root);
}

template
int B_tree::find_rank(T v, Node* ptn){
if(!ptn) return 1;
else if(ptn->val >= v) return find_rank(v, ptn->lc);
else return (1 + ((ptn->lc) ? (ptn->lc->s) : 0) + find_rank(v, ptn->rc));
}

template
int B_tree::size(){
return _root->s;
}

template
bool B_tree::empty(){
return !_root;
}

template
bool B_tree::remove(T v){
Node* ptn = rfind(v, -1);
if(!ptn) return false;
Node* node_suc;
while(ptn->lc || ptn->rc){
if(!(ptn->lc)){
node_suc = ptn->rc;
}
else if(!(ptn->rc)){
node_suc = ptn->lc;
}
else{
node_suc = ptn->successor();
}
--(ptn->s);
ptn->val = node_suc->val;
ptn = node_suc;
}
if(!(ptn->rb_color)){
--(ptn->s);
solve_double_black(ptn);
}
if(ptn == _root){
_root = NULL;
delete ptn;
return true;
}
if(ptn->ftr->lc == ptn)
ptn->ftr->lc = NULL;
else
ptn->ftr->rc = NULL;
delete ptn;
return true;
}

template
void B_tree::solve_double_black(Node* nn){
while(nn != _root){
Node* pftr = nn->ftr;
Node* bthr = bro(nn);
if(bthr->rb_color){
bthr->rb_color = false;
bthr->rb_color = true;
if(_root == pftr) _root = bthr;
if(pftr->ftr){
if(pftr->ftr->lc == pftr)
pftr->ftr->lc = bthr;
else
pftr->ftr->rc = bthr;
}
bthr->ftr = pftr->ftr;
if(islc(nn)){
connect34(bthr, pftr, bthr->rc, nn, bthr->lc, bthr->rc->lc, bthr->rc->rc);
}
else{
connect34(bthr, bthr->lc, pftr, bthr->lc->lc, bthr->lc->rc, bthr->rc, nn);
}
bthr = bro(nn);
pftr = nn->ftr;
}
if(bthr->lc &&  bthr->lc->rb_color){
bool old_rb_color = pftr->rb_color;
pftr->rb_color = false;
if(pftr->lc == nn){
if(pftr->ftr) {
if(pftr->ftr->lc == pftr)
pftr->ftr->lc = bthr->lc;
else
pftr->ftr->rc = bthr->lc;
}
bthr->lc->ftr = pftr->ftr;
if(_root == pftr) _root = bthr->lc;
connect34(bthr->lc, pftr, bthr, pftr->lc, bthr->lc->lc, bthr->lc->rc, bthr->rc);
}
else {
bthr->lc->rb_color = false;
if(pftr->ftr) {
if(pftr->ftr->lc == pftr)
pftr->ftr->lc = bthr;
else
pftr->ftr->rc = bthr;
}
bthr->ftr = pftr->ftr;
if(_root == pftr) _root = bthr;
connect34(bthr, bthr->lc, pftr, bthr->lc->lc, bthr->lc->rc, bthr->rc, pftr->rc);
}
pftr->ftr->rb_color = old_rb_color;
return;
}
else if(bthr->rc && bthr->rc->rb_color) {   ////BB-3
bool old_rb_color = pftr->rb_color;
pftr->rb_color = false;
if(pftr->lc == nn) {
bthr->rc->rb_color = false;
if(pftr->ftr) {
if(pftr->ftr->lc == pftr)
pftr->ftr->lc = bthr;
else
pftr->ftr->rc = bthr;
}
bthr->ftr = pftr->ftr;
if(_root == pftr) _root = bthr;
connect34(bthr, pftr, bthr->rc, pftr->lc, bthr->lc, bthr->rc->lc, bthr->rc->rc);
} else {
if(pftr->ftr) {
if(pftr->ftr->lc == pftr)
pftr->ftr->lc = bthr->rc;
else
pftr->ftr->rc = bthr->rc;
}
bthr->rc->ftr = pftr->ftr;
if(_root == pftr) _root = bthr->rc;
connect34(bthr->rc, bthr, pftr, bthr->lc, bthr->rc->lc, bthr->rc->rc, pftr->rc);
}
pftr->ftr->rb_color = old_rb_color;
return;
}
if(pftr->rb_color) {                    ////BB-2R
pftr->rb_color = false;
bthr->rb_color = true;
return;
} else {                        ////BB-2B
bthr->rb_color = true;
nn = pftr;
}
}
#ifdef __REDBLACK_DEBUG
--blackheight;
#endif
}
b_tree_main.cpp

Код: Выделить всё

#include
#include "B_tree.h"

inline int readint(){
int ret(0);
int sgn(1);
char c;
while(isspace(c = getchar()));
if(c == '-') {
sgn = -1;
c = getchar();
}
while(isdigit(c)) {
ret = (ret 

Подробнее здесь: [url]https://stackoverflow.com/questions/79767929/how-can-i-solve-the-undefined-reference-error-when-implementing-b-treered-bla[/url]
Вернуться к началу
Ответить

Быстрый ответ

Изменение регистра текста: 
Смайлики
:) :( :oops: :roll: :wink: :muza: :clever: :sorry: :angel: :read: *x)
Ещё смайлики…
   
К этому ответу прикреплено по крайней мере одно вложение.

Если вы не хотите добавлять вложения, оставьте поля пустыми.

Максимально разрешённый размер вложения: 15 МБ.

Вернуться в «C++»