dev7

SAX란?

SAX(Simple API for XML)는 XML을 사용하는 웹파일들을 해석할 수 있게 해주는 응용프로그램 인터페이스이다. SAX는 XML 파일을 해석하기 위해 DOM 대신 사용할 수 있는 대안이다. 그 이름이 시사하는 바와 같이 SAX는 DOM에 대해 단순한 인터페이스이며, 처리해야할 파일이 많거나 매우 큰 경우에 적합하다. 그러나 데이터 내용을 조작할 수 있는 기능은 상대적으로 적다. SAX는 이벤트 중심의 인터페이스이다. 프로그래머가 일어날 수 있는 이벤트를 설정해놓으면, SAX는 그 인벤트가 일어났을 때 제어권을 가지고 상황을 처리한다. SAX는 직접 XML 파서와 함께 일한다.

*자막 파일(smi)이 SAX 방식으로 구현되었고 동영상 플레이어는 SAX Parsing으로 각 프레임의 자막을 플레이어에 출력한다. 처리해야할 파일이 많거나 매우 큰 경우 적합한 파싱법이므로 자막 파일에 적당하고 내가 구현하려는 프로젝트에도 가장 적합한 방식으로 보여진다. 

SAX를 사용해서 XML 문서를 파싱하려면 먼저 DefaultHandler를 확장한 클래스가 필요하다. 

또한 JAVA 애플리케이션에서 동적으로 SAX 드라이버를 사용하기 위해 XMLReaderFactory 클래스의 createXMLReader 메소드를 사용해서 XML Reader를 만들어줘야한다. 

여기서 만든 오브젝트를 사용하려면 XML 문서를 파싱할 수 있는데, 먼저 XML Reader 인터페이스에서 setContentHandler와 setErrorHandler 메소드를 사용해 파싱 결과와 에러가 발생하였을 때 리포트하는데 사용되는 핸들러를 등록해준다. 일반적으로 실제 복잡한 애플리케이션에서는 핸들러를 별로의 오브젝트로 만든다. 

기존의 연결 리스트가 단방향 연결 리스트였다면 이중 연결 리스트는 양방향으로 포인터를 가진 연결 리스트이다. 기존의 연결 리스트는 선행 노드를 찾으려면 구조적으로 매우 어렵다. 만약 특정 노드의 선행 노드를 찾기 위해서는 헤드 포인터부터 시작하여 탐색을 하여야 한다.(물론 더 쉽게 구현할 수 있는 방법도 있다.) 이러한 단점을 극복하기 위해서는 노드의 탐색 방향이 양방향으로 자유로워야한다. 

이중 연결 리스트는 하나의 노드가 선행 노드와 후행 노드에 대한 두 개의 포인터를 가진다. 양방향 검색이 가능하단 장점이 있지만 노드별로 포인트를 하나씩 더 가지고 있어야 하므로 공간을 더 많이 차지하게 된다. 

이중 연결 리스트의 한 노드는 다음과 같은 구조를 가지게 된다. 

[ llink | data | rlink ]

typedef struct DList{
      element data;

DList *llink;

DList *rlink;

}

더보기

배열을 사용하여 리스트를 구현하면 구현이 간단하다는 장점이 있지만 크기가 고정되고 경우에 따라 삽입, 삭제 연산에 많은 오버헤드가 발생한다는 단점이 있다. 배열이 아닌 포인터를 이용하면 동적으로 항목을 추가, 삭제하는 리스트인 연결 리스트를 구현할 수 있다. 연결 리스트는 스택, 큐, 트리, 그래프등을 구현하는데에도 사용된다. 

연결 리스트는 항목을 의미하는 데이터와 항목과 항목 사이를 잇는 포인터로 구성된다. 연결 리스트의 데이터는 메모리상에서 어디에서나 흩어져서 존재할 수 있다. 배열은 하드웨어적으로 연속된 메모리 공간으로 구성되지만 연결 리스트는 흩어져 존재하는 각 항목을 다음 항목을 가리키는 포인터를 통해 연결되어 구성된다. 포인터를 이용하면 다음 항목을 쉽게 가리킬 수 있다. 

연결 리스트를 이용하면 배열로 구현한 리스트에서 기존 항목들 사이에 새로운 항목을 삽입할 때 한 쪽의 모든 항목들을 이동시켜야했던 과정이 필요없게 된다. 새로운 항목과 기존 항목의 포인터를 바꾸고 새 포인터를 잇기만 하면 되기 때문이다. 뿐만 아니라 새로운 항목이 필요로 추가할 때마다 동적으로 삽입할 수 있다. 배열과 같이 크기를 정해놓고 메모리를 낭비할 필요가 없어지게 된다. 

이러한 장점이 있지만 연결 리스트는 배열을 이용한 리스트에 비해 구현이 훨씬 까다롭다. 

