我正试图在链表中创建一个函数，当我将两个整数传递给它时。它会通过更改每个节点的指向来交换它们的节点。函数完成后，我会丢失其中一个节点。我怎样才能让它工作？
这是函数本身
void linkedList::swapTwoAdjacent(int num1, int num2) {
if (head == NULL) {
cout << "List is empty" << endl;
return;
}
node *temp1, *temp2, *temp3;
for (temp1 = head, temp2 = temp1->next; temp1->next != NULL; temp1 = temp1->next, temp2 = temp2->next) {
cout << endl << "IN FOR" << endl;
if (temp1->data == num1 && temp2->data == num2) {
cout << "IN IF BEFORE NODES SWAP" << endl;
// swap nodes
cout << "Temp1 : " << temp1 << " -- Temp2 : " << temp2 << " -- Temp3 : " << temp3 << endl;
temp3 = temp2->next;
temp2->next = temp1;
temp1->next = temp3;
cout << "IN IF AFTER NODES SWAP" << endl;
}
else {
continue;
}
}
}
这是完整的实现
#include <iostream>
using namespace std;
struct node
{
int data;
node* next;
};
class linkedList {
private:
node* head;
public:
linkedList();
node* createNode(int num);
void append(int num);
// void add_as_first(int num);
// void addAfter(int c, int num);
void del(int num);
void display();
int count();
void swapTwoAdjacent(int num1, int num2);
// ~linkedList();
};
int main (){
linkedList List;
List.display();
int numNodes = 0;
cout << "Enter number of nodes that you want to add: ";
cin >> numNodes;
cout << endl;
for (int i = 0; i < numNodes; i++) {
int current_element;
cin >> current_element;
List.append(current_element);
cout << endl << current_element <<" has been appended to the list "<< endl;
cout << "-------------------------------------------------------------------" << endl;
}
List.display();
// List.del(5);
List.swapTwoAdjacent(4,6);
List.display();
// List.count();
return 0;
}
// constructor initializes head to null
linkedList::linkedList()
{
head = NULL;
}
// create node
node* linkedList::createNode(int num)
{
node* new_node;
new_node = new node;
new_node -> data = num;
new_node -> next = NULL;
return new_node;
}
void linkedList::append(int num)
{
node *temp, *nNode;
nNode = createNode(num);
if (head == NULL) {
head = nNode;
}
else {
temp = head;
while(temp -> next != NULL)
{
temp = temp -> next;
}
temp -> next = nNode;
}
}
void linkedList::display()
{
// if the list is empty
if (head == NULL) {
cout << "No nodes added yet!" << endl;
}
else {
// create a temp variable to hold the heads
node* temp = head;
// as long as we haven't reached the end of the list
while (temp != NULL) {
// print current element
cout << temp->data << " ";
// go to the next node
temp = temp->next;
}
}
}
int linkedList::count()
{
int counter = 0;
if (head == NULL) {
cout << endl << "The list has " << counter << " elements." << endl;
}
else {
for (node* temp = head; temp != NULL; temp = temp->next) {
counter++;
}
}
cout << endl << "The list has " << counter << " elements." << endl;
}
void linkedList::del(int n) {
if (head == NULL) {
cout << "No elements are in the list " << endl;
}
node *temp1, *temp2;
if (head-> next == NULL) {
head = NULL;
cout << endl << n << " was deleted" << endl;
cout << endl << "Current elements in the list :" << endl << "-----------------------------------------" << endl;
this->display();
return;
}
for (temp1 = head, temp2 = temp1->next; temp2 != NULL; temp1 = temp1->next, temp2 = temp1->next) {
if (temp1->data == n) {
head = temp2;
cout << endl << n << " was deleted" << endl;
cout << endl << "Current elements in the list :" << endl << "-----------------------------------------" << endl;
this->display();
break;
}
else if (temp2->data == n) {
temp1->next = temp2->next;
cout << endl << n << " was deleted" << endl;
cout << endl << "Current elements in the list :" << endl << "-----------------------------------------" << endl;
this->display();
break;
}
else {
continue;
}
}
}
void linkedList::swapTwoAdjacent(int num1, int num2) {
if (head == NULL) {
cout << "List is empty" << endl;
return;
}
node *temp1, *temp2, *temp3;
for (temp1 = head, temp2 = temp1->next; temp1->next != NULL; temp1 = temp1->next, temp2 = temp2->next) {
cout << endl << "IN FOR" << endl;
if (temp1->data == num1 && temp2->data == num2) {
cout << "IN IF BEFORE NODES SWAP" << endl;
// swap nodes
cout << "Temp1 : " << temp1 << " -- Temp2 : " << temp2 << " -- Temp3 : " << temp3 << endl;
temp3 = temp2->next;
temp2->next = temp1;
temp1->next = temp3;
cout << "IN IF AFTER NODES SWAP" << endl;
}
else {
continue;
}
}
}
输出通过Valgrind的样本测试显示出许多错误
==14392== Memcheck, a memory error detector
==14392== Copyright (C) 2002-2013, and GNU GPL'd, by Julian Seward et al.
==14392== Using Valgrind-3.10.1 and LibVEX; rerun with -h for copyright info
==14392== Command: ./singleLinkedList
==14392==
No nodes added yet!
Enter number of nodes that you want to add: 5
9
9 has been appended to the list
-------------------------------------------------------------------
2
2 has been appended to the list
-------------------------------------------------------------------
4
4 has been appended to the list
-------------------------------------------------------------------
6
6 has been appended to the list
-------------------------------------------------------------------
8
8 has been appended to the list
-------------------------------------------------------------------
9 2 4 6 8
IN FOR
IN FOR
IN FOR
IN IF BEFORE NODES SWAP
==14392== Use of uninitialised value of size 8
==14392== at 0x4F36E01: int std::__int_to_char<char, unsigned long>(char*, unsigned long, char const*, std::_Ios_Fmtflags, bool) (locale_facets.tcc:826)
==14392== by 0x4F3845B: std::ostreambuf_iterator<char, std::char_traits<char> > std::num_put<char, std::ostreambuf_iterator<char, std::char_traits<char> > >::_M_insert_int<unsigned long>(std::ostreambuf_iterator<char, std::char_traits<char> >, std::ios_base&, char, unsigned long) const (locale_facets.tcc:876)
==14392== by 0x4F3864E: std::num_put<char, std::ostreambuf_iterator<char, std::char_traits<char> > >::do_put(std::ostreambuf_iterator<char, std::char_traits<char> >, std::ios_base&, char, void const*) const (locale_facets.tcc:1191)
==14392== by 0x4F45729: put (locale_facets.h:2460)
==14392== by 0x4F45729: std::ostream& std::ostream::_M_insert<void const*>(void const*) (ostream.tcc:73)
==14392== by 0x4010AE: linkedList::swapTwoAdjacent(int, int) (in /home/captainmoha/uni/data_structure/singleLinkedList)
==14392== by 0x400AEA: main (in /home/captainmoha/uni/data_structure/singleLinkedList)
==14392== Uninitialised value was created by a stack allocation
==14392== at 0x400F86: linkedList::swapTwoAdjacent(int, int) (in /home/captainmoha/uni/data_structure/singleLinkedList)
==14392==
==14392== Conditional jump or move depends on uninitialised value(s)
==14392== at 0x4F36E08: int std::__int_to_char<char, unsigned long>(char*, unsigned long, char const*, std::_Ios_Fmtflags, bool) (locale_facets.tcc:824)
==14392== by 0x4F3845B: std::ostreambuf_iterator<char, std::char_traits<char> > std::num_put<char, std::ostreambuf_iterator<char, std::char_traits<char> > >::_M_insert_int<unsigned long>(std::ostreambuf_iterator<char, std::char_traits<char> >, std::ios_base&, char, unsigned long) const (locale_facets.tcc:876)
==14392== by 0x4F3864E: std::num_put<char, std::ostreambuf_iterator<char, std::char_traits<char> > >::do_put(std::ostreambuf_iterator<char, std::char_traits<char> >, std::ios_base&, char, void const*) const (locale_facets.tcc:1191)
==14392== by 0x4F45729: put (locale_facets.h:2460)
==14392== by 0x4F45729: std::ostream& std::ostream::_M_insert<void const*>(void const*) (ostream.tcc:73)
==14392== by 0x4010AE: linkedList::swapTwoAdjacent(int, int) (in /home/captainmoha/uni/data_structure/singleLinkedList)
==14392== by 0x400AEA: main (in /home/captainmoha/uni/data_structure/singleLinkedList)
==14392== Uninitialised value was created by a stack allocation
==14392== at 0x400F86: linkedList::swapTwoAdjacent(int, int) (in /home/captainmoha/uni/data_structure/singleLinkedList)
==14392==
==14392== Conditional jump or move depends on uninitialised value(s)
==14392== at 0x4F38564: std::ostreambuf_iterator<char, std::char_traits<char> > std::num_put<char, std::ostreambuf_iterator<char, std::char_traits<char> > >::_M_insert_int<unsigned long>(std::ostreambuf_iterator<char, std::char_traits<char> >, std::ios_base&, char, unsigned long) const (locale_facets.tcc:905)
==14392== by 0x4F3864E: std::num_put<char, std::ostreambuf_iterator<char, std::char_traits<char> > >::do_put(std::ostreambuf_iterator<char, std::char_traits<char> >, std::ios_base&, char, void const*) const (locale_facets.tcc:1191)
==14392== by 0x4F45729: put (locale_facets.h:2460)
==14392== by 0x4F45729: std::ostream& std::ostream::_M_insert<void const*>(void const*) (ostream.tcc:73)
==14392== by 0x4010AE: linkedList::swapTwoAdjacent(int, int) (in /home/captainmoha/uni/data_structure/singleLinkedList)
==14392== by 0x400AEA: main (in /home/captainmoha/uni/data_structure/singleLinkedList)
==14392== Uninitialised value was created by a stack allocation
==14392== at 0x400F86: linkedList::swapTwoAdjacent(int, int) (in /home/captainmoha/uni/data_structure/singleLinkedList)
==14392==
Temp1 : 0x5aa7d20 -- Temp2 : 0x5aa7d70 -- Temp3 : 0xffefffca0
IN IF AFTER NODES SWAP
9 2 4 8 ==14392==
==14392== HEAP SUMMARY:
==14392== in use at exit: 72,784 bytes in 6 blocks
==14392== total heap usage: 6 allocs, 0 frees, 72,784 bytes allocated
==14392==
==14392== LEAK SUMMARY:
==14392== definitely lost: 32 bytes in 2 blocks
==14392== indirectly lost: 48 bytes in 3 blocks
==14392== possibly lost: 0 bytes in 0 blocks
==14392== still reachable: 72,704 bytes in 1 blocks
==14392== suppressed: 0 bytes in 0 blocks
==14392== Rerun with --leak-check=full to see details of leaked memory
==14392==
==14392== For counts of detected and suppressed errors, rerun with: -v
==14392== ERROR SUMMARY: 19 errors from 3 contexts (suppressed: 0 from 0)
当您尝试交换两个节点时，最终会删除一个。
if (temp1->data == num1 && temp2->data == num2)
{
temp3 = temp2->next; //temp# == node# at this moment
temp2->next = temp1; //node2 now links back to node1
temp1->next = temp3; //node1 now skips node2 and goes to node3
}
执行完此代码后，您现在已经从列表中删除了我称之为node2的节点。由于循环的编写方式，您会比预期更快地到达列表的末尾，并尝试取消引用空指针。在你的for循环中：
temp1 = temp1->next, /*temp1->next now points to last node*/
temp2 = temp1->next /*temp2 is now a null pointer*/
因此循环条件temp2->next != NULL失败，因为temp2本身为NULL。
在评论中，发现将temp2 = temp1->next更改为temp2 = temp2->next会使segfault停止。这是因为temp2->next指向node，因此需要更多的迭代才能到达循环失败的末尾。如果您只是在"交换"之后从函数中return，则不会出现此错误。
编辑：我添加了交换两个节点的代码。
void linkedList::swapTwoAdjacent(int num1, int num2)
{
if (head == NULL) {
cout << "List is empty" << endl;
return;
}
node** np = &head; //two star programmer club
node* temp;
while ((*np)->next != NULL) //As long as next node exists
{
if ((*np)->data == num1 && (*np)->next->data == num2)
{
temp = *np; //temp = &node1
*np = (*np)->next; //node0->next = &node2
temp->next = (*np)->next; //node1->next = node2->next
(*np)->next = temp; //node2->next = node1
//node0->node2->node1->node3
//If you want to only swap the first pair of values you find, uncomment the next line, otherwise it swaps every matching pair
//return;
}
np = &((*np)->next); //Point to pointer to next node
}
}
通过使用指向节点的指针，我们可以修改指向我们正在迭代的当前节点的指针。希望这些评论能解释所有的作业都在做什么。
对于记录，我使用三个指针使其工作。我的问题是，在我交换的两个节点之前，我没有办法知道节点，所以我一直在丢失一个节点。
这是一种带有注释的工作方法，希望能解释我所做的事情：
void linkedList::swapTwoAdjacent(int num1, int num2) {
node *temp1, *temp2, *temp3;
temp1 = head;
temp2 = temp1->next;
if (head == NULL) {
cout << "List is empty" << endl;
return;
}
else if (head->next == NULL) {
cout << "Swap not possible! List has only one node." << endl;
}
else if (temp1->data == num1 && temp2->data == num2) { // if the nodes to swap are the first two nodes
head->next = temp2->next; // make the next of head point to the third node
temp2->next = head; // make the next of the second node point to head
head = temp2; // now make the second node the head
}
else {
node *tempHolder1, *tempHolder2, *tempHolder3; // holders for nodes in temps to make swapping easier
// go through nodes in the list with three pointers
// temp1->temp2->temp3
// I'm using three pointers so that I always know the node before the two nodes I'm looking for
for (temp1 = head, temp2 = temp1->next, temp3 = temp2->next; temp3 != NULL; temp1 = temp1->next, temp2 = temp1->next, temp3 = temp2->next) {
// cout << "IN FOR" << endl;
if (temp2->data == num1 && temp3->data == num2) { // if the two nodes are found
// these are just placeholders to make swapping easier
tempHolder1 = temp1; // now temp1 is the node before the two nodes I want to swap
tempHolder2 = temp2; // temp2 is the first node
tempHolder3 = temp3; // temp3 is the second node
temp1->next = tempHolder2->next; // make the first node point to the third node
temp2->next = tempHolder3->next; // make the second node point to what's after the third node
temp3->next = tempHolder2; // make the third node point to the second node
break;
}
else {
continue;
}
}
}
}