선형 자료구조 순차리스트

선형 자료 구조에서는 순차 리스트(선형리스트와 배열)와 연결리스트가 있다 두개는 서로 각각의 장단점을 가지고 있다

 

순차리스트

순차리스트란 구현할 자료들을 논리적 순서로 메모리에 연속 저장하는 방식

순차리스트에서는 원소를 삽입하거나 삭제를 한다면 그 앞뒤에 있는 모든 원소들이 이동을 해야한다

 

삽입: 선형 리스트에서 k번째 원소를 삽입하는 경우 k번 원소부터 마지막 인덱스 n번 원소까지 (n-k+1)개의 원소 이동

삭제: 마지막 원소의 인덱스 - 삭제한 자리의 인덱스 = n-(k+1) +1 = n-k

 

순차 리스트의 구현

순차구조의 배열을 사용한다

#include<stdio.h>
void main() {
  int i =0;
  int list[4] = {12,54,78,55};
  for (i = 0; i<4; i++) {
    printf("address %u list[%d]=%d",&list[i],i,list[i]);
  }
}

주소는 시작 주소+4byte 이므로 첫 주고 +4가되는 것을 알 수 있고 논리적 순서대로 메모리에 연속 저장된다

2차원 배열일때는 행 우선 순서 방법으로 2차원 배열을 저장한다

 

행렬의 순차 리스트 표현

m x n행렬: m 행 n 열

정방 행렬: 행렬중 m과n이 같은 행렬

전치 행렬: 행렬의 행과 열을 서로 바꿔서 구성한 행렬

희소 행렬: 행렬에서 0이 많은 행렬 -> 사용하지 않는 공간이 많음

위 같은 행렬이 있다면 0이 많아서 효율성이 떨어진다 따라서 2차원 배열로 표현할 수 있다

(전체행)8	(전체열)7	(저장된 값)10
0	2	2
0	6	12
1	4	7
2	0	23
3	3	31
4	1	14
4	5	25
5	6	6
6	0	52
8	4	11

 

희소 행렬(행->열 순서로 정렬됨)을 전치 연산하기

일반적으로 행열만 바꾸면 가능하지만 정렬이 안되어 있다

#include<stdio.h>

typedef struct _term {
  int row;
  int col;
  int value;
} term;

void smTranspose(term a[],term b[]){
  //
  int m,n,v,i,j,p;
  m = a[0].row;
  n = a[0].col;
  v = a[0].value;
  b[0].row = n;
  b[0].col = m;
  b[0].value = v; 
  // 맨위 값으로 행렬의 크기를 바꾸는것

  if (v>0) { //값이 0이 아닌경우 전치연산 수행
    p = 1;
    for (i=0;i<n;i++){
      for (j=0;j<=v;j++){
        if (a[j].col ==i){
          b[p].row = a[j].col;
          b[p].col = a[j].row;
          b[p].value = a[j].value;
          p++;
        }
      }
    }
  }
  for (i = 0;i<6;i++){
    printf("%drow %dcol %dvlaue\n",b[i].row, b[i].col, b[i].value);
  }
  printf("============\n");
  for (i = 0;i<6;i++){
    printf("%drow %dcol %dvlaue\n",a[i].row, a[i].col, a[i].value);
  }
}

int main() {
  term term1[6] = \{\{3,3,5},{0,1,1},{0,2,4},{1,0,3},{2,0,5},{2,1,2}\}\;//희소 행렬
  term term2[6]; //새로 저장될 공간
  smTranspose(term1,term2);

}

위 알고리즘의 시간 복잡도는 O(col * col * row)이다

더 빠른 알고리즘이 존재한다

#include<stdio.h>

#define MAX_COL 6

typedef struct _term {
  int row;
  int col;
  int value;
} term;

void fast_transpose(term a[],term b[]){
    int row_terms[MAX_COL];
    int starting_pos[MAX_COL];
    int i, j, num_cols = a[0].col, num_terms = a[0].value;
    b[0].row = num_cols; b[0].col = a[0].value;
    b[0].value = num_terms;
    if(num_terms > 0) {
        for (i =0;i<num_cols;i++)
            row_terms[i]=0;
        for (i = 1;i<=num_terms; i++){
            row_terms[a[i].col]++;
        }
        starting_pos[0]=1;
        for(i=1;i<num_cols;i++)
            starting_pos[i]=starting_pos[i-1]+row_terms[i-1];
        for(i=0;i<=num_terms;i++){
            j = starting_pos[a[i].col]++;
            b[j].row = a[i].col;
            b[j].col = a[i].row;
            b[j].value = a[i].value;
        }
    }
    for (i = 0;i<6;i++){
        printf("%drow %dcol %dvlaue\n",a[i].row, a[i].col, a[i].value);
    }
    printf("============\n");
    for (i = 0;i<6;i++){
    printf("%drow %dcol %dvlaue\n",b[i].row, b[i].col, b[i].value);
    }
    
    
}
int main() {
  term term1[6] = \{\{3,3,5},{0,1,1},{0,2,4},{1,0,3},{2,0,5},{2,1,2\}\};
  term term2[6];
  fast_transpose(term1,term2);

}

해당 알고리즘은 O(col * row)이다

 

 

	순차 리스트	연결 리스트
메모리 저장 방식	메모리의 저장 시작 위치부터 빈자리 없이 자료를 순서대로 연속해서 저장 논리적 물리적 순서가 일치	메모리에 저장된 물리적 순서나 위치에 상관 없이 순서를 표현한 방식
연산 특징	삽입 삭제 연산을 해도 빈자리 없이 유지해야한다	논리적 순서가 변경되어도 링크만 변경되고 믈리적 순서는 변경되지 않는다
구현	배열을 이용한 구현	포인터를 이용한 구현