기술나눔

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

선형 테이블

우리는 얘기하고 싶어시퀀스 테이블, 순차 테이블은 선형 테이블 유형이므로 먼저 선형 테이블에 대해 이야기해야 합니다.

선형 테이블의 정의

이름에서 알 수 있듯이 선형 테이블은 데이터를 선처럼 구성하는 테이블입니다.
현실의 대기열을 생각해보면 이해할 수 있다.

선형 테이블의 특성:

• 선형 테이블의 데이터 요소 사이에는 순서가 있습니다.
• 첫 번째 요소와 마지막 요소를 제외한 모든 요소에는 선행 요소와 후속 요소가 있습니다.

시퀀스 테이블

시퀀스 테이블은 단락을 사용합니다.물리적 주소가 연속적입니다.저장 장치는 마치 사람들이 나란히 줄을 서 있는 것과 같습니다.
일반적으로 다음을 사용하여 데이터 요소를 순서대로 저장하는 선형 구조입니다.정렬저장.
어레이의 데이터 추가, 삭제, 확인 및 수정을 완료합니다.

시퀀스 테이블 인터페이스 구현

시퀀스 테이블을 직접 구현하고(storage int 유형 데이터) 시퀀스 테이블을 클래스로 사용하며 일부 인터페이스, 즉 일부 인터페이스를 구현합니다.회원 방법데이터의 추가, 삭제, 확인 및 수정을 실현합니다.

public class SeqList {
     private int[] elem;
     private int usedSize;
     // 默认构造方法
     SeqList(){   }
     // 将顺序表的底层容量设置为initcapacity
     SeqList(int initcapacity){   }
     // 新增元素,默认在数组最后新增
     public void add(int data) { }
     // 在 pos 位置新增元素
     public void add(int pos, int data) { }
     // 判定是否包含某个元素
     public boolean contains(int toFind) { return true; }
     // 查找某个元素对应的位置
     public int indexOf(int toFind) { return -1; }
     // 获取 pos 位置的元素
     public int get(int pos) { return -1; }
     // 给 pos 位置的元素设为 value
     public void set(int pos, int value) {   }
     //删除第一次出现的关键字key
     public void remove(int toRemove) {   }
     // 获取顺序表长度
     public int size() { return 0; }
     // 清空顺序表
     public void clear() {   }
     
 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

기본 생성자

기본적으로 처음에는 10개의 데이터 공간을 엽니다.

private static final int DEFAULT_SIZE = 10;
    public SeqList() {
        this.elem= new int[DEFAULT_SIZE];
    }
1
2
3
4

시퀀스 테이블의 기본 용량을 initcapacity로 설정합니다.

배열 길이를 전달하고 배열 길이를 사용하여 공간을 확보합니다.

private static final int DEFAULT_SIZE = 10;
    public SeqList(int initcapacity) {
        this.elem= new int[initcapacity];
    }
1
2
3
4

테일 플러그

기본적으로 새 요소는 배열 끝에 추가됩니다.
고려해야 할 사항:

• 현재 시퀀스 테이블이 꽉 찼는지 확인하세요. 꽉 차 있으면 공간을 추가하세요.
• 요소가 추가되고 UsedSize가 1씩 증가합니다.

