我试图在我的链表中创建一个函数，当我将两个整数传递给它时。它会通过改变每个节点指向的内容来交换它们的节点。函数完成后我丢失了其中一个节点。我怎样才能让它发挥作用？
这是函数本身
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 循环的编写方式，您比预期更快地到达列表末尾，并尝试取消引用空指针。在你的 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 会使段错误停止。这是因为 temp2->next 指向回 node，因此需要更多迭代才能到达循环失败的结尾。如果您只是在“交换”之后从函数中返回，就不会出现此错误。
编辑:我添加了交换两个节点的代码。
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
}
}
通过使用指向节点指针的指针，我们可以修改指向我们正在迭代的当前节点的指针。这些评论有望解释所有作业都在做什么。
关于c++ - 如何创建一个函数，仅通过更改链接来交换单向链表中的两个相邻元素？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/33620194/