C ++
 Computer >> コンピューター >  >> プログラミング >> C ++

スプレーツリーを実装するC++プログラム


これは、スプレーツリーを実装するためのC++プログラムです。

クラスの説明:

Begin
   class SplayTree has the functions:
      Create a function Splay() to implement top-down splay tree.
      Here head.rch points to the Left tree and head.lch points to the right tree.
      Create a link to Right tree.
      Create a link to Left tree.
      Assemble left, middle and right tree.
   Create a function Insert() to insert nodes into the tree.
      If root->k >= all keys will be the root→lch
      Else if
      root->k <=all keys will be the root→rch
      Else
      Return root.
End

クラスの説明と擬似コード:

Begin
   Create a structure s to declare variable k and left child pointer lch and right child pointer rch.
   Create a class SplayTree :
      Create a function RR_Rotate to rotate to the right.
      Create a function LL_Rotate to rotate to the left.
      Create a function Splay to implement top-down splay tree.
      Here head.rch points to the Left tree and head.lch
      points to the right tree.
      Create a link to Right tree.
      Create a link to Left tree.
      Assemble left, middle and right tree.
   Create a function New_Node() to create nodes in the tree.
   Create a function Insert() to insert nodes into the tree.
      If root→k >= all keys will be the root→lch
      Else if
      root->k >=all keys will be the root→rch
      Else
      Return root.
   Create a function Delete() to delete nodes from the tree.
   Create a function Search() to search the nodes in the tree.
   Create a function InOrder() for InOrder traversal of the tree.
   Create a function main(), and perform selective function calls as per choice.
End

サンプルコード

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
struct s//node declaration
{
   int k;  
   s* lch;
   s* rch;
};
class SplayTree
{
   public:
   s* RR_Rotate(s* k2)
   {
      s* k1 = k2->lch;
      k2->lch = k1->rch;
      k1->rch = k2;
      return k1;
   }
   s* LL_Rotate(s* k2)
   {
      s* k1 = k2->rch;
      k2->rch = k1->lch;
      k1->lch = k2;
      return k1;
   }
   s* Splay(int key, s* root)
   {
      if (!root)
      return NULL;
      s header;
      header.lch= header.rch = NULL;
      s* LeftTreeMax = &header;
      s* RightTreeMin = &header;
      while (1)
      {
         if (key < root->k)
         {
            if (!root->lch)
            break;
            if (key< root->lch->k)
            {
               root = RR_Rotate(root);
               if (!root->lch)
               break;
            }
            RightTreeMin->lch= root;
            RightTreeMin = RightTreeMin->lch;
            root = root->lch;
            RightTreeMin->lch = NULL;
         }
         else if (key> root->k)
         {
            if (!root->rch)
            break;
            if (key > root->rch->k)
            {
               root = LL_Rotate(root);
               if (!root->rch)
               break;
            }
            LeftTreeMax->rch= root;
            LeftTreeMax = LeftTreeMax->rch;
            root = root->rch;
            LeftTreeMax->rch = NULL;
         }
         else
         break;
      }
      LeftTreeMax→rch = root->lch;
      RightTreeMin→lch = root->rch;
      root->lch = header.rch;
      root->rch = header.lch;
      return root;
   }
   s* New_Node(int key)
   {
      s* p_node = new s;
      if (!p_node)
      {
         fprintf(stderr, "Out of memory!\n");
         exit(1);
      }
      p_node->k = key;
      p_node->lch = p_node->rch = NULL;
      return p_node;
   }
   s* Insert(int key, s* root)
   {
      static s* p_node = NULL;
      if (!p_node)
      p_node = New_Node(key);
      else
      p_node->k = key;
      if (!root)
      {
         root = p_node;
         p_node = NULL;
         return root;
      }
      root = Splay(key, root);
      if (key < root->k)
      {
         p_node->lch= root->lch;
         p_node->rch = root;
         root->lch = NULL;
         root = p_node;
      }
      else if (key > root->k)
      {
         p_node->rch = root->rch;
         p_node->lch = root;
         root->rch = NULL;
         root = p_node;
      }
      else
      return root;
      p_node = NULL;
      return root;
   }
   s* Delete(int key, s* root)//delete node
   {
      s* temp;
      if (!root)//if tree is empty
      return NULL;
      root = Splay(key, root);
      if (key != root->k)//if tree has one item
      return root;
      else
      {
         if (!root->lch)
         {
            temp = root;
            root = root->rch;
         }
         else
         {
            temp = root;
            root = Splay(key, root->lch);
            root->rch = temp->rch;
         }
         free(temp);
         return root;
      }
   }
   s* Search(int key, s* root)//seraching
   {
      return Splay(key, root);
   }
   void InOrder(s* root)//inorder traversal
   {
      if (root)
      {
         InOrder(root->lch);
         cout<< "key: " <<root->k;
         if(root->lch)
         cout<< " | left child: "<< root->lch->k;
         if(root->rch)
         cout << " | right child: " << root->rch->k;
         cout<< "\n";
         InOrder(root->rch);
      }
   }
};
int main()
{
   SplayTree st;
   s *root;
   root = NULL;
   st.InOrder(root);
   int i, c;
   while(1)
   {
      cout<<"1. Insert "<<endl;
      cout<<"2. Delete"<<endl;
      cout<<"3. Search"<<endl;
      cout<<"4. Exit"<<endl;
      cout<<"Enter your choice: ";
      cin>>c;
      switch©//perform switch operation
      {
         case 1:
            cout<<"Enter value to be inserted: ";
            cin>>i;
            root = st.Insert(i, root);
            cout<<"\nAfter Insert: "<<i<<endl;
            st.InOrder(root);
            break;
         case 2:
            cout<<"Enter value to be deleted: ";
            cin>>i;
            root = st.Delete(i, root);
            cout<<"\nAfter Delete: "<<i<<endl;
            st.InOrder(root);
            break;
         case 3:
            cout<<"Enter value to be searched: ";
            cin>>i;
            root = st.Search(i, root);
            cout<<"\nAfter Search "<<i<<endl;
            st.InOrder(root);
            break;
         case 4:
            exit(1);
         default:
            cout<<"\nInvalid type! \n";
      }
   }
   cout<<"\n";
   return 0;
}

