リニアテーブル(配列、チェーンテーブル、キュー、スタック)詳細まとめ

リニア・テーブルは、主に次の内容を含む非常に基礎的で重要なデータ構造です.

配列

チェーンテーブル

キュー

スタック

次に、チェーンテーブルに対して10数種類の一般的な操作を実現した4つのデータ構造を詳細にまとめます.あなたに役に立つことを願っています.
1.配列
配列(Array)は、線形テーブルデータ構造です.同じタイプのデータのセットを格納するために、連続したメモリ領域のセットを使用します.注意点:①.配列は線形テーブルです.②.連続メモリ領域と同じタイプのデータは、2番目の性質のため、配列は「ランダムアクセス」をサポートし、下表のランダムアクセスの時間複雑度はO(1)である.しかし同時に配列から削除され,挿入データには大量のデータ移動作業が必要となる.
非効率の挿入と削除
挿入アクション
配列の長さがnの場合、配列のk番目の位置にデータを挿入する必要があります.k~n番目のビット要素を順番に後ろに移動する必要があります.最良の場合、時間複雑度はO(1)であり、この場合、配列の末尾に要素を挿入することに対応する.最悪の場合の時間複雑度はO(n)であり、このとき配列の先頭に要素を挿入することに対応する.平均時間複雑度はO(n)であり,各位置に元素を挿入する確率が同じであるため(1+2+3+......+n)/n=O(n);しかし、私たちのニーズに応じて、特定のシーンがあります.配列のデータが秩序化されている場合は、挿入時に必ずそうしなければなりません.しかし、配列に格納されているデータに法則がなければ、配列は格納データの集合として扱われるだけで、k番目の要素を配列要素の最後に直接移動し、新しいデータをk番目の位置に直接入れればよい(簡単ではないでしょうか)、挿入要素の複雑さはO(1)である.
アクションの削除
挿入操作と同様に、メモリの連続性を保証するために、削除操作もデータを移動する必要があります.最良の場合、時間複雑度はO(1)であり、この場合、配列の末尾の要素を削除することに対応する.最悪の場合の時間複雑度はO(n)であり,このとき配列の先頭の要素を削除することに対応する.平均時間複雑度はO(n)であり,各位置の要素を削除する確率が同じであるため(1+2+3+......+n)/n=O(n);もちろん、特定の状況では、複雑な削除操作を行う必要はありません.削除する必要があるデータを記録し、削除されたふりをします.配列にデータを格納するスペースがなくなるまで、本格的な削除操作をトリガーします.
これは生活の中のゴミ箱と似ていて、ゴミは消えていません.
「マーク」はごみになり、ゴミ箱がいっぱいになるまでゴミ箱を片付けます.
配列アクセスの限界を警戒
C言語では、アクセス制限されたメモリでない限り、すべてのメモリ領域に自由にアクセスできます.油断すると深刻な結果をもたらす.もちろん、Javaは自動的に検出されます.
2.チェーンテーブル

チェーンテーブル接点表示

シングルチェーンテーブル

を印刷する.

単鎖テーブルインデックスに従ってノード

を挿入する.

単一チェーンテーブルの長さ

を取得する.

印刷シングルチェーンテーブルの長さ

単一チェーンテーブル指定インデックスのノード

を削除

単一チェーンテーブルは要素検索を実現し、ブール値

が存在するかどうかを返す.

単一チェーンテーブル指定インデックスの後続ノード

を削除する.

単鎖表反転

単鎖表反転

を再帰的に行う.

チェーンテーブルにリング

が含むか否かを検出する.

最後からk番目のノード

を削除する.

中間ノード

を求める

秩序チェーンテーブル連結

チェーンテーブル接点表示

public class Node{
    int data;
    Node Next;
}

シングルチェーンテーブルの印刷

public class Method {
    //     
    public static void PrintNode (Node list){
        for(Node x=list;x!=null;x=x.Next)
        System.out.print(x.data+" ");
        System.out.println();
    }

単一チェーンテーブルインデックスに基づいてノードを挿入

    public static Node insert(Node first,int index,Node a){
        Node ret = new Node();
        ret.Next=first;//         
        Node p=ret;
        while((index--)!=0) p=p.Next;
        //         
        a.Next=p.Next;
        p.Next=a;
        //            
        return ret.Next;//          
    }

単一チェーンテーブルの長さの取得

