[SOS CLASS] 자료구조기초 - 3차시

 

---

✅ 오늘의 진도 (2022/04/09)

1. 순차 자료구조와 선형 리스트의 이해

- 순차 자료구조 VS 연결자료구조

- 선형 리스트의 원소 삽입

- 선형 리스트의 원소 삭제

 

2. 선형 리스트의 구현

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

- 행 우선 순서 방법

- 열 우선 순서 방법

 

3. 선형 리스트의 응용 및 구현

- 다항식의 선형 리스트 표현

- 행렬의 선형 리스트 표현

---

 ✅ 순차 자료구조 VS 연결 자료구조

---

✅ 선형 리스트에서 원소 삽입

선형୉리스트  중간에 원소가 삽입되면, 그 이후의 원소들은 한 자리씩 뒤로 이동

(물리적 순서 == 논리적 순서)

 

1. 원소를 삽입할 빈 자리 생성

2. 삽입할 자리 이후의 원소들을 한 칸씩 뒤로 이동

3. 빈 자리에 원소 삽입

 

⚡ 이동횟수 = n-k+1 = 마지막 원소의 인덱스 - 삽입할 자리의 인덱스 + 1
예) n=5, k=2 ⏩ 4

---

✅ 선형 리스트에서 원소 삭제

선형୉리스트  중간에 원소가 삭제되면, 그 이후의 원소들은 한 자리씩 앞으로 이동

(물리적 순서 == 논리적 순서)

 

1. 원소 삭제하기

2. 삭제한 자리 이후의 원소들을 한 칸씩 앞으로 이동

 

⚡ 이동횟수 = n-(k+1)+1 = n-k = 마지막 원소의 인덱스 - 삭제한 자리의 인덱스
예) n=6, k=2 ⏩ 4

---

✅ 선형 리스트의 구현

⚡ 리스트

 

⚡ 2차원 배열을 이용한 구현

int sale[][4] = { {63, 84, 140, 130}, {157, 209, 251, 312} };

 

⚡ 논리적 구조

 

⚡ 물리적 구조

 

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

 

1. 행 우선 순서 방법

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

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

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

 α + (i * nj + j) * ℓ 

 

2. 열 우선 순서 방법

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

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

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

 α + (j * ni + i) * ℓ 

 

3. 예시 - 251

1) 행 우선 순서 방법

 α + (i * nj + j) * ℓ  = 0 + (1 * 4 + 2) * 4 =  24

 

2) 열 우선 순서 방법

 α + (j * ni + i) * ℓ  = 0 + (2 * 2 + 1) * 4 = 20

 

 

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

 

1. 면 우선 순서 방법

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

면의 개수가 ni 이고, 행의 개수가 nj이고, 열의 개수가 nk 인 3차원 배열 A[ni][nj][nk],

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

 α + {(i * nj + * nk) + ( j * nk ) + k} * ℓ 

 

2. 열 우선 순서 방법

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

α + {(k ⅹ nj ⅹ ni) + (j ⅹ ni) + i}ⅹℓ

 

3. 예시 - 239

1) 면 우선 순서 방법

 α + {(i * nj + * nk) + ( j * nk ) + k} * ℓ = 56

 

2) 열 우선 순서 방법

α + {(k ⅹ nj ⅹ ni) + (j ⅹ ni) + i}ⅹℓ

= 0 + {(2 * 2 * 2) + (1 * 2) + 1} * 4

= 44

 

---

✅ 선형 리스트의 응용 및 구현

⚡ 다항식의 선형 리스트 표현

ex) A(x) = 4x^3 + 3x^2 + 2 

 

단점: 최고 차항에 맞춰 칸을 준비해야 하므로 메모리 공간 낭비가 심함

 

⚡ 행렬의 선형 리스트 표현

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

단점 : 희소행렬은 실제로 사용하지 않는 공간이 많아 기억공간의 활용도가 떨어짐 

 

1. 희소행렬 => 전체 행의 개수 / 전체 열의 개수 / 0이 아닌 원소의 개수

 

2. 희소행렬의 전치

---

✅ 오늘의 과제

 

SOS CLASS 자료구조기초 - 3차시 과제 .hwp

0.03MB