[C言語]線形リストの追加と削除を行う関数[コード付き]

今日は線形リストを実装してみます。
ゴリゴリにポインタを使うのでそこは注意。

また一番最後に全体のコードを貼ってあります。参考にどうぞ。

線形リストとは
コードの実装
完成

線形リストとは

リスト構造っていうのは複数のデータをポインタでつないだ構造のことです。
つまり構造体にデータが格納される部分とポインタが格納される部分があるってことですね。

とりあえずリストで使う構造体のイメージ

もちろんポインタの型は、その構造体自身の型です。

そんでその構造体を何個か集めます

この状態ではそれぞれのポインタはバラバラになっていますが
いい感じにつないであげると…

こんな感じで一列につながった構造になります。
これが線形リスト構造です。

コードの実装

今回は簡単な線形リストの操作関数をつくってみます。
具体的にはリストに新たな要素を追加する関数とリストの要素を削除する関数です。

構造体の定義

普通に上に書いたように値を持つ部分と次の構造体を指すポインタの部分を要素とします。

名前はtypedefで扱いやすいように変えておきます。

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

追加関数

追加関数をつくっていく前に、まず新しく追加するリストのメモリを確保する関数を作ります。

malloc関数を使って構造体が入る予定の場所へのポインタを返す関数です。
これで追加関数で使う新しいリストの場所が確保できます。

list *cre(void){
    list *A;
    A = (list*)malloc(sizeof(list));
    
    return A;
}

そして追加関数です。

どのように実装するかを図にしました。
したのコードと合わせて確認するとわかりやすいと思います。

ポインタを繋ぎ変えれば良いということですね。

pはnextを使ってheadから操作したいところまで走査してます。
headは扱う線形リストの先頭を指すポインタです。
main関数でそのように定義して、この関数の仮引数もheadにします。

また今回はmain関数で線形リスト構造を定義するときに、
headがダミーを指す、つまり線形リストの先頭の一個前にダミーを置いてます。
こうすることで操作関数を作りやすくしてます。

具体的に言うと、もしダミーがなければ先頭の要素(headが指す要素)を変更する場合にhead自体が指す場所を変えなければいけないからです。
そうなるとまず関数の仮引数をlistのポインタのポインタ型にする必要があって、更にほかも変更しなければいけないのでダミーを置きました。

コードです。

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が指す場所を、削除したい所の一個手前にします。
ダミーが入ってることを忘れずに。

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

完成

適当に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;
}