链表的排序插入

Question

链表的排序插入

5

你好，

我已经尝试了12个小时来调试我的循环链表问题。该函数接收一个抽象数据类型（ADT），其中包含一个起始位置和光标字段。初始虚拟单元格指向自己。插入元素，不允许重复元素。

    int setInsertElementSorted(setADT buffer, setElementT E)
    {
        bool isUnique = true;
        cellT *previous;

        previous = buffer->start;
        buffer->cursor = buffer->start->next;

        while(buffer->cursor != buffer->start){
            if(buffer->cursor->value == E){
                isUnique = false;
            } else if(E < buffer->cursor->value)
                break;
              else {   
                previous = buffer->cursor;
                buffer->cursor = buffer->cursor->next;
            }
        }

        if(isUnique != false){
            cellT *newNode = malloc(sizeof(cellT));
            newNode->value = E;
            previous->next = newNode;
            newNode->next = buffer->cursor;

            buffer->count++;
            return (buffer->count);   
            }
    }

代码接收一系列整数，然后将它们排序到LL参数中。这个代码应该用于一个集合（因此没有重复条目）。

输入9、8、7、6、5、4、3、2、1的输出是3、4、5、6、7、8和9（前两个值怎么了？）。

当输入7、3、5、1、9、2等内容时，输出只有7和9（所以它无法处理间隔大于1的值... o.O）。 附加信息：

typedef struct cellT {
    int value;
    struct cellT *next;
} cellT;

struct setCDT{
    int count;
    cellT *start;
    cellT *cursor;   
};

setADT setNew()
{
    setADT newNode = malloc(sizeof(struct setCDT));
    newNode->start = newNode->cursor = malloc(sizeof(cellT));
    newNode->start->next = newNode->cursor->next = newNode->start;
    newNode->count = 0;
    return (newNode);
}

setADT是指向setCDT的指针类型。但是，setElementT只是一个简单的int类型。对于这种模糊不清的表述，我们表示歉意。

- Bilal Siddiqui

1

我看不到任何代码，你可以发一下吗？ - Cheiron

@ameyCU New 可能是一个自定义函数，在 C 中该单词并不是保留字。 - Arkku

3

setElementT和setADT是指针吗？注意：不要使用typedef隐藏指针！这是灾难的完美配方。对于bool：使用stdbool.h而不是自定义类型。这会产生糟糕的影响，而标准布尔类型（自C99以来）则没有这些问题。另外，在C中有效，但使用C++关键字不是一个好主意，因为您可能稍后会迁移到C++或使用带有“extern“C” ”的C++库。 - too honest for this site

1

问题是什么？请提供一个最小完整可运行示例 [MCVE]。目前给出的信息不清楚你在问什么。建议您先好好休息一下，再重新审视您的代码，然后再提出问题。 - too honest for this site

setElementT 是一个整型变量。setADT 是一个指针。现在正在添加 typedef。 - Bilal Siddiqui

显示剩余12条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Arkku · Accepted Answer

一些观察：

while(buffer->cursor != buffer->start && buffer->cursor->value < E){
    if(buffer->cursor->value == E) // never true

第一个循环中的value == E永远不会为真，因为循环条件是value < E，因此遇到等于E的值会停止迭代。将循环条件改为<= E，如果找到重复项，则只需简单地return，而不是使用flag。

当flag == false时的路径也不返回值（尽管由于上述错误目前无法到达），如果修复了与flag相关的错误并且列表中已存在E，则为newNode分配的内存也会泄漏。

以下的if似乎毫无意义，并且由于在else后没有{，缩进非常误导人：

if(buffer->cursor != buffer->start){
    newNode->next = buffer->cursor; // would be harmless in both branches
    previous->next = newNode;       // done in both branches
} else                              // always using { } would make this clear
    previous->next = newNode;
    buffer->count++;
    return (buffer->count);

同时，不要将setADT定义为指针类型，这会导致误解，结合New(setADT)等结构几乎一定会导致错误。

同时，在setNew中，由于只有一个节点，所以将newNode-> start->next = newNode->cursor->next = newNode->start;替换为newNode->start->next = newNode->start；

更改摘要：

int setInsertElementSorted(struct setCDT * const buffer, const int E) {
    cellT *newNode;
    cellT *previous = buffer->start;
    buffer->cursor = previous->next;

    while (buffer->cursor != buffer->start && buffer->cursor->value <= E) {
        if (buffer->cursor->value == E) {
            return buffer->count; // duplicate value
        }
        previous = buffer->cursor;
        buffer->cursor = buffer->cursor->next;
    }
    if ((newNode = malloc(sizeof(*newNode)))) {
        newNode->value = E;
        newNode->next = buffer->cursor;
        previous->next = newNode;
        buffer->count++;
    }
    return buffer->count;
}

如果错误仍然存在，那么问题很可能出现在其他地方。

测试代码：

int main (int argc, char **argv) {
    struct setCDT *list = setNew();
    for (int i = 1; i < argc; ++i) {
        setInsertElementSorted(list, atoi(argv[i]));
    }
    list->cursor = list->start;
    while ((list->cursor = list->cursor->next) != list->start) {
        (void) printf("%d\n", list->cursor->value);
    }
    return EXIT_SUCCESS;
}