線形リスト(片方向)

http://www.geocities.jp/ky_webid/algorithm/010.html

さてとうとうmalloc関数を使って動的に拡張していくタイプの処理に入りました。

このあたりのリスト構造を極めれば今後割りと何でも作れそうな気がします。

ということでここは何としてもキッチリと押さえたいですね。

さて、さっそくいつものように実装しようとしたのですが、言葉だけではいまいちどういったものかイメージできなかったので今回は先に実装を軽く見て理解したうえで自分なりに実装してみます。

#include <stdio.h>
#include <stdlib.h>

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

LIST *create_list() {
    LIST *p;
    p = (LIST *)malloc(sizeof(LIST));
    if ( p == NULL ) {
        // メモリ不足エラー
        return NULL;
    }
    p->next = NULL;
    
    printf("create %p\n",p);
    return p;
}

void add_list (LIST *p,int data) {
    LIST *add,*q;
    
    add = create_list();
    add->data = data;
    
    q = p;
    while( p != NULL ){
        q = p;
        p = p->next;
    }
    
    q->next = add;
}

void free_list (LIST *p) {
    LIST *q;
    while( p != NULL ){
        q = p;
        p = p->next;
        printf("free   %p\n",q);
        free(q);
        q = NULL;
    }
}

void delete_list (LIST *p,int data) {
    LIST *q;
    while( p != NULL ){
        q = p;
        p = p->next;
        if ( p->data == data ) {
            q->next = p->next;
            printf("free   %p\n",p);
            free(p);
            p = NULL;
            // まだ同じ値の要素があるかもしれないので引き続き検索する
            p = q->next;
        }
    }
}

void show_list (LIST *head) {
    LIST *p;
    
    p = head;
    while( (p = p->next) != NULL){
        printf("%d\n",p->data);
    }
}

int main (void) {
    LIST *head;
    
    head = create_list();
    
    add_list(head,100);
    add_list(head,200);
    add_list(head,300);
    add_list(head,200);
    
    delete_list(head,200);
    
    show_list(head);
    free_list(head);
    
    return 0;
}

create 00383148
create 00383158
create 00383168
create 00383178
create 00383188
free   00383168
free   00383188
100
300
free   00383148
free   00383158
free   00383178

実装できました。

createとfreeのデバッグ表示は確保したメモリがちゃんと開放されてるかを確認するためです。

これを見る限りうまくいってますね。