Javaデータ構造のまとめ

4661 ワード
Java常用データ構造
いくつかのソースコードを通して、さまざまなデータ構造の使用方法を示します.1.シーケンステーブルの概念と構造:順序表は物理アドレスの連続的なストレージユニットでデータ要素を順次記憶する線形構造で、一般的には配列記憶を採用します.配列の上でデータの添削を完成します.
public interface ISequence
{    // pos    val  
boolean add(int pos,Object data);   
//     key     key   ，    null;   
int search(Object key);  
//         key        (   search    )  
boolean contains(Object key);  
//  pos       
Object getPos(int pos); 
//           key   
Object remove(Object key);  
//            
int size();   
//      
void display();  
//              
void clear();
}
2.チェーン概念:チェーンテーブルは物理的な記憶構造上の非連続的、非順序的な記憶構造であり、データ要素の論理的順序はチェーンテーブルの参照リンク順によって実現される.
チェーンの種類:
  • ヘッドレス一方向非循環リンク表:構造が簡単で、データを単独で保存することは一般的ではない.実際には、ハッシュバケット、図の隣接テーブルなどの他のデータ構造としてのサブ構造が多い.
  • 率先して循環するシングルチェーン表:構造は比較的無頭一方向の非循環チェーンテーブルが簡単である.
  • 率先しない双方向循環リンク表:Javaの集合フレームワークライブラリのLinkkedList最下層で実現することは、率先しない双方向循環チェーン
    • である.
    // 1、           
public interface ILinked
{    //    
void addFirst(int data);   
//      
void addLast(int data);   
//      ,        0    
boolean addindex(int index,int data);   
//         key         
boolean contains(int key);
//           key   
    int remove(int key);  
        //      key    
        void removeAllKey(int key);  
        //            
        int getLength();  
        void display();    
        void clear(); 
        }
//2、         
public interface ICLinked
{    //      
void addFirst(int data);  
//      
void addLast(int data); 
//      ,        0     
boolean addindex(int index,int data);   
//         key           
boolean contains(int key);   
//           key      
int remove(int key);    
//      key     
void removeAllKey(int key); 
//          
int getLength(); 
void display();   
void clear();
}
/ 3、         
public interface IDoubleLinked 
{    //     
void addFirst(int data);   
//      
void addLast(int data);
//      ,        0      
boolean addindex(int index,int data);  
//         key          
boolean contains(int key);   
//           key     
int remove(int key);   
//      key      
void removeAllKey(int key); 
//           
int getLength();  
void display();   
void clear(); 
}
    3.スタックの概念及び構造スタック:特殊な線形表であり、固定された端のみに要素の挿入と削除操作を行うことができる.データの挿入と削除を行う端をスタックトップといい、他端をスタック底といいます.スタック中のデータ要素は、後進先のLIFO(Last In First Out)の原則に従う.スタック:スタックの挿入操作は進スタック/圧スタック/入スタックといい、入力データはスタックの一番上にあります.スタック:スタックの削除操作をスタックといいます.出荷データもスタックトップにあります.スタックの実装は、一般的に、配列またはチェーンテーブルを使用して実装され、相対的に配列の構造がより優れている.行列が最後にデータを挿入するのは比較的に小さいからです.
    interface MyStack
{    //            
boolean empty();        
//       ，      
int peek();    
//       ，        
int pop();        
//   item      
void push(int item);   
//           
int size(); 
}
    4.キューキューの概念及び構造キュー:端だけにデータを挿入する操作を許可し、他端でデータを削除する操作を行う特殊なリニアテーブルで、キューは先のFIFO(First In First Out)を持ってキューに入る:挿入操作を行う端をチームの後出キューといいます.削除操作を行う端をチームヘッドといいます.行列の実現行列は、配列とチェーンテーブルの構造を使用して、より優れた構造を実現することもできます.配列の構造を使用すると、行列がアレイヘッドにデータを出して、効率が低いからです.
    interface IMyQueue
{    //             
boolean empty();    
//       ，       
int peek();    
//       ，       
int poll();  
//   item       
void add(int item);    
//         
int size(); 
}
    5:二叉樹の一本の二叉樹は結点の一つの有限集合であり、この集合は或いは空であり、或いは一本のノードに二本の左子樹と右子樹と呼ばれる二叉樹からなる.1)二叉樹の特徴:
  • 各結点には最大2ケケの木があります.つまり、二叉の木は存在度が2より大きい結点がありません.
  • 二叉樹の子木には左右の区別があり、その子樹の順序は逆にしてはいけない.
    • 2)特別な二叉樹:
  • は二叉の木をいっぱいにします.一つの二叉の木で、各層の接合点数が最大値に達したら、この二叉の木は満二叉の木です.つまり、二叉の木の層数がKで、総結点数が(2^k)-1であれば、二叉の木がいっぱいです.
  • 完全に二叉の木:完全に二叉の木は効率の高いデータ構造で、完全に二叉の木は満二叉の木から引き出されたのです.深さがKの場合、n個の結点を有する二叉樹があり、その各結点がKの深さを持つ満二叉樹の中の番号が1からnの結点にそれぞれ対応するときのみ、完全二叉樹と称される.注意したいのは、満二叉樹という特殊な完全二叉樹です.
    • 3)二叉樹の記憶構造の二叉樹は、一般的に、二種類の構造記憶を使用することができ、一つの順序構造、一つのチェーン構造の1.二叉樹の順序記憶は物理的には1つの配列であり、論理的には1つの二叉樹である.
  • 連鎖式記憶:二叉樹のチェーン式記憶構造とは、二叉樹の一株をチェーンで表し、すなわち要素の論理関係をチェーンで表しています.通常の方法は、チェーンテーブルの各結点が3つのドメインからなり、データドメインと左右のポインタ領域であり、左右のポインタはそれぞれ、その結点の左の子供と右の子供がいるリンクポイントの記憶アドレスを与えるために用いられる.
    class Node {  
int value;    //            
Node leftChild;    //         
Node rightChild;   //        
}
    (1)二叉樹の順序格納構造:普通は完全な二叉樹である.ヒープの概念を導入する:(配列のストレージ構造を利用して、完全に二叉のツリーを保存する)ヒープの概念と構造がある場合は、キーコードのセットK={k 0,k 1,k 2,...,kn-1}は、そのすべての要素を完全な二叉のツリーの順序で1次元配列に格納し、Ki<=K 2 i+1、Ki+2=>2 K+2.i=0,1,2…は、小さな山(または山)という.ルートノードの最大のヒープを最大ヒープまたは大ルートヒープと呼び、ルートノードの最小のヒープを最小ヒープまたは小ルートヒープと呼ぶ.ヒープの性質:ヒープの中のあるノードの値は常に親ノードの値より大きくないか、またはそれより小さくないか.山はいつも一本で、完全に二叉の木です.
    • (2)二叉樹のチェーン式記憶構造.
    //     
int getSize(Node root);

//       
int getLeafSize(Node root);

//   k      
int getKLevelSize(Node root, int k);

//   ，         、   、        value，    ，
    ，    null
Node find(Node root, int value);
    Tclデータ構造の配列