2

我的班级正在通过实现一个循环单链表来模拟约瑟夫斯问题。我的代码可以编译，但是当它运行时出现分段错误：构建列表后的 11 。到目前为止，我的调试使我意识到错误发生在程序进入主函数的最后一个while循环时。我认为这与我使用 first->next 的方式有关，但我不确定。任何帮助都会很棒，谢谢。如果这不明显，我正在用 C++ 编码。

#include <iostream>
#include <string>
using namespace std;



/*
 * Node structure used by the linked list.
 */
struct Node {
    // The name stored in this node.
    string name;

    // A pointer to the next node in the list.
    Node * next;
};

/* 
 * Build the linked list
 */

class LinkedList {
    private:
        //pointer to the head of the list
        Node *head;

    public:
        // constructor for LinkedList
        LinkedList(){
            head = NULL;
        }

        /*
        * Add the given value to the list, making it the head.
        */
        void insert(string name){


            // Remember where old head was
            Node *oldHead = head;

            // allocate a new node in memory
            head = new Node;

            // set new node's fields
            head->name = name;
            head->next = oldHead;
        }

        /*
        * Remove the item on the top of the stack, returning nothing.
        */
        void remove() {
            // Remember what the new head will be
            Node* newSecond = head->next->next;

            // Deallocate the head from memory
            delete head->next;
            // Set the head to the new head
            head->next = newSecond;
        }
        /*
         * Shifts the head forward one node.
         */
        void cycle(){

            head = head->next;
        }

        Node* getHead(){
            return head;
        }

         // This is the opposite of a constructor - a destructor! You (almost)
        // never need these in Java, but in C++ they are essential because 
        // you have to clean up memory by yourself. In particular, we need to
        // empty out the stack.
        ~LinkedList() {
            // While there's a head node still left, remove the head node.
            while (head != NULL) {
                remove();
            }
        }
};



int main(){
    //create the circular linked list
    LinkedList circle;

    int people;
    cin >> people;
    string soldier;
    Node* first = circle.getHead();

    //Insert all the names
    for(int i = 0; i < people; i++){
        cin >> soldier;
        circle.insert(soldier);
    }

    //begin the killing
    while(first->next != NULL){
        circle.cycle();
        cout << " killed " << endl;
        Node* temp = first->next->next;
        circle.remove();
        first->next = temp;
    }
}
4

1 回答 1

0

该代码中有几个问题。首先是这样的：

Node* newSecond = head->next->next;

如果head->next为 NULL，那么您将获得 NULL 指针取消引用。这会导致崩溃。

但是，此特定崩溃的实际原因是：

while(first->next != NULL)

是一个 NULL 指针取消引用。一开始main()你有：

Node* first = circle.getHead();

circle那时是空的，所以first被赋值为 NULL。并且它保持 NULL 直到您在while语句中取消引用它。因此，您会崩溃。

于 2012-10-20T03:07:43.007 回答