鏈接列表（C++）的分段錯誤

Question

當下列程序運行時，出現分段錯誤。問題究竟在哪裏？

頭文件：

#ifndef MAIN_SAVITCH_NODE1_H 
#define MAIN_SAVITCH_NODE1_H 
#include <cstdlib> // Provides size_t and NULL 

namespace main_savitch_5 
{ 
    class node 
    { 
    public: 
     // TYPEDEF 
     typedef double value_type; 

     // CONSTRUCTOR 
     node(
      const value_type& init_data = value_type(), 
      node* init_link = NULL 
      ) 
     { 
      data_field = init_data; link_field = init_link; 
     } 

     // Member functions to set the data and link fields: 
     void set_data(const value_type& new_data) { data_field = new_data; } 
     void set_link(node* new_link)    { link_field = new_link; } 

     // Constant member function to retrieve the data: 
     value_type data() const { return data_field; } 

     // Constant member functions to retrieve the link: 
     node* link() const   { return link_field; } 

    private: 
     value_type data_field; 
     node* link_field; 
    }; 

    // FUNCTIONS for the linked list toolkit 
    std::size_t list_length(const node* head_ptr); 
    void list_head_insert(node*& head_ptr, const node::value_type& entry); 
    void list_insert(node* previous_ptr, const node::value_type& entry); 
    node* list_search(node* head_ptr, const node::value_type& target); 
    node* previous_to_min(node* marker_ptr); 
    node* list_locate(node* head_ptr, std::size_t position); 
    void list_head_remove(node*& head_ptr); 
    void list_remove(node* previous_ptr); 
    void list_clear(node*& head_ptr); 
    void list_copy(const node* source_ptr, node*& head_ptr, node*& tail_ptr); 
    void print_list(const node* head_ptr); 

} 

#endif 

實現文件（這些都不是我的）

#include "node1.h" 
#include <cassert> // Provides assert 
#include <iostream> 
#include <cstdlib> // Provides NULL and size_t 
using namespace std; 

namespace main_savitch_5 
{ 
    size_t list_length(const node* head_ptr) 
     // Library facilities used: cstdlib 
    { 
     const node *cursor; 
     size_t answer; 

     answer = 0; 
     for (cursor = head_ptr; cursor != NULL; cursor = cursor->link()) 
      ++answer; 

     return answer; 
    } 

    void print_list(const node* head_ptr) 
    { 
     const node *cursor; 
     cout << endl; 
     for (cursor = head_ptr; cursor != NULL; cursor = cursor->link()) cout << cursor->data() << " "; 
     cout << endl; 
    } 

    void list_head_insert(node*& head_ptr, const node::value_type& entry) 
    { 
     head_ptr = new node(entry, head_ptr); 
    } 

    void list_insert(node* previous_ptr, const node::value_type& entry) 
    { 
     node *insert_ptr; 

     insert_ptr = new node(entry, previous_ptr->link()); 
     previous_ptr->set_link(insert_ptr); 
    } 

    node* list_search(node* head_ptr, const node::value_type& target) 
     // Library facilities used: cstdlib 
    { 
     node *cursor; 

     for (cursor = head_ptr; cursor != NULL; cursor = cursor->link()) 
      if (target == cursor->data()) 
       return cursor; 
     return NULL; 
    } 

    node* previous_to_min(node* marker_ptr) 
    { 
     node * cursor; 
     node * pre_cursor; 
     node * current_min_prev_cursor; 
     int current_min; 

     pre_cursor = marker_ptr; 
     cursor = marker_ptr->link(); 
     current_min = cursor->data(); 
     current_min_prev_cursor = pre_cursor; 

     while (cursor != NULL) 
     { 
      if (cursor->data() < current_min) 
      { 
       current_min = cursor->data(); 
       current_min_prev_cursor = pre_cursor; 
      } 

      pre_cursor = cursor; 
      cursor = cursor->link(); 
     } 
     return current_min_prev_cursor; 
    } 










    node* list_locate(node* head_ptr, size_t position) 
     // Library facilities used: cassert, cstdlib 
    { 
     node *cursor; 
     size_t i; 

     assert(0 < position); 
     cursor = head_ptr; 
     for (i = 1; (i < position) && (cursor != NULL); i++) 
      cursor = cursor->link(); 
     return cursor; 
    } 


    void list_head_remove(node*& head_ptr) 
    { 
     node *remove_ptr; 

     remove_ptr = head_ptr; 
     head_ptr = head_ptr->link(); 
     delete remove_ptr; 
    } 