出力

1. Insert
2. Delete
3. Search
4. Exit
Enter your choice: 1
Enter value to be inserted: 7
After Insert: 7
key: 7
1. Insert
2. Delete
3. Search
4. Exit
Enter your choice: 1
Enter value to be inserted: 6
After Insert: 6
key: 6 | right child: 7
key: 7
1. Insert
2. Delete
3. Search
4. Exit
Enter your choice: 1
Enter value to be inserted: 4
After Insert: 4
key: 4 | right child: 6
key: 6 | right child: 7
key: 7
1. Insert
2. Delete
3. Search
4. Exit
Enter your choice: 1
Enter value to be inserted: 5
After Insert: 5
key: 4
key: 5 | left child: 4 | right child: 6
key: 6 | right child: 7
key: 7
1. Insert
2. Delete
3. Search
4. Exit
Enter your choice: 1
Enter value to be inserted: 3
After Insert: 3
key: 3 | right child: 4
key: 4 | right child: 5
key: 5 | right child: 6
key: 6 | right child: 7
key: 7
1. Insert
2. Delete
3. Search
4. Exit
Enter your choice: 1
Enter value to be inserted: 2
After Insert: 2
key: 2 | right child: 3
key: 3 | right child: 4
key: 4 | right child: 5
key: 5 | right child: 6
key: 6 | right child: 7
key: 7
1. Insert
2. Delete
3. Search
4. Exit
Enter your choice: 3
Enter value to be searched: 2
After Search 2
key: 2 | right child: 3
key: 3 | right child: 4
key: 4 | right child: 5
key: 5 | right child: 6
key: 6 | right child: 7
key: 7
1. Insert
2. Delete
3. Search
4. Exit
Enter your choice: 2
Enter value to be deleted: 3
After Delete: 3
key: 2 | right child: 4
key: 4 | right child: 5
key: 5 | right child: 6
key: 6 | right child: 7
key: 7
1. Insert
2. Delete
3. Search
4. Exit
Enter your choice: 4

  1. シーザー暗号を実装するC++プログラム

    これは、平文の各文字が別の文字に置き換えられて暗号文を形成するモノアルファベット暗号です。これは、換字式暗号方式の最も単純な形式です。 この暗号システムは、一般にシフト暗号と呼ばれます。コンセプトは、各アルファベットを、0から25の間の固定数で「シフト」された別のアルファベットに置き換えることです。 このタイプのスキームでは、送信者と受信者の両方がアルファベットをシフトするための「秘密のシフト番号」に同意します。この0から25までの数字が暗号化の鍵になります。 「シーザー暗号」という名前は、「3シフト」が使用されている場合のシフト暗号を表すために使用されることがあります。 プロセス

  2. AVLツリーを実装するためのC++プログラム

    AVLツリーは自己平衡二分探索木であり、左右のサブツリーの高さの差がすべてのノードで複数になることはありません。 ツリーの回転は、AVLツリーの要素の順序を妨げることなく構造を変更する操作です。ツリー内で1つのノードを上に移動し、1つのノードを下に移動します。これは、ツリーの形状を変更したり、小さいサブツリーを下に移動したり、大きいサブツリーを上に移動したりして高さを低くしたりするために使用され、多くのツリー操作のパフォーマンスが向上します。回転の方向は、木のノードが移動する側に依存しますが、他の人は、どの子がルートの場所をとるかに依存すると言います。これは、AVLツリーを実装するためのC+