Как отсортировать данные в связанном списке по Quicksort? - PullRequest
Новая
       14

Как отсортировать данные в связанном списке по Quicksort?

0 голосов
/ 21 марта 2020

Я хочу отсортировать данные в связанном списке по быстрой сортировке. Вот мой код: 

struct stu
{

    int id; 
    char name[100]; 
    int score; 
    stu* next;
}head;

int address(stu* StudentList)
{

    //return the index of data
    int index = 0;
    stu* test = head;
    for (index = 0; test != StudentList; temp++)
    {
        test = test->next;
    }
    return index;
}

stu* section(int low)
{

    //Classification discussion on data
    stu* StudentList1=head;
    for (int i = 0; i < low; i++)
    {
        StudentList1 = StudentList1->next;
    }
    return StudentList1;
}

void swap(stu *Student1,stu *Student2)
{

    int t_id = 0, t_score = 0;
    char t_name[10] = "000";
    //exchange id 
    t_id = Student1->id;
    Student1->id = Student2->id;
    Student2->id = t_id;
    //exchange name
    strcpy(t_name, Student1->name);
    strcpy(Student1->name, Student2->name);
    strcpy(Student2->name, t_name);
    //exchange score
    t_score = Student1->score;
    Student1->score = Student2->score;
    Student2->score = t_score;
}

void sort(int low, int high)
{

    stu* StudentList1 = head, * StudentList2 = StudentList1->next;
    if (low >= high)
        return;
    else 
    {
        StudentList1=section(low);
        StudentList2 = StudentList1->next;
        stu* key = StudentList1;
        int i;
        for (int i = 0; i <= (high - low) && StudentList2 != NULL; i++)
        {
            if (StudentList2->score >= key->score)
            {
                StudentList1 = StudentList1->next;
                swap(StudentList1, StudentList2);
            }
            StudentList2 = StudentList2->next;
        }
        swap(key, StudentList1);
        int temp = address(StudentList1);
        StudentList2 = head;
        for (i = 0; StudentList2->next!=NULL;StudentList2=StudentList2->next)
        {
            if (StudentList2->next->score <= StudentList2->score)
            {
                i++;
            }
        }
        high = temp - 1;
        low = temp + 1;
        if (i < num - 1)
        {
            sort(0, high);
            sort(low, num - 1);
        }
        return;
    } 
}

Проблема в том, что программа бесконечно l oop. Я пытался изменить его, но это не помогло. Поэтому я должен превратиться в Stackoverflow. Спасибо!

Я только что изменил свой код. Но есть еще некоторые проблемы. При обработке 7 данных программа может работать хорошо. Однако при обработке 8 данных компилятор сообщил мне о переполнении стека в «разделе». Надеюсь, что вы можете указать на проблемы. Спасибо искренне!

1 Ответ

0 голосов
/ 22 марта 2020

Одна потенциальная проблема - эта строка: 

            sort(0, high);

Рекурсивные вызовы всегда должны быть как минимум на один узел меньше, чем sort (lo, hi). Могут быть и другие проблемы.

Предполагая, что это присвоение класса, я не уверен, почему быстрая сортировка была выбрана в качестве метода для сортировки связанного списка, когда сортировка слиянием обычно используется. Существует также выбор «сортировки» связанного списка путем переупорядочения данных в узлах, а не сортировки путем переупорядочения узлов в связанном списке. Поскольку в вопросе не указаны требования к назначению, я не могу быть уверен, что цель здесь.

Использование индексации для связанного списка неэффективно. Вы можете использовать быструю сортировку на основе указателя, например: 

void QuickSort(stu * lo, stu * hi);

Вот вариант схемы разбиения Lomuto, который можно преобразовать для сортировки связанного списка, в который будут преобразованы lo, hi, i, j, k на указатели на узел. 

void QuickSort(int a[], int lo, int hi);

void QuickSort(int a[])
{
    int lo = 0;
    int hi = sizeof(a)/sizeof(a[0])-1;
    if(lo >= hi)
        return;
    QuickSort(a, lo, hi);
}

void QuickSort(int a[], int lo, int hi)
{
    int p = a[lo];
    int i = lo;
    int j = lo;
    int k;
    for(k = lo+1; k <= hi; k++){
        if(a[k] < p){
            j = i++;
            std::swap(a[k], a[i]);
        }
    }
    std::swap(a[i], a[lo]);
    if(j != lo)
        QuickSort(a, lo, j);
    if(i != hi)
        QuickSort(a, i+1, hi);
}

Можно также рассмотреть метод, подобный быстрой сортировке, который создает 3 списка с каждым уровнем рекурсии, сортируя узлы вместо обмена данными. 3 списка будут узлами pivot. Рекурсия будет использоваться в 2 списках с узлами! = Pivot, тогда эти 3 списка будут объединены.

...