g++による演習 (5)

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;
}