자료구조
1. 자료구조 개요 및 분류
1) 자료구조란?
자료를 효율적으로 사용하기 위해서 자료의 특성에 따라서 분류하여 구성하고 저장 및 처리하는 모든 작업
2) 컴퓨터 분야에서 자료구조를 왜 배워야 하는가?
- 컴퓨터가 효율적으로 문제를 처리하기 위해서는 문제를 정의하고 분석하여 그에 대한 최적의 프로그램을 작성해야 함
- 자료구조에 대한 개념과 활용 능력 필요!
graph LR
subgraph 문제 도출 단계<br>
A[문제정의]
end
subgraph 문제 변환 단계
A --> B[처리방식<br>결정]
B --> C[알로리즘<br>작성]
C --> D[프로그램<br>작성]
A --> E[처리대상<br>결정]
E --> F[자료정의]
F --> D
end
subgraph 실행 단계
D --> G[프로그램<br>번역 및 실행]
G --> H[실행<br>결과]
end
subgraph 결과 분석 단계
H --> I[문제<br>해답]
end각 단계별 처리자
실행단계만 컴퓨터이다. 나머지는 사람
3) 자료구조에서 다루는 내용
- 자료구조는 이론적인 측면과 실제적인 측면을 모두 다루어야 함
- 성공적인 시스템을 개발하는 고급 개발자가 되기 위해서는 자료의 특성을 이해하고 분석하여 최적의 알고리즘을 개발하는 능력이 필요
자료구조의 내용
graph TD
A[이론적인 측면] --- B[그래프이론]
A --- C[집합이론]
A --- D[조합적 분석]
A --- E[확률이론]
B --- F[이산수학]
C --- F
D --- F
F --- G[알고리즘 분석]
E --- G
G --- H[검색]
G --- I[정렬]
G --- J[효울 분석]
J --- K[공간적 효율성]
J --- L[시간적 효율성]
M[실제적인 측면] --- N[문자열]
M --- O[리스트]
M --- P[트리]
M --- Q[파일]
N --- R[알고리즘의 구현]
O --- R
P --- R
Q --- R
R --- S[응용]
S --- T[프로그래밍]
S --- U[파일작성]
S --- V[메모리관리]
S --- W[운영체제]4) 자료구조의 분류
자료의 형태에 따른 분류
표현할 자료의 특서오가 양, 자료의 주된 사용 방법과 수행하는 연산의 조류, 구현에 필요한 기억 공간 요량을 고려하여 가장 효율적인 자료구조를 선택해야 함
단순구조
- 정수, 실수, 문자, 문자열 등의 기본 자료형
선형구조
- 자료들 간의 앞뒤 관계가 1:1의 선형 관계
- 리스트, 연결 리스트, 스택, 큐, 덱 등
비선형 구조
- 자료들 간의 앞뒤 관계가 ‘1:다’, 또는 ‘다:다’의 관계
- 트리그래프등
파일구조
- 레코드의 집합인 파일에 대한 구조
- 순차파일, 색인 파일, 직접파일 등
graph TD
A[자료구조] --- B[단순구조]
A --- C[선형구조]
A --- D[비선형 구조]
A --- E[파일구조]
B --- F[정수];
B --- G[실수]
B --- H[문자]
B --- I[문자열]
C --- J[순차 리스트]
C --- K[연결 리스트]
C --- L[큐]
C --- M[덱]
D --- N[트리]
D --- O[그래프]
E --- P[순차 파일]
E --- Q[색인 파일]
E --- R[직접 파일]
K --- S[단순 연결 리스트]
K --- T[이중 연결 리스트]
K --- U[원형 연결 리스트]
N --- V[일반 트리]
N --- W[이진 트리]
O --- X[방향 그래프]
O --- Y[무방향 그래프]2. 자료의 표현 (1)
1) 디지털 시스템에서의 자료 표현
숫자, 문자, 그림, 소리, 기호 등 모든 형식의 자료를 2진수 코드로 표현하여 저장 및 처리
2진수 코드란?
- 1과 0, On과 Off, 참(True)과 거짓(False)의 조합
2진수 코드의 단위
1 비트bit
4 비트 = 1니블(nibble)
8 비트 = 2니블(nibble) = 1바이트(byte)
n개의 비트로 \(2^n\) 개의 상태 수 표현
n = 2인 경우
4개 (\(2^n= 2^2 = 4\))
n = 4인 경우
16개 (\(2^n= 2^4 = 16\))
2) 컴퓨터 내부에서 표현할 수 있는 자료의 종류
graph TD
A[자료의 표현] --- B[수치 자료]
A --- C[문자 자료]
A --- D[논의 자료]
A --- E[포인터 자료]
A --- F[문자열 자료]
B --- G[10진수]
B --- H[2진수]
C --- I[BCD 코드]
C --- J[EBCDIC 코드]
C --- K[ASCII 코드]
G --- L[존 형식]
G --- M[팩 형식]
H --- N[정수]
H --- O[실수]
N --- P[부호 절대값]
N --- Q[1의 보수]
N --- R[2의 보수]
O --- S[고정 소수점]
O --- T[부동 소수점]3) 수치 자료의 표현
10진수의 표현
존(Zone) 형식의 표현
- 10진수 한 자리를 표현하기 위해서 1바이트(8비트)를 사용하는 형식
- 존 영역
- 상위 4비트로 항상 1111로 표현
- 수치영역
- 하위 4비트
- 표현하고자 하는 10진수 한 자리 값에 대한 2진수 값을 표시
- 0에서 15까지의 두 자릿수는 A에서 F까지의 문자를 사용
존형식의 구조
│ 존 영역 │ 수치영역 │
├―――――――――――――――――――――――――――――――┤
│ 1 │ 1 │ 1 │ 1 │ 8 │ 4 │ 2 │ 1 │
└―――――――――――――――――――――――――――――――┘
4비트의 2진수에 대한 10진수 표현
| 4비트의 2진수 | 10진수로 변환 | 10진수 |
|---|---|---|
| 0 0 0 0 | 0 * 8 + 0 * 4 + 0 * 2 + 0 * 1 | 0 |
| 0 0 0 1 | 0 * 8 + 0 * 4 + 0 * 2 + 1 * 1 | 1 |
| 0 0 1 0 | 0 * 8 + 0 * 4 + 1 * 2 + 0 * 1 | 2 |
| 0 0 1 1 | 0 * 8 + 0 * 4 + 1 * 2 + 1 * 1 | 3 |
| 0 1 0 0 | 0 * 8 + 1 * 4 + 0 * 2 + 0 * 1 | 4 |
| 0 1 0 1 | 0 * 8 + 1 * 4 + 0 * 2 + 1 * 1 | 5 |
| 0 1 1 0 | 0 * 8 + 1 * 4 + 1 * 2 + 0 * 1 | 6 |
| 0 1 1 1 | 0 * 8 + 1 * 4 + 1 * 2 + 1 * 1 | 7 |
| 1 0 0 0 | 1 * 8 + 0 * 4 + 0 * 2 + 0 * 1 | 8 |
| 1 0 0 1 | 1 * 8 + 0 * 4 + 0 * 2 + 1 * 1 | 9 |
| 1 0 1 1 | 1 * 8 + 0 * 4 + 1 * 2 + 1 * 1 | 11 = B |
| 1 1 0 0 | 1 * 8 + 1 * 4 + 0 * 2 + 0 * 1 | 12 = C |
| 1 1 0 1 | 1 * 8 + 1 * 4 + 0 * 2 + 1 * 1 | 13 = D |
| 1 1 1 0 | 1 * 8 + 1 * 4 + 1 * 2 + 0 * 1 | 14 = E |
| 1 1 1 1 | 1 * 8 + 1 * 4 + 1 * 2 + 1 * 1 | 15 = F |
여러 자리의 10진수를 표현하는 방법
- 10진수의 자릿수만큼 존 형식을 연결하여 사용
- 예, 100단위의 경우 3개의 존 사용
- 마지막자리의존영역에부호를표시
- 양수(+): 1100 = C
- 음수(-): 1101 = D
- 단점:기억공간의낭비와처리지연
존 형식의 10진수 표현 형식
상위비트 하위비트
│<- 1바이트 -> │ │<- 1바이트 -> │
├――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――┤
│ 1111 │ d │ 1111 │ d │ ... │ 1111 │ d │ S │ d │
└――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――┘
d: 10진수 숫자 S: 부호 (1) 양수(+)일경우: 1100 = C
부호 (2) 음수(-)일경우: 1101 = D
존 형식으로 10 진수를 표현하는 예
-
+213
-
-213
팩(Pack) 형식의 표현
- 10진수 한 자리를 표현하기 위해서 존 영역 없이 4비트를사용하는 형식
- 1 바이트에 10진수 2자리 표현
- 최하위 4비트에 부호를 표시
- 양수(+) : 1100 = C
- 음수(-) : 1101 = D
팩 형식의 10진수 표현 형식
상위비트 하위비트
│<- 1바이트 -> │ │ <- 1바이트 -> │
├―――――――――――――┴――――――――――――――――――――――――――――――――――――――――┴―――――――――――――――┤
│ d │ d │ d │ d │ ... │ d │ d │ d │ S │
└――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――┘
d: 10진수 숫자 S: 부호 (1) 양수(+)일경우: 1100 = C
부호 (2) 음수(-)일경우: 1101 = D
팩 형식으로 10 진수를 표현하는 예
-
+213
-
-213
2진수의 정수 표현
n 비트의 부호 쩔대값 형식
- 최상위 1비트: 부호 표시
- 양수(+): 0
- 음수(-): 1
- 나머지 n-1 비트: 이진수 표시
1바이트를 사용하는 부호 절대값 형식의 예
+ 21 - 21
│ 1비트 │ <- 7 비트 -> │ │ 1비트 │ <- 7 비트 -> │
├――――――┴―――――――――――――――――――――――――――――┤ ├――――――┴―――――――――――――――――――――――――――――┤
│ 0 │ 0 │ 0 │ 1 │ 0 │ 1 │ 0 │ 1 │ │ 1 │ 0 │ 0 │ 1 │ 0 │ 1 │ 0 │ 1 │
├――――――――――――――――――――――――――――――――――――┤ ├――――――――――――――――――――――――――――――――――――┤
│ 부호 │ 절대값 = 21 │ │ 부호 │ 절대값 = 21 │
1의 보수(1’ Complement) 형식
- 양수(+)는 부호 절대값 형식으로 표현
- 음수(-)는 부호 비트를 사용하는 대신 1의 보수를 사용하여 표현
n비트의 2진수를 1의 보수로 만드는 방법
- n비트를 모두 1로 만든 이진수에서 변환하고자 하는 절대값을 뺀다
- 예) -21을 1의 보수로 만들기(1바이트 사용)
1 1 1 1 1 1 1 1
- 0 0 0 1 0 1 0 1 <- -21 의 절대값
---------------------------------------
1 1 1 0 1 0 1 0 <- 21의 1의 보수 = -21
1바이트를 사용하는 1의 보수 형식의 예
+ 21 - 21
┌―――――――――――――――――――――――――――――――┐ ┌―――――――――――――――――――――――――――――――┐
│ 0 │ 0 │ 0 │ 1 │ 0 │ 1 │ 0 │ 1 │ │ 1 │ 0 │ 0 │ 1 │ 0 │ 1 │ 0 │ 1 │
├―――――――――――――――――――――――――――――――┤ ├―――――――――――――――――――――――――――――――┤
│ 부 │ <- 21 의 절대값 -> │ │ 부 │ │
│ 호 │ │ 호 │
양수(+)의 경우 부호절대값형식의 표현과 같음!
2의 보수(2’ Complement) 형식
- 양수(+)의 경우 부호 절대값 형식과 같음
- 음수(-)의 경우 부호 비트를 사용하는 대신 2의 보수를 사용하는 방법
n비트의 2진수를 2의 보수로 만드는 방법
- 1의 보수에 1을 더해준다
- 예) -21을 2의 보수로 만들기(1바이트 사용)
1 1 1 1 1 1 1 1
- 0 0 0 1 0 1 0 1 <- -21 의 절대값
---------------------------------------
1 1 1 0 1 0 1 0 <- 21의 1의 보수 = -21
+ 1
1 1 1 0 1 0 1 1 <- 21의 2의 보수 = -21
1바이트를 사용하는 2의 보수 형식의 예
+ 21 - 21
┌―――――――――――――――――――――――――――――――┐ ┌―――――――――――――――――――――――――――――――┐
│ 0 │ 0 │ 0 │ 1 │ 0 │ 1 │ 0 │ 1 │ │ 1 │ 1 │ 1 │ 0 │ 1 │ 0 │ 1 │ 1 │
├―――――――――――――――――――――――――――――――┤ ├―――――――――――――――――――――――――――――――┤
│ 부 │ <- 21 의 절대값 -> │ │ 부 │ │
│ 호 │ │ 호 │
양수(+)의 경우 부호절대값형식의 표현과 같음!
2진수 정수의 세 가지 표현 방법에서 양수의 표현은 같고 음수의 표현만 다름
2의 보수 연산의 예 : -8과 12의 덧셈
12의 이진수 표현 0000 1100
-8의 이진수 표현 1000 1000
1111 1111
0000 0000
---------
-8의 1의 보수 표현 1111 0111
1
---------
-8의 2의 보수 표현 1000 1000
12의 이진수 표현 0000 1100
---------
-8과 12의 덧셈 결과 0000 0100
2진수의 정수 표현 정리
| 구분 | 내용 |
|---|---|
| 부호 절대값 형식 |
- 음수 표현은 부호비트만 다르게 표현하여 편리해 보임 - 부호와 절대값을 따로 구분해야 처리해야 함 - 덧셈 연산기와 뺄셈 연산기를 따로 구현해야 함 - 실제로 사용하지 않음 |
| 1의 보수 형식 |
- 부호와 절대값을 따로 계산하지 않아도 됨 - 뺄셈 연산기를 따로 구현할 필요 없음 -양수0(00000000)과 음수0(11111111)이 존재하여 논리적 오류 발생 |
| 2의 보수 형식 |
- 음수0을제거하여덧셈연산에대한처리를단순화시킴 - 컴퓨터 시스템에서 실제로 사용하는 표현 방식 |
3진수의 실수 표현
정수와 실수의 차이점은 소수점의 유무
고정 소수점 표현
- 소수점이항상최상위비트의왼쪽밖에고정되어있는것으로 취급하는 방법
- 고정 소수점 표현의 00010101은 0.00010101(0.21)의 실수 값을 의미
-
부동 소수점 형식의 표현
-
고정 소수점 형식에 비해서 표현 가능한 값의 범위가 넓음
- 부호, 지수, 소수로 구분하여 표현
부동 소수점 형식의 표현(계속)
- 일반적으로 컴퓨터에서는 4바이트 또는 8바이트로 표현
4바이트를 사용하는 부동 소수점 형식
│ 1비트 │ <- 7비트 -> │ <- 24비트(3바이트) ->│
├――――――┴――――――――――――┴―――――――――――――――――――┤
| 31 | 30 ... 24 | 23 ... 0 |
| 부호 | 지수부 | 소수부 |
└――――――┴――――――――――――┴―――――――――――――――――――┘
- 양수: 0
- 음수: 1
3. 자료의 표현
1) 문자 자료의 표현
- 컴퓨터 상에서는 문자 자료도 1과 0의 2진수 조합으로 표현
- 문자에 대해 2진 코드를 정의해 놓은 문자 코드를 사용
- BCD 코드
- EBCDIC 코드
- ASCII 코드
BCD(Binary-Coded Decimal) 코드
6비트를 사용하여 문자 표현
- 상위 2비트 : 존(zone) 비트
- 하위 4비트 : 숫자 비트
- 존 비트와 숫자 비트를 조합하여 10진수 0~9와 영어 대문자, 특수 문자를 표현
│ 존비트 │ <- 숫자 비트 ->│
├――――――――┴―――――――――――――――┤
| A | B | 8 | 4 | 2 | 1 |
└――――┴―――┴―――┴―――┴―――┴―――┘
존 비트 AB 의 값
00: 0, 1~9 (1010, 0001~1001)
01: 문자 A~I (0001 ~ 1001)
10: 문자 J~R (0001 ~ 1001)
11: 문자 S~Z (0010 ~ 1001)
BCD 코드표
- 예) 영문자 A에 대한 BCD 코드 -> 010001
| 존 비트 |
숫자 비트 |
표현 문자 |
존 비트 |
숫자 비트 |
표현 문자 |
존 비트 |
숫자 비트 |
표현 문자 |
|---|---|---|---|---|---|---|---|---|
| 0 0 | 0 0 0 0 | 1 | 0 1 | 0 0 0 0 | A | |||
| 0 0 | 0 0 1 0 | 2 | 0 1 | 0 0 1 0 | B | 1 1 | 0 0 1 0 | S |
| 0 0 | 0 0 1 1 | 3 | 0 1 | 0 0 1 1 | C | 1 1 | 0 0 1 1 | T |
| 0 0 | 0 1 0 0 | 4 | 0 1 | 0 1 0 0 | D | 1 1 | 0 1 0 0 | U |
| 0 0 | 0 1 0 1 | 5 | 0 1 | 0 1 0 1 | E | 1 1 | 0 1 0 1 | V |
| 0 0 | 0 1 1 0 | 6 | 0 1 | 0 1 1 0 | F | 1 1 | 0 1 1 0 | W |
| 0 0 | 0 1 1 1 | 7 | 0 1 | 0 1 1 1 | G | 1 1 | 0 1 1 1 | X |
| 0 0 | 1 0 0 0 | 8 | 0 1 | 1 0 0 0 | H | 1 1 | 1 0 0 0 | Y |
| 0 0 | 1 0 0 1 | 9 | 0 1 | 1 0 0 1 | I | 1 1 | 1 0 0 1 | Z |
| 0 0 | 1 0 1 0 |
EBCDIC (Extended Binary-Coded Decimal Interchange Code)
IBM에서 8비트를 사용하여 개발한 문자 표현 코드
- 상위 4비트 : 존 비트
- 하위4비트:숫자비트
- 존 비트와 숫자 비트를 조합하여 10진수 0~9와 영어 대문자/소문자, 특수문자를 표현
│<-존비트->│ <- 숫자 비트 -> │
├――――――――┴―――――――――――――――――――――――┤
| A | B | C | E | 8 | 4 | 2 | 1 |
└――――┴―――┴―――┴―――┴―――┴―――┴―――┴―――┘
존 비트 AB의 값 존 비트 CD의 값
00: 여분 00: 문자 A~I(0001 ~ 1001)
01: 특수문자 01: 문자 J~R(0001 ~ 1001)
10: 영어 소문자 10: 문자 S~Z(0010 ~ 1001)
11: 영어 대문자 11: 0~9 (0000 ~ 1001)
EBCDIC 코드표
- 예) 영문 대문자 ‘A’ 에 대한 EBCDIC 코드 -> 11000001
| 0000 | 0001 | 0010 | 0011 | 0100 | 0101 | 0110 | 0111 | 1000 | 1001 | 1010 | 1011 | 1100 | 1101 | 1110 | 1111 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0000 | NUL | DLE | DS | SP | & | - | { | } | (\) | 0 | ||||||
| 0001 | SCH | DC1 | SOS | / | a | j | ~ | A | J | 1 | ||||||
| 0010 | STX | DC2 | FS | SYN | b | k | s | B | K | S | 2 | |||||
| 0011 | ETX | TM | c | l | t | C | L | T | 3 | |||||||
| 0100 | RF | RES | BYP | PN | d | m | u | D | M | U | 4 | |||||
| 0101 | HT | NL | LF | RS | e | n | v | E | N | V | 5 | |||||
| 0110 | LC | BS | ETB | UC | f | o | w | F | O | W | 6 | |||||
| 0111 | DEL | IL | ESC | EOT | g | p | x | G | P | X | 7 | |||||
| 1000 | GE | CAN | h | q | y | H | Q | Y | 8 | |||||||
| 1001 | RLF | EM | i | r | z | I | R | Z | 9 | |||||||
| 1010 | SMM | CC | SM | ¢ | ! | : | ||||||||||
| 1011 | VT | CU1 | CU2 | CU3 | , | $ | , | # | ||||||||
| 1100 | FF | IFS | DC4 | < | * | % | @ | |||||||||
| 1101 | CR | IGS | ENQ | NAK | ( | ) | _ | ' | ||||||||
| 1110 | SO | IRS | ACK | + | ; | > | = | |||||||||
| 1111 | SI | IUS | BEL | SUB | | | ¬ | ? | " |
ASCII (American Standard Code for Information Interchange)
7비트를 사용하여 문자 표현
- 상위 3비트: 존 비트
- 하위4비트: 숫자비트
- 존 비트와 숫자 비트를 조합하여 10진수 0~9와 영어 대문자/소문자, 특수문자를 표현
EBCDIC 코드와 유사하지만, 일반적으로 ASCII코드를 더 많이 사용함
│<-존비트->│ <- 숫자 비트 -> │
├――――――――┴―――――――――――――――┤
| | | | 8 | 4 | 2 | 1 |
└――┴――┴――┴―――┴―――┴―――┴―――┘
ASCII 코드표 - 예) 영문 대문자 ‘A’ 에 대한 ASCII 코드 -> 1000001
| 000 | 001 | 010 | 011 | 100 | 101 | 110 | 111 | |
|---|---|---|---|---|---|---|---|---|
| 0000 | NUL | DLE | SP | 0 | @ | P | ` | p |
| 0001 | SCH | DC1 | ! | 1 | A | Q | a | q |
| 0010 | STX | DC2 | " | 2 | B | R | b | r |
| 0011 | ETX | DC3 | # | 3 | C | S | c | s |
| 0100 | EOT | DC4 | $ | 4 | D | T | d | t |
| 0101 | END | NAK | % | 5 | E | U | e | u |
| 0110 | ACK | SYN | & | 6 | F | V | f | v |
| 0111 | BEL | ETB | ' | 7 | G | W | g | w |
| 1000 | BS | CAN | ( | 8 | H | X | h | x |
| 1001 | HIT | EM | ) | 9 | I | Y | i | y |
| 1010 | LF | SUB | * | : | J | Z | j | z |
| 1011 | VT | ESC | _ | ; | K | [ | k | {} |
| 1100 | FF | FS | , | < | L | (\) | l | | |
| 1101 | CR | GS | - | = | M | ] | m | } |
| 1110 | SO | RS | . | > | N | ^ | n | ~ |
| 1111 | SI | US | / | ? | O | _ | o | DEL |
2) 논리 자료의 표현
논리 자료
- 논리값을 표현하기 위한 자료 형식
-
- 논리값 참(True)와 거짓(False), 1과 0
1바이트를 사용하여 논리 자료를 표현하는 방법 1
- 참 : 최하위 비트를 1로 표시 00000001
- 거짓 : 전체 비트를 0으로 표시 00000000
1바이트를 사용하여 논리 자료를 표현하는 방법 2
- 참 : 전체 비트를 1로 표시 11111111
- 거짓 : 전체 비트를 0으로 표시 00000000
1바이트를 사용하여 논리 자료를 표현하는 방법 1
- 참 : 하나 이상의 비트를 1로 표시 00000001 or 00000100 ...
- 거짓 : 전체 비트를 0으로 표시 00000000
3) 포인터 자료의 표현
포인터 자료
- 메모리의 주소를 표현하기 위한 자료 형식
- 변수의 주소나 메모리의 특정 위치에 대한 주소를 저장하고 주소 연산을 위해 사용
- 복잡한 자료구조 연산을 메모리에서의 주소 연산만으로 처리 가능
4) 문자열 자료의 표현
문자열 자료
- 하나의문자만표현할수있는문자자료와달리여러문자로 이루어진 문자의 그룹을 하나의 자료로 취급하여 메모리에 연속적으로 저장하는 자료 형식
하나의 문자열 자료에 포함된 부분 문자열을 표현하는 방법 1
- 부분문자열사이에구분자를두고연속저장하는방법
하나의 문자열 자료에 포함된 부분 문자열을 표현하는 방법 2
- 가장 긴 부분문자열의 길이에 맞추어 고정 길이로 연속 저장하는 방법
하나의 문자열 자료에 포함된 부분 문자열을 표현하는 방법 3
- 부분문자열을 연속 저장하고 각 부분문자열에 대한 주소와 문자열의 마지막 주소를 포인터에 저장하는 방법
부분 문자열의 표현 예
- 방법1: 구분자를 사용하는 표현 : 구분자로 세미콜론(;) 사용
┌―――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――┐
│ C │ O │ M │ P │ U │ T │ E │ R │ ; │ D │ A │ T │ A │ │ S │ T │ R │ U │ C │ T │ U │ R │ E │ ; │ S │ T │ R │ I │ N │ G │
├―――――――――――――――――――――――――――――――┼―――┼―――――――――――――――――――――――――――――――――――――――――――――――――――――――┼―――┼―――――――――――――――――――――――┤
│ <- 부분 문자열1 -> │ │ <- 부분 문자열2 -> │ │ <- 부분 문자열3 -> │
방법2:고정길이를사용하는방법
┌―――――――――――――――――――――――――――――――――――――――――――――――――――――――┐
│ C │ O │ M │ P │ U │ T │ E │ R │ │ │ │ │ │ │ <- 부분 문자열1 (빈칸: 미사용 공간)
├―――――――――――――――――――――――――――――――――――――――――――――――――――――――┤
│ D │ A │ T │ A │ │ S │ T │ R │ U │ C │ T │ U │ R │ E │ <- 부분 문자열2
├―――――――――――――――――――――――――――――――――――――――――――――――――――――――┤
│ S │ T │ R │ I │ N │ G │ │ │ │ │ │ │ │ │ <- 부분 문자열3 (빈칸: 미사용 공간)
└―――――――――――――――――――――――――――――――――――――――――――――――――――――――┘
방법3 : 포인터를 사용하는 방법
┌―――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――┐
│ 10│ 11│ 12│ 13│ 14│ 15│ 16│ 17│ 18│ 19│ 20│ 21│ 22│ 23│ 24│ 25│ 26│ 27│ 28│ 29│ 30│ 31│ 32│ 33│ 34│ 35│ 36│ 37│
├―――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――┤
│ C │ O │ M │ P │ U │ T │ E │ R │ D │ A │ T │ A │ │ S │ T │ R │ U │ C │ T │ U │ R │ E │ S │ T │ R │ I │ N │ G │
└―――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――┘
↑ ↑ ↑ ↑
└―――――――――――――――――――――――――――┐ └―――――――┐ ┌―――――――――――――――――――――――――――――――――――――――――┘ ┌――――――――――――┘
│ │ │ │
│ ┌――――――――――――――┐ ┌――――┐
└――――│ 10 │ 18 │ 32 │ HEAD END │ 37 │
└――――――――――――――┘ └――――┘
4) 문자열 자료의 표현
문자열 자료 표현방법 비교
| 구분자를 사용하는 방법 |
고정길이로 저장하는 방법 |
포인터를 사용하는 방법 |
|
|---|---|---|---|
| 메모리이용율 | 문자열 길이 +구분자 길이 ->효율적 |
가장 긴 부분문자열 길이 X 부분문자열의 개수 -> 비효율적 |
문자열의 길이 +포인터 저장공간 -> 효율적 |
| 부분문자열 탐색기간 |
문자비교 연산 시간 + 구분자 식별 시간 -> 비효율적 |
문자 비교 연산 시간 -> 효율적 |
문자 비교 연산시간 + 포인터 주소 연산 시간 ->효율적 |
```