자료검색

컴퓨터로 어떤 문제를 해결하기 위해 필요한 자료들을 효율적으로 관리하고 구조화시키기 위한 학문 '자료구조'. 이 책은 자료구조를 보다 명확하게 배울 수 있도록 구성되어 있다. 각 장에서는 먼저 쉬운 그림을 통해 각 자료구조의 개념을 이해하고, 추상 자료형을 생각해 본다. 다음으로 그림과 유사코드를 통해 자료구조의 동작을 이해한 후 최종적으로 C언어로 구현하는 방법을 학습하도록 하였다.

CHAPTER 01 자료구조와 알고리즘

1.1 자료구조

자료구조의 분류

1.2 알고리즘

프로그램 = 자료구조 + 알고리즘

알고리즘 기술 방법

1.3 추상 자료형

추상화란?

추상 자료형이란?

1.4 알고리즘의 성능 분석

실행시간 측정방법

알고리즘의 복잡도 분석방법

시간 복잡도 함수

빅오표기법

빅오표기법 이외의 표기법

최선, 평균, 최악의 경우

연습문제

프로그래밍 프로젝트



CHAPTER 02 배열과 구조체

2.1 대용량 자료의 처리

2.2 배열

1차원 배열

2차원 배열

함수의 매개변수로서의 배열

2.3 구조체

구조체의 정의와 선언

구조체의 연산

구조체를 포함하는 구조체와 구조체 배열

구조체와 함수

2.4 배열과 구조체의 응용: 다항식 프로그램

다항식의 표현

다항식의 구현

다항식 입력 함수 read_poly()

두 다항식 합 add_poly()

전체 프로그램

희소 다항식의 표현

연습문제

프로그래밍 프로젝트



CHAPTER 03 스택

3.1 스택이란?

스택의 추상 자료형

스택의 활용

스택의 구현 방법

3.2 배열을 이용한 스택

공백상태와 포화 상태 검사

삽입 연산

삭제 연산

3.3 스택의 구현: int 스택

3.4 스택의 구현: 구조체를 저장하는 스택

3.5 괄호 검사

3.6 후위 표기 수식의 계산

3.7 중위 표기 수식의 후위 표기 변환

연습문제

프로그래밍 프로젝트



CHAPTER 04 큐

4.1 큐란?

큐의 추상 자료형

큐의 활용

4.2 배열을 이용한 큐

선형 큐

원형 큐

4.3 원형 큐의 구현

4.4 덱이란?

덱의 추상 자료형

배열을 이용한 원형 덱

4.5 덱의 구현

4.6 큐의 응용: 은행 시뮬레이션

4.7 덱의 응용: 미로 탐색 프로그램

4.8 전역 변수와 객체지향 프로그래밍

C++ 클래스를 이용한 원형큐 구현

C언어의 구조체를 이용한 원형큐 구현

연습문제

프로그래밍 프로젝트



CHAPTER 05 포인터와 연결리스트

5.1 포인터

포인터 선언

포인터의 활용

포인터 연산

포인터와 배열

포인터와 구조체

자체 참조 구조체

포인터 사용시 주의점

5.2 동적 메모리 할당

동적 메모리 할당 라이브러리 함수

포인터와 동적 메모리 할당

5.3 연결 리스트

연결리스트의 구조

연결 리스트의 특징

연결리스트의 종류

5.4 포인터의 응용: 연결리스트로 구현한 스택

연결된 스택의 구조

연결된 스택의 연산

5.5 포인터의 응용: 연결리스트로 구현한 큐

연결된 큐의 구조

연결된 큐의 연산

구조체 항목에 대한 연결된 큐 구현: 학생정보 큐

연습문제

프로그래밍 프로젝트



CHAPTER 06 리스트

6.1 리스트란?

리스트의 추상 자료형

6.2 배열로 구현한 리스트

리스트의 구조

리스트의 연산

6.3 연결 리스트로 구현된 리스트

리스트의 구조

단순한 연산들

삽입연산

삭제연산

헤드 포인터와 헤드 노드

6.4 다양한 형태의 연결 리스트

원형 연결 리스트(circular linked list)

이중 연결 리스트(doubly linked list)

6.5 연결 리스트의 응용: 라인 편집기

연습문제

프로그래밍 프로젝트



CHAPTER 07 순환

