C로 만드는 자료구조

chapter 01. 자료구조의 개요

학습 목표 자료구조의 의미와 중요성 자료구조의 내용 컴퓨터 내부의 2진수 코드 체계 자료의 형태에 따른 자료 표현 형식

자료구조 개요 자료구조란? 자료를 효율적으로 사용하기 위해서 자료의 특성에 따라서 분류하여 구성하고 저장 및 처리하는 모든 작업(조직화 구조화) 컴퓨터 분야에서의 자료구조:자료를 컴퓨터에 어떻게 표현, 표현한 자료를 효율적으로 저장할 것을 처리하는 논리적인 구조와 프로그램적인 처리 방법 컴퓨터(자료처리 장치), 자료구조는 컴퓨터를 전공에 기본적이고 필수적.

자료구조 개요 컴퓨터 분야에서 자료구조를 왜 배워야 하는가? 컴퓨터가 효율적으로 문제를 처리하기 위해서는 문제를 정의하고 분석하여 그에 대한 최적의 프로그램을 작성해야 한다. ☞ 자료구조에 대한 개념과 활용 능력 필요! 자료구조의 내용[그림 1-3] 다양한 자료구조에 대하여 이해하고, 논리적이고 수학적인 분석을 통해 최적의 알고리즘을 개발할 수 있는 능력을 갖추어야만 실제 시스템을 개발할 수 있는 고급 개발자가 된다.

자료구조 개요 자료구조의 내용[그림 1-3] 다양한 자료구조에 대하여 이해하고, 논리적이고 수학적인 분석을 통해 최적의 알고리즘을 개발할 수 있는 능력을 갖추어야만 실제 시스템을 개발할 수 있는 고급 개발자가 된다

일상생활과 자료구조의 비교 Ticket Box 해야할일 리스트 C B A a b c NULL 전단(front) 후단(rear) 일상생활에서의 예 자료구조 물건을 쌓아두는 것 스택 영화관 매표소의 줄 큐 할일 리스트 리스트 영어사전 사전, 탐색구조 지도 그래프 조직도 트리

자료구조와 알고리즘 … 프로그램 = 자료구조(자료를 프로그램 안에서 표현하는 방법) + 알고리즘(어떤 일을 하는 절차) (예) 최대값 탐색 프로그램 = 배열+ 순차탐색 자료구조 알고리즘 score[] 80 70 90 … 30 tmp←score[0]; for i ← 1 to n do if score[i]>tmp then tmp←score[i];

박철수의 전화번호는 바로 부근으로 넘기면 찾을 수 있겠군 알고리즘 알고리즘(algorithm): 컴퓨터로 문제를 풀기 위한 단계적인 절차 알고리즘의 조건 입 력 : 0개 이상의 입력이 존재하여야 한다. 출 력 : 1개 이상의 출력이 존재하여야 한다. 명백성 : 각 명령어의 의미는 모호하지 않고 명확해야 한다. 유한성 : 한정된 수의 단계 후에는 반드시 종료되어야 한다. 유효성 : 각 명령어들은 실행 가능한 연산이어야 한다. 박철수의 전화번호는 바로 부근으로 넘기면 찾을 수 있겠군

알고리즘의 기술 방법 영어나 한국어와 같은 자연어 흐름도(flow chart) 유사 코드(pseudo-code) (예) 배열에서 최대값 찾기 알고리즘 1 2 3 4 5 6 7 8 9 10

자연어로 표기된 알고리즘 인간이 읽기가 쉽다. 그러나 자연어의 단어들을 정확하게 정의하지 않으면 의미 전달이 모호해질 우려가 있다. (예) 배열에서 최대값 찾기 알고리즘 ArrayMax(A,n) 배열 A의 첫번쨰 요소를 변수 tmp에 복사 배열 A의 다음 요소들을 차례대로 tmp와 비교하면 더 크면 tmp로 복사 배열 A의 모든 요소를 비교했으면 tmp를 반환

흐름도로 표기된 알고리즘 직관적이고 이해하기 쉬운 알고리즘 기술 방법 그러나 복잡한 알고리즘의 경우, 상당히 복잡해짐. tmp←A[0] i←1 i < n A[i]>tmp tmp←A[i] tmp no yes i++

유사코드로 표현된 알고리즘 알고리즘의 고수준 기술 방법 자연어보다는 더 구조적인 표현 방법 프로그래밍 언어보다는 덜 구체적인 표현방법 알고리즘 기술에 가장 많이 사용 프로그램을 구현할 때의 여러가지 문제들을 감출 수 있다. 즉 알고리즘의 핵심적인 내용에만 집중할 수 있다. ArrayMax(A,n) tmp ← A[0]; for i←1 to n-1 do if tmp < A[i] then tmp ← A[i]; return tmp; 대입 연산자가 ←임을 유의

