分段錯誤 - 數組越界

我寫了一個簡單的算法，以便當用戶輸入一個int N時，它將創建一個N×N網格，其中在同一行或列中沒有重複。該算法的工作原理有時候數字較小，但通常會引發分段錯誤。故障發生在設置網格數組元素的行中的noRowDuplicates函數中。分段錯誤 - 數組越界

我不確定爲什麼會發生這種情況，並希望得到任何幫助。提前致謝！

// Author: Eric Benjamin 
// This problem was solved using recursion. fill() is the recursive function. 


#include <iostream> 
#include <cstdlib> 
#include <time.h> 

using namespace std; 

void fillOptions(); 
void fill(int arrayPosition); 
int inputNum; 
int gridSize; 
int *grid; 
int allOptionsSize = 0; 
int *allOptions; 

int main() { 
    cout << "Please enter a number!" << endl; 
    cin >> inputNum; 
    gridSize = inputNum * inputNum; 

    grid = new int[gridSize]; 
    allOptions = new int[inputNum]; 
    for (int i = 0; i < inputNum; i++) { 
     allOptions[i] = i + 1; 
     allOptionsSize++; 
    } 

    srand((unsigned)time(0)); 
    fill(0); 

    delete[] grid; 
    delete[] allOptions; 
    return 0; 
} 

bool noColumnDuplicates(int arrPosition, int valueToCheck) { 
    for (int i = 1; i < inputNum; i++) { 
     if (arrPosition - (inputNum * i) >= 0) { 
      if (grid[arrPosition - (inputNum * i)] == valueToCheck) { 
       return false; 
      } 
     } 
    } 
    return true; 
} 

bool noRowDuplicates(int arrPosition, int valueToCheck) { 
    int rowPosition = arrPosition % inputNum; // 0 to num - 1 
    if (rowPosition > 0) { 
     for (int p = 1; p < rowPosition + 1; p++) { 
      if (grid[arrPosition - p] == valueToCheck) { 
       return false; 
      } 
     } 
    } 
    return true; 
} 

void fill(int arrayPosition) { 
    if (arrayPosition < gridSize) { 
     int randomPosition = rand() % allOptionsSize; 
     grid[arrayPosition] = allOptions[randomPosition]; 
     if (noColumnDuplicates(arrayPosition, grid[arrayPosition])) { 
      if (noRowDuplicates(arrayPosition, grid[arrayPosition])) { 
       if (arrayPosition % inputNum == 0) { 
        cout << endl; 
       } 
       cout << grid[arrayPosition] << " "; 
       fill(arrayPosition + 1); 
      } else { 
       fill (arrayPosition); 
      } 
     } else { 
      fill(arrayPosition); 
     } 
    } 
}

來源

2017-04-30 BowmanBeric

提示：停止在C++中使用C風格的數組，而是使用'std :: vector'。 – tadman

**警告**：使用['rand（）'被認爲是有害的]（https://channel9.msdn.com/Events/GoingNative/2013/rand-Considered-Harmful），強烈建議您使用適當的[標準庫中的隨機數生成器工具]（http://en.cppreference.com/w/cpp/numeric/random），它實際上產生隨機值。你使用'time（NULL）'作爲一個隨機數種子意味着如果在同一秒內運行，這將產生相同的結果，並且在很多平臺上，rand（）是[*幾乎不隨意]（http：///dilbert.com/strip/2001-10-25）。 – tadman

學習如何調試代碼的時間 – UnholySheep

你最初的呼叫填寫（）將通過0它的參數，arrayPosition。

gridSize是矩陣/數組的大小。

如果您檢查您的fill()邏輯，你會得出這樣的結論，除非arrayPosition等於或大於gridSize具有更大arrayPosition，以fill()遞歸調用會進行，無論是相同的，或1

遞增

通過fill()的所有邏輯執行路徑，當arrayPosition < gridSize導致對fill()的遞歸調用。

爲了說話，例如，如果您的數組/矩陣有一萬個值，您的fill()將嘗試至少（可能超過）一萬個嵌套遞歸調用自己！

這不會很好。當您的代碼通過操作系統分配的最大堆棧空間時，會遇到分段錯誤，操作系統拒絕爲您的進程分配更多堆棧空間。

您將需要重構您的邏輯，以避免這種失控遞歸。不幸的是，堆棧空間並不是無限的。顯示的邏輯在C++中基本上被打破了。你不能依靠你的編譯器來消除尾遞歸，並且避免爲每次遞歸函數調用消耗棧空間。

簡要回顧表明，嵌套遞歸可以簡單地用while循環代替。整體算法仍然有一定的改進空間，但至少可以解決遞歸問題。

來源

2017-04-30 22:23:37

分段錯誤 - 數組越界

回答

相關問題