    void list_remove(node* previous_ptr) 
    { 
     node *remove_ptr; 

     remove_ptr = previous_ptr->link(); 
     previous_ptr->set_link(remove_ptr->link()); 
     delete remove_ptr; 
    } 

    void list_clear(node*& head_ptr) 
     // Library facilities used: cstdlib 
    { 
     while (head_ptr != NULL) 
      list_head_remove(head_ptr); 
    } 

    void list_copy(const node* source_ptr, node*& head_ptr, node*& tail_ptr) 
     // Library facilities used: cstdlib 
    { 
     head_ptr = NULL; 
     tail_ptr = NULL; 

     // Handle the case of the empty list. 
     if (source_ptr == NULL) 
      return; 

     // Make the head node for the newly created list, and put data in it. 
     list_head_insert(head_ptr, source_ptr->data()); 
     tail_ptr = head_ptr; 

     // Copy the rest of the nodes one at a time, adding at the tail of new list. 
     source_ptr = source_ptr->link(); 
     while (source_ptr != NULL) 
     { 
      list_insert(tail_ptr, source_ptr->data()); 
      tail_ptr = tail_ptr->link(); 
      source_ptr = source_ptr->link(); 
     } 
    } 

} 

我的主文件

#include <cstdlib> 
#include <ctime> 
#include <iostream> 
#include <cassert> 
#include "node1.h" 

using namespace main_savitch_5; 

void list_sort(node* &head_ptr); 

int main() 
{ 
    unsigned seed = time(0); 
    size_t n; 
    node *head; 
    node *current; 

    srand(seed); 

    std::cout << "How many items would you like to sort?\n"; 
    std::cin >> n; 
    assert(n > 0); // Ensure the list is not empty 

    list_head_insert(head, 1 + rand() % 1000); 
    current = head; 

    for (size_t i = 1; i < n; i++) 
    { 
     list_insert(current, (1 + rand() % 1000)); 
     current = current->link(); 
    } 

    std::cout << "Unsorted list:\n"; 
    print_list(head); 

    list_sort(head); 

    std::cout << "Sorted list:\n"; 
    print_list(head); 

    list_clear(head); 

    return 0; 
} 

    void list_sort(node* &head_ptr) 
    { 
     node* marker; 
     node* min_node; 
     node* temp; 
     node* cursor; 

     min_node = previous_to_min(head_ptr); 
     // Set a pointer to the minimum data value in the list 
     if (head_ptr->data() < min_node->data()) 
      marker = head_ptr; 
     else 
     { 
      // If the head pointer does not hold the smallest value, 
      // swap it with the node containing the min value 
      temp = min_node->link(); 
      min_node->set_link(temp->link()); 
      temp->set_link(head_ptr); 
      head_ptr = temp; 
      marker = head_ptr; 
     } 

     while (marker->link()->link() != NULL) 
     { 
      cursor = previous_to_min(marker); 
      // Find the smallest value of our new sublist 

      if (cursor == marker) 
       marker = marker->link(); 
      else 
      { 
       // Swap the head of the sublist with the new min value 
       temp = cursor->link(); 
       cursor->set_link(temp->link()); 
       temp->set_link(marker->link()); 
       marker->set_link(temp); 
       marker = marker->link(); 
      } 
     } 
    } 

段故障呼叫後立即發生print_list（）第一次。

Answer 1

的問題是，你開始了你的清單與未設置爲NULL鏈接節點：

在你main功能，你有這樣的：

node *head; 
     //... 
    list_head_insert(head, 1 + rand() % 1000); 

然而，list_head_insert功能用途第一個參數的值設置下一個鏈接。

void list_head_insert(node*& head_ptr, const node::value_type& entry) 
{ 
    head_ptr = new node(entry, head_ptr); 
} 

由於指針爲未初始化的，不管垃圾它被設置爲創建一個新的node時調用list_head_insert使用前爲head_ptr，如下所示：

node(const value_type& init_data = value_type(), 
    node* init_link = NULL) 
{ 
    data_field = init_data; 
    link_field = init_link; // oh no. 
} 

什麼捲起發生每個添加到鏈表的新節點都依賴於前一節點的鏈接值。因此，當您構建鏈接列表時，這個不良鏈接值將從節點傳遞到節點，並最終被用作列表的哨點節點。

由於哨兵節點有一個垃圾值，當節點爲NULL時停止的循環都是錯誤的（因爲沒有NULL）。

因此，解決辦法是設置head節點爲NULL在main開頭：

node *head = NULL; 

現在，這將設置鏈接爲NULL，然後該值將被用作前哨淋巴結。