【データ構造】JavaによるチェーンテーブルクラスLinkListの実装

78576 ワード

チェーンテーブル紹介

Java->チェーンテーブルAPI

Java->チェーンテーブルコード

チェーンテーブル使用例

チェーンテーブルの紹介
Javaインプリメンテーションのシーケンステーブルを知りたい場合は、ここをスタンプします:【データ構造】JavaインプリメンテーションシーケンステーブルクラスSeqListを使用します
上記で紹介したシーケンステーブルはデータストレージ構造として多くの利点があり,最も重要なのはシーケンステーブルの要素がランダムにアクセスされることである.しかしシーケンステーブルにも多くの欠点があり,主な欠点は2つあり,1つは挿入と削除の効率が低下し,挿入と削除操作には部分要素の位置を変化させる必要があり,時間的複雑度はO(n)である.2つ目は、データが作成されるとサイズを変更することはできません.配列の容量を拡大するには、新しいより大きな新しい配列を作成し、元の配列を新しい配列にコピーする必要があります.これはとても不便です.
そこで上記の問題を解決するために、チェーンテーブルが現れ、チェーンテーブルの主な特徴は:1、チェーンテーブルの大きさは動的で、データの増加あるいは削除に伴って動的に長さを変える.2、チェーンテーブルの挿入、削除は非常に効率的で、常にデータの挿入と削除を必要とする応用に対して、チェーンテーブルをデータストレージ構造として使用するのに非常に適している.
シーケンステーブルとチェーンテーブルは線形テーブルに属します.
Java->チェーンテーブルAPI
コードを見る前に、チェーンテーブルがどのようなタスクを完了する必要があるか、つまりチェーンテーブルのAPIを見てみましょう.これはコードの理解に役立ち、自分が実現したい機能を迅速に検索するのに役立ちます.

LinkList():コンストラクション関数

clear():リスト全体を削除

removeAll():リスト全体を削除し、clear関数を呼び出して

を実現します.

getNode(int i):論理的i番ノード

を取得する.

get(int i):論理上のi番ノードの値

を取得する.

set(int i,Tx):i番ノードの値

を変更する

add(int i,Tx):値xのノードをi番位置

に挿入する.

add(T key):チェーンテーブルの末尾に要素key

を挿入する

addBack(T key):チェーンテーブルの末尾に要素keyを挿入し、add(T key)関数と同様に

addFront(T key):チェーンテーブルの先頭に要素key

を挿入する

remove(int i):i番ノードを削除し、i番ノードに対応する値

を返します.

remove():removeを再ロードし、ヘッダノード

を削除する.

removeFront():チェーンヘッダーノードを削除し、remove()関数と同義

removeBack():チェーンテーブルの末尾ノード

を削除

addSort(T value):値valueを小さい順にチェーンテーブル

に挿入する.

sort():チェーンテーブルを小さい順に並べ替える

indexOf(int begin,int end,T key):インデックスbeginとendの間で値keyを検索し、論理番号

を返します.

search(T key):機能はindexOfと同じで、チェーンテーブル全体を遍歴し、一般的には使用されず、主に辞書

を実現するために使用される.

contains(T key):チェーンテーブルに値がkeyノード

が存在するか否かを判断する.

toString():チェーンテーブルの値を文字列

に変換します.

toArray():チェーンテーブルをObject配列

に変換する

toArray(E[]a):単一チェーンテーブルを特定のタイプの配列に変換し、関数汎用

を使用します.

iterator():反復オブジェクト

を返します.
Java->チェーンテーブルコード
1、コードを使うときはpackageを自分のファイルがあるパッケージ名に変更することを忘れないでください.2、コードのLinkListで継承された親AbsListはここでは書かれていません.コードを書くとき、シーケンステーブルSeqListでAbsListクラスを実現しました.このAbsListはデフォルトでdefault、つまりパケットアクセス権(default修飾のクラスはパケットアクセス)です.それから、SeqListとLinkListの2つのクラスを1つのパケットに入れました.だから実はLinkListが使用しているAbsListは実はSeqListクラスのAbsListなので、ここでは前編のSeqListのAbsListを使用していますので、このクラスを使用できるようにするには、上記の記事のAbsListクラスcopyを探してみてください.あるいは---->転送ドアをクリックしても届きます

