Удаление всех узлов с определенным значением в связанном списке - PullRequest
Новая
       34

Удаление всех узлов с определенным значением в связанном списке

0 голосов
/ 23 декабря 2011

Название довольно понятно.Вот функция, которую я написал для этой цели: 

void wipeLoneCells()
{
    cell *tmp;

    tail = head;
    while (1)
    {
        if (head == tail && !tail->flag)
        {
            head = head->next;
            free(tail);
            tail = head;
            continue;
        }

        tmp = tail->next;

/***/   if (tmp->next == NULL && !tmp->flag)
        {
            tail->next = NULL;
            free(tmp);
            break;
        }
        else if (!tmp->flag)
        {
            tail->next = tmp->next;
            free(tmp);
            continue;
        }

        tail = tail->next;      
    }
}

Голова и хвост списка являются глобальными, и список строится к тому времени, когда эта функция вызывается, когда голова указывает на первый узел, а хвост указываетдо последнего (чей следующий NULL).Я почти уверен, что мой связанный список составлен правильно, так как я могу напечатать их без ошибок.Иногда эта функция работает отлично, а иногда это приводит к нарушению доступа на линии, отмеченной звездочками.Я знаю, что это не совсем неправильно, так как я получаю нужный результат, когда он не выдает ошибку, хотя я часто получаю ошибку, поэтому я должен что-то пропустить.Заранее благодарю за любую помощь.

РЕДАКТИРОВАТЬ: Вот фиксированный код: 

void wipeLoneCells()
{
    cell *tmp;

    tail = head;
    while (1)
    {
        if (head == tail && !tail->flag)
        {
            head = head->next;
            free(tail);
            tail = head;
            continue;
        }

        tmp = tail->next;

        if (tmp->next == NULL && !tmp->flag)
        {
            tail->next = NULL;
            free(tmp);
            break;
        }
        else if (tmp->next == NULL)
        {
            tail = tmp;
            break;
        }
        else if (!tmp->flag)
        {
            tail->next = tmp->next;
            free(tmp);
            continue;
        }

        tail = tail->next;      
    }
}

Ответы [ 2 ]

4 голосов
/ 23 декабря 2011

Что делать, если 

tmp = tail->next;

это NULL? Следующая строка пытается разыменовать указатель NULL, что приводит к неопределенному поведению - что может привести к падению.

Вы должны проверить это условие и принять соответствующие меры.

1 голос
/ 23 декабря 2011

Правильное deleteitem() в односвязном списке должно быть следующим:

Вы можете избежать рекурсии и придумать итерационную версию (попробуйте, но дайте мне знать, если вам нужна помощь),Я бы не использовал while(1) для этого случая! 

typedef struct node {
    int data;
    struct node *next;
}NODE;


/*

(1) deleting head 
    delete element and adjust head pointer

(2) deleting tail
    delete element and adjust tail pointer

(3) one element list
    if data is the data for the only element
    then delete the list and set head and tail
    pointers to NULL

(4) all the other cases
    traverse through the list and hold the
    previous pointer. delete element and adjust
    the next pointers. 

(5) if not the above cases, then element not
    present.. do nothing..

*/
void deleteitem(int data)
{
    printf("%s: %d - ", __FUNCTION__, data);
    NODE *cur = head;
    NODE *prev = cur;
    NODE *temp = NULL;

    if (head == NULL) {
        assert (tail == NULL);
        printf("Empty list \n");
        return;
    }

    if (head->data == data) {
        temp = head;

        // one element list
        if (head == tail)
            head = tail = NULL;
        else
            // list has more than one element
            head = head->next;

        printf("%d \n", temp->data);
        free(temp);
        deleteitem(data);
        return;
    }

    while (cur != NULL) {
        if (cur->data == data) {
            if (cur == tail) {
                tail = prev;
            }
            prev->next = cur->next;
            printf(" %d deleted\n", cur->data);
            free(cur);
            assert(tail->next == NULL);
            deleteitem(data);
            return;
        }
        prev =cur;
        cur = cur->next;
    }

    printf(" %d not found\n", data);
    return;
}
...