재 학 데이터 구조 - 분류 + 희소 배열

1. 데이터 구조의 분류
1. 데이터 구조 두 가지 유형
선형 구조 와 비 선형 구조
1) 선형 구조

선형 구 조 는 가장 흔히 볼 수 있 는 데이터 구조 로 요소 간 에 일대일 의 선형 관계 가 존재 하 는 것 이 특징 이다.

선형 구 조 는 두 가지 로 나 뉘 는데 하 나 는 순서 저장 (순서 표 라 고 함) 이 고 다른 하 나 는 체인 저장 (체인 표 라 고 함) 이다.순서 표 에 저 장 된 요소 의 연속 적 인.링크 에 저 장 된 요 소 는 반드시 연속 적 인 것 이 아니 라 요소 노드 에 데이터 요소 와 인접 요소 의 주소 정 보 를 저장 합 니 다.

흔히 볼 수 있 는 선형 구 조 는 배열, 대열, 링크 와 스 택 이다.

2) 비 선형 구조
비 선형 구 조 는 결점 요소 가 여러 개의 직접적인 전진 과 여러 개의 직접적인 후속 이 존재 할 수 있다 는 것 이다. (이 진 트 리 를 연상 하면 알 수 있 지만 비 선형 구 조 는 이 진 트 리 만 있 는 것 이 아니다.)

비 선형 구 조 는 다 차원 배열, 광의 표, 나무 구조, 그림 구 조 를 포함한다.

2. 희소 배열
1. 희소 배열 (sparse array)
1) 장면 분석
10 * 10 바둑 의 걸음 수 기록 을 실현 해 야 하 는 장면 이 있 습 니 다.그러면 가장 간단 한 것 은 2 차원 배열 int 10 을 사용 하면 되 지만 바둑판 초기 에 이 2 차원 배열 은 거의 의미 가 없 는 데 이 터 를 사용 할 수 있다.이 2 차원 배열 을 압축 할 수 있다 면 유용 한 데이터 만 기록 하 는 방법 을 찾 았 으 면 좋 겠 다.이 럴 때 는 희소 한 배열 이 도움 이 될 것 이다.
2) 희소 배열
상기 바둑판 처럼 시작 할 때 데이터 에 기 록 된 대부분의 요소 가 0 이거 나 같은 값 의 배열 일 때 희소 배열 로 이 배열 을 저장 할 수 있 습 니 다.
3) 희소 배열 의 처리 방법 은:

기록 배열 은 모두 몇 줄 몇 열 이 있 고 몇 개의 서로 다른 값

이 있 습 니까?

서로 다른 요 소 를 가 진 행렬 과 값 을 작은 규모 의 배열 에 기록 하여 프로그램의 규 모 를 축소 시킨다.

4) 예 를 들 면:
만약 에 다음 과 같은 10 * 6 의 바둑판 이 있다 면 정수 로 낙자 순 서 를 표시 하고 희소 한 배열 로 이 바둑판 을 압축 하면 오른쪽 에 표시 된다.0 줄 은 각각 줄 수, 열 수, 총 몇 개의 값 이 있 는 지 를 나타 낸다.첫 줄 부터 마지막 까지 줄 수, 열 수, 수 치 를 나타 낸다.
그 러 다 보 니 610 이 었 던 배열 이 37 로 압축 돼 메모리 공간 을 크게 절약 했다.
5) 코드 구현
사고 분석.
(1) 2 차원 배열 은 희소 배열 로 전환한다.

원본 2 차원 배열 을 옮 겨 다 니 며 효과 적 인 데 이 터 를 얻 은 갯 수 sum

희소 배열 sparseArrsum + 1

만 들 기

유효 데 이 터 를 희소 배열 sparseArr 에 하나씩 채 워 넣 기

코드 구현:

/**
*          
* 
* @param arr    
* @return     
*/
public int[][] reserveSparseArray(int[][] arr) {
    //       
    int sum = 0;
    //       
    for (int[] is : arr) {
        for (int num : is) {
            if (num != 0) {
                sum++;
            }
        }
    }
    //       
    int[][] sparseArr = new int[sum + 1][3];
    sparseArr[0][0] = arr.length;
    sparseArr[0][1] = arr[0].length;
    sparseArr[0][2] = sum;
    for (int i = 0; i < arr.length; i++) {
        for (int j = 0; j < arr[i].length; j++) {
            if (arr[i][j] != 0) {
                sparseArr[sum][0] = i;
                sparseArr[sum][1] = j;
                sparseArr[sum][2] = arr[i][j];
                sum--;
            }
        }
    }
    return sparseArr;
}

(2) 희소 배열 을 원시 배열 로 전환한다.

희소 한 배열 의 첫 번 째 줄 을 읽 고 첫 번 째 row, 두 번 째 숫자 col 을 꺼 내 2 차원 배열 shessArrrow

를 만 듭 니 다.

드문드문 배열 뒤의 몇 줄 을 옮 겨 다 니 며, 유효 치 를 원래 배열 chessArr

에 채 웁 니 다.

코드 구현:

/**
*          
* 
* @param sparseArr     
* @return    
*/
public static int[][] reserveOriginalArray(int[][] sparseArr) {
    //               
    int[][] originalArr = new int[sparseArr[0][0]][sparseArr[0][1]];
    //               
    for (int i = 1; i < sparseArr.length; i++) {
        int row = sparseArr[i][0];
        int col = sparseArr[i][1];
        int value = sparseArr[i][2];
        originalArr[row][col] = value;
    }
    return originalArr;
}

사람 이 이름 이 없 으 면 검 연습 에 전념 하 라!
좋아 하 는 친 구 는 당신 의 칭찬 을 남 길 수 있 습 니 다!