/*
 * created on April 16 14:40 2019
 * 
 * @author:lhy
 */
package DS;

import java.util.Iterator;


//     Lnode
class Lnode<T> implements Comparable<Lnode<T>> {
	public T data;	//    
	public Lnode<T> next;	//       

	// Lnode    
	public Lnode(T key) {
		data = key;
		next = null;
	}

	public Lnode(T key, Lnode<T> next) {
		data = key;
		this.next = next;
	}

	//          
	public boolean equals(Object e) {
		Lnode<T> node = (Lnode<T>) e;
		return data.equals(node.data);
	}

	//   Comparable compareTo  ，            
	public int compareTo(Lnode<T> e) {
		Comparable<T> x;
		if(data instanceof Comparable) {
			x=(Comparable<T>)data;
			return (int)x.compareTo(e.data);
		}
		else {
			throw new ClassCastException("      ");
		}
	}
	
	//             
	public String toString() {
		return data.toString();
	}
}

/*
 * LinkList API  
 * 
 * LinkList():     
 * clear():       
 * removeAll():       ,  clear     
 * getNode(int i):      i   
 * get(int i):      i     
 * set(int i,T x):   i     
 * add(int i,T x):    x      i   
 * add(T key):          key
 * addBack(T key):          key， add(T key)       
 * addFront(T key):          key
 * remove(int i):   i   ，   i       
 * remove():   remove，     
 * removeFront():        ， remove()    
 * removeBack():        
 * addSort(T value):   value              
 * sort():                 
 * indexOf(int begin,int end,T key):    begin end     key，      
 * search(T key):    indexOf，      ，     ，        
 * contains(T key):            key  
 * toString():             
 * toArray():       Object  
 * toArray(E[] a):               ，       
 * iterator():        
 */
public class LinkList<T> extends AbsList<T> implements Iterable<T> {
	//LinkList   SeqList  AbsList   ，   Iterable  
	Lnode<T> first=null,last=null; //       
	Iterator<T> iterator=null; //          
	//    
	public LinkList() {
		first=last=null;
		length=0;
		this.iterator=new LinkIterator();
	}
	
	//   ，     
	private int compare(Lnode<T> a,Lnode<T> b) {
		return a.compareTo(b);
	}
	//      
	public void clear() {
		first=last=null;
		length=0;
	}
	
	//      ,  clear     
	public void removeAll() {
		clear();
	}
	
	//      i   
	public Lnode<T> getNode(int i){
		//  i       
		if(i<0||i>length-1) {
			return null;
		}
		//  i       （        ）
		if(i==0) {
			return first;
		}
		else {
			Lnode<T> p=first;
			int j=0;
			while (p!=null&&j<i) {
				p=p.next;
				j++;
			}
			return p;
		}
		
	}
	
	//  i     ，  getNode      
	public T get(int i) {
		Lnode<T> pLnode=getNode(i);
		if(pLnode==null)
			return null;
		else 
			return pLnode.data;
	}
	
	//  i     
	public boolean set(int i,T x) {
		Lnode<T> p=getNode(i);
		if(p==null) {
			return false;
		}
		else {
			p.data=x;
			return true;
		}
	}
	
	//   x      i   
	public void add(int i,T x) {
		Lnode<T> p,s;
		int j=i-1;
		s=new Lnode<T>(x,null);
		//         s
		if(first==null||length==0) {
			first=s;
			last=s;
		}
		
		//          s， i=0 
		else if(j<0) {
			s.next=first;
			first=s;
		}
		//         s
		else if(j>=length-1) {
			last.next=s;
			last=s;
		}
		//         s
		else {
			p=getNode(j);
			s.next=p.next;
			p.next=s;
		}
		length++;
	}
	
	//  add()  ，         key
	public void add(T key) {
		add(length,key);
	}
	
	//         key， add(T key)       
	public void addBack(T key) {
		add(length,key);
	}
	
	//         key
	public void addFront(T key) {
		add(0,key);
	}
	
