제3장 총결산
추상 데이터 형식(abstract data type, ADT)은 일련의 작업을 가진 대상의 집합이다.
배열 구현 테이블의 용량 확장:
int[] newArr=new int[arr.length*2];
for(int i=0;i
newArr[i]=arr[i];
arr=newArr;
3.3 Java Collections API의 테이블
ADT 추가 삭제 요약:
l 교체기는remove를 삭제하고next()에서 최근에 되돌아온 항목을 삭제합니다. 이후에remove()를next()에 다시 호출할 때까지 실행할 수 없습니다.
교체기 삭제는 용기 클래스 삭제보다 정확한 위치를 알고 있습니다.
교체기나 증강for를 사용하면 교체된 집합이 구조적으로 바뀌고 (add/remove/clear) 있으면 교체기는currentModificationException 이상을 합법적으로 던지지 않습니다.
상기 교체기의 두 가지 장점을 바탕으로 교체기의 사용 원칙은 다음과 같다. 교체기는 즉각 사용할 때만 얻을 수 있고 교체기는 자신의remove 방법을 사용하는 것이 합법적이다.
반복하는 방법은 세 가지가 있는데 그것이 바로 교체기, 증강for, 색인 번호이다.
l 공백기 인터페이스add/remove는 반복적으로 삭제됩니다.집합이 중복을 허용하지 않을 때 삭제할 요소가 집합에 없을 때false를 되돌려줍니다.
l List 인터페이스에는 Collections 메서드, 인덱스 수정 및 listIterator가 있습니다.
정적 함수 쓰기:public,static,범용,반환값,함수명,형참.
컨테이너 클래스 Collections 인터페이스: 공백을 판정하고 용량을 삭제합니다.Collections 인터페이스는 Iterable 인터페이스의 계승 클래스입니다.
public interface Collection extends Iterable{
int size();
boolean isEmpty();
void clear();
boolean add(AnyType x);
boolean remove(AnyType x);
boolean contains(AnyType x);
java.util.Iterator iterator();
}
교체기 Iterator 커넥터:
public interface Iterator{
boolean hasNext();
AnyType next();
void remove();
}
List 인터페이스:list 인터페이스에 색인화된 추가 검색 방법 (add/remove/set/get) 과listIterator 교체기를 추가했습니다.
public interface List extends Collection{
void add(int idx,AnyType x);
void remove(int idx,AnyType x);
AnyType set(int idx,AnyType x);
AnyType get(int idx);
ListIterator listIterator(int pos);
}
List의 ArrayList 구현은 get/set에서 O(1)를 사용합니다.Array List의 끝에 변동이 발생하지 않는 한 add/remove는 비용이 많이 듭니다.
리스트의 더블 체인 테이블 링크드 리스트는 변동 항목의 위치가 알려진 상황에서dd/remove 비용이 적습니다.표의 앞부분add/remove는 상수 시간을 소비하기 때문에LinkedList는ddFirst/removeFirst/addLast/removeLast 방법을 제공합니다.get/set 호출은 테이블의 끝에 접근하지 않는 한 O (N) 를 사용합니다.
ArrayList와 LinkedList를 검색하여 Collections를 실현하는 contains와remove 방법은 모두 O (N) 를 사용합니다.
ArrayList는 용량 개념이 있어 ensureCapacity () 를 추가하고 trimTosize () 를 추가하면 공간을 절약할 수 있습니다.
삭제를 위한 선택 삽입하기
l 끝 add/remove는 ArrayList, LinkedList 모두 가능합니다.
l 첫 번째 add/remove는 링크드 리스트를 사용하는데 이때 Array 리스트가 가장 나쁘다.
l 알려진 색인에 add/remove는 LinkedList를 사용합니다.
알 수 없는 색인에 추가: Array List의 이동 효율과 Linked List의 스트리밍 효율을 비교하기
l 반복 상황:Array List는 색인 번호, 교체기를 모두 O(N)할 수 있고,Linked List는 교체기 O(N)만 사용할 수 있습니다.LinkedList는 색인 번호로 이동하는 데 O (N^2) 를 사용합니다.
실제 ArrayList는 LinkedList보다 성능이 우수합니다.
프로그램 시간:
long startTime=System.currentTimeMillis();
long endTime=System.currentTimeMillis();
System.out.println ("프로그램 실행 시간:"+ (endTime-startTime) + "ms");
배열 짝수 값을 제거하고LinkedList의remove 방법을 연습합니다
한 가지 생각은 홀수를 새 시계에 복사하고, 원본을 비운 다음, 홀수를 원표로 복사하는 것이다.
또 다른 생각은 증강for를 사용하면 원소를 삭제하면 이상을 던진다는 것이다.
또 다른 생각은 색인 번호를 사용하면 Array List는 O (N) 를 쓰고 링크드 List는 O (N ^2) 를 쓴다는 것이다.
public static void removeEvensVer1(List lst){
for(int i=0;i}
더 좋은 방법은 짝수 값을 만나면 테이블을 삭제하는 것을 피하는 것이다.반복기는 반복해서 삭제할 수 있으며, O (N) 로 효율이 매우 높다.이로써 링크드 리스트의 교체기 삭제가 가장 효율적인 방법임을 검증했다.
public static void removeEvensVer2(List lst){
Iterator iter=lst.iterator();
while(iter.hasNext()){
if(iter.next()%2==0)
iter.remove();
}
}
ListIterator 인터페이스
ListIterator는 Iterator의 기능을 확장하고, 전방향 스트리밍과 교체기를 추가합니다.
public interface ListIterator extends Iterator{
boolean hasPrevious();
AnyType previous();
void add(AnyType x);
void set(AnyType x);
}
보충: ArrayList 및 LinkedList의 API
3.4 ArrayList 클래스의 구현
범용수 그룹의 생성은 불법입니다.우리의 방법은 범용 형식 한계의 그룹을 만들고 하나의 그룹으로 형식 변환을 하는 것이다.이것은 컴파일 경고를 생성하지만, 이것은 일반 집합의 실현에서 피할 수 없는 것이다.
확장 함수도 비우기와 초기화에 사용됩니다.
일반적으로 체인 테이블에 위치 지침을 저장하지 않고 여러 번 반복하는 데 적합하지 않기 때문에 체인 테이블의 내부 클래스로 쓰고 위치 지침은 교체기에 저장한다.
내부류는 교체기와 체인표 간의 은밀한 정보 교류를 형성했다.교체기에서 체인 테이블 대상을 만드는 것을 피합니다.
교체기에서current라고 불리며next()를 가리키는 요소를 실현합니다.
(원서에서 비교한 교체기의 3가지 실현 방법: 2개 클래스 인용 대상, 끼워넣기 클래스, 내부 클래스. 조사 대상 간 통신)
도메인 이름 접근: 클래스 내this.데이터, 외부 클래스 내 Outer.this.data.
접근 권한:public 공공, 보호된, 만두 접근,private 클래스 내 접근.
static 플러그인 클래스는 외부 클래스의 일부로 여겨지는 층을 개방합니다.private static은 외부 클래스 범위 내에서만 작동하는 것을 의미합니다.
pulic class MyArrayList implements Iterable{
private static final int DEFAULT_CAPACITY=10;
private int theSize;
private AnyType[] theItems;
public int size(){
return theSize;
}
public boolean isEmpty(){
return size()==0;
}
public void trimToSize(){
ensureCapacity(size());
}
public void ensureCapacity(int newCapacity){
if(newCapacityidx;i--)
theItems[i]=theItems[i--];
theItems[idx]=x;
theSize++;
}
public boolean add(AnyType x){//
add(size(),x);
}
public AnyType delete(int idx){
AnyType removedItem=theItems[idx];
for(int i=idx+1;i=size())
throw new ArrayIndexOutOfBoundsException();
AnyType oldItem=theItems[idx];
theItems[idx]=x;
return oldItem;
}
public AnyType get(int idx){
if(idx<0||idx>=size())
throw new ArrayIndexOutOfBoundsException();
return theItems[idx];
}
}
3.5 LinkedList 클래스의 구현
성능:LinkedList의 '플러그인' 이외의 추가 삭제와 수정은 getNode () 방법을 사용하는 것은 모두 O (N) 시간입니다. 사용하는 것을 추천하지 않습니다.LinkedList는 교체기add/remove에만 능합니다.
링크드 리스트는 플러그인 클래스로 노드를 실현하고 인덱스로 체인을 바꾸기 전에 추가/체인 삭제를 통해 인덱스식 삭제 검사를 실현한다. 교체기는 오류 검사를 수정하지 않는 것을 의미하며 점프 바늘(next) 오류 검사, 점프 바늘 1 삭제 오류 검사를 포함한다.
LinkedList 클래스 구현:
public class MyLinkedList implements Iterable{
private Node beginMarker;
private Node EndMarker;
private int theSize;
private int modCount=0;
private static Node{//
private AnyType data;
private Node prev;
private Node next;
public Node(AnyType d,Node p,Node n){
data=d;prev=p;next=n;
}
}
private Node getNode(int idx){}
private void addBefore(Node p,AnyType x){}
private AnyType remove(Node p){}
public int size(){return theSize;}
public boolean isEmpty(){return theSize==0;}
public void clear(){}
public void add(int idx,AnyType x){addBefore(getNode(idx),x);}
public boolean add(AnyType x);
public AnyType remove(int idx){return remove(getNode idx);}
public AnyType set(int idx,AnyType newVal){
Node p=getNode(idx);
AnyType oldVal=p.data;
p.data=newVal;
return oldVal;
}
public AnyType get(int idx){return getNode(idx).data;}
}
LinkedList의 공백 설정 방법:
public void clear(){
beginMarker=Node(null,null,null);
endMarker=Node(null,beginMarker,null);
beginMarker.next=endMarker;
theSize=0;
modCount++;
}
LinkedList의 색인 체인, 체인 앞 추가, 체인 삭제:
인덱싱 방법(양방향 인덱싱은 모두 자리맞춤 기호의 원칙에 따른다):
l 인덱스 p=array[0], int i=0;i
l 역방향 인덱스 p=array [size-1], int j=size-1;i>idx.
체인은 4개의 지침을 추가하고, 체인은 2개의 지침을 삭제한다.
public Node getNode(int idx){
if(idx<0||idx>=size())
throw new IndexOutOfBoundsException();
Node p=null;
if(idxidx;i--)
p=p.prev;
}
return p;
}
public void addBefore(int idx,AnyType x){
Node p=getNode(idx);
Node newNode=new Node(x,p.prev,p);
p.prev.next=newNode;
p.prev=newNode;
theSize++;
modCount++;
}
public AnyType remove(int idx){
Node p=getNode(idx);
p.prev.next=p.next;
p.next.prev=p.prev;
theSize--;
modCount++;
return p.data;
}
LinkedList의 교체기:
교체기의current 바늘은next ()의 되돌아오는 요소를 가리킨다.
public java.util.Iterator iterator(){
return new LinkedListIterator();
}
private class LinkedListIterator implements java.util.Iterator{
Node current=beginMarker.next;
private int exceptedModCount=modCount;
private boolean okToRemove=false;
public boolean hasNext(){
return current!=endMarker;
}
public AnyType next(){
if(modCount!=exceptedModCount)
throw new java.util.ConcurrentModificationException();
if(!hasNext())
throw new java.util.NoSuchElementException();
okToRemove=true;
AnyType nextData=current.data;
current=current.next;
return nextData;
}
public void remove(){
if(modCount!=exceptedModCount)
throw new java.util.ConcurrentModificationException();
if(!okToRemove)
throw new IllegalStateException();
MyLinkedList.this.remove(current.prev);
okToRemove=false;
expectModCount++;
}
}
3.6 스택 ADT
창고는 표에서 낮은 효과로 검색하고 옮겨다니지 않으며, 창고를 눌러서push/탄창pop/창고를 비우면 모두 상수 시간이 걸립니다.창고는 LIFO 후진 선출표라고도 부른다.
창고의 체인 테이블 구현: 단일 체인 테이블을 사용하고 테이블 꼭대기 삽입은push를 실현하며 테이블 꼭대기 삭제는pop을 실현한다.
스택의 배열 개선: 배열 the Array, 스택 프레임 top Of Stack(빈 스택 top Of Stack==-1).창고에 들어오기 전에 프레임을 점프한 후 theArray [++topOfStack]=x를 부여합니다.체크아웃 return the Array [topOfStack--];
스택 구현에 theSize 필요 없음
창고는 매우 빠른 상수 시간에 운행되며, 자동 증가와 자동 주소 찾기 기능이 있는 레지스터에서push와 pop은 기계 명령어로 쓸 수 있기 때문에 창고는 수조 이후의 가장 기본적인 데이터 구조가 된다.
창고는 끊는 것을 의미한다.
스택 적용 1: 균형 기호
균형 기호 방법:
，
， ； ； （ 、 ）。
（ ）。
알고리즘 복잡도 O (N).
창고 응용 2: 접두사 표현식을 접두사 표현식으로 바꾸기(과학 계산)
접미사 회전 접미사 방법: 연산자 입고, 알파벳 전체 출력;높은 곳을 만나면 창고를 압축하고 낮은 동탄을 낮은 곳으로 출력한다.괄호를 열고 창고를 눌러 놓고, 괄호를 닫으면 열릴 때까지 탄다.복잡도 O (N).
동급 연산자 처리, 낮은 동탄에서 낮은 동탄 처리는 표현식이 왼쪽에서 오른쪽으로 진행되는 것을 보장합니다.멱 연산자(예를 들어 223=256)가 오른쪽에서 왼쪽으로 결합하는 것을 주의하고 낮은 탄환을 만나면 같은 탄환을 만나야 한다는 원칙을 따라야 한다.
역폴란드 표현식은 오른쪽에서 왼쪽으로 계산된다는 것을 알아차렸다.
창고 응용 3: 접두사 표현식 계산(과학 계산)
접미사 표현식(postfix)은 역폴란드 표현식(reverse Polish)이라고도 부른다.
역폴란드 표현식 계산 방법: 역폴란드 표현식을 읽습니다.숫자가 나오면 창고에 넣지 않는다.연산자가 두 개의 연산을 튀어나오면 연산 결과가 다시 창고에 쌓인다.복잡도 O (N).
스택 적용 4: 메소드 호출
방법 호출과 방법 반환은 개폐괄호와 유사하며 균형 기호의 검출 알고리즘도 방법 호출에 사용할 수 있다.
주 방법이 새로운 방법을 호출할 때, 주 방법의 국부 변수와 주 방법의 현재 위치를 저장합니다. 즉, 레지스터 값과 되돌아오는 주소를 새 방법으로 다시 쓰지 않도록 합니다.
새 방법이 끝났을 때 레지스터를 복원하고 이전을 되돌려줍니다.
반복되는 마운트 방법을 실현하는 창고를 '활동 기록' 또는 '창고 프레임' 이라고도 부른다.너무 많은 방법으로 창고가 넘칠 수 있습니다. 자바에서 이상을 던질 수 있습니다.
꼬리 귀속(마지막 줄 호출 귀속)은 대량의 창고 공간을 소모하는데 전형적인 귀속 사용이 부적절한 예이다.
반복되는 복구 방법은 다음과 같습니다:while에 코드를 넣고 방법 매개 변수의 값을 대체합니다.
비귀속 프로그램은 등가의 귀속 프로그램보다 빨라야 하고 속도 우위의 대가는 프로그램의 명확성이다.
3.7 대기열 ADT
대열은 모두 표두출대, 표미입대다.
대기열의 단일 체인 테이블 구현은 비교적 간단합니다: 바늘front (단일 체인 폼 표시 begin Marker), 바늘back, 수량 the Size.시계 끝에 들어가는 엔queue, 시계 끝에 나오는 dequeue.
대기열의 수조는 반환 수조를 사용합니다: 반환 수조는 theSize를 사용하여 대열의 크기를 판단하고 대열이 비어 있는 것을 더욱 편리하게 합니다.비반환수 그룹 사용: 팀은 빈 백-front=-1, 팀 크기 백-front+1(반환수 그룹은 theArray.length+back-front+1)%theArray.length).대열에 들어가기 전에 먼저 용량을 검사하고, 대열이 가득 차면 용량을 늘려야 한다.
유한한 자원은 대열에 써야 한다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