    public static int GetLength(Node first){
        int n=0;
        for(Node x=first;x!=null;x=x.Next){
            ++n;
        }
        return n;
    }

シングルチェーンテーブルの長さを印刷

    public static void PrintLength(Node first){
        System.out.println("Length : "+GetLength(first));
    }

単一チェーンテーブル指定されたインデックスのノードを削除

    public static Node Delete(Node first,int index){
        if(index<0||index>=GetLength(first)) return first;
        else{
        Node ret=new Node();
        ret.Next=first;
        Node p=ret;
        while((index--)!=0) p=p.Next;
        //         
        p.Next=p.Next.Next;
        return ret.Next;
        }
    }

単一チェーンテーブルは要素検索を実現し、ブール値が存在するかどうかを返します.

    public static boolean Find(Node first,int key){
        for(Node x=first;x!=null;x=x.Next){
            if(x.data==key) return true;
        }
        return false;
    }

単一チェーンテーブル指定されたインデックスの後続ノードを削除

    public static void RemoveAfter(Node first,int index){
        Node ret=new Node();
        ret.Next=first;
        Node p=ret;
        while((index--)!=0) p=p.Next;
        p.Next.Next=null;

    }

シングルチェーンテーブル反転

    public static Node  reverse(Node list){
        Node curr=list,pre=null;
        while(curr!=null){
            Node next=curr.Next;
            curr.Next=pre;
            pre=curr;
            curr=next;
        }
        return pre;
    }

単一チェーンテーブルの再帰的な反転

    public static Node reverseRecursively(Node head){
        if(head==null||head.Next==null) return head;//       ，           
        Node reversedListHead=reverseRecursively(head.Next);
        head.Next.Next=head;//              
        head.Next=null;
        return  reversedListHead;//           
    }

チェーンテーブルにリングが含まれているかどうかを検出

    public static boolean checkCircle(Node list){
        if(list==null) return false;

        Node fast=list.Next;
        Node slow=list;

        while(fast!=null&&fast.Next!=null){
            fast=fast.Next.Next;
            slow=slow.Next;

            if(slow==fast) return true;
        }
        return false;
    }

最後からk番目のノードを削除

