Путаница в связанных списках - PullRequest
Новая
       27

Путаница в связанных списках

0 голосов
/ 23 июня 2011

Я просматривал один и тот же раздел этой книги последние несколько дней и не могу понять, как изменилось поле этого связанного списка / структуры. 

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


/**************************************************> main <*/
int main (int argc, const char * argv[]) {
    char            command;

    gHeadPtr = NULL;
    gTailPtr = NULL;

    while ( (command = GetCommand() ) != 'q' ) {
        switch( command ) {
            case 'n':
                AddToList( ReadStruct() );
                break;
            case 'l':
                ListDVDs();
                break;
        }
    }

    printf( "Goodbye..." );

    return 0;
}


/*******************************************> GetCommand <*/
char    GetCommand( void )
{
    char    command;

    do {
        printf( "Enter command (q=quit, n=new, l=list):  " );
        scanf( "%c", &command );
        Flush();
    }
    while ( (command != 'q') && (command != 'n')
           && (command != 'l') );

    printf( "\n----------\n" );
    return( command );
}


/*******************************************> ReadStruct <*/
struct DVDInfo  *ReadStruct( void ) {
    struct DVDInfo  *infoPtr;
    int             num;

    infoPtr = (struct DVDInfo *)malloc( sizeof( struct DVDInfo ) );

    if ( NULL == infoPtr ) {
        printf( "Out of memory!!!  Goodbye!\n" );
        exit( 0 );
    }

    printf( "Enter DVD Title:  " );
    fgets( infoPtr->title, kMaxTitleLength, stdin );
    ReplaceReturnAtEndOfString( infoPtr->title );

    printf( "Enter DVD Comment:  " );
    fgets( infoPtr->comment, kMaxCommentLength, stdin );
    ReplaceReturnAtEndOfString( infoPtr->comment );

    do {
        num = 0;
        printf( "Enter DVD Rating (1-10):  " );
        scanf( "%d", &num );
        Flush();
    }
    while ( ( num < 1 ) || ( num > 10 ) );

    infoPtr->rating = num;

    printf( "\n----------\n" );

    return( infoPtr );
}


/*******************************************> AddToList <*/
void    AddToList( struct DVDInfo *curPtr ) {
    if ( NULL == gHeadPtr )
        gHeadPtr = curPtr;
    else
        gTailPtr->next = curPtr;

    gTailPtr = curPtr;
    curPtr->next = NULL;
}


/*******************************************> ListDVDs <*/
void    ListDVDs( void ) {
    struct DVDInfo  *curPtr;

    if ( NULL == gHeadPtr ) {
        printf( "No DVDs have been entered yet...\n" );
        printf( "\n----------\n" );
    } else {
        for ( curPtr=gHeadPtr; curPtr!=NULL; curPtr = curPtr->next ) {
            printf( "Title:  %s\n", curPtr->title );
            printf( "Comment:   %s\n", curPtr->comment );
            printf( "Rating:  %d\n", curPtr->rating );

            printf( "\n----------\n" );
        }
    }
}

Когда я отлаживаю эту программу, в строке:

gTailPtr-> следующая = curPtr;

gHeadPtr-> next также указывает на текущий указатель, хотя я не вижу как.

Это из раздела «Обучение C на Mac» (Addison), стр. 256, и если кто-то может помочь, спасибо! Или объясни хотя бы.

Ответы [ 2 ]

1 голос
/ 23 июня 2011

Если это второй элемент, вставляемый в список, то gTailPtr и gHeadPtr первоначально будут указывать на один и тот же узел (первый и единственный узел в списке). Итак, на данный момент gTailPtr->next и gHeadPtr->next - это просто два имени для одного и того же объекта.

Ключевым моментом для понимания является то, что gHeadPtr не является самим узлом и вообще не содержит поля next. Это просто указатель на узел: это означает, что в нем содержится ссылка на какой-то узел (или вообще нет узла). Когда вы присваиваете gHeadPtr сам, вы изменяете , на какой узел он указывает . Когда вы используете оператор ->, вы проверяете узел, на который он указывает прямо сейчас.

Думайте об этом так: переменная-указатель похожа на клочок бумаги, на котором может быть написан номер телефона. Когда вы изменяете переменную указателя, это похоже на стирание номера телефона и замену его другим; когда вы используете оператор ->, это похоже на звонок по номеру телефона. Переменные с двумя указателями, которые указывают на один и тот же узел, похожи на две бумажки с одним и тем же номером телефона: неважно, какую вы используете для вызова, вы достигнете одного и того же пункта назначения. NULL указатель - это чистый лист бумаги: пытаться набрать этот номер просто бессмысленно.

0 голосов
/ 23 июня 2011

Это двуглавый связанный список.Вы можете использовать его как очередь (первым пришел-первым вышел), так и как стеком (последний пришел-первым вышел).Указатель gHeadPtr предназначен для извлечения первого вставленного элемента, а gTailPtr для извлечения последнего вставленного элемента.Подумайте, когда список пуст.И gHeadPtr, и gTailPtr равны нулю.Теперь условие, чтобы выяснить, является ли список пустым, if ( NULL == gHeadPtr ).Поэтому, когда первый элемент должен быть вставлен, вы указываете curPtr на gHeadPtr.После вставки до тех пор, пока вам не понадобится вытолкнуть первый элемент, нет необходимости прикасаться к gHeadPtr.Впервые даже gTailPtr будет указывать на curPtr.Поэтому, когда вставляется только один элемент, и gHeadPtr, и gTailPtr указывают на один и тот же элемент.Когда следующий элемент вставлен, gHeadPtr остается нетронутым.Новый элемент добавляется рядом с gTailPtr, и gTailPtr будет указывать на новый элемент.Это довольно простой материал об очереди.Лучше учиться о структурах данных.

...