从DoublyLinkedList中删除重复项 [英] Removing duplicates from a DoublyLinkedList
问题描述
我试图在C ++中删除重复的项目。我设法通过使用对象的默认构造函数来获得对象= null。但我无法从列表中完全删除它。此代码还会删除两个对象，而不只是一个。这是从另一个问题的重新发布。我的代码和部分我的帖子已更改。如何通过全名删除重复链接列表中的重复。任何人都可以帮助我这个？这是我的removeDuplicates函数：
I'm trying to remove duplicate items in C++. I've managed to get the object to = null by using the objects default constructor. But I am unable to completely remove it from the list. This code also deletes the two objects rather than just one. This is a re-post from another question. My code and partially my post has changed.How to remove duplicates from a doubly linked list by full name. Can anyone help me with this? Here is my removeDuplicates function:
***Remove Duplicates***
void RemoveDuplicates(DoublyLinkedListIterator<Datatype> m_itr, string searchByFirstName, string searchBySecondName)
{
for (m_itr.Start(); m_itr.Valid(); m_itr.Forth())
{
if ((m_itr.Item().getFirstName() == searchByFirstName )
&& (m_itr.Item().getSecondName() == searchBySecondName))
{
for (m_itr.Item(); m_itr.Valid(); m_itr.Forth())
{
if ((m_itr.Item().getFirstName() == searchByFirstName )&&
(m_itr.Item().getSecondName() == searchBySecondName))
{
m_itr.Item() = Stats();
}
}
}
}
delete m_itr.Item();
}
***Remove***
void Remove(DoublyLinkedListIterator<Datatype> m_itr)
{
query.clock1();
DoublyLinkedListNode<Datatype>* node = m_head;
//Check to see if the iterator belongs to this list, if not return nothing.
if (m_itr.m_list != this)
return;
//Check to see if the node is valid, if not return nothing.
if (m_itr.m_node == 0)
return;
//If the iterator is pointing to the head...
if (m_itr.m_node == m_head)
{
//Move the iterator forward.
m_itr.Forth();
//Delete the head.
RemoveHead();
//Decrement the size.
m_count--;
}
//If the iterator is not pointing to the head...
else
{
//Search forward through the list until you find
//the node prior to the node you want to remove.
while (node->m_next != m_itr.m_node)
node = node->m_next;
// move the iterator forward.
m_itr.Forth();
//If the node being are deleted is the tail...
//Then update the tail node.
if (node->m_next == m_tail)
{
//Tail is now equal to node. Which means we can now delete the node.
m_tail = node;
}
//Delete the node.
delete node -> m_next;
//Relink the list.
node -> m_next = m_itr.m_node;
//Decrement the count because a node was removed.
m_count--;
query.clock2();
cout << "\nTime Taken : " << query.time2 - query.time1 << "\n";
}
}
***Class Declarations***
template <class Datatype>
class DoublyLinkedList
{
public:
//-------------------------------------------------------------------------------------------
// Member Vairables.
//-------------------------------------------------------------------------------------------
DoublyLinkedListNode<Datatype>* m_head;
DoublyLinkedListNode<Datatype>* m_tail;
int m_count;
template<class Datatype>
class DoublyLinkedListNode
{
public:
//-------------------------------------------------------------------------------------------
// Member Vairables.
//-------------------------------------------------------------------------------------------
DoublyLinkedListNode<Datatype>* m_next; //The next node.
DoublyLinkedListNode<Datatype>* m_prev; //The previous node.
Datatype m_data; //The data in the node.
template <class Datatype>
class DoublyLinkedListIterator
{
public:
//-------------------------------------------------------------------------------------------
// Member Vairables.
//-------------------------------------------------------------------------------------------
DoublyLinkedListNode<Datatype>* m_node; //A node for the Iterator to pointn to.
DoublyLinkedList<Datatype>* m_list; //A list for the Iteraotor to go through.
//-------------------------------------------------------------------------------------------
// Name: Constructor.
// Description: Constructs the DoublyLinkedListIterator.
//-------------------------------------------------------------------------------------------
DoublyLinkedListIterator(DoublyLinkedList<Datatype>* p_list= 0, DoublyLinkedListNode<Datatype>* p_node= 0)
{
m_list= p_list;
m_node= p_node;
}
// ------------------------------------------------------------------
// Name: Start
// Description: Resets the iterator to the beginning of the list.
// Arguments: None.
// Return Value: None.
// ------------------------------------------------------------------
void Start()
{
if(m_list!= 0)
m_node= m_list -> m_head;
}
// ----------------------------------------------------------------
// Name: End
// Description: Resets the iterator to the end of the list.
// Arguments: None.
// Return Value: None.
// ----------------------------------------------------------------
void End()
{
if(m_list!= 0)
m_node = m_list->m_tail;
}
// ----------------------------------------------------------------
// Name: Forth
// Description: Moves the iterator forward by one position.
// Arguments: None.
// Return Value: None.
// ----------------------------------------------------------------
void Forth()
{
if(m_node != 0)
{
m_node = m_node ->m_next;
}
}
// ----------------------------------------------------------------
// Name: Back
// Description: Moves the iterator back by one position.
// Arguments: None.
// Return Value: None.
// ----------------------------------------------------------------
void Back()
{
if(m_node!= 0)
m_node = m_node->m_prev;
}
// ----------------------------------------------------------------
// Name: Item
// Description: Gets the item that the iterator is pointing to.
// Arguments: None.
// Return Value: Reference to the data in the node.
// ----------------------------------------------------------------
Datatype& Item()
{
return m_node->m_data;
}
//-----------------------------------------------------------------
// Name: Valid
// Description: Determines if the node is valid.
// Arguments: None.
// Return Value: true if valid.
// ----------------------------------------------------------------
bool Valid()
{
return (m_node!= 0);
}
};
推荐答案
使用DoublyLinkedList的内置Remove函数并传递迭代器。 delete 调用是裸机C ++变体，不处理节点的删除和正确地重新链接列表。调用 delete 只会删除节点中的内容，而不是节点本身！
Use the DoublyLinkedList's built-in Remove function and pass it the iterator. The delete call is the bare bones C++ variant which doesn't deal with the deletion of nodes and re-linking the list properly. The call to delete only removes what's in the node, not the node itself!
Remove(m_itr);
而不是
delete m_itr.Item();
此外，我认为删除的位置可能已关闭（您将总是删除最后一个项目，它似乎）。也许你想做一些下面的事情。不知道什么Stats（），但希望你会得到的想法。基本上你需要放弃要删除的项目，前进常规迭代器，然后删除一个你放弃。或者，一旦删除完成，完全停止迭代。这是需要的，因为当迭代器被删除，它不能用于进一步的迭代。
Also, I think the place of your deletion might be off (you will always delete the last item, it seems). Maybe you want to do something like below. Not sure what Stats() does, but hopefully you'll get the idea. Basically you need to put away the item to delete, step forward the regular iterator and then remove the one you put away. Alternatively, stop the iteration completely once removal is complete. This is needed because when the iterator gets removed, it can't be used for further iterating.
if ((m_itr.Item().getFirstName() == searchByFirstName ) &&
(m_itr.Item().getSecondName() == searchBySecondName))
{
DoublyLinkedListIterator<Datatype> toDelete = m_itr;
m_itr.Forth();
Remove(toDelete);
}
这篇关于从DoublyLinkedList中删除重复项的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
