颠倒链表

#include<iostream>
using namespace std;
struct node{
int data;
node* next;
};
node *head=NULL;
void print(struct node*)
{
node *temp=head;
while(temp!=NULL)
{
cout<<temp->data;
temp=temp->next;
}
}
struct node* insert(struct node* head,int x)
{
node *temp=new node();
temp->data=x;
temp->next=head;
head=temp;
return head;
}
struct node* reverse(struct node* head)
{
node *current,*next,*prev;
current=head;
prev=NULL;
next=NULL;
while(current!=NULL)
{
next=current->next;
current->next=prev;
current=next;
prev=current;
}
head=prev;
return head;
}
int main()
{
struct node *head=NULL;
head=insert(head,2);
head=insert(head,4);
head=insert(head,3);
head=insert(head,8);
print(head);
head=reverse(head);
print(head);
return 0;
}

有人能指出这个代码的错误吗。我试过执行它，但我似乎在打印方面遇到了问题。即使在我尝试进行更正之后，它也只是打印链接列表，而不是反向链接列表。我是个初学者。谢谢

问题：

您的代码有很多问题需要解决，但针对您的问题，问题出在print函数中。

你的问题有两个问题：

您使用的是一个名为head的全局变量，该变量始终为NULL，而不是使用作为参数传递的变量
倒车功能不正确

解决方案

更改此

node *head=NULL;
void print(struct node*)
{
node *temp=head;
while(temp!=NULL)
{
cout<<temp->data;
temp=temp->next;
}
}

为此：

void print(struct node* head)
{
node *temp=head;
while(temp!=NULL)
{
cout<<temp->data;
temp=temp->next;
}
}

通过这种方式，您将使用参数中的节点，而不是全局范围中始终为NULL的节点。

反向功能更改：

current = next;
prev = current;

为此：

prev = current;
current = next;

附加信息：

using namespace std;是一种糟糕的做法(更多信息请点击此处(
您可能应该添加一个类来用方法包装链表
我会使用nullptr而不是NULL来避免混淆(更多信息请点击此处(
也许你应该找一本好的C++教材

完整代码：

#include<iostream>
struct node{
public:
int data;
node* next;
};
class linkedList
{
private:
node* head;
public:
linkedList();
void print();
void reverse();
void insert(int);
void invert();
};
linkedList::linkedList()
{
head = nullptr;
}
void linkedList::print()
{
node *temp = this->head;
while(temp!=nullptr)
{
std::cout << temp->data;
temp = temp->next;
}
}
void linkedList::insert(int x)
{
node *temp = new node();
temp->data = x;
temp->next = this->head;
this->head = temp;
}
void linkedList::reverse()
{
node *current,*next,*prev;
current = this->head;
prev = nullptr;
next = nullptr;
while(current != nullptr)
{
next = current->next;
current->next=prev;
prev = current;
current = next;
}
this->head = prev;
}
int main()
{
linkedList myList;
myList.insert(4);
myList.insert(4);
myList.insert(3);
myList.insert(8);
myList.print();
myList.reverse();
myList.print();
return 0;
}

如其他人所述修复您的print。

您的reverse不正确。

在reverse中，您有：

current = next;
prev = current;

prev在第一次迭代中将是NULL[这是正确的]。但是，之后，它将不再是上一个节点，而是与当前节点相同。

您想要：

prev = current;
current = next;

我的答案不是直接回答困扰您的代码的问题，而是查看；适当的"；C++解决方案可能看起来像。它使用双链接列表，这意味着节点知道列表中的前一个和下一个节点是什么。我这样做是因为像reverse()这样的函数变得容易得多。

Tangent
学生通常可以选择写一个双链表并跳过它，但他们没有意识到这会让他们的生活变得多么轻松，唯一的代价是多做几次指针作业。不管怎样，那是我的课
/切线

C++是C的独立语言。每当新的C++标准发布时，情况就会越来越严重。这个带有全局节点和自由函数的C方法简直是可怕的C++。

下面是一个C++链表的示例。这是一个快速的代码，根本不应该被认为是决定性的。我使用一个类，并将关于链表的所有内容封装到该类中。我有一些评论解释了一些代码选择(或缺乏代码选择(。

我选择不使用智能指针，因为对我来说，它们在数据结构中没有多大意义。这是一个非常主观的观点。

我也没有利用任何C++20功能；我只是还不够了解他们。

#include <algorithm>
#include <iostream>
// Ideally all of this linked list code would be in its own header file that
// you include in your main.cpp
template <typename T>
class LinkedList;
template <typename T>
void print(LinkedList<T>& list);
template <typename T>
class LinkedList {
public:
LinkedList() = default;
~LinkedList();
// I am ommitting the remainder of the Rule of 0/3/5 functions which are
// required if you want the list to function properly. It is much simpler
// to implment them using the copy/swap idiom
// https://stackoverflow.com/a/3279550/6119582
void push_back(T val);  // for C++ insert() usually means at any position
void reverse();
// Added for simplicity. The real way would be to ensure T can be printed
// (operator<<() for custom T) and provide iterators for the LinkedList.
// Worth noting that because I didn't want to implement the full Rule of
// 0/3/5, that this function is less than ideal, but it exists only to
// demonstrate that the list is behaving.
friend void print<T>(LinkedList& list);
private:
struct Node {
T data;
Node* next = nullptr;
Node* prev = nullptr;
};
Node* m_head = nullptr;
Node* m_tail = nullptr;
};
template <typename T>
LinkedList<T>::~LinkedList() {
Node* tmp = m_head;
while (tmp) {
m_head = m_head->next;
delete tmp;
tmp = m_head;
}
m_tail = nullptr;
}
template <typename T>
void LinkedList<T>::push_back(T val) {
// Empty list
if (!m_head) {
m_head = new Node{val};
m_tail = m_head;
return;
}
m_tail->next = new Node{val};
m_tail->next->prev = m_tail;
m_tail = m_tail->next;
}
template <typename T>
void LinkedList<T>::reverse() {
// We start at the end of the list, and simply swap the next and prev
// pointers. And we do that for every Node in the list, finally, we swap the
// LinkedList's head and tail pointers. This is a lot tougher in a singly-
// linked list.
Node* walker = m_tail;
while (walker) {
std::swap(walker->next, walker->prev);
walker = walker->next;
}
std::swap(m_head, m_tail);
}
template <typename T>
void print(LinkedList<T>& list) {
typename LinkedList<T>::Node* tmp = list.m_head;
while (tmp) {
std::cout << tmp->data << ' ';
tmp = tmp->next;
}
std::cout << 'n';
}
int main() {
LinkedList<int> list;
for (int i = 1; i < 11; ++i) {
list.push_back(i);
}
print(list);
list.reverse();
print(list);
}

输出：

1 2 3 4 5 6 7 8 9 10 
10 9 8 7 6 5 4 3 2 1

正如你所看到的，实际上为链表编写C++与用C编写链表非常不同。不幸的是，你的类至少有十年没有发展了。

同样值得一提的是，如果这个类被完全实现(迭代器和我说的其他东西缺失了(，主函数看起来会更好，并允许更多的标准库使用我们的列表。

相关内容

最新更新

热门标签：