CASL U - 2つのデータテーブルから共通データを取り出す
 前へ 目次へ 次へ

2つのデータテーブルから共通データを取り出す

 2つのデータテーブルATBLとBTBLがあり、正の整数(1〜32767)がデータとして複数個(1つの番地に1つのデータ)格納されている。それぞれのテーブルのデータは昇順(小さい順)に整列されており、データの最後には-1が格納されている。また、それぞれのテーブルのデータには重複がないものとする。
 この2つのテーブルから共通するデータを取り出し、データテーブルCTBLに記憶する副プログラムSAMEを作成する。CTBLの最後にも終わりのデータとして-1を格納する。
 (これらのデータテーブルは一次元配列と同じである。)

 2つのデータテーブルATBL, BTBLから共通するデータを取りだし、CTBLに格納する。データの終わりとして-1を格納する。 

 それぞれのテーブルの場所を指し示すものを用意し、Pa, Pb, Pc とする。すなわち、Pa, Pb, Pcにはそれぞれのテーブルの先頭アドレスが記憶されている。
 右図《図0》のようにデータが格納されているときについて考えてみる。

Pa番地とPb番地の内容を比較する。
  → Pa(102) > Pb(101) なので Pb を1加算する。 《図1》
Pa番地とPb+1番地の内容を比較する。
  → Pa(102) < Pb(108) なので Pa を1加算する。 《図2》
Pa+1番地とPb+1番地の内容を比較する。
  → Pa(108) = Pb(108) なので データをPc番地に格納する。
     Pa, Pb, Pc をそれぞれ1加算する。       《図3》
Pa+2番地とPb+2番地の内容を比較する。
  → Pa(203) < Pb(208) なので Pa を1加算する。 《図4》
Pa+3番地とPb+2番地の内容を比較する。
  → Pa(432) > Pb(208) なので Pb を1加算する。 《図5》
Pa+3番地とPb+3番地の内容を比較する。
  → Pa(432) < Pb(678) なので Pa を1加算する。 《図6》
Pa+4番地とPb+3番地の内容を比較する。
  → Pa(678) = Pb(678) なので データをPc+1番地に格納する。
     Pa, Pb, Pc をそれぞれ1加算する。       《図7》
Pa+5番地とPb+4番地の内容を比較する。
  → Pa(876) = Pb(876) なので データをPc+2番地に格納する。
     Pa, Pb, Pc をそれぞれ1加算する。       《図8》
Pa+6番地とPb+5番地の内容を比較する。
  → Pa(-1) < Pb(999) であるが、 一方のデータが終了した(なくなった)ので
     Pc+3番地に-1を格納して、処理は終了する。 《図9》

《図》をクリックすると図が変わります。

処理のポイント
 上の例でわかったことは、次の3点である。
    (1) Pa番地とPb番地の内容を比較し、一致したときは、
      → @そのデータをPc番地に格納し、APa, Pb, Pc番地をそれぞれ 1加算する。
    (2) Pa番地とPb番地の内容を比較し、一致しないときは、
      → 小さい方の番地を1加算する。
    (3) どちらかのテーブルのデータがなくなったときは、
      → @Pc番地に-1を格納し、A処理を終了する。


 ATBL, BTBL, CTBLのテーブルの先頭アドレスが順にメモリに記憶されており、その先頭アドレスをGR1に格納して副プログラムSAMEに渡す。共通するデータはCTBLに格納される。

(GR1)
(GR1)+1
(GR1)+2
ATBLの先頭アドレス
BTBLの先頭アドレス
CTBLの先頭アドレス
MAIN2    START
         LAD     GR1, ADDR
         CALL    SAME
         RET
ADDR     DC      ATBL, BTBL, CTBL
ATBL     DC      102, 108, 203, 432, 678, 876, -1
BTBL     DC      101, 108, 208, 678, 876, 999, -1
CTBL     DS      7
         END
SAME     START
         RPUSH
         LD      GR2, 1, GR1   ;PB,BTBLの先頭アドレス.
         LD      GR3, 2, GR1   ;PC,CTBLの先頭アドレス.
         LD      GR1, 0, GR1   ;PA,ATBLの先頭アドレス.
LOOP     LD      GR4, 0, GR1   ;(a)PA番地のデータ.
         CPA     GR4, EOD      ;終わりか?
         JZE     OWARI
         LD      GR4, 0, GR2   ;(b)PB番地のデータ.
         CPA     GR4, EOD      ;終わりか?
         JZE     OWARI
         CPA     GR4, 0, GR1   ;(c)PBとPAを比較.
         JZE     ONAJI         ;PB=PA
         JPL     BIGPB         ;PB>PA
BIGPA    LAD     GR2, 1, GR2   ;PB=PB+1
         JUMP    LOOP
BIGPB    LAD     GR1, 1, GR1   ;PA=PA+1
         JUMP    LOOP
ONAJI    ST      GR4, 0, GR3   ;データをPCに格納.
         LAD     GR1, 1, GR1   ;PA=PA+1
         LAD     GR2, 1, GR2   ;PB=PB+1
         LAD     GR3, 1, GR3   ;PC=PC+1
         JUMP    LOOP
OWARI    ST      GR4, 0, GR3   ;PCに終わりのデータを格納.
         RPOP
         RET
EOD      DC      -1    ;終わりのデータ.
         END

 プログラムでは、(a),(b)のように比較の前にデータを取り出すので、そのときに"処理のポイント(3)"の終わりかどうかを判定している。(a)でPa番地の内容がGR4に格納され、(b)でPb番地の内容が同じくGR4に格納される。(c)でPa番地の内容とPb番地の内容を比較するときにはGR4はPb番地の内容であり、Pa番地の内容はなくなっているので指標レジスタとして 0, GR1 のように書いている。
 ラベルOWARIに来たとき、GR4の内容は終わりのデータである-1となっているので、GR4の内容をPc番地に格納している。

 文字列を処理する場合も同じように、文字コードが一次元配列に格納されていると考えればよい。


 前へ 目次へ 次へ
 CASL U Copyright © 2003  Hiroshi Masuda

 

 

inserted by FC2 system