技術共有

[Java データ構造] 最初の線形テーブルの 1 つ: シーケンシャル テーブル

2024-07-12

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Javaを使用したシーケンステーブルの簡単な実装

シーケンス テーブルは、連続した物理アドレスを持つストレージ ユニットを使用してデータ要素を順番に格納する線形構造です。一般に、配列ストレージが使用されます。アレイ上のデータの追加、削除、確認、変更を完了します。

線形テーブルには通常、次のメソッドが含まれます。

パブリッククラスMyArrayList {
プライベートint[]配列;
プライベート int サイズ;
   // デフォルトの構築方法では、デフォルトでスペースが割り当てられます。
シーケンスリスト(){}
    // シーケンス テーブルの基礎となる容量を指定された容量に設定します
SeqList(int 初期容量){ }

   // 新しい要素を追加します。デフォルトでは、配列の最後に追加されます。
パブリック void add(int データ) { }
    // pos 位置に要素を追加
パブリック void add(int pos, int data) { }
   // 要素が含まれているかどうかを判断します
パブリックブール値 contains(int toFind) { true を返す; }
    // 要素に対応する位置を検索します
パブリック int indexOf(int toFind) { 戻り値 -1; }
    // pos 位置の要素を取得します
パブリック int get(int pos) { 戻り値 -1; }
   // pos 位置の要素を value に設定します
パブリック void set(int 位置、int 値) { }
    //最初に出現したキーワードキーを削除します
パブリック void 削除 (int toRemove) { }
   // シーケンステーブルの長さを取得する
パブリック int サイズ() { 0 を返す; }
    // シーケンステーブルをクリアする
パブリックボイドクリア（）{}
   
   // シーケンステーブルを印刷する
パブリック void display() { }
}

次に、上記の方法に従って int 型のシーケンス テーブルを実装します。

  1. import java.util.Arrays;
  2. public class MyArrayList {
  3.     private int[] elem;
  4.     private int usedSize;
  5.     private static final int DEFAULT_SIZE = 10;
  6.     public MyArrayList(){
  7.         elem = new int[DEFAULT_SIZE];
  8.     }
  9.     public MyArrayList(int initCapacity){
  10.         elem = new int[initCapacity];
  11.     }
  12.  
  13.     private boolean checkCapacity(){
  14.         if(this.usedSize == elem.length){
  15.             return true;
  16.         }
  17.         return false;
  18.     }
  19.  
  20.     public void display(){
  21.         for (int i = 0; i < this.usedSize; i++) {
  22.             System.out.print(this.elem[i] + " ");
  23.         }
  24.     }
  25.     public void add(int data){
  26.         if(checkCapacity()){
  27.             this.elem = Arrays.copyOf(this.elem,2*elem.length);
  28.         }
  29.         this.elem[this.usedSize] = data;
  30.         this.usedSize++;
  31.         return;
  32.     }
  33.     public void add(int pos,int data){
  34.         if(pos > this.usedSize || pos < 0){
  35.             throw new PosOutOfBoundsException("插入位置错误！");
  36.         }
  37.         if(checkCapacity()){
  38.             this.elem = Arrays.copyOf(this.elem,2*elem.length);
  39.         }
  40.         for (int i = this.usedSize - 1; i >=pos ; i--) {
  41.             elem[i+1] = elem[i];
  42.         }
  43.         this.elem[pos] = data;
  44.         this.usedSize++;
  45.         return;
  46.     }
  47.  
  48.     public boolean contains(int data){
  49.         for (int i = 0; i < this.usedSize; i++) {
  50.             if(this.elem[i] == data){
  51.                 return true;
  52.             }
  53.         }
  54.         return false;
  55.     }
  56.  
  57.     public int indexof(int data){
  58.         for (int i = 0; i < this.usedSize; i++) {
  59.             if(this.elem[i] == data){
  60.                 return i;
  61.             }
  62.         }
  63.         return -1;
  64.     }
  65.     public int get(int pos){
  66.         if(pos >= this.usedSize || pos < 0){
  67.             throw new PosOutOfBoundsException("输入的位置错误！");
  68.         }
  69.         return this.elem[pos];
  70.     }
  71.     public void set(int pos,int data){
  72.         if(pos >= this.usedSize || pos < 0){
  73.             throw new PosOutOfBoundsException("输入的位置错误！");
  74.         }
  75.         this.elem[pos] = data;
  76.     }
  77.     public int size(){
  78.         return this.usedSize;
  79.     }
  80.     public void remove(int data){
  81.         if(this.contains(data)){
  82.             int pos = this.indexof(data);
  83.             for (int i = pos; i < this.usedSize - 1; i++) {
  84.                 this.elem[pos] = this.elem[pos+1];
  85.             }
  86.             this.usedSize--;
  87.         }else{
  88.             throw new PosOutOfBoundsException("没有该元素");
  89.         }
  90.     }
  91.     public void clear(){
  92.         this.usedSize = 0;
  93.         return;
  94.     }
  95. }

