ぼんさい塾

ぼんさいノートと補遺に関する素材や注釈です.ミスが多いので初稿から1週間を経た重要な修正のみ最終更新日を残しています.

広告

※このエリアは、60日間投稿が無い場合に表示されます。記事を投稿すると、表示されなくなります。

g++による演習 (5)

2014-02-20 11:43:00 | 暮らし
progC.pdf
progC-s.pdf
progC-e.pdf
記事一覧

                             実行結果

 

旧 p5.cpp の誤動作は強引な型変換が原因ではありませんでした.下記プログラムは Visual C++ でも正常に動作します.
※ 誤動作は STreeC(Cell* p, int n) で idle チェインを修正しなかったことが原因でした.

 

/* --- p5.cpp (全角 < は半角 < に置換してください)--- */
//--- p5.h --------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
class Node{
public:
  int d; Node *l, *r;
  Node(void);
  Node(int);
  void show(char*, Node*);
};
class Tree{
public:
  Node *root, *tmp, *idle; int sz;
  Tree(void);
  Tree(Node*, int);
  void push(Node*);
  void pop(void);
  virtual void ins(int) = 0;
  virtual void del(int) = 0;
  virtual void show(void);
};
class STree: public Tree{
public:
  STree(Node*, int);
  Node* search(int);
  void ins(int);
  void del(int);
};
class Cell: public Node{
public:
  char s[80];
  Cell(void);
  Cell(int, char*);
  char* sp(Node *p);
};
class STreeC: public STree{
public:
  Cell c;
  STreeC(Cell*, int);
  void ins(int, char*);
  void show(void);
};
//--- p51.cpp -----------------------------------------------
//#include "p5.h"
Node::Node(void){d = 0; l = r = NULL;}

//Node::Node(int d0){Node( ); d = d0;}
Node::Node(int d0){d = d0; l = r = NULL;}
void Node::show(char *s, Node *p){
    char sl[8], sr[8];
    if(strlen(s) > 7){exit(1);}
    if(p == NULL) return;
    strcpy(sl, s); strcpy(sr, s);
    show(strcat(sl, "L"), p->l);
    printf("%s: %d\n", s, p->d);
    show(strcat(sr, "R"), p->r);
}
Tree::Tree(void){root = tmp = idle = NULL; sz = 0;}
Tree::Tree(Node *p, int n){
    root = tmp = NULL; idle = p; sz = n;
    for(int k = 0; k < n-1; k++){p[k].r = &p[k+1];}
    p[n-1].r = NULL;
}
void Tree::push(Node *p){p->r = idle; idle = p; sz++;}
void Tree::pop(void){
    if(sz == 0){exit(1);}
    tmp = idle; idle = idle->r; sz--;
    tmp->l = tmp->r = NULL;
}
void Tree::show(void){root->show("", root);}
STree::STree(Node *p, int n): Tree(p, n){ }
Node* STree::search(int k){
  Node *p=root;
  while(p != NULL && p->d != k){
    if(p->d < k){p = p->r;}else{p = p->l;}
  }
  if(p == NULL){printf("not ");}
  printf("found\n"); return p;
}
void STree::ins(int k){
  Node *p=root;
  pop( ); if(tmp == NULL) return;
  while(p != NULL && k != p->d){
    if(k < p->d){
      if(p->l != NULL){p = p->l;}else{p->l = tmp; break;}
    }else{
      if(p->r != NULL){p = p->r;}else{p->r = tmp; break;}
    }
  }
  tmp->d = k; if(p == NULL){root = tmp;}
} //既存なら変更なし
void STree::del(int k){ //削除
  Node *p=root, *p1=root, *p2, *p3;
  while(p != NULL && p->d != k){
    p1 = p; //if(p->d == k){break;}
    p = (k < p->d ? p->l: p->r);
  } //「□?□:□」は[#19%31B]
  p2 = p; if(p == NULL){return;}
  if(p->l == NULL || p->r == NULL){
    if(p->l == NULL){p = p->r;}else{p = p->l;}
  }else{
    p3 = p = p->r;
    while(p->l != NULL){ p3 = p;
      if(p->l != NULL){p = p->l;}
    }
    if(p != p3){p3->l = p->r;}
    if(p == p3){p2->r = p3->r;}
    p->l = p2->l; p->r = p2->r;
  }
  push(p2);
  if(p1 == p2){root = p;}
  else if(p1->l == p2){p1->l = p;}
  else{p1->r = p;}
} //不在なら変更なし
//--- p52.cpp -----------------------------------------------
//#include "p5.h"
Cell::Cell( ): Node( ){s[0] = '\0';}

