スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

単方向リストの C 言語プログラム

C 言語における構造体の応用例として、単方向リストを実装するサンプルプログラムの紹介。

単方向リストは、単連結リスト、一方向リスト、片方向リストとも呼ばれます。英訳すると singly linked list です。

サンプルプログラム

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

/* ノード */
typedef struct Node_tag {
    int data;
    struct Node_tag *next;
} Node;

/* 単方向リスト */
typedef struct {
    Node *head;
} List;

/* リストの初期化 */
void init_list(List *list)
{
    list->head = NULL;
}

/* ノードの生成 */
Node *create_node(int num)
{
    Node *new_node;

    if ((new_node = malloc(sizeof(Node))) == NULL) {
        perror("malloc");
        exit(1);
    }

    new_node->data = num;
    new_node->next = NULL;

    return new_node;
}

/* ノードをリストの先頭に挿入する */
void insert_front(List *list, Node *node)
{
    node->next = list->head;
    list->head = node;   
}

/* ノードの追加 (ノードを生成して先頭に挿入) */
void add(List *list, int num)
{
    insert_front(list, create_node(num));
}

/* リストの構築
   i 番目に追加するノードに d[i] を格納 */
void create_list(List *list, const int d[], size_t length_of_d)
{
    for (size_t i = 0; i < length_of_d; i++) {
        add(list, d[i]);
    }  
}

/* 全ノードのデータを表示 */
void show_list(const List *list, const char *list_name)
{
    printf("\n[List: %s]\n", list_name);
    printf("head = %p\n", list->head);  /* 先頭のノードのアドレス */
    for (Node *p = list->head; p != NULL; p = p->next) {
        puts("\t|\n\tV");  /* 下矢印 */
        printf("[Node: %p]\n", p, p->data, p->next);  /* ノードのアドレス */
        printf("data = %d\n", p->data);  /* ノードのデータ */
        printf("next = %p\n", p->next);  /* 次のノードのアドレス */
    }
    putchar('\n');
}

/* 先頭のノードを削除 */
void remove_front(List *list)
{
    if (list->head != NULL) {
        Node *temp = list->head->next;
        free(list->head);
        list->head = temp;  
    }
}

/* 全ノード削除 */
void clear_list(List *list)
{
    while (list->head != NULL) {
        remove_front(list);
    }
}

/* ノードの探索 (線形探索) */
Node *search(const List *list, int key)
{
    for (Node *p = list->head; p != NULL; p = p->next) {
        if (p->data == key) { 
            return p; 
        }
    }

    return NULL;
}

int main(void)
{
    List list1;
    int d[] = {1, 2, 3, 4, 5};
    size_t length_of_d = sizeof(d) / sizeof(d[0]);  /* 配列 d の要素数 */
    int key; 
    Node *p;

    init_list(&list1);   /* 初期化 */
    create_list(&list1, d, length_of_d);  /* リストの構築 */
    show_list(&list1, "list1");   /* 各ノードのデータを表示 */

    /* 探索 (見つかる例) */
    key = 3;
    if ((p = search(&list1, key)) == NULL) {
        printf("%d not found. ", key);
    } else {
        printf("%d found. ", p->data);
    }

    clear_list(&list1);  /* 終了処理 (malloc で確保した領域の解放) */

    return 0;
}

実行結果は以下のようになります。

[List: list1]
head = 006A1838
    |
    V
[Node: 006A1838]
data = 5
next = 006A1828
    |
    V
[Node: 006A1828]
data = 4
next = 006A1818
    |
    V
[Node: 006A1818]
data = 3
next = 006A1808
    |
    V
[Node: 006A1808]
data = 2
next = 006A1DC8
    |
    V
[Node: 006A1DC8]
data = 1
next = 00000000

3 found.

ただし、表示されるアドレス値は実行するたびに変わります。

【theme : プログラミング
【genre : コンピュータ

プロフィール

よしいず

Author:よしいず
MATHEMATICS.PDFというウェブサイトを運営しています。

管理の都合上、トラックバックとコメントはオフにしてあります。ブログ経験者なら分かっていただけると思いますが、スパム(アダルトやその他の宣伝)ばかりなのが現実です。

リンクは自由です。当サイトの記事に対する間違いの指摘・意見・感想などを述べた記事からのリンクは歓迎です。ただし、ブログ記事アップ直後はミスが多く、頻繁に修正します。場合によっては削除する可能性もあります。その際、何も断りもなく修正・削除しますがご了承ください。内容を参考にする場合には投稿後一週間ほど様子を見てからにしてください(笑)。

記事の間違いを指摘するときは、その具体的箇所、理由(仕様に反するなど)・根拠(参考にした文献など)、代替案(同じ結果を得るための正しいやり方)も教えてください。そうしないと、(指摘される側および第三者はその時点では無知の状態なので、)どこが間違いなのか分かりませんし、本当に間違っているのかどうかが判断・検証できません。実際、間違いだと指摘されたことが結局は正しかったというケースもありますので。

このブログのタイトル一覧

リンク
月別アーカイブ
カテゴリ
最新記事
検索フォーム
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。