Car, Cdr で連鎖

5
4
3
2
1
11
12
13

Binary Tree の Car と Cdr を使って連鎖します。

前田稔(Maeda Minoru)の超初心者のプログラム入門

プログラムの説明

  1. フォルダーに次のファイルを格納して下さい。
    /******************************************/
    /*★ Binary Tree 末尾に連鎖     前田 稔 ★*/
    /******************************************/
    using System;
    
    class console
    {
        public static void Main()
        {   Tree    pt = new Tree();
    
            for(int i=1; i<6; i++)  pt.SetCar(i);
            for(int i=11; i<14; i++)  pt.SetCdr(i);
            pt.Print(pt.Top);
        }
    }
    
    class Tree
    {
        Tree            car;    //前のポインタ
        Tree            cdr;    //後のポインタ
        public  int     val;    //データの格納領域
        Tree            top;    //Binary Tree のトップポインタ
    
        //Constructor
        public Tree()
        {   car = null;
            cdr = null;
            top = null;
        }
        //top を取得
        public Tree Top
        {   get
            {   return top;  }
        }
        //car の末端に連鎖
        public void SetCar(int v)
        {   Tree    wk;
            Tree    wp;
    
            wk= new Tree();
            wk.val= v;
            if (top==null)
            {   top= wk;
                return;
            }
            for(wp=top; wp.car!=null; wp=wp.car);
            wp.car= wk;
            return;
        }
        //cdr の末端に連鎖
        public void SetCdr(int v)
        {   Tree    wk;
            Tree    wp;
    
            wk= new Tree();
            wk.val= v;
            if (top==null)
            {   top= wk;
                return;
            }
            for(wp=top; wp.cdr!=null; wp=wp.cdr);
            wp.cdr= wk;
            return;
        }
        //Binary Tree を表示
        public void Print(Tree pt)
        {   if (pt==null)   return;
            if (pt.car!=null)   Print(pt.car);
            Console.WriteLine("{0} ",pt.val);
            if (pt.cdr!=null)   Print(pt.cdr);
        }
    }
    
  2. Binary Tree 構造とはセルから二個のポインタで次のセルを連鎖したデータ構造です。
    セルは次のセルに連鎖するための car と cdr のポインタとデータ領域で構成されます。
    carポインタ cdrポインタ データ
  3. Main() 関数から 1~5 の値で car に連鎖し、11~13 の値で cdr に連鎖します。
    次に連鎖をたどって Binary Tree の全データを表示します。
        public static void Main()
        {   Tree    pt = new Tree();
    
            for(int i=1; i<6; i++)  pt.SetCar(i);
            for(int i=11; i<14; i++)  pt.SetCdr(i);
            pt.Print(pt.Top);
        }
        
  4. Car の末尾にセルを連鎖する SetCar 関数です。
    new で新しいセルを割り当てて v を格納します。
    top が null のとき(最初のデータ)は top から連鎖します。
    二件目以降のデータは Car の末尾のセルを検索して wp に格納します。
    wp.car から wk に連鎖します。
    SetCdr 関数も同じ要領です。
        //car の末端に連鎖
        public void SetCar(int v)
        {   Tree    wk;
            Tree    wp;
    
            wk= new Tree();
            wk.val= v;
            if (top==null)
            {   top= wk;
                return;
            }
            for(wp=top; wp.car!=null; wp=wp.car);
            wp.car= wk;
            return;
        }
        
  5. Print 関数で Binary Tree に格納されている値を印字します。
    このメソッド(関数)は再起で組まれています。
    Print() 関数の中から Print() 関数を呼び出していることに注目して下さい。
    pt から car と cdr で連鎖されている全てのセルが印字されます。
    if (pt.car!=null) で判定していますが、判定を省略することも出来ます。
    判定を省略するとどうなるか考えてみて下さい。
        //Binary Tree を表示
        public void Print(Tree pt)
        {   if (pt==null)   return;
            if (pt.car!=null)   Print(pt.car);
            Console.WriteLine("{0} ",pt.val);
            if (pt.cdr!=null)   Print(pt.cdr);
        }
        

超初心者のプログラム入門(C# Frame Work)