Cell::Cell(int d0, char *s0): Node(d0){
  char *p=s; strcpy(p, s0);//unsafe
}
char* Cell::sp(Node *p){
  return ((Cell*)p)->s;
}
STreeC::STreeC(Cell* p, int n): STree(p, n){
    for(int k = 0; k < n-1; k++){p[k].r = &p[k+1];}
    p[n-1].r = NULL;
}
void STreeC::ins(int k, char *q){
  STree::ins(k);
  Node *p=tmp;
  char *r=c.sp(p);
  strcpy(r, q);//unsafe
  //printf("ins: %p, %p, %p, %s\n", p, &r, r, r);
}
void STreeC::show(void){STree::show( );}
int main(void){//main2
  Cell n[8]; STreeC t(n, 8);
  t.ins(7, "abc"); t.ins(3, "pq"); t.ins(5, "xyz");
  t.ins(9, "123"); t.ins(2, "89"); t.show( );
  printf("\n"); t.del(3); t.show( );
  for(int k = 0; k < 8; k++){
    printf("%p, %d, %p, %p, %s\n",
     &n[k], n[k].d, n[k].l, n[k].r, n[k].s);
  }
  getchar( ); return 0;
}

コメント

参照について

2014-02-04 17:10:29 | 暮らし
progJ.pdf
progJ-s.pdf
progJ-e.pdf

記事一覧

                     Javaにおける参照の値渡し [4]

「参照」に関する説明をGoogleで検索してみました.

Javaで「ポインタ」の代わりに「参照」という用語を用いているので,C++プログラマが「参照渡し」と「参照の値渡し」の違いを強調する意味が分かり難いと感じる諸君のために駄文を書きました --- 素人の無責任見解なので,鵜呑みにせず自分で調べてください.

私見: (本質的に違うが) C++ の「参照渡し」を知っても感激はない --- 無くても困らない.
[3] の「オブジェクトの参照と配列参照だけはポインタを持っているが」のように「参照」もポインタを使って説明するのが分かり易いようです.C++ では「参照」とは実体に対する「別名」であることが強調されていますが,参照変数も (広義というより普通の意味の) ポインタの一種と考えていいと思います --- NULL (Pascal では nil) も許す方が自然.  Cでは「int *p;」と宣言したポインタ p は,その値にかかわらず「*p」を先頭番地が p である領域に int 型の変数があるとして (勝手に決め込んで) 処理されますが,これは非常に安直な (融通性があふれた?) 仕様で,この領域が実際に所望のデータ型を格納するように宣言されている場合に用途を限定したのが「参照」です --- したがって宣言時には参照先がなくても「x = new int[4];」のように動的に領域を割り当てれば,x はint[4] 型の領域への参照になります(x は名無しの領域 new int[4] の別名?).
※ Javaで「参照」を使わず,「ポインタを本来の用途に限定する」 (変な使い方は許さない) と述べていれば「参照の値渡し」という込み入った表現が(Cも含めて)「ポインタ渡し」で済んだはずです.

参考資料([n]は本文でも引用, *.pptはブロック解除が面倒なので未調査):
[1] 参照 (情報工学) - Wikipedia
  http://ja.wikipedia.org/wiki/%E5%8F%82%E7%85%A7_(%E6%83%85%E5%A0%B1%E5%B7%A5%E5%AD%A6)
