자료구조기초 (4) - 순차자료구조와 선형리스트

순차 자료구조의 개념

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

ƒ C 프로그래밍에서 순차 자료구조의 구현 방식 제공하는 프로그램 기법은 배열

 

ƒ 리스트 : 자료를 구조화하는 가장 기본적인 방법은 나열하는 것

 

 

™ 선형 리스트Linear List

ƒ 순서 리스트Ordered List

ƒ 자료들 간에 순서를 갖는 리스트

 

선형 리스트의 저장

ƒ 순차 방식으로 구현하는 선형 순차 리스트(선형 리스트)

    • 순차 자료구조는 원소를 논리적인 순서대로 메모리에 연속하여 저장

ƒ 연결 방식으로 구현하는 선형 연결 리스트(연결 리스트)

 

선형 리스트에서 원소 삽입

선형리스트 중간에 원소가 삽입되면,

그 이후의 원소들은 한 자리씩 자리를 뒤로 이동하여 물리적 순서를 논리적 순서와 일치시킴

 

순차적인게 장점이지만, 자리를 이동하는데에 시간이 걸림

 

ƒ 원소 삽입 방법

① 원소를 삽입할 빈 자리 만들기 ☞ 삽입할 자리 이후의 원소들을 한 자리씩 뒤로 자리 이동

② 준비한 빈 자리에 원소 삽입하기

ƒ 삽입할 자리를 만들기 위한 자리 이동 횟수

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

− 이동횟수 = n-k+1 = 마지막 원소의 인덱스 - 삽입할 자리의 인덱스 +1

− 예) n=5, k=2

 

선형 리스트에서 원소 삭제

ƒ 선형리스트 중간에서 원소가 삭제되면, 그 이후의 원소들은 한 자리 씩 자리를 앞으로 이동하여 물리적 순서를 논리적 순서와 일치시킴

 

ƒ 원소 삭제 방법

① 원소 삭제하기

② 삭제한 빈 자리 채우기 ☞ 삭제한 자리 이후의 원소들을 한 자리씩 앞으로 자리 이동

삭제 후, 빈 자리를 채우기 위한 자리이동 횟수

• (n+1)개의 원소로 이루어진 선형 리스트에서 k번 자리의 원소를 삭제한 경우 : (k+1)번 원소부터 마지막 n번 원소까지 (n-(k+1)+1)개의 원소를 이동

− 이동횟수 = n-(k+1)+1 = n-k = 마지막 원소 인덱스-삭제한 자리 인덱스

− 예) n=6, k=2

 

구현

 

ƒ 2차원 배열의 물리적 저장 방법

• 2차원의 논리적 순서를 1차원의 물리적 순서로 변환하는 방법 사용

• 행 우선 순서 방법row major order

− 2차원 배열의 첫 번째 인덱스인 행 번호를 기준으로 사용하는 방법

− sale[0][0]=63, sale[0][1]=84, sale[0][2]=140, sale[0][3]=130, sale[1][0]=157, sale[1][1]=209, sale[1][2]=251, sale[1][3]=312

− 원소의 위치 계산 방법 : 행의 개수가 ni 이고 열의 개수가 nj 인 2차원 배열 A[ni ][nj ]의 시작주소가 α이고 원소의 길이가 ℓ 일 때, i행 j열 원소 즉, A[i][ j]의 위치는?

α + (i x nj+j)xℓ 

 

0행 ~2행, 4열의 표

0	1	2	3
4	5	6	7
8	9	10	11

A[2][2] 의 위치는?

시작주소 : 0 

0 + ( 2 x 4 + 2) x 1 = 10

왜 1임근데?

 

 

• 열 우선 순서 방법column major order

− 2차원 배열의 마지막 인덱스인 열 번호를 기준으로 사용하는 방법

− sale[0][0]=63, sale[1][0]=157, sale[0][1]=84, sale[1][1]=209, sale[0][2]=140, sale[1][2]=251, sale[0][3]=130, sale[1][3]=312

− 원소의 위치 계산 방법 :

행의 개수가 ni 이고 열의 개수가 nj 인 2차원 배열 A[ni ][nj ]의 시작주소가 α이고

원소의 길이가 ℓ 일 때, i행 j열 원소 즉, A[i][ j]의 위치는?

α + (j ⅹ ni+ i)ⅹ ℓ 

0	1	2	3
4	5	6	7
8	9	10	11

 A[2][2]의 위치

0 + (2 * 3 + 3) *1 =? 9나오는데... 아 머라는거여

 

예) α : 0, i : 1, j : 2, ni : 2, nj : 4, ℓ : 4, A[i][j] 의 위치는 ?

0 + ( 1 * 4 + 2 ) * 4

4 바이트라서 4

 

 

ƒ 3차원 배열의 물리적 저장 방법

 

• 3차원의 논리적 순서를 1차원의 물리적 순서로 변환하는 방법 사용

• 면 우선 순서 방법

− 3차원 배열의 첫 번째 인덱스인 면 번호를 기준으로 사용하는 방법

− 원소의 위치 계산 방법 : 면의 개수가 ni 이고 행의 개수가 nj 이고, 열의 개수가 nk 인 3차원 배열 A[ni ][nj ][nk],

시작주소가 α이고 원소의 길이가 ℓ 일 때, i면 j행 k열 원소 즉, A[i][ j][k]의 위치는?

a + ((i * nj * nk) + ( j * nk) +k) *l

 

• 열 우선 순서 방법

− 3차원 배열의 마지막 인덱스인 열 번호를 기준으로 사용하는 방법

− 원소의 위치 계산 방법 : α + {(k ⅹ nj ⅹ ni ) + (j ⅹ ni ) + i}ⅹℓ

 

다항식의 선형 리스트 표현

ƒ 다항식의 개념

• aXe 형식의 항들의 합으로 구성된 식

− a : 계수(coefficient)

− X : 변수(variable)

− e : 지수(exponent)

ƒ 다항식의 특징

• 지수에 따라 내림차순으로 항을 나열

• 다항식의 차수 : 가장 큰 지수

• 다항식 항의 최대 개수 = (차수 + 1)개

 

지수가 높은 것의 계수를 순차적으로 먼저 쓰면 됨.

 

 

™ 행렬의 선형 리스트 표현

ƒ 행렬matrix의 개념

• 행과 열로 구성된 자료구조

• m×n 행렬 : 행 개수가 m개, 열 개수가 n개인 행렬

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

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

 

올~롸잇!