연결 리스트의 데이터(항목)는 노드(node)라고 부른다. 연결 리스트는 이들 노드들의 집합이며 이들은 데이터를 저장하고 서로 연결되어 있다. 노드는 데이터 필드와 링크 필드로 구성되어 진다. 데이터 필드에는 우리가 저장하고 싶은 데이터가 들어가고 링크 필드에는 다음 노드를 가리키는 포인터가 저장된다. 이 포인터를 이용하여 다음 노드로 이동을 할 수 있다. 그리고 이 연결 리스트의 어떤 항목에 접근하기 위해서는 반드시 첫 번째 노드를 알아야만 한다. 이를 헤드 포인터라 한다. 그리고 연결 리스트의 마지막 노드는 null로 설정된다. 리스트의 마지막 항목을 구분할 때 null 값으로 구분하게 된다. 

연결 리스트는 구조적으로 세 가지의 연결 리스트로 나뉜다. 첫 번째는 가장 기본적인 단순 연결 리스트(singly linked list)이다. 단순 연결 리스트는 한 방향으로만 연결되고 마지막 노드의 링크 필드는 null을 가리킨다. 두 번째는 원형 연결 리스트(circular linked list)이다. 단순 연결 리스트와 비슷하나 맨 마지막 노드의 링크 필드가 첫 번째 노드를 가리킨다. 마지막으로 이중 연결 리스트(doubly linked list)이다. 이중 연결 리스트는 단순 연결 리스트와는 달리 양방향의 링크 필드를 가진다. 다음 노드 뿐만 아니라 이전 노드도 가리킨다는 것이다. 

연결 리스트의 대표적인 연산이 삽입, 삭제 연산이다. 먼저 삽입 연산을 살펴보자면 

-> (10, *) -> (20, *) ->

위와 같이 두 개의 항목 사이에 새로운 항목 (30, *)을 삽입한다고 생각해보면, 

가장 먼저 첫 번째 항목(10,*)이 두번째 항목(20,*)을 가리키는 주소를 새로운 항목의 링크 필드에 복사하여야 한다. 

다음으로 첫 번째 항목(10,*)의 링크 필드를 새로운 항목(30,*)을 가리키도록 하면 된다. 

삽입 함수는 3개의 인자를 전달받는다. 첫 번째로 연결 리스트의 헤드를 가리키는 head 포인터, 다음으로 삽입될 이전 노드를 가리키는 이전 항목 포인터, 다음으로 삽입 할 노드를 가리키는 포인터이다. 

void InsertNore(ListNode **head, ListNode *pre, ListNode *newNode);

다음으로 삭제 연산을 살펴보자면

-> (10, *) -> (30, *) -> (20, *) ->

위와 같이 세 개의 항목중에서 두 번째 항목(30, *)을 삭제한다고 생각해보면,

가장 먼저 삭제할 항목(30, *)의 링크 필드를 첫 번째 항목(10, *)의 링크 필드로 복사하여 준 뒤 삭제할 항목을 바로 메모리 해제하여 주면 된다. 

삭제 함수는 3개의 인자를 전달 받는다. 첫 번째로 삽입 함수와 마찬가지로 연결 리스트의 헤드를 가리키는 head 포인터, 다음으로 삭제될 이전 노드를 가리키는 이전 항목 포인터, 다음으로 삭제 할 노드를 가리키는 포인터이다. 

void removeNore(ListNode **head, ListNode *pre, ListNode *removeNode);

위와 같이 만든 함수는 사용할 때 제약사항이 있는데 이는 다음과 같다.

1. 첫 번째 항목을 삭제하기 위해서는 두번째 인자(pre)를 NULL로, 세번째 인자(removeNode)를 head가 가리키는 주소로 설정해야한다.

2. 특정 위치에 있는 노드를 삭제하기 위해서는 두번째 인자를 삭제할 노드를 가리키는 이전 노드로, 세번째 인자는 삭제할 노드로 설정해야 한다. 노드를 처음 생성할 때 각 노드의 데이터를 가지고 있지 않는다면(예를 들면 insertNode()를 호출할 때 함수내에서 createNode를 호출한다면 노드의 정보를 가지지 않으므로 특정 위치의 노드를 삭제할 수 없게 된다. 만약에 삭제할 노드의 인스턴스는 가지고 있지만 삭제할 노드를 가리키는 이전 노드의 인스턴스는 가지고 있지 않다면 이 또한 삭제할 수 없는 경우이다. 생각해보면 pre 인자로 NULL을 보내고 remoceNode로 삭제할 노드를 설정한채 삭제 함수를 호출한다면 삭제할 노드가 해제는 되겠지만 이전 노드는 여전히 삭제된 노드의 주소를 가리키므로 NullPointer 예외를 발생한다. 

더보기