선형 표 의 순서 저장 구조의 순서 표 류 의 실현Java

이전 블 로그 - 선형 표 인터페이스 의 실현자바 에서 우 리 는 선형 표 의 인 터 페 이 스 를 실현 했다. 오늘 우 리 는 선형 표 의 순서 저장 구조 인 순서 표 류 를 실현 한다.
우선 순서 표 의 정 의 를 살 펴 보 자.
선형 표 의 순서 저장 은 연속 적 인 메모리 유닛 으로 선형 표 의 데이터 요 소 를 순서대로 저장 하 는 것 이다. 요소 가 메모리 에 있 는 물리 적 저장 순 서 는 선형 표 에서 의 논리 적 순서 와 같다. 즉, 요소 ai 는 직접 전구 ai - 1 과 직접 후계 ai + 1 의 저장 위치 와 인접 하 다.순차 적 으로 저 장 된 선형 표 도 순서 표 (sequential list) 가 된다.
순서 표 류 SeqList 는 선형 표 가 순서 저장 구 조 를 바탕 으로 하 는 실현 을 제공 합 니 다. 이 는 두 개의 개인 구성원 변수 table 과 n 이 있 고 table 은 요 소 를 저장 하 는 대상 배열 입 니 다.n 은 선형 표 길이, n ≤ table. length.SeqList 성명 은 다음 과 같 습 니 다. 선형 표 의 인터페이스 LList 를 실현 합 니 다.

package dataStructure.linearList;
import dataStructure.linearList.LList;

public class SeqList implements LList					//    ，       
{
	private Object[] table;									//    ，    
	private int n;											//     
	
	public SeqList(int capacity)							//    ，         
	{
		this.table = new Object[Math.abs(capacity)];
		this.n = 0;
	}
	
	public SeqList()										//         
	{
		this(16);
	}
	
	public boolean isEmpty()								//         ，    true
	{
		return this.n == 0;
	}
	
	public int length()										//       
	{
		return this.n;
	}
	
	public E get(int index)									//  index(   0)     ，     ，  null
	{
		if(index>=0 && index < this.n)
		{
			return (E)this.table[index];
		}
		return null;
	}
	
	public E set(int index,E element)						//  index      element，     ，     ，    null
	{
		if(index >= 0 && index < this.n && element != null)
		{
			E old =(E)this.table[index];
			this.table[index] = element;
			return old;
		}
		return null;
	}
	
	public boolean add(int index,E element)					// index    element  ，       true，    null
	{
		if(element == null)									//    null
		{
			return false;
		}
		if(this.n == table.length)							//    ，          
		{
			Object[] temp = this.table;
			this.table = new Object[temp.length*2];			//             
			for(int i = 0;i < temp.length;i++)
			{
				this.table[i] = temp[i];
			}
		}
		
		if(index < 0)										//    
		{
			index = 0;
		}
		if(index > this.n)
		{
			index =this.n;
		}
		for(int j = this.n-1;j >= index;j--)				//    ，    n/2
		{
			this.table[j+1] = this.table[j];
		}
		this.table[index] = element;
		this.n++;
		return true;
	}
	
	public boolean add(E element)							//        element  
	{
		return add(this.n,element);
	}
	
	public E remove(int index)								//  index     ，     ，         ，    null
	{
		if(this.n != 0 && index >= 0 && index < this.n)
		{
			E old = (E)this.table[index];
			for(int j = index;j < this.n-1;j++)				//    ，    n/2
			{
				this.table[j] = this.table[j + 1];
			}
			this.table[this.n - 1] = null;
			this.n--;
			return old;
		}
		return null;
	}
	
	public void clear()										//     
	{
		if(this.n != 0)
		{
			for(int i = 0;i < this.n;i++)
			{
				this.table[i] = null;
			}
			this.n=0;
		}
	}
	public String toString()								//            ，   (,)
	{
		String str = "(";
		if(this.n != 0)
		{
			for(int i = 0;i < this.n - 1;i++)
			{
				str += this.table[i].toString()+",";
			}
			str += this.table[this.n - 1].toString();
		}
		return str + ")";
	}
}

순서 표 는 모든 요 소 를 액세스 하 는 get (), set () 방법의 시간 복잡 도 는 O (1) 입 니 다.
순서 표를 삽입 하거나 삭제 하 는 작업 은 알고리즘 이 걸 리 는 시간 은 주로 요 소 를 이동 하 는 데 사 용 됩 니 다.등 확률 상황 에서 하나의 요 소 를 삽입 하려 면 평균 절반 의 요 소 를 이동 해 야 하고 시간 복잡 도 는 O (n) 이다.같은 맥락 에서 하나의 요 소 를 삭제 하 는 시간 복잡 도 는 O (n) 입 니 다.
상술 한 바 와 같이 순서 표 는 다음 과 같은 특징 을 가지 고 있다.
①: 요소 의 물리 적 저장 순 서 는 표 에 있 는 요소 의 논리 적 순 서 를 직접 반영 하여 요 소 를 무 작위 로 액세스 할 수 있다.
② 삽입 및 삭제 작업 효율 이 낮다.하나의 요 소 를 삽입 하거나 삭제 할 때마다 대량의 요 소 를 이동 해 야 할 수 있 습 니 다. 평균 이동 횟수 는 순서 표 길이 의 절반 입 니 다.게다가 배열 의 용량 은 변경 할 수 없고 용량 이 작 아서 데이터 가 넘 치 거나 용량 이 너무 커서 메모리 자원 의 낭 비 를 초래 하 는 문제 가 존재 한다.데이터 넘 침 을 해결 하 는 방법 은 다른 대 용량 의 배열 을 신청 하고 배열 요 소 를 복사 하 는 것 이지 만 삽입 작업 효율 이 낮다.
다음 장 에서 저 는 여러분 과 순서 표 로 조세 프 문 제 를 해결 하 는 것 을 토론 할 것 입 니 다 (조세 프 링).