C++로 구현한 위상정렬 (Topological Sorting)

소개

C++을 이용하여 구현한 위상정렬입니다.
위상정렬을 위한 그래프는 Linked List와 Array List로 각각 따로 소스를 첨부하였습니다.
그래프, 리스트, 스택, 리스트 반복자 등의 클래스를 각각 모두 따로 작성하여
보다 객체 지향적으로 작성했습니다.

목차

없음

본문내용

1. 프로그램 설명서
1) 주요 알고리즘 / 자료구조 / 기타
- 주요 알고리즘 : 그래프를 탐색하여 직전선행자가 없는 정점들을 하나씩 제거해 나가면서 리스트에 저장하여 순서대로 출력한다.
- 자료구조 : 위상정렬을 위한 그래프, 그래프를 위한 리스트, 스택이 필요하다.

2) 함수 설명서
① List 클래스 함수
- List(): 생성자, 리스트 자료 수와 헤드를 초기화
- ~List() : 소멸자, 리스트의 각 노드를 제거
- void Insert(ITEM v) : 리스트에 아이템을 삽입(INSERT)하는 함수
- void PrintLIST() : 리스트를 순서대로 출력하는 함수
- void Delete_LinkedNodes(NODE *head) : 리스트의 각 노드를 제거하는 함수, LinkedList에서만사용
- int Length() : 리스트 자료 개수를 반환하는 함수
- bool IsEmpty() : 리스트가 비었는지 확인하는 함수
- bool IsFull() : 리스트가 비었는지 확인하는 함수, ArrayList에서만 사용
② ListIterator 클래스 함수
- ListIterator(List* list) : 생성자, 반복자를 초기화하는 함수
- VERTEX GetCurItem() : 현재 위치의 아이템 반환 함수
- void Begin() : 반복자를 첫 위치로 설정하는 함수 (생성자와 별개)
- void Next() : 반복자를 다음 위치로 이동하는 함수
- bool End() : 반복자가 끝인지 조사하는 함수

참고자료

· 없음