掲示板利用宣言

 次のフォームをすべてチェックしてからご利用ください。

 私は

 題名と投稿者名は具体的に書きます。
 課題の丸投げはしません。
 ソースの添付は「HTML変換ツール」で字下げします。
 返信の引用は最小限にします。
 環境(OSとコンパイラ)や症状は具体的に詳しく書きます。
 返信の付いた投稿は削除しません。
 マルチポスト(多重投稿)はしません。

掲示板2

管理者用メニュー    ツリーに戻る    携帯用URL    ホームページ    ログ    タグ一覧

No.26122

双方向リスト
投稿者---io(2006/02/15 10:07:18)


おはようございます。
双方向リストを勉強してますがなかなか意味分かりません。
以下のものは自分が見つけた例ですがどなたかご説明いただけますでしょうか?

この辺の意味を分かりません。
よろしくお願いします。


<要素を挿入するとき、変更が必要なポインタは4箇所です。挿入した要素のnextとprev、挿入した要素の直前の要素のnext、挿入した要素の直後の要素のprevの4つです。また、削除したときには2箇所変更します。削除した要素の直前の要素のnext、削除した要素の直後の要素のprevの2つです。この辺りのポインタの付け替え作業が理解できれば、双方向リストの実装は難しくありません。>

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

struct LIST
{
    int data;           /* 具体的なデータ */
    struct LIST* next;  /* 次の要素へのポインタ */
    struct LIST* prev;  /* 前の要素へのポインタ */
};
struct LIST head;  /* リストの先頭要素(ダミー) */

/* プロトタイプ宣言 */
void addlist(void);
void deletelist(void);
void showlist(void);


int main(void)
{
    char command;
    
    head.next = &head;  /* リストは循環しているので、先頭の次は先頭 */
    head.prev = &head;  /* リストは循環しているので、先頭の前は先頭 */
    
    do
    {
        puts( "コマンドを入力して下さい" );
        puts( "双方向リストに要素を追加:a" );
        puts( "双方向リストから要素を削除:b" );
        puts( "双方向リストの内容を表示:c" );
        puts( "終了:q" );
        scanf( "%c", &command );
        
        switch( command )
        {
        case 'a':   /* 追加 */
            addlist();
            break;
        case 'b':   /* 削除 */
            deletelist();
            break;
        case 'c':   /* 表示 */
            showlist();
            break;
        case 'q':   /* 終了 */
            break;
        default:    /* 無効 */
            puts( "コマンドが正しくありません" );
            break;
        }
        
        puts( "" );
        fflush( stdin );
        
    }while( command != 'q' );
    
    return 0;
}

/* 双方向リストに要素を追加する */
void addlist(void)
{
    struct LIST* p, *newcell;
    int data;
    
    puts( "追加する要素の値を入力して下さい" );
    scanf( "%d", &data );
    
    p = head.next;   /* 先頭要素の次の要素のアドレス */
    if( p != NULL )  /* リストは空ではないか */
    {
        while( p != &head ) /* 先頭要素に戻ってきたら循環したことになるので終了 */
        {
            p = p->next;  /* 次の要素へ進む */
        }
    }
    
    /* 新しく追加する要素のためのメモリ領域を確保する */
    newcell = malloc( sizeof(struct LIST) );
    if( newcell == NULL )
    {
        puts( "メモリ不足" );
        return;
    }
    
    newcell->data = data;     /* 新しい要素のデータを設定 */
    newcell->next = p->next;  /* 新しい要素の次の要素へのアドレスを設定 */
    newcell->prev = p;        /* 新しい要素の前の要素へのアドレスを設定 */
    p->next->prev = newcell;  /* 新しい要素の直後の要素のprevに、新しい要素のアドレスを設定 */
    p->next = newcell;        /* 新しい要素の直前の要素のnextに、新しい要素のアドレスを設定 */
}

/* 双方向リストから要素を削除する */
void deletelist(void)
{
    struct LIST *p;
    int data;
    
    puts( "削除する要素の値を入力して下さい" );
    scanf( "%d", &data );
    
    p = head.next;   /* 先頭要素の次の要素のアドレス */
    if( p != NULL )  /* リストは空ではないか */
    {
        while(p != &head && data != p->data)
        {
            p = p->next;   /* 次の要素へ進む */
        }
    }
    
    if( p == &head )  /* 一致する値がないままリストの末尾まで来た */
    {
        puts( "指定された要素はリスト内に存在しません" );
    }
    else
    {
        p->prev->next = p->next; /* 削除する要素の直後の要素を再設定 */
        p->next->prev = p->prev; /* 削除する要素の直前の要素を再設定 */
        free( p );          /* 要素はmallocで確保されているのでfreeで解放する */
    }
}

/* 双方向リストの内容を表示する */
void showlist(void)
{
    struct LIST *p;
    
    for( p=head.next; p!=&head; p=p->next )
    {
        printf( "%d\n", p->data );
    }
} 



このプログラム例は、双方向循環リストになっています。双方向でないリストに比べて、挿入や削除の操作の際に、prevポインタも変更していかなければならない点が難しくなっています。

要素を挿入するとき、変更が必要なポインタは4箇所です。挿入した要素のnextとprev、挿入した要素の直前の要素のnext、挿入した要素の直後の要素のprevの4つです。また、削除したときには2箇所変更します。削除した要素の直前の要素のnext、削除した要素の直後の要素のprevの2つです。この辺りのポインタの付け替え作業が理解できれば、双方向リストの実装は難しくありません。




この投稿にコメントする

削除パスワード

発言に関する情報 題名 投稿番号 投稿者名 投稿日時
<子記事> Re:双方向リスト 26124 REE 2006/02/15 10:17:59


No.26124

Re:双方向リスト
投稿者---REE(2006/02/15 10:17:59)


>この辺の意味を分かりません。
>よろしくお願いします。
>
>
><要素を挿入するとき、変更が必要なポインタは4箇所です。挿入した要素のnextとprev、挿入した要素の直前の要素のnext、挿入した要素の直後の要素のprevの4つです。また、削除したときには2箇所変更します。削除した要素の直前の要素のnext、削除した要素の直後の要素のprevの2つです。この辺りのポインタの付け替え作業が理解できれば、双方向リストの実装は難しくありません。>

文章だけで、分かりにくい場合には、図を描いて見ましょう。
ポインタの指す先を矢印で表現するとよいです。
そして、その図から、挿入または、削除してみましょう。




この投稿にコメントする

削除パスワード

管理者用メニュー    ツリーに戻る    携帯用URL    ホームページ    ログ    タグ一覧