 public void add(int data) {
        if(isFull()){
            elem = Arrays.copyOf(elem,elem.length * 2);
        }
        elem[usedSize++] = data;
    }
     /**
     * 判断当前的顺序表是不是满的！
     *
     * @return true:满   false代表空
     */
    private boolean isFull() {
        return usedSize == elem.length;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

pos 위치에 요소 추가

pos 아래 첨자에 요소를 삽입합니다.
지침:

• 현재 시퀀스 테이블이 꽉 찼는지 확인하세요. 꽉 차 있으면 공간을 추가하세요.
• 주어진 pos 위치가 합법적입니까? 그렇지 않은 경우 예외가 발생합니다.
• 뒤로-앞으로 루프를 사용하여 위치 위치 뒤의 요소를 뒤로 이동합니다.
• 요소가 추가되고 UsedSize가 1씩 증가합니다.

private boolean checkPosInAdd(int pos) throws PosIllegalException{

        if(pos < 0 || pos > usedSize){
            throw new PosIllegalException("位置不合法");
        }
        return true;
    }

    // 在 pos 位置新增元素
    public void add(int pos, int data) {
        try{
            if(checkPosInAdd(pos)){
                if(isFull()){
                    elem = Arrays.copyOf(elem,elem.length * 2);
                }
                for (int i = usedSize; i > pos ; i--) {
                    elem[i] = elem[i-1];
                }
                elem[pos] = data;
                usedSize++;
            }
        }catch(PosIllegalException e){
            e.printStackTrace();
        }

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

요소가 포함되어 있는지 확인

주어진 데이터가 시퀀스 테이블에 포함되어 있는지 확인하세요.
직접 루프를 돌면서 찾으면 true를 반환하고, 찾지 못하면 false를 반환합니다.

public boolean contains(int toFind) {
        for (int i = 0; i < usedSize; i++) {
            if(elem[i] == toFind){
                return true;
            }
        }
        return false;
    }
1
2
3
4
5
6
7
8

요소에 해당하는 위치 찾기

이 시퀀스 테이블에서 주어진 데이터의 인덱스를 살펴보세요.
직접 반복하여 -1을 반환하지 않고 반환 첨자를 찾으세요.

public int indexOf(int toFind) {
        for (int i = 0; i < usedSize; i++) {
            if(elem[i] == toFind){
                return i;
            }
        }
        return -1;
    }
1
2
3
4
5
6
7
8

pos 위치에 있는 요소 가져오기

pos 위치의 요소를 출력합니다.
지침:

• POS가 합법인지 확인하세요

public int get(int pos) {
        try{
            if(checkPosInAdd(pos)){
                return elem[pos];
            }
        }catch(PosIllegalException e){
            e.printStackTrace();
        }
        return 0;
    }
1
2
3
4
5
6
7
8
9
10

pos 위치의 요소를 value로 설정합니다.

pos 위치 요소를 수정합니다.
지침:

• POS가 합법인지 확인하세요.

public void set(int pos, int value) {
        try{
            if(checkPosInAdd(pos)){
                elem[pos] = value;
            }
        }catch(PosIllegalException e){
            e.printStackTrace();
        }
    }
1
2
3
4
5
6
7
8
9

키워드 키의 첫 번째 항목 삭제

키의 첫 번째 항목을 삭제합니다.
지침:

• 검색을 반복합니다.
• 찾은 키 뒤의 요소를 사용하여 앞쪽으로 하나씩 덮으세요.
• UsedSize가 1씩 감소합니다.

public void remove(int key) {
        for (int i = 0; i < usedSize; i++) {
            if(elem[i] == key){
                for (int j = i; j < usedSize - 1; j++) {
                    elem[j] = elem[j + 1];
                }
                usedSize--;
            }
        }
    }
1
2
3
4
5
6
7
8
9
10

시퀀스 테이블 길이 가져오기

여기서 시퀀스 테이블의 길이를 구한다는 것은 유용한 데이터의 개수, 즉 UsedSize를 의미한다.

public int size() {
        return usedSize;
    }
1
2
3

시퀀스 목록 지우기

시퀀스 테이블의 내용을 비어 있도록 설정합니다.
지침:

• 실제 순차 테이블은 제네릭을 저장하기 때문에 요소는 하나씩 순회할 때 비어 있도록 설정되며 아래에서는 해당 요소를 0으로 설정하여 대체됩니다.
• UsedSize도 0으로 설정됩니다.

public void clear() {
        for (int i = 0; i < usedSize; i++) {
            elem[i] = 0;
        }
        usedSize = 0;
    }
1
2
3
4
5
6

자바의 배열리스트

ArrayList 클래스는 순차 목록을 나타내기 위해 Java에서 제공됩니다.

구현된 인터페이스

인터페이스 설명:

1. RandomAccess 인터페이스는 무작위 액세스 지원을 나타냅니다.
2. Cloneable 인터페이스는 복제 지원을 나타냅니다.
3. 직렬화 가능 인터페이스는 직렬화 지원을 나타냅니다.

공법

Java는 표에 표시된 대로 3가지 구성 방법을 제공합니다.

일반적인 방법

제공되는 일반적인 방법은 위에서 구현한 것과 유사합니다.

서열 목록의 장점과 단점

이점

시퀀스 테이블의 장점은 다음과 같습니다.

1. 무작위 액세스가 지원됩니다.
2. 주어진 첨자를 쿼리하는 것은 빠릅니다.

결점

1. 공간이 부족하면 확장을 해야 하고, 메모리 낭비가 발생하게 됩니다.
2. 헤더와 중간에 삽입과 삭제를 하면 데이터가 이동됩니다.

관행

연습 링크는 다음과 같습니다.
양희삼각형