welcome: please sign in
location: "線形リスト"の差分
23と41のリビジョン間の差分 (その間の編集: 18回)
2009-11-05 12:39:39時点のリビジョン23
サイズ: 3017
編集者: masahiko
コメント:
2010-11-29 13:13:10時点のリビジョン41
サイズ: 3281
編集者: masahiko
コメント:
削除された箇所はこのように表示されます。 追加された箇所はこのように表示されます。
行 1: 行 1:
## page was renamed from リスト処理
行 3: 行 2:
線形リストは同じ形式のデータが一列に並んだものです。<<BR>> 同じ形式のデータが一列に並んでおり、
前から順にたどりながら参照できる形のものを'''線形リスト'''といいます。
行 5: 行 5:
データの追加や削除が配列と比べて楽に行えます。<<BR>>
真ん中あたりにデータを追加する場合を考えると分かります。
これも'''線形リスト'''の1種です。
 . {{attachment:chain42.png}}
行 8: 行 8:
Javaで記述してみましょう。 線形リストの特徴
 1. 前から順にすべてのデータをたどることができます。
 1. データの追加や削除が配列と比べて楽に行えます。
行 10: 行 13:
このようなインスタンスを使います。
 . {{attachment:list1.png}}
 . 1つ目の変数には値を保存します
 . 2つ目の変数には次の項目へのリンクを記入します。
3つのインスタンスをつないだ例を示します。
 . {{attachment:list2.png}}
 . これより先につながっていないことを、'''null'''という値で表します。
=== 線形リストの修正 ===
次のような処理を考えましょう。
行 18: 行 16:
'''null'''はシステムで用意されている'''定数'''です。
 * 参照型の変数はnullで初期化されます。
 * nullはどこも参照していないことを表します。
 * リストの先頭に追加
 * リストの途中に追加
 * リストの最後に追加
 * リストの先頭を削除
 * リストの途中を削除
 * リストの最後を削除

つぎのことが分かっています。

追加する場合
 追加したい位置の直前にあるオブジェクトを参照できれば簡単に行える。

削除する場合
 取り除きたい位置の直前にあるオブジェクトを参照できれば簡単に行える。
行 22: 行 31:
=== 追加 ===
途中にデータを追加するには、リンク2箇所を修正すればよい。
 . {{attachment:list3.png}}
=== つながっているものすべてを表示するメソッド ===
これは以前に作成したものです。
 {{{#!java
void showAll()
{
 Chain c;

 c = this;
 System.out.println("(");
 while (c != null)
 {
  c.show();
  c = c.next;
 }
 System.out.println(")");
}
 }}}
これをもとにして、次の2つのメソッドを作成します。
行 26: 行 50:
=== 削除 ===
途中のデータを削除するには、リンク1箇所を修正すればよい。
 . {{attachment:list4.png}}
削除されたデータからのリンクが残っていますが、リストをたどってこのデータにたどり着くことはできません。
----
=== サンプル ===
値としてItemクラスのインスタンスを使った例です。
=== つながっている個数を返すメソッド ===
行 34: 行 52:
クラス名は List1 としました。
 . {{attachment:list1.png}}
属性(インスタンス変数)の型は
 . 値にはItemクラスのインスタンスが入るので Item
 . リンクには次のデータを記憶するためのオブジェクトすなわち List1のインスタンスが入りますから List1
となります。
つながっている個数を返すメソッドlengthを作ります。

返す値はintです。次の修正が必要。
 * メソッドの型宣言
 * return

処理内容
 showAllではオブジェクト1つずつに対してshowを行っていたので、
 ここでカウントを行えばよい。

変数の宣言と初期化を加え、不要な部分を除けば完成。
行 42: 行 65:
 public class List1
 {
  Item val;
  List1 link;
  
  void dispList()
  {
   List1 x;
   
   x = this;
   while(x != null)
   {
    x.val.disp();
    x = x.link;
   }
  }
  
  public static void main(String[] args)
  {
   List1 a;
   List1 b;
   List1 c;
   
   a = new List1();
   a.val = new Food("パン", 150, 200.0, 200.0);
   b = new List1();
   a.link = b;
   b.val = new Drink("コーヒー", 120, 250);
   c = new List1();
   b.link = c;
   c.val = new Food("みかん", 100, 150.0, 200.0);
   
   a.dispList();
  }
 }
int length()
{
 Chain c = this;
 int cnt = 0;

 while (c != null)
 {
  cnt++;
  c = c.next;
 }
 return cnt;
}
行 78: 行 78:
mainメソッドでは、変数a,b,cの3つを用いて図のようなリストを作っています。
 . {{attachment:list5.png}}
最後に
 . a.dispList();
