So I've got this non-circular doubly linked list sample and I find it rather hard to transfer it to a circular one. (segfaulting on the //added lines) Any advise would be nice. Thanks in advance. Also, should I use overloading to handle input of different types? How do I manipulate them? A link with a proper example (really couldn't find one) would make me happy.
所以我有这个非循环的双链表样本,我觉得很难把它转换成圆形的。 (在//添加的行上划分)任何建议都会很好。提前致谢。另外,我应该使用重载来处理不同类型的输入吗?我该如何操纵它们?一个带有正确例子的链接(真的找不到一个)会让我开心。
main.cpp
#include <iostream>
#include "dlring.cpp"
int main()
{
dlring<int> dlist;
dlist.Append( 11 );
dlist.Push( 100 );
while(dlist)
std::cout << dlist.pop_back() << " ";
}
dlring.h
template <typename T>
class dlring
{
struct node
{
T data;
node* prev;
node* next;
node(T t, node* p, node* n) : data(t), prev(p), next(n) {}
};
node* head;
node* tail;
public:
dlring() : head(nullptr), tail (nullptr) {}
bool empty() const { return ( !head || !tail ); }
operator bool() const { return !empty(); }
//Yes, I also wish to implement this bool stuff otherwise.
void Append(T);
void Push(T);
T pop_back();
T pop_front();
~dlring()
{
while(head)
{
node* temp(head);
head=head->next;
delete temp;
}
}
};
dlring.cpp
#include "dlring.h"
#include <iostream>
template <typename T>
void dlring<T>::Append(T data)
{
tail = new node(data, tail, head); //changed NULL=>head
if( tail->prev )
{
tail->prev->next = tail;
head->prev = tail; //added
}
if( empty() )
head = tail;
}
template <typename T>
void dlring<T>::Push(T data)
{
head = new node(data, tail, head); //changed NULL=>tail
if( head->next )
{
head->next->prev = head;
tail->next = head; //added
}
if( empty() )
tail = head;
}
template<typename T>
T dlring<T>::pop_back()
{
if( empty() )
std::cout<<"List empty";
node* temp(tail);
T data( tail->data );
tail = tail->prev ;
if( tail )
{
tail->next = head; //null=>head;
head->prev = tail; //added
}
else
head = nullptr; //NULL=>nullptr
delete temp;
return data;
}
template<typename T>
T dlring<T>::pop_front()
{
if( empty() )
std::cout<<"List empty";
node* temp(head);
T data( head->data );
head = head->next ;
if( head )
{
head->prev = tail; //NULL=>nullptr=>tail
tail->next = head;
}
else
tail = nullptr; //NULL=>nullptr
delete temp;
return data;
}
1 个解决方案
#1
You problem is in the pop_back function:
问题出在pop_back函数中:
node * temp(tail);
T data(tail->data);
tail = tail->prev;
if(tail)
{
tail->next = head; //null=>head;
head->prev = tail; //added
}
else
{
head = nullptr; //NULL=>nullptr
}
delete temp;
When there is only one node in the list, tail isn't null - this means the if condition will be met, and the code below will be hit:
如果列表中只有一个节点,则tail不为null - 这意味着将满足if条件,并且将触发以下代码:
tail->next = head; //null=>head;
head->prev = tail; //added
But this code does nothing, because tail and head are the same thing. You then delete the only node in the list, and head and tail no longer point to anything. To solve this, you need a better way to detect if the list will be empty after deletion, and to alter the deletion code a bit:
但是这段代码什么也没做,因为尾巴和头部是一回事。然后删除列表中唯一的节点,并且head和tail不再指向任何内容。要解决此问题,您需要一种更好的方法来检测删除后列表是否为空,并稍微更改删除代码:
if (tail != temp)
{
tail->next = head; //null=>head;
head->prev = tail; //added
}
else
{
head = nullptr; //NULL=>nullptr
tail = nullptr;
}
delete temp;
temp = nullptr;
#1
You problem is in the pop_back function:
问题出在pop_back函数中:
node * temp(tail);
T data(tail->data);
tail = tail->prev;
if(tail)
{
tail->next = head; //null=>head;
head->prev = tail; //added
}
else
{
head = nullptr; //NULL=>nullptr
}
delete temp;
When there is only one node in the list, tail isn't null - this means the if condition will be met, and the code below will be hit:
如果列表中只有一个节点,则tail不为null - 这意味着将满足if条件,并且将触发以下代码:
tail->next = head; //null=>head;
head->prev = tail; //added
But this code does nothing, because tail and head are the same thing. You then delete the only node in the list, and head and tail no longer point to anything. To solve this, you need a better way to detect if the list will be empty after deletion, and to alter the deletion code a bit:
但是这段代码什么也没做,因为尾巴和头部是一回事。然后删除列表中唯一的节点,并且head和tail不再指向任何内容。要解决此问题,您需要一种更好的方法来检测删除后列表是否为空,并稍微更改删除代码:
if (tail != temp)
{
tail->next = head; //null=>head;
head->prev = tail; //added
}
else
{
head = nullptr; //NULL=>nullptr
tail = nullptr;
}
delete temp;
temp = nullptr;