以下で説明するのはC++のそれではなく、一般概念である。C++の参照については、ポインタ (プログラミング)#参照を参照のこと。
[2] ポインタ (プログラミング) - Wikipedia
  http://ja.wikipedia.org/wiki/%E3%83%9D%E3%82%A4%E3%83%B3%E3%82%BF_(%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0)#.E5.8F.82.E7.85.A7
C++における参照は、ポインタと同様「変数がメモリ上に置かれている場所」と解される場合もあるが、それよりもむしろ「その変数を参照する(=変数の値を操作したり出来る)権限」と解されることが多い。
[3] JavaとC++の比較 - Wikipedia
  http://ja.wikipedia.org/wiki/Java%E3%81%A8C%2B%2B%E3%81%AE%E6%AF%94%E8%BC%83
「2.2 意味論」の5番目の項目:
C++ではポインタを使ってメモリアドレスを直接操作できる。Javaはメモリアドレスを直接操作できるポインタを持っていない(オブジェクトの参照と配列参照だけはポインタを持っているが、どちらもメモリアドレスの直接アクセスを許可しない)。C++ではポインタへのポインタを構築できるが、Javaではオブジェクトアクセスにだけ参照を用いる。
※ 引用する資料は progC-e.pdf
[4] Javaの参照型変数とセキュリティ(1/2):CodeZine
  http://codezine.jp/article/detail/6704
『Java言語仕様』でもわざわざ次のように記述されています。
2つの変数が同じオブジェクトへの参照を保持している場合、どちらか一方の変数に設定されたオブジェクト参照を用いてオブジェクトの状態を変更することができ、変更された状態はもう一方の変数に設定された参照を用いて取得することができる。
※ 要するに,この方が実装が楽だからです.
[5] C++編(言語解説) 第15章 参照
  http://www.geocities.jp/ky_webid/cpp/language/015.html
つまり、参照変数を宣言するときには、必ず初期値が必要だということです。理由は「参照変数は、他の変数の別名」だからです。
[6] 参照渡し
  http://wisdom.sakura.ne.jp/programming/java/java23.html
JAVA言語にはポインタのようなものは存在しません.そのかわり、JAVA言語は配列、及びオブジェクトは参照渡しなのです
[7] 値渡しと参照渡し (と参照の値渡し) - ぐるぐる
  http://bleis-tift.hatenablog.com/entry/20090603/1244031097
しかし、例えば Java ではミュータブルなオブジェクト *1 を渡した場合、呼出し元の値自体を変更できるという勘違いをする可能性があるため、この説明はあまり好ましくない。
[8] イミュータブル - Wikipedia
  http://ja.wikipedia.org/wiki/%E3%82%A4%E3%83%9F%E3%83%A5%E3%83%BC%E3%82%BF%E3%83%96%E3%83%AB
イミュータブル(immutable)なオブジェクトとは、作成後にその状態を変えることのできないオブジェクトのことである。
--------------------
[9] ポインタ渡しと参照渡しのは何が違うの? - Yahoo!知恵袋
  http://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q1320144958
[10] 参照とポインタ
  http://sealsoft.jp/ptr_and_ref.html
[11] C++「ポインタの参照渡し」と「ポインタ渡し」 | Programer's memo
  http://of.studio23c.com/index.php/archives/248
[12] ポインタと参照の棲み分け - KAB-studio
  http://www.kab-studio.biz/Programing/Codian/Pointer/10.html

補足:(1) アセンブルリスト (生成されたコード) にはコンパイル時にアセンブラが用いた記号表の情報があまり反映されないので,ポインタ渡しと参照渡しの違いを見るにはコンパイル時のエラーになり方を見るのがお勧め --- アセンブラから見れば参照変数もポインタ(記号表では他の変数と大差なし).
(2) 昔のプログラミング教育でよく使われたPascalでは,名前呼びの引数に予約語「var」を付けます --- Borland 社のDelphiにも引き継がれていたのですが・・・.
(3) Cに融通性が溢れているのは当初のユーザーがベル研究所の優秀な研究員だったから余計なお節介はをしなくても使いこなせたからでしょう --- BSTJ は学会誌以上の権威がありました.

コメント