トリッキーコードネット トップへ戻る   C/C++, Java, Perl, PHP, JavaScript, アルゴリズム, ショートコーディング, IOCCCコードの解説, 等々

サイト情報

トリッキーなコード

7行プログラミング

物凄いコード集

アルゴリズム

データ構造

C/C++な話題

コードサンプル

ツール/環境構築

開発ノウハウ 等

ネタ/ジョーク集

おススメ書籍/サイト

サイトTOP >> データ構造 >> 単方向連結リスト(Simple Linked-List) (C言語)

単方向連結リスト(Simple Linked-List)とは?

前回の説明を踏まえ、単方向連結リストについて説明します^^;)

単方向連結リストとは、リストの一方向にしかリンクがつながっていない、連結リストの事です。

図にするとこんな感じ↓
単方向連結リスト(Simple Linked-List)

リストの先頭を指すポインタ(g_head)と、リストの末尾を指すポインタ(g_tail)があります。

それでは、さっそくコーディング開始。


ノードの定義・先頭ポインタ・末尾ポインタ

まずは、ノードを定義します。そして、リストの先頭を指し示すポインタ(g_head)と、末尾を指し示すポインタ(g_tail)を宣言します。
typedef struct _tagNode {

    // 重複不可のID
    int nId;

    // 重複可能な名前
    char * pszName;

    struct _tagNode * next;

} node;

node * g_head;
node * g_tail;
ここでは一例として、ノード中に、重複不可のIDと名前、そして次のノードを指すポインタが入っているという事にします。 (※ データのみを別の構造体に纏めておき、ノード中には「データ構造体」と「次のノードを指すポインタ」の、2つのみを入れるパターンも存在します。)

ノードの作成

続いて、ノードのインスタンスを作成し、そこへユーザからの入力を埋め込む関数を作成します。
/*
 新規ノードの作成

 return : 成功 - 作成されたnodeのポインタ / 失敗 - NULL
*/
node * makeNode()
{
    node * n;
    int  nId, nLen;
    char buff[100];

    // 新規ノードの作成
    if ( ! (n = (node *)malloc(sizeof(node))) ) {
        return NULL;
    }

    memset(buff, '\0', sizeof(buff));

    puts("IDを入力して下さい。->");
    scanf("%d", &nId);

    if (listSearch(nId)) {
        printf("[%d]のIDは既に登録されています。\n", nId);
        return NULL;
    }

    puts("名前を入力して下さい。->");
    fflush(stdin);
    fgets(buff, 100, stdin);
    nLen = strlen(buff);
    buff[nLen - 1] = '\0'; // 文字列最後の改行を削除

    if ( ! (n -> pszName = (char *)malloc(nLen)) ) { // 文字列最後のNULL文字分を考慮し、(nLen + 1)とする必要はない。
        free(n);
        return NULL;
    }

    // 新規ノードへIDをセット
    n -> nId = nId;

    // 新規ノードへ名前をセット
    memset(n -> pszName, '\0', nLen);
    strcpy(n -> pszName, buff);

    // 新規ノードのリンクを初期化
    n -> next = NULL;

    return n;
}
mallocでのメモリ割当に失敗したり、重複したIDが入力された場合は、NULLを返します。 それ以外の場合では、作成したnodeのポインタを返します。 (※ リストをIDで検索するlistSearch()に関しては後述します。)

リストへの追加

作成したノードをリストへ追加する関数です。
/*
 連結リストへの追加

 add    : 追加するノード
 return : 成功 - 0 / 失敗(重複IDを入力した等) - 1
*/
int listAdd(node * add)
{
    if (! add) {
        return 1;
    }

    if (! g_head) {
        // 1つもノードが登録されていない場合
        g_head = g_tail = add;
    }
    else {
        g_tail -> next = add;
        g_tail = add;
    }

    return 0;
}
g_headがNULLの場合、つまり、1つもリストにノードが登録されていない場合は、g_headに新規ノードをセットします。 空の単方向連結リスト(Simple Linked-List)にノードを追加 g_headがNULLで無い場合は、リストの末尾ノードを表すg_tailのnextに、新規ノードをセットします。 単方向連結リスト(Simple Linked-List)の末尾(Tail)にノードを追加

リストへソート(昇順・降順)追加

上で紹介したlistAdd()関数は、データを無条件でリストの後ろに繋げて行く関数でしたが、
以下は、ソートをかけながらノードをリストへ追加する関数です。
/*
 連結リストへID順にソートしながら追加

 add    : 追加するノード
 return : 成功 - 0 / 失敗(重複IDを入力した等) - 1
*/
int listSortAdd(node * add)
{
    node * tmp, * prev;

    if (! add) {
        return 1;
    }

    if (! g_head) {
        // 1つもノードが登録されていない場合
        g_head = add;
    }
    else {
        prev = NULL;
        tmp  = g_head;
        while (tmp) {

            if (tmp -> nId > add -> nId) {

                if (tmp == g_head) {
                    // リストの先頭に登録
                    add -> next = g_head;
                    g_head = add;
                }
                else {
                    // リストの中間に登録
                    prev -> next = add;
                    add  -> next = tmp;
                }

                break;
            }

            prev = tmp;
            tmp  = tmp -> next;
        }

        if (! tmp) {
            // リストの末尾に登録
            prev -> next = add;
        }
    }

    return 0;
}
g_headがNULLの場合の動作は、listAdd()の場合と同様です。 g_headがNULLでない場合は、リストの先頭(g_head)から、ループでリストの値を1つ1つチェックしていき、 新規ノードをセットする場所を探します。 (※ その為、ノードの追加時にlistSortAddr()を使用する場合は、g_tailポインタが不必要となります。   また、listAdd()関数に比べ、処理が非常に低速です・・・) 新規ノードをセットする場所を探した後は、以下の3パターンで処理を行います。

