[자료구조][C++]원형 리스트

소개

*문제개요*
정수 계수를 가진 일원 다항식들을 표현하고 관리하는 연결 할당 시스템을 설계하고 작성하라. 헤드 노드를 가진 원형 연결 리스트를 사용하라. 다항식의 각 항은 노드로 표현되면, 이 시스템에서 노드는 세 개의 데이터 멤버(지수,계수,링크)를 가진다. 다항식을 효과적으로 제거하기 위해 이 절에서 설명한 가용 공간 리스트와 관련된 함수들을 사용하라. 일원 다항식의 입력, 출력을 위한 외부 표현은 연속된 정수들로 가정한다.

목차

1. 문제 개요
2. 알고리즘
3. 소스 및 주석
4. 결과화면
5. 느낀점

본문내용

(1)원형리스트
▪ 단순 연결 리스트(체인)에서 마지막 노드의 link필드가 첫 번째 노드를 가리키게 하면 원형 리스트가 된다.
① 포인터 current가 원형 리스트의 마지막 노드를 가리키는지 검사(current->link==first)
② 원형리스트에 대한 삽입, 삭제 알고리즘에서는 마지막 노드의 link 필드가 첫 번째 노드를 가리키는지 반드시 확인
▪ 노드 삽입

(2)다항식
▪ 템플리트 클래스를 이용
▪ 리스트 템플리트 Type은 struct term으로 구체화(term의 데이터 멤버가 공용)
▪ term은 coef와 exp로 구성
▪ av를 삭제된 노드 체인을 가리키는 ListNode<Type>* 타입인 CircList<Type>의 정적 클래스 멤버라 한다. 이 리스트를 가용 공간 리스트라 표현한다. 초기에는 av=0이다. 그래서 new나 delete 명령 대신에 함수 CircList::GetNode와 CircList::RetNode를 사용한다.
▪ 함수 CircList<Type>::~CircList를 사용하여 리스트의 노드 수에 관계없이 일정 시간에 원형 리스트를 제거한다.
▪ 제로다항식을 특별한 경우로 처리해야 하는 문제점이 발생하기 때문에 이런 경우를 만들지 않게 하기 위해 각 다항식은 헤드 노드(head node)를 갖도록 한다. 즉, 제로 다항식과 제로가 아닌 다항식 모두 부가적인 노드를 갖게 하는 것이다. 이 노드의 exp와 coef 데이터 멤버는 의미가 없다. 초기화 시킬 때 exp = -1, coef = 0으로 둔다.

참고자료

· 파일 실험 테스트 완료했습니다. 파일 만드셔서 붙여넣기 하시면 되고요
· 혹시라도 파일 원하시는 분은 [e-mail]으로 연락주세요...
· 단, 자료 다운로드한 하신분께만 드리겠습니다.