C로 표현된 알고리즘 알고리즘의 가장 정확한 기술이 가능 반면 실제 구현시의 많은 구체적인 사항들이 알고리즘의 핵심적인 내용들의 이해를 방해할 수 있다. #define MAX_ELEMENTS 100 int score[MAX_ELEMENTS]; int find_max_score(int n) { int i, tmp; tmp=score[0]; for(i=1;i<n;i++){ if( score[i] > tmp ){ tmp = score[i]; } return tmp;

자료구조의 분류 자료의 형태에 따른 분류 단순 구조 선형구조 비선형구조 파일구조 정수, 실수, 문자, 문자열 등의 기본 자료형 자료들 간의 앞뒤 관계가 1:1의 선형 관계 리스트, 연결리스트, 스택, 큐, 덱 등 비선형구조 자료들 간의 앞뒤 관계가 1:多, 또는 多:多의 관계 트리, 그래프 등 파일구조 레코드의 집합인 파일에 대한 구조 순차파일, 색인파일, 직접파일 등

자료구조의 분류 그림1-4 자료구조의 형태에 따른 분류

자료의 표현 디지털 시스템에서의 자료의 표현 숫자, 문자, 그림, 소리, 기호 등 모든 형식의 자료를 2진수 코드로 표현하여 저장 및 처리, 0 1 자료표현의 최소단위 2진수 코드 1과 0, ON과 OFF, 참(True)과 거짓(False)의 조합 2진수 코드의 단위

자료의 표현 n개의 비트로 2n개의 상태수 표현 예) n=2 인 경우 예) n=4 인 경우

자료의 표현 컴퓨터 내부에서 표현할 수 있는 자료의 종류

자료의 표현 - (1) 수치자료의 표현 10진수의 표현 자료의 표현 - (1) 수치자료의 표현 10진수의 표현 존(Zone) 형식의 표현(Zone format, Unpack format) 10진수 한자리를 표현하기 위해서 1바이트(8비트)를 사용하는 형식 존 영역 상위 4비트 1111로 표시 수치 영역 하위 4비트 표현하고자 하는 10진수 한자리 값에 대한 2진수 값을 표시 존 형식의 구조

자료의 표현 - (1) 수치자료의 표현 [표 1-1]수치 영역의 값 표현

자료의 표현 - (1) 수치자료의 표현 여러 자리의 10진수를 표현하는 방법 10진수의 자릿수 만큼 존 형식을 연결하여 사용 자료의 표현 - (1) 수치자료의 표현 여러 자리의 10진수를 표현하는 방법 10진수의 자릿수 만큼 존 형식을 연결하여 사용 마지막 자리의 존 영역에 부호를 표시 양수(+) : 1100 (C16진수) 음수(-) : 1101 (D16진수) 부호를 갖지 않는 데이터 : 1111(F16진수) 부호 갖지 않는 수 1111=F 부호

자료의 표현 - (1) 수치자료의 표현 존 형식으로 10진수를 표현하는 예 +213 -213 2 1 3 1111 0010 자료의 표현 - (1) 수치자료의 표현 존 형식으로 10진수를 표현하는 예 +213 -213 2 1 3 1111 0010 0001 1100 0011 F 2 1 C(+) 3 2 1 3 1111 0010 0001 1101 0011 F 2 1 D(-) 3

자료의 표현 - (1) 수치자료의 표현 팩(Pack) 형식의 표현( Pack format) 자료의 표현 - (1) 수치자료의 표현 팩(Pack) 형식의 표현( Pack format) 10진수 한자리를 표현하기 위해서 존 영역 없이 4비트를 사용하는 형식 최하위 4비트에 부호를 표시 양수(+) : 1100 음수(-) : 1101 [그림 1-11] 팩 형식의 10진수 표현 형식 부호

자료의 표현 - (1) 수치자료의 표현 팩 형식으로 10진수를 표현하는 예 + 213 - 213 0010 0001 0011 자료의 표현 - (1) 수치자료의 표현 팩 형식으로 10진수를 표현하는 예 + 213 - 213 0010 0001 0011 1100 2 1 3 C(+) 0010 0001 0011 1101 2 1 3 D(-)