ArrayList の概要

コレクション フレームワークでは、ArrayList は List インターフェイスを実装する通常のクラスです。具体的なフレームワーク図は次のとおりです。

  • ArrayList は汎用的な方法で実装されているため、使用前にインスタンス化する必要があります。
  • ArrayList は RandomAccess インターフェイスを実装し、ArrayList がランダム アクセスをサポートしていることを示します。
  • ArrayList は Cloneable インターフェイスを実装し、ArrayList をクローンできることを示します
  • ArrayList は Serializable インターフェイスを実装し、ArrayList がシリアル化をサポートしていることを示します
  • Vector とは異なり、ArrayList はスレッドセーフではなく、マルチスレッドで使用できます。Vector または
  • コピーオンライト配列リスト
  • ArrayList の最下層は連続空間であり、動的に展開できる動的型の配列リストです。

ArrayListの使い方

ArrayList コンストラクター

ArrayList のコンストラクター メソッド:

ArrayList(); //パラメータ構築なし

ArrayList(コレクション<? extends E> c); //他のコレクションを使用して ArrayList を構築します

ArrayList(int initialCapacity) //シーケンステーブルの初期容量を指定

コード例:

  1. public class Test {
  2.     public static void main(String[] args) {
  3.         List<Integer> list1 = new ArrayList<>();//无参构造
  4.         List<Integer> list2 = new ArrayList<>(10);//指定容量
  5.         list2.add(1);
  6.         list2.add(2);
  7.         list2.add(3);
  8.         List<Integer> list3 = new ArrayList<>(list2);//利用其他 Collection 构建 ArrayList
  9.     }
  10. }

ArrayList に対する一般的な操作

テールプラグ

  1. public class Test {
  2.     public static void main(String[] args) {
  3.         List<Integer> list = new ArrayList<>();//无参构造
  4.         list.add(1);
  5.         list.add(2);
  6.         list.add(3);
  7.         System.out.println(list);
  8.     }
  9. }

指定した位置に要素を挿入

  1. public class Test {
  2.     public static void main(String[] args) {
  3.         List<Integer> list = new ArrayList<>();
  4.         list.add(1);
  5.         list.add(2);
  6.         list.add(3);
  7.         list.add(1,4);
  8.         System.out.println(list);
  9.     }
  10. }

別のシーケンス リストからの要素の挿入を終了する

  1. public class Test {
  2.     public static void main(String[] args) {
  3.         List<Integer>  list1 = new ArrayList<>();
  4.         list1.add(4);
  5.         list1.add(5);
  6.         list1.add(6);
  7.         List<Integer> list = new ArrayList<>();
  8.         list.add(1);
  9.         list.add(2);
  10.         list.add(3);
  11.         list.addAll(list1);
  12.         System.out.println(list);
  13.     }
  14. }

指定した位置の要素を削除します

  1. public class Test {
  2.     public static void main(String[] args) {
  3.         List<Integer> list = new ArrayList<>();
  4.         list.add(1);
  5.         list.add(2);
  6.         list.add(3);
  7.         list.remove(1);
  8.         System.out.println(list);
  9.     }
  10. }

指定したデータを削除する

  1. public class Test {
  2.     public static void main(String[] args) {
  3.         List<Integer> list = new ArrayList<>();
  4.         list.add(1);
  5.         list.add(2);
  6.         list.add(3);
  7.         list.remove(new Integer(2));
  8.         System.out.println(list);
  9.     }
  10. }

指定した位置の要素を取得する

  1. public class Test {
  2.     public static void main(String[] args) {
  3.         List<Integer> list = new ArrayList<>();
  4.         list.add(1);
  5.         list.add(2);
  6.         list.add(3);
  7.         System.out.println(list.get(1));
  8.     }
  9. }

指定された位置の要素を新しいデータに設定します

  1. public class Test {
  2.     public static void main(String[] args) {
  3.         List<Integer> list = new ArrayList<>();
  4.         list.add(1);
  5.         list.add(2);
  6.         list.add(3);
  7.         list.set(1,4);
  8.         System.out.println(list);
  9.     }
  10. }

