在由 csv 文件填充的结构化列表中进行冒泡排序

Question

我加载了一个填充我的结构的 .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 指向下一个节点。

Answer 1

STL 提供了很好的内置排序算法。检查 http://www.cplusplus.com/reference/algorithm/

Answer 2

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]) {

Answer 3

您的内部 if 不正确（if 条件和交换）。
您想要交换整个 TList，而不仅仅是每个 TList 的索引。例如，如果你有两个像这样的 TList：

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"

但它实际上并没有这样做，因为你的 if 条件不起作用，正如 Mooing Duck 在评论中指出的那样。提示：您不想更改任何 TList 中的任何内容，您只想更改它们之间的相对位置。

Answer 4

为什么哦为什么你想使用冒泡排序？这是算法的经典示例，但本质上总是是错误的选择！

如果您在实际代码中执行此操作，只需使用标准集合（如果您坚持使用链接列表，则可以使用 std::list ，如果您坚持使用链表，则可能使用 std::vector ）保持理智），然后使用 std::sort 进行排序。

如果您正在为诸如家庭作业之类的事情执行此操作，并且确实必须使用自己的列表结构和可怕的算法，那么您将使用指针而不是下标来实现迭代和比较，因此您的比较将类似于

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

您将（可能）还希望至少将内部循环基于指针操作而不是整数和索引 - 它的增量操作可能类似于 pos=pos->next 。

另请注意，对于单链表，很难进行涉及当前节点的交换，因此您经常需要考虑下一个节点及其后的节点（至少当您可以时 - 即，不处理第一个节点）。