小贝子编程

在C++中反转单链表



我尝试递归地反转单链表的实现时遇到了问题。

我读过关于这个过程的其他类似问题，然而，在我尝试在自己的程序中实现这个过程时，我遇到了不足。

这是我下面的尝试（与下面的代码略有不同）：

注意：我的列表使用root指针，该指针不包含有效数据，仅用作引用列表中数据的地址。

void IntList::reverse(Node* t_node) {
    if(t_node == NULL) {
        reverse(root);
    } else
    if(t_node->next == NULL) {
        cout << "In (swapping): " << t_node->value << endl;
        root->next = t_node;
    } else {
        cout << "In: " << t_node->value << endl;
        Node* tmp = t_node->next;
        reverse(t_node->next);
        tmp->next = t_node;
    }
    return NULL;
}

我在某个地方失去了参考，在尝试显示列表时无休止地打印。我真的不知道我犯了什么错误，但怀疑这可能与我如何处理root有关。

为了完整性，这里是整个程序（除了reverse()方法之外，所有程序都在运行）。

#ifndef INTLIST_H
#define INTLIST_H
#include<iostream>
using namespace std;
class IntList {
private:
   struct Node {
      int value;
      Node* next;
   };
   int size;
   Node* root;
   void destroy();
public:
   IntList() { root = new Node; root->next = 0; root-> value = 0; size = 0;}
   IntList(const IntList& list) { this->root = list.root; this->size = list.size; }
   ~IntList() {}
   void appendNode(int val);
   void insertNode(int pos, int val);
   void deleteNode(int pos);
   int searchNode(int val);
   int getSize() const;
   void print() const;
   Node* reverse(Node* t_node);
   int &operator[](int element) const;
   void pop_back();
   void pop_front();
   void push_back(int val);
   void push_front(int val);
};
void IntList::appendNode(int val) {
    push_back(val);
}
void IntList::insertNode(int pos, int val) {
    Node* tmp;
    Node* current = root;
    for(int i = 0; i < pos && current->next != NULL; i++) {
        current = current->next;
    }
    tmp = new Node;
    tmp->value = val;
    tmp->next = current->next;
    current->next = tmp;
    size++;
}
void IntList::deleteNode(int pos) {
    Node* tmp;
    Node* current = root;
    if(pos <= size-1) {
        for(int i = 0; i < pos; i++) {
            current = current->next;
        }
        tmp = current->next;
        current->next = tmp->next;
        delete tmp;
        size--;
    } else {
        cout << "ERROR: Out of range." << endl;
    }
}
int IntList::searchNode(int val) {
    int position = 0;
    Node* current = root->next;
    if(size != 0) {
        for(position = 0; position < size && current->value != val; position++) {
            current = current->next;
        }
    } else {
        cout << "ERROR: List is empty." << endl;
        position = -1;
    }
    return position;
}
int IntList::getSize() const {
    return size;
}
void IntList::print() const {
    Node* current = root->next;
    cout << "List: ";
    while(current != NULL) {
        cout << current->value << " ";
        current = current->next;
    }
    if(getSize() == 0) {
        cout << "Empty.";
    }
    cout << endl;
}
IntList::Node* IntList::reverse(Node* t_node) {
#define REVERSE
#ifndef REVERSE
    if(t_node == NULL) {
        reverse(root);
    } else
    if(t_node->next == NULL) {
        cout << "In (swapping): " << t_node->value << endl;
        root->next = t_node;
    } else {
        cout << "In: " << t_node->value << endl;
        Node* tmp = t_node->next;
        reverse(t_node->next);
        tmp->next = t_node;
    }
#endif //reverses list, but causes infinite loop in display
    return NULL;
}
int &IntList::operator[](int pos) const {
    Node* current = root->next;
    if(pos <= size-1) {
        for(int i = 0; i < pos; i++) {
            current = current->next;
        }
    } else {
        cout << "ERROR: Out of bounds.";
        current = NULL;
    }
    return current->value;
}
void IntList::pop_back() {
    deleteNode(size-1);
}
void IntList::pop_front() {
    deleteNode(0);
}
void IntList::push_back(int val) {
    insertNode(size, val);
}
void IntList::push_front(int val) {
    insertNode(0, val);
}
#endif
#ifndef LINKEDLIST_H
#define LINKEDLIST_H
#include<iostream>
using namespace std;
template<typename T>
class LinkedList {
private:
   struct Node {
      T value;
      Node* next;
   };
   int size;
   Node* root;
   void destroy();
public:
   LinkedList() { root = new Node; root->next = 0; root-> value = 0; size = 0;}
   LinkedList(const LinkedList &) {}
   ~LinkedList() {}
   void appendNode(T val);
   void insertNode(int pos, T val);
   void deleteNode(int pos);
   int searchNode(T val);
   int getSize() const;
   void print() const;
   void reverse(Node* t_node);
   int &operator[](int element) const;
   void pop_back();
   void pop_front();
   void push_back(T val);
   void push_front(T val);
};
template <typename T>
void LinkedList<T>::appendNode(T val) {
    push_back(val);
}
template <typename T>
void LinkedList<T>::insertNode(int pos, T val) {
    Node* tmp;
    Node* current = root;
    for(int i = 0; i < pos && current->next != NULL; i++) {
        current = current->next;
    }
    tmp = new Node;
    tmp->value = val;
    tmp->next = current->next;
    current->next = tmp;
    size++;
}
template <typename T>
void LinkedList<T>::deleteNode(int pos) {
    Node* tmp;
    Node* current = root;
    if(pos <= size-1) {
        for(int i = 0; i < pos; i++) {
            current = current->next;
        }
        tmp = current->next;
        current->next = tmp->next;
        delete tmp;
        size--;
    } else {
        cout << "ERROR: Out of range." << endl;
    }
}
template <typename T>
int LinkedList<T>::searchNode(T val) {
    int position = 0;
    Node* current = root->next;
    if(size != 0) {
        for(position = 0; position < size && current->value != val; position++) {
            current = current->next;
        }
    } else {
        cout << "ERROR: List is empty." << endl;
        position = -1;
    }
    return position;
}
template <typename T>
int LinkedList<T>::getSize() const {
    return size;
}
template <typename T>
void LinkedList<T>::print() const {
    Node* current = root->next;
    cout << "List: ";
    while(current != NULL) {
        cout << current->value << " ";
        current = current->next;
    }
    if(getSize() == 0) {
        cout << "Empty.";
    }
    cout << endl;
}
template <typename T>
void LinkedList<T>::reverse(Node* t_node) {
/*
    if(t_node == NULL) {
        reverse(root);
    } else
    if(t_node->next == NULL) {
        cout << "In (swapping): " << t_node->value << endl;
        root->next = t_node;
    } else {
        cout << "In: " << t_node->value << endl;
        Node* tmp = t_node->next;
        reverse(t_node->next);
        tmp->next = t_node;
    }
*/ //reverses list, but causes infinite loop in display
}
template <typename T>
int &LinkedList<T>::operator[](int pos) const {
    Node* current = root->next;
    if(pos <= size-1) {
        for(int i = 0; i < pos; i++) {
            current = current->next;
        }
    } else {
        cout << "ERROR: Out of bounds.";
        current = NULL;
    }
    return current->value;
}
template <typename T>
void LinkedList<T>::pop_back() {
    deleteNode(size-1);
}
template <typename T>
void LinkedList<T>::pop_front() {
    deleteNode(0);
}
template <typename T>
void LinkedList<T>::push_back(T val) {
    insertNode(size, val);
}
template <typename T>
void LinkedList<T>::push_front(T val) {
    insertNode(0, val);
}
#endif
//test driver
int main() {
    IntList i_list;
    int n;
    cout << "Appending node: value = " << 0 << endl;
    i_list.appendNode(0);
    i_list.print();
    cout << endl;
    n = 5;
    cout << "Inserting nodes (at their values). Node values = { ";
    for(int i = 0; i < n; i++) {
        cout << i << " ";
        i_list.insertNode(i,i);
    }
    cout << "}" << endl;
    i_list.print();
    cout << endl;
    cout << "Deleting node at position: " << i_list.getSize()-1 << endl;
    i_list.deleteNode(i_list.getSize()-1);
    i_list.print();
    cout << endl;
    cout << "Searching for value: " << 3 << endl;
    cout << "Found at: " << i_list.searchNode(3) << endl;
    cout << endl;
    i_list.print();
    cout << "List size: " << i_list.getSize() << endl;
    cout << endl;
    n = 3;
    cout << "Calling node at list[" << n << "]: " << i_list[n] << endl;
    cout << endl;
    i_list.print();
    cout << "Deleting node from back position." << endl;
    i_list.pop_back();
    i_list.print();
    cout << endl;
    i_list.print();
    cout << "Deleting node from front position." << endl;
    i_list.pop_front();
    i_list.print();
    cout << endl;
    n = 9;
    i_list.print();
    cout << "Adding node (value = " << n << ") to back position." << endl;
    i_list.push_back(n);
    i_list.print();
    cout << endl;
    n = 8;
    i_list.print();
    cout << "Adding node (value = " << n << ") to front position." << endl;
    i_list.push_front(n);
    i_list.print();
    cout << endl;
    i_list.print();
    cout << "Copying list to new list." << endl;
    IntList t_list(i_list);
    cout << endl;
    cout << "List copy:" << endl;
    t_list.print();
    cout << endl;
    /*
     * Showing functionality transfers over to LinkedList template class
     * generally, for primitive data types (lacks absolutely generality
     * for data which can't be passed directly to cout).
     */
    cout << "List functionality transfers generally to LinkedList class:" << endl;
    LinkedList<int> int_list;
    LinkedList<double> double_list;
    LinkedList<char> char_list;
    cout << "Appending nodes:" << endl;
    n = 5;
    for(int i = 0; i < n; i++){
        int_list.appendNode(i);
    }
    int_list.print();
    n = 5;
    for(int i = 0; i < n; i++){
        double_list.appendNode(i+0.1);
    }
    double_list.print();
    n = 5;
    for(int i = 0; i < n; i++){
        char_list.appendNode('A' + i);
    }
    char_list.print();
    cout << "Removing nodes:" << endl;
    n = 5;
    for(int i = 0; i < n; i++){
        int_list.pop_back();
    }
    int_list.print();
    n = 5;
    for(int i = 0; i < n; i++){
        double_list.pop_back();
    }
    double_list.print();
    n = 5;
    for(int i = 0; i < n; i++){
        char_list.pop_back();
    }
    char_list.print();
    return 0;
}

