Bubble Сортировка в структурированном списке, заполненном CSV-файлом - PullRequest
Новая
       5

Bubble Сортировка в структурированном списке, заполненном CSV-файлом

0 голосов
/ 30 ноября 2011

Я загружаю файл .csv, который заполняет мою структуру 

typedef struct list TList;
    struct list {
        int index;
        char data;
        TList* prox;
    };

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

Я попробовал следующее 

void bubble(TList *list, int siz) {
    int c = 0;
    int x, y, temp;

    for (x = (siz - 1); x >= 0; x--) {
        c++;
        for (y = 1; y <= x; y++) {
            c++;
            if (list->index[y - 1] > list->index[y]) {
                temp = list->index[y - 1];
                list->index[y - 1] = list->index[y];
                list->index[y] = temp;
            }
        }
    }
    printf("\nNeeded Steps: %i\n", c);
}

Я думаю, это потому, что list->index[y].Это как таблица в базе данных ... в позиции 0 (индекс), у меня есть данные и указатель на следующий узел.С list->index[..] я хочу передать позицию и получить этот узел, как массив.Это связанный список, и prox должен указывать на следующий узел.Я заполнил свой список данными, полученными из CSV-файла, и list->prox указывает на следующий узел.

Ответы [ 4 ]

1 голос
/ 30 ноября 2011

STL обеспечивает хороший встроенный алгоритм сортировки. чек http://www.cplusplus.com/reference/algorithm/

1 голос
/ 30 ноября 2011 
typedef struct list TList;
struct list {
    int index;
    char data;
    TList* prox;

    //give the list an [] like an array
    char& operator[](int index) {
        TList* cur = this;
        while(cur->index != index) {
            if (cur->prox == NULL)
                throw std::exception("INVALID INDEX");
            cur = cur->prox;
        }
        return cur->data;
    }
};

Это позволит вам использовать оператор индекса в вашем связанном списке как массив. 

        if ((*list)[y - 1] > (*list)[y]) {
0 голосов
/ 30 ноября 2011

Почему вы хотите использовать пузырьковую сортировку? Это классический пример алгоритма, который по сути всегда неправильный выбор!

Если вы делаете это в реальном коде, просто используйте стандартную коллекцию (std::list, если вы настаиваете на связанном списке, вероятно, std::vector, если вы в здравом уме), а затем используйте std::sort, чтобы сделать сортировка.

Если вы делаете это для чего-то вроде домашней работы и действительно должны использовать свою собственную структуру списка и ужасный алгоритм, тогда вы реализуете свою итерацию и сравнение, используя указатели вместо индексов, поэтому ваше сравнение будет выглядеть примерно так 

if (pos->index > pos->next->index)
    /* swap items */

Вы (вероятно) также захотите основывать, по крайней мере, свой внутренний цикл на операциях с указателями, а не на целых числах и индексировании - его операция приращения, вероятно, будет выглядеть примерно так: pos=pos->next.

Также обратите внимание, что с односвязным списком трудно выполнить своп с текущим узлом, поэтому вам часто требуется рассмотреть следующий узел и следующий после него (по крайней мере, когда вы можете - т. Е. Не иметь дело с первый узел).

0 голосов
/ 30 ноября 2011

Ваш внутренний if неверен (как условный, так и обмен). Вы хотите поменять местами весь TList, а не только индексы каждого TList. Например, если у вас есть два списка TL, как это: 

TList[0]       TList[1]
Index1         Index0
"Data for 1"   "Data for 0"

после замены вы хотите 

TList[0]       TList[1]
Index0         Index1
"Data for 0"   "Data for 1"

Вместо этого ваш внутренний цикл делает это: 

TList[0]       TList[1]
Index0         Index1
"Data for 1"   "Data for 0"

Но на самом деле это не так, потому что ваше условное условие не работает, как указала в комментариях Утка Мунинг. Подсказка: вы не хотите ничего менять ни в одном из списков TL, вы просто хотите изменить их расположение относительно друг друга.

...