제 4 장 연결 리스트.

Presentation on theme: "제 4 장 연결 리스트."— Presentation transcript:

1 제 4 장 연결 리스트

2 4.1 단순 연결 리스트 순차적 표현 연결된 비순차 표현 노드 원소들의 저장 순서가 리스트에 표현된 순서와 동일 : 배열
원소들의 저장 순서가 리스트의 표현 순서와 다를 수 있음 : 리스트 각 리스트 원소들에 대하여 다음 원소를 가리키는 포인터(pointer)를 이용 삽입, 삭제가 용이 노드 데이타 링크(포인터)

3 3-문자 리스트 : (BAT, CAT,… , WAT) data link HAT 15 1 2 CAT 4 3 EAT 9 4
first = 8 data[8] = BAT : 데이타 link[3] = 4 : 주소 data[link[3]] = EAT 5 6 WAT 7 BAT 3 8 FAT 1 9 10 VAT 7 11 .. ..

4 연결 리스트를 그리는 일반적인 방법 first BAT CAT EAT WAT

5 삽입 절차(GAT) (1) 주소가 x인 공백 노드 하나를 할당 (2) 노드 x의 data 필드에 GAT라는 값을 저장
(3) x의 link 필드에 FAT 다음 노드, 즉 HAT의 주소를 저장 (4) FAT라는 값을 가진 노드의 link 필드에 x를 저장 note : GAT를 삽입하기 위하여 리스트의 다른 항목들을 이동시킬 필요가 없음

6 노드 삽입 HAT CAT EAT GAT WAT BAT FAT VAT 15 4 9 1 3 5 7 2 6 8 10 11 data
3 5 7 2 6 8 10 11 data link (a) Data[5]에 GAT 삽입 (b) 리스트에 노드 GAT 삽입 BAT first CAT EAT FAT HAT GAT x

7 삭제 GAT 바로 앞에 있는 원소 FAT의 주소, link[9]의 값을 HAT의 주소로 변경 리스트에서 GAT 삭제 first
BAT CAT EAT FAT GAT HAT WAT 리스트에서 GAT 삭제

8 4.2 C++에서 리스트 표현법 C++에서 리스트 노드 정의 리스트 구조를 위한 노드 구조
class ThreeLetterNode { private: char data[3]; ThreeLetterNode *link; }; class nodea { int data1; char data2; float data3; nodea *linka; nodeb *linkb; } ; class nodeb int data; nodeb *link; 55 ‘c’ 22 3.14 data1 data2 data3 linka linkb data link nodea nodeb 노드 구조 nodea와 nodeb에 대한 예

9 C++에서 리스트 설계 설계 1 ThreeLetterNode *first;
전역변수 first->data, first->link first를 이용한 데이타 멤버 참조 first->data[0], first->data[1], first->data[2] 데이타 멤버 data의 요소를 참조 캡슐화 원칙과 컴파일 오류 data와 link는 private로 선언 → first로 접근 불가 *first first->data first first->data[0] first->data[0] first->data[0] first->link

10 C++에서 리스트 설계 설계 2 연결 리스트에서 노드의 삽입이나 삭제 등과 같이 리스트 조작 연산을 수행하는 함수에 대해서만 클래스 ThreeLetterNode의 데이타 멤버를 접근할 수 있도록 허용 다른 함수들은 직접이든 또는 간접이든 간에 클래스 ThreeLetterNode의 데이타 멤버를 접근을 금함 설계 3 단순 연결 리스트(일명 체인)로 표현 ThreeLetterNode와 ThreeLetterList라는 두 클래스를 조합하여 사용 ThreeLetterList를 ThreeLetterNode 객체로 구성  ThreeLetterList HAS-A ThreeLetterNode

11 C++에서 리스트 설계 정의 만일 개념적으로 A라는 타입이 B라는 타입을 포함하거나 또는 B가 A의 일부분인 경우, 타입 A의 객체가 타입 B의 객체에 대해 HAS-A 관계를 가지고 있다라고 하고 "타입 A의 객체 HAS-A 타입 B의 객체"라고 표기 ThreeLetterList ThreeLetterNode first BAT CAT WAT ThreeLetterList와 ThreeLetterNode 사이의 개념적 관계성

12 C++에서 리스트 설계 클래스 ThreeLetterList는 리스트의 첫 번째 노드를 지시하는 접근 포인터, first만 포함하도록 정의 클래스 ThreeLetterList를 클래스 ThreeLetterNode의 friend로 선언 ThreeLetterList ThreeLetterNode first BAT CAT WAT ThreeLetterList와 ThreeLetterNode사이의 실제 관계성

13 C++에서 리스트 설계 class ThreeLetterList; //전방 선언 class ThreeLetterNode {
friend class ThreeLetterList; private: char data[3]; ThreeLetterNode *link; }; class ThreeLetterList { public: //리스트 조작 연산 . ThreeLetterNode *first; 복합 클래스

14 C++에서 리스트 설계 중첩 클래스 하나의 클래스가 다른 클래스 정의 안에서 정의
ThreeLetterNode 객체가 클래스 ThreeLetterList의 외부로부터 접근될 수 없도록 보장 ThreeLetterNode의 데이타 멤버들은 public class ThreeLetterList { public: //리스트 조작 연산 . private: class ThreeLetterNode{ //중첩 클래스 char data[3]; ThreeLetterNode *link; }; ThreeLetterNode *first;

15 C++에서 포인터 조작 생성: new 사용 삭제: delete 사용 포인터 변수에 널 포인터 상수인 0을 지정
예) ThreeLetterNode* f; nodea* y; nodeb* z; f = new ThreeLetterNode; y = new nodea; z = new nodeb; 삭제: delete 사용 예) delete f; delete y; delete z; 포인터 변수에 널 포인터 상수인 0을 지정 포인터(메모리 주소) 출력: cout 사용 x a a x b x y b b y b y (a) (b) x = y (c) *x = *y 포인터 지정의 효과

