자료구조 : 데이터를 구조화하는 수단
자료구조의 유형
◦ 배열, 리스트, 스택, 큐, 트리
컴퓨터의 메모리는 셀들로 구성
◦ 메모리 셀은 메모리 주소와 내용을 가짐
◦ 메모리 주소는 연속적으로 구성됨
배열
◦ 가장 간단한 메모리 자료구조
◦ 일련의 연속적인 메모리 셀들로 구성
◦ 메모리 셀들은 동질적인 데이터를 저장
유용성
◦ 많은 수의 비슷한 항목에 대해서 하나의 변수 이름
선언(정의) : 데이터 유형과 크기를 제공
Java의 예: int[ ] aGrades = new int[5];
◦ “int[ ]”는 컴퓨터에게 배열이 정수를 보관함을 알려줌
◦ “aGrades”는 배열의 이름
◦ “new”키워드는 새로운 배열이 생성됨을 명세함
◦ “int[5]”는 5개의 메모리 장소를 확보함
차원성
◦ 차원 : 원소(메모리 셀)의 행/열
◦ aGrades는 1차원임(한 줄의 우편함처럼)
1차원 배열의 조작
◦ 인덱스 : 접근을 위해 “[]”내에 위치한 정수
예 : aGrades[0] = 50;
◦ 하한값: 영(0)
◦ 상한값: 배열의 크기-1 ex) aGrades의 크기 =49 : “aGrades”를 명명하기 위한 표준
[그림 9-6] 모든 원소들이 저장된 배열
다차원 배열
◦ 둘 또는 그 이상의 1차원 배열로 구성됨
◦ 각행의 위에 여러 행들이 쌓여 있음
아파트 건물의 우편함
Tic-tac-toe 게임판
정의 : char[ ][ ] aTicTacToe = new char[3][3];
지정 : aTicTacToe[1][1] = ’X’;
◦ X를 두 번째 행의 두 번째 열에 놓음
3차원 이상의 배열도 가능
배열의 장점
◦
메모리 셀의 순차 접근을 허용◦
이름과 데이터를 사용하여 데이터를 검색/저장◦
구현이 쉬움◦
프로그램 작성과 판독을 단순화
제약점 및 단점
◦
클래스와 달리 이질적인 항목들을 저장할 수 없음◦
동적인 메모리 할당 불가능◦
정렬되어 있지 않은 배열의 탐색은 효율적이지 않음
리스트 : 동적 자료구조
◦ 데이터의 양이 알려져 있지 않거나 변화할 수 있는 경우 에 적절함
기본적인 세가지 리스트 형태 :
◦ 연결리스트(Linked lists)
◦ 스택(Stack)
◦ 큐(Queue)
연결리스트
◦ 가변 데이터 집합을 위해 사용되는 구조
◦ 배열과는 달리 데이터를 불연속적으로 저장
◦ 데이터와 다음에 연결된 셀의 주소를 관리
연결리스트는 고급자료구조의 기본임
◦ 각각의 구조들은 포인터에 기반함
포인터 : 메모리 위치를 가리키는 메모리 변수
예 : 연결리스트 게임
종이는 두 부분으로 구분된 하나의 노드를 나타냄
◦
데이터(첫 번째 부분, 색상)◦
포인터 : 다음 위치(학생 ID 번호)
교수의 종이 : 데이터가 없는 head pointer
마지막 학생 : 포인터 값은 NULL임
새로운 원소의 삽입
◦
배열과 달리 크기 조정이 불필요함◦
데이터와 포인터를 가진 새로운 “종이”를 만듬◦
새로운 노드(종이)를 수용하도록 포인터를 조정
항목의 삭제를 위해서도 유사한 과정
◦ 목표 항목의 앞에 있는 원소의 포인터를 변경
◦ 원소를 이동시키지 않고 리스트로부터 학생을 제거
동적 메모리 할당
◦ 연결리스트가 배열보다 더 효율적임
◦ 메모리 셀들은 연속적일 필요 없음
스택 : 특별한 형태의 리스트
◦
새 항목의 저장을 위해, 리스트에 “푸시(push)”함◦
현재항목의 검색을 위해, 리스트로부터 “팝(pop)”함
LIFO 자료구조
◦
스택에 처음 PUSH된 항목이 가장 나중에 POP 됨
Stack Pointer(스택 포인터)는 스택의 top을 나타냄
POP이나 PUSH 연산의 적용 이전에 스택의 상태를 검
사
큐 : 다른 유형의 연결리스트
◦
선입선출(FIFO) 저장시스템을 구현◦
삽입은 큐의 끝에서 이루어짐◦
삭제는 처음에서 이루어짐◦
기다리는 줄과 같음
큐의 사용 : 프린터 예
◦
인쇄되는 첫 항목은 가장 오랫동안 기다린 문서임◦
현재 항목이 큐로부터 삭제된 후 다음 항목이 인쇄됨◦
새로운 문서는 큐의 끝에 위치함
포인터
◦ 헤드 포인터는 큐의 시작을 유지함
◦ 테일 포인터는 큐의 끝을 유지함
디큐 (dequeue) 연산
◦ 큐로부터 항목(가장 오래된 엔트리)을 제거
◦ 헤드 포인터는 리스트내에 다음 항목을 가리키도록 변경 됨
인큐 (enqueue) 연산
◦ 리스트의 끝에 항목이 놓여지며, tail 포인터가 변경됨
트리 : 조직도나 가계도와 유사한 계층 자료 구조
◦ 트리내의 각 장소는 노드 또는 점검이라 함
◦ 트리의 시작 노드는 루트라 함
◦ 노드들 사이에는 부모-자식 관계가 있음
◦ 자식이 없는 노드는 리프 노드라 함
◦ 깊이(레벨) : 루트 노드로부터의 거리를 나타냄
◦ 높이 : 최대 레벨 수
[그림 9-23] 트리의 노드들
이진 트리 : 트리의 한 유형
◦ 부모 노드는 0, 1 또는 2개의 자식 노드를 가질 수 있음
◦ 자식은 “왼쪽” 또는 “오른쪽” 위치로 구분됨
이진 탐색 트리 : 이진 트리의 한 종류
◦ 왼쪽 자식 노드의 데이터 값 < 부모 노드의 값
◦ 오른쪽 자식 노드의 데이터 값 > 부모 노드의 값
[그림 9-24] 이진 트리의 레벨과 높이
이진 탐색 트리는 세 요소를 포함
◦ 왼쪽 자식 포인터
◦ 오른쪽 자식 포인터
◦ 데이터
루트 : 트리의 접근을 위한 초기 시작점
[그림 9-26] 이진 트리 노드
탐색 루틴
◦
루트 위치에서 시작◦
경로가 왼쪽 또는 오른쪽 자식으로 이동하는지 결정◦
데이터의 방향(왼쪽 또는 오른쪽)으로 이동◦
값이 발견되면 노드에서 정지하고 호출자에게 반환◦
값이 발견되지 않으면 자식 노드에 대해서 과정 반복
정렬된 데이터의 예
◦ 사전내의 단어
◦ 디렉토리내의 화일
◦ 책의 색인
수 많은 정렬 알고리즘 각각의 장단점이 있다 .
◦ 코드, 공간, 시간 복잡도에 따라 분석됨
◦ 예) 선택 정렬과 버블 정렬
선택 정렬 : 수작업 정렬 과정을 흉내 냄
◦ 리스트에서 최소값을 찾음
◦ 첫 번째 위치에 있는 항목과 교환
◦ 두 번째 위치로 이동
◦ 줄어든 리스트(첫 번째 위치가 제외된)를 대상으로 과정 반복
◦ 마지막 항목의 바로 이전 항목까지 과정을 진행
선택 정렬은 사용과 구현이 간단
선택 정렬은 큰 리스트에 비효율적
버블 : 가장 오래된 정렬 방법 중 하나
◦
리스트 내의 마지막 원소부터 시작◦
이 원소의 값을 바로 위 항목의 값과 비교◦
만일 더 작으면 위치를 변경하고 리스트의 위를 계속함 더 작은 항목이 발견될 때까지 비교를 계속함
◦
더 작지 않으면 다음 항목을 그 위의 항목과 비교◦
가장 작은 값이 꼭대기로 올라갈 때까지 검사를 계속함◦
처음 항목이 제외된 리스트에 대해서 과정 반복
버블정렬은 구현이 단순