① リストの先頭に登録する場合

追加ノードのnextに、現在のg_headを。そして、g_headへ追加ノードをセットします。 単方向連結リスト(Simple Linked-List)の先頭にノードを追加

② リストの中間に登録する場合

追加場所の1つ前ノードのnextに、追加ノードをセット。そして、追加ノードのnextに、追加場所の1つ後ノードをセットします。 単方向連結リスト(Simple Linked-List)の中間にノードを追加

③ リストの末尾に登録する場合

listAdd()の場合と同様です。

リストの検索

IDを元にノードを検索し、該当IDを持つノードを発見したら、ノードのポインタを返す関数です。
/*
 リストの検索

 nSearchId : 検索するID
 return    : 探し出したノード
*/
node * listSearch(int nSearchId)
{
    node * tmp = g_head;

    while (tmp) {
        if (tmp -> nId == nSearchId) {
            return tmp;
        }
        tmp = tmp -> next;
    }

    return NULL;
}
g_headから順に、ループで辿りながら検索を行います。

リストの削除

指定されたIDのノードを削除する関数です。
/*
 リストの削除

 nDeleteId : 削除するID
 return    : 成功 - 0 / 失敗(該当IDを持つノードがない) - 1
*/
int listDelete(int nDeleteId)
{
    node * prev, * tmp;

    prev = NULL;
    tmp  = g_head;

    while (tmp) {
        if (tmp -> nId == nDeleteId) {

            if (tmp == g_head) {
                // 削除対象ノードがリストの先頭
                g_head = g_head -> next;
            }
            else if (tmp == g_tail) {
                // 削除対象ノードがリストの末尾
                g_tail         = prev;
                g_tail -> next = NULL;
            }
            else {
                // 削除対象ノードがリストの中間
                prev -> next = tmp -> next;
            }

            free(tmp -> pszName);
            free(tmp);

            return 0;
        }
        prev = tmp;
        tmp  = tmp -> next;
    }

    return 1;
}
g_headから順に辿り、削除するノードを検索します。そして、削除するノードを探し出したら、以下の3パターンで処理を行います。

① 削除ノードが、リストの先頭(Head)の場合

g_headへ、現在のg_headのnextをセット。その後、対象ノードを削除 単方向連結リスト(Simple Linked-List)の先頭(Header)を削除

② 削除ノードが、リストの中間に存在する場合

削除ノードの前ノードのnextに、削除ノードの後ノードをセット。その後、対象ノードを削除 単方向連結リスト(Simple Linked-List)の中間を削除

③ 削除ノードが、リストの末尾(Tail)の場合

削除ノードの前ノードをg_tailににセット。g_tailのnextをNULLにセット。その後、対象ノードを削除 単方向連結リスト(Simple Linked-List)の末尾(Tail)を削除

リストの初期化(全削除)

リストを全削除する関数です。
/*
 連結リストの初期化(全削除)を行う
*/
void listInit()
{
    node * tmp, * del;

    if (g_head) {
        tmp = g_head;

        while (tmp) {
            del = tmp;
            tmp = tmp -> next;

            free(del -> pszName);
            free(del);
        }
    }

    g_head = g_tail = NULL;
}
g_headから順に辿り、全てのノードを削除します。
実行ファイルが作成できる形でソースコードを置いておくので、よろしければ参考にして下さい^^;) (※ リストへのノード追加時にソートを行う関数(listSortAdd)の方を使用している為、g_tailポインタを使用していません。) simple-linked-list.h  simple-linked-list.c  test.c さてさて、連結リストは、C++やJava等にはデフォルトで備わっている機能です。 ・・・が、しかし、Cにはデフォルトでは備わっていない為、逐一コーディングを行う必要があります (ノД`)シクシク 連結リストは実務でも多用するテクニックなので、是非ともモノにしておきたいですね♪ 続いて、双方向連結リストについて説明します。 ※ コード中に、1箇所とんでもないバグを発見しました~~。 しかし、あえて修正をせずに、そのまま放置しておきます。 ・・・連結リストを正しく理解し、間違いに気付いて下さいネ☆ ^^;)
         このエントリーをはてなブックマークに追加   


作業効率化・ライフハックのオススメ記事




コンピュータ・テクノロジーのオススメ記事





恋愛・人間関係のオススメ記事




※ 当サイトは、トップページからリンクで辿る事の出来るページに限り、リンクフリーです。
※ 当サイトの閲覧/利用によって生じた如何なる損害も、当サイト管理人は責任を負いません。
※ 当サイトの内容を転載される場合は、当サイトへのリンクをお願い致します。