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