C 语言中的硬链表

Question

我不明白AddToList是如何工作的，如果gHeadPtr总是指向第一个（最小）评级结构，我理解它，但gHeadPtr没有指向它，或者我弄错了？或者有人可以告诉我如何工作 AddToList？我不知道最后一个字符串是什么意思，为什么我们需要双指针以及什么结构点 gHeadPtr 以及当 gHeadPtr 指向第一个（最小）评级结构时，何时添加到我们刚刚添加的结构（具有最大评级）

struct DVDInfo
{
     char           rating;
     char           title[ kMaxTitleLength ];
     char           comment[ kMaxCommentLength ];
     struct DVDInfo  *prev;
     struct DVDInfo *next;
};
char            GetCommand( void );
struct DVDInfo  *ReadStruct( void );
void            AddToList( struct DVDInfo *curPtr );
void            ListDVDs( bool forward );
char            *TrimLine( char *line );
struct DVDInfo *gHeadPtr, *gTailPtr;
int main (int argc, const char * argv[])
{
     char command;   
     while ( (command = GetCommand() ) != 'q' ) 
     {
          switch( command ) 
          {
               case 'n':
                    AddToList( ReadStruct() );
                    break;
               case 'l':
               case 'r':
                    ListDVDs( command=='l' );
                    break;
          }
          printf( "n----------n" );
     }  
     printf( "Goodbye...n" );  
     return 0;
}
char GetCommand( void )
{
     char buffer[ 100+1 ];
     printf( "Enter command (q=quit, n=new, l=list, r=reverse list):  " );
     fgets( buffer, sizeof(buffer), stdin );
     return *TrimLine( buffer );
}
struct DVDInfo *ReadStruct( void )
{
     struct DVDInfo *infoPtr;   
     infoPtr = malloc( sizeof( struct DVDInfo ) );  
     if ( infoPtr == NULL ) 
     {
          printf( "Out of memory!!!  Goodbye!n" );
          exit( 1 );
     }
     char buffer[ 500+1 ];    
     printf( "Enter DVD Title:  " );
     fgets( buffer, sizeof(buffer), stdin );
     strlcpy( infoPtr->title, TrimLine( buffer ), sizeof(infoPtr->title) ); 
     printf( "Enter DVD Comment:  " );
     fgets( buffer, sizeof(buffer), stdin );
     strlcpy( infoPtr->comment, TrimLine( buffer ), sizeof(infoPtr->comment) ); 
     int num;
     do 
     {
          printf( "Enter DVD Rating (1-10):  " );
          fgets( buffer, sizeof(buffer), stdin );
          num = atoi( TrimLine( buffer ) );
     }
     while ( ( num < 1 ) || ( num > 10 ) );
     infoPtr->rating = num; 
     return( infoPtr );
}
void AddToList( struct DVDInfo *curPtr )
{
     struct DVDInfo **nextPtrPtr = &gHeadPtr;
     struct DVDInfo *prevPtr = NULL;    
     while ( *nextPtrPtr != NULL && curPtr->rating > (*nextPtrPtr)->rating ) 
     {
          prevPtr = *nextPtrPtr;
          nextPtrPtr = &(prevPtr->next);
     }
     curPtr->prev = prevPtr;                // link to previous struct
     curPtr->next = *nextPtrPtr;              // link to next struct
     if ( curPtr->next != NULL )
          curPtr->next->prev = curPtr;       // link prev of next struct to curPtr
     else
          gTailPtr = curPtr;                  // no next struct: curPtr is now the tail
     *nextPtrPtr = curPtr;                      // link next or previous struct (or head) to curPtr
} //когда функция передах структкру, а потом получает новую, указатели сохраняются?
void ListDVDs( bool forward )
{
     struct DVDInfo *curPtr = ( forward ? gHeadPtr : gTailPtr );
     bool separator = false;    
     if ( curPtr == NULL ) 
     {
          printf( "No DVDs have been entered yet...n" );
     } 
     else 
     {
          while ( curPtr != NULL ) 
          {
               if ( separator )
                    printf( "--------n" );
               printf( "Title:   %sn", curPtr->title );
               printf( "Comment: %sn", curPtr->comment );
               printf( "Rating:  %dn", curPtr->rating );            
               curPtr = ( forward ? curPtr->next : curPtr->prev );
               separator = true;
          }
     }
}
char *TrimLine( char *line )
{
     size_t length = strlen( line );
     while ( length > 0 && isspace( line[length-1] )) 
     {
          line[length-1] = '';
          length--;       
     }
     return line + strspn( line, " t" );
}