16 리스트 조작 연산 포인터 조작 연산을 이용한 리스트 연산 구현 ListNode 타입의 두 노드로 구성된 연결 리스트 생성
class List; class ListNode { private: int data; ListNode *link; }; void List::Create2(){ first = new ListNode(10); //첫 번째 노드의 생성 및 초기화 //두 번째 노드를 생성하고 초기화해서 //그 주소를 first->link에 저장한다. first->link = new ListNode(20); } ListNode::ListNode(int element = 0){ //ListNode의 생성자에서의 0은 묵시 인자 data = element; link = 0; //NULL 포인터 상수

17 리스트 조작 연산 2-노드 리스트 공백 리스트와 공백이 아닌 리스트에서의 노드 삽입 10 20 first
first void List::Insert50(ListNode *x) { ListNode *t = new ListNode(50); //새 노드의 생성 및 초기화 if(!first) //공백 리스트에 삽입 first = t; return; //List::Insert50 종료 } //x 다음에 삽입한다 t->link = x->link; x->link = t;

18 리스트 조작 연산 공백 리스트와 공백이 아닌 리스트에서의 노드 삽입 리스트로부터 노드 삭제 50 first x t (b)
first x t (b) (a) void List::Delete(ListNode *x, ListNode *y) //y는 x 앞의 노드 { if(!y) first = first->link; else y->link = x->link; delete x; //노드의 반납 }

19 4.3 재사용가능한 연결 리스트 클래스 연결 리스트 - 컨테이너 클래스 : 템플리트가 적절 연결 리스트의 템플리트 정의
정수로 구성된 공백 연결 리스트 정의 List<int> intlist; template <class Type> class List; // 전방 선언 template <class Type> class ListNode { friend class List<Type>; private: Type data; ListNode *link; }; class List { public: List() first = 0;; // first를 0으로 초기화하는 생성자 // 리스트 조작 연산들 . ListNode<Type> *first; List<type>이 ListNode<Type>의 friend first는 ListNode<Type> 객체에 대한 포인터로 선언

20 연결 리스트 반복자 반복자(iterator): 컨테이너 클래스의 모든 원소를 순회하는데 사용되는 객체
사용 대상 연산(클래스 C) (1) C에 포함된 모든 정수를 인쇄하라. (2) C에 포함된 모든 정수의 최대값, 최소값, 평균값, 중간값을 계산하라. (3) C에 포함된 모든 정수의 합, 곱, 제곱의 합을 계산하라. (4) C에 포함된 모든 정수 중에서 어떤 성질 P를 만족하는 것을 검색하라(예를 들어, P는 양수, 어떤 정수의 제곱 등이 될 수 있다). (5) 어떤 함수 f(x)의 값이 최대값이 되는 C의 원소 x를 찾아라. 코드 형태 초기화 과정; for C의 각 원소에 대해{ current = C의 현재 원소; 본체; } 후처리 과정;

21 연결 리스트 반복자 단점 별도로 ListIterator<Type> 클래스 정의
List<Type>은 템플리트 클래스이므로, 그의 모든 연산은 Type이 인스턴스화되는 객체의 타입과는 독립적이어야 한다. List<Type>이 지원하는 연산이 매우 많다. 컨테이너 클래스 순회 방법을 배워야 한다. 별도로 ListIterator<Type> 클래스 정의 ListIterator <Type>은 List<Type>과 ListNode<Type>의 friend로 선언 ListIterator<Type>의 객체는 그것과 연관될 List<Type> 객체의 이름 l로써 초기화 ListIterator<Type>객체는 ListNode<Type>* 타입의 private 데이타멤버 current를 포함하고 항상 리스트 l의 한 노드를 가리키게 함 ListIterator<Type> 객체에서는 l의 원소에 대해 다양한 검사와 검색을 수행하기 위해 public 멤버 함수로 NotNull(), NextNotNull(), First(), Next()를 정의

22 연결 리스트 반복자 연결 리스트 재구현 enum Boolean { FALSE, TRUE } ;
연결 리스트 재구현 enum Boolean { FALSE, TRUE } ; template <class Type> class List; template <class Type> class ListIterator; template <class Type> class ListNode { friend class List<Type>; friend class ListIterator<Type>; private: Type data; ListNode *link; }; template <class Type> class List { friend class ListIterator<Type>; public: List() first = 0;; // 리스트 조작 연산들 ListNode<Type> *first; template <class Type> class ListIterator { ListIterator(const List<Type> &l): list(l), current(l.first) ; Boolean NotNull(); Boolean NextNotNull(); Type* First(); Type* Next(); const List<Type> &list; //기존의 리스트를 참조한다. ListNode<Type> *current; // list의 한 노드를 가리킨다. } ;

23 연결 리스트 반복자 ListIterator <Type>의 멤버함수 정의
template <class Type> // list의 현재 원소가 null이 아닌지 검사한다. Boolean ListIterator<Type>::NotNull() { if(current) return TRUE; else return FALSE; } template <class Type> // list의 다음 원소가 null이 아닌지 검사한다. Boolean ListIterator<Type>::NextNotNull() { if(current && current->link) return TRUE; template <class Type> // list의 첫 번째 원소에 대한 포인터를 반환한다. Type* ListIterator<Type>::First() { if(list.first) return &list.first->data; else return 0; template <class Type> // list의 다음 원소에 대한 포인터를 반환한다. Type* ListIterator<Type>::Next() { if(current) { current = current->link; return &current->data;

24 연결 리스트 반복자 반복자를 이용한 원소의 합 계산
Note : List<Type>이나 ListNode<Type>의 전용 데이타 멤버를 접근 안함 int sum(const List<int>& l) { Listiterator<int> li(l); // li는 리스트 l과 연관된다. if(!li.NotNull()) return 0; // 공백 리스트, 0을 반환 int retvalue = *li.First(); // 첫 번째 원소를 얻는다. while(li.NextNotNull()) // 다음 원소가 존재하는지 확인한다. retvalue += *li.Next(); // 다음 원소를 얻어서 현재의 총합에 더한다. return retvalue; }

25 연결 리스트 연산 재사용가능한 클래스에 포함될 연산 연결 리스트 연산
생성자(묵시 및 복사 생성자) 파괴자 지정 연산자(operator =) 등가 검사 연산자(operator == ) 클래스 객체 입출력 연산자 (operator>>와 operator<<를 각각 다중화) 연결 리스트 연산 삽입, 삭제, 기타 조작 연산이 필요 last : class List<Type> 전용 데이타 멤버 추가 // 리스트의 마지막 노드를 가리킴 리스트의 뒤에 노드 첨가 template<class Type> void List<Type>::Attach(Type k){ ListNode<Type>* newnode = new ListNode<Type>(k); if(first==0) first=last=newnode; else last->link = newnode; last = newnode; }

26 연결 리스트 연산 체인을 역순으로 변환하는 연산 두 체인을 접합하는 연산 template <class Type>
void List<Type>::Invert() // 체인 x = (a1, ..., an)이 x = (an, ..., a1)로 변환된다. { ListNode<Type> *p = first, *q = 0; // q는 p를 따라간다. while(p) { ListNode<Type> *r = q; q = p; // r은 q를 따라간다. p = p->link; // p가 다음 노드로 옮겨 간다. q->link = r; // q에 이전 노드를 연결한다. } first = q; template <class Type> void List<Type>::Concatenate(List<Type>b) // this = (a1, ..., am)과 b = (b1, ..., bn), m, n0 // 으로부터 새로운 체인 z = (a1, ..., am, b1, ..., bn)을 생성한다. { if(!first) { first = b.first; return; } if(b.first) { for(ListNodt<Type> *p = first; p->link; p = p->link); p->link = b.first; }

27 클래스의 재사용 필요한 경우에만 재사용 클래스의 재사용보다 새로 설계하는 유리한 경우
(1) 클래스(C1)를 재사용하여 다른 클래스(C2)를 구현하는 것보다 (C2를) 직접 구현하는 것이 더 효율적일 때 (2) 응용에서 요구하는 연산이 복잡하고 특수한 것이어서 재사용 클래스에서 지원하지 못하는 경우

28 4.4 원형 리스트 원형 리스트(circular list) 원형 리스트 원형 리스트 예
단순 연결 리스트(체인)에서 마지막 노드의 link 필드가 첫 번째 노드를 가리킴 마지막 노드 : current->link == first 원형 리스트 원형 리스트 예 BAT CAT EAT first WAT x1 x2 x3 first data link

29 원형 리스트 원형 리스트의 마지막 노드를 가리킴 맨 앞에 삽입 x1 x2 x3 data link last
template <class Type> void CircList::InsertFront(ListNode <Type> *x) // x가 가리키는 노드를 원형 리스트 this의 앞에 삽입한다. // last는 리스트의 마지막 노드를 가리킨다. { if(!last) { // 공백 리스트 last = x; x->link = x; } else { x->link = last->link; last->link = x;

30 원형 리스트 헤드 노드를 사용하는 원형 리스트 BAT CAT EAT WAT first (a) 공백 원형 리스트 (b)

31 4.5 연결 리스트를 이용한 스택과 큐 표현 연결 스택과 큐 표현 생성자 공백 Stack : top을 0으로 초기화
공백 Queue : front를 0으로 초기화 data link front rear top (a) 연결 스택 (b) 연결 큐

32 스택 클래스 정의 class Stack; // 전방 선언 class StackNode { friend class Stack;
private: int data; StackNode *link; StackNode(int d = 0, StackNode *l = 0) : data(d), link(l) ; // 생성자 }; class Stack { public: Stack() top = 0; ; // 생성자 void Add(const int); int* Delete(int&); StackNode *top; void StackEmpty();

33 연결 스택의 삽입 연결 스택에서의 제거 void Stack::Add(const int y) {
top = new StackNode(y, top); } int* Stack::Delete(int& retvalue) //스택에서 톱 노드를 지우고 그 데이타에 대한 포인터를 반환 { if(top==0)StackEmpty();return 0; //널 포인터 상수를 반환 StackNode* x = top; retvalue = top->data; //톱 노드의 data 필드를 가져옴 top = x->link; //톱 노드 제거 delete x; //노드 해방 return &retvalue; // 포인터를 데이타로 반환 }

34 연결 큐에서의 삽입 연결 큐에서의 제거 void Queue::Add(const int y) {
if(front==0) front=rear=new QueueNode(y,0); //공백 큐 else rear=rear->link=new QueueNode(y,0); //노드를 붙이고 rear를 수정함 } int* Queue::Delete(int& retvalue) //큐에 있는 첫번째 노드를 제거하고 그 데이타의 포인터를 반환 { if(front==0) QueueEmpty(); return 0; QueueNode* x=front; retvalue=front->data; //데이타를 얻음 front=x->link; //앞의 노드를 제거 delete x; //노드 해방 return &retvalue; }

35 4.6 다항식의 연결 리스트 표현 클래스 Polynomial 연결리스트 template class 사용
다항식은 리스트로 표현되기 떄문에, Polynomial은 List에 IS-IMPLEMENTED-BY 관계 연결리스트 template class 사용 타입 : struct term

36 다항식의 연결 리스트 표현 Polynomial 클래스의 정의 struct Term
// Term의 모든 멤버는 묵시적으로 public { int coef; // 계수 int exp; // 지수 void Init(int c, int e) coef = c; exp = e; ; }; class Polynomial friend Polynomial operator+(const Polynomial&, const Polynomial&); private: List<Term> poly;

37 다항식의 연결 리스트 표현 3x14+ 2x8 +1과 8x14 + 3x10 + 10x6의 다항식 표현 3 14 2 8 1
a.first -3 10 6 b.first (a) (b)

38 다항식의 덧셈 덧셈 알고리즘 두 다항식 a, b 만일 두 항의 지수가 같으면 계수를 더해서 그 합이 0이 아니면 결과 다항식 c에 새로운 항을 만든다. 만약 b의 현재 항의 지수보다 a의 현재 항의 지수가 작으면, b의 항과 똑같은 항을 만들어 결과 다항식에 첨가 새로운 노드의 첨가를 위해 List::Attach()를 사용 다항식 덧셈 알고리즘 operator+()

39 다항식의 덧셈 C=a+b의 처음 세 항을 생성 3 14 2 8 1 a -3 10 6 b 11 c p q
a -3 10 6 b 11 c p q (i) p->exp == q->exp (iii) p->exp > q->exp (ii) p->exp < q->exp C=a+b의 처음 세 항을 생성

40 Polynomial operator+(const Polynomial& a, const Polynomial& b) {
// 다항식 a와 b를 더하여 그 합을 반환 Term *p, *q, temp; ListIterator<term> Aiter(a.poly); ListIterator<term> Biter(b.poly); Polynomial c; p = Aiter.First(); q = Biter.First(); // a와 b의 첫 번째 노드를 가져옴 while (Aiter.NotNull() && Biter.NotNull()) { //현재의 노드가 널이 아님 switch (compare(p->exp,q->exp)) { case '=': int x = p->coef + q->coef; temp.Init(x,q->exp); if (x) c.poly.Attach(temp); p = Aiter.Next(); q = Biter.Next(); // 다음 항으로 진행 break; case '<': temp.Init(q->coef,q->exp); c.poly.Attach(temp); q = Biter.Next(); // b의 다음 항 case '>': temp.Init(p->coef,p->exp); c.poly.Attach(temp); p = Aiter.Next(); // a의 다음 항 } while (Aiter.NotNull()) { // a의 나머지를 복사 p = Aiter.Next(); while (Biter.NotNull()) { // b의 나머지를 복사 q = Biter.Next(); return c;

41 다항식의 덧셈 operator+에서 총 연산 시간에 영향을 미치는 연산 계수 덧셈의 횟수 지수 비교 회수는 m+n을 경계
(1) 계수 덧셈 (2) 지수 비교 (3) 가용 공간에 대한 첨가/삭제 (4) c를 위한 새로운 노드 생성 계수 덧셈의 횟수 0  계수 덧셈의 횟수  min{m.n} 지수 비교 회수는 m+n을 경계 operator+()에서 명령문들의 최대 수행 회수는 m+n 연산 시간은 O(m+n)이다.

42 다항식의 제거 d(x)=a(x)*b(x)+c(x)를 계산하고 출력하는 함수 void func() {
Polynomial a,b,c,d,t; cin >> a; // 다항식을 읽고 생성함 cin >> b; cin >> c; t = a * b; d = t + c; cout << d; }

43 다항식의 제거 메모리 문제 (a) (b) Polynomial List<Term> poly
first Polynomial ListNode<Term> List<Term> poly (a) (b) (a) 다항식 객체가 범위를 벗어나기 전 (b) 다항식 객체가 범위를 벗어난 후

44 다항식의 제거 파괴자(destructor) template <class Type>
List<Type>::~List() // 체인의 모든 노드를 해방 { ListNode<Type>* next; for (; first; first = next) { next = first->link; delete first; }

45 다항식의 원형 리스트 표현 ptr=3x14+2x8+1의 원형 리스트 표현
가용 공간 리스트(available space list) 삭제된 노드를 체인으로 유지 새로운 노드가 필요하면 이 리스트에서 할당 공백일 때는 함수 new를 이용하여 새로운 노드를 생성 first 3 14 2 8 1

46 다항식의 원형 리스트 표현 노드 하나를 얻음 노드 하나를 반환 template <class Type>
ListNode<Type>* CircList::GetNode() // 사용할 노드를 제공 { ListNode<Type>* x; if(!av) x = new ListNode<Type>; else { x = av; av = av->link; } return x; } template <class Type> void CircList<Type>::RetNode(ListNode<Type>* x) // x가 가리키는 노드를 해방 { x->link = av; av = x; }

47 다항식의 원형 리스트 표현 원형 리스트의 제거 점선은 원형 리스트에서 변경을 표시 av first second
template <class KeyType> void CircList<Type>::~CircList() // first가 가리키는 원형 리스트를 제거 { if (first) { ListNode* second = first->link; // 두 번째 노드 first->link = av; // 첫 번째 노드를 av에 연결 av = second; // 리스트의 두 번째 노드가 av리스트의 첫 번째 노드가 됨 first = 0; } first av second

48 다항식의 원형 리스트 표현 헤드 노드를 가진 리스트 헤드 노드의 exp 필드를 -1로 설정 - -1 first 3 14 2 8
(a) 제로 다항식 (b) 3x + 2x + 1 헤드 노드의 exp 필드를 -1로 설정

49 Polynomial operator+(const Polynomial& a, const Polynomial& b){
Term *p, *q, temp; CircListIterator<Term> Aiter(a.poly); CircListIterator<Term> Biter(b.poly); Polynomial c; // 생성자가 exp=-1인 헤드 노드를 생성한다고 가정 p = Aiter.First(); q = Biter.First(); while (1) switch (compare(p->exp,q->exp)) { case '=': if(p->exp == -1) return c; else { int sum = p->coef + q->coef; if (sum) { temp.Init(sum, q->exp); c.poly.Attach(temp); } p = Aiter.Next(); q = Biter.Next(); break; case '<': temp.Init(q->coef,q->exp); case '>': temp.Init(p->coef,p->exp); } // end of switch and while

50 4.7 동치관계 관계  의 성질 정의 동치부류(equivalence class) (1) 반사적(reflexive)
어떠한 다각형 x에 대해서, x x가 성립 (2) 대칭적(symmetric) 어떤 두 다각형 x,y에 대해서, x y이면 y x (3)이행적(transitive) 어떤 세 개의 다각형 x, y, z에 대해서, x y이고 y z이면 x z 정의 집합 S에 대하여 관계 ≡ 가 대칭적, 반사적, 이행적이면,관계 ≡를 집합 S에 대해 동치 관계(equivalence relation). 그리고 그 역도 성립 예: = : 동일 동치부류(equivalence class) x y이면 x, y는 같은 동치부류 0≡4, 3≡1, 6≡10, 8≡9, 7≡4, 6≡8, 3≡5, 5≡11, 11≡0 { 0, 2, 4, 7, 11}, {1, 3, 5}, {6, 8, 9, 10}

51 동치 결정 알고리즘 (1) 동치 쌍(equivalence pair) (i,j)를 읽어 기억
(2) 0에서부터 0과 j가 같은 동치 부류라는 것을 나타내는(0,j) 형태의 모든 쌍을 찾는다. (j,k)가 있으면 같은 동치부류에 포함시킨다. (3) 같은 방법으로 0이 포함된 동치 부류의 모든 객체를 찾아 표시하고 출력 (4) 아직 출력되지 않은 객체가 있으면, 새로운 동치 부류이므로 같은 방법으로 수행하여 출력

52 개략적인 동치 알고리즘 void equivalence() { 초기화; while 나머지 쌍 다음 쌍 (i,j)를 읽음; 이 쌍을 처리; } 출력을 위해 초기화; for (출력이 안된 객체에 대해) 이 객체를 포함하고 있는 동치 부류를 출력; }// equivalence의 끝

53 구체적인 동치 알고리즘 m : 동치쌍의 수 n : 객체 수(0, ... , n-1)
동치쌍의 저장구조: 리스트, 노드는 data와 link seq[n]: n개의 리스트 헤드 out[n]: 출력 여부를 표현(T or F) 구체적인 동치 알고리즘 void equivalence(){ read n; // 객체의 수를 읽어들임 seq를 0으로 초기화하고 out을 FALSE로 초기화; while 나머지 쌍 // 입력 쌍 { 다음 쌍 (i,j)를 읽음; seq[i] 리스트에 j를 삽입; seq[j] 리스트에 i를 삽입; } for (i = 0; i < n; i++) if (out[i] == FALSE) { out[i] = TRUE; 객체 i를 포함하고 있는 동치 부류를 출력; }// equivalence의 끝

54 쌍들이 입력된 뒤의 리스트 11 3 5 7 8 4 6 1 10 9 2 [0] [1] [2] [3] [4] [5] [6] [7]
5 7 8 4 6 1 10 9 2 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] seq data link

55 동치부류를 찾는 프로그램 enum Boolean { FALSE, TRUE ; } class ListNode {
friend void equivalence(); private: int data; ListNode *link; ListNode(int); }; typedef ListNode *ListNodePtr; // new를 사용하여 포인터 배열을 만들 수 있음 ListNode::ListNode(int d) { data = d; link = 0;

56 void equivalence() // 동치 쌍을 입력하고, 동치 부류를 출력함 { ifstream inFile("equiv.in",ios::in); // 입력 화일 "equiv.in" if(!inFile) cerr << "Cannot open input file " << endl; return; } int i,j,n; inFile >> n; // 객체 개수를 읽음 // seq와 out을 초기화 ListNodePtr *seq = new ListNodePtr[n]; Boolean *out = new Boolean[n]; for (i = 0; i < n; i++) { seq[i] = 0; out[i] = FALSE; // 1 단계: 동치 쌍들을 입력 inFile >> i >> j; while (inFile.good()) // 화일의 끝인지 검사 ListNode *x = new ListNode (j); x->link = seq[i]; seq[i] = x; // seq[i]에 j를 첨가 ListNode *y = new ListNode (i); y->link = seq[j]; seq[j] = y; // seq[j]에 i를 첨가

57 // 2 단계: 동치 부류를 출력 for (i = 0; i < n; i++) if (out[i] == FALSE) { // 출력이 되기 위해 필요 cout << endl << " a new class: " << i; out[i] = TRUE; ListNode *x = seq[i]; ListNode *top = 0; // 스택을 초기화 while(1){ // 부류의 나머지를 찾음 while (x) { // 리스트 처리 j = x->data; if (out[j] == FALSE) { cout << "," << j; out[j] = TRUE; ListNode *y = x->link; x->link = top; top = x; x = y; } else x = x->link; } // end of while(x) if (!top) break; else { x = seq[top->data]; top = top->link; // 스택에서 제거 } //end of while(1) } // end of if (out[i] == FALSE) delete [] seq; delete [] out; } // equivalence의 끝

58 4.8 희소 행렬 표현 희소 행렬의 각 열은 헤드 노드를 가진 원형 연결 리스트로 표현
희소 행렬의 각 열은 헤드 노드를 가진 원형 연결 리스트로 표현 또한 각 행도 헤드 노드를 가진 연결 리스트 헤드 노드 down 필드: 열 리스트에 연결하는데 사용 right 필드: 행 리스트에 연결하는데 사용 next 필드: 헤드 노드들을 서로 연결 다른 노드 down 필드: 같은 열에 있는 다음 (0이 아닌)항에 연결하는데 사용 right 필드: 같은 행에 있는 다음 (0이 아닌)항과 연결 down right next head row col value f i j a ij (a) head node (b) typical node (c) set up for a

59 필요한 노드 갯수 : r개의 0이 아닌 항을 가진 n*m 희소 행렬이라면 max{n,m}+ r + 1 개
-4 -9 11 13 -8 14 12 필요한 노드 갯수 : r개의 0이 아닌 항을 가진 n*m 희소 행렬이라면 max{n,m}+ r + 1 개

60 희소 행렬 A의 연결 표현 (노드의 head 데이타 멤버는 표시되지 않았음) 7 6 11 2 13 5 14 1 -8 -4 12
2 13 5 14 1 -8 -4 12 -9 H0 H1 H2 H3 H4 H5 H6 headnode points to H6 희소 행렬 A의 연결 표현 (노드의 head 데이타 멤버는 표시되지 않았음)

61 희소 행렬의 클래스 정의 enum Boolean { FALSE, TRUE };
struct Triple { int value, row, col; }; class Matrix; // 전방 선언 class MatrixNode { friend class Matrix; friend istream& operator>>(istream&, Matrix&); // 행렬을 읽어 들이기 위해서 private: MatrixNode *down, *right; Boolean head; union { // 무명 union MatrixNode *next; Triple triple; }; MatrixNode(Boolean, Triple *); // 생성자 MatrixNode::MatrixNode(Boolean b, Triple *t) // 생성자 head = b; if (b) {right = next = this;} // 행/열 헤드 노드 else triple = *t; // headnode 또는 원소 노드 리스트에 대한 헤드 노드 } typedef MatrixNode *MatrixNodePtr; // 포인터 배열의 연속적인 생성을 위해 class Matrix{ friend istream& operator>>(istream&, Matrix&); public: ~Matrix(); // 파괴자 MatrixNode *headnode; 희소 행렬의 클래스 정의

62 희소 행렬 입력 2 // 행렬을 읽어 들이고 그것의 연결 표현을 설정한다. 3 // 보조 배열 head가 사용되었다. 4 {
1 istream& operator>>(istream& is, Matrix& matrix) 2 // 행렬을 읽어 들이고 그것의 연결 표현을 설정한다. 3 // 보조 배열 head가 사용되었다. 4 { Triple s; int p; is>> s.row >> s.col >> s.value; // 행렬의 차원 if (s.row > s.col) p = s.row; else p = s.col; // 헤드 노드의 리스트를 위한 headnode를 설정 matrix.headnode = new MatrixNode(FALSE, &s); if (p == 0) {matrix.headnode -> right = matrix.headnode; return is; } // 적어도 하나의 행 또는 열 MatrixNodePtr *head = new MatrixNodePtr[p]; // 헤드 노드를 초기화 for (int i = 0; i < p; i++) head[i] = new MatrixNode(TRUE, 0); int CurrentRow = 0; MatrixNode *last = head[0]; // 현재 행의 마지막 노드

63 희소 행렬 읽어 들이기 16 for (i = 0; i < s.value; i++) // 트리플 입력 17 {
{ Triple t; is >> t.row >> t.col >> t.value; if (t.row > CurrentRow){ // 현재 행을 닫음 last->right = head[CurrentRow]; CurrentRow = t.row; last = head[CurrentRow]; }// if문 끝 last = last->right = new MatrixNode(FALSE, &t);//새 노드를 행 리스트에 연결 head[t.col]->next = head[t.col]->next->down = last; // 열 리스트에 연결 }// for문 끝 last->right = head[CurrentRow]; // 마지막 행 닫기 for (i = 0; i<s.col; i++) head[i]->next->down = head[i];//모든 열 리스트 닫기 // 헤드 노드를 서로 연결 for (i = 0; i < p - 1; i++) head[i]->next = head[i + 1]; head[p - 1]->next = matrix.headnode; matrix.headnode->right = head[0]; delete []head; return is; 36 } 희소 행렬 읽어 들이기

64 희소 행렬 삭제 가용 공간 리스트를 이용한 파괴자 ~Matrix()의 분석: 계산 시간은 O(n+m)
Matrix::~Matrix() // 모든 노드를 av 리스트에 반환한다. 이 리스트는 right 필드를 통해서 // 연결된 체인이다. // av는 MatrixNode * 타입의 전역 변수이고 그것의 처음 노드를 가리킨다. { if (!headnode) return; // 삭제할 노드가 없음 MatrixNode *x = headnode->right, *y; headnode->right = av; av = headnode; // headnode를 반환한다. whilte (x != headnode) { // 모든 행을 지운다. y = x->right; x->right = av; av = y; x = x->next; // 다음 행 } headnode = 0; ~Matrix()의 분석: 계산 시간은 O(n+m)

65 4.9 이중 연결 리스트 이중 연결 리스트(doubly linked list) 특성
각 노드는 전방과 후방을 가리키는 두개의 링크를 가짐 - LeftLink data RightLink Head Node 특성 p == p->llink->rlink == p->rlink->llink - first 헤드 노드가 있는 이중 연결 원형 리스트

66 이중 연결 리스트 클래스 정의 이중 연결 원형 리스트에서의 삭제 class DblList; class DblListNode {
friend class DblList; private: int data; DblListNode *llink, *rlink; }; class DblList { public: // 리스트 조작 연산 DblListNode *first; // 헤드 노드를 가리킴 이중 연결 리스트 클래스 정의 void DblList::Delete(DblListNode *x) { if ( x == first ) cerr << "Deletion of headnode not permitted" << endl; else { x->llink->rlink = x->rlink; x->rlink->llink = x->llink; delete x; } 이중 연결 원형 리스트에서의 삭제

67 이중 연결 원형 리스트에서의 삭제 이중 연결 원형 리스트에 삽입 - first x Before After x p
void DblList::Insert(DblListNode *p, DblListNode *x) // 노드 p를 노드 x의 왼쪽에 삽입한다. { p->llink = x; p->rlink = x->rlink; x->rlink->llink = p; x->rlink = p; } x p

68 4.10 범용 리스트 정의 범용 리스트 A는 n 0 개 원소의 유한 순차 즉, 0 ,…, n-1 (i 는 원자(atom) 또는 리스트 원소) 원자가 아닌 원소 i (0in-1)는 A의 서브리스트 표현 리스트 A 자체는 A =(0 ,…, n-1 )라고 표기 A는 리스트 의 이름 n은 리스트의 길이 모든 리스트의 이름은 대문자로 표기 소문자는 원자를 표현 n1일 때, 0 는 A의 헤드, (1 ,…, n-1 ) A의 테일

69 범용 리스트의 예 (1) D = () : 널 또는 공백 리스트 ; 길이는 0 (2) A = (a,(b,c)) : 길이는 2
(3) B = (A,A,()) : 길이는 3 원소는 두 A와 널 리스트 (4) C = (a,C) : 길이가 2인 순환 리스트 C는 무한 리스트 C = (a,(a,(a,…) head(A) = 'a' tail(A) = ((b,c)) head(tail(A)) = (b,c) tail(tail(A)) = ()

70 범용 리스트를 이용한 다변수 다항식 표현 PolyNode 타입의 노드 정의
P(x,y,z)=x10y3z2 + 2x8y3z2 + x4y4z + 6x3y4z + 2yz ((x10 + 2x8)y3 + 3x8y2 )z2 + ((x4 +6x3)y4 + 2y)z  Cz2+Dz  C(x,y) = Ey3 +Fy2 PolyNode 타입의 노드 정의 enum Triple { var, ptr, no }; class PolyNode { PolyNode *link; int exp; Triple trio; union { char vble; PolyNode *dlink; int coef; };

71 노드의 종류 (3x2y)의 표현 trio == var : 리스트의 헤드 노드
trio == ptr : 계수는 그 자체가 리스트이고, 이것을 dlink 필드가 지시 trio == no : 계수는 정수이고, coef 필드에 그 값이 저장 (3x2y)의 표현 trio vble exp link P var y 0 trio dlink exp link ptr var x 0 no

72 범용 리스트의 노드 구조 자료 구조 정의 tag=FALSE/TRUE data/link link
enum Boolean { FALSE, TRUE }; class GenList; // forward declaration class GenListNode { friend class GenList; private: GenListNode *link; Boolean tag; union { char data; GenListNode *dlink; }; class GenList { public: // 리스트 조작 연산 GenListNode *first;

73 data/dlink 데이타 멤버 head(A)가 원자(f) : 원자를 유지(data)
head(A)가 리스트(t) : head(A)의 리스트 표현을 지시하는 포인터를 유지(dlink) f a t b A B C D = 공백 리스트 A = (a,(b,c)) B = (A, A,()) C = (a, C) c v

74 리스트를 위한 순환 알고리즘 순환적으로 정의된 객체 → 순환 알고리즘이 유용 순환 알고리즘의 구성 리스트의 복사
순환 함수 자체(workhorse) 순환 함수를 기동시키는 함수(driver) 구현: Driver는 공용, workhorse는 전용 멤버 함수로 정의 리스트의 복사 // Driver void GenList::Copy(const GenList& l) { first = Copy(l.first); } // Workhorse GenListNode* GenList::Copy(GenListNode* p) { // 공유하는 서브리스트가 없고 p가 가리키는 비순환 리스트의 복사 GenListNode *q = 0; if (p) { q = new GenListNode; q->tag = p->tag; if (!p->tag) q->data = p->data; else q->dlink = Copy(p->dlink); q->link = Copy(p->link); }; return q; }

75 A = ((a,b),((c,d),e))의 표현 f a b c d t e u v w x r

76 리스트의 동일성 // Driver - GenList의 friend로써 가정
int operator==(const GenList& l, const GenList& m) // l과 m은 비순환 리스트이다. // 함수는 두 리스트가 동일하면 1을, 그렇지 않으면 즉시 0을 반환한다. { return equal (l.first, m.first); } // Workhorse는 GenListNode의 friend로 가정 int equal(GenListNode* s, GenListNode* t) int x; if ((!s) && (!t)) return 1; if (s && t && (s->tag == t->tag)) if (!s->tag) if (s->data == t->data) x = 1; else x = 0; else x = equal (s->dlink, t->dlink); if (x) return equal (s->link, t->link); return 0;

77 리스트 깊이 0 s가 원자인 경우 depth(s)=
1+ max(depth(x1),…,depth(xn) s가 리스트 (x1,…,xn)이고, n1 depth(s)= // Driver int GenList::depth() // 비순환 리스트의 깊이를 계산 { return depth(first); } // Workhorse int GenList::depth(GenListNode *s) { if (!s) return 0; GenListNode *p = s; int m = 0; while (p) { if (p->tag) { int n = depth(p->dlink); if (m<n) m = n; } p = p->link; return m+1;

78 참조 계수, 공유 순환 리스트 리스트의 정의 확장 리스트의 공용은 노드의 삽입과 삭제에 문제를 야기 헤드 노드를 첨가하여 해결
리스트의 정의 내에 나타나는 서브리스트는 그 리스트 바로 앞에 이름을 붙인다. 예) A = (a,(b,c)) : A(a,Z(b,c)) 리스트의 공용은 노드의 삽입과 삭제에 문제를 야기 헤드 노드를 첨가하여 해결 tag=f, data/dlink: 참조계수(리스트를 참조하는 포인터수) f 1 3 2 a t c b (i) X (ii) Y (iii) Z (iv) W tag data/dlink link A = (a, (b,c)) B = (A,A,()) C = (a,C)

79 t.~GenList()  t.first의 참조계수를 하나 감소 참조계수가 0이 될 때 t의 노드들은 가용공간으로 반환
class GenListNode { friend class GenList; private: GenListNode *link; int tag; // 0은 data, 1은 dlink, 2는 ref union{ char data; GenListNode *dlink; int ref; };

80 리스트 삭제를 위한 순환 알고리즘 // Driver GenList::~GenList()
// 각 헤드 노드는 참조 계수를 가진다. first는 0이 아니라고 가정한다. { Delete(first); first = 0; } // Workhorse void GenList::Delete(GenListNode* x) x->ref--; // 헤드 노드의 참조 계수를 감소 if (!x->ref) GenListNode *y = x; // y는 x의 최상위 레벨을 순회 while (y->link) y = y->link; if (y->tag == 1) Delete(y->dlink); y->link = av; // 최상위 레벨 노드를 av 리스트에 첨가 av = x;

81 y.~GenList() 호출 : y의 참조 계수를 2로 감소 그 다음에 z.~GenList() 호출
(2) 그 다음 노드가 처리되고 y.first ->ref가 1로 감소 (3) 다시 y.first->ref는 0이 되고 리스트 A(a,(b,c))의 노드들이 가용 공간 리스트로 반환 (4) z의 최상위 레벨 노드들이 가용 공간 리스트에 연결 순환 리스트의 참조 계수: 0이 될 수 없음 w.~GenList() : w.first ->ref를 1로 감소. 반환은 되지 않으나 접근 불가능

82 변수 r과 s에 의해 지시되는 리스트 A와 B의 간접 순환
3 2 1 r s A = (B,B) B = (A) r.~GenList(), s.~GenList() 다음에 r.first->ref는 1, s.first ->ref는 접근 불능, 반환 불능 → 쓰레기(garbage)

83 4.11 C++에서 가상 함수와 동적 바인딩 Rectangle은 Polygon과 I-A 관계이다.
동적 타입(Dynamic Types)과 공용 계승 공용 계승의 중요한 결과는 한 파생 클래스 타입에 대한 포인터는 그것의 기본 클래스에 대한 참조로 은연중에 변환된다. 파생 클래스 타입에 대한 참조는 은연중에 그것의 기본 클래스에 대한 참조로 변환된다. 예) Polygon에 대한 참조를 형식 매개변수로 가진 함수는 Rectangle에 대한 참조를 실인자로 취할 수 있다 Rectangle r; // 파생 클래스의 인스턴스 Polygon *s =&r; // rectangle을 polygon에 지정, s는 동적타입 이때 어떤 함수(Polygon 또는 Rectangle)가 사용되는가?:가상함수

84 class Polygon{ public: int GetId(); // 비가상 멤버함수 virtual Boolean Concave(); // 가상 멤버함수 virtual int Perimeter() = 0; // 순수 가상 멤버함수 protected: int id; }; class Rectangle : public Polygon{ // Rectangle은 Polygon 으로부터 공용으로 계승받음 Boolean Concave(); // Rectangle에서 재정의됨 int Perimeter; // Rectangle에서 정의됨 // GetId()와 id는 Polygon으로부터 계승되며 // 이들은 각각 Rectangle의 public과 protected 멤버가 됨 private: // Rectangle을 세분화하는 데 필요한 추가 데이타 멤버들 int x1, y1, h, w; // GetId()는 파생 클래스에서 재정의해서는 안 된다. int Polygon::GetId() { return id }; // Polygon 에 있는 Concave()의 묵시적 구현. // 다각형 안에 있는 두 점을 이어서 다각형 안에 완전히 포함되지 // 않는 직선을 만들 수 있다면 그 다각형은 오목이다. Boolean Polygon::Concave() { return TRUE;}

85 공용 계승 // Rectangle은 Perimeter()를 반드시 정의해야 한다.
// 왜냐하면 이것은 순수 가상 함수이기 때문이다. int Rectangle::Perimeter { return 2*(h + w);} // Concave()의 묵시적 구현은 rectangles에 적용되지 않는다. // 따라서, 재정의되어야 한다 Boolean Rectangle::Concave { return FALSE; } 공용 계승

86 세가지 유형의 멤버 함수 (a) 가상 멤버 함수(Virtual Member Functions) 가상 멤버 함수의 동작
파생 클래스에서 구현이 재정의될 것을 예상 가상 함수가 어떤 기본 클래스 객체에 의하여 기동되면, 그 기본 클래스 객체의 현재의 동적 타입과 일치하는 구현이 사용 가상 멤버 함수의 동작 Rectangle r; . // r이 이 지점에서 초기화되었다고 가정한다 Polygon *s = &r; s->Concave(); // FALSE를 반환, Rectangle의 Concave함수를 사용

87 세가지 유형의 멤버 함수 (b)비가상 멤버함수(non-virtual member functions) 비가상 함수의 재구현
GetId(): 각 다각형 객체의 식별 번호, 즉 id를 반환하는 것 파생 클래스에서 재정의 삼가 rectangle에서 GetId가 재정의 되었다고 가정 비가상 함수의 재구현 Rectangle r; . // r이 이 지점에서 초기화되었다고 가정한다 Polygon *s = &r; s->GetId(); // Polygon에 있는 함수 구현을 사용 Rectangle *t = &r; t->GetId(); // Rectangle에 있는 함수 구현을 사용, s->GetId()의 사용과 모순

88 세가지 유형의 멤버 함수 (c) 순수 가상 함수(Pure virtual functions)
가상 멤버 함수가 자기 클래스에서는 구현되지 않은 경우 순수 가상 함수라는 것을 표시하기 위하여 값 0을 지정 virtual int Perimeter()=0; 추상 클래스(abstract class) 하나 이상의 순수 가상 함수를 포함한 기본 클래스 순수 가상 함수를 포함함으로써 발생되는 두 가지 결과 (1)추상 클래스의 인스턴스를 생성할 수 없다 그러나 추상 클래스에 대한 포인터를 선언은 합법 Polygon p; // 불법 Polygon *q // 합법 순수 가상 함수는 파생 클래스에서 반드시 재정의 Rectangle r; // r이 이 지점에서 초기화되었다고 가정한다 Polygon *s = &r; s->Perimeter(); // r의 둘레를 반환한다

89 4.12 이질 리스트 이질 리스트(Heterogeneous Lists)
상이한 타입의 노드들을 포함한 리스트 상이한 구조의 헤드 노드와 원소 노드 Union을 이용하여 상이한 타입의 노드들을 하나의 클래스로 통합 리스트의 포인터 사용이 용이

90 Union을 사용한 혼합 노드의 리스트 표현 struct Data int id;
// 노드가 char, int, float를 포함하느냐에 따라 각각 id는 0, 1, 또는 2 union { int i; char c; float f; }; class CombinedNode // 상이한 노드 타입들을 하나의 클래스 정의로 합병하기 위하여 // union을 사용한다 { friend class List; friend class ListIterator; private: Data data; CombinedNode *link;

91 class List { friend class ListIterator; public: // List 조작 연산들 생략 private: CombinedNode *first; }; // class ListIterator는 First와 Next의 반환 타입이 Data*라는 점만 // 제외하면, 4.3절에서 정의한 것과 같다

92 공용 계승을 이용한 혼합 노드의 리스트 구현 // struct Data는 프로그램 4.44에서 같이 정의되었다고 가정한다
class Node { friend class List; friend class ListIterator; protected: Node *link; virtual Data GetData() = 0; }; template<class Type> class DerivedNode: public Node { friend class List; friend class ListIterator; public: Type data; Data GetData(); Data DerivedNode<char>::GetData() { Data t; t.id=0; t.c = data; return t; }

93 // DerivedNode<int>와 DerivedNode<float>를 위한 GetData()의 구현은
// DerivedNode<char>::GetData()와 유사하다 class List { friend class ListIterator; public: // List 조작 연산들 생략 . private: Node *first; };

94 class ListIterator { public: ListIterator(const List &l); list(l), current(l.first) ; Data * First(); // 동질 리스트 구현에 약간의 변화 Data * Next(); // 동질 리스트 구현에 약간의 변화 Boolean NotNull(); // 동질 리스트와 같이 구현 Boolean NextNotNull(); // 동질 리스트와 같이 구현 private: const List& list; Node* current; Data temp; }; Data * ListIterator::First() { if (list.first) { temp = list->first->GetData(); // 원소를 검색하기 위하여 // getData() 사용 return &temp; } return 0;

95 (2) Node로부터 공용으로 파생된 템플리트 클래스 DerivedNode<Type>가 정의
이 클래스는 노드 구조에서 사용되는 모든 노드 타입에 공통적인 데이타 멤버들을 포함 (2) Node로부터 공용으로 파생된 템플리트 클래스 DerivedNode<Type>가 정의 이 클래스는 노드 안에 저장되는 Type 형의 객체를 저장하는데 필요한 필드를 추가로 포함 (3) 노드 안의 데이타를 찾아서 반환해 주는 Node에 대한 순수 가상 함수 GetData를 정의 (4) 클래스 List와 ListIterator는 First와 Next 연산의 구현을 제외하면 변함이 없음 이 두 연산은 GetData를 이용하여 데이타를 얻음

96 note 공용 계승의 동적 타입으로 Node*(즉, link)에 대한 포인터가 DerivedNode<char>, DerivedNode<int> 그리고 DerivedNode<float> 타입의 노드를 가리킬 수 있다