7.1 순환의 소개

순환이란?

순환호출의 내부적인 구현

7.2 순환 알고리즘의 구조

순환↔반복

분할정복(divide and conquer)

순환 알고리즘의 성능

7.3 거듭제곱값 계산

7.4 피보나치수열의 계산

7.5 순환의 응용: 하노이탑

7.6 순환의 응용: 미로 탐색

연습문제

프로그래밍 프로젝트



CHAPTER 08 트리

8.1 트리의 개념

트리의 용어들

트리의 종류

8.2 이진트리

이진트리의 성질

이진트리의 분류

이진트리의 추상 자료형

8.3 이진트리의 표현

배열 표현법

링크 표현법

8.4 링크 표현법을 이용한 이진트리의 구현

8.5 이진트리의 순회

전위 순회(preorder)

중위 순회(inorder)

후위 순회

레벨 순회

8.6 이진트리 연산

노드 개수 구하기

단말 노드 개수 구하기

트리의 높이 구하기

8.7 이진트리 응용

수식 트리

폴더 용량 계산

연습문제

프로그래밍 프로젝트



CHAPTER 09 이진탐색트리

9.1 이진탐색트리

이진탐색트리의 정의

9.2 이진탐색트리의 연산

탐색 연산

삽입 연산

삭제 연산

9.3 이진탐색트리의 성능 분석

9.4 심화 학습: 균형 이진탐색트리

AVL 트리란?

AVL 트리의 삽입 연산

9.5 이진탐색트리의 응용: 나의 단어장

연습문제

프로그래밍 프로젝트



CHAPTER 10 우선순위 큐

10.1 우선순위 큐

우선순위 큐 추상 자료형

10.2 우선순위 큐의 구현 방법

정렬되지 않은 배열을 사용하는 방법

정렬된 배열을 사용하는 방법

연결 리스트를 사용하는 방법

힙을 사용하는 방법

10.3 힙(Heap)

힙의 표현 방법

배열을 이용한 힙의 구조

10.4 힙의 연산

삽입 연산

삭제 연산

힙의 복잡도 분석

10.5 힙의 응용: 힙 정렬

10.6 힙의 응용: 허프만 코드

허프만 코드 생성 방법

연습문제

프로그래밍 프로젝트



CHAPTER 11 그래프

11.1 그래프란?

그래프의 역사

그래프의 종류

그래프의 용어

그래프의 추상 자료형

11.2 인접 행렬을 이용한 그래프의 표현

인접 행렬을 이용한 그래프의 구현

11.3 인접 리스트를 이용한 그래프의 표현

인접 리스트를 이용한 그래프의 구현

11.4 그래프의 탐색

깊이 우선 탐색

너비 우선 탐색

11.5 연결 성분 검사

11.6 신장 트리

11.7 위상 정렬

연습문제

프로그래밍 프로젝트



CHAPTER 12 가중치 그래프

12.1 가중치 그래프란?

12.2 가중치 그래프의 표현

인접 행렬을 이용한 가중치 그래프의 구현

12.3 최소비용 신장트리

Kruskal의 MST 알고리즘

Prim의 MST 알고리즘

12.4 최단 경로

Dijkstra의 최단 경로 알고리즘

Floyd의 최단 경로 알고리즘

연습문제

프로그래밍 프로젝트



CHAPTER 13 정렬

13.1 정렬이란?

정렬 알고리즘의 분류

13.2 선택 정렬

13.3 삽입 정렬

13.4 버블 정렬

13.5 함수 포인터를 사용한 정렬

13.6 셸 정렬

13.7 병합 정렬

13.8 퀵 정렬

13.9 힙 정렬

13.10 기수정렬

13.11 정렬 알고리즘의 비교

연습문제

프로그래밍 프로젝트



CHAPTER 14 탐색

14.1 탐색이란?

맵 이란?

14.2 정렬되지 않은 배열에서의 탐색

순차 탐색

14.3 정렬된 배열에서의 탐색

이진 탐색

색인 순차 탐색

보간 탐색

14.4 해싱을 이용한 탐색

14.5 해시 함수

14.6 해싱의 오버플로 처리 방법

선형 조사법

체이닝

해싱의 성능 분석

해싱과 다른 탐색 방법의 비교

연습문제

프로그래밍 프로젝트