데이터 구조 (7) -- 시퀀스

서열
본 고 는 일반적인 서열 ADT 를 정의 하고 실현 하여 벡터 ADT 와 목록 ADT 의 모든 방법 을 통합 시 킬 것 이다. 즉, 이 ADT 는 순위 나 위치 로 그 중의 요 소 를 방문 하 는 것 을 동시에 지원 할 것 이다.따라서 이런 데이터 구 조 는 더 많은 실제 문 제 를 해결 하 는 데 적 용 될 것 이다.
데이터 구조 (5) - 벡터
데이터 구조 (6) -- 목록
2. 시퀀스 ADT (AbstractDataType)
시퀀스 ADT 는 벡터 ADT 와 목록 ADT 의 모든 방법 을 동시에 지원 할 것 입 니 다. 그 밖 에 다음 과 같은 두 가지 방법 도 지원 합 니 다. 바로 이 두 가지 방법 을 통 해 우 리 는 순위 와 위치의 개념 을 연결 할 수 있 습 니 다.
조작 방법
기능 설명
rank2Pos(r)
0 ≤ r < getSize () 의 경우 r 의 요소 가 있 는 위 치 를 되 돌려 줍 니 다.그렇지 않 으 면 오류 입력: 하나의 정수 출력: 위치
pos2Rank(p)
p 가 시퀀스 의 합 법 적 인 위치 라면 p 에 저 장 된 요소 의 순 서 를 되 돌려 줍 니 다.그렇지 않 으 면 오류 입력: 한 위치 출력: (순위 로) 정수
3. 양 방향 링크 를 바탕 으로 서열 을 실현 한다.
인터페이스:

package dsa.Sequence;

import other.Position;
import dsa.List.ExceptionPositionInvalid;
import dsa.List.List;
import dsa.Vector.ExceptionBoundaryViolation;
import dsa.Vector.Vector;

/*
 *     
 */

public interface Sequence extends Vector, List {
    //  0 <= r < getSize()，     r        ；  ，  
    public Position rank2Pos(int r) throws ExceptionBoundaryViolation;

    //  p         ，      p      ；  ，  
    public int pos2Rank(Position p) throws ExceptionPositionInvalid;
}

실현:

package dsa.Sequence;

import other.Position;
import dsa.Deque.DLNode;
import dsa.List.ExceptionPositionInvalid;
import dsa.List.List_DLNode;
import dsa.Vector.ExceptionBoundaryViolation;

/*
 *           
 */
public class Sequence_DLNode extends List_DLNode implements Sequence {
    //    r   [0, n)  
    protected void checkRank(int r, int n) throws ExceptionBoundaryViolation {
        if (r < 0 || r >= n)
            throw new ExceptionBoundaryViolation("  ：    " + r + "，    [0, "
                    + n + ")");
    }

    //  0 <= r < getSize()，     r        ；  ，  --O(n)
    public Position rank2Pos(int r) throws ExceptionBoundaryViolation {
        DLNode node;
        checkRank(r, getSize());
        if (r <= getSize() / 2) {//     ， 
            node = header.getNext();//      
            for (int i = 0; i < r; i++)
                node = node.getNext();//     
        } else {//     ， 
            node = trailer.getPrev();//      
            for (int i = 1; i < getSize() - r; i++)
                node = node.getPrev();//     
        }
        return node;
    }

    //  p         ，      p      ；  ，  --O(n)
    public int pos2Rank(Position p) throws ExceptionPositionInvalid {
        DLNode node = header.getNext();
        int r = 0;
        while (node != trailer) {
            if (node == p)
                return (r);
            node = node.getNext();
            r++;
        }
        throw new ExceptionPositionInvalid("  ：            ");
    }

    //    r   --O(n)
    public Object getAtRank(int r) throws ExceptionBoundaryViolation {
        checkRank(r, getSize());
        return rank2Pos(r).getElem();
    }

    //    r      obj--O(n)
    public Object replaceAtRank(int r, Object obj)
            throws ExceptionBoundaryViolation {
        checkRank(r, getSize());
        return replace(rank2Pos(r), obj);
    }

    //   obj，    r   --O(n)；     
    public Object insertAtRank(int r, Object obj)
            throws ExceptionBoundaryViolation {
        checkRank(r, getSize() + 1);
        if (getSize() == r)
            insertLast(obj);
        else
            insertBefore(rank2Pos(r), obj);
        return obj;
    }

    //     r   --O(n)
    public Object removeAtRank(int r) throws ExceptionBoundaryViolation {
        checkRank(r, getSize());
        return remove(rank2Pos(r));
    }
}