자료구조 (2학기)

강태원 , 정광식 지음

한국방송통신대학교출판문화원 2023년 09월 01일 출간 종이책 : 2023년 07월 25일 출간

작품소개

책소개

프로그램이 구조물이라면 ‘자료구조’는 블록입니다. 적당한 블록이 없다면 원 하는 것을 만들 수 없거나 아주 불편하고 복잡한 과정으로 만들 수밖에 없을 것입니다. 그리고 그 결과물 역시 아름답지 않을 것입니다. 마찬가지로 자료구조를 잘 알지 못하면 효율적인 프로그램을 원하는 대로 만들 수 없습니다. 이 교재는 프로그램이라는 구조물을 만드는 데 사용하는 자료구조라는 블록의 생김새와 기능을 설명하는 것입니다. 자료구조에서 다뤄야 할 다양한 추상 자료형과 구체적 프로그램 코드를 긴밀하게 연결해 설명하려고 노력했습니다. 이 교재는 대학의 학부과정에서 반드시 이해해야 하는 내용을 15주의 학습 기간에 맞추어 다섯 부분으로 나누어 구성했습니다.
첫 번째 부분은 자료구조의 의미와 개념, 그리고 자료구조의 가장 중심 개념인 추상화에 대해서 설명합니다.
두 번째 부분은 프로그래밍 언어에서 기본적으로 제공하거나 정의하여 사용하는 자료구조와 그것들을 여러 개 붙여서 사용하는 배열에 대해서 다룹니다. 즉, 가장 기초적인 블록에 대해 설명합니다.
세 번째 부분은 프로그래머가 스스로 정의하여 사용하는 자료구조인 스택, 큐, 리스트와 그것의 응용을 담았습니다. 쉽게 풀이하자면 몇 개의 블록을 조합하여 특수하게 작동하는 새로운 블록을 만드는 것과 그것이 특별한 구조물을 만들 때 어떻게 편리하게 사용되는지 설명합니다.
마지막 두 부분은 비선형 자료구조라 불리는 것들을 다룹니다. 이 자료구조 들은 대상의 관계를 컴퓨터에 표현하는 것을 가능하게 하는 강력한 도구입니다. 레고로 비유하자면 이것들은 많은 구조물을 만드는 데 자주 사용하는 블록 덩어리와 같습니다. 다소 복잡하지만 진짜 그럴싸한 구조물, 즉 작품을 만드는 데 꼭 필요한 블록 구조물이라고 생각하면 됩니다. 구체적 내용으로 먼저 자료들 사이의 계층 관계를 표현하는 트리구조를 쉽고 상세하게 설명합니다. 여기에는 트리의 기본 개념과 여러 용어부터 스레드, 힙, 선택트리, 숲, 이진 트리와 이진 탐색 트리(BS), Splay, AVL, BB, 다양한 멀티웨이 탐색 트리 등이 포함됩니다. 마지막으로 세상의 많은 것을 추상화할 수 있는 그래프와 그래프를 순회하는 방법에 대해서 배웁니다.

목차

제1장 자료구조란 무엇인가

1. 자료와 정보

2. 추상화

3. 자료구조

4. 자료구조와 알고리즘의 관계 및 알고리즘의 특성

5. 알고리즘의 성능



제2장 배 열

1. 배열의 정의

2. 배열의 추상 자료형

3. 배열의 연산의 구현

4. 1차원 배열

5. 배열의 확장

6. 희소행렬의 개념



제3장 스 택

1. 스택의 개념

2. 스택의 추상 자료형

3. 스택의 응용

4. 스택의 연산

5. 사칙연산식의 전위 ㆍ 후위 ㆍ 중위 표현



제4장 큐

1. 큐의 개념

2. 큐의 추상 자료형

3. 큐의 응용

4. 배열을 이용한 큐의 구현

5. 원형 큐



제5장 연결 리스트

1. 리스트의 개념

2. 배열을 이용한 리스트의 구현

3. 포인터를 이용한 리스트의 구현

4. 포인터 변수

5. 연결 리스트에서 노드의 삽입과 삭제

6. 연결 리스트의 여러 가지 연산 프로그램



제6장 연결 리스트의 응용

1. 연결 리스트의 변형

2. 원형 연결 리스트

3. 이중 연결 리스트



제7장 트 리

1. 트 리

2. 용어와 논리적 표현 방법 163

3. 추상 자료형

4. 이진 트리

5. 이진 트리 연산

5.2. 이진 트리 생성, 삽입, 삭제

6. 일반 트리를 이진 트리로 변환



제8장 스레드 트리

1. 스레드 트리

2. 스레드 트리 구현

3. 스레드 트리 순회, 삽입, 삭제



제9장 힙

1. 우선순위 큐

2. 힙 추상 자료형

3. 힙에서 삭제 및 삽입 연산



제10장 선택 트리, 숲, 이진 트리 개수

1. 선택 트리

2. 숲

3. 이진 트리 개수



제11장 BS, Splay, AVL, BB

1. 이진 탐색 트리(BS 트리)

2. Splay, AVL, BB 트리



제12장 멀티웨이 탐색 트리 Ⅰ

1. m원 탐색 트리

2. B 트리

3. B*, B+ 트리



제13장 멀티웨이 탐색 트리 Ⅱ

1. 2-3 트리

2. 2-3-4 트리

3. 레드 블랙 트리



제14장 그래프 Ⅰ

1. 개념 및 용어

2. 추상 자료형

3. 그래프 표현법



제15장 그래프 Ⅱ

1. 그래프 탐색

2. 최소 신장 트리

작가정보

저자(글) 강태원

연세대학교 수학과 졸업

고려대학교 전산과학과 졸업

고려대학교 대학원 수학과 전산학전공(이학석사)

고려대학교 대학원 컴퓨터학과(이학박사)

캐나다 Thompson Rivers University 방문교수

ㆍ현재: 강릉원주대학교 컴퓨터공학과 교수

저자(글) 정광식

고려대학교 컴퓨터학과 졸업

고려대학교 대학원 컴퓨터학과(이학석사, 이학박사)

영국 University College London Research Fellow

삼성 SDS(주) 책임컨설턴트

ㆍ현재: 한국방송통신대학교 컴퓨터과학과 교수