编辑：我已经修改了我的算法，我相信它在算法上是有效的，但在功能上它可能会做一些导致内存问题的事情。我不确定为什么会这样，但它是：

void IntList::reverse() {
    IntList tmp(*this);
    int list_size = size;
    for(int i = 0; i < list_size; i++) {
        this->insertNode(i, tmp[tmp.getSize()-1]);
        this->pop_back();
        tmp.pop_back();
    }
}

事实上，如果我的[]运算符重载在这个方法中起作用（由于某种原因，它不是？），我可以取消tmp列表，只将列表中的最后一个值直接引用为this[size-1]。

这里的问题是什么？

您的问题是，在reverse()之后，列表中的最后一个元素将指向根元素，而不是指向null。一种解决方案可以是对这种情况进行明确的检查，这样你就会得到：

void IntList::reverse(Node* t_node) {
    if(t_node == NULL) {
        reverse(root);
        return;
    }
    if(t_node->next == NULL) {
        cout << "In (swapping): " << t_node->value << endl;
        root->next = t_node;
    } else {
        cout << "In: " << t_node->value << endl;
        Node* tmp = t_node->next;
        reverse(t_node->next);
        // If this node was the first node it will now be the last
        if (t_node == root) {
            tmp->next = NULL;
        } else {
            tmp->next = t_node;
        }
    }
}

