행렬 과 산 목록

목적: 1. 3 대각 행렬 류 를 만 들 고 열 맵 방식 으로 store 와 retrieve 방법 을 제공 합 니 다.2. 다음 삼각 행렬 류 를 만 들 고 열 맵 방식 으로 store 와 retrieve 방법 을 제공 합 니 다.3. 희소 행렬 류 를 만 들 고 줄 의 주 순서 로 희소 행렬 을 1 차원 배열 에 투사 하여 희소 행렬 의 전환 과 두 개의 희소 행렬 의 덧셈 작업 을 실현 한다.4. 산 목록 디자인 을 사용 하여 하나의 사전 을 실현 하고 키워드 가 정수 이 고 D 가 961 이 라 고 가정 하 며 사전에 무 작위 로 발생 하 는 500 개의 서로 다른 정 수 를 삽입 하여 사전 의 구축 과 검색 작업 을 실현 합 니 다.선형 개방 형 주소 지정 과 링크 해시 로 넘 침 을 해결 합 니 다.
특수 행렬 류 를 만 드 는 중점 은 행렬 의 위치 가 1 차원 배열 에 있 는 맵 방식 을 분석 하고 공식 에 따라 요소 가 저 장 된 위 치 를 계산 하 는 것 이다.먼저 n 을 비교적 작은 값 으로 가정 하고 배열 의 위치 가 행렬 내 요소 에 있 는 번 호 를 그 려 서 구 해 공식 을 가 져 올 수 있다.이번 목적 에서 우 리 는 모두 열 맵 방식 을 사용 하여 위치 가 맞지 않 으 면 MustBeZero 이상 을 던 집 니 다.3 대각 행렬: 열 주 맵 을 사용 하여 요 소 를 3 * n - 2 크기 의 배열 에 저장 합 니 다. 행렬 의 차이 가 1 보다 크 면 이상 을 던 집 니 다. 저장 할 수 있다 면 배열 의 2 * column + row - 3 위치 에 존재 합 니 다.아래 삼각 행렬: 열 주 맵 을 사용 하여 원 소 를 n * (n - 1) / 2 크기 의 배열 에 저장 합 니 다. 열 수가 줄 보다 작 으 면 이상 을 던 집 니 다. 저장 할 수 있 으 면 배열 에 column * (2 * n - column + 1) / 2 - (n - row) - 1 의 위치 에 저장 합 니 다.
희소 행렬 은 행렬 의 대부분 요소 가 0 인 행렬 로 사용자 정의 형식 으로 요 소 를 저장 합 니 다.

template<class T>
class Term
{
    friend SparseMatrix;
private:
    int row, column;
    T value;
};

저장 할 때 줄 의 주 맵 을 사용 하여 요소 의 줄, 열, 값 을 저장 합 니 다. 줄 수가 작은 것 은 앞 에 있 고 줄 수가 같은 열 수가 작은 것 은 앞 에 있 습 니 다.
리 셋 할 때 두 개의 배열 을 설정 합 니 다. 하 나 는 (ColSize) 각 열의 요소 수량 을 기록 하고 다른 하 나 는 (Row Next) 요소 수량 으로 계 산 된 각 줄 의 시작 위 치 를 기록 한 다음 에 행렬 의 모든 요 소 를 해당 하 는 열 순서에 따라 새 행렬 의 줄 위 에 놓 고 요소 의 줄 과 열 을 교환 하여 저장 합 니 다. 각 요 소 를 놓 을 때마다 해당 하 는 줄 의 시작 위치 (Row Next) 를 설정 합 니 다.모든 요 소 를 새 행렬 에 넣 을 때 까지 하나만 더 하 세 요.

template<class T>
void SparseMatrix::Transpose(SparseMatrix& b) const
{// *this    ，         b 
    if (terms > b.MaxTerms) throw NoMem();

    b.rows = columns;
    b.columns = rows;
    b.terms = terms;

    int *ColSize, *RowNext;
    ColSize = new int[columns + 1];
    RowNext = new int[columns + 1];

    //          
    for (int i = 1; i <= columns; i++)
        ColSize[i] = 0;
    for (int i = 0; i < terms; i++)
        ColSize[a[i].column]++;

    //          
    RowNext[1] = 0;
    for (int i = 2; i <= columns; i++)
        RowNext[i] = RowNext[i - 1] + ColSize[i - 1];

    for (int i = 0; i < terms; i++) {
        int j = RowNext[a[i].column]; //b a[i]   ,a Term   
        RowNext[a[i].column]++;
        b.a[j].column = a[i].row;
        b.a[j].row = a[i].column;
        b.a[j].value = a[i].value;
    }

    delete[] ColSize;
    delete[] RowNext;
}