により、aに対してメソッドdispList()を行っています。
行 84: 行 79:
メソッドの動作を追っかけてみましょう。
 1. aの値がthisに対応づけられます。
 1. x = this; により、thisに入っている値が変数xに代入されます。これはaの値と同じです。
 1. 11行目のwhileの条件判定を行います。xには先に作ったリストの参照が入っておりnul
----
=== 指定された位置にあるオブジェクトを返すメソッド ===
定された位置にあるオブジェクトを返すメソッドnthを作ります。

 * 引数として位置を表す数値(int)を取ります。
 * 返す値はChainです。
次の修正が必要。
 * メソッドの型宣言
 * return

処理内容
 カウントを行い指定の箇所まできたら、そのとき指しているオブジェクトを返せばよい。

条件はwhileの条件に追加。

 {{{#!java
Chain nth(int n)
{
 Chain c = this;
 int cnt = 0;

 while (c != null && cnt < n)
 {
  cnt++;
  c = c.next;
 }
 return c;
}
 }}}
 . {{attachment:chain41.png}}

----
=== メソッド内でメソッドを使う ===
メソッド内でメソッドを呼び出すこともできます。

このメソッドは次回使うので追加しておくこと。
 {{{#!java
void showContent()
{
 next.showAll();
}
 }}}
----
=== 線形リストを修正する ===
上で作成したメソッドを使うと、リストの修正が簡単にできます。


 aが参照しているリストの3番目のオブジェクトを削除する。
 {{{
Chain a, temp;
...
temp = a.nth(2);
temp.next = temp.next.next;
 }}}

線形リスト

同じ形式のデータが一列に並んでおり、 前から順にたどりながら参照できる形のものを線形リストといいます。

これも線形リストの1種です。

  • chain42.png

線形リストの特徴

  1. 前から順にすべてのデータをたどることができます。
  2. データの追加や削除が配列と比べて楽に行えます。


線形リストの修正

次のような処理を考えましょう。

  • リストの先頭に追加
  • リストの途中に追加
  • リストの最後に追加
  • リストの先頭を削除
  • リストの途中を削除
  • リストの最後を削除

つぎのことが分かっています。

追加する場合

  • 追加したい位置の直前にあるオブジェクトを参照できれば簡単に行える。

削除する場合

  • 取り除きたい位置の直前にあるオブジェクトを参照できれば簡単に行える。


つながっているものすべてを表示するメソッド

これは以前に作成したものです。

  •    1 void showAll()
       2 {
       3         Chain c;
       4 
       5         c = this;
       6         System.out.println("(");
       7         while (c != null)
       8         {
       9                 c.show();
      10                 c = c.next;
      11         }
      12         System.out.println(")");
      13 }
    

これをもとにして、次の2つのメソッドを作成します。


つながっている個数を返すメソッド

つながっている個数を返すメソッドlengthを作ります。

返す値はintです。次の修正が必要。

  • メソッドの型宣言
  • return

処理内容

  • showAllではオブジェクト1つずつに対してshowを行っていたので、 ここでカウントを行えばよい。

変数の宣言と初期化を加え、不要な部分を除けば完成。

  •    1 int length()
       2 {
       3         Chain c = this;
       4         int cnt = 0;
       5 
       6         while (c != null)
       7         {
       8                 cnt++;
       9                 c = c.next;
      10         }
      11         return cnt;
      12 }
    


指定された位置にあるオブジェクトを返すメソッド

定された位置にあるオブジェクトを返すメソッドnthを作ります。

  • 引数として位置を表す数値(int)を取ります。
  • 返す値はChainです。

次の修正が必要。

  • メソッドの型宣言
  • return

処理内容

  • カウントを行い指定の箇所まできたら、そのとき指しているオブジェクトを返せばよい。

条件はwhileの条件に追加。

  •    1 Chain nth(int n)
       2 {
       3         Chain c = this;
       4         int cnt = 0;
       5 
       6         while (c != null && cnt < n)
       7         {
       8                 cnt++;
       9                 c = c.next;
      10         }
      11         return c;
      12 }
    
  • chain41.png


メソッド内でメソッドを使う

メソッド内でメソッドを呼び出すこともできます。

このメソッドは次回使うので追加しておくこと。

  •    1 void showContent()
       2 {
       3         next.showAll();
       4 }
    


線形リストを修正する

上で作成したメソッドを使うと、リストの修正が簡単にできます。

  • aが参照しているリストの3番目のオブジェクトを削除する。
    Chain a, temp;
    ...
    temp = a.nth(2);
    temp.next = temp.next.next;

線形リスト (最終更新日時 2010-11-29 13:13:10 更新者 masahiko)