排序插入链表

Question

攻角,

我已经尝试调试循环链表中的问题 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（所以它不能处理由一个以上分隔的值..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。抱歉含糊不清。

Answer 1

一些观察：

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

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

，则将循环条件更改为 <= E 并简单地 return

flag == false 所在的路径也没有 return 值（尽管由于上述错误，目前无法访问），以及为 newNode 分配的内存如果 flag 的错误已修复且 E 已存在于列表中，则会泄漏。

下面的 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;
}

排序插入链表

Sorted Insertion into Linked List

c

linked-list

sorted