C언어에 의한 자료구조론

제 1 장 소개
1.1 자료구조와 알고리즘
1.2 자료의 추상화와 프로그램의 설계
1.3 추상 자료형
1.4 알고리즘 분석
1.4.1 알고리즘의 효율성과 복잡도 함수
1.4.2 차수 표기법
1.5 재귀 알고리즘과 반복 알고리즘
1.5.1 계승 함수
1.5.2 피보나치 수
1.5.3 하노이탑
● 연습문제

제 2 장 기본 자료 구조
2.1 선형 리스트
2.1.1 선형 리스트의 정의
2.1.2 선형 리스트상의 연산
2.1.3 배열
2.1.4 배열의 구현
2.1.5 배열의 응용 : 다항식
2.2 스택과 큐
2.2.1 스택
2.2.2 큐
2.2.3 다중 스택
2.2.4 스택의 활용
2.2.4.1 시스템 스택
2.2.4.2 연산식의 계산
2.2.4.3 중위 표기의 후위 표기 변환
2.3 연결 리스트
2.3.1 연결 리스트의 개념
2.3.2 연결 리스트의 구현 방법
2.3.2.1 배열을 이용한 연결 리스트의 구현
2.3.2.2 포인터와 동적 메모리 할당
2.3.2.3 포인터를 이용한 연결 리스트의 구현
2.3.3 연결 리스트를 이용한 스택과 큐의 구현
2.3.4 환형 연결 리스트
2.3.5 이중 연결 리스트
2.3.6 연결 리스트의 활용 : 다항식의 계산
2.3.6.1 연결 리스트를 이용한 다항식의 표현
2.3.6.2 연결 리스트의 메모리 관리
2.3.6.3 환형 연결 리스트를 이용한 다항식의 표현
● 연습문제

제 3 장 트리
3.1 기본적인 용어 정의
3.1.1 트리의 표현
3.1.2 k차 트리의 2차 트리(이진 트리) 표현
3.2 이진 트리
3.2.1 이진 트리의 표현
3.3 이진 트리의 운행법
3.3.1 중순위 운행법
3.3.2 전순위 운행법
3.3.3 후순위 운행법
3.3.4 레벨 순위 운행법
3.3.5 포리스트
3.4 트레드된 이진 트리
3.5 이진 탐색 트리
3.5.1 이진 탐색 트리에 대한 탐색
3.5.2 이진 탐색 트리에 대한 노드의 삽입
3.5.3 이진 탐색 트리의 노드 제거
3.5.4 이진 탐색 트리의 높이
3.6 트리를 이용한 집합의 Union-Find연산
3.7 서로 다른 이진 트리의 수
3.8 힙
3.8.1 삽입 연산
3.8.2 최소값 제거 연산
3.9 이항 큐
3.9.1 이항 큐의 연산
3.9.2 이항 큐의 구현
● 연습문제

제 4 장 그래프와 유향그래프
4.1 그래프의 기본 정의
4.2 그래프의 표현 방법
4.2.1 인접 행렬
4.2.2 인접 리스트
4.3 그래프의 운행법
4.3.1 깊이우선 탐색과 너비우선 탐색
4.3.2 그래프의 연결 성분
4.4 그래프의 이중 연결 성분
4.5 최소 스패닝 트리
4.5.1 Prim의 알고리즘
4.5.2 Kruskal의 알고리즘
4.6 최단 경로와 도달 가능 행렬
4.6.1 단순 원천 최단 경로
4.6.2 도달 가능 행렬과 모든 쌍 최단 경로
4.7 유향 그래프의 위상 정렬
4.8 그래프의 응용
4.8.1 사각틀 고정 문제
4.8.2 신호등 제어 문제
4.8.3 회전 드럼 문제
● 연습문제

제 5 장 정 렬
5.1 정렬의 정의
5.2 기본적인 정렬 방법
5.2.1 선택 정렬
5.2.2 삽입 정렬
5.2.3 교환 정렬
5.3 퀵 정렬
5.4 힙 정렬
5.5 병합 정렬
5.6 결정 트리와 정렬 문제 복잡도의 하한선
5.7 기타 정렬
5.7.1 래딕스 정렬
5.7.2 외부 정렬
5.7.2.1 외부 정렬의 기본개념
5.7.2.2 다중 병합(multiway merging)
5.7.2.3 다상 정렬(polyphase sorting)
5.7.2.4 허프만 트리를 이용한 병합
● 연습문제

제 6 장 집합과 탐색
6.1 집합의 기본적인 표현과 연산
6.1.1 비트벡터에 의한 표현
6.1.2 연결 리스트에 의한 표현
6.2 선형 탐색과 자가조직(self-organizing) 리스트
6.3 이진 탐색과 그의 변형
6.4 최적 이진 탐색 트리
6.5 높이 균형 이진 트리 (AVL트리)
6.6 2-3 트리와 B-트리
6.6.1 2-3 트리의 탐색
6.6.2 2-3 트리의 삽입
6.6.3 2-3 트리의 제거
6.7 해슁(Hashing)
6.7.1 해쉬 함수
6.7.2 오버플로우의 처리
6.7.3 동적 해슁(dynamic hashing)
● 연습문제
● 찾아보기