(2021/10/22再編集済)
今日は線形リストを実装してみます。
ゴリゴリにポインタを使うのでそこは注意。
また一番最後に全体のコードを貼ってあります。参考にどうぞ。
(2021/12/23追記)
線形リストの探索についての記事も書きましたのでそちらもよろしければどうぞ
(2022/1/13追記)
双方向リストの実装についての記事を書きました！是非どうぞ！
線形リストとは
リスト構造っていうのは複数のデータをポインタでつないだ構造のことです。
つまり構造体にデータが格納される部分とポインタが格納される部分があるってことですね。
とりあえずリストで使う構造体のイメージ
もちろんポインタの型は、その構造体自身の型です。
基本的には名前はnextですね。意味通り次に繋がるデータを指すからです。
そんでその構造体を何個か集めます
この状態ではそれぞれのポインタはバラバラになっていますが
いい感じに繋いであげると…
こんな感じで一列につながった構造になります。
これが線形リスト構造です。
ちなみに最後の要素はNULLを指すようにします。
（どこの要素が最後かを示すため）
コードの実装
今回は簡単な線形リストの操作関数をつくってみます。
具体的にはリストに新たな要素を追加する関数とリストの要素を削除する関数です。
線形リストの構造体の定義
普通に上に書いたように値を持つ部分と次の構造体を指すポインタの部分を要素とします。
名前はtypedefで扱いやすいように変えておきます。
typedef struct list{
int date;
struct list *next;
}list;追加関数
追加関数をつくっていく前に、まず新しく追加するリストのメモリを確保する関数を作ります。
malloc関数を使って構造体が入る予定の場所へのポインタを返す関数です。
これで追加関数で使う新しいリストの場所が確保できます。
list *cre(void){
list *A;
A = (list*)malloc(sizeof(list));
return A;
}
そして追加関数です。
どのように実装するかを図にしました。
pで指した要素の次に、要素を追加したいとします。
つまり現在の時点でpとp->nextが指す要素の間に入れたいということですね。
とりあえずpの指す要素を、追加したい要素にします。
追加したい要素をnewとすると p->next = new とすれば良いですね。
図を見てわかる通り、これだけで要素を追加してリスト自体も綺麗になっているのがわかると思います。
これを踏まえてコードを作ります。
void insert(list *head){
list *new;
new = cre();
list *p = head;
int k, l;
printf("挿入する値を入力してください:");
scanf("%d",&k);
printf("何番目のあとに挿入しますか(先頭に挿入するなら0):");
scanf("%d",&l);
for(int i=0; i<l; i++)
p = p->next;
new->date = k;
new->next = p->next;
p->next = new;
}
まずpはnextを使ってheadから操作したいところまで走査してます。
headは扱う線形リストの先頭を指すポインタです。
main関数でそのように定義して、この関数の仮引数もheadにします。
また今回はmain関数で線形リスト構造を定義するときに、
headがダミーを指す、つまり線形リストの先頭の一個前にダミーを置いてます。
こうすることで操作関数を作りやすくしてます。
list A,B,C;
list dummy;
list *head;
head = &dummy; dummy.next = &A; A.next = &B; B.next = &C; C.next = NULL;
具体的に言うと、もしダミーがなければ先頭の要素(headが指す要素)を変更する場合にhead自体が指す場所を変えなければいけないからです。
そうなるとまず関数の仮引数をlistのポインタのポインタ型にする必要があって、更にほかも変更しなければいけないのでダミーを置きました。
つなぎ変えの部分に関しては、まずnewをcreで作って要素の値をscanfで入力させる。
そのあとは上の図で説明したポインタのつなぎ変えを行なっています。
順番に気をつけましょう！！
削除関数
こちらも同じようにポインタの繋ぎ変えで実装します。
pが指している要素の次の要素を削除したいとします。
とりあえず削除したい要素の次の要素、つまりp->next->nextをqとします
線形リストにおいて、削除するのは無視するのと同じです。
つまりpの次の要素を飛ばしてqにすれば良いので、p->next = qとします。
こうすることで図のように削除したい要素はどの要素からも指されていない、つまりリストの流れから外れたことになります。
このつなぎ変えをコードにします。
void delete(list *head){
list *p = head;
int l;
printf("何番目の要素を削除しますか:");
scanf("%d",&l);
for(int i=0; i<(l-1); i++)
p = p->next;
list *q;
q = p->next->next;
p->next = q;
}同じようにheadを受け取ってそれをpに渡します。
その後、削除したい場所までpを進めます。（リストの先頭がダミーであることに注意してfor文を組みましょう）
その後上の図で示したつなぎ変えを行うのですが、
ちなみに消したい要素が最後の要素の場合、つまりp->next->next=NULLの場合も成り立つの？って思う方もいるかと思いますが大丈夫です。
その場合はp->next=NULLとなって、うまい具合に削除できてます。
完成
適当にmain関数でリスト構造を作りました。
また現在の線形リストの中身が表示できる関数も作りました。
動作を確認してみます。
おｋ
てことで完成しました。
下に全体のコードを貼っておくので参考にしてください。
ではまた。
#include <stdio.h>
#include <stdlib.h>
typedef struct list{
int date;
struct list *next;
}list;
list *cre(void){
list *A;
A = (list*)malloc(sizeof(list));
return A;
}
void insert(list *head){
list *new;
new = cre();
list *p = head;
int k, l;
printf("挿入する値を入力してください:");
scanf("%d",&k);
printf("何番目のあとに挿入しますか(先頭に挿入するなら0):");
scanf("%d",&l);
for(int i=0; i<l; i++)
p = p->next;
new->date = k;
new->next = p->next;
p->next = new;
}
void delete(list *head){
list *p = head;
int l;
printf("何番目の要素を削除しますか:");
scanf("%d",&l);
for(int i=0; i<(l-1); i++)
p = p->next;
list *q;
q = p->next->next;
p->next = q;
}
void show(list *head){
list *p;
for(p=head->next; p!=NULL; p=p->next)
printf("%d\n",p->date);
printf("~~~~~~~~\n");
}
int main(int argc, const char * argv[]) {
list A,B,C;
list dummy;
list *head;
head = &dummy; dummy.next = &A; A.next = &B; B.next = &C; C.next = NULL;
A.date = 1; B.date = 3; C.date = 9;
show(head);
insert(head);
show(head);
delete(head);
show(head);
return 0;
}
コメント