자료의 표현 - (1) 수치자료의 표현 2진수의 정수 표현 n비트의 부호 절대값 형식 최상위 1비트 - 부호 표시 자료의 표현 - (1) 수치자료의 표현 2진수의 정수 표현 n비트의 부호 절대값 형식 최상위 1비트 - 부호 표시 양수(+) : 0 음수(-) : 1 나머지 n-1 비트 – 이진수 표시 1바이트를 사용하는 부호 절대값 형식의 예 + 21  - 21 1비트 ←  7 비트      → 0  0  1  0  1  0  1 부호 21의 절대값  1비트 ← 7 비트      → 1 0  0  1  0  1  0  1 부호 21의 절대값 

자료의 표현 - (1) 수치자료의 표현 1의 보수(1’ Complement) 형식 자료의 표현 - (1) 수치자료의 표현 1의 보수(1’ Complement) 형식 음수의 표현에서 부호 비트를 사용하는 대신 1의 보수를 사용하는 방법 n비트의 2진수를 1의 보수로 만드는 방법 n비트를 1로 한 이진수에서 변환하고자 하는 이진수를 뺀다. 예) 10진수 21을 1의 보수로 만들기 (1바이트 사용) 1바이트를 사용하는 1의 보수 형식의 예 + 21  - 21      1 1 1 1 1 1 1 1  -  0 0 0 1 0 1 0 1 ☜  21의 2진수 값     1 1 1 0 1 0 1 0  21의 1의 보수 0  0  1  0  1  0  1 ←  21의 절대값      → 1 1  1  0  1  0  1  0 ←  21의 1의 보수     → ☞ 부호절대값형식의 양수 표현과 같음!

자료의 표현 - (1) 수치자료의 표현 2의 보수(2’ Complement) 형식 자료의 표현 - (1) 수치자료의 표현 2의 보수(2’ Complement) 형식 음수의 표현에서 부호 비트를 사용하는 대신 2의 보수를 사용하는 방법 n비트의 2진수를 2의 보수로 만드는 방법 1의 보수에 1을 더해준다. 예) 10진수 21을 2의 보수로 만들기 (1바이트 사용)      1 1 1 1 1 1 1 1  -  0 0 0 1 0 1 0 1 ☜  21의 2진수 값     1 1 1 0 1 0 1 0 + 1  21의 1의 보수     1 1 1 0 1 0 1 1  21의 2의 보수

자료의 표현 - (1) 수치자료의 표현 2진수 정수의 세 가지 표현 방법에서 양수의 표현은 같고, 음수의 표현만 다르다. 자료의 표현 - (1) 수치자료의 표현 1바이트를 사용하는 2의 보수 형식의 예 + 21  - 21 2진수 정수의 세 가지 표현 방법에서 양수의 표현은 같고, 음수의 표현만 다르다. 0  0  1  0  1  0  1 ←  21의 절대값      → 1 1  1  0  1  0  1  1 ←  21의 2의 보수     → ☞ 부호절대값형식의 양수 표현과 같음!

자료의 표현 - (1) 수치자료의 표현 2진수의 실수 표현 고정 소수점 표현 자료의 표현 - (1) 수치자료의 표현 2진수의 실수 표현 고정 소수점 표현 소수점이 항상 최상위 비트의 왼쪽 밖에 고정되어있는 것으로 취급하는 방법 고정 소수점 표현의 00010101 은 0.00010101 의 실수 값을 의미

자료의 표현 - (1) 수치자료의 표현 부동 소수점 형식의 표현 고정 소수점 형식에 비해서 표현 가능한 값의 범위가 넓다. 자료의 표현 - (1) 수치자료의 표현 부동 소수점 형식의 표현 고정 소수점 형식에 비해서 표현 가능한 값의 범위가 넓다. 실수를 부호와 지수, 소수의 세 부분으로 구분하여 표현 4바이트를 사용하는 부동 소수점 형식

자료의 표현 - (2) 문자자료의 표현 문자자료의 표현 문자에 대한 이진수 코드를 정의하여 사용 문자에 대한 이진수 코드표 자료의 표현 - (2) 문자자료의 표현 문자자료의 표현 문자에 대한 이진수 코드를 정의하여 사용 문자에 대한 이진수 코드표 BCD 코드 EBCDIC 코드 ASCII 코드

자료의 표현 - (2) 문자자료의 표현 BCD 코드 6비트를 사용하여 문자 표현 BCD 코드의 구성 상위 2비트 : 존 비트 자료의 표현 - (2) 문자자료의 표현 BCD 코드 6비트를 사용하여 문자 표현 상위 2비트 : 존 비트 하위 4비트 : 2진수 비트 존 비트와 2진수 비트를 조합하여 10진수 0~9와 영어 대문자와 특수문자 를 표현 BCD 코드의 구성