シーケンスリストをクリアする

  1. public class Test {
  2.     public static void main(String[] args) {
  3.         List<Integer> list = new ArrayList<>();
  4.         list.add(1);
  5.         list.add(2);
  6.         list.add(3);
  7.         list.clear();
  8.         System.out.println(list);
  9.     }
  10. }

要素がシーケンス リストにあるかどうかを判断する

  1. public class Test {
  2.     public static void main(String[] args) {
  3.         List<Integer> list = new ArrayList<>();
  4.         list.add(1);
  5.         list.add(2);
  6.         list.add(3);
  7.         System.out.println(list.contains(2));
  8.         System.out.println(list.contains(4));
  9.     }
  10. }

最初に指定された要素のインデックスを返します。

  1. public class Test {
  2.     public static void main(String[] args) {
  3.         List<Integer> list = new ArrayList<>();
  4.         list.add(1);
  5.         list.add(2);
  6.         list.add(3);
  7.         list.add(1);
  8.         System.out.println(list.indexOf(1));
  9.     }
  10. }

最後に指定された要素のインデックスを返します。

  1. public class Test {
  2.     public static void main(String[] args) {
  3.         List<Integer> list = new ArrayList<>();
  4.         list.add(1);
  5.         list.add(2);
  6.         list.add(3);
  7.         list.add(1);
  8.         System.out.println(list.lastIndexOf(1));
  9.     }
  10. }

リストの一部をインターセプトする

  1. public class Test {
  2.     public static void main(String[] args) {
  3.         List<Integer> list = new ArrayList<>();
  4.         list.add(1);
  5.         list.add(2);
  6.         list.add(3);
  7.         System.out.println(list.subList(0,2));
  8.     }
  9. }

ArrayList をトラバースする 3 つの方法

ArrayList は、for ループ + 添字、foreach 拡張ループ、イテレータの使用の 3 つの方法で走査できます。

  1. public class Test {
  2.     public static void main(String[] args) {
  3.         List<Integer> list = new ArrayList<>();
  4.         list.add(1);
  5.         list.add(2);
  6.         list.add(3);
  7.         //使用fori遍历
  8.         for (int i = 0; i < list.size(); i++) {
  9.             System.out.print(list.get(i));
  10.         }
  11.         System.out.println();
  12.         //使用foreach遍历
  13.         for(Integer integer:list){
  14.             System.out.print(integer);
  15.         }
  16.         System.out.println();
  17.         //使用迭代器遍历
  18.         Iterator<Integer> it = list.listIterator();
  19.         while(it.hasNext()){
  20.             System.out.print(it.next());
  21.         }
  22.     }
  23. }

操作結果:

ArrayList のシナリオ使用法

シャッフルアルゴリズム

トランプのデッキをランダムにシャッフルし、各 5 枚のカードを 3 人に配ります。

アルゴリズムの元のコードの場所:

シャッフルカード · 常に淡水魚/Java の古典的な例 - コード クラウド - オープンソース中国 (gitee.com)

ヤン・フイ・トライアングル

トピックの説明:

コード：

  1. public class Test {
  2.     public static List<List<Integer>> generate(int numRows) {
  3.         List<List<Integer>> list = new LinkedList<>();
  4.         for (int i = 0; i < numRows; i++) {
  5.             List<Integer> row = new LinkedList<>();
  6.             for (int j = 0; j < i + 1; j++) {
  7.                 if (j == 0 || i == j) {
  8.                     row.add(1);
  9.                 } else {
  10.                     row.add(list.get(i - 1).get(j - 1) + list.get(i - 1).get(j));
  11.                 }
  12.             }
  13.             list.add(row);
  14.         }
  15.         return list;
  16.     }
  17.  
  18.     public static void main(String[] args) {
  19.         Scanner scanner = new Scanner(System.in);
  20.         int numRows = scanner.nextInt();
  21.         List<List<Integer>> list = generate(numRows);
  22.         for (int i = 0; i < numRows; i++) {
  23.             for (int j = 0; j < i + 1; j++) {
  24.                 System.out.print(list.get(i).get(j) + " ");
  25.             }
  26.             System.out.println();
  27.         }
  28.     }
  29. }

走行結果グラフ：

個人プロフィール

彼は 30 年以上テクノロジーの研究に専念しており、java、linux、javascript、php、css などのさまざまな言語に堪能であり、オープンソース分野で多くの貢献を行っています。将来の参考のために技術開発におけるいくつかの問題を共有する開発者ドキュメント ステーション。

プライベートな連絡先の最初の情報

送料