Afro-Blue

双方向リスト

アルゴリズムとデータ構造

次は双方向リストのプログラム
次の要素を示すnext変数の他に前の要素をしめすprev変数も構造体に追加している。
あとは先頭要素としてheadをグローバル変数として宣言して初期化時に
next、prevそれぞれ自分のアドレスを代入する。headは今回はポインタではないので注意。
このリストには必ず空き要素headが一つ存在することになる。

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

typedef struct CELL {
    struct CELL *next;
    struct CELL *prev;
    int value;
} Cell;

Cell head;

/* リストの初期化。head要素のnext,prevを設定する*/
void init() {
    head.next = &head;
    head.prev = &head;
}

/* リストの末尾に新しく要素を設定 */
void insert_last(int value) {
    Cell *ptr, *new;

    for (ptr = head.next; ptr != &head; ptr = ptr->next) {
        ;
    }

    new = malloc(sizeof(Cell));
    new->value = value;
    /* ptrの指す前の要素が最後の要素なので新しい要素をその次に追加 */
    ptr->prev->next = new;
    new->next = ptr;
    new->prev = ptr->prev;
    ptr->prev = new;
    
}

/* リストの先頭に新しく要素を設定 */
void insert_top(int value) {
    Cell *new;
    new = malloc(sizeof(Cell));
    new->value = value;
    new->next = head.next;
    (head.next)->prev = new;
    head.next = new;
    new->prev = &head;

}

/* 指定した要素を削除 */
void delete_list(int value) {
    Cell *ptr;

    for (ptr = head.next; ptr != &head; ptr = ptr->next) {
        if (ptr->value == value) {
            break;
        }
    }
    /* 要素が見つからなかった場合 */
    if (ptr == &head) {
        printf("指定した要素が見つかりません\n");
        return;
    }

    ptr->prev->next = ptr->next;
    ptr->next->prev = ptr->prev;
    free(ptr);
    ptr == NULL;
}

void print_list() {
    Cell *ptr;
    int i;
    for (ptr = head.next, i = 0; ptr != &head; ptr = ptr->next, i++) {
        printf("%d番目の要素:%d\n", i, ptr->value);
    }
}

int main(void) {
    int x, value;
    char buf[256];
    Cell *ptr;

    /* リストを初期化する */
    init();

    while(1) {
        print_list();
        
        printf("1:末尾に追加 2:最初に追加 3:指定した値の要素を削除\n");
        printf("9:終了   :");
        fgets(buf, 256, stdin);
        sscanf(buf, "%d", &x);

        if (x==9) {
            break;
        }

        switch(x) {
        case 1:
            printf("追加するデータを入力してください:");
            fgets(buf, 256, stdin);
            sscanf(buf, "%d", &value);
            insert_last(value);
            break;

        case 2:
            printf("追加するデータを入力してください:");
            fgets(buf, 256, stdin);
            sscanf(buf, "%d", &value);
            insert_top(value);
            break;

        case 3:
            printf("削除するデータを指定してください:");
            fgets(buf, 256, stdin);
            sscanf(buf, "%d", &value);
            delete_list(value);
            break;
            
        }
    }
    return 0;
}

Permalink | コメント(0) | トラックバック(0) | 16:54