	//  i   ，   i       ，    removeNode  
	public T remove(int i) {
		Lnode<T> p=removeNode(i);
		if(p!=null)
			return p.data;
		else
			return null;
	}
	
	//    ，      i   ，    ，  Lnode
	protected Lnode<T> removeNode(int i){
		Lnode<T> p,q;
		//        
		if(first==null) {
			return null;
		}
		//     
		if(i==0) {
			p=first;
			first=first.next;
			length-=1;
			return p;
		}
		//          
		if(i>=1 && i<=length-1) {
			//    i-1       
			p=getNode(i-1);
			//  i        
			q=p.next;
			p.next=q.next;
			if(q==last) {
				last=p;
			}
			length--;
			return q;
		}
		return null;
	}
	
	//  remove，     
	public T remove() {
		return removeNode(0).data;
	}
	
	//     ， remove()    
	public T removeFront() {
		return removeNode(0).data;
	}
	
	//     
	public T removeBack() {
		return removeNode(length-1).data;
	}
	
	//  value              ，  insertOrder  
	public void addSort(T value) {
		Lnode<T> s=new Lnode(value);
		insertOrder(s);
	}
	
	//         
	private void insertOrder(Lnode<T> s) {
		Lnode<T> p1,p2;
		length++;
		//         
		if(first==null) {
			first=s;
			last=first;
			return ;
		}
		//       ，           
		if(compare(s, first)<0) {
			s.next=first;
			first=s;
			return ;
		}
		//         ，          
		if(compare(s, last)>0) {
			last.next=s;
			last=s;
			return ;
		}
		//      p p1 p2  ，p1  ，p2  
		p2=first;
		p1=p2;
		while(p2!=null) {
			//s   p2    , p1  p2，p2      ,  s    p2     ，  s     p1 p2  
			if(compare(s, p2)>0) {
				p1=p2;
				p2=p2.next;
			}
			else {
				break;
			}
		}
		s.next=p2;
		p1.next=s;
		return;
	}
	
	//     
	public void sort() {
		LinkList<T> sl=new LinkList<T>();//             
		Lnode<T> p;
		p=this.removeNode(0);//          
		while(p!=null) {
			sl.addSort(p.data);
			p=this.removeNode(0);
		}
		Lnode<T> q=sl.first;
		while(q!=null) {
			this.add(q.data);
			q=q.next;
		}
	}
	
	//   begin end     key，      
	public int indexOf(int begin,int end,T key) {
		Lnode<T> p=getNode(begin);//      
		int i=begin;
		while(p!=null&&i<end) {
			if(p.data.equals(key))
				return i;
			p=p.next;
			i++;
		}
		return -1;
	}
	
	//   indexOf，     ，        
	public T search(T key) {
		Lnode<T> p=getNode(0);
		while(p!=null) {
			if(p.data.equals(key)) {
				return p.data;
			}
			p=p.next;
		}
		return null;
	}
	
	//           key  
	public boolean contains(T key) {
		if(indexOf(0,length,key)==-1) return false;
		else return true;
	}
	
	//            
	public String toString() {
		String string;
		Lnode<T> pLnode;
		pLnode=first;
		string="(";
		while(pLnode!=null) {
			string+=pLnode.data.toString()+" ";
			pLnode=pLnode.next;
		}
		return string+")";
	}
	
	//      Object  
	public Object[] toArray() {
		Object[] a=new Object[length];
		Lnode<T> pLnode=first;
		for(int i=0;i<length;i++) {
			a[i]=pLnode.data;
			pLnode=pLnode.next;
		}
		return a;
	}
	
	//              ，       
	public <E> E[] toArray(E[] a) {
		if(a.length<length) {
			//       length(       )，     a        ，      E[]  
			a=(E[])java.lang.reflect.Array.newInstance(a.getClass().getComponentType(), length);
		}
		int i=0;
		Object[] result=a;
		Lnode<T> xLnode=this.first;
		for(i=0;i<length;i++) {
			result[i]=xLnode.data;
			xLnode=xLnode.next;
		}
		if(a.length>length) {
			a[length]=null;
		}
		return a;
	}
	
	//       
	public Iterator<T> iterator(){
		return new LinkIterator();
	}
	
