我调整了我的简单应用程序，它允许您使用链表。 每个节点都有一个 char 值作为数据，还有一个 int 计数，用于计算每个数据的出现次数。 我需要一个函数来复制现有列表并将其粘贴到其他地方，最后返回粘贴列表的第一个节点的地址。我该怎么做？ 这是我的整个代码：
#include <iostream>
using namespace std;
struct Snode //Snode class defines a node in a list
{
char data;
int count = 1;
Snode *next = NULL;
Snode(char a) : data(a) {}
};
class set//set class defines the list
{
private:
Snode *head;
public:
set() : head(NULL)//constructor method of the list
{
Snode *temp = head;
while (temp != NULL)
{
Snode *next = temp->next;
delete temp;
temp = next;
}
head = NULL;
}
~set()//destructor method of the list
{
Snode *temp = head;
while (temp != NULL)
{
head = head->next;
delete temp;
}
}
bool isAvailable(char value)//checks if the node is already in the list or not
{
Snode *temp = head;
while (temp != NULL)//untill the end of the list
{
if (temp->data == value)//if a similar node is found
return true;
else//if temp is not equal check the next node
temp = temp->next;
}
return false;//if no node is found return false
}
bool isFirst(char value)//checks if the node is the first node or not
{
return(head->data == value);//if it equals to head, it's the first node
}
bool isLast(char value)//checks if the node is the last node or not
{
Snode *last ;
return(last->next = NULL);//if its next pointer points the null pointer, it's the last node in the list
}
void display()//showing all the nodes
{
//creating a variable node to travers available nodes
Snode *temp = head;
while (temp != NULL)//travers nodes untill the end of the list
{
cout << temp->data << " " << temp->count << "n"; //output format
temp = temp->next;//setting the next node as the variable
}
}
void insert(char value)//inserts a new node
{
if (head == NULL)//if the list is empty
{
//create a new node, set its count to 1 and set it as head of the list
Snode *temp = new Snode(value);
temp->count = 1;
head = temp;
}
else//is the list is'nt empty
{
if (isAvailable(value))//if the value is already available
{
//find the existing node and increase its count by 1
Snode *temp = head;
while (temp->data != value)//check the list to the end
temp = temp->next;
temp->count += 1;
}
else//if there's not an existing node with the given value
{
//create a new node with a count of 1 at the end of the list by setting *next equal to NULL
Snode *temp = new Snode(value);
temp->count = 1;
temp->next = NULL;
}
}
}
int count(char value)//counts the occurrence of a character value by reading the same node's count
{
Snode *temp = head;
while (temp != NULL)//travers nodes untill the end of the list
{
if(temp->data==value)
{
cout<<temp->count;
}
else
{
cout<<"This character is not in the list";
}
}
return temp->count;
}
void deleteFirst(char value)//delete the first node in the list
{
Snode *temp = head;//create a new node including head's data
head = head->next;//setting the second node as head
delete temp;//deleting the first node
}
void deleteLast(char value)//deleting the last node in the list
{
Snode *current= new head;//creating two new nodes and starting the travers from the first node
Snode *previous=new Snode();
while(current->next!=NULL)//continue traversing untill the end of the list
{
previous=current;//moving current and previous nodes to the right in order to check the next nodes
current=current->next;
if(current->next == NULL)//if the list is finished
{
previous->next = NULL;//pointing the previous node's next as NULL, instead of the last node
delete current;//deleting the last node
}
}
}
char remove(char value, struct Snode *temp)//removing a node from the list
{
if(!isAvailable(value))//if there's no node with the given data
{
cout<<"Not available";
return NULL;
}
else//if there is already a node with the same data
{
if(temp->count == 1)//if there's a node with one time occurrence
{
if(isFirst(value)//if it's equal to the first node
{
deleteFirst(value);
}
else if(isLast(value))//if it's equal to the last node
{
deleteLast(value);
}
else//if it's in the middle, neither first nor last
{
Snode *current = head;//traversing all nodes
Snode *previous=new Snode();
while(current->next=NULL)
{
if(current->data==value)
{
previous->next = current->next;
delete current;
}
previous=current;
current=current->next;
}
}
}
else if(temp->count > 1)
{
temp->count--;//decrease the count
}
}
}
};
int main()
{
//defining a mySet as a "set" type
set mySet;
//adding values to create nodes
mySet.insert('c');
mySet.insert('a');
mySet.insert('a');
mySet.insert('c');
mySet.insert('c');
//displaying nodes through "value count" format
mySet.display();
return 0;
}
您需要枚举旧列表的节点，为复制的数据分配新节点并将它们添加到新列表中。 执行此操作的最佳位置是在set类的复制构造函数和复制赋值运算符中。
此外，set类的默认构造函数正在执行析构函数应该执行的工作。这不是必需的，因为构造函数中还没有要删除的内容。析构函数未正确循环访问列表。默认构造函数中的代码正在正确迭代。 该代码需要从构造函数移动到析构函数。
您的其他set类方法的实现效率不高(列表的冗余搜索(，甚至在某些情况下(完全错误的逻辑、内存泄漏等(都不正确。
尝试更多类似的东西：
struct Snode
{
char data;
int count;
Snode *next = nullptr;
Snode(char a, int c = 1) : data(a), count(c) {}
};
class set
{
private:
Snode *head = nullptr;
Snode *tail = nullptr;
void append(char value, int count)
{
Snode *temp = new Snode(value, count);
if (!head)
head = temp;
if (tail)
tail->next = temp;
tail = temp;
}
void remove(Snode *node, Snode *previous)
{
if (previous)
previous->next = node->next;
if (head == node)
head = node->next;
if (tail == node)
tail = previous;
delete node;
}
void swap(set &other)
{
Snode *ptr = head;
head = other.head;
other.head = ptr;
ptr = tail;
tail = other.tail;
other.tail = ptr;
}
public:
set() = default;
set(const set &src)
{
Snode *temp = src.head;
while (temp)
{
append(temp->data, temp->count);
temp = temp->next;
}
}
set(set &&src)
{
src.swap(*this);
}
~set()
{
Snode *temp = head;
while (temp)
{
Snode *next = temp->next;
delete temp;
temp = next;
}
}
set& operator=(const set &rhs)
{
if (&rhs != this)
{
set temp(rhs);
temp.swap(*this);
}
return *this;
}
set& operator=(set &&rhs)
{
rhs.swap(*this);
return *this;
}
bool isAvailable(char value)
{
return (find(value) != nullptr);
}
Snode* find(char value, Snode **previous = nullptr)
{
if (previous)
*previous = nullptr;
Snode *temp = head;
Snode *prev = nullptr;
while (temp)
{
if (temp->data == value)
{
if (previous)
*previous = prev;
return temp;
}
prev = temp;
temp = temp->next;
}
return nullptr;
}
bool isFirst(char value)
{
return ((head) && (head->data == value));
}
bool isLast(char value)
{
return ((tail) && (tail->data == value));
}
void display()
{
Snode *temp = head;
while (temp)
{
std::cout << temp->data << " " << temp->count << std::endl;
temp = temp->next;
}
}
void insert(char value)
{
Snode *temp = find(value);
if (temp)
temp->count += 1;
else
append(value, 1);
}
int count(char value)
{
Snode *temp = find(value);
return (temp) ? temp->count : 0;
}
void deleteFirst()
{
if (head)
remove(head, nullptr);
}
void deleteLast()
{
if (head)
{
Snode *last = head;
Snode *previous = nullptr;
while (last->next)
{
previous = last;
last = last->next;
}
remove(last, previous);
}
}
void remove(char value)
{
Snode *previous;
Snode *temp = find(value, &previous);
if (temp)
{
if (temp->count > 1)
temp->count -= 1;
else
remove(temp, previous);
}
}
};
然后你可以做这样的事情：
int main()
{
//defining a mySet as a "set" type
set mySet;
//adding values to create nodes
mySet.insert('c');
mySet.insert('a');
mySet.insert('a');
mySet.insert('c');
mySet.insert('c');
set myCopiedSet = mySet; // make a copy of the list
//adding more values to create nodes
myCopiedSet.insert('a');
myCopiedSet.insert('b');
myCopiedSet.insert('b');
myCopiedSet.insert('c');
//displaying nodes through "value count" format
std::cout << "original:" << std::endl;
mySet.display();
std::cout << "copy:" << std::endl;
myCopiedSet.display();
return 0;
}
如果使用双链表而不是单链表，则可以进一步简化set类：
struct Snode
{
char data;
int count;
Snode *previous = nullptr;
Snode *next = nullptr;
Snode(char a, int c) : data(a), count(c) {}
};
class set
{
private:
Snode *head = nullptr;
Snode *tail = nullptr;
void append(char value, int count)
{
Snode *temp = new Snode(value, count);
if (!head)
head = temp;
if (tail)
{
temp->previous = tail;
tail->next = temp;
}
tail = temp;
}
void remove(Snode *node)
{
if (node->previous)
node->previous->next = node->next;
if (node->next)
node->next->previous = node->previous;
if (head == node)
head = node->next;
if (tail == node)
tail = node->previous;
delete node;
}
void swap(set &other)
{
Snode *ptr = head;
head = other.head;
other.head = ptr;
ptr = tail;
tail = other.tail;
other.tail = ptr;
}
public:
set() = default;
set(const set &src)
{
Snode *temp = src.head;
while (temp)
{
append(temp->data, temp->count);
temp = temp->next;
}
}
set(set &&src)
{
src.swap(*this);
}
~set()
{
Snode *temp = head;
while (temp)
{
Snode *next = temp->next;
delete temp;
temp = next;
}
}
set& operator=(const set &rhs)
{
if (&rhs != this)
{
set temp(rhs);
temp.swap(*this);
}
return *this;
}
set& operator=(set &&rhs)
{
rhs.swap(*this);
return *this;
}
bool isAvailable(char value)
{
return (find(value) != nullptr);
}
Snode* find(char value)
{
Snode *temp = head;
while (temp)
{
if (temp->data == value)
return temp;
temp = temp->next;
}
return nullptr;
}
bool isFirst(char value)
{
return ((head) && (head->data == value));
}
bool isLast(char value)
{
return ((tail) && (tail->data == value));
}
void display()
{
Snode *temp = head;
while (temp)
{
std::cout << temp->data << " " << temp->count << std::endl;
temp = temp->next;
}
}
void insert(char value)
{
Snode *temp = find(value);
if (temp)
temp->count += 1;
else
append(value, 1);
}
int count(char value)
{
Snode *temp = find(value);
return (temp) ? temp->count : 0;
}
void deleteFirst()
{
if (head)
remove(head);
}
void deleteLast()
{
if (tail)
remove(tail);
}
void remove(char value)
{
Snode *temp = find(value);
if (temp)
{
if (temp->count > 1)
temp->count -= 1;
else
remove(temp);
}
}
};
在这种情况下，你可以通过使用 STL 的std::list容器来大大简化set类，这是双链表的标准化实现：
#include <list>
#include <algorithm>
struct Snode
{
char data;
int count;
};
class set
{
private:
std::list<Snode> nodes;
auto findValue(char value)
{
return std::find_if(nodes.begin(), nodes.end(),
[=](const Snode &n){ return (n.data == value); }
);
}
public:
bool isAvailable(char value)
{
return (find(value) != nullptr);
}
Snode* find(char value)
{
auto iter = findValue(value);
if (iter != nodes.end())
return &*iter;
return nullptr;
}
bool isFirst(char value)
{
return ((!nodes.empty()) && (nodes.front().data == value));
}
bool isLast(char value)
{
return ((!nodes.empty()) && (nodes.back().data == value));
}
void display()
{
for (auto &n : nodes)
std::cout << n.data << " " << n.count << std::endl;
}
void insert(char value)
{
Snode *temp = find(value);
if (temp)
temp->count += 1;
else
nodes.push_back(Snode{value, 1});
}
int count(char value)
{
Snode *temp = find(value);
return (temp) ? temp->count : 0;
}
void deleteFirst()
{
if (!nodes.empty())
nodes.pop_front();
}
void deleteLast()
{
if (!nodes.empty())
nodes.pop_back();
}
void remove(char value)
{
auto iter = findValue(value);
if (iter != nodes.end())
{
if (iter->count > 1)
iter->count -= 1;
else
nodes.erase(iter);
}
}
};