c++ - Quicksort 出现段错误

Question

int main() {
    int yearsToLoop;
    cin >> yearsToLoop;
    annual_stats* ptr = new annual_stats [yearsToLoop];
    for (int i = 0; i < yearsToLoop; i++)
    {
        int annualYear;
        cin >> annualYear;
        ptr[i].year = annualYear;
        for (int j = 0; j < NO_TEAMS; j++)
        {
            string team_name;
            getline(cin, team_name, '\t');
            strcpy(ptr[i].teams[j].team_name, team_name.c_str());

            int games;
            cin >> games;
            ptr[i].teams[j].games = games;

            float pts_per_game;
            cin >> pts_per_game;
            ptr[i].teams[j].pts_per_game = pts_per_game;

            int total_points;
            cin >> total_points;
            ptr[i].teams[j].total_points = total_points;

            int scrimmage_plays;
            cin >> scrimmage_plays;
            ptr[i].teams[j].scrimmage_plays = scrimmage_plays;

            float yds_per_game;
            cin >> yds_per_game;
            ptr[i].teams[j].yds_per_game = yds_per_game;

            float yds_per_play;
            cin >> yds_per_play;
            ptr[i].teams[j].yds_per_play = yds_per_play;

            float first_per_game;
            cin >> first_per_game;
            ptr[i].teams[j].first_per_game = first_per_game;

            int third_md;
            cin >> third_md;
            ptr[i].teams[j].third_md = third_md;

            int third_att;
            cin >> third_att;
            ptr[i].teams[j].third_att = third_att;

            int third_pct;
            cin >> third_pct;
            ptr[i].teams[j].third_pct = third_pct;

            int fourth_md;
            cin >> fourth_md;
            ptr[i].teams[j].fourth_md = fourth_md;

            int fourth_att;
            cin >> fourth_att;
            ptr[i].teams[j].fourth_att = fourth_att;

            int fourth_pct;
            cin >> fourth_pct;
            ptr[i].teams[j].fourth_pct = fourth_pct;

            int penalties;
            cin >> penalties;
            ptr[i].teams[j].penalties = penalties;

            int pen_yds;
            cin >> pen_yds;
            ptr[i].teams[j].pen_yds = pen_yds;

            string top_per_game;
            cin >> top_per_game;
            strcpy(ptr[i].teams[j].top_per_game, top_per_game.c_str());

            int fum;
            cin >> fum;
            ptr[i].teams[j].fum = fum;

            int lost;
            cin >> lost;
            ptr[i].teams[j].lost = lost;

            int to;
            cin >> to;
            ptr[i].teams[j].to = to;
        }
    }
    int numberOfC;
    cin >> numberOfC;

    for (int i = 0; i < numberOfC; i++)
    {
        string command;
        cin >> command;

        if(command == "qsort") {
            string command2;
            cin >> command2;
            int num = atoi(command2.c_str());
            if (num >= 2010)
            {
                string year;
                year = command2;
                string field;
                cin >> field;
                string order;
                cin >> order;
                qSortYearFieldOrder(year, field, order, ptr, yearsToLoop);
            }
        }

所以就在(部分)main 中，我获得了所有输入，然后使用一些输入调用了一个函数。我目前遇到 qSortYearFieldOrder(year, field, order, ptr, yearsToLoop) 错误。

void qSortYearFieldOrder(string year, string field, string order, annual_stats* ptr, int amountYears) {
    int yearIndex = 0;
    if  (amountYears == 1) {
        yearIndex == 0;
    }
    else {
        if (year == "2010") {
            yearIndex = 0;
        }
        else if (year == "2011") {
            yearIndex = 1;
        }
        else if (year == "2012") {
            yearIndex = 2;
        }
        else if (year == "2013") {
            yearIndex = 3;
        }
        else if (year == "2014") {
            yearIndex = 4;
        }
        else if (year == "2015") {
            yearIndex = 5;
        }
    }

    if (field == "team_name") {
        if (order == "decr") {


            cout << "\n\nDecreasing Order" << endl;
            for (int i = 0; i < NO_TEAMS; i++) {
                cout << ptr[yearIndex].teams[i].team_name;
            }
        }
        else if (order == "incr") {

            cout << "\n\nIncreasing Order" << endl;
            for (int i = 0; i < NO_TEAMS; i++) {
                cout << ptr[yearIndex].teams[NO_TEAMS - 1 - i].team_name;
            }
        }
    }
    else if (field == "games") {
        if (order == "decr") {
             quicksortGames(ptr, 0, NO_TEAMS - 1, yearIndex, order);
            cout << "TEAM" << "\t\t" << "Number Of Games Decreasing";
            for (int i = 0; i < NO_TEAMS; i++) {
                cout << ptr[yearIndex].teams[i].team_name << " " << ptr[yearIndex].teams[NO_TEAMS - 1 - i].games;
            }
        }
        else if (order == "incr") {
            quicksortGames(ptr, 0, NO_TEAMS - 1, yearIndex, order);  
            cout << "TEAM" << "\t\t" << "Number Of Games Increasing";
            for (int i = 0; i < NO_TEAMS; i++) {
                cout << ptr[yearIndex].teams[NO_TEAMS - 1 - i].team_name << " " << ptr[yearIndex].teams[i].games;
            }
        }
    }

然后在这个函数中，我根据代码所在的字段以及递增/递减顺序对代码进行排序。

void quicksortGames(annual_stats* pointer, int firstIndex, int lastIndex, int yearIndex, string order)
{
    //declaring index variables
    int pivotIndex, temp, index1, index2;

    if(firstIndex < lastIndex)
    {
        //assigning first element index as pivot element
        pivotIndex = pointer[yearIndex].teams[firstIndex].games;
        index1 = pointer[yearIndex].teams[firstIndex].games;
        index2 = pointer[yearIndex].teams[lastIndex].games;

        //Sorting in Ascending order with quick sort
        while(index1 < index2)
        {
            while(pointer[yearIndex].teams[index1].games <= pointer[yearIndex].teams[pivotIndex].games && index1 < lastIndex)
            {
                index1++;
            }
            while(pointer[yearIndex].teams[index2].games <= pointer[yearIndex].teams[pivotIndex].games)
            {
                index2--;
            }

            if(index1<index2)
            {
                //Swapping opertation
                temp = pointer[yearIndex].teams[index1].games;
                pointer[yearIndex].teams[index1].games = pointer[yearIndex].teams[index2].games;
                pointer[yearIndex].teams[index2].games = temp;
            }
        }

        //At the end of first iteration, swap pivot element with index2 element
        temp =  pointer[yearIndex].teams[pivotIndex].games;
        pointer[yearIndex].teams[pivotIndex].games =  pointer[yearIndex].teams[index2].games;
        pointer[yearIndex].teams[index2].games = temp;

        //Recursive call for quick sort, with partiontioning
        quicksortGames(pointer, firstIndex, index2-1, yearIndex, order);
        quicksortGames(pointer, index2+1, lastIndex, yearIndex, order);
    }
}

此功能用于快速排序游戏。我单独做了它，因为快速排序是递归的，因此我不能在以前的函数中快速排序。我从这个网站得到了快速排序:http://www.cprogramto.com/c-program-quick-sort/ .

基本上，我试图获取所有输入，将它们放入一个按字段/顺序排序的函数中，然后专门为该字段调用快速排序。

代码可以编译，但每当我尝试使用类似于 qsort 2015 games decr 等的代码运行代码时，我目前都会收到段错误 11 错误。当我省略 qsort 时，我的代码运行并适用于另一个排序算法(此处未显示)因此我确定错误在快速排序范围内。有人可以帮我看看我的错误到底在哪里吗？

Answer 1

考虑:

    pivotIndex = pointer[yearIndex].teams[firstIndex].games;
    index1 = pointer[yearIndex].teams[firstIndex].games;
    index2 = pointer[yearIndex].teams[lastIndex].games;
    ...
    while(pointer[yearIndex].teams[index1].games <= pointer[yearIndex].teams[pivotIndex].games && index1 < lastIndex)

您将数组索引(index1、index2)设置为游戏数。

不能保证少于团队数组中元素的数量。

因此，您最终会越界访问团队数组 == 段错误。

更多信息:将您的代码与您从中获取算法的站点进行比较:

   ...
   index2 = lastIndex;

    //Sorting in Ascending order with quick sort
    while(index1 < index2)
    {
        while(array[index1] <= array[pivotIndex] && index1 < lastIndex)
        {
            index1++;
    ....

Index 是数组中的位置，其中 array[index] 是值。在您的情况下，您正在(内部)while 循环中正确进行比较:

    while(pointer[yearIndex].teams[index1].games <= pointer[yearIndex].teams[pivotIndex].games && index1 < lastIndex)

但是你设置的索引不正确:

    index1 = pointer[yearIndex].teams[firstIndex].games;

为了更具体一点，假设有 10 支球队，但第一支球队(第 0 支球队)打了 1000 场比赛。然后你的代码会这样做:

    index1 = pointer[yearIndex].teams[0].games; // index1=1000

    while(pointer[yearIndex].teams[1000].games <= 
              pointer[yearIndex].teams[1000].games && 1000 < 9)

问题是，如果只有 10 个团队，那么 teams[1000] 是无效的，当您在 C 中像这样越界访问数组时，您会遇到段错误(如果幸运的话)或内存损坏和/或安全漏洞(如果你不走运)。

此外，评论中提出的学习源代码调试器(GDB 或其他 - 取决于您的平台)的建议对于学习 C 语言至关重要。