C++共通データ構造

一般的なデータ構造:
1配列
配列は集約データ型です.memset()を使用できます.sort(a,a+n,cmp); char[]の場合はstrlen()も可能です.長さを得る.
また、c++言語スタイルのint*a=new int[12];削除時にdelete[]a;2 D配列の場合は、次のようなスタイルになります.

int**a = new int *[12];
   for(int i=0;i<12;i++)
{
   a[i]= new int[12];
}

同時にdeleteは各deleteに対して以下のフォーマットdelete[]a[i];
c言語のスタイルを使用する場合、フォーマットは次のとおりです.

int *a = (int *)malloc(sizeof(a)*10);
free(a);

このような関数は解放され,2次元配列も同様である.
2スタック
スタックは特殊な構造です.スタックの動作は主にシーケンスとチェーンによって実現される.スタックの基本操作コードは以下の通りである.
実装可能なデータ型はあります.
応用するテーマは主にあります:スタックの出スタックの順序など
3キュー
キューの基本的な操作は次のとおりです.
FIFO queue:
Emplaceとswapはc++11でサポートされています.

// queue::emplace
#include        // std::cin, std::cout
#include           // std::queue
#include          // std::string, std::getline(string)
 
int main ()
{
  std::queue<:string>myqueue;
 
 myqueue.emplace ("Firstsentence");
 myqueue.emplace ("Secondsentence");
 
 std::cout << "myqueuecontains:
";
  while (!myqueue.empty())
  {
   std::cout << myqueue.front() << '
';
   myqueue.pop();
  }
 
  return 0;
}

 
  
// queue::emplace
#include        // std::cin, std::cout
#include           // std::queue
#include          // std::string, std::getline(string)
 
int main ()
{
  std::queue<:string> myqueue;
 
  myqueue.emplace ("First sentence");
  myqueue.emplace ("Second sentence");
 
  std::cout << "myqueue contains:
";
  while (!myqueue.empty())
  {
    std::cout << myqueue.front() << '
';
    myqueue.pop();
  }
 
  return 0;
}
  
// queue::emplace
#include        // std::cin, std::cout
#include           // std::queue
#include          // std::string, std::getline(string)
 
int main ()
{
  std::queue<:string> myqueue;
 
  myqueue.emplace ("First sentence");
  myqueue.emplace ("Second sentence");
 
  std::cout << "myqueue contains:
";
  while (!myqueue.empty())
  {
    std::cout << myqueue.front() << '
';
    myqueue.pop();
  }
 
  return 0;
}
  
そして優先キューです.前のブログでも話しましたが、priority_queue , cmp> 
あるいは自分でリロードしたかstd::lessというタイプです.
Greaterはクラスです.
    ：
  
 
  
   
   
template  struct greater {
  bool operator() (const T& x, const T& y) const {return x>y;}
  typedef T first_argument_type;
  typedef T second_argument_type;
  typedef bool result_type;
};

template  struct greater {
  bool operator() (const T& x, const T& y) const {return x>y;}
  typedef T first_argument_type;
  typedef T second_argument_type;
  typedef bool result_type;
};
  
  
 
  
 
   
 
  
 
  
   
4   
  
   
              。      ，            。           。
  
   
 
  
   
5  
  
   
        。
  
   
    ，     。    ，   ，           。    path   ，     。       ，    (dfs)，  (bfs)
  
  
         ，        。
 
  
    ，3   (         )，       
 
  
        ：
 
   
   
typedef int T;
struct BinaryNode{
  Telement;
 BinaryNode *left, *right;
 BinaryNode(T d, BinaryNode *l=NULL, BinaryNode* r=NULL):element(d),left(l), right(r) {};
};
  
  
 
   
typedef int T;
struct BinaryNode{
  Telement;
 BinaryNode *left, *right;
 BinaryNode(T d, BinaryNode *l=NULL, BinaryNode* r=NULL):element(d),left(l), right(r) {};
};
  
  
  ：    
 
  
 
   
Traverse the tree p (which points to theroot)：
a)       If p!= NULL, push it into stack;
b)       Traveser p->left, that is p = p->left;
c)       If p==NULL, pop out the root, visit the root, and then traverse theright subtree root->right, that is
       p = root->right;
Repeat the process until the stack isempty。
 
void nonRecursiveInorder(BinaryNode *root,void(*visit)(T &x))
 stack s；
  p=root；//p points the current root of traversal
  while(p|| !s.empty())
       if(p)
      {// push root into stack and traverse the left subtree
raverse the left subtree
           s.push(p)；
           p=p->left；
       }
      else{  
      //no left subtree, pop out the root, visit the root
      //and traverse the right subtree             
              p = s.top()；
            visit(p->data)) ；
              p=p->right；
      }
   }
}

           s.push(p)；
           p=p->left；
       }
      else{  
      //no left subtree, pop out the root, visit the root
      //and traverse the right subtree             
              p = s.top()；
            visit(p->data)) ；
              p=p->right；
      }
   }
}
  
  
 
  
 
  
      ：          。
 
  
  BST 
 
   
  
      ；
 
   
  
 
 
  
AVL     ，     。       。
 
  
 
 
  
6： 
 
  
            。           。        ，         ，         。
 
  
       ：    (   ，      ，     )    。
 
  
          ：http:soj.me/1509
 
  
      
 
  
 
   
  
Bfs    
 
  
Dfs           
 
   
  
       dijkstra  ，      
 
   
   
Dijkstra(G, s):
Input: s is thesource
Output: mark everyvertex with the shortest distance froms.
    for every vertex v {
         set v (F, weight(s,v))
    }
    set s(T, 0);
   while ( there is a vertex with (F, _)) {
        find the vertex v with thesmallest distvamong (F, dist)
        set v(T, distv)
        for every w(F, dist) adjacent tov{
              if(distv + weight(v,w) 
  
  
 
  
 
  
       MST      prim  krusal
 
  
DFS  ：
 
  
 
 
   
 
  

 
  
7： 
 
  
            。        ，                ，      ，         ，            ，         。
 
   
   
#include     // std::cout
#include    // std::make_heap,std::pop_heap, std::push_heap, std::sort_heap
#include       // std::vector
 
int main () {
  int myints[] = {10,20,30,5,15};
  std::vector v(myints,myints+5);// vector       
 
  std::make_heap (v.begin(),v.end());
  std::cout << "initial maxheap   : " << v.front()<< '
';
 
  std::pop_heap (v.begin(),v.end());
     v.pop_back();
  std::cout << "max heap after pop :" << v.front() << '
';
 
     v.push_back(99);
  std::push_heap (v.begin(),v.end());
  std::cout << "max heap after push:" << v.front() << '
';
 
  std::sort_heap (v.begin(),v.end());
 
  std::cout << "final sorted range:";
  for (unsigned i=0; i
  
  

 
   
  
     vectorv   heap  ，     make_heap(); pop_heap(); v.push(); push_heap(), sort_heap(v.begin(),v.end());  v        。
 
  
8:            。