2023. 12. 1. 16:15ㆍ프로그래밍 공부/OOP
17.2 연결리스트 응용
예: 스택 템플릿 클래스
스택: 데이터가 저장된 순서의 반대로 데이터를 검색하는 데이터 구조
스택에 'A', 'B', 그리고 'C' 문자를 넣었다고 가정해보자.
이 문자들을 스택에서 꺼내면 'C', 그다음 'B', 그리고 'A' 순서로 제거된다.
스택의 사용은 디스플레이 17.16에 도표로 표시되어 있다.
거기에 표시된 것처럼, 스택을 땅에 있는 구멍이라고 생각할 수 있다.
스택에서 무언가를 빼내기 위해서는 먼저 원하는 것 위에 있는 항목들을 제거해야 한다.
스택: 선출후입(last-in/first-out) 자료 구조
디스플레이 17.16 스택
pushing
popping
스택은 많은 언어 처리 작업에 사용된다.
13장에서는 컴퓨터 시스템이 C++ 함수 호출을 추적하기 위해 스택을 사용하는 방법에 대해 설명했다.
하지만 여기서는 아주 간단한 응용 프로그램 하나만 다룰 것이다.
이 예제에서 우리의 목표는 스택과 같은 특정한 데이터 구조를 구현하기 위해
연결 리스트 기법을 사용하는 방법을 보여주는 것이다.
우리의 스택 클래스에 대한 인터페이스는 디스플레이 17.17에 나와 있다.
이것은 스택에 저장된 데이터의 종류에 대한 형식 매개 변수 T를 갖는 템플릿 클래스이다.
스택에 저장된 하나의 아이템은 T 형식의 값이다.
우리가 제시한 예제에서 T는 char 형식으로 대체되었다.
그러나 대부분의 응용 프로그램에서 스택에 저장된 아이템은 struct 또는 클래스 객체일 가능성이 높다.
스택 프레임: 스택에 저장된 각각의 레코드(T 형식의 항목)
-> 스택 템플릿 클래스의 정의에서 stackFrame을 식별자 이름으로 사용하는 이유를 설명한다.
스택에서 수행할 수 있는 기본적인 작업
1. 스텍에 항목을 추가하는 것 - 스택에 항목을 push하는 것- 멤버 함수 push
2. 스택에서 항목을 제거하는 것 - 스택에서 항목을 pop하는 것 - 멤버 함수 pop
push and pop이라는 이름은 스택을 시각화하는 특정한 방법에서 유래되었다.
스택은 식당에서 판을 고정하는 데 가끔 사용되는 메커니즘과 유사하다.
메커니즘은 카운터 상판의 구멍에 판을 저장한다.
판 아래에는 꼭대기 판만 카운터 상판 위로 돌출되도록 장력이 조절된 스프링이 있다.
이런 메커니즘이 스택 자료 구조로 사용되었다면 데이터는 판에 기록될 것이다.
스택에 판을 추가하려면 다른 판 위에 놓고 새로운 판의 무게를 스프링 아래로 밀어낸다.
판을 제거하면 그 아래에 있는 판이 시야에 뜬다.
디스플레이 17.18은 Stack 클래스가 어떻게 사용되는지를 보여주는 간단한 프로그램을 보여준다.
이 프로그램은 한 번에 한 줄의 문자를 읽고 문자들을 스택에 넣는다.
그런 다음 프로그램은 문자들을 하나씩 제거하고 화면에 기록한다.
스택에서 데이터가 들어가는 순서의 반대로 데이터를 스택에서 제거하기 때문에
출력에는 뒤로 쓴 행이 표시된다.
보통 템플릿 클래스를 사용하는 것처럼
Stack 클래스의 구현을 응용 프로그램에 #include시켰다.
즉, Stack 클래스 템플릿을 구현하기 전까지는 응용 프로그램을 실행하거나 컴파일할 수 없다.
템플릿 클래스 Stack에 대한 멤버 함수의 정의는 디스플레이 17.19의 구현 파일에 나와 있다.
우리의 스택 클래스는 리스트의 헤드가 스택의 top 역할을 하는 연결 리스트로 구현된다.
멤버 변수 top은 연결 리스트의 헤드를 가리키는 포인터이다.
포인터 to은 연결 리스트에 대한 이전 논의에서 포인터 head와 같은 역할을 한다.
디스플레이 17.17 스택 템플릿 클래스 인터페이스 파일
//This is the header file stack.h. This is the interface for the class
//Stack, which is a template class for a stack of items of type T .
#ifndef STACK_H
#define STACK_H
namespace StackSavitch
{
template<class T>
class Node
{
public:
Node(T theData, Node<T>* theLink) : data(theData), link(theLink){}
Node<T>* getLink( ) const { return link; }
const T getData( ) const { return data; }
void setData( const T& theData) { data = theData; }
void setLink(Node<T>* pointer) { link = pointer; }
private:
T data;
Node<T> *link;
};
template<class T>
class Stack
{
public:
Stack( );
//Initializes the object to an empty stack .
Stack( const Stack<T>& aStack);
Stack<T>& operator =( const Stack<T>& rightSide);
virtual ̃Stack( );
void push(T stackFrame);
//Postcondition: stackFrame has been added to the stack .
T pop( );
//Precondition: The stack is not empty .
//Returns the top stack frame and removes that top
//stack frame from the stack .
bool isEmpty( ) const;
//Returns true if the stack is empty. Returns false otherwise .
private:
Node<T> *top;
};
} //StackSavitch
#endif //STACK_H매개변수 형식 T를 const T&로 대체하는 것이 좋다.
Stack( const Stack<T>& aStack);
복사 생성자
virtual ~Stack( );
소멸자는 스택을 소멸하고 모든 메모리를 freestore로 반환한다.
디스플레이 17.18 스택 템플릿 클래스를 사용한 프로그램
//Program to demonstrate use of the Stack template class .
#include <iostream>
#include "stack.h"
#include "stack.cpp"
using std::cin;
using std::cout;
using std::endl;
using StackSavitch::Stack;
int main( )
{
char next, ans;
do
{
Stack<char> s;
cout << "Enter a line of text:\n";
cin.get(next);
while (next != '\n')
{
s.push(next);
cin.get(next);
}
cout << "Written backward that is:\n";
while ( ! s.isEmpty( ) )
cout << s.pop( );
cout << endl;
cout << "Again?(y/n): ";
cin >> ans;
cin.ignore(10000, '\n');
} while (ans != 'n' && ans != 'N');
return 0;
}cin의 ignore 멤버는 9장에서 논의한다.
그것은 라인에 남아있는 입력을 버린다.
샘플 대화 상자
Enter a line of text:
straw
Written backward that is:
warts
Again?(y/n): y
Enter a line of text:
I love C++
Written backward that is:
++C evol I
Again?(y/n): n
디스플레이 17.19 스택 템플릿 클래스의 구현
//This is the implementation file stack.cpp .
//This is the implementation of the template class Stack .
//The interface for the template class Stack is in the header file
//stack.h.
#include <iostream>
#include <cstdlib>
#include <cstddef>
#include "stack.h"
using std::cout;
namespace StackSavitch
{
//Uses cstddef:
template<class T>
Stack<T>::Stack( ) : top(NULL)
{
//Intentionally empty
}
template<class T>
Stack<T>::Stack( const Stack<T>& aStack)
< The definition of the copy constructor is Self-Test Exercise 14 .>
template<class T>
Stack<T>& Stack<T>::operator =( const Stack<T>& rightSide)
< The definition of the overloaded assignment operator is Self-Test Exercise 15 .>
template<class T>
Stack<T>:: ̃Stack( )
{
T next;
while (! isEmpty( ))
next = pop( );//pop calls delete.
}
//Uses cstddef:
template<class T>
bool Stack<T>::isEmpty( ) const
{
return (top == NULL);
}
template<class T>
void Stack<T>::push(T stackFrame)
< The rest of the definition is Self-Test Exercise 13 .>
//Uses cstdlib and iostream:
template<class T>
T Stack<T>::pop( )
{
if (isEmpty( ))
{
cout << "Error: popping an empty stack.\n";
exit(1);
}
T result = top->getData( );
Node<T> *discard;
discard = top;
top = top->getLink( );
delete discard;
return result;
}
} //StackSavitch
Self-Test Practice 13은 멤버 함수 push의 정의를 작성하는 것이다.
그러나 이 작업에 대한 알고리즘은 이미 제시되어 있다.
멤버 함수 push의 코드는 기본적으로 디스플레이 17.15의 함수 headInsert와 같지만,
멤버 함수 push에서는 head라는 이름의 포인터 대신 top이라는 이름의 포인터를 사용한다.
빈 스택은 단지 빈 연결 리스트이므로
포인터 탑(top)을 NULL과 동일하게 설정하여 빈 스택을 구현한다.
일단 NULL이 빈 스택을 나타낸다는 것을 알게 되면 기본 생성자와 멤버 함수 empty의 구현이 명백해진다.
복사 생성자의 정의는 조금 더 복잡하지만,
우리가 아직 논의하지 않은 어떤 기법도 사용하지 않는다.
자세한 내용은 Self-Test Practice 14에 맡긴다.
pop 멤버 함수는 먼저 스택이 비어 있는지 확인한다.
비어 있지 않으면 스택의 맨 위 문자를 제거하는 작업을 진행한다.
스택의 맨 위 기호와 같은 지역 변수 결과를 다음과 같이 설정한다:
T result = top->getData( );
상위 노드의 데이터가 변수 result에 저장된 후,
포인터 top은 연결 리스트의 다음 노드로 이동되어
리스트에서 상위(top) 노드가 효과적으로 제거된다.
포인터 top은 다음 문장과 함께 이동된다
top = top->getLink( );
그러나 포인터 top을 이동하기 전에 discard라고 하는 임시 포인터가
리스트에서 제거하려는 노드를 가리키도록 배치된다.
그런 다음 제거된 노드의 저장소를 다음과 같이 delete하도록 호출하여 재사용할 수 있다:
delete discard;
멤버 함수 pop에 의해 연결 리스트에서 제거된 각 노드는
delete할 호출과 함께 메모리를 재사용하므로,
소멸자는 pop에 대한 호출과 함께 스택에서 각 항목을 제거하기만 하면 된다.
그러면 각 노드는 재사용을 위해 해당 메모리를 freestore로 반환한다.
스택
스택(stack): 선출후입(Last-in/First-out) 자료 구조
즉, 데이터 항목은 스택에 배치된 순서와 반대로 검색된다.
Push와 Pop
데이터 아이템을 스택 자료 구조에 추가하는 것 = 데이터 아이템을 스택에 푸쉬(push)하는 것
데이터 아이템을 스택에서 제거하는 것 = 해당 아이템을 스택에서 팝(pop)하는 것
예: 큐 템플릿 클래스
스택은 선출후입(last-in/first-out) 자료 구조
큐(queue): 선출선입(first-in/first-out) 방식으로 데이터를 처리하는 자료 구조
Stack 템플릿 클래스의 구현과 유사한 방식으로 큐를 연결 리스트로 구현할 수 있다.
하지만 두 위치에서 모두 작업이 수행되므로
큐는 리스트의 맨 앞과 연결 리스트의 맨 끝 모두에 포인터를 필요로 한다.
연결 리스트의 다른 끝보다 연결 리스트의 맨 앞에서 노드를 제거하는 것이 더 쉽다.
따라서 구현에서는 리스트의 맨 앞에서 노드를 제거하고 리스트의 다른 끝에 노드를 추가한다.
연결 리스트의 다른 끝에서보다 연결 리스트의 헤드에서 노드를 제거하는 것이 더 쉽다.
따라서 우리의 구현은
1. 리스트의 맨 앞에 있는 노드를 제거할 것이다.
리스트의 front - 리스트의 맨 앞에 있는 노드
2. 리스트의 다른 끝에 노드를 추가한다.
리스트의 back(또는 큐의 back) - 리스트의 맨 끝에 있는 노드
Queue 템플릿 클래스의 정의는 디스플레이 17.20에 나와 있다.
Queue 클래스를 사용하는 샘플 응용 프로그램은 디스플레이 17.21에 나와 있다.
디스플레이 17.20 큐 템플릿 클래스 인터페이스 파일
//This is the header file queue.h. This is the interface for the class
//Queue, which is a template class for a queue of items of type T .
#ifndef QUEUE_H
#define QUEUE_H
namespace QueueSavitch
{
template<class T>
class Node
{
public:
Node(T theData, Node<T>* theLink) : data(theData), link(theLink){}
Node<T>* getLink( ) const { return link; }
const T getData( ) const { return data; }
void setData( const T& theData) { data = theData; }
void setLink(Node<T>* pointer) { link = pointer; }
private:
T data;
Node<T> *link;
};
template<class T>
class Queue
{
public:
Queue( );
//Initializes the object to an empty queue .
Queue( const Queue<T>& aQueue);
Queue<T>& operator =( const Queue<T>& rightSide);
virtual ~Queue( );
void add(T item);
//Postcondition: item has been added to the back of the queue .
T remove( );
//Precondition: The queue is not empty .
//Returns the item at the front of the queue
//and removes that item from the queue .
bool isEmpty( ) const;
//Returns true if the queue is empty. Returns false otherwise .
private:
Node<T> *front; //Points to the head of a linked list .
//Items are removed at the head
Node<T> *back; //Points to the node at the other end of the
//linked list .
//Items are added at this end .
};
} //QueueSavitch
#endif //QUEUE_H이는 Display 17.17에서 스택 인터페이스에 대해 제공한 템플릿 클래스 Node의 정의와 동일하다.
중복에 대한 자세한 내용은 "팁: 네임스페이스에 대한 의견"를 참조하자.
void setData( const T& theData)
매개변수 형식 T를 const T&로 대체하는 것이 좋다.
Queue( const Queue<T>& aQueue);
복사 생성자
virtual ~Queue( );
소멸자는 큐를 소멸하고 모든 메모리를 freestore에 반환한다.
디스플레이 17.21 큐 템플릿 클래스를 이용한 프로그램
//Program to demonstrate use of the Queue template class .
#include <iostream>
#include "queue.h"
#include "queue.cpp"
using std::cin;
using std::cout;
using std::endl;
using QueueSavitch::Queue;
int main( )
{
char next, ans;
do
{
Queue< char> q;
cout << "Enter a line of text:\n";
cin.get(next);
while (next != '\n')
{
q.add(next);
cin.get(next);
}
cout << "You entered:\n";
while ( ! q.isEmpty( ) )
cout << q.remove( );
cout << endl;
cout << "Again?(y/n): ";
cin >> ans;
cin.ignore(10000, '\n');
} while (ans != 'n' && ans != 'N');
return 0;
}디스플레이 17.18에서 제공한 큐 대신 스택을 사용하는 유사한 프로그램과 대조한다.
샘플 대화 상자
Enter a line of text:
straw
You entered:
straw
Again?(y/n): y
Enter a line of text:
I love C++
You entered:
I love C++
Again?(y/n): n
큐
큐(queue): 선입선출(first-in/first-out) 자료 구조
즉, 데이터 항목은 큐에 추가된 순서와 동일하게 큐에서 제거된다.
팁: 네임스페이스에 대한 의견
네임스페이스 StackSavitch(디스플레이 17.17)와 QueueSavitch(디스플레이 17.20)는 모두 Node라는 템플릿 클래스를 정의한다.
밝혀진 바와 같이, Node의 두 정의는 동일하지만,
여기서 논의되는 점은 두 정의가 동일하든 상이하든 동일하다.
C++는 두 정의가 동일하더라도
두 개의 이름이 어떻게든 구분되지 않는 한
동일한 식별자를 두 번 정의하는 것을 허용하지 않다.
이 경우 두 개의 정의는 두 개의 서로 다른 네임스페이스에 있기 때문에 허용된다.
심지어 Stack 템플릿 클래스와 Queue 템플릿 클래스를 모두 동일한 프로그램에서 사용하는 것은 합법이다.
그러나
using namespace StackSavitch;
using namespace QueueSavitch;
보다는
using StackSavitch::Stack;
using QueueSavitch::Queue;
를 사용해야 한다.
Node라는 식별자를 사용하지 않을 경우
대부분의 컴파일러는 using 지시문 중 하나를 사용할 수 있지만,
두 번째 using지시문은 Node라는 식별자에 대한 두 가지 정의를 제공하므로 피해야 한다.
다음 중 하나를 사용해도 괜찮지만 두 가지 모두 사용하지는 않는다:
using StackSavitch::Node;
or
using QueueSavitch::Node;
friend 클래스 및 유사한 대안
템플릿 클래스 Node에서
접근자 및 설정자 getLink 및 setLink를 사용하는 것이
성가신 일임을 발견했을 수 있다
(디스플레이 17.17 또는 디스플레이 17.20 참조).
클래스 Node의 멤버 변수 link를 private으로 만드는 것만으로
getLink 및 setLink의 호출을 피할 수 있다.
모든 멤버 변수를 private로 만드는 원칙을 포기하기 전에 두 가지 사항에 유의하자.
1. 프로그래머인 당신은 getLink 및 setLink를 사용하는 것이 노드의 링크에 직접 접근하는 것보다 더 어렵지 않다.
하지만 getLink 및 setLink는 일부 오버헤드를 도입하므로 효율성이 다소 저하될 수 있다.
2. 멤버 변수 link를 public으로 만들지 않고 노드의 링크에 직접 접근하는 방법이 있다.
두 번째 가능성을 살펴보자.
8장에서는 friend 함수에 대해 논의했다.
만약 f가 클래스 C의 friend 함수라면 f는 C의 멤버 함수가 아니다.
그러나 함수 f의 정의를 쓸 때
C의 멤버 함수의 정의에서 볼 수 있는 것처럼 C의 private 멤버에게도 접근할 수 있다.
함수가 클래스의 friend가 되는 것과 같은 방식으로 클래스는 다른 클래스의 friend가 될 수 있다.
클래스 F가 클래스 C의 friend라면
클래스 F의 모든 멤버 함수는 클래스 C의 friend가 된다.
따라서 예를 들어,
만약 Queue 템플릿 클래스가 Node 템플릿 클래스의 friend라면
private 링크 멤버 변수는 큐의 멤버 함수 정의에서 직접 사용할 수 있다.
자세한 내용은 디스플레이 17.22에 나와 있다.
디스플레이 17.22 Node 클래스의 friend로서 Queue 템플릿 클래스
//This is the header file queue.h. This is the interface for the class
//Queue, which is a template class for a queue of items of type T .
#ifndef QUEUE_H
#define QUEUE_H
namespace QueueSavitch
{
template<class T>
class Queue;
template<class T>
class Node
{
public:
Node(T theData, Node<T>* theLink) : data(theData), link(theLink){}
friend class Queue<T>;
private:
T data;
Node<T> *link;
};
template<class T>
class Queue
{
< The definition of the template class Queue is identical to the one given in Display 17.20 .
However, the definitions of the member functions will be different from the ones we gave
(in the Self-Test Exercises) for the nonfriend version of Queue .>
}
} //QueueSavitchtemplate<class T>
class Queue;
전방 선언. 세미콜론 잊지 말기.
이 방법은 디스플레이 17.20에 제공된 방법에 대한 대체 접근 방법이다.
이 버전에서 Queue 템플릿 클래스는 Node 템플릿 클래스의 friend이다.
Node<T>가 친구 클래스 Queue<T>의 정의에만 사용되는 경우,
설정자(mutator)나 접근자(accessor) 기능이 필요 없다.
#endif //QUEUE_H
#include <iostream>
#include <cstdlib>
#include <cstddef>
#include "queue.h"
using std::cout;
namespace QueueSavitch
{
template<class T> //Uses cstddef:
void Queue<T>::add(T item)
{
if (isEmpty( ))
front = back = new Node<T>(item, NULL);
else
{
back->link = new Node<T>(item, NULL);
back = back->link;
}
}
template<class T> //Uses cstdlib and iostream:
T Queue<T>::remove( )
{
if (isEmpty( ))
{
cout << "Error: Removing an item from an empty queue.\n";
exit(1);
}
T result = front->data;
Node<T> *discard;
discard = front;
front = front->link;
if (front == NULL) //if you removed the last node
back = NULL;
delete discard;
return result;
}
} //QueueSavitch구현 파일에는 이러한 정의와 노드의 링크 및 데이터 멤버 변수에 대한
이름별 접근을 허용하도록 유사하게 수정된 다른 멤버 함수의 정의가 포함된다.
효율성이 주요 문제인 경우 ( is Empty( )) 대신 (front == NULL)을 사용할 수 있다.
전방 선언
한 클래스가 다른 클래스의 friend인 경우에는
클래스 정의에서 서로를 참조하는 것이 일반적이다.
이렇게 하려면 디스플레이 17.22와 같이
두 번째로 정의된 클래스 또는 클래스 템플릿에 대한 전달 선언을 포함해야 한다.
전달 선언(forward declaration): 클래스 또는 클래스 템플릿 정의 다음에 세미콜론이 오는 표제
17.4절에 friend 클래스를 사용한 완전한 예가 나와 있다(프로그래밍 예제 "트리 템플릿 클래스" 참조).
friend 클래스와 거의 동일한 목적을 수행하고
Node 및 Queue와 같은 클래스 및 템플릿 클래스와
거의 동일한 방식으로 사용할 수 있는 2가지 접근 방식
(1) protected 또는 private 상속을 사용하여 Node에서 Queue를 도출한다.
(2) Node의 정의 내에서 Node의 정의를 제공하므로 Node는 지역 클래스(템플릿) 정의이다.
예: 연쇄적인 해시 테이블
해시 테이블
해시 테이블(hash table) 또는 해시 맵(hash map): 메모리에서 데이터를 효율적으로 저장하고 검색하는 데이터 구조이다.
해시 테이블을 구성하는 데에는 여러 가지 방법이 있다.
이 절에서는 배열을 단일 연결 리스트와 함께 사용할 것이다.
17.1절에서는 대상을 찾는 목록의 모든 노드를 반복하여 연결 리스트을 검색했다.
목록이 매우 긴 경우
이 과정에서 목록에 있는 모든 노드를 검사해야 하며, 시간이 많이 소요될 수도 있다.
반면 최악의 경우(가능성이 거의 없음)에는
단일 연결 리스트를 사용하는 것처럼 느리게 실행되지만,
해시 테이블은 대상을 매우 빨리 찾을 수 있다.
해시 함수
어떤 물체는 키(key)와 연관 지어 해시 테이블에 저장된다.
키가 주어지면, 우리는 그 물체를 검색할 수 있다.
이상적으로, 그 키는 각각의 물체에 고유하다.
만약 그 물체에 고유한 키가 없다면,
우리는 해시 함수(hash function)를 사용하여 하나를 계산할 수 있다.
대부분의 경우, 해시 함수는 숫자를 계산한다.
예를 들어, 해시 테이블을 사용하여 단어 사전을 저장해 보자.
그런 해시 테이블은 철자 검사기를 만드는 데 유용할 수도 있는데,
해시 테이블에서 빠진 단어들의 철자가 틀릴 수도 있다.
우리는 배열이 고정된 해시 테이블을 만들 것이고,
배열의 각 요소는 연결 리스트를 참조할 것이다.
해시 함수에 의해 계산된 키는 배열의 인덱스에 매핑될 것이다.
실제 데이터는 해시 값의 인덱스에 있는 연결된 목록에 저장될 것이다.
디스플레이 17.23은 열 개의 항목으로 이루어진 고정된 배열을 보여준다.
처음에 배열 hasharray의 각 항목에는 빈 단일 연결 리스트에 대한 참조가 포함되어 있다.
먼저, 우리는 키 또는 해시 값 2가 할당된 "cat"이라는 단어를 추가한다.
다음으로, 우리는 "dog"와 "bird"를 각각 4와 7의 해시 값으로 추가한다.
이 문자열들은 배열에서 해시 값을 인덱스로 사용하여 연결된 목록의 선두로 삽입된다.
마지막으로, 우리는 해시 값이 2인 "turtle"을 추가한다.
"cat"은 이미 인덱스 2에 저장되어 있으므로, 이제 충돌(collision)이 발생한다.
"turtle"과 "cat"은 배열의 동일한 인덱스에 매핑된다.
이런 일이 연쇄(chaining)가 있는 해시 테이블에서 발생하면,
단순히 기존의 연결 리스트에 새로운 노드를 삽입한다.
예를 들어, 인덱스 2에는 이제 "거북"과 "고양이"라는 두 개의 노드가 있다
해시 테이블에서 값을 검색하려면 먼저 대상의 해시값을 계산한다.
다음으로 대상에 대해 hasharray[hashvalue]에 저장된 연결 리스트를 순차적으로 검색한다.
이 연결 리스트에서 대상을 찾지 못하면 대상은 해시 테이블에 저장되지 않는다.
연결 리스트의 크기가 작으면 검색 과정이 빠르다.
문자열에 대한 해시 함수
문자열에 대한 숫자 해시 값을 계산하는 간단한 방법은
문자열의 모든 문자의 ASCII 값을 합한 다음
고정 배열의 크기를 사용하여 합계의 합동식(modulus)를 계산하는 것이다.
합동식(modulus): 정수의 합과 곱을 어떠한 수의 나머지에 대해 정의하는 방법
ASCII 코드의 하위 집합은 부록 3에 나와 있다.
함수 computeHash에는 해시 값을 계산하는 코드가 나와 있다.
int computeHash(string s)
{
int hash = 0;
for (int i = 0; i < s.length( ); i++)
{
hash = hash + s[i];
}
return hash % SIZE; //SIZE = 10 in example
}
예를 들어, 문자열 "dog"의 ASCII 코드는
d -> 100
o -> 111
g -> 103
해시 함수는 다음과 같이 계산된다
Sum = 100 + 111 + 103 = 314
Hash = Sum % 10 = 314 % 10 = 4
이 예에서는 먼저 문자열 내 ASCII 값의 합인 경계 없는 값을 계산한다.
그러나 배열은 유한한 수의 요소를 포함하도록 정의되었다.
합을 배열의 크기로 확장하기 위해,
배열의 크기에 대한 합의 모듈러스를 계산하는데, 이것은 예제에서 10이다.
실제로 배열의 크기는 일반적으로 해시 테이블에 넣을 항목의 수보다 더 큰 소수이다.
계산된 해시 값 4는 문자열 "dog"의 지문 역할을 한다.
그러나 다른 문자열도 같은 값에 매핑할 수 있다.
예시)
"cat"은 (99 + 97 + 116) % 10 = 2로,
"turtle"은 (116 + 117 + 114 + 116 + 108 + 101) % 10 = 2
로 매핑되는 것을 확인할 수 있다.
해시 테이블 클래스에 대한 전체 코드 목록은 디스플레이 17.24 및 17.25에 나와 있다.
시연은 디스플레이 17.26에 나와 있다.
해시 테이블 정의는 각 요소가 디스플레이 17.14에 정의된 Node 클래스인 배열을 사용한다.
연결 리스트는 디스플레이 17.14 및 17.15에 정의된 일반 연결 리스트 라이브러리를 사용하여 구현된다.
디스플레이 17.23 해시 테이블 세우기
연결 리스트가 10개 비어 있는 기존 해시 테이블
Node<string> *hashArray[10];
for (int i=0; i<10; i++) hashArray[i] = NULL;
해시가 2인 "cat"을 추가한 후
해시가 4인 "dog"와 해시가 7인 "bird"를 추가한 후
해시가 2개인 "turtle"을 추가하고 "cat"과 연결 리스트에 연결된 후
디스플레이 17.24 HashTable 클래스 인터페이스 파일
//This is the header file hashtable.h. This is the interface
//for the class HashTable, which is a class for a hash table
//of strings .
#ifndef HASHTABLE_H
#define HASHTABLE_H
#include <string>
#include "listtools.h"
using LinkedListSavitch::Node;
using std::string;
namespace HashTableSavitch
{
const int SIZE = 10; //Maximum size of the hash table array
class HashTable
{
public:
HashTable( ); //Initialize empty hash table .
//Normally a copy constructor and overloaded assignment
//operator would be included. They have been omitted
//to save space .
virtual ~HashTable( ); //Destructor destroys hash table .
bool containsString(string target) const;
//Returns true if target is in the hash table,
//false otherwise .
void put(string s);
//Adds a new string to the hash table .
private:
Node<string> *hashArray[SIZE]; //The actual hash table
static int computeHash(string s); //Compute a hash value
}; //HashTable
} //HashTableSavitch
#endif //HASHTABLE_H라이브러리 "listtools.h"는 디스플레이 17.14의 연결 리스트 라이브러리 인터페이스이다.
디스플레이 17.25 HashTable 클래스의 구현
//This is the implementation file hashtable.cpp .
//This is the implementation of the class HashTable .
#include <string>
#include "listtools.h"
#include "hashtable.h"
using LinkedListSavitch::Node;
using LinkedListSavitch::search;
using LinkedListSavitch::headInsert;
using std::string;
namespace HashTableSavitch
{
HashTable::HashTable( )
{
for ( int i = 0; i < SIZE; i++)
{
hashArray[i] = NULL;
}
}
HashTable::~HashTable( )
{
for ( int i=0; i<SIZE; i++)
{
Node<string> *next = hashArray[i];
while (next != NULL)
{
Node<string> *discard = next;
next = next->getLink( );
delete discard;
}
}
}
int HashTable::computeHash(string s)
{
int hash = 0;
for ( int i = 0; i < s.length( ); i++)
{
hash = hash + s[i];
}
return hash % SIZE;
}
void HashTable::put(string s)
{
int hash = computeHash(s);
if (search(hashArray[hash], s)==NULL)
{
//Only add the target if it's not in the list
headInsert(hashArray[hash], s);
}
}
}
//HashTableSavitch
디스플레이 17.26 해시 테이블 시연
//Program to demonstrate use of the HashTable class
#include <string>
#include <iostream>
#include "hashtable.h"
#include "listtools.cpp"
#include "hashtable.cpp"
using std::string;
using std::cout;
using std::endl;
using HashTableSavitch::HashTable;
int main( )
{
HashTable h;
cout << "Adding dog, cat, turtle, bird" << endl;
h.put("dog");
h.put("cat");
h.put("turtle");
h.put("bird");
cout << "Contains dog? " << h.containsString("dog") << endl;
cout << "Contains cat? " << h.containsString("cat") << endl;
cout << "Contains turtle? " << h.containsString("turtle") << endl;
cout << "Contains bird? " << h.containsString("bird") << endl;
cout << "Contains fish? " << h.containsString("fish") << endl;
cout << "Contains cow? " << h.containsString("cow") << endl;
return 0;
}
샘플 대화 상자
Adding dog, cat, turtle, bird
Contains dog? 1
Contains cat? 1
Contains turtle? 1
Contains bird? 1
Contains fish? 0
Contains cow? 0
해시 테이블
해시 테이블(hash table): 자료 항목을 키와 연결하는 자료 구조이다.
키는 해시 함수에 의해 계산된다.
해시 테이블의 효율성
해시 테이블의 효율성은 여러 가지 요인에 의해 결정된다.
먼저 몇 가지 극단적인 경우를 살펴보도록 하겠다.
테이블에 삽입된 모든 항목이 동일한 해시 키를 가지면 최악의 런타임 성능이 발생한다.
그러면 모든 것이 하나의 연결 리스트에 저장되고 find 연산은 목록의 각 항목을 검색해야 할 수도 있다.
다행히 우리가 삽입하는 항목들이 다소 무작위적이라면, 모두 같은 키로 해시될 가능성은 거의 없다.
반대로, 최상의 경우 런타임 성능은 테이블에 삽입되는 모든 항목이 다른 해시 키를 가질 경우 발생한다.
이는 충돌이 없음을 의미하므로 find 연산은 하나의 항목 리스트만 검색하면 되는데,
왜냐하면 대상은 항상 연결 리스트의 첫 번째 노드이기 때문이다.
우리는 더 나은 해시 함수를 사용함으로써 충돌 가능성을 줄일 수 있다.
예를 들어, 문자열의 각 문자를 합하는 간단한 해시 함수는 문자의 순서를 무시한다.
"rat"과 "tar"는 같은 값으로 해시된다.
문자열 s에 대한 더 나은 해시 함수는 각 문자에 단어의 위치에 따라 증가하는 가중치를 곱하는 것이다:
int hash = 0;
for ( int i = 0; i < s.length( ); i++)
{
hash = 31 * hash + s[i];
}
충돌 가능성을 줄이는 또 다른 방법은 해시 테이블을 더 크게 만드는 것이다.
예를 들어 해시 테이블 배열의 입력 용량이 10,000개인데 1000개의 항목만 삽입하고 있다면
충돌할 확률은 해시 테이블 배열이 1000개의 항목만 저장할 수 있는 경우보다 훨씬 적을 것이다.
그러나 10,000개의 항목으로 이루어진 해시 테이블에 1000개의 항목만 삽입하면
9,000개의 메모리 위치가 사용되지 않게 되므로 메모리 낭비가 된다.
시공간의 상충 관계(time-space tradeoff): 보통 메모리 공간을 희생시키면서 런타임 성능을 높이는 것이 가능하며, 그 반대의 경우도 가능하다.
예: 집합 템플릿 클래스
집합(set): 어떤 원소도 두 번 이상 일어나지 않는 원소들의 모임
컴퓨터 과학의 많은 문제들은 집합된 자료 구조의 도움으로 해결될 수 있다.
집합을 구현하기 위한 간단한 방법은 연결 리스트의 변화이다.
이 구현에서는 각 집합의 항목을 하나의 연결 리스트으로 저장한다.
각 노드의 데이터 변수에는 집합의 항목이 포함되어 있을 뿐이다.
디스플레이 17.27은 이 자료 구조를 사용하여 저장된 두 개의 샘플 세트를 보여준다.
세트 round는 “peas”, “ball”, 그리고 “pie”를 포함하고
세트 green은 “peas”과 “grass”을 포함한다.
문자열 “peas”은 둥글고 녹색이기 때문에 두 세트 모두에 있다.
Node 템플릿을 채우는 데 사용된 데이터 형식이 객체의 포인터인 경우,
각 리스트에 동일한 객체의 복사본을 여러 개 만드는 대신
여러 개의 리스트이 공통 객체를 참조할 수 있다.
기본적인 집합 연산
집합 클래스가 지원해야 할 몇 가지 기본 작업은 다음과 같다
add element(요소를 추가한다) 새 항목을 집합에 추가한다.
contains(포함한다): 대상 항목이 집합의 멤버인지 확인한다.
합집합(union): 두 집합의 합집합을 반환한다.
교집합(intersection): 두 집합의 교집합인 집합을 반환한다.
우리는 또한 집합의 각 요소를 통해 반복하는 방법을 포함해야 한다.
다른 유용한 집합 연산에는
집합의 크기(cardinality)를 검색하고 집합에서 항목을 제거하는 함수가 포함된다.
일반적인 요소 집합을 구현하기 위한 코드는 디스플레이 17.28과 17.29에 나타난다.
Set 클래스는 Display 17.14의 연결 리스트 툴을 사용한다.
add 함수 - 단순히 연결 리스트의 맨 앞에 노드를 추가하지만 항목이 아직 집합에 없는 경우에만 추가한다.
contains 함수 - 연결 리스트 라이브러리의 search 기능을 사용한다.
우리는 단순히 대상을 찾기 위해 리스트의 모든 항목을 순환시킨다.
함수 union - 호출 객체 집합의 요소를 입력 인수의 집합인 otherSet의 요소와 결합한다.
이 집합들을 union(결합)하기 위해
1. 빈 집합 객체를 새로 만든다.
2. 호출 객체의 집합과 다른 집합의 집합을 모두 반복한다.
모든 요소가 새로운 집합에 추가된다.
함수 add - 유일성을 강제하므로 우리는 함수 union에서 중복되는 요소를 확인할 필요가 없다.
함수 intersection은 비어 있는 새로운 Set 개체도 생성한다는 점에서 Union 함수와 유사하다.
이 경우 호출 객체의 집합과 다른 Set의 집합에 공통된 항목으로 집합을 채운다.
호출 개체의 집합에 있는 모든 항목을 반복하면 이 작업이 수행된다.
각 항목에 대해 다른 Set에 대한 contains 함수를 호출한다.
contains가 true를 반환하면 항목은 두 집합 모두에 있으며 새 집합에 추가할 수 있다.
짧은 시연 프로그램은 디스플레이 17.30에 있다.
디스플레이 17.27 연결 리스트를 사용하여 집합 구현
집합
집합(set): 자료 요소의 순서 없는 모임
디스플레이 17.28 집합 템플릿 클래스 인터페이스 파일
//This is the header file set.h. This is the interface
//for the class Set, which is a class for a generic set .
#ifndef SET_H
#define SET_H
#include "listtools.h"
using LinkedListSavitch::Node;
namespace SetSavitch
{
template<class T>
class Set
{
public:
Set( ) { head = NULL; } //Initialize empty set.
//Normally a copy constructor and overloaded assignment
//operator would be included. They have been omitted
//to save space .
virtual ~Set( ); //Destructor destroys set .
bool contains(T target) const;
//Returns true if target is in the set, false otherwise .
void add(T item);
//Adds a new element to the set.
void output( );
//Outputs the set to the console.
Set<T>* setUnion( const Set<T>& otherSet);
//Union calling object's set with otherSet
//and return a pointer to the new set.
Set<T>* setIntersection( const Set<T>& otherSet);
//Intersect calling object's set with otherSet
//and return a pointer to the new set.
private:
Node<T> *head;
}; //Set
} //SetSavitch
#endif //SET_H라이브러리 "listtools.h"는 디스플레이 17.14의 연결 리스트 라이브러리 인터페이스이다.
디스플레이 17.29 집합 템플릿 클래스 구현 파일
//This is the implementation file set.cpp .
//This is the implementation of the class Set .
#include <iostream>
#include "listtools.h"
#include "set.h"
using std::cout;
using std::endl;
using LinkedListSavitch::Node;
using LinkedListSavitch::search;
using LinkedListSavitch::headInsert;
namespace SetSavitch
{
template<class T>
Set<T>::~Set( )
{
Node<T> *toDelete = head;
while (head != NULL)
{
head = head->getLink( );
delete toDelete;
toDelete = head;
}
}
template<class T>
bool Set<T>::contains(T target) const
{
Node<T>* result = search(head, target);
if (result == NULL)
return false;
else
return true;
}
void Set<T>::output( )
{
Node<T> *iterator = head;
while (iterator != NULL)
{
cout << iterator->getData( ) << " ";
iterator = iterator->getLink( );
}
cout << endl;
}
template<class T>
void Set<T>::add(T item)
{
if (search(head, item)==NULL)
{
//Only add the target if it's not in the list
headInsert(head, item);
}
}
template<class T>
Set<T>* Set<T>::setUnion( const Set<T>& otherSet)
{
Set<T> *unionSet = new Set<T>( );
Node<T>* iterator = head;
while (iterator != NULL)
{
unionSet->add(iterator->getData( ));
iterator = iterator->getLink( );
}
iterator = otherSet.head;
while (iterator != NULL)
{
unionSet->add(iterator->getData( ));
iterator = iterator->getLink( );
}
return unionSet;
}
template<class T>
Set<T>* Set<T>::setIntersection( const Set<T>& otherSet)
{
Set<T> *interSet = new Set<T>( );
Node<T>* iterator = head;
while (iterator != NULL)
{
if (otherSet.contains(iterator->getData( )))
{
interSet->add(iterator->getData( ));
}
iterator = iterator->getLink( );
}
return interSet;
}
} //SetSavitch
디스플레이 17.30 집합 템플릿 클래스를 이용한 프로그램
//Program to demonstrate use of the Set class
#include <iostream>
#include <string>
#include "set.h"
#include "listtools.cpp"
#include "set.cpp"
using std::cout;
using std::endl;
using std::string;
using namespace SetSavitch;
int main( )
{
Set<string> round; //Round things
Set<string> green; //Green things
round.add("peas"); //Sample data for both sets
round.add("ball");
round.add("pie");
round.add("grapes");
green.add("peas");
green.add("grapes");
green.add("garden hose");
green.add("grass");
cout << "Contents of set round: ";
round.output( );
cout << "Contents of set green: ";
green.output( );
cout << "ball in set round? " <<
round.contains("ball") << endl;
cout << "ball in set green? " <<
green.contains("ball") << endl;
cout << "ball and peas in same set? ";
if ((round.contains("ball") && round.contains("peas")) ||
(green.contains("ball") && green.contains("peas")))
cout << " true" << endl;
else
cout << " false" << endl;
cout << "pie and grass in same set? ";
if ((round.contains("pie") && round.contains("grass")) ||
(green.contains("pie") && green.contains("grass")))
cout << " true" << endl;
else
cout << " false" << endl;
cout << "Union of green and round: " << endl;
Set<string> *unionset = round.setUnion(green);
unionset->output( );
delete unionset;
cout << "Intersection of green and round: " << endl;
Set<string> *interset = round.setIntersection(green);
interset->output( );
delete interset;
return 0;
}
샘플 대화 상자
Contents of set round: grapes pie ball peas
Contents of set green: grass garden hose grapes peas
ball in set round? 1
ball in set green? 0
ball and peas in same set? true
pie and grass in same set? false
Union of green and round:
garden hose grass peas ball pie grapes
Intersection of green and round:
peas grapes
일부 컴파일러는 1과 0 대신 true와 false를 출력할 수 있다.
연결 리스트를 이용한 집합의 효율성
기본적인 집합 연산의 관점에서 집합 자료 구조의 런타임 효율성을 분석할 수 있다.
집합에 항목을 추가하면 항상 리스트의 맨 앞에 새로운 노드가 삽입된다.
이것은 연결 리스트에서 하나의 링크만을 설정해야 한다.
contains 함수는
대상을 찾는 전체 집합을 반복하며,
이는 목록의 모든 노드를 검사해야 할 수도 있다.
집합 A와 B에 대해 setUnion 함수를 호출하면,
두 집합을 모두 반복하며 각 항목을 새로운 집합에 추가한다.
집합 A에 n개의 항목이 있고 집합 B에 m개의 항목이 있으면 n+m개의 항목을 검사해야 한다.
그러나 add 함수는
새로운 항목을 추가하기 전에 전체 목록을 통해 중복된 항목을 검색하기 때문에 숨겨진 비용이 있다.
이 비용은 새로운 집합에 추가되는 항목의 수가 증가함에 따라 상당히 커진다.
마지막으로 집합 A와 B에 적용되는 setIntersection 함수는
집합 A의 각 항목에 대한 집합 B의 포함 함수를 호출한다.
contains 함수는 집합 A의 각 항목에 대해 최대 m개의 노드를 검사해야 하므로,
setIntersection 함수는 최대 m * n개의 노드를 검사해야 한다.
이러한 함수는 집합 구현에서 비효율적인 함수이다.
예를 들어 연결 리스트 대신 해시 테이블을 사용한 집합을 나타내는 다른 접근 방식은
최대 n + m개의 노드를 검사하는 setIntersection 함수를 생성할 수 있다.
그럼에도 불구하고,
연결 리스트 구현은
작은 집합을 사용하는 응용 프로그램이나
setIntersection 함수를 자주 호출하지 않는 응용 프로그램에 적합할 것이며
이해하기 쉬운 비교적 간단한 코드의 이점을 가지고 있다.
효율성이 정말 필요하다면 Set<T> 클래스와 동일한 인터페이스를 유지하되 연결 리스트 구현을 다른 것으로 대체할 수도 있을 것이다.
만약 우리가 디스플레이 17.25의 해시 테이블 구현을 사용한다면 contains 함수는 훨씬 더 빨리 실행될 것이다.
하지만 해시 테이블로 바꾸면 항목 집합을 반복하기가 더 어려워진다.
연결 리스트 하나를 순회하여 집합의 모든 항목을 검색하는 대신
해시 테이블 버전은 이제 해시 테이블 배열을 반복하고
배열의 각 인덱스는 해당 인덱스에서 연결 리스트를 반복해야 한다.
해시 테이블 배열의 각 항목을 검사하려면
집합의 단일 연결 리스트 구현에서 필요하지 않은 추가 시간이 걸린다.
따라서 항목을 찾는 데 걸리는 단계는 줄었지만 모든 항목을 반복하는 데 걸리는 단계는 늘렸다.
만약 이것이 번거롭다면 연결된 목록과 빠른 검색을 위해
해시 테이블을 모두 사용한 Set<T> 구현으로 이 문제를 극복할 수 있을 것이다.
그러나 이러한 접근법을 사용하면 코드의 복잡도가 상당히 증가한다.
'프로그래밍 공부 > OOP' 카테고리의 다른 글
| 18장 예외 처리 (1) | 2023.12.03 |
|---|---|
| 17장 연계된 자료 구조(3) (0) | 2023.12.01 |
| 17 연계된 자료 구조(1) (1) | 2023.12.01 |
| 16장 탬플릿 (1) | 2023.11.30 |
| 15장 다형성과 가상함수 (1) | 2023.11.30 |