행렬 덧셈 은 먼저 두 행렬 이 같은 열 에 있 는 지 확인 하고 이상 을 던 지 는 것 이 아니 라 두 개의 포인터 가 두 개의 행렬 을 가리 키 는 첫 번 째 요 소 를 설정 합 니 다.두 포인터 가 가리 키 는 위치의 줄 주 색인 값 을 각각 계산 하고 색인 값 을 작은 추가 로 새 행렬 의 마지막 에 놓 고 해당 지침 을 뒤로 이동 합 니 다.같 으 면 0 이 아 닌 경우 새 행렬 의 마지막 에 추가 하고 0 이 되면 요 소 를 추가 하지 않 으 며 두 개의 포인터 가 두 행렬 의 데 이 터 를 추가 할 때 까지 뒤로 이동 합 니 다.

template
void SparseMatrix::Add(const SparseMatrix& b, SparseMatrix& c) const
{// *this b  ，       c 
    if (rows != b.rows || columns != b.columns)
        throw SizeMismatch();   //     

    //    c   
    c.rows = rows;
    c.columns = columns;
    c.terms = 0; //     

    //   *this b   
    int ct = 0, cb = 0;

    //  *this b   
    while (ct < terms && cb < b.terms) {
        //         
        int it = a[ct].row * columns + a[ct].column;
        int ib = b.a[cb].row * columns + b.a[cb].column;

        if (it < ib) {
            c.Append(a[ct]);
            ct++;
        }
        else if (it == ib) {
            if (a[ct].value + b.a[cb].value) { 
                //      0，   c  
                Term temp;
                temp.column = a[ct].column;
                temp.row = a[ct].row;
                temp.value = a[ct].value + b.a[cb].value;
                c.Append(temp);
            }
            ct++;
            cb++;
        }
        else {
            c.Append(b.a[cb]);
            cb++;
        }
    }

    for (; ct < terms; ct++)
        c.Append(a[ct]);
    for (; cb < b.terms; cb++)
        c.Append(b.a[cb]);
}

산 목록: 선형 주소 지정 표 는 배열 을 통 해 요 소 를 저장 합 니 다.저장 할 때 모 하 시 함수 의 나머지 위 치 를 찾 습 니 다. 위치 가 비어 있 으 면 바로 저장 합 니 다. 위치 가 비어 있 지 않 으 면 선형 으로 빈 자 리 를 찾 습 니 다. 찾 으 면 요 소 를 빈 자리 에 저장 합 니 다. 최초의 위 치 를 계속 찾 았 는데 빈 자 리 를 찾 지 못 하면 표 가 가득 차 서 이상 을 던 집 니 다.찾 을 때 모 하 시 함수 의 나머지 위 치 를 찾 습 니 다. 위치 가 비어 있 으 면 찾 을 수 없습니다. 위치 에 이 요소 가 없 으 면 뒤로 찾 습 니 다. 빈 자 리 를 찾 으 면 요소 가 산 목록 에 저장 되 지 않 았 음 을 설명 합 니 다. 설명 요 소 를 찾 으 면 산 목록 에 저장 되 었 습 니 다.링크 가 실 현 된 해시 표 는 링크 를 통 해 요 소 를 저장 합 니 다.저장 할 때 모 하 시 함수 의 나머지 위치 에 있 는 링크 에 삽입 을 시도 합 니 다. 이상 을 찾 을 수 있다 면 키 값 이 큰 요소 앞 에 저장 할 수 없습니다.찾 을 때 모 하 시 함수 의 나머지 위 치 를 나 누 는 링크 에서 직접 검색 합 니 다. 흩 어 진 목록 에 없다 는 설명 을 찾 지 못 하면.삽입 시 rand () 함 수 를 사용 하여 무 작위 수 를 생 성 합 니 다. 데이터 가 중복 되 었 을 때 이상 을 포착 하고 다시 무 작위 수 를 생 성 합 니 다. 500 개의 무 작위 수가 들 어 갈 때 까지.
소스 코드: MatrixAndHashTable. zip