如何使用指向要插入鏈接列表的指針的指針

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