当 main 使用构造的 dlring 类型的变量运行时，使用此模板类可以正常工作，但我的目标是允许动态分配，因此我可以处理非预定义数量的双链循环列表以允许使用以下函数：
- 通过使用节点位置(通过
迭代)或值输入将列表拆分为两个。 - 将两个列表链接为一个具有单个头/尾的列表也是如此 双。 从一个列表(实例)
- 导出到另一个列表(实例)的节点。
- 等。
我非常确定有一个优雅的解决方法，我根本不知道，但如果您没有足够努力解决，我认为为社区提出一个问题并不好。(检查谷歌
因此，有了这个目标，我应该使用某种指针到指针 AFAIK 动态分配内存(通过构造函数调用)。如果有更智能的方法来实施这些，请告诉我。我的解决方案尝试在此代码段的末尾给出。请随时批评以下所有内容。
双向链接的循环列表类标头(简化)
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(); }
void Push(T);
T pop_back();
~dlring()
{
while(head)
{
node* temp(head);
head=head->next;
delete temp;
}
}
};
我应该使用注释掉的运算符布尔重载吗？
pop_back和推送方法：
template <typename T>
void dlring<T>::Push(T data)
{
head = new node(data, tail, head);
if( head->next )
{
head->next->prev = head;
tail->next = head;
}
if( empty() )
{
tail = head;
head->next=tail;
head->prev=tail;
tail->next=head;
tail->prev=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 != temp)
{
tail->next->next = head;
head->prev = tail;
}
else
{
head = nullptr;
tail = nullptr;
}
delete temp;
temp = nullptr;
return data;
}
我的尝试没有正确的行为：当我尝试通过迭代显示所有列表时，代码失败，在 dlist[0] 的头>数据访问尝试中出现段错误，其中0是 k 的迭代。这是片段：
int main()
{
int k;
std::cout<<"Rings count?"<<std::endl;
std::cin>>k;
dlring<int>* dlist = new dlring<int>[k]; //I suppose I'm allocating *k*
//dlring<int> elements. this line is not confirmed to call the constructor.
(dlist[0]).Push(10);
(dlist[0]).Push(13);
(dlist[1]).Push(99);
/*{
while(!dlist[0].empty())
std::cout<<(dlist[0]).pop_back()<<" ";
std::cout<<std::endl;
while(!dlist[1].empty())
std::cout<<(dlist[1]).pop_back()<<" ";
}*/
//this section works perfectly fine, while this
for(int i=0;i<k;i++)
{
while(!dlist[k].empty())
std::cout<<(dlist[k]).pop_back()<<" ";
std::cout<<std::endl;
}
//is causing a segmentation fault while attempting to access dlist[*0*].tail->data.
std::cout<<(dlist[0]).head->data;
//line was checked and is confirmed to be functional,
//I suppose dlist[variable] has some trick I don't know yet.
//what I wish to look like an instance call would be *
return 0;
}
此致敬意。同样，请随时批评我的任何代码/逻辑。
for(int i=0;i<k;i++)
{
while(!dlist[k].empty())
std::cout<<(dlist[k]).pop_back()<<" ";
std::cout<<std::endl;
}
未使用迭代器i。它应该是：
for(int i=0;i<k;i++)
{
while(!dlist[i].empty())
std::cout<<(dlist[i]).pop_back()<<" ";
std::cout<<std::endl;
}
由于dlist是一个大小k数组，原始代码产生越界访问。
由于上述循环使dlist数组中的每个列表都为空，因此所有这些列表的head都将是一个空指针。请注意，您根本无法访问它，因为它是私有成员。如果这样做，则在取消引用时会出现段错误：
std::cout<<(dlist[0]).head->data;
如果编译，在程序的这一点上，dlist[0].head == nullptr，因此段错误。
另请注意，您正在泄漏内存，因为您没有释放动态分配的dlist。附加到程序末尾：
delete[] dlist;
通过这些更改，我不会从 clang 的地址清理器中得到任何段错误、问题或报告。
另一个问题(在您的main中没有体现)是pop_back中tail的设置。我将尝试使用一些 ASCII 艺术进行说明。一个盒子
D ->
<- D
表示具有数据、next指针和prev指针的节点。 所有箭头都是指针。
非空列表：
+-----------------------------+
v |
D -> D -> .. D -> D -+
+- D <- D .. <- D <- D
| ^
+-----------------------------+
^ ^
|head |tail
head->prev指向与tail相同的对象，类似地，tail->next指向与head相同的对象。
现在，pop_back函数的"动画"。
template<typename T>
T dlring<T>::pop_back()
{
if( empty() )
std::cout<<"List empty";
node* temp(tail);
/*
+-----------------------------+
v |
D -> D -> .. D -> D -+
+- D <- D .. <- D <- D
| ^
+-----------------------------+
^ ^
|head |tail
|temp
*/
T data( tail->data );
tail = tail->prev ;
/*
+-----------------------------+
v |
D -> D -> .. D -> D -+
+- D <- D .. <- D <- D
| ^
+-----------------------------+
^ ^ ^
|head |tail |temp
*/
if (tail != temp)
{
tail->next->next = head;
/*
+-----------------------------+
v |
D -> D -> .. D -> D -+ (A)
+- D <- D .. <- D <- D
| ^
+-----------------------------+
^ ^ ^
|head |tail |temp
The pointer (A) is what is changed when writing to tail->next->next.
Yes, nothing has actually changed in the list!
*/
head->prev = tail;
/*
+-----------------------------+
v |
D -> D -> .. D -> D -+
+- D <- D .. <- D <- D
| ^
+---------------------+
^ ^ ^
|head |tail |temp
*/
}
else
{
head = nullptr;
tail = nullptr;
}
delete temp;
/*
D -> D -> .. D ->
+- D <- D .. <- D
| ^
+---------------------+
^ ^ ^
|head |tail |temp
*/
temp = nullptr;
return data;
}
请注意，在最后一个"图片"中，tail->next是一个无效的指针。
相反，它应该是：
if (tail != temp)
{
tail->next = head;
/*
+---------------------+-------+
v | |
D -> D -> .. D -+ D -+
+- D <- D .. <- D <- D
| ^
+-----------------------------+
^ ^ ^
|head |tail |temp
删除temp后(没有进一步的更改)，它将如下所示：
/*
+---------------------+
v |
D -> D -> .. D -+
+- D <- D .. <- D
| ^
+---------------------+
^ ^ ^
|head |tail |temp
最后但并非最不重要的一点是，请注意您违反了三法则。