Answer 1

struct DVDInfo **nextPtrPtr = &gHeadPtr;
struct DVDInfo *prevPtr = NULL;

nextPtrPtr是必需的，因为程序员不想弄乱全局头指针（gHeadPtr）。我们只是使用此指针来迭代列表，因为使用指针到指针比使用头指针本身进行迭代更好。

while ( *nextPtrPtr != NULL && curPtr->rating > (*nextPtrPtr)->rating ) 
    {
    prevPtr = *nextPtrPtr;
    nextPtrPtr = &(prevPtr->next);
    }

上面来自 AddToList 的代码处理找出新节点应该在列表中的位置（即电影的降序评级）。

curPtr->prev = prevPtr;                 // link to previous struct
curPtr->next = *nextPtrPtr;               // link to next struct

上面的行用于插入到链表中。

if ( curPtr->next != NULL )
    curPtr->next->prev = curPtr;     // link prev of next struct to curPtr
else
    gTailPtr = curPtr; 

如果新节点 （curPtr） 是链表中的第一个节点或最后一个节点，则使用上面的这些行。

Answer 2

struct DVDInfo **nextPtrPtr = &gHeadPtr;
...
...
*nextPtrPtr = curPtr;  

双指针的值是另一个指针的地址。对于AddToList（），你需要双指针，因为这样nextPtrPtr指向的值会自动以列表标题（gHeadPtr）的地址开头，如果需要，可以更新它。如果不需要更新gHeadPtr，你可以很容易地使用"struct DVDInfo *nextPtrPtr"。

对于 AddToList（），有两种情况，对于第一种情况，我们肯定需要双指针。第一种情况是，如果 gHeadPtr 为 NULL，这意味着列表中没有元素。对于这种情况，"**nextPtrPtr = &gHeadPtr"意味着nextPtrPtr的值将为NULL。这就是我们正在用"*nextPtrPtr ！= NULL"检查的内容。 由于它是 NULL，它将跳过 while 循环，并且 *nextPtrPtr 将指向 curPtr"。因此，gHeadPtr将开始指向curPtr。第二种情况是，如果头部（gHeadPtr）不是NULL，那么我们将进入while循环，下一个PtrPtr将根据评级标准指向最后一个元素。因此，curPtr 将被添加为下一个 PtrPtr 节点之后的节点。

为了进一步说明这一点，假设AddToList（）使用单个指针和gHeadPtr是 NULL（我提供了以下代码，这使得 nextPtrPtr 成为为了解释起见）。在这种情况下，nextPtrPtr将指向gHeadPtr，这意味着它将以gHeadPtr的地址为例（假设0x1010）。因为 nextPtrPtr 是空的（你可能应该用 NULL 初始化 gHeadPtr，顺便说一句），它现在将跳过 while 循环和最后一个语句将执行 "nextPtrPtr = curPtr;"。有了这个，nextPtrPtr现在指向curPtr（让我们说有地址0x2020） - 这样，gHeadPtr永远不会更新为指向0x2020。

/* Note: Incorrect version for the sake of explanation */
void AddToList( struct DVDInfo *curPtr ) {
    struct DVDInfo *nextPtrPtr = gHeadPtr;
    struct DVDInfo *prevPtr = NULL;
    while (nextPtrPtr != NULL && curPtr->rating > (nextPtrPtr)->rating ) {
        prevPtr = nextPtrPtr;
        nextPtrPtr = prevPtr->next;
    }
    curPtr->prev = prevPtr;                 // link to previous struct
    curPtr->next = nextPtrPtr;               // link to next struct
    if ( curPtr->next != NULL )
        curPtr->next->prev = curPtr;     // link prev of next struct to curPtr
    else
        gTailPtr = curPtr;                // no next struct: curPtr is now the tail
    nextPtrPtr = curPtr;                   // link next or previous struct (or head) to curPtr
}