    public static Node deleteLastKth(Node list,int k){
        //      ，fast slow，     k   ，    fast.Nest=null,     slow         k   
        Node fast=list;
        int i=1;
        while(fast!=null&&i

中間のノードを求めます

    public static Node findMiddleNode(Node list){
        if(list==null) return null;

        Node fast=list;
        Node slow=list;

        while(fast!=null&&fast.Next!=null){
            fast=fast.Next.Next;
            slow=slow.Next;
        }

        return slow;
    }

順序付きチェーンテーブルの結合

    public static Node mergeTwoLists(Node l1,Node l2){
        Node soldier=new Node();
        Node p=soldier;

        while(l1!=null&&l2!=null){
            if(l1.data

3.スタック

シーケンススタック

チェーンスタック

1.配列に基づいて実現される順序スタック

構造関数

インスタック動作

スタックアウト動作

印刷動作

package Stack;

//          
public class ArrayStack {
    private int[] items;
    private int count;//       
    private int n;//    
  //     ，       n     
public ArrayStack(int n){
    this.items=new int[n];
    this.n=n;
    this.count=0;
}

//    
public boolean push(int item){
    //      ，    false，    
    if(count==n) return false;
    // data     count   ，  count  
    items[count]=item;
    ++count;
    return true;
}

//    
public int pop(){
    //   ，    -1;
    if(count==0) return -1;
    //     count-1     ，        count  
    int tmp=items[count-1];
    --count;
    return tmp;
}
public void PrintStack(){
    for(int i=count-1;i>=0;--i){
        System.out.print(items[i]+" ");
    }
    System.out.println();
    }
}

2.チェーンテーブルベースのチェーンスタック

インスタック動作

スタックアウト動作

印刷動作

package Stack;

public class LinkedListStack {
    private Node top;//  （       ）
    private int N;//    
    private class Node{
        //         
        int data;
        Node Next;
    }
    public boolean isEmpty(){
        return top==null;
    }
    public int size(){
        return N;
    }

    public void push(int data){
        /*Node newNode=new Node();
        //       
        //if(top==null) 
        newNode=top;
        top.data=data;
        top.Next=newNode;
        N++;*/
        Node newNode=top;
        top=new Node();
        top.data=data;
        top.Next=newNode;
        ++N;
    }
    public int pop(){
        //       
        if(top==null) return -1;//   -1        
        int data=top.data;
        top=top.Next;
        N--;
        return data;
    }
    public void PrintStack(){
        for(Node x=top;x!=null;x=x.Next){
            System.out.print(x.data+" ");
        }
        System.out.println();
    }

}

4.一般キュー

配列に基づく一般的なキュー

チェーンテーブルに基づくキュー

配列に基づく循環キュー

1.配列ベースの一般的なキュー

構造関数

エンキュー操作

デキュー操作

印刷キューの要素

package Queue;

//       
public class ArrayQueue {
    //  ：items，    ：n
    private int[] items;
    private int n=0;
    //head      ，tail      
    private int head=0;
    private int tail=0;

    //       capacity   
    public ArrayQueue(int capacity){
        items=new int[capacity];
        n=capacity;
    }

    //  ( ),   
    public boolean enqueue(int item){
        //  tail==n，             
        if(tail==n) return false;
        items[tail]=item;
        ++tail;
        return true;
    }

    //  （ ），   
    public boolean enqueue1(int item){
        //  tail==n，             
        if(tail==n){
            //tail==n&&head==0,          
            if(head==0) return false;
            //    
            for(int i=head;i

2.チェーンテーブルに基づくキュー

構造関数

エンキュー操作

デキュー操作

印刷キューの要素

package Queue;

//         
public class LinkedListQueue {

    private Node head;//            
    private Node tail;//            
    private int N;//        
    private class Node{
        //         
        int data;
        Node Next;
    }
    public boolean isEmpty(){
        return head==null;
    }
    public int size(){ return N;}

    //       ,   
    public void enqueue(int data){
        Node newNode=tail;
        tail=new Node();
        tail.data=data;
        tail.Next=null;
        if(isEmpty()) head=tail;
        else newNode.Next=tail;
        ++N;
    }
    public int dequeue(){
        //       
        int data=head.data;
        head=head.Next;
        if(isEmpty()) tail=null;
        N--;
        return data;
    }

    //        
    public void PrintQueue(){
        for(Node x=head;x!=null;x=x.Next){
            System.out.print(x.data+" ");
        }
        System.out.println();
    }
}

3.配列ベースの循環キュー

構造関数

エンキュー操作

デキュー操作

印刷キューの要素

package Queue;

public class CircularQueue {
    //  items，    n
    private int[] items;
    private int n=0;
    //head      ，tail      
    private int head=0;
    private int tail=0;

    //       capacity   
    public CircularQueue(int capacity){
        items = new int[capacity];
        n=capacity;
    }

    //  
    public boolean enqueue(int item){
        //    
        if((tail+1)%n==head) return false;
        items[tail]=item;
        tail=(tail+1)%n;//       
        return true;
    }

    //  
    public int dequeue(){
        //  head==tail，      
        if(head==tail) return -1;// -1      
        int ret=items[head];
        head=(head+1)%n;
        return ret;
    }

    //    
    public void PrintQueue(){
        if(n==0) return;
        for(int i=head;i%n!=tail;i=(i+1)%n){
            System.out.print(items[i]+" ");
        }
        System.out.println();
    }
}

説明
文章のコードが多すぎて、私はもともといくつかの文章に分けて書くことを望んでいましたが、いくつかの原因で、最終的に一緒に置いて、少し太っていました.コードはすべてテスト例でテストされたので、間違いはないはずです.
もし体験があまりよくなければ、私のGithubを移動することができて、中の観感は比較的に良いです.
余談:アルゴリズム初心者には、niceの本「アルゴリズム第4版」をお勧めします.中にはいろいろな配図が詳しく入っています.電子版ファイルが必要な場合は、バックグラウンド返信アルゴリズム4でダウンロードリンクを取得できます.バックグラウンド返信アルゴリズム01は、アルゴリズムとデータ構造の思考ガイドを送ります.最後に、私たちが一緒に進歩して、一緒に成長することを望んでいます!