자료의 표현 - (2) 문자자료의 표현 [표 1-2] BCD 코드 표 예) 영문자 A에 대한 BCD 코드 ☞ 010001

자료의 표현 - (2) 문자자료의 표현 EBCDIC 코드 8비트를 사용하여 문자 표현 EBCDIC 코드의 구성 자료의 표현 - (2) 문자자료의 표현 EBCDIC 코드 8비트를 사용하여 문자 표현 상위 4비트 : 존 비트 하위 4비트 : 2진수 비트 존 비트와 2진수 비트를 조합하여 10진수 0~9와 영어 대문자/소문자와 특수문자를 표현 EBCDIC 코드의 구성

자료의 표현 - (2) 문자자료의 표현 [표 1-3] EBCDIC 코드 표 자료의 표현 - (2) 문자자료의 표현 [표 1-3] EBCDIC 코드 표 예) 영문자 A에 대한 EBCDIC 코드 ☞ 11000001

자료의 표현 - (2) 문자자료의 표현 ASCII 코드 7비트를 사용하여 문자 표현 ASCII 코드의 구성 자료의 표현 - (2) 문자자료의 표현 ASCII 코드 7비트를 사용하여 문자 표현 상위 3비트 : 존 비트 하위 4비트 : 2진수 비트 존 비트와 2진수 비트를 조합하여 10진수 0~9와 영어 대문자/소문자와 특수문자를 표현 ASCII 코드의 구성 100 A-O 101 P-Z 011 숫자 010 특수문자 110 a-o 111 p-z

자료의 표현 - (2) 문자자료의 표현 [표 1-4] ASCII 코드 표 자료의 표현 - (2) 문자자료의 표현 [표 1-4] ASCII 코드 표 예) 영문자 A에 대한 ASCII 코드 ☞ 1000001 100 A-O 101 P-Z 011 숫자 010 특수문자 110 a-o 111 p-z

자료의 표현 - (3) 논리자료의 표현 논리자료 논리값을 표현하기 위한 자료 형식 논리값 자료의 표현 - (3) 논리자료의 표현 논리자료 논리값을 표현하기 위한 자료 형식 논리값 참(true)과 거짓(false), 1과 0 1바이트를 사용하여 논리자료를 표현하는 방법 방법1) 참 - 최하위 비트를 1로 표시. 00000001 거짓 – 전체 비트를 0으로 표시. 00000000 방법2) 참 – 전체 비트를 1로 표시. 11111111 방법3) 참 – 하나 이상의 비트를 1로 표시

자료의 표현 - (4) 포인터 자료의 표현 포인터 자료 메모리의 주소를 표현하기 위한 자료 형식 자료의 표현 - (4) 포인터 자료의 표현 포인터 자료 메모리의 주소를 표현하기 위한 자료 형식 변수의 주소나 메모리의 특정 위치에 대한 주소를 저장하고 주소연산하기 위해 사용

자료의 표현 - (5) 문자열 자료의 표현 문자열(string) 자료 자료의 표현 - (5) 문자열 자료의 표현 문자열(string) 자료 여러 문자로 이루어진 문자의 그룹을 하나의 자료로 취급하여 메모리에 연속적으로 저장하는 자료 형식 하나의 문자열 자료에 포함된 부분문자열을 표현하는 방법 방법1) 부분문자열 사이에 구분자를 두고 연속 저장하는 방법 방법2) 가장 긴 부분문자열의 길이에 맞추어 고정 길이로 연속 저장하는 방법 방법3) 부분문자열을 연속 저장하고 각 부분문자열에 대한 포인터를 사용 하는 방법

자료의 표현 - (5) 문자열 자료의 표현 부분문자열의 표현 예 자료의 표현 - (5) 문자열 자료의 표현 부분문자열의 표현 예 표현할 문자열 : {COMPUTER, DATA STRUCTURE, STRING} 방법1) 구분자를 사용하는 표현 : 구분자로 세미콜론(;) 사용 방법2) 고정길이를 사용하는 표현 방법3) 포인터를 사용하는 표현 문자 비교와 구분자 식별 연산과 시간 필요 가장 긴 문자열을 기준으로 사용, 찾기는 쉽다. 사용공간의 낭비 부분문자열에 대한 주소와 문자열의 마지막 주소를 포인터에 저장

자료의 표현 - (5) 문자열 자료의 표현 부분 문자열 표현 방법의 비교