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

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

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

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

Answer 2

的eInstead试图找到在没有后继列表中person元素，试图找到第一个空指针。像这样（未经）：

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

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

Answer 3

可以有几个选项。

我会将if在compare_people函数内部移动，只要您可以更改它即可。毕竟，在列表中添加第一个元素就像添加一个新的“列表顶部”元素（至少是列表）。我知道这可以被视为“作弊”。而且的确如此！

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

实际上，您可以使用临时支持结构（如指针数组）和qsort（）来从stdlib中稍微高于当前O（n），O（n * log（n））。 h以保持列表排序。

最后，执行insertion sort，它将利用原始集在插入新元素之前已被排序的事实。

Answer 4

该函数可以写成下面的方式（没有测试，因为我不知道名单的一些定义）

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 5

未经测试：

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 6

您使用指针指针的方式不使用间接寻址。你只写(*ptr2ptr)你通常会写'ptr`。

使用指针指向节点指针的想法是通过添加一个间接级别，您可以从调用函数访问和修改头指针。如果您只传入一个节点指针，则该指针的所有更改都是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的指针地址。这意味着空单不再是特例。

你的函数需要返回新的头指针。忘记分配它很容易，它也为呼叫增加了一些冗余。指针指针方法也解决了这个问题。

这里是你插入代码，如何能看起来像，需要一个指针，指针作为自变量的函数：

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; 
}