在特定位置插入单链表

Question

我只是通过单向链表..我从参考书中复制了这段代码..但我不知道如何运行它在main..我应该传递什么作为struct node *new 中的参数？我不知道.. 如果可能的话请帮忙....

struct node *insertatspecificposition(  struct node *new,int n){
    struct node *pred = head;
    if(n<=1){
        new->next = head;
        return new;
    }
    while(--n && pred != NULL ){
        pred = pred->next;
    }
    if(pred == NULL){
        return NULL;
    }
    new->next = pred->next;
    pred->next = new;
    return head;
}

Answer 1

提供的函数有逻辑错误。

当位置设置为 1 时，由于此代码段

，函数会在当前 head 节点之前插入一个新节点

if(n<=1){
    new->next = head;
    return new;
}

因此，例如，如果您有一个空列表（head 等于 NULL），则调用

之类的函数

head = insertatspecificposition( a_new_node_with_value_1, 1 );

你会得到看起来像

的列表

1 -> null

现在逻辑上一致的是，如果在下次调用该函数时指定位置 2，您将获得看起来像

的列表

1 -> 2 -> null

然而这样的调用

head = insertatspecificposition( one_more_new_node_with_value_2, 2 );

returns NULL 而不是返回指针的当前值 head.

这是一个演示程序。

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

struct node
{
    int data;
    struct node *next;
} *head;

struct node * create( int data )
{
    struct node *new = malloc( sizeof( struct node ) );
    
    if ( new != NULL )
    {
        new->data = data;
        new->next = NULL;
    }
    
    return new;
}

struct node *insertatspecificposition(  struct node *new,int n){
    struct node *pred = head;
    if(n<=1){
        new->next = head;
        return new;
    }
    while(--n && pred != NULL ){
        pred = pred->next;
    }
    if(pred == NULL){
        return NULL;
    }
    new->next = pred->next;
    pred->next = new;
    return head;
}

void display( void )
{
    for ( struct node *current = head; current != NULL; current = current->next )
    {
        printf( "%d -> ", current->data );
    }
    
    puts( "null" );
}

int main(void) 
{
    display();
    
    head = insertatspecificposition( create( 1 ), 1 );
    
    display();
    
    head = insertatspecificposition( create( 2 ), 2 );
    
    display();
    
    return 0;
}

程序输出为

null
1 -> null
null

而不是预期的输出

null
1 -> null
1 -> 2 -> null

另请注意，该函数应检查传递的指针 new 是否不等于 NULL。

当函数依赖于全局变量时，这不是一个好的设计。

至于我，我会按照下面的演示程序所示的方式编写函数。

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

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

struct node * create( int data )
{
    struct node *new = malloc( sizeof( struct node ) );
    
    if ( new != NULL )
    {
        new->data = data;
        new->next = NULL;
    }
    
    return new;
}

int insertatspecificposition(  struct node **head, int data, size_t n )
{
    struct node *new_node = create( data );
    int success = new_node != NULL;
    
    if ( success )
    {
        while ( n-- && *head != NULL )
        {
            head = &( *head )->next;
        }
        
        new_node->next = *head;
        
        *head = new_node;
    }
    
    return success;
}

FILE * display( const struct node *head, FILE *fp )
{
    for ( ; head != NULL; head = head->next )
    {
        fprintf( fp, "%d -> ", head->data );
    }
    
    fputs( "null", fp );
    
    return fp;
}

int main(void) 
{
    struct node *head = NULL;
    
    putc( '\n', display( head, stdout ) );
    
    insertatspecificposition( &head, 1, 0 );
    
    putc( '\n', display( head, stdout ) );
    
    insertatspecificposition( &head, 3, 1 );
    
    putc( '\n', display( head, stdout ) );
    
    insertatspecificposition( &head, 2, 1 );
    
    putc( '\n', display( head, stdout ) );
    
    insertatspecificposition( &head, 4, 3 );
    
    putc( '\n', display( head, stdout ) );
    
    return 0;
}

程序输出为

null
1 -> null
1 -> 3 -> null
1 -> 2 -> 3 -> null
1 -> 2 -> 3 -> 4 -> null

如果指定的位置大于或等于列表中的节点数，则新节点将附加到列表的尾部。

C 中数组索引的位置从 0 开始。

当然，您至少还需要一个函数来清除列表，即释放所有分配的内存。

在特定位置插入单链表

insertion in a singly linked list at a specific position

c

linked-list

insert

singly-linked-list

function-definition