3 순차 자료구조와 선형 리스트.

Presentation on theme: "3 순차 자료구조와 선형 리스트."— Presentation transcript:

1 3 순차 자료구조와 선형 리스트

2 학습목표 내용 순차 자료구조의 개념과 특징을 알아본다. 선형 리스트의 개념과 연산을 알아본다.
C 언어를 이용해 선형 리스트의 순차 자료구조를 구현한다. 선형 리스트의 응용과 순차 자료구조 구현 방법을 알아본다. 내용 01 순차 자료구조와 선형 리스트의 이해 02 선형 리스트의 구현 03 선형 리스트의 응용 및 구현

3 1. 순차 자료구조와 선형 리스트의 이해 순차 자료구조의 개념 구현할 자료들을 논리적 순서로 메모리에 연속 저장하는 구현 방식
논리적인 순서와 물리적인 순서가 항상 일치해야 함 C 프로그래밍에서 순차 자료구조의 구현 방식 제공하는 프로그램 기 법은 배열

4 1. 순차 자료구조와 선형 리스트의 이해 선형 리스트의 표현 리스트 : 자료를 구조화하는 가장 기본적인 방법은 나열하는 것

5 1. 순차 자료구조와 선형 리스트의 이해 선형 리스트Linear List 순서 리스트Ordered List
자료들 간에 순서를 갖는 리스트

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

7 1. 순차 자료구조와 선형 리스트의 이해 선형 리스트의 저장 순차 방식으로 구현하는 선형 순차 리스트(선형 리스트)
순차 자료구조는 원소를 논리적인 순서대로 메모리에 연속하여 저장 연결 방식으로 구현하는 선형 연결 리스트(연결 리스트)

8 1. 순차 자료구조와 선형 리스트의 이해 선형 리스트에서 원소 삽입
선형리스트 중간에 원소가 삽입되면, 그 이후의 원소들은 한 자리씩 자리를 뒤로 이동하여 물리적 순서를 논리적 순서와 일치시킴

9 1. 순차 자료구조와 선형 리스트의 이해 원소 삽입 방법 원소를 삽입할 빈 자리 만들기 준비한 빈 자리에 원소 삽입하기
☞ 삽입할 자리 이후의 원소들을 한 자리씩 뒤로 자리 이동 준비한 빈 자리에 원소 삽입하기

10 1. 순차 자료구조와 선형 리스트의 이해 삽입할 자리를 만들기 위한 자리 이동 횟수
(n+1)개의 원소로 이루어진 선형 리스트에서 k번 자리에 원소를 삽입하는 경우 : k번 원소부터 마지막 인덱스 n번 원소까지 (n-k+1)개의 원소를 이동 이동횟수 = n-k+1 = 마지막 원소의 인덱스 - 삽입할 자리의 인덱스 +1

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

12 1. 순차 자료구조와 선형 리스트의 이해 원소 삭제 방법 원소 삭제하기 삭제한 빈 자리 채우기
☞ 삭제한 자리 이후의 원소들을 한자리씩 앞으로 자리 이동

13 1. 순차 자료구조와 선형 리스트의 이해 삭제 후, 빈 자리를 채우기 위한 자리이동 횟수
(n+1)개의 원소로 이루어진 선형 리스트에서 k번 자리의 원소를 삭제한 경 우 : (k+1)번 원소부터 마지막 n번 원소까지 (n-(k+1)+1)개의 원소를 이동 이동횟수 = n-(k+1)+1 = n-k = 마지막 원소의 인덱스-삭제한 자리의 인덱스

14 2. 선형 리스트의 구현 선형 리스트의 구현 순차 구조의 배열을 사용 배열 : <인덱스, 원소>의 순서쌍의 집합
배열 : <인덱스, 원소>의 순서쌍의 집합 배열의 인덱스 : 배열 원소의 순서 표현

15 2. 선형 리스트의 구현 1차원 배열을 이용한 선형 리스트 구현 1차원 배열을 이용한 구현

16 2. 선형 리스트의 구현 원소의 논리적·물리적 순서 확인하기 프로그램 : 교재 129p

17 2. 선형 리스트의 구현 실행 결과 실행 결과 확인 배열 sale의 시작 주소 : 5241668
= (2ⅹ4바이트) = 논리적인 순서대로 메모리에 연속하여 저장된 순차 구조임을 확인!

18 2. 선형 리스트의 구현 2차원 배열을 이용한 선형 리스트의 구현 2차원 배열을 이용한 구현

19 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 원소의 위치 계산 방법 : α + (iⅹnj + j)ⅹℓ 행의 개수가 ni이고 열의 개수가 nj인 2차원 배열 A[ni][nj]의 시작주소가 α이고 원소의 길이가 ℓ 일 때, i행 j열 원소 즉, A[i][j]의 위치 열 우선 순서 방법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 원소의 위치 계산 방법 : α + (jⅹni + i)ⅹℓ

20 2. 선형 리스트의 구현 2차원 논리 순서를 1차원 물리 순서로 변환

21 2. 선형 리스트의 구현 2차원 배열의 논리적·물리적 순서 확인하기 프로그램 : 교재 131p

