c - 递归添加有序元素

Question

为什么我会在这段代码上出现段错误？

void inserord(Lint *li, int x, Lint *k){

    if(((*li)->value) > x){
        Lint New;
        New = (Lint) calloc(1,sizeof(Nodo));
        New->value= x;
        New->next = (*li);
        (*k)->next = New;
        return;

    }else if(*li == NULL){
        return;
    }
    *k = *li;
    inserord( &((*li)->next), x, &(*k));
}

问题似乎是当我制作 *k = *li 时，它们是同一类型的指针，Lint。

这是数据结构:

typedef struct slist *Lint;

typedef struct slist {
    int value;
    Lint next;
} Nodo;

*k 的想法是将前一个节点传递给下一个递归调用，因此我可以将这个旧结构链接到新结构，再将新结构链接到下一个。

编辑:

这是完整的代码:

typedef struct slist *Lint;

typedef struct slist {
    int value;
    Lint next;
} Nodo;

void inserord(Lint *li, int x, Lint *k){
    if(((*li)->value) > x){
        Lint New;
        New = (Lint) calloc(1,sizeof(Nodo));
        New->value= x;
        New->next = (*li);
        (*k)->next = New;
        return;

    }else if(*li == NULL){
        return;
    }
    *k = *li;
    inserord( &((*li)->next), x, &(*k));
}

void insertend(Lint *l, int x){
    Lint new, aux;

    new = (Lint) calloc(1,sizeof(Nodo));
    new->value = x;
    new->next = NULL;

    if(*l==NULL){
        *l=new;
        return;
    }
    else
    {
        for(aux=*l; aux!=NULL ; aux = aux->next){
            if(aux->next == NULL){
                aux->next = new;
                return;
            }
        }
    }
}

int main(){
    Lint listinha;

    printf("\n");

    insertend(&listinha, 1);
    insertend(&listinha, 2);
    insertend(&listinha, 3);
    insertend(&listinha, 4);
    insertend(&listinha, 5);
    insertend(&listinha, 7);

    listVal(&listinha);

    Lint k = NULL;

    inserord(&listinha, 4, &k);

    listVal(&listinha);

    return 0;
} 

Answer 1

您可以通过以下方式更简单地编写函数

Lint inserord( Lint li, int x )
{
    if ( ( li == NULL ) || !( li->value < x ) )
    {
        Lint new_li = malloc( sizeof( Nodo ) );
        new_li->value = x;
        new_li->next = li;

        return new_li;
    }

    li->next = inserord( li->next, x );

    return li;
}

并称它为

Lint listinha = NULL;

listinha = inserord( listinha, 1 );

如果使用你的方法那么函数可以写成下面的方式(我使用了我自己的变量名，因为这对我来说很容易)

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

struct Nodo
{
    int value;
    struct Nodo *next;
};

void inserord( struct Nodo **current, int x, struct Nodo **prev )
{
    if ( ( *current == NULL ) || !( ( *current )->value < x ) )
    {
        struct Nodo *nodo = malloc( sizeof( struct Nodo ) );

        nodo->value = x;
        nodo->next = *current;

        if ( *prev == *current ) *current = nodo;
        else ( *prev )->next = nodo;

        return;
    }

    prev = current;
    current = &( *current )->next;

    inserord( current, x, prev );
}

void display( struct Nodo *current )
{
    for ( ; current != NULL; current = current->next )
    {
        printf( "%d ", current->value );
    }
}

int main(void) 
{
    struct Nodo *head = NULL;

    for ( int i = 10; i != 0;  ) inserord( &head, --i, &head );

    display( head );
    printf( "\n" );

    return 0;
}

程序输出为

0 1 2 3 4 5 6 7 8 9 

或者如果你想用第三个参数调用它，比如指向 NULL 的指针，那么函数可以看起来像

void inserord( struct Nodo **current, int x, struct Nodo **prev )
{
    if ( ( *current == NULL ) || !( ( *current )->value < x ) )
    {
        struct Nodo *nodo = malloc( sizeof( struct Nodo ) );

        nodo->value = x;
        nodo->next = *current;

        if ( *prev == NULL ) *current = nodo;
            //   ^^^^^^^^^^^^^ 
        else ( *prev )->next = nodo;

        return;
    }

    prev = current;
    current = &( *current )->next;

    inserord( current, x, prev );
}

并被称为

struct Nodo *head = NULL;
struct Nodo *prev = NULL;


for ( int i = 10; i != 0;  ) inserord( &head, --i, &prev );