Quicksort引发堆栈溢出错误

Question

好的，我的整个程序如下所示。出于某种原因，当分区函数被调用时，它会抛出堆栈溢出错误。我倾倒了代码并寻求帮助。你很好的程序员是我最后的希望。其他一切工作正常，或至少它需要。如果你能看到Quicksort和分区功能，并看看能否弄清楚我在哪里搞砸了，我将不胜感激。

#include <iostream> 
    #include <string> 
    #include <fstream> 
    #include <vector> 
    #include <time.h> 
    #include <stdio.h> 
    #include <dos.h> 

using namespace std; 

vector<int> DataIn(ifstream&); 

void quickSort(int, int, vector<int>&, int); 

int partition(vector<int>& list, int start, int end) 
{ 
    int pivot = list[start]; 
    int index = start; 

    for (int i = start + 1; i < end; i++) 
    { 
     if (list[i] <= pivot) 
     { 
      swap(list[index], list[i]); 
     } 
    } 

    index++; 

    if (index != end) 
    { 
     swap(list[index], list[start]); 
    } 
    return index; 
} 

void swap(int& a, int& b) 
{ 
    int temp = a; 
    a = b; 
    b = temp; 
} 

int main() 
{ 
    int repeat = 0; 
    int fileCount = 1; 

    while (repeat == 0) 
    { 

     int loadFail = NULL; 

     cout << "\nWhat is the file name: "; 

     string fileName; 
     cin >> fileName; 

     ifstream fileIn(fileName); 

     do 
     { 
      if (fileIn.fail()) 
      { 
       loadFail = 1; 
       cout << "\nUnable to open file. Please try again:"; 

       cout << "\nWhat is the file name: "; 

       cin >> fileName; 
       ifstream fileIn(fileName); 

       if (fileIn.good()) 
       { 
        loadFail = 0; 
       } 
      } 
      else 
      { 
       loadFail = 0; 
      } 
     } while (loadFail == 1); 

     vector<int> fileData; 

     fileData = DataIn(fileIn); 

     int fileLength = fileData.size(); 

     void quickTime = quickSort(0, fileLength - 1, fileData, fileCount); 


    return 0; 
}; 

vector<int> DataIn(ifstream& read) 
{ 
    vector<int> data; 
    int dataLine; 

    while (!read.eof()) 
    { 
     read >> dataLine; 
     read.ignore(); 
     data.push_back(dataLine); 
    } 

    return data; 
} 

void quickSort(int begin, int end, vector<int>& list, int fileNum) 
{  
    int mid = 0; 

    if (end > begin) 
    {  
     mid = partition(list, begin, end); 
     quickSort(begin, mid, list, fileNum); 
     quickSort(mid + 1, end, list, fileNum); 
    } 

    return elapsed_time;  
} 

Answer 1

您在发布的代码中有几个主要问题。

1. 您试图在void函数（quickSort）中返回一个值。另外我也没有看到你声明变量的地方。

2. 您正在声明一个类型为void的变量，这是错误的。一个void函数返回void，这意味着它不返回任何东西。

3. 在main（）函数的结尾处有缺失的括号。

4. while循环将永远不会停止，因为重复总是以0

5. 在你的快速排序功能相同，在第一次循环调应该有中期的1

6. 你的分区功能逻辑错误

此外filenum变量不在任何地方使用。

这是您的代码的修改版本，它的工作。

#include <iostream> 
#include <string> 
#include <fstream> 
#include <vector> 
#include <time.h> 
#include <stdio.h> 
#include <dos.h> 

using namespace std; 

vector<int> DataIn(ifstream&); 

void quickSort(int, int, vector<int>&); 

int partition(vector<int>& arr, int left, int right) 
{ 
    int pivot = arr[left]; 
    while (left != right) 
    { 
     if (arr[left] > arr[right]) 
     { 
      swap(arr[left], arr[right]); 
     } 
     if (pivot == arr[left]) 
      right--; 
     else 
      left++; 
    } 
    return left; 
} 

void swap(int& a, int& b) 
{ 
    int temp = a; 
    a = b; 
    b = temp; 
} 

int main() 
{ 
    int repeat = 0; 
    int fileCount = 1; 

     int loadFail = NULL; 

     cout << "\nWhat is the file name: "; 

     string fileName; 
     cin >> fileName; 

     ifstream fileIn(fileName); 

     do 
     { 
      if (fileIn.fail()) 
      { 
       loadFail = 1; 
       cout << "\nUnable to open file. Please try again:"; 

       cout << "\nWhat is the file name: "; 

       cin >> fileName; 
       ifstream fileIn(fileName); 

       if (fileIn.good()) 
       { 
        loadFail = 0; 
       } 
      } 
      else 
      { 
       loadFail = 0; 
      } 
     } while (loadFail == 1); 

     vector<int> fileData; 

     fileData = DataIn(fileIn); 

     int fileLength = fileData.size(); 

     quickSort(0, fileLength - 1, fileData); 


     return 0; 
} 

    vector<int> DataIn(ifstream& read) 
    { 
     vector<int> data; 
     int dataLine; 

     while (!read.eof()) 
     { 
      read >> dataLine; 
      read.ignore(); 
      data.push_back(dataLine); 
     } 

     return data; 
    } 

    void quickSort(int begin, int end, vector<int>& list) 
    { 
     int mid = 0; 

     if (end > begin) 
     { 
      mid = partition(list, begin, end); 
      quickSort(begin, mid-1, list); 
      quickSort(mid + 1, end, list); 
     } 
    }