線形リストで場合分けなしの挿入をダブルポインタで作成する方法がわかりません

Question

前提・実現したいこと

線形リストの昇順にソートされる挿入関数を以下の図のように作成する上で、関数insert1は
ノードを先頭に挿入するか否かで場合分けをするように作成し、
一方の関数insert2はその場合を分けをなくすためにダブルポインタを用いて作成するのですが、以下の空欄のあ〜きに入る式、特にお〜きがわかりません。
また,それ以前にinsert2のmain関数において
list *head = NULL;
と定義しているのに対し,
insert2の関数の引数ではダブルポインタ
void insert2(list **head_p, ...)
とあるのでmainで定義するのは合致するようにダブルポインタを用いなくていいのでしょうか?

また, mainで引数でinsert(&head,...)とありますが、これはポインタが指しているアドレスではなく、ポインタ自身のアドレスを渡している意味がわかりません。

ググったのですが, ダブルポインタを用いた線形リストの参考になるサイトが見当たらなかったのでよろしくお願いいたします。

![

該当のソースコード

typedef struct list {
  int data;
  struct list *next;
} list

list * list_alloc(int data) {
  list *p = malloc(sizeof(list));
  p->data = data;
  p->next = NULL;
  return p;
}

list * insert1(list *head, int data) {
  list *new = list_alloc(data);
  list *p = head;
  if( あ || い ) { //先頭に挿入する条件                                                                                                                                                                     
    new->next = p;
    return new;
  } else {
    while( う && え ) { //挿入箇所を探す                                                                                                                                                                    
      p = p->next;
    }
    new->next = p->next;
    p->next = new;
    return head;
  }
}

int main() {
  list *head = NULL;
  head = insert1(head,100);
  head = insert1(head,50);
  head = insert1(head,20);
}

void insert2(list ** head_p, int data) {
  list * new = list_alloc(data);
  list **p = head_p;
  while(  お  && か  ) {
    p = き; //次のnextメンバーを指す                                                                                                                                                                        
  }
  new->next = *p;
  *p = new;
}
int main() {
  list *head = NULL;
  insert2(&head,100);
  insert2(&head,50);
  insert2(&head,20);
}

試したこと

まず、"あ"と"い"は先頭が空リストの場合と値が昇順になることを考えて

(p=NULL || data > p->data)
(p=NULL || data < p->data)

次の"う"と"え"は

while(p->next != NULL && data < p->next->data)
while(p->next != NULL && data > p->next->data)

でいいと思うのですが次の"か"と"き"を考える上でinsert2関数内の
list **p = head_p;
とありますが, このhead_pの値はリストの先頭のアドレスを指しているのでしょうか？

**追記: *間接メンバー"->"は選択演算、アドレス演算＆より優先順位が高いことを考慮して,
"お"、"か"はそれぞれ
while(*p != NULL && data < (*p)->data)
であり、"き"は
p = &(*p)->next;
であると思うのですが、これは
p = **pと表記することも等しいと思うのですかどうなんでしょうか。

Comments

[kasa0]

"い"と"え"は間違っているよ。

[apeirogon0813]

降順になっているようでした、

Answer 1

まず、"あ"と"い"は先頭が空リストの場合と値が昇順になることを考えて
(p=NULL || data > p->data)
次の"う"と"え"は
while(p->next != NULL && data < p->next->data)

既に指摘があるように、降順になりますね。

でいいと思うのですが次の"か"と"き"を考える上でinsert2関数内の
list **p = head_p;

リストの先頭アドレスですね。

C言語の場合、引数で渡された値を書き換える事ができないので、そのアドレスを渡す事で、(アドレスが指し示す)値を書き換えます。

insert1() と insert2() の違いは、挿入済みリストの戻し方だけかと思います。

---

insert1() の先頭じゃない場合ですが、挿入位置が違うと思います。
一つ前ではないでしょうか?
また、ソースコードに誤記が多いように感じます。
lost → list, $ → & ではないでしょうか?
list, list_alloc() は、ここでは未定義ですね。

Comments

[apeirogon0813]

申し訳ありません。誤表記は修正いたしました。
なるほど, 上記に追加した画像のような構造になっているのでしょうか？
また, 間接メンバー"->"は選択演算*、アドレス演算＆より優先順位が高いことを考慮して,
"お"、"か"はそれぞれ
while(*p != NULL && data < (*p)->data)
であり、"き"は
p = &(*p)->next;
であると思うのですが、これは
p = **pと表記することも等しいと思うのですがいかかでしょうか。

Answer 2

ダミー要素を使わずに先頭要素へのポインタのポインタを使う事で効率化したリストですね。

mainで定義するのは合致するようにダブルポインタを用いなくていいのでしょうか?

やってる事は

void a(int* ip){ *ip = 100; }
int main(){
  int i =0;
  a(&i);
  printf("%d\n", i); // => 100が表示される
}

と同じです。

list *head = NULL;が何を指しているかを書き換えたいのでlist**を引数にとります。

Comments

[apeirogon0813]

なるほど **list = &head　と代入している感覚ですかね

[asm]

list *head;
list **list = &head;
の事ならばそのとおりです。

型名を抜いてしまうと、
list *head;
list ****list;
**list = &head;
の事かと一瞬びっくりしました。

[apeirogon0813]

すみません省略しすぎました。