	//   ，     
	private class LinkIterator implements Iterator<T>{
		private int index=0;
		private Lnode<T> current=first;
		public boolean hasNext() {
			//   next()  ，index  ，  index   person   
			return (index!=length() && current!=null);
		}
		
		public T next() {
			T temp=current.data;
			current=current.next;
			index++;
			return temp;
		}
		
		public int nextIndex() {
			return index++;//   index  ，  1
		}
		public void remove() {
			//      
		}
	}
}

チェーンテーブルの使用例
LinkListチェーンテーブルオブジェクトを作成し、LinkListクラスの各関数を検証します.コードは以下の通りです.

/*
 * created on April 16 15:40 2019
 * 
 * @author:lhy
 */
package DS;

import java.util.Iterator;

/*
 * LinkList API  
 * 
 * LinkList():     
 * clear():       
 * removeAll():       ,  clear     
 * get(int i):      i     
 * set(int i,T x):   i     
 * add(int i,T x):    x      i   
 * add(T key):          key
 * addBack(T key):          key， add(T key)       
 * addFront(T key):          key
 * remove(int i):   i   ，   i       
 * remove():   remove，     
 * removeFront():        ， remove()    
 * removeBack():        
 * addSort(T value):   value              
 * sort():                 
 * indexOf(int begin,int end,T key):    begin end     key，      
 * search(T key):    indexOf，      ，     ，        
 * contains(T key):            key  
 * toString():             
 * toArray():       Object  
 * toArray(E[] a):               ，       
 * iterator():        
 */

public class Test_LinkList {
	public static void main(String[] args) {
		LinkList<Integer> linkList=new LinkList<Integer>();
		// linkList  
		for(int i=0;i<10;i++) {
			linkList.add((int)(Math.random()*1000));
		}
		System.out.println("            ："+linkList.toString());
		System.out.println("  7         ："+linkList.get(7));
		//    1       2333
		linkList.set(1,2333);
		System.out.println(" 1       2333，    ："+linkList.toString());
		// 3       5555   
		linkList.add(3,5555);
		System.out.println(" 3         5555   ,    ："+linkList.toString());
		//         9999   
		linkList.add(9999);
		System.out.println("         9999   ,    ："+linkList.toString());
		//         12345   
		linkList.addFront(12345);
		System.out.println("         12345   ，    ："+linkList.toString());
		System.out.println("  4   ，    ："+linkList.remove(4));
		System.out.println("  4    ，    "+linkList.toString());
		//     
		linkList.removeBack();
		System.out.println("      ，    ："+linkList.toString());
		// linkList    
		linkList.sort();
		System.out.println("       ："+linkList.toString());
		//            666   
		linkList.addSort(666);
		System.out.println("            666    ，    ："+linkList.toString());
		System.out.println("    666          ："+linkList.indexOf(0, linkList.length,666));
		System.out.println("          665   ："+linkList.contains(665));
		//           
		Iterator<Integer> iterator=linkList.iterator();
		//           
		System.out.print("           ：");
		while(iterator.hasNext()) {
			System.out.print(iterator.next()+" ");
		}
		//    
		linkList.clear();
		System.out.println("
        ："+linkList.toString());

	}
}

出力:

            ：(834 738 152 568 863 608 495 975 742 475 )
  7         ：975
 1       2333，    ：(834 2333 152 568 863 608 495 975 742 475 )
 3         5555   ,    ：(834 2333 152 5555 568 863 608 495 975 742 475 )
         9999   ,    ：(834 2333 152 5555 568 863 608 495 975 742 475 9999 )
         12345   ，    ：(12345 834 2333 152 5555 568 863 608 495 975 742 475 9999 )
  4   ，    ：5555
  4    ，    (12345 834 2333 152 568 863 608 495 975 742 475 9999 )
      ，    ：(12345 834 2333 152 568 863 608 495 975 742 475 )
       ：(152 475 495 568 608 742 834 863 975 2333 12345 )
            666    ，    ：(152 475 495 568 608 666 742 834 863 975 2333 12345 )
    666          ：5
          665   ：false
           ：152 475 495 568 608 666 742 834 863 975 2333 12345 
        ：()

15、javascriptスクリプト言語

XR開発時の参考資料集