22 2. 선형 리스트의 구현 실행 결과 실행 결과 확인 시작 주소 α= , ni=2, nj=4, i=1, j=1, ℓ=4 sale[1][2]=251의 위치 = α+ (iⅹnj+j)ⅹℓ = (1ⅹ4+2)ⅹ4 = = C 컴파일러가 행 우선 순서 방법으로 2차원 배열을 저장함을 확인!

23 2. 선형 리스트의 구현 3차원 배열을 이용한 선형 리스트의 구현 3차원 배열을 이용한 구현

24 2. 선형 리스트의 구현 3차원 배열의 물리적 저장 방법 3차원의 논리적 순서를 1차원의 물리적 순서로 변환하는 방법 사용
면 우선 순서 방법 3차원 배열의 첫 번째 인덱스인 면 번호를 기준으로 사용하는 방법 원소의 위치 계산 방법 : α + {(iⅹnjⅹnk) + (jⅹnk) + k}ⅹℓ 면의 개수가 ni이고 행의 개수가 nj이고, 열의 개수가 nk 인 3차원 배열 A[ni][nj][nk], 시작주소가 α이고 원소의 길이가 ℓ 일 때, i면 j행 k열 원소 즉, A[i][j][k]의 위치 열 우선 순서 방법 3차원 배열의 마지막 인덱스인 열 번호를 기준으로 사용하는 방법 원소의 위치 계산 방법 : α + {(kⅹnjⅹni) + (jⅹni) + i}ⅹℓ

25 2. 선형 리스트의 구현 3차원의 논리 순서에 대한 1차원의 물리 순서 변환

26 2. 선형 리스트의 구현 3차원 배열의 논리적·물리적 순서 확인하기 프로그램 : 교재 134p

27 2. 선형 리스트의 구현 실행 결과 실행 결과 확인 시작 주소 α= , ni=2, nj=2, nk=4, i=1, j=1, k=2, ℓ=4 sale[1][1][2]=239의 위치 = α+{(iⅹnjⅹnk)+(jⅹnk)+k}ⅹℓ   = {(1ⅹ2ⅹ4)+(1ⅹ4)+2}ⅹ4 = = C 컴파일러가 면 우선 순서 방법으로 3차원 배열을 저장함을 확인!

28 3. 선형 리스트의 응용 및 구현 다항식의 선형 리스트 표현 다항식의 개념 다항식의 특징
aXe 형식의 항들의 합으로 구성된 식 a : 계수(coefficient) X : 변수(variable) e : 지수(exponent) 다항식의 특징 지수에 따라 내림차순으로 항을 나열 다항식의 차수 : 가장 큰 지수 다항식 항의 최대 개수 = (차수 +1)개

29 3. 선형 리스트의 응용 및 구현 다항식의 추상 자료형(1/2)

30 3. 선형 리스트의 응용 및 구현 다항식의 추상 자료형(2/2)

31 3. 다항식의 순차 자료구조 구현 A(x) = 4x3 + 3x2 + 2
차수가 1000이므로 크기가 1001인 배열을 사용하는데, 항이 3개 뿐이므로 배열의 원소 중에서 3개만 사용 ☞ 998개의 배열 원소에 대한 메모리 공간 낭비

32 3. 다항식의 순차 자료구조 구현 다항식의 덧셈 연산

33 3. 다항식의 순차 자료구조 구현 다항식의 덧셈 연산 알고리즘

34 3. 다항식의 순차 자료구조 구현 다항식의 덧셈 연산 프로그램 : [알고리즘 3-1]의 구체화 교재 140p 예제 3-4
실행 결과

35 3. 다항식의 순차 자료구조 구현 행렬의 선형 리스트 표현 행렬matrix의 개념 행과 열로 구성된 자료구조
m×n 행렬 : 행 개수가 m개, 열 개수가 n개인 행렬 정방행렬 : 행렬 중에서 m과 n이 같은 행렬 전치행렬 : 행렬의 행과 열을 서로 바꿔 구성한 행렬

36 3. 다항식의 순차 자료구조 구현

37 3. 다항식의 순차 자료구조 구현 희소행렬Sparse Matrix은 실제로 사용하지 않는 공간이 많아 기억 공간의 활용도가 떨어짐

38 3. 다항식의 순차 자료구조 구현 희소 행렬에 대한 2차원 배열 표현
희소 행렬 B는 배열의 원소 56개 중 실제 사용하는 것은 0이 아닌 원소를 저장하는 10개뿐이므로 46개의 메모리 공간 낭비 0이 아닌 원소만 추출하여 <행번호, 열번호, 원소> 쌍으로 배열에 저장 추출한 순서쌍을 2차원 배열에 행으로 저장 원래의 행렬에 대한 정보를 순서쌍으로 작성하여 0번 행에 저장 ③ ① B[8][7] [0] [1] [2] [3] [4] [5] [6] 2 12 7 23 31 14 25 6 52 [7] 11 <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> <7, 4, 11> ②

39 3. 다항식의 순차 자료구조 구현 희소행렬 B의 2차원 배열 표현 예2
기억 공간을 좀 더 효율적으로 사용하기 위해 0이 아닌 값이 있는 원소만 따로 배열로 구성하는 방법 사용

40 3. 다항식의 순차 자료구조 구현

41 3. 다항식의 순차 자료구조 구현 희소행렬의 전치 연산 함수 프로그램 : 교재 145p

42