不过，如果有可能推翻清单中的一个子部分，那就行不通了。如果这是您需要的，那么您可能需要使用一个helper函数来处理除第一个元素之外的所有元素。

假设我们有IntList｛1,2,3｝，它实际上有这样的形式：

0 -> 1 -> 2 -> 3

然后我们调用reverse(root)，使得t_node具有与root相同的值（因此指向（0））。

Node* tmp = t_node->next;

所以tmp指向（1）。

reverse(t_node->next);

假设这是有效的，并且列表现在是0->1->3->2

tmp->next = t_node;

所以现在1->0。该列表现在是一个循环，其他节点已经丢失。

目前还不清楚您打算让这个函数做什么，但您一定误解了什么。

编辑：当您不了解低级机制时，您正在尝试高级解决方案。

您的复制构造函数：

IntList(const IntList& list) { this->root = list.root; this->size = list.size; }

执行我们所说的"浅拷贝"；它复制指针成员，但不复制它们所指向的东西。如果你有一个列表A，看起来像这样：

0->1->2->3

然后调用IntList B(A);，你会得到这样的东西：

   0
   |
   v
0->1->2->3

如果您调用A.pop_back()和B.pop_back()，您认为会发生什么

更重要的是，你想做什么你想知道如何编写递归函数，还是不再需要了？

相关内容

  • 没有找到相关文章

最新更新


热门标签：

javascript python java c# php android html jquery c++ css ios sql mysql arrays asp.net json python-3.x ruby-on-rails .net sql-server django objective-c excel regex ruby linux ajax iphone xml vba spring asp.net-mvc database wordpress string postgresql wpf windows xcode bash git oracle list vb.net multithreading eclipse algorithm macos powershell visual-studio image forms numpy scala function api selenium