実験二伸張木アルゴリズムの設計と実現
32098 ワード
一、実験名称:伸展樹アルゴリズムの設計と実現
二、実験目的:
1.伸張木のデータ構造を把握する.
2.ストレッチアルゴリズムの実装を把握する.
三、実験内容
以下の手順を完備し、質問に答える.
補足プログラム:
プログラムの問題:回答:Insert関数の2つのパラメータがそれぞれ表す意味は何ですか. は、伸張ツリー挿入アルゴリズムの基本フローチャートを描くか、または挿入アルゴリズム全体の実装過程を自然言語で記述する. これに数字を入力すると、75、89、72、42、18、25、99、90、17、33となります.最終的な画像は何ですか.ノードの例図を描いてください. 入力された数字は、25、99、90、17、75、89、72、42、18です.最終的な画像は何ですか. (オプション)ソースプログラムに基づいてアクセス関数access(Tx)を記述し、xがツリーに存在することを実装すると、そのポインタを指し、そうでなければ空のポインタを返す.成功するかどうかにかかわらず、ストレッチが行われ、成功するとノードはツリーのルートノードであり、成功しないと最後に検索されたノードはルートノードです.質問に答えます.実現思想:Insert関数を書き換える.問題1.4つの問題に対して、18、42、72、90、42、75、90、72、42、18、72の順にアクセスした後、このツリーの画像は何であるか.
四、実験のまとめと心得
二、実験目的:
1.伸張木のデータ構造を把握する.
2.ストレッチアルゴリズムの実装を把握する.
三、実験内容
以下の手順を完備し、質問に答える.
1 #include <iostream.h>
2 enum ResultCode{Underflow, Overflow, Success, Duplicate, Fail, NotPresent};
3 template<class T>
4 struct BTNode
5 {//
6 BTNode(const T& x){ element=x; lChild=rChild=NULL; }
7 T element;
8 BTNode* lChild,*rChild;
9 };
10 template<class T>
11 class SPTree
12 {//
13 public:
14 SPTree(){root=NULL;}
15 ResultCode Insert(T x);
16 void printTree(){cout<<" ："<<endl; printTree(root);};
17 void printTree( BTNode<T>* &p){
18 if(p == NULL) return;
19 if(p->lChild != NULL){
20 cout<<" "<<p->element<<" "<<p->lChild->element<<endl;
21 printTree(p->lChild);
22 }
23 if(p->rChild != NULL){
24 cout<<" "<<p->element<<" "<<p->rChild->element<<endl;
25 printTree(p->rChild);
26 }
27 };
28 void printTree(int level){cout<<" ："; printTree(root, level); cout<<endl;};
29 void printTree( BTNode<T>* &p, int level){
30 if(p == NULL) return;
31 if(p->lChild != NULL){
32 printTree(p->lChild, level+1);
33 }
34 cout<<endl;
35 for(int i = 0; i<level; i++) cout<<" ";
36 cout<<p->element;
37 if(p->rChild != NULL){
38 printTree(p->rChild, level+1);
39 }
40 };
41 protected:
42 BTNode<T>* root;
43 private:
44 ResultCode Insert(BTNode<T>* &p, T x);
45 void LRot(BTNode<T>* &p);
46 void RRot(BTNode<T>* &p);
47 };
48
49 template <class T>
50 void SPTree<T>::LRot(BTNode<T>*& p)
51 { //
52
53 }
54 template <class T>
55 void SPTree<T>::RRot(BTNode<T>*& p)
56 { //
57
58 }
59
60 template <class T>
61 ResultCode SPTree<T>::Insert(T x)
62 {
63 return Insert(root, x);
64 }
65 template <class T>
66 ResultCode SPTree<T>::Insert(BTNode<T>* &p, T x)
67 {
68
69 }
70
71 void main(){
72 SPTree<int> tree;
73 int ele[30] = {75,89,72,42,18,25,99,90,17,33};
74 int n = 10;
75 for(int i = 0; i < n; i++) tree.Insert(ele[i]);
76 cout<<"--- ---"<<endl<<endl;
77 cout<<" ：";
78 for(int j = 0; j < n; j++) cout<<ele[j]<<",";
79 tree.printTree();
80 tree.printTree(0);
81 }補足プログラム:
1 #include <iostream.h>
2 enum ResultCode{Underflow, Overflow, Success, Duplicate, Fail, NotPresent};
3 template<class T>
4 struct BTNode
5 {//
6 BTNode(const T& x){ element=x; lChild=rChild=NULL; }
7 T element;
8 BTNode* lChild,*rChild;
9 };
10 template<class T>
11 class SPTree
12 {//
13 public:
14 SPTree(){root=NULL;}
15 ResultCode Insert(T x);
16 void printTree(){cout<<" ："<<endl; printTree(root);};
17 void printTree( BTNode<T>* &p){
18 if(p == NULL) return;
19 if(p->lChild != NULL){
20 cout<<" "<<p->element<<" "<<p->lChild->element<<endl;
21 printTree(p->lChild);
22 }
23 if(p->rChild != NULL){
24 cout<<" "<<p->element<<" "<<p->rChild->element<<endl;
25 printTree(p->rChild);
26 }
27 };
28 void printTree(int level){cout<<" ："; printTree(root, level); cout<<endl;};
29 void printTree( BTNode<T>* &p, int level){
30 if(p == NULL) return;
31 if(p->lChild != NULL){
32 printTree(p->lChild, level+1);
33 }
34 cout<<endl;
35 for(int i = 0; i<level; i++) cout<<" ";
36 cout<<p->element;
37 if(p->rChild != NULL){
38 printTree(p->rChild, level+1);
39 }
40 };
41 protected:
42 BTNode<T>* root;
43 private:
44 ResultCode Insert(BTNode<T>* &p, T x);
45 void LRot(BTNode<T>* &p);
46 void RRot(BTNode<T>* &p);
47 };
48
49 template <class T>
50 void SPTree<T>::LRot(BTNode<T>*& p)
51 { //
52 BTNode<T>* r=p->rChild;
53 p->rChild=r->lChild;
54 r->lChild=p;p=r;
55
56 }
57 template <class T>
58 void SPTree<T>::RRot(BTNode<T>*& p)
59 { //
60 BTNode<T>* r=p->lChild;
61 p->lChild=r->rChild;
62 r->rChild=p;p=r;
63
64 }
65
66 template <class T>
67 ResultCode SPTree<T>::Insert(T x)
68 {
69 return Insert(root, x);
70 }
71 template <class T>
72 ResultCode SPTree<T>::Insert(BTNode<T>* &p, T x)
73 {
74 //
75 ResultCode result=Success;
76 BTNode<T>* r;
77 if(p==NULL){
78 p=new BTNode<T>(x);return result;
79 }
80 if(x==p->element)
81 {
82 result=Duplicate;return result;
83 }
84 if(x<p->element)
85 {
86 r=p->lChild;
87 if(r==NULL){
88 r=new BTNode<T>(x);r->rChild=p;p=r;
89 return result;
90 }
91 else if(x==r->element){
92 RRot(p);result=Duplicate;return result;
93 }
94 if(x<r->element){
95 result=Insert(r->lChild,x);
96 RRot(p);
97 }
98 else{
99 result=Insert(r->rChild,x);
100 LRot(r);p->lChild=r;
101 }
102 RRot(p);
103 }
104 else{
105 r=p->rChild;
106 if(r==NULL){
107 r=new BTNode<T>(x);r->lChild=p;p=r;
108 return result;
109 }
110 else if(x==r->element)
111 {
112 LRot(p);
113 result=Duplicate;return result;
114 }
115 if(x>r->element){
116 result=Insert(r->rChild,x);LRot(p);
117 }
118 else{
119 result=Insert(r->lChild,x);
120 RRot(r);p->rChild=r;
121 }
122 LRot(p);
123 }
124 return result;
125 }
126
127 int main(){
128 SPTree<int> tree;
129 //int ele[30] = {75,89,72,42,18,25,99,90,17,33};
130 int ele[30] = {25,99,90,17,75,89,72,42,18};
131 int n = 10;
132 for(int i = 0; i < n; i++) tree.Insert(ele[i]);
133 cout<<"--- ---"<<endl<<endl;
134 cout<<" ：";
135 for(int j = 0; j < n; j++) cout<<ele[j]<<",";
136 tree.printTree();
137 tree.printTree(0);
138 }プログラムの問題:
四、実験のまとめと心得