如何使用指向指针的指针插入链表

Question

think 是一个按照名称顺序插入新元素的函数。如果我使用 if 来分隔开始时插入的条件和其他条件，我就知道该怎么做。但是我被要求将 if 和 while 合并到一个 while 循环中。我如何将插入函数集成到一个带有指向指针的 while 循环中？

person* insert_sorted(person *people, char *name, int age)
{
    person *p=NULL;//,*t=NULL,*q=NULL;
    person *ptr= people;
    person **ptr2ptr=&ptr;

    p=malloc(sizeof(person));

    if ( p == NULL ){
        printf("malloc() failed\n");
        return NULL;
    }
    else {
        p->name = name;
        p->age = age;

        if ( people == NULL ){ // empty list
            people = p;
            people->next =NULL;
        }
        else{
            *ptr2ptr = ptr;
            while( (*ptr2ptr) !=NULL )
            {
                if ( compare_people(p, people)<=0 )  // insert at the start
                    break;
                else if ( (*ptr2ptr)->next == NULL) //insert at the end
                    break;
                else if ( compare_people(*ptr2ptr, p) <=0 && compare_people( p, (*ptr2ptr)->next)<=0 )//insert at the middle
                    break;
                *ptr2ptr = (*ptr2ptr)->next;
            }
            //insert at the end
            p->next =  (*ptr2ptr)->next;
            (*ptr2ptr)->next = p;

        }
    }

Answer 1

e与其试图在列表中找到没有后继者的 person 元素，不如尝试找到第一个空指针。像这样的东西（未经测试）：

void insert_sorted(person **p, char *name, int age)
{
  while (*p) {
    p = &(*p)->next;
  }
  *p = malloc( ... );
  /* ... */
}

这种问题通常最好用笔在纸上画几个方框和箭头来解决。这个想法是你的 'p' 指针不再指向特定的 person 而是指向某个指向 person.

的指针

Answer 2

可以有几个选项。

我会在 compare_people 函数中移动 if ，前提是您可以更改它。毕竟，在列表中添加第一个元素就像添加一个新的 "top of the list" 元素（至少是列表中的元素）。我知道这可以看作是"cheating"。确实如此！

您可以创建一个 "fake" 列表元素，该元素将始终被测试为排序列表的第一个（或最后一个）（例如使用空名称）。所以这个列表永远不会是空的，也不会有 "check for an empty list" 测试。当然那个假项目的内容需要符合compare_people函数的语义。

实际上，成本略高于当前的 O(n)，O(n*log(n))，您可以使用临时支持结构（如指针数组）和来自 stdlib.h 为了保持列表排序。

最后，实现 insertion sort 这将利用原始集合在插入新元素之前已经排序的事实。

Answer 3

函数可以这样写（没有测试因为我不知道列表的一些定义）

person * insert_sorted( person **people, char *name, int age )
{
    person *p = malloc( sizeof( person ) );

    if ( p == NULL )
    {
        printf( "malloc() failed\n" );
    }
    else 
    {
        p->name = name;
        p->age = age;

        person *prev = NULL;
        person *current = *people;

        while ( current && !( compare_people( p, current ) < 0 ) )
        {
            prev = current;
            current = current->next;
        }

        p->next = current;
        if ( prev == NULL ) *people = p;
        else prev->next = p;
    }

    return p;
}

函数应该这样调用

insert_sorted( &people, name, age );
               ^^^^^^^

Answer 4

未经测试：

person* insert_sorted(person** people, char *name, int age) {
    person* added = malloc(sizeof(person));
    added->name = name;
    added->age = age;
    added->next = NULL;

    person* previous = NULL;
    person* current = *people;
    while (current && compare_people(current, added) <= 0) {
        previous = current;
        current = current->next;
    }

    if (!people) {
        *people = added;
    } else {
        previous->next = added;
        added->next = current;
    }

    return added;   
}

Answer 5

您使用指向指针的指针的方式没有使用间接寻址。您只需在通常会写 ´ptr` 的地方写 (*ptr2ptr)。

使用指向节点指针的指针的想法是，通过添加一级间接，您可以从调用函数访问和修改头指针。如果您只是传入一个节点指针，则对该指针的所有更改都是 insert 函数的本地更改，并且在必要时不会更新调用函数中列表的头指针。

您的函数签名应该已经传递了一个指向节点指针的指针：

void insert(person **p, const char *name, int age);

并这样称呼它：

person *head = NULL;

insert(&head, "Betty", 26);
insert(&head, "Ralph", 23);
insert(&head, "Chuck", 19);
insert(&head, "Alice", 42);
insert(&head, "Simon", 34);

进入函数时，p是调用函数中head的地址。当您使用

遍历列表时

p = &(*p)->next;

*p保存前一个节点的next指针的地址。 p 是一个 "whence" 指针：它保存着指向您正在处理的 ode 的指针的地址。这意味着空列表不再是特例。

您的函数需要 return 新的头指针。很容易忘记分配它，它还为调用增加了一些冗余。指针对指针的方法也解决了这个问题。

下面是你的插入代码看起来像一个函数，该函数将指向指针的指针作为参数：

struct person {
    const char *name;
    int age;
    person *next;
};

int compare(const person *p1, const person *p2)
{
    return strcmp(p1->name, p2->name);
}

person *person_new(const char *name, int age)
{
    person *p = malloc(sizeof(*p));

    p->name = name;
    p->age = age;
    p->next = NULL;

    return p;
}

void insert(person **p, const char *name, int age)
{
    person *pnew = person_new(name, age);

    while (*p && compare(*p, pnew) < 0) {
        p = &(*p)->next;
    }

    pnew->next = *p;
    *p = pnew;
}

Answer 6

在这里我找到了这个问题最有用的答案：http://www.mvps.org/user32/linkedlist.html

       ptr2ptr = &people;
        while ( *ptr2ptr!=NULL && compare_people(*ptr2ptr,p) ) {
            ptr2ptr = &(*ptr2ptr)->next;
        }
        p->next = *ptr2ptr;
        *ptr2ptr = p;

如何使用指向指针的指针插入链表

how to use a pointer to pointer to insert in a linked list

c

linked-list

pointer-to-pointer