小白学アルゴリズム1.2——チェーンテーブル

小白学アルゴリズム1.2——チェーンテーブル
ラベル:白白学アルゴリズム
1.チェーンテーブルとは
チェーンテーブルは、再帰的なデータ構造であり、空であるか、次のノードを指している.

struct node{
    int data;
    node* next;
    };

は抽象的な感じに見えますが、私自身の理解では、チェーンテーブルのコンピュータ内の構造を車でシミュレートすることができます.「チェーンテーブルノード」は、チェーンの上にある「円柱ノード」であり、各「円柱ノード」は、最大2つの他の「円柱ノード」に接続され、チェーンが環状でない場合、ヘッドとテールの「円柱ノード」は、1つの他の「円柱ノード」にのみ接続される

である.

ノードは、一般に、データだけでなく、他のノードへのポインタまたは

参照も含む.

チェーンテーブルは方向があり、一般的には一方向チェーンテーブルと双方向チェーンテーブルに分けられる.一方的なチェーンテーブルの結点は地下党のように、前の人は次の人を探すしかなく、次の人は前の人を探すことができません.双方向チェーンテーブルのノードは階段のように上り下り可能ですが、

を越えることはできません.

一方向チェーンテーブルには、一般に1つの変数がチェーンヘッダを指し、双方向チェーンテーブルには一般的に2つの変数がチェーンヘッダとテール

を指す.

チェーンテーブルの一般的な操作は、新規、追加、削除、および変更

です.

チェーンテーブルは空間の利用率が高く,配列の重要な代替方式である

である.
2.一方向チェーンテーブルで一つのスタックを実現する
チェーンテーブルは動的にメモリを申請するので、チェーンテーブルのサイズを設定する必要はありません.チェーンテーブルの操作を行うためにheadを設定するだけでいいです.node* head = null;2.1インスタック

void push(int mydata)
{
    node* p = (node*)malloc(sizeof(node));//      
    p->data = mydata;
    p->next = NULL;
    if (head == NULL)
        head = p;
    else
    {
        p->next = head;
        head = p;
    }
}

mallocはヘッダファイルstdlibを含む必要がある.h

mallocの役割はメモリの中で1段のメモリ空間を申請することであり、戻り値はvoid*タイプであり、パラメータは申請空間の大きさを表し、一般的にsizeof()関数と協力して

を使用する.

sizeof()パラメータは、一般に、構造体nodeint

のようなデータ型である.

malloc関数の戻り値を使用するには、特定のタイプ

に強制的に変換する必要がある.

スタックに入るとき、チェーンテーブルが空の場合、メモリ領域を申請し、最初のノードとします.チェーンテーブルが空でない場合は、メモリ領域を申請し、元のチェーンテーブルヘッダの前に

を配置します.

JavaまたはC++ではnewを使用して空間

を申請することができる.
2.2出庫

int pop()
{
    int mydata = head->data;
    node* p = head;
    head = head->next;
    free(p);//    
    return mydata;
}

C/C++言語で自分が申請したメモリは自分で解放され、mallocとfreeは一つ一つ対応し、newとdeleteは一つ一つ

に対応する.

Javaメモリを解放する必要はありません

2.3スタックが空かどうか

bool isEmpty()
{
    return head == NULL;
}

2.4主関数
この主関数は4~0を順次スタックに入れ,その後順次スタックを出る.

int main(int argc, char* argv[])
{
    printf("        ：http://blog.csdn.net/xuelabizp
");

    int n = 5;
    while (n--)
    {
        printf("%d\t",n);
        push(n);
    }
    printf("
");

    while (!isEmpty())
    {
        printf("%d\t",pop());
    }

    printf("
");
    return 0;
}

運転結果は以下の通り:逆順序出力,OK~
3.まとめ

ノード要素にnode*タイプのメンバーを追加することができ、pushの新しい数値のたびに、新しいノードがヘッドノードを指すことができ、ヘッドノードが新しいノードを指すことができる.これは双方向チェーンテーブルであり、もちろんチェーンテーブルの尾を常に指すtail

も必要である.

チェーンテーブルの削除、挿入と修正はチェーンテーブル全体を遍歴し、削除または修正されたノードまたは挿入の位置を見つけて操作すればよい.肝心なのは削除と挿入が前後のノードの関係を処理しなければならないことであり、矩形図を描いて

を理解することができる.

主流言語にはチェーンテーブルテンプレートクラスがあり、

を直接使用することができます.