Удаление элемента из связанного списка - PullRequest
Новая
       83

Удаление элемента из связанного списка

1 голос
/ 08 июля 2020

Предполагая, что у меня есть этот список ниже: 

List of CDData
    1: Test1
    2: Test2
    3: Test3
    4: Test4
    5: Test5
    6: Test6

Теперь я хочу удалить третий из списка, используя связанный список: что означает бесплатный (removeFromDList (3)); Это моя функция: 

TCD *removeFromDList(int res)
{
    int count = 0;
    TCD *CDData = First;
    CDData->Prev = First;

    if (First == NULL)
    {
        printf("Error\n");
        return NULL;
    }

    while (CDData)
    {
        count++;
        if (count == res)
        {
            if (count == 1)
            {
                if (CDData == Last)
                    Last = NULL;
                First = First->Next;
                return CDData;
            }
            else
            {
                while (CDData != NULL)
                {
                    CDData->Prev = CDData->Next;
                    if (CDData == Last)
                        Last = CDData->Prev;

                    // printf("%s",CDData->Title) I tested here whether my function is going to 
                    //  delete the third one or not with the printf() and it's actually printing the third one 
                    // Which means it's correct 
                   
                    return CDData;
                }
            }
        }

        else
            CDData->Prev = CDData;
        CDData = CDData->Next;
    }
}

Кстати, это определение TCD 

typedef struct F
{
 char *Title;
 struct F *Next;
 struct F *Prev;
}TCD;

Теперь после повторной печати моего списка кажется, что все CDData (все данные структура) были освобождены. Есть идеи, почему?

Я получаю это как результат 

List of CDData

1 Ответ

1 голос
/ 08 июля 2020

Я думаю, что в этом определении структуры 

typedef struct F
{
 char *Titel;
 struct F *Next;
 struct F *Prev;
}TCD;

вы имеете в виду, что имя первого члена данных Title вместо Titel.

И вам нужно динамически выделять память для строки, на которую будет указывать этот член данных.

Ваша функция может вызывать неопределенное поведение хотя бы потому, что изначально глобальная переменная First (кстати, это плохая идея, когда функции зависят от глобального переменных) может быть равно NULL. Итак, в этом фрагменте кода 

TCD *CDData = First;
CDData->Prev = First;

есть попытка использовать нулевой указатель (CDData->Prev) для доступа к памяти.

Это внутреннее while l oop

            while (CDData != NULL)
            {
                CDData->Prev = CDData->Next;
                if (CDData == Last)
                    Last = CDData->Prev;

                // printf("%s",CDData->Title) I tested here whether my function is going to 
                //  delete the third one or not with the printf() and it's actually printing the third one 
                // Which means it's correct 
               
                return CDData;
            }

не имеет смысла.

Обратите внимание, что в C индексы начинаются с 0.

Используя ваш подход, функцию можно записать следующим образом, как показано на демонстрационная программа ниже. 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct F
{
    char *Title;
    struct F *Next;
    struct F *Prev;
} TCD;

TCD *First, *Last;

TCD * removeFromDList( size_t n )
{
    TCD **Current = &First;
    
    while ( *Current && n--)
    {
        Current = &( *Current )->Next;
    }
    
    TCD *target = *Current;
    
    if ( *Current )
    {
        if ( ( *Current )->Next == NULL ) 
        {
            Last = ( *Current )->Prev;  
        }
        else
        {
            ( *Current )->Next->Prev = ( *Current )->Prev;
        }
        
        *Current = ( *Current )->Next;
    }
    
    return target;
}

int append( const char *s )
{
    TCD *Current = malloc( sizeof( TCD ) );
    int success = Current != NULL;
    
    if ( success )
    {
        Current->Title = malloc( strlen( s ) + 1 );
        success = Current->Title != NULL;
        
        if ( success )
        {
            strcpy( Current->Title, s );
            Current->Prev = Last;
            Current->Next = NULL;
        }
        else
        {
            free( Current );
        }
    }
    
    if ( success )
    {
        if ( Last )
        {
            Last = Last->Next = Current;
        }
        else
        {
            First = Last = Current;
        }
    }
    
    return success;
}

FILE * display( FILE *fp )
{
    for ( TCD *Current = First; Current; Current = Current->Next )
    {
        fprintf( fp, "%s -> ", Current->Title );
    }
    
    fputs( "NULL", fp );
    
    return fp;
}

int main(void) 
{
    
    for ( char s[] = "A"; s[0] != 'E'; ++*s )
    {
        append( s );
    }
    
    
    fputc( '\n', display( stdout ) );
    
    TCD *p = removeFromDList( 3 );
    free( p->Title );
    free( p );
    fputc( '\n', display( stdout ) );
    
    p = removeFromDList( 1 );
    free( p->Title );
    free( p );
    fputc( '\n', display( stdout ) );
    
    p = removeFromDList( 0 );
    free( p->Title );
    free( p );
    fputc( '\n', display( stdout ) );
    
    p = removeFromDList( 0 );
    free( p->Title );
    free( p );
    fputc( '\n', display( stdout ) );
    
    printf( "First == NULL : %d, Last == NULL : %d\n", First == NULL, Last == NULL );
    return 0;
}

Результат программы: 

A -> B -> C -> D -> NULL
A -> B -> C -> NULL
A -> C -> NULL
C -> NULL
NULL
First == NULL : 1, Last == NULL : 1
...