C中链表的冗余计数

Question

我正在练习可以在链接列表中查找冗余的代码。 例如:

输入

777

输出

contains 2 redundancies

输入

32182

输出

contains 1 redundancies

我正在努力实际跟踪代码中的冗余。我对链表进行了排序，然后我假设我只创建 2 个指针，一个遍历链表的当前位置，一个遍历链表的前一个位置，如果它们相等的话 count++ 。但我总是得到 0 裁员。

在下面的代码中，我认为我的挑战主要在于 countRedun() 方法。

struct digit * insertAtFront(struct digit *start, struct digit * newDig){
    struct digit * ptr = start;
    newDig = start;
    return newDig;

}
struct digit * insertIntoSorted(struct digit *start, struct digit *newDig) {
    struct digit *ptr = start;
    struct digit *prev = NULL;
    while ((ptr!=NULL) && (ptr->num < newDig->num)) {
        prev = ptr;
        ptr = ptr->next;
    }
    if (prev == NULL) {
        start = insertAtFront(start, newDig);
    } else {
        prev->next = newDig;
        newDig->next = ptr;
    }
    return(start);
}

struct digit * sortedCopy(struct digit * start) {
    //! heap1=showMemory(start=348, cursors=[start, ptr, sortedStart, newDigit])
    //! heap2=showMemory(start=519, cursors=[start, newDigit, ptr, prev])
    struct digit *ptr = start;
    struct digit *sortedStart = NULL;
    struct digit *newDigit;

    if (start!=NULL) {
        sortedStart = createDigit(start->num);
        ptr = ptr->next;
    }
    while (ptr!=NULL) {
        newDigit = createDigit(ptr->num);
        sortedStart = insertIntoSorted(sortedStart, newDigit);
        ptr = ptr->next;
    }
    return(sortedStart);
}

int countRedun(struct digit * start){
    struct digit  *sorted, *ptr, *prev, * curr;
    ptr = start;
    prev = start;


    //sort linked list
    sorted = sortedCopy(start);
    int count = 0;

    while(ptr != NULL)
    {

        if(ptr->num == prev->num)
        {
        count++;
        }
    prev = ptr;
    ptr = ptr->next;
    }

}

我已经排除了要求用户输入的代码以及链接列表创建器方法，假设排序和计数方法是这个问题的关键。

Answer 1

看起来sortedCopy创建了一个全新的列表，但是已经排序了。如果是这样，那么您需要重新排序:

ptr = start;
prev = start;


//sort linked list
sorted = sortedCopy(start);

与:

//sort linked list
sorted = sortedCopy(start);
ptr = sorted;
prev = sorted;

请注意，您可能最好:

 prev = NULL;
 while(ptr != NULL) {
    count += (prev && ptr->num == prev->num);
    prev = ptr;
    ptr = ptr->next;
}

否则你数的总是会少一。