C로 배우는 자료구조 (알고리즘 공부를 위한 실전적 자료구조)

홍지만지음

출간작으로『C로배우는자료구조』등이있다.

ChapterI자료구조공부를위한프로그래밍과수학기초
A.C프로그래밍기초
1.배열(Array)
(1)정적배열
(2)동적배열
2.포인터변수와포인터연산
3.구조체(Structure)와공용체(Union)
(1)구조체의정의
(2)공용체
4.문자열
(1)응용1.문자열삽입프로그램
(2)응용2.문자열패턴매칭프로그램
(3)응용3.strcat()을사용하지않고두개의문자열을합치는프로그램
(4)응용4.문자열을역순으로출력하는프로그램
(5)응용5.문자열에서특정문자의출현빈도확인하는프로그램
(6)응용6.strcpy()를사용하지않고문자열을복사하는프로그램

B.수학기초
1.조합론적원리
2.지수와로그(ExponentialsandLogarithms)
3.합계와반복
4.점진적표기법
5.랜덤화와확률(RandomizationandProbability)
Exercise

ChapterII자료구조기본개념
1.자료구조용어정리
(1)문제,알고리즘,프로그램
(2)데이터와자료구조
2.자료구조와ADT
3.알고리즘의성능분석과복잡도(Complexity)
(1)시간복잡도
(2)공간복잡도
4.점근적알고리즘분석과점근표기법(????????????asymptoticnotation)
(1)????(BigOh)
(2)????(Omega)
(3)????(Theata)
(4)????????????의관계
(5)????(BigOh)기반의시간복잡도클래스
5.최적의알고리즘
6.대표적인문제들의복잡도
7.병합정렬
8.자료구조:데이터의조직
Exercise

ChapterIII재귀(Recursion)
1.재귀의기본개념
2.재귀와반복의차이
3.재귀의일반적인오류
(1)베이스케이스생략오류
(2)스택오버플로우
(3)진행실패
4.재귀의복잡도
5,응용:힐버트곡선(HilbertCurve)문제
Exercise

ChapterIV연결리스트(LinkedList)
1.단일연결리스트
(1)노드와노드구조체
(2)연결리스트의정의와시작
(3)연결리스트의삽입
(4)연결리스트의삭제
(5)응용1.간단한다항식프로그램
(6)응용2.이중연결리스트를활용한다항식프로그램
2.이중연결리스트(DoublyLinkedList)
(1)이중연결리스트(DoubleLinkedList)를위한노드구조체
(2)이중연결리스트에노드삽입
(2)이중연결리스트에서노드삭제
(3)응용1.이중연결리스트를활용한프로그램
3.환형연결리스트(CircularlyLinkedList)
(1)응용1.이중연결리스트를활용한프로그램
Exercise

ChapterV스택(Stack)
1.스택기본연산
(1)스택의원소정의와초기화
(2)스택이비어있는지가득차있는지검사
(3)push()
(4)pop()
(5)스택의오류처리
(6)동적배열을사용하는스택구현
2.응용
(1)응용1.하노이타워(TowerofHanoi)
(2)응용2.N-퀸문제(N-QueensProblem)
(3)응용3.수식표기법의변환
3.연결스택
(1)연결스택의구조
Exercise

ChapterVI큐(Queue)
1.배열을사용한큐의구현
2.정적배열을이용한환형큐(CircularQueue)
3.동적배열을이용한환형큐
4.연결리스트를이용한큐
Exercise

ChapterVII트리(Tree)
1.트리의표현
2.이진트리(BinaryTree)
(1)이진트리의분류
(2)이진트리의구현
(3)이진트리의순회(BinaryTreeTraversal)
3.힙트리(heaptree)
(1)최대힙에서삽입
4,우선순위큐(priorityqueue)
(1)정적배열을이용한우선순위큐구현
(2)힙을이용한우선순위큐구현
(3)이진탐색트리를이용한우선순위큐구현
5.힙정렬(HeapSort)
6.이진탐색트리(BinarySearchTree,BST)
7.선택트리(SelectionTree)
(1)승자트리(winnertree)
(2)패자트리(losertree)
8.포리트리
Exercise

ChapterVIII정렬
1.버블정렬(BubbleSort)
2.선택정렬(SelectionSort)
3.삽입정렬(InsertionSort)
4.합병정렬(MergeSort)
5.퀵정렬(QuickSort)
(1)삼분할퀵정렬
(2)랜덤화퀵정렬
(3)쓰리미디언퀵정렬
(4)비재귀적퀵정렬
(5)중앙피벗퀵정렬
6.힙정렬(HeapSort)
7.기수정렬(RadixSort)
8.정렬프로그램통합
Exercise

ChapterIX해싱
1.정적해싱(StaticHashing)
(1)해시테이블의예
(2)해시함수
(3)해시함수의종류
(4)충돌(Overflow)처리
2.동적해싱
(1)디렉터리를사용하는동적해싱
(2)디렉터리를사용하지않는동적해싱
Exercise

ChapterX탐색(Searching)
1.순차탐색(SequentialSearch)
2.이진탐색(BinarySearch)
3.색인순차탐색(IndexedSequentialSearch)
4.보간탐색(InterpolationSearch)

ChapterXI이진탐색트리(BinarySearchTree)
1.AVL(AdelsonVelskyLandis)트리
(1)LL회전(Left-LeftRotation)
(2)LR회전(Left-RightRotation)
(3)RR회전(Right-RightRotation)
(4)RL회전(Right-LeftRotation)
(5)이중회전알고리즘
2.2-3트리
(1)2-3트리의삽입
(2)2-3트리의삭제
3.기타이진탐색트리
(1)2-3-4트리
(2)레드-블랙(Red-Black)트리
Exercise

ChapterXII그래프
1.그래프이론의역사와활용
2.용어
3.그래프의표현방법
4.그래프순회(GraphTraversal)
(1)깊이우선탐색(DFS,DepthFirstSearch)
(2)너비우선탐색(BFS,BreathFirstSearch)
5.최단경로알고리즘(ShortestPathAlgorithm)
(1)Dijikstra(다익스트라)의최단경로알고리즘
(2)Bellman-Ford(벨만-포드)의최단경로알고리즘
(3)Floyd(프로이드)의최단경로알고리즘
6.최소신장트리(MinimumSpanningTree)
(1)크루스칼(Kruskal)최소비용신장트리
(2)프림(Prim)의최단경로알고리즘
Exercise