'COMPUTER TECH/C, C++ 참고자료'에 해당되는 글 20건

  1. 2010.08.13 STL List 사용법 총정리
  2. 2010.08.13 STL (Standard Templete Library)
  3. 2010.08.13 STL - map
  4. 2010.08.13 2. STL - list
  5. 2010.08.13 Pair, Map
  6. 2010.08.13 STL의 Set, Map 사용
  7. 2010.08.13 stl - map사용법 (1)
  8. 2010.08.13 AVL 트리
  9. 2010.08.13 단순 연결리스트
  10. 2010.08.13 이중 연결리스트
STL List 사용법 총정리 (by wono77) *

코딩 by 하얀별....(20070820)

문서 수정 20071116 .. main함수 추가, using name space 추가

                       .. 소스를 긁을 수 있도록 수정

문서 수정 20071117 .. STL Vector 사용법 정리 후,참고 자료 링크 추가

 

STL을 한번 써볼려고해도 제대로 쉽게 정리해 놓은 곳이 별로 없더군요

그래서, STL List 사용법을 나름 간단하게 정리해 보았습니다.

STL List에서의 삽입, find, 소팅, 원소삭제, 해당index에 값 넣기, 개수세기, 모든 원소 삭제, 전체 값 출력하기를 어떻게 사용해야할지 코드를 통해 살펴보도록 하겠습니다..

 

실행화면은 아래와 같습니다.

 

 

위 화면 출력을 위한 코드는 아래와 같습니다.

 

 

#include <stdio.h>
#include <list>
#include <iostream>
#include <algorithm> //find()를 위해 필요

 

using namespace std;

 

//STL LIST 테스트를 위한 함수
void stl()
{

    list<char>  list1;
 //리스트의 반복을 가리키는 반복자 선언
    list<char>::iterator itor;// = list1.begin();      // 따로, 또는 이렇게 ..
 itor=list1.begin(); //시작을 가리키도록 한다.
      //이 부분이 없으면 동작안함.
  
 //-----------------------------------------
 //값 삽입
 //-----------------------------------------

 cout<< "--- c, b, a 값 삽입 ---" << endl;
    list1.push_front('c');
    list1.push_back('b');
    list1.push_back('a');

 //처음부터 끝까지 값 출력
 for(itor=list1.begin(); itor != list1.end(); itor++)
 {
  cout<< *itor << endl;
 }

 //-----------------------------------------
 //포인터  rewind  연습
 //-----------------------------------------

 /*
 itor=list1.begin(); //앞으로 다시 감기
 //끝에 도달할때까지 데이터 출력
 while(list1.end()!=itor)
 {
  cout<< *itor << endl;
  itor++;
 }
 */
 
 //-----------------------------------------
 //find -처음부터 끝까지 뒤져서 index를 던지고 있나 본다.
 //단 include <algorithm>
 //반환값은 반복자, 즉 *itor이다.
 //-----------------------------------------

    itor=find(list1.begin(), list1.end(), 'a');
 cout<< "----- find (a를 찾아 그 위치에 d를 삽입한다.) ----" << endl;
 //찾아낸 값이 있는 앞 위치에 집어 넣기
 //없으면 맨 뒤에 들어간다.
 list1.insert(itor,'d');
 
 //처음부터 끝까지 값 출력
 for(itor=list1.begin(); itor != list1.end(); itor++)
 {
  cout<< *itor << endl;
 }
 //-----------------------------------------
 //소팅
 //-----------------------------------------

 cout<< "----- sorting ----- " << endl;
 list1.sort();
 //처음부터 끝까지 값 출력
 for(itor=list1.begin(); itor != list1.end(); itor++)
 {
  cout<< *itor << endl;
 }
 //-----------------------------------------
 //b 삭제하기
 //-----------------------------------------

 cout<< "----- remove b ----- " << endl;
 itor=find(list1.begin(), list1.end(), 'b');
 list1.erase(itor);
 for(itor=list1.begin(); itor != list1.end(); itor++)
 {
  cout<< *itor << endl;
 }

 //-----------------------------------------
 //STL에서 해당 index 위치에 값을 넣는 방법
 //STL의 index는 맨처음이 0이다.
 //-----------------------------------------

 int i=0;
 int index=2;
 cout<< "----- 해당 index 위치(2)에 값 f 넣기  ----- " << endl;
 for(itor=list1.begin(); itor!= list1.end(); itor++, i++)
 {
  if(i==index) break;
  //cout<< *itor << endl;
 }
 //삽입
 list1.insert(itor,'f');
 //전체 출력
 for(itor=list1.begin(); itor != list1.end(); itor++)
 {
  cout<< *itor << endl;
 }

 //-----------------------------------------
 // 갯수 세기
 //-----------------------------------------

 cout<< "----- 전체 리스트의 갯수 세기   ----- " << endl;
 cout<< list1.size()<< endl;;

 //-----------------------------------------
 // 모두 삭제하기
 //-----------------------------------------

 
 cout<< "----- 리스트 모두 삭제하기   ----- " << endl;
 for(itor=list1.begin(); itor != list1.end();)
 {
  //if(list1.empty()) break;
  list1.erase(itor++); //erase의 경우 후위형 연산자로만 증가시켜야함
 }
 
 list1.clear();

 //전체 출력
 for(itor=list1.begin(); itor != list1.end(); itor++)
 {
  //if(list1.empty()) break;
  cout<< *itor << endl;
 }
 
}//End of stl()

 

void main(){
 stl();
}

 

------------------------------------------------------------------------------------------

STL 강좌 참고 URL:

서울대 OOPSLA lab(컴퓨터공학부 객체지향시스템 연구실)에 있는 사람의 개인홈피

http://idb.snu.ac.kr/~sjjung/stl/ 

stl 튜토리얼 번역본 저자분이다. 아래책..

 


관련 참고:

STL Vector 사용법 - http://blog.naver.com/wono77/140044776369

 

추가 : 20071220

STL List는 위에는 제가 처음 테스트 할때라 저렇게 코드를 적었지만, Add, Del, Get, Insert을 사용하기 편한 자신만의 함수를 만들어서 사용하는게 좋을 듯합니다. 차후에 한번 정리해 보아야겠군요.. 그냥 쌩으로 iterator를 가져다 써버리면 너무 지저분한듯 합니다.

 

추가 : 20080416

요즘은 STL 책으로 이걸 추천하네요.

이펙티브 STL

저도 이거 한번 사 볼 생각입니다..

 

 
stl ietrator에 포인터를 집어 넣었을 때, 해제를 직접 해주지 않으면,
메모리가 끝까지 사라지지 않더군요.

다음에는 그 내용에 관련해서 글을 한번 정리해 보겠습니다.

 


'COMPUTER TECH > C, C++ 참고자료' 카테고리의 다른 글

STL List 사용법 총정리  (0) 2010.08.13
STL (Standard Templete Library)  (0) 2010.08.13
STL - map  (0) 2010.08.13
2. STL - list  (0) 2010.08.13
Pair, Map  (0) 2010.08.13
STL의 Set, Map 사용  (0) 2010.08.13
Posted by ... XJAPAN

이번에는 반복자(Iterator)의 사용에 대한 것들입니다. 앞으로 한번 만 더 올리면
STL 기초는 마무리가 될거 같네요....
------------------------------------------------------------------------
STL (Standard Templete Library) part-9

Yonghan, Yoon
yonghany@orgio.net
------------------------------------------------------------------------
                            THE WAITE GROUP's
                   Object-Oriented Programming in C++
                              Third Edition
                           Robert Lafore(Author)
                              SAMS(Publisher)
------------------------------------------------------------------------

4.4 Iterators at Work

지금까지 이터레이터에 대해서 복잡하게 떠들었지만, 백문이불여일견! 직접 사용해보면
의외로 간단하다. 이미 앞에서 몇가지 예를 살펴보았듯이 일반적으로 사용되는 이터레이터들은
콘테이너의 begin(), end()가 이터레이터의 값을 리턴하게된다. 여태까지 이러한 함수들이
리턴하는 이터레이터 값이 포인터로만 취급된다고 말해었지만, 이젠 이러한 이터레이터들이
다른 함수에서 어떻게 사용되는지 확실하게 살펴보자.


4.4.1 Data Access
랜덤 액세스 이터레이터를 제공하는(vector, deque) 콘테이너에서는 [] 오퍼레이터를 이용하여
쉽게 엘리먼트를 참조했다. 랜덤 액세스를 지원하지 않는 list 같은 콘테이너는 이것과는 다른
방식의 참조 방법이 필요하다. 앞에서 들었던 예 중에 아이템을 하나씩 pop 해서 리스트의
내용을 display하기위해 "LIST"와 "LISTPLUS" 예제에서 destructive readout을
사용했었다. 이걸 좀더 심화하여 콘테이너에 정의된 이터레이터를 사용해보자.

// listout.cpp
// iterator and for loop for output
#include <iostream>
#include <list>
#include <algorithm>
using namespace std;

int main()
	{
	int arr[] = {2, 4, 6, 8 };
	list<int> theList;
	
	for (int k=0; k<4; k++) // 배열의 엘리먼트로 리스트를 채운다.
		theList.push_back(arr[k]);
	
	list<int>::iteratior iter; // iterator to list-of-ints
	
	for (iter=theList.begin(); iter != theList.end(); iter++)
		cout << *iter << ' '; // display the list
	
	cout << endl;
	
	return 0;
}


이 프로그램은 단순히 theList 콘테이너의 내용을 보여주는 것이다. 결과는

2 4 6 8

이다.

위에서 콘테이너의 타입과 매치시키기위해 list<int>타입의 이터레이터를 선언했다. 마치
포인터를 사용하듯이 이터레이터를 사용하기 전에 먼저 초기값을 설정해야 한다. 
for 루프에서 iter = theList.begin() 구문으로 리스트의 첫부분으로 초기화를 해주었다.
++ 오퍼레이터로 포인터를 증가시켜 *오퍼레이터로 이터레이터가 가리키고 있는 값을 역참조 했다.
그리고 루프의 종료는 이터레이터가 콘테이너의 끝에 다다랐나를 체크함으로써 처리를 해주었다.
또한 for 루프와 기능적으로 동일하게 작동하게 하기 위해서 while 루프를 이용할 수 도 있다.

iter = theList.begin();
while ( iter != theList.end() )
	cout << *iter++ << ' ';

*iter++ 문법은 포인터와 같다.




4.4.2 Data Insertion

아래의 LISTFILL 예제를 통해 콘테이너의 엘리먼트가 이미 존재하는 곳에 데이터를 삽입하는
과정을 살펴보자.

// listfill.cpp
// uses iterator to fill list with data
#include <iostream>
#include <list>
using namespace std;

int main()
	{
	list<int> iList (5); // empty list holds 5 ints
	list<int>::iterator it; // iterator
	int data = 0;

	// fill list with data
	for (it=iList.begin(); it != theList.end(); it++)
		*it = data + 2;

	// display the list
	for (it=iList.begin(); it != theList.end(); it++)
		cout << *it << ' ';
	cout << endl;

	return 0;
}


첫번째 for 루프는 콘테이너에 int 값은 2, 4, 6, 8, 10으로 채운다. 그리고 두번째 for
루프는 이 값들을 보여준다.



4.4.3 Algorithms and Iterators

우리가 얘기했던 알고리즘들은 인자로 이터레이터를 이용한다. 그리고 때론 값을 리턴하기도 한다.
ITERFIND 예제는 find() 알고리즘이 리스트에 적용되는 걸 보여준다. (이미 알고있겠지만
find()알고리즘은 오직 input 이터레이터만 필요하기때문에 list와 함께 쓰일 수 있다.)

// ITERFIND.cpp
// find() returns a list iterator
#include <iostream>
#include <list>
#include <algorithm>
using namespace std;

int main()
	{
	list<int> iList (5); // empty list holds 5 ints
	list<int>::iterator it; // iterator
	int data = 0;

	// fill list with data
	for (it=iList.begin(); it != theList.end(); it++)
		*it = data + 2; // 2, 4, 6, 8, 10

	it = find (iList.begin(), iList.end(), 8);
	if (it != iList.end())
		cout << "\nFound 8.\n";
	else
		cout << "\nDid not find 8.\n";

	return 0;
}

find() 알고리즘은 3개의 인자를 취한다. 첫번째와 두번째 인자는 검색될 범위를 나타내는 이터레이터이고,
세번째 인자는 찾을 값이다. find()가 iList.end()를 리턴했다면 값을 찾지 못하고 끝에
도달한 것이고 그렇지 않다면 그 값이 있는 곳을 가리키고 있을 것이다. 위의 결과는 아래와 같다.

Found 8.

그렇다면 검색한 값 8이 콘테이너에서 몇번째 위치에 있는지 어떻게 알수 있을까? 아마도
일치되는 아이템의 offset에서 시작 이터레이터를 빼주면 될것이라고 생각할 것이다.
(it - iList.begin()). 그러나 이것은 리스트의 이터레이터로 사용된 올바른 오퍼레이션이 아니다.
리스트 이터레이터는 단지 bidirectional 이터레이터다. 따라서 여기에 산술 오퍼레이션을
수행할 수 없고 랜덤 액세스를 지원하는 vector나 deque에서나 산술 오퍼레이션을 쓸 수 있다.
그러므로 iList가 아니라 벡터 v라면 위의 코드를 다시 써서 검색 위치를 나타낼 수 있다.

it = find (v.begin(), v.end(), 8);
if (it != v.end())
	cout << "\nFound 8 at location " << (it - v.begin());
else
	cout << "\nDid not find 8.";

위의 결과는 

Found 8 at location 3

이 될 것이다.

인자로 이터레이터를 받는 다른 예제를 보자. vector를 copy() 알고리즘으로 다른 vector로 복사하는데
인자로 복사원본의 범위와 목적 콘테이너를 적어준다.

// itercopy.cpp
// uses iterators for copy() algorithm
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
	int beginRange, endRange;
	int arr[] = { 11,13,15,17,19,21,23,25,27,29};
	vector<int> v1 (arr, arr+10); // 벡터 초기화
	vector<int> v2 (10); // 초기화되지 않은 벡터
	
	cout << "Enter range to be copied (example: 2 5: ";
	cin >> beginRange >> endRange;
	
	vector<int>::iterator iter1 = v1.begin() + beginRange;
	vector<int>::iterator iter2 = v1.begin() + endRange;
	vector<int>::iterator iter3;
	
	// copy from v1 to v2
	iter3 = copy (iter1, iter2, v2.begin());
	// iter3에는 마지막 아이템이 복사된다.
	
	iter1 = v2.begin();
	while (iter1 != iter3)
		cout << *iter1++ << ' ';
	cout << endl;

	return 0;
}

범위를 입력해주면 결과는

Enter range to be copied (example: 2 5): 3 6
17 19 21

이 될 것이다. v2의 모든 아이템을 보여줄 필요없이 복사된 것만 보여주면 된다. 다행히도
copy() 알고리즘은 복사될 콘테이너의 마지막 포인터(이터레이터)를 리턴한다. 이 프로그램은
이 값을 이용하여 복사된 값들을 display하게 했다.





4.5 Speialized Iterators

이번 장에서는 특별한 이터레이터 형태 2가지를 살펴본다. 첫번째는 흥미있는 방법으로 
이터레이터의 작동을 변경할 수 있는 이터레이터 어뎁터와 마치 이터레이터 처럼  동작하는
입력과 출력 스트림을 허용하는 스트림 이터레이터들이다.



4.5.1 Iterator Adapters

STL의 이터레이터는 보통 3개의 변종을 제공한다. 이런것들에는 reverse iterator,
insert iterator, raw storage iterator가 있다. reverse iterator는 콘테이너의 내용을
역순으로 참조하기위해 사용되고, insert iterator는 copy()나 merge()같은 알고리즘이 콘테이너의
내용을 변경시키고자 때 사용된다. 따라서 데이터가 있는 곳에 덮어쓰게 된다. 마지막으로
raw storage iterator는 초기화되지 않은 메모리로 결과를 저장하고자 할때 사용하면 된다.
그러나, raw storage iterator는 특별한 경우에만 사용된다. 그러므로 이 내용은 다루지 않을 것이다.

4.5.1.1 Reverse Iterators

콘테이너의 끝에서 부터 역순으로 반복하기를 원한다고 가정해보자.
언뜻 생각하기에 다음처럼 하고 싶을 것이다.

list<int>::iterator iter;
iter = iList.end();
while ( ier != iList.begin() )
	cout << *iter-- << ' ';

하지만 불행하게도 위의 코드는 돌아가지 않는다. 이유는 단 한가지, 범위가 틀리기 때문이다.
(n-1 부터 0까지 여야 되지만 위의 코드는 n 부터 0까지 가 된다)
역순으로 반복하고 싶을때는 reverse iterator를 사용하면 된다. ITEREV 프로그램은 
역순으로 데이터를 보여주기 위해 reverse iterator가 사용된 경우를 보여준다.

// iterev.cpp
// demonstrates reverse iterator
#include <iostream>
#include <list>
using namespace std;

int main()
	{
	int arr[] = {2, 4, 6, 8, 10};
	list <int> theList;
	
	for (int j=0; j<5; j++)
		theList.push_back( arr[j] );
	
	list< int>::reverse_iterator revit;
	
	revit = theList.rbegin();
	while (revit != theList.rend() )
		cout << *revit++ << ' ';
	cout << endl;
	return 0;
	}

이 프로그램의 결과는

10 8 6 4 2

가 된다. reverse iterator를 사용할때 rbegin()과 rend()를 사용한다(이걸로 정상적
순서로된 이터레이터에 적용하면 않된다. -_-; ) 당황스럽겠지만 콘테이너의 끝에서부터 시작하기위해
멤버함수는 rbegin()을 사용해야하고 이터레이터를 --하지 말고 ++해야 한다.
reverse iterator는 항상 ebegin()으로 시작하고 rend()로 끝나고, 이터레이터를 증가
시켜야한다.


4.5.1.2 Insert Iterators

copy() 같은 일부 알고리즘들은 존재하는 내용위에 덮어쓰는 경우가 있다. COPYDEQ 프로그램은
다른 데큐로 복사하는 예를 보여준다.

// copydeq.cpp
// demonstrates normal copy with deques
#include <iostream>
#include <deque>
#include <algorithm>
using namespace std;

int main()
	{
	int arr1[] = {1, 3, 5, 7,  9};
	int arr2[] = {2, 4, 6, 8, 10};
	deque <int> d1;
	deque <int> d2;
	
	for (int j=0; j<5; j++) {
		d1.push_back( arr1[j] );
		d2.push_back( arr2[j] );
	}

	// d1 을 d2로 복사한다.
	copy (d1.begin(), d1.end(), d2);
	
	for (int k=0; k<d2.size(); k++)
		cout << d2[k] << ' ';
	cout << endl;
	return 0;
	}

이 프로그램의 결과는 1 3 5 7 9 가 된다.

d2를 들여다 보면 d2가 가지고 있던 내용들이 d1의 겻들로 덮어 쓰여진 것이다.
이런 동작은 일반적인 것이다. 하지만 때로는 copy() 보다는 콘테이너에 새로운 엘리먼트를
추가하고 싶을때도 있을 것이다. 이때는 insert 이터레이터를 사용하면 된다. 이것의 세가지
변종을 보자

	● back_iterator : 뒤에다 new 엘리먼트를 넣는다.
	● front_iterator : 앞에다 new 엘리먼트를 넣는다.
	● inserter : new 아이템을 원하는 위치에 넣는다.

DINSITER 프로그램은 back_iterator의 사용 예를 보여준다.

// dinsiter.cpp
// demonstrates insert iterators with queues
#include <iostream>
#include <deque>
#include <algorithm>
using namespace std;

int main()
	{
	int arr1[] = {1, 3, 5, 7,  9};
	int arr2[] = {2, 4, 6,};
	deque <int> d1;
	deque <int> d2;
	
	for (int i=0; i<5; i++)
		d1.push_back( arr1[i] );
	for (int j=0; j<3; j++)
		d2.push_back( arr2[j] );

	// d1 을 d2로 복사하는데 순서는 역순이된다.
	copy (d1.begin(), d1.end(), back_iterator (d2));
	
	cout << "\nd2: ";
	for (int k=0; k<d2.size(); k++)
		cout << d2[k] << ' ';
	cout << endl;
	return 0;
	}

타겟 콘테이너의 뒤에다가 삽입하기 위해 back_iterator는 push_back() 멤버함수를 이용하고
소스 콘테이너의 내용은 변함이 없다. 이 프로그램의 결과는 원래 d2의 내용에 d1의 내용이 
추가된
2 4 6 1 3 5 7 9
가 된다.

만일 front iterator를 사용한다면

copy (d1.begin(), d1.end(), front_iterator (d2));

push_front() 멤버함수를 이용하여 앞에서부터 삽입해나간다.

결과: 9 7 5 3 1 2 4 6

또한 임의의 위치에 new 아이템을 추가할 수도 있다. 아래는 d2의 처음에 d1을 추가하는 것이다.

copy (d1.begin(), d1.end(), inserter (d2, d2.begin()));

결과: 1 3 5 7 9 2 4 6


여기서 주의할 점은 inserter의 두번째 인자는 vector에서는 사용할 수 없다는 것이다.
이유는 vector에는 push_front() 메쏘드가 없기 때문이다. 백터는 무조건 끝에서부터
접근이 가능하다.



4.5.1.3 Stream Iterators

스트림 이터레이터는 화일 과 I/O 디바이스(cin이나 cout)를 이터레이터로 다룰수 있는 방법을 제공한다.
이것은 알고리즘의 인자로 파일과 IO 디바이스를 이용하여 쉽게 처리할 수 있게 해준다.
input과 output이터레이터의 주목적이 이러한 스트림 이터레이터 클래스를 지원하는 것이다.
알고리즘은 직접 input과 output이터레이터를 사용할수 있게된다. 사실 스트림 이터레이터는
서로 다른 input이나 output을 템플릿화한 것이다. 여기에는 두가지의 스트림이 이터레이터가 있는데
ostream_iterator와 istream_iterator이다.



4.5.1.3.1 The ostream_iterator Class

 ostream_iterator 오브젝트는 어떤 알고리즘이나 인자로 사용할 수 있다. 

// outiter.cpp
// demonstrates ostream_iterator
#include <iostream>
#include <algorithm>
#include <list>
using namespace std;

int main()
{
	int arr [] = { 10, 20, 30, 40, 50 };
	list <int> theList;
	
	for (int j=0; j<5; j++)
		theList.push_back (arr[j]);
	
	ostream_iterator<int> ositer(cout, ","); // ostream iterator
	
	cout << "\nContents of list: ";
	copy (theList.begin(), theList.end(), ositer); // display list
	cout << endl;
	return 0;
}

여기서는 int 값을 읽기 위해 ostream iterator를 정의했다. 생성자의 첫번째 인자는
int 값이 씌어질 스트림 value이고, 두번째 인자 문자열은 각 값마다 덫붙는 문자열이다.
일반적으로 stream value는 화일명이나 cout이면 된다.
copy() 알고리즘은 리스트의 내용을 cout으로 복사하게된다. copy()의 세번째 인자가 바로
ostream iterator를 나타낸다.
위의 결과는 다음과 같다.

Contents of list: 10, 20, 30, 40, 50,


다음 예제 FOUTITER는 ostream iterator로 화일을 사용하는 것을 보여준다.

// outiter.cpp
// demonstrates ostream_iterator with files
#include <fstream>
#include <algorithm>
#include <list>
using namespace std;

int main()
{
	int arr [] = { 11, 21, 31, 41, 51 };
	list <int> theList;

	for (int j=0; j<5; j++)
		theList.push_back (arr[j]);
	
	ofstream outfile ("ITER.DAT"); // create file object
	
	ostream_iterator<int> ositer(outfile, " "); // ostream iterator
	
	cout << "\nContents of list: ";
	copy (theList.begin(), theList.end(), ositer); // display list

	return 0;
}

화일과 연계하기 위해서는 반드시 ofstream을 선언해야한다. 프로그램을 실행하고
메모장으로 ITER.DAT를 열어보면 다음과 같은 결과를 확인할 수 있다.

11 21 31 41 51


<EOF>
------------------------------------------------------------------------
NEXT: 4.5.1.3.2 The istream_iterator Class
 

'COMPUTER TECH > C, C++ 참고자료' 카테고리의 다른 글

STL List 사용법 총정리  (0) 2010.08.13
STL (Standard Templete Library)  (0) 2010.08.13
STL - map  (0) 2010.08.13
2. STL - list  (0) 2010.08.13
Pair, Map  (0) 2010.08.13
STL의 Set, Map 사용  (0) 2010.08.13
Posted by ... XJAPAN

3. map
   3.1 인크루드 헤더
      #include <map>
      using namespace std;

 

   3.2 map 선언
      형식)
         map<key 형, value 형>  변수명;

 

      예1)
         map<int, float>  mp;

 

      예2)
         map<int, int*>  mt;

 

      예3)
         map<string, VECTOR3*> mp;

 

   3.3 map 사용
      3.3.1 값 추가
         예1)
            map<int, float> mp;
            mp[3] = 10.0f;  // 3이라는 key값으로 value 10.0f가 map에 추가 된다.

         주의!
            []안의 key값이 이미 추가된 key라면 기존 데이터가 업데이트 된다

 

         예2)
            map<int, float> mp;
            int   k = 10;
            foat   f = 20.12f;
            mp[k] = f;  // k값 10이 key값으로 f의 값 20,12f가 value 값으로 map에 추가

 

     3.3.2 값 참조
         begin() : map의 첫 번째 데이터가 들어있는 주소를 리턴해준다.
         end() : map의 마지막 데이터가 들어있는 다음 주소를 리턴해준다.
         find() : map에서 key값으로 value를 찾는다.

 

         예1)
            map<int, float>::iterator i;
            for( i = mp.begin(); i != mp.end(); i++ )
            {
               float f = i->second; // i->second에 값이 들어있다, 또한 i->first는 key값이 된다.
            }

 

         예2) key값으로 value을 참조
            map<int, float>::iterator i;
            i = mp.find( 3 );  // key값 3과 일치하는 데이터를 찾는다
            if( i != mp.end() ) // map의 끝이 아니라면 key에 해당하는 value를 찾은 것이다
            {
               float f = i->second; // map의 value는 second 들어있다
            }

 

      3.3.3 데이터의 개수 검사
         int nCount = mp.size(); // map에 들어있는 데이터의 개수를 리턴해 준다

 

      3.3.4 데이터의 제거
         erase() : map의 데이터 1개를 제거한다
         clear() : map의 모든 데이터를 제거한다

 

         예1) key값으로 데이터 제거
            map<int, float>::iterator i;
            float  f;
            i = mp.find( 3 );
            if( i != mp.end() )
            {
               mp.erase( i );
            }

 

         예2)
            map<int, float>::iterator i;
            float  f;
            for( i = mp.begin(); i != mp.end(); )
            {
               f = i->second;
               if( f <= 1.0f )
               {
                  mp.erase( i++ ); // 인자로 i++을 해줘야지만 다음 주소를 가리키게 된다.
               }
               else
               {
                  i++;  // 여기서 i++연산을 하자
               }
            }

 

         예3) erase()를 사용한 map의 모든 데이터 제거
            map<int, float>::iterator i;
            for( i = mp.begin(); i != mp.end(); )
            {
               mp.erase(i++);
            }

 

'COMPUTER TECH > C, C++ 참고자료' 카테고리의 다른 글

STL List 사용법 총정리  (0) 2010.08.13
STL (Standard Templete Library)  (0) 2010.08.13
STL - map  (0) 2010.08.13
2. STL - list  (0) 2010.08.13
Pair, Map  (0) 2010.08.13
STL의 Set, Map 사용  (0) 2010.08.13
Posted by ... XJAPAN

 list
   2.1 인크루드 헤더
      #include <list>
      using namespace std;

 

   2.2 list 선언
      형식)
         list<데이터형>  변수명;

 

      예1)
         list<int>  lt;

 

      예2)
         list<int*>  lt;

 

      예3)
         list<VECTOR3*> lt;

 

   2.3 list 사용
      2.3.1 값 추가
         예1)
            list<int> lt;
            lt.push_back( 10 ); // list의 맨 마지막에 10이 추가된다.

 

         예2)
            list<int> lt;
            int   i = 10;
            lt.push_back( i );  // list의 맨 마지막에 i의 값 10이 추가된다.

 

         예3)
            lt.insert( lt.begin(), 100 );  // list의 첫 번째에 100 추가

         주의! list는 임의 위치를 데이터를 직접 사용할 수 없다.

            즉, "lt.begin()+2" 이런거 안된다.

 

      2.3.2 값 참조
         begin() : list의 첫 번째 데이터가 들어있는 주소를 리턴해준다.
         end() : list의 마지막 데이터가 들어있는 다음 주소를 리턴해준다.

 

         예)
            list<int>::iterator i;
            for( i = lt.begin(); i != lt.end(); i++ )
            {
               // i는 list에서 값이 들어있는 주소에 해당한다
            }

 

      2.3.3 데이터의 개수 검사
         int nCount = lt.size(); // list에 들어있는 데이터의 개수를 리턴해 준다

 

      2.3.4 데이터의 제거
         erase() : list의 데이터 1개를 제거한다
         clear() : list의 모든 데이터를 제거한다

 

         예1)
            list<int>::iterator  i;
            int  k;
            for( i = lt.begin(); i != lt.end(); )
            {
               k = *i;
               if(k == 0)
               {
                  lt.erase( i++ ); // 인자로 i++을 해줘야지만 다음 주소를 가리키게 된다.

               }
               else
               {
                  i++;  // 여기서 i++연산을 하자
               }
            }

 

         예2) erase()를 사용한 list의 모든 데이터 제거
            list<int>::iterator i;
            for( i = lt.begin(); i != lt.end(); )
            {
               lt.erase( i++ );
            }

 

'COMPUTER TECH > C, C++ 참고자료' 카테고리의 다른 글

STL (Standard Templete Library)  (0) 2010.08.13
STL - map  (0) 2010.08.13
2. STL - list  (0) 2010.08.13
Pair, Map  (0) 2010.08.13
STL의 Set, Map 사용  (0) 2010.08.13
stl - map사용법  (1) 2010.08.13
Posted by ... XJAPAN

pair

pair <자료형, 자료형>

2개 한쌍..

map 에 자료 입력시 주로 사용 ( typedef  pair<int, int>  DataPair


map

map<Key, Elements>

중복 허용 안함.

Member
 - .clear() : 비우기
 - .empty() : 비었는지 결과리턴
 - .begin() , .end() : 처음과 끝의 iterator 리턴
 - .size() : 크기 리턴 (size_t형)
 - .insert( pair<key, elements> ) : 삽입
 - .find( elements ) : elements 검색 후 iterator 리턴

 

1. 맵의 생성

map <Key, Elem>  m_MemberVariable;  //기본적인 생성 방법이다

 

2. 유용함 함수들

c.size()

실제 원소의 개수를 반환

c.empty()

컨테이너가 비어 있는지를 판단

c.max_size()

컨테이너가 가질 있는 최대 원소의 개수를 반환

 

3. 검색 함수들

find(key)

key 값을 가지는 원소의 위치를 반환한다. 만약 존재 하지 않는 다면 end() 반환한다.

 

4. 반복자 함수

c.begin()

번째 원소에 대한 양방향 반복자를 반환한다

c.end()

마지막 원소 뒤를 가리키는 양방향 반복자를 반환한다

 

 

5. 삽입 제거 함수

c.insert(elem)

elem 복사본을 삽입하고, 새로운 원소의 위치를 반환한다

c.erase(key)

key 원소를 제거한다

c.erase(pos)

반복자 pos 위치로 원소를 제거한다.

c.clear()

모든 원소들을 제거한다.                                                                

 

6. 연관 배열처럼 map 사용하기

m[key]

key key 가진 원소의 값을 레퍼런스로 반환한다.

만약 key 존재하지 않는다면 key 가진 원소를 삽입한다


'COMPUTER TECH > C, C++ 참고자료' 카테고리의 다른 글

STL - map  (0) 2010.08.13
2. STL - list  (0) 2010.08.13
Pair, Map  (0) 2010.08.13
STL의 Set, Map 사용  (0) 2010.08.13
stl - map사용법  (1) 2010.08.13
AVL 트리  (0) 2010.08.13
Posted by ... XJAPAN
 
 
음... 이 이번 강좌를 쓰기 전에 하나의 그림을 보여주려고 합니다.
바로 위의 그림입니다.
위의 그림을 보면서 SetMap Container 에 대해 빠른 이해(?)를 주려고 합니다.
 
뭐 그럼..
일단 Set 부터 쓰겠습니다.
 
 
- Set 이란 >  Set은 단어 뜻 그대로 집합을 의미한다. 물론 이는 동일한 자료형들을 모아 놓은 것이다. 또한 위의 그림에서 보았듯이 Set은 저장하는 데이터 자체가 키로 사용되며 값은 저장되지 않는다. 동일한 자료형이라는 측면에서는 Vector와 유사해 보이지만 정렬된 위치에 삽입된다는 아주 큰 차이점을 가지고 있다.
   또한, Set은 키의 중복을 허용하지 않는다. 이는 DB를 하는 분이라면 빠른 이해가 될 가능성이 높아 보인다. DBTable 등 에서는 Key의 값은 중복이 불가능하다. 하지만 Set에는 특별히 Multi-Set이라는 것이 있다. 하지만 Set의 주요 용도는 이러한 부분이 아니다. 그럼, Set의 대표적인 사용 용도에 대해 알아보자. Set은 특별히 주민등록번호를 저장할때 주로 사용한다. 이 좁은(?) 대한민국 (The Republic Of Korea (SK))에서 자신과 주민등록번호가 일치하는 사람이 존재한다면 큰 낭패이다. 고로 중복을 허용치 않는다. 하지만 Set은 이런 경우를 제외하고는 잘 사용되지 않는다.
 
그럼.. 위의 그림을 다시 한번 보면서 아래의 예제 소스를 분석해보도록 하죠.
 
- Example.l16.Set -
 

#include <iostream>

#include <set>

#include <algorithm>

using namespace std;

<?xml:namespace prefix = o /><?xml:namespace prefix = o /><?xml:namespace prefix = o /> 

void main()

{

     set<int> s;                           // 이 점은 모든 STL-Container들이 비슷하다.

     s.insert(1);                          // Set의 삽입

     s.insert(2);

     s.insert(3);

 

     set<int>::iterator it;               // iterator 에 대해선 앞 강좌에서 설명하였다.

     it=s.find(2);

     if (it != s.end()) {

          cout << *it << endl;        // Set의 값이 존재하면 출력.

     } else {

          cout << "Error!" << endl;

     }

}

 
 
자.. 그럼 Set에 대해 이해가 오셨죠? 이해가 가셧나?/.....
 
뭐..어쨋든 그럼 Map 에 대해 설명하겠습니다.
 
 
- Map 이란? > Map은 Set과는 다르게 키와 값을 동시에 관리한다. 연관이 있는 두 쌍의 컨테이너를 관리하기 때문에 가장 대표적인 연관 컨테이너라고 볼 수도 있다. Set과 마찬가지로 Data를 정렬시켜 저장하므로 키값으로 빠르게 검색할 수 있다. 참고로 Map 의 정렬 기준은 키값이다. 또한 Map은 Set과 거의 유사하다. Set과 마찬가지로 Map 은 한 키에 해당하는 하나의 값만 저장할 수 있지만, Multi-MapMulti-Set과 마찬가지로 여러 값을 동시에 저장하는 것이 가능하므로 용이하다. 또 Map은 연관성이 있는 Data의 관게를 구현하는데 주로 사용된다. 예를 들어 대한민국 국민의 주민등록번호와 이름의 관계이다. 번호를 키로, 이름을 값으로 하여 하나의 짝으로 묶어서 맵에 정렬된 상태를 저장하면 번호로 부터 이름을 빠르게 검색할 수 있다. 하지만 이름을 키값으로, 주민등록번호를 값으로 저장한다면, 이런 경우에 Multi-Map을 사용해야 한다. 대한민국 땅안에는 동명 이인이 있을 가능성이 있기 때문이다. 앞의 예에서 봤듯이, Map은 연관이 있는 두 Data의 쌍을 관리하므로 Set보다는 훨씬 실용적이고 사용 빈도가 비교적 높다. 고로 STL-Sequence-Container중에 Vector를 가장 많이 사용된다고 가정하면 그 다음 순위는 바로 Map이다.
 
자.. Map의 사용빈도가 높다는거.. 참고해두셔야 되구요..
뭐.. 이런거 그냥 배열이나 C연결리스트로 해도 되긴 되지만... (키와 셋값이 모두 int형이 경우)
 
가끔씩 Map으로 구현하는게 훨씬 간편하고 실용적일 때가 있다. 그런 경우를 위해 공부해보자.
 
그럼.. 위의 그림을 다시 한번 보고 오세요.
 
 
보고 오셨다면... 바로 예제 소스 분석 들어갑니다..
 
- Example.l16.Map -
 include <iostream>

#include <string>

#include <map>

using namespace std;

 

void main()

{

     map<string,int> m;                                            // Map 생성. Key=String형 , 값=int형

     m.insert(pair<string,int>(string("서울"),1000));      // Map에 Data를 삽입하는 방법 1

     m.insert(pair<string,int>("부산",500));

     m["대전"]=400;                                                 // Map에 Data를 삽입하는 방법 2

     m["대구"]=300            

     m["광주"]=200;

     m["인천"]=100;

     m["독도"]=1;

 

     m.erase(m.begin());

     m.erase("인천");

 

     map<string,int>::iterator it;

     for (it=m.begin();it!=m.end();it++) {

          cout << it->first << ":" << it->second << "만명" << endl;

     }

}

- 소스출처 : WinApi
 
자.. 이번에는 Winapi의 소스를 약간 참고하겠습니다.
 
물론 모든 데이터를 삽입할 때에는 정렬되어 들어갑니다. (키값 기준.)
나머지는.. 앞에서 한 Container들과 모두 비슷할 껍니다..
 

'COMPUTER TECH > C, C++ 참고자료' 카테고리의 다른 글

2. STL - list  (0) 2010.08.13
Pair, Map  (0) 2010.08.13
STL의 Set, Map 사용  (0) 2010.08.13
stl - map사용법  (1) 2010.08.13
AVL 트리  (0) 2010.08.13
단순 연결리스트  (0) 2010.08.13
Posted by ... XJAPAN

1. 맵(Map)이란?

 맵(Map)은 set, multiset, multimap등과 같이 STL이 제공하는 자료형 중 하나이다.


2. 맵(Map)의 특징

 첫번째, 두 개의 요소가 한 쌍을 이루어 하나의 자료를 이룬다.  첫 번째 요소는 first로써 인덱스이고, 두 번째 요소는 second로써 데이터이다. 그러므로, 인덱스와 데이터가 분리된 상태이며 독립적으로 자료형을 지정해줄 수 있다.

두번째, 반복자(iterator)와 배열 첨자를 사용하여 접근할 수 있다.
 
 세번째, 자동적으로 정렬된 상태를 유지한다. 만약에 정렬할 수 없다면 출력 순서는 먼저 입력된 것이 가장 나중에 출력된다.

 네번째, 인덱스가 중복되서 추가를 한다면, 기존의 데이터는 없어지고 새로운 데이터로 덮어씌여진다.

 다섯번째, Template를 사용하여, 인덱스나 데이터나 형식에 대하여 자유롭다.


3. 선언 방법

  map<인덱스형식,데이터형식> 사용할이름; 과 같이 선언하면 된다.
Example : map<int, string> iMapt;


4. 접근 방법

 접근 방법엔 두 가지가 있다.

 ㄱ. iterator를 사용한 접근 방법.
map<인덱스형식,데이터형식>::iterator iterator이름; 과 같이 iterator를 선언 한 후, 사용한다. 접근 방법은 iterator->first, iterator->second와 같은 형식으로 접근한다.

 ㄴ. 인덱스 요소를 이용하여 접근할 수 있다.


5. 요소 추가, 삭제 방법

 추가를 하고 싶다면 map[인덱스]=데이터; 식으로 추가를 해주자. 물론, 인덱스에는 문자열이 와도 된다.
 그리고 삭제를 하고 싶다면 map.erase(인덱스)와 같이 삭제은 방법으로 인덱스를 통하여 삭제를 할 수 있다.


6. Map사용 예제

#include <map>
#include <string>
#include <stdio.h>

using namespace std;

void main()
{
     map<int, string> iMap;

     iMap[5] = "5번요소의 데이터"; //요소에 대한 데이터를 임의 순서로 추가
     iMap[3] = "3번요소의 데이터";
     iMap[9] = "9번요소의 데이터";

     map<int, string>::iterator itMap;

     printf("iMap\n");
     for(itMap = iMap.begin(); itMap != iMap.end(); itMap++)
          printf("%d : %s\n",itMap->first, itMap->second.c_str()); //정렬된 상태
     printf("\n");

     iMap[9] = "안녕하세요!"; //덮어 씌우기

     printf("iMap\n");
     for(itMap = iMap.begin(); itMap != iMap.end(); itMap++)
          printf("%d : %s\n",itMap->first, itMap->second.c_str());
     printf("\n");

     printf("iMap[5] = %s\n\n",iMap[5].c_str()); //인덱스를 통한 접근

     map<char*, string> sMap; //char*과 string 둘다 문자열이지만
                                           //char*는 정렬되지 않는다.

     sMap["미국"] = "United State of America";
     sMap["중국"] = "China";
     sMap["일본"] = "Japan";
     sMap["한국"] = "Korea, Republic";

     map<char*, string>::iterator itStrMap;

     printf("sMap\n");
     for(itStrMap = sMap.begin(); itStrMap != sMap.end(); itStrMap++)
          printf("%s : %s\n",itStrMap->first, itStrMap->second.c_str());
     printf("\n"); //마지막으로 넣은 한국이 가장 먼저 출력됨

     sMap.erase("일본"); //일본을 삭제

     printf("sMap\n");
     for(itStrMap = sMap.begin(); itStrMap != sMap.end(); itStrMap++)
          printf("%s : %s\n",itStrMap->first, itStrMap->second.c_str());
     printf("\n");
}

[Result]
iMap
3 : 3번요소의 데이터
5 : 5번요소의 데이터
9 : 9번요소의 데이터

iMap
3 : 3번요소의 데이터
5 : 5번요소의 데이터
9 : 안녕하세요!

iMap[5] = 5번요소의 데이터

sMap
한국 : Korea, Republic
일본 : Japan
중국 : China
미국 : United State of America

sMap
한국 : Korea, Republic
중국 : China
미국 : United State of America

 

'COMPUTER TECH > C, C++ 참고자료' 카테고리의 다른 글

Pair, Map  (0) 2010.08.13
STL의 Set, Map 사용  (0) 2010.08.13
stl - map사용법  (1) 2010.08.13
AVL 트리  (0) 2010.08.13
단순 연결리스트  (0) 2010.08.13
이중 연결리스트  (0) 2010.08.13
Posted by ... XJAPAN

본격적으로 AVL 트리를 설명하겠다.

 

AVL 트리란 바로 균형이 갖춰진 이진트리를 의미한다. 균형이 갖춰져 있다는 말은 거의 완전 이진트리를 갖춘다는 뜻이다.

완전이진트리는 검색시 O(log2 n)에 해당하는 검색속도를 유지할 수 있게 된다.

 

이에 따라 AVL 트리는 최적의 검색 속도를 보장하기 때문에

삽입과 삭제가 적은 경우에 아주 효율적이라고 볼 수 있다.

 

AVL 트리에서 가장 중요한 개념은 높이 차이를 나타내는 균형인수(Balance factor)이다.

 

균형 변수란 무엇인가?

간단하게 말하면 특정 노드에서 자식 노드들의 높이 차이를 말한다.

즉, 왼쪽 서브트리의 높이와 오른쪽 서브트리의 높이의 차이를 현재 노드의 균형인수라고 한다.

 

균형인수 = |왼쪽자식높이 - 오른쪽자식높이|

 

 

 

 

위 트리를 보면 맨 밑단의 단말노드의 균형인수는 0인 것을 알 수 있다. 왜냐하면 자식들이 없으니까 높이 차이는 0 이다.

이로써 제일 왼쪽의 단말노드의 부모의 균형인수는 1이 되는 이유가 설명이 된다. 이렇게 전체적으로 ±1을 이하를 이루는

트리를 AVL 트리라고 한다.

 

만약 제일 왼쪽에 또 하나의 단말노드를 붙여보자.

 

 

 

그렇다면 이처럼 균형인수가 2인 트리가 나타나게 된다. 이는 AVL 트리 조건이 깨져버린 것이다.

이 때 AVL 트리 구성을 위해 균형을 맞추기 위해 재구축 해야한다.

 

일반적으로 AVL 트리에서는 4가지 형태의 삽입으로 AVL 트리가 조건이 깨져버린다.

LL 형식, LR 형식, RR 형식, RL 형식

 

 

LL 형식

 

 

A의 왼쪽 자식, 그 자식의 왼쪽으로 넣는 경우

 

 

LR 형식

 

 

 

A의 왼쪽 자식, 그 자식의 오른쪽으로 넣는 경우

 

 

RR 형식

 

 

 

 

 

A의 오른쪽 자식, 그 자식의 오른쪽으로 넣는 경우

 

RL 형식

 

 

 

A의 오른쪽 자식, 그 자식의 왼쪽으로 넣는 경우

 

 

여기까지 본 삽입시 AVL 트리의 조건이 깨지는 4가지 경우를 다시 한 번 정리해보겠다.

 

LL 형식 : A의 왼쪽(L)     자식의  왼쪽(L)에넣는 경우

LR 형식 : A의 왼쪽(L)     자식의  오른쪽(R)에 넣는 경우

RR 형식 : A의 오른쪽(R) 자식의  오른쪽(R)에 넣는 경우

RL 형식 : A의 오른쪽(R) 자식의  왼쪽(L)에 넣는 경우

 

여기서 보아야할 것은 LL의 대칭은 RR 이고 LR의 대칭은 RL이라는 점이다.

 

이제 이러한 4가지 경우에 따라 트리를 재구축하는 방법을 알아보자.

 

일단 AVL 트리는 균형인수가 ±1 이하인 트리라고 했다.

삽입시 균형인수가 틀어지기 시작한 노드를 중심으로 재구축을 진행한다.

 

 

우선 LL 형식을 먼저 보자.

 

 

일단 아래를 보며 신규노드를 삽입했을 경우 빨간색 자식노드에 삽입되어 불균형이 발생하게 된다.

 

           

 

                                 <LL 형식>                                                   <재구축 : 오른쪽 회전>

 

 

LL 형식은 오른쪽 회전(rotation)이라는 작업을 통해 재구축한다. 회전?

말이 회전이지 그냥 각각의 노드들에 대한 위치 변경이라고 보면 된다.

 

이에 대한 알고리즘은 다음과 같다.

 

roatateLL(A)

   B = A의 왼쪽 자식

   A 왼쪽 자식       = B의 오른쪽 자식

   B의 오른쪽 자식 = A

return B

 

 

이를 코드로 표현하면 다음과 같다.

 

 

065: Node* rotateLL(Node *node)
066: {
067:         Node *child=node->left;
068:         node->left=child->right;
069:         child->right=node;
070:         return child;
071: }

 

 

왜 B를 리턴하는가? 원래의 A 자리에 B가 결국에는 올라왔기 때문에

이에 포인터를 리턴하여 이 위치를 저장하기 위한 것이다.

 

신규 A' = 기존의 A를 대신하는 B 포인터

 

이처럼 포인터의 위치 변경만을 통해 LL 형식은 재구축 할 수 있다.

 

 

   

 

                      <AVL 트리 깨짐 : LL 형식>                                                  <재구축 : LL 오른쪽 회전>

 

여기서 신규노드를 삽입했을 경우 부모 쪽으로 타고 올라가다보면 A 노드에서 균형인수 2로 불균형이 발생했다.

재구축의 기준은 삽입한 노드로부터 조상 쪽으로 올라가며 만나는 위치다. A를 토대로 LL 회전을 발생하여 재구축한다.

 

그렇다면 RR의 형식에 대한 회전은 어떠할까?

 

RR형식은 LL의 대칭 개념이라고 했다. LL이 왼쪽의 왼쪽에 집어넣어진 것이라면 RR은 오른쪽의 오른쪽에 넣어진 것이다.

 

 

                     

                <AVL 트리 깨짐 : RR 형식>                                                  <재구축 : RR 왼쪽 회전>

 

RR회전 역시 포인터의 위치만 바꾸면 된다.

 

roatateRR(A)

   B = A의 오른쪽 자식

   A 오른쪽 자식   = B의 왼쪽 자식

   B의 왼쪽 자식   = A

return B

 

 

이를 코드로 표현하면 다음과 같다.

 

 

073: Node* rotateRR(Node *node)
074: {
075:         Node *child=node->right;
076:         node->right=child->left;
077:         child->left=node;
078:         return child;
079: }

 

 

RR은 LL의 대칭이라고 위에 적어놨다. 정말 순서만 바뀐 것으로 보일 것이다.

 

이제 LR 형식과 RL 형식에 대해 알아보자. 마찬가지로 LR과 RL은 대칭이다.

LR만 제대로 이해한다면 RL은 금방 이해 될 것이다.

 

 

우선 LR 형식에 대해 알아보자.

 

 

 

LR은 왼쪽 자식트리의 오른쪽 트리에 삽입되는 형식이라고 설명했다.

즉, A의 노드 왼쪽 자식 B의 오른쪽 자식 C에 삽입되는 순간 AVL 트리의 구조가 깨져버리는 것이다.

 

위의 트리를 보는 것과 같이 일단 B 에서 RR 회전을 해주면 조금 해결이 될 것 같다.

 

 

 

 

 

회전을 시켰는데 C와 A의 균형인수가 ±2가 되면 다시 A를 기준으로 LL 회전을 해주어야 한다.

 

 

 

 

그렇다면 이렇게 AVL 트리 구조가 갖춰지게 된다. 그림을 잘 생각해보길 바란다.

 

LR 회전은 다시 말해서 RR 회전과 LL회전으로 이루어진다.

 

좀더 다시 말하면 LR 회전의 기준이 되는 노드(A노드) 일 때

왼쪽 자식을 기준(B노드)으로 RR 회전,

본인 노드를 기준(A노드)으로 LL회전을 한다.

 

이것을 알고리즘으로 구현하면

 

roatateLR(A)

   B = A의 왼쪽 자식

   A 왼쪽 자식   = rotateRR(B)

return rotateLL(A)

 

 

이렇게 된다. 일단 B를 기준으로 RR 회전을 돌리면 원래 B의 자리로 오게 되는 노드를 A의 왼쪽 자식으로 놓는다.

그리고 A를 기준으로 LL 회전을 시키면 원래의 A 자리에도 다른 노드가 오게 될 수 있으니

rotateLR 함수를 호출하는 곳으로 return 시켜서 마찬가지로 엮어줘야 한다.

 

코드는 아래와 같다.

 

081: Node* rotateLR(Node *node)
082: {
083:         Node *child=node->left;
084:         node->left=rotateRR(child);
085:         return rotateLL(node);
086: }

 

 

RL 회전은 LR 회전의 대칭이라고 했다.

 

일단 RL 형식은 현재 노드(A)의 오른쪽 서브트리(B)의 왼쪽 서브트리(C)에 삽입되는 형태라고 했다.

아래처럼 A노드의 오른쪽(B)의 왼쪽(C)에 삽입되어 AVL트리가 깨지는 것을 의미한다.

 

 

LR 회전과 마찬가지로 B를 기준으로 LL회전(오른쪽)을 한다.

 

 

그러나 그래도 AVL 트리가 깨진 것을 확인 할 수 있을 것이다. 이제는 A를 기준으로 RR회전(왼쪽)을 한다.

 

 

 

이처럼 균형이 잡힌다. 이것을 알고리즘으로 표현하면 아래와 같다.

 

roatateLR(A)

   B = A의 오른쪽 자식

   A 오른쪽 자식   = rotateRR(B)

return rotateLL(A)

 

코드로 표현하면 다음과 같다.

 

 

088: Node* rotateRL(Node *node)
089: {
090:         Node *child=node->right;
091:         node->right=rotateLL(child);
092:         return rotateRR(node);
093: }

 

 

RL회전과 LR 회전이 어렵기는 하지만  이 과정을 머릿속으로 그려봐야 한다. 그래야 완벽한 이해가 된다.

일단 회전이라는 개념을 잘 잡아야 한다.  자식노드가 부모노드와의 위치 변환을 이루어 균형을 잡는 과정을 말이다.


일단 AVL 트리에서는 균형인수(Balance factor)가 중요하다고 했다.

균형인수를 구하려면 자식들의 높이를 구해서 그 차이를 알아야 한다.

 

018: int GetHeight(Node *node)
019: {
020:         int height=0;
021:         if(node!=NULL)
022:                 height=1+max(GetHeight(node->left),GetHeight(node->right));
023:        
024:         return height;
025: }


 

높이를 구하는 방법은 바로 이전에 이야기를 했기 때문에 별 설명 안 하겠다.

 

095: int GetHeight_Diff(Node *node)
096: {
097:         int leftHeight;
098:         int rightHeight;
099:
100:         if(node==NULL)  return 0;
101:         else
102:         {
103:                 leftHeight=GetHeight(node->left);
104:                 rightHeight=GetHeight(node->right);
105:
106:                 return leftHeight-rightHeight;
107:         }
108: }


 

이제 균형인수는 자식들의 높이를 구해서 빼주기만 하면 되니 함수는 위와 같은 것이다.

이제 본격적으로 AVL 트리에서 가장 중요한 문제를 논의해볼까?

 

많은 사람들이 이 부분에 대해서 헷깔려 한다. 사실 위에서부터 꼼꼼히 봤다면 이해가 되었을라나 모르겠지만

역시 가장 중요한 문제는 과연 언제 AVL 트리를 RR, LL, LR, RL 등으로 재구성해야할까? 이다.

 

정답은 삽입할 때이다. 삽입하는 다음에 재구축에 관련된 함수를 호출하면 된다.

 

027: Node* InsertNode(Node *node, int data)
028: {
029:         if(!node)
030:         {
031:                 node=(Node*)malloc(sizeof(Node));
032:                 node->data=data;
033:                 node->left=node->right=NULL;
034:         }
035:         else if(data < node->data)
036:         {
037:                 node->left=InsertNode(node->left,data);
038:                 node=ReBalance(node);
039:
040:         }
041:         else if(data > node->data)
042:         {
043:                 node->right=InsertNode(node->right, data);
044:                 node=ReBalance(node);
045:         }
046:         else
047:         {
048:                 printf("중복");
049:                 exit(1);
050:         }
051:
052:         return node;
053: }

 

 

뭐, 간단하지 않은가? 그러나 이제 과연 재구축을 하는 함수는 어떻게 구현하는가이다.

이것 역시 간단한 문제이다. 일단 현재 노드의 균형인수(Balance factor)를 구한다.

 

만약  2보다 크다면 왼쪽서브트리 쪽으로 삽입이 되어 깨진 것이고

만약 -2보다 작다면 오른쪽서브트리 쪽으로 삽입 되어 깨진 것이다.

 

그 이유는 균형인수 = 왼쪽자식높이 - 오른쪽자식높이 라고 처음에 이야기 했다.

 

111: Node* ReBalance(Node *node)
112: {
113:         int heightDiff=GetHeight_Diff(node);
114:         if(heightDiff >=2)
115:         {
116:                 if(GetHeight_Diff(node->left) >=1)
117:                 {
118:                         printf("[LL회전]\n");
119:                         node=rotateLL(node);
120:                 }
121:                 else
122:                 {
123:                         printf("[LR회전]\n");
124:                         node=rotateLR(node);
125:                 }
126:         }
127:


 

여기까지가 바로 왼쪽서브트리에 삽입되어 깨지는 조건이다. LL형식이 되는 순간도 머릿속으로 그려보자.

현재의 노드(A)에서 왼쪽자식(B)의 왼쪽자식(C)에 삽입이 되는 것이니 결국 왼쪽자식(B)의 균형인자는 1 이상으로 된다.

 

그게 아니라면 LR 회전인 셈이다.

 

이제 오른쪽 서브트리 쪽으로 삽입이 되었을 경우는 다음과 같다.

 

128:         else if(heightDiff <= -2)
129:         {
130:                 if(GetHeight_Diff(node->right) <= -1)
131:                 {
132:                         printf("[RR회전]\n");
133:                         node=rotateRR(node);
134:                 }
135:                 else
136:                 {
137:                         printf("[RL회전]\n");
138:                         node=rotateRL(node);
139:                 }
140:         }
141:
142:         return node;
143: }

 

단순히 왼쪽, 오른쪽은 서로 대칭이기 때문에 사실상 왼쪽만 제대로 이해하고 있어도 이해가 될 것이다.

이제 AVL트리를 사용하는 메인함수를 볼까?


016: Node *root=NULL;

147: int main()
148: {
149:         root=InsertNode(root,7);
150:         root=InsertNode(root,8);
151:         root=InsertNode(root,9);
152:         root=InsertNode(root,2);
153:         root=InsertNode(root,1);
154:         root=InsertNode(root,5);
155:         root=InsertNode(root,3);
156:         root=InsertNode(root,6);
157:         root=InsertNode(root,4);
158:
159:         printf("\n# Prefix 순회 #\n");
160:         PreOrder(root);
161:
162:
163:         return 0;
164: }

 

일단 삽입을 할 때 재구축이 진행되므로 최상단의 root 의 위치까지 회전의 대상이 될 수 있다. 

변화가 이루어져 새롭게 위치한 노드를 가리키기 위해 root 포인터에 대입을 해야한다.

 

만약 이것이 보기 싫다면 이중포인터를 이용해서 구현도 가능하다.

여기까지 AVL 트리였다. 사실상 AVL 트리부터는 고급 자료구조에 해당되는 부분이고

제대로 이해하고 코드로 구현할 수 있는 정도의 사람이라면 학부수준에서는 중급이상이다.

(그러니 이것을 이해하고 구현하는 사람은 조금은 우쭐해도 된다. 잘난 척은 금물)

 

AVL 트리는 균형 트리라는 점에서 B-트리로 넘어가는 중요한 단계이므로 소스를 참조하여 잘 이해하도록 하자.

 

'COMPUTER TECH > C, C++ 참고자료' 카테고리의 다른 글

STL의 Set, Map 사용  (0) 2010.08.13
stl - map사용법  (1) 2010.08.13
AVL 트리  (0) 2010.08.13
단순 연결리스트  (0) 2010.08.13
이중 연결리스트  (0) 2010.08.13
스택과 큐  (0) 2010.08.13
Posted by ... XJAPAN

일반적으로 자료구조에서 가장 초보수준 여겨지는 것이 연결리스트이며 가장 활용도가 많은 것도 연결리스트이다.

운영체제를 공부하다보면 운영체제의 내부에 연결리스트가 상당히 많이 사용되는 것을 알 수 있다.

 

그만큼 중요도가 있다. (자료구조에서 중요하지 않은 것이 어디있겠느냐만)

 

연결리스트란 무엇인가, 데이터를 묶어서 선형적으로 연결시킨 것을 말한다. 그 이상도 그 이하도 아니다.

배열도 선형적으로 연결된 하나의 연결리스트라고 봐도 무방하다. 인덱스를 증가시켜 접근할 수 있는 선형 연결리스트이다.

 

여기서 다룰 주제는 동적 연결리스트이다.

배열과 동적연결리스트의 차이는 배열은 정적으로 사용하기 앞서 메모리에 할당하는 것이고

동적 연결리스트는 필요한 순간에만 임의로 메모리를 생성하여 할당하여 사용한다.

서로 장단점이 있지만 여기서는 논외 대상으로 삼겠다.

 

 

아래는 연결리스트를 구성하는 구성요소(Element)인 노드(Node)의 구조체이다.

 

004: typedef struct Node
005: {
006:         int     data;
007:         struct Node *next;
008: }Node;

처음 자료구조를 접하거나 포인터에 익숙하지 않은 사람들에게는 낯선 표현이다.

밑줄 친것처럼 대부분의 자료구조는 구조체 내에 같은 이름의 구조체 포인터가 존재한다.

이것이 바로 링크(Link)의 개념이다.

 

연결리스트의 최대의 장점은 동적메모리 생성이다. 필요한 순간에만 메모리에 할당하여 사용한다.

일반적으로 메모리를 할당할 때 다시 그 주소를 정확히 짚어내기 위해서는

주소를 가리키는 지시자가 필요하다. 

 

메모리를 할당하는 순간, 그 주소를 잡고 있기 위해서 자신의 타입과 같은 포인터를 가지고 있어야 한다.

물론 void 형태의 포인터로 여러 타입의 데이터를 갖는 방법도 있는데

여기서는 초보를 위한 것이니까 설명하지 않겠다. :)

 

010: Node *headNode, *tailNode;
011:

012: void InitnextedList()
013: {
014:         headNode=(Node*)malloc(sizeof(Node));
015:         tailNode=(Node*)malloc(sizeof(Node));
016:         headNode->next=tailNode;
017:         tailNode->next=tailNode;
018: }

연결리스트의 일반적인 구성은 머리와 꼬리라는 존재가 있다.

어디가 시작이고 어디가 끝인지를 알 수 있도록 더미(Dummy) 구조체를 생성하여 표시한다.

 

초기화로는 머리의 포인터는 꼬리를 가리키고, 꼬리의 포인터는 자기 자신을 가리킨다.

다음은 리스트의 전체 요소들을 출력하는 리스트이다.

 

020: void printList()
021: {
022:         Node    *findNode;
023:         findNode=headNode;
024:
025:         while(findNode->next!=tailNode)
026:         {
027:                 findNode=findNode->next;
028:                 printf("%d ",findNode->data);
029:         }
030:         printf("\n");
031: }

보는 것과 같이 findNode 라는 임시 노드 포인터를 만들었다.

findNode는 일단 머리의 주소에서부터 하나씩 앞으로 나아가며 출력을 한다.

 

만약 머리와 꼬리 사이의 노드가 3개라면 25번-29번줄을 대략적으로 다음과 같이 표현할 수 있다.

 

[  머리  ]-[  노드 1  ]-[  노드 2  ]-[  노드 3  ]-[  꼬리  ]

    ↑

findNode=headNode

 

[  머리  ]-[  노드 1  ]-[  노드 2  ]-[  노드 3  ]-[  꼬리  ]

                     ↑

        findNode=findNode->next

 

[  머리  ]-[  노드 1  ]-[  노드 2  ]-[  노드 3  ]-[  꼬리  ]

                                       ↑

                           findNode=findNode->next

 

[  머리  ]-[  노드 1  ]-[  노드 2  ]-[  노드 3  ]-[  꼬리  ]

                                                      ↑

                                           findNode=findNode->next

 

[  머리  ]-[  노드 1  ]-[  노드 2  ]-[  노드 3  ]-[  꼬리  ]

                                                       ↑

                                         findNode->next == tailNode (끝)

 

 

참 쉽죠~ 잉? 이것이 연결리스트의 요소들을 탐색하는 과정이다. 

포인터를 이용하면 포인터가 가리키는 방향으로 나아갈 수 있다.

 

이제 이것을 이용하여 맨 마지막 요소 뒤에다 새로운 데이터를 삽입하는 함수를 알아보자.

 

033: int InsertData(int data)
034: {
035:         Node *tempNode;
036:         Node *findNode;
037:
038:         if( (tempNode=(Node*)malloc(sizeof(Node)))
039:                 ==NULL )
040:         {
041:                 printf("Can't allocate memory \n");
042:                 return -1;
043:         }
044:         else tempNode->data=data;
045:
046:         findNode=headNode;
047:         while(findNode->next!=tailNode)
048:                 findNode=findNode->next;
049:        
050:         tempNode->next=tailNode;
051:         findNode->next=tempNode;
052:
053: }

이제 findNode는 무슨 역할을 하는지 알 것이고, tempNode 는 무엇일까?

 

위에서도 주욱 이야기 했듯이 일반적으로 동적 연결리스트에서는

 

1. 노드에 메모리를 할당한다.

2. 포인터로 주소를 가리켜서 연결리스트로 묶는다.

 

이 때 사용할 노드가 바로 tempNode이다. 임시적으로 사용되는 노드라는 것이다.

 

038:         if( (tempNode=(Node*)malloc(sizeof(Node)))
039:                 ==NULL )
040:         {
041:                 printf("Can't allocate memory \n");
042:                 return -1;
043:         }

044:         else tempNode->data=data;

 

38번 줄은 tempNode=(Node*)malloc(sizeof(Node)) 로 임시 노드에게 메모리를 할당 한다.

39번 줄은 NULL이라면 메모리 할당이 안 된 것이니 에러를 표시하고 함수를 끝내도록 한다.

 

에러 없이 메모리 할당이 성공했다면 tempNode 구조체의 data 변수에 data 값을 넣어준다.

 

여기까지 1. 노드에 메모리를 할당한다. 가 끝난 것이다.

 

이제는 이 노드를 연결리스트로 묶어야 한다.

그렇다면 일단 맨 끝단의 요소를 찾아서 그 뒤에 넣어주면 된다.

 

046:         findNode=headNode;
047:         while(findNode->next!=tailNode)
048:                 findNode=findNode->next;
049:        
050:         tempNode->next=tailNode;
051:         findNode->next=tempNode;

 

여기서 46번-48번까지가 바로 맨 끝의 요소를 찾는 것이다.

while 문이 끝나면 일단 findNode는 맨 끝의 노드의 주소를 가지고 있게 된다.

 

그리고 tempNode를 findNode의 다음으로, tempNode의 다음은 꼬리 노드로 오도록 하면 된다.

다음은 데이터 값을 찾아서 지우도록 하는 함수를 만들어보자. 위의 출력과 삽입을 이해했다면 아래도 쉽다.

 

 

055: int DeleteData(int data)
056: {
057:         Node *findNode;
058:         Node *prevNode;
059:
060:         if(headNode->next==tailNode) return -1;
061:
062:         findNode=headNode;
063:
064:         while(findNode->next!=tailNode)
065:         {
066:                 prevNode=findNode;
067:                 findNode=findNode->next;
068:
069:                 if(findNode->data==data)
070:                 {
071:                         prevNode->next=findNode->next;
072:                         free(findNode);
073:                         return 1;
074:                 }
075:         }
076:
077:         printf("Not exists the data. \n");
078:         return -1;
079: }

 

단일 연결리스트의 최대의 단점은 나아가는 방향이 하나라는 것이다. 앞으로~ 앞으로~ ♪

덕분에 삭제하고자 하는 노드를 찾았다고 해도 막상 그것을 대뜸 지워버리면 이전의 노드가 가리키는 노드가 휙 사라진다.

 

아래에서 대뜸 노드 2를 삭제해보자.

 

[  머리  ]-[  노드 1  ]-[  노드 2  ]-[  노드 3  ]-[  꼬리  ]

     ↑  

 findNode

 

[  머리  ]-[  노드 1  ]-[  노드 2  ]-[  노드 3  ]-[  꼬리  ]

                     ↑  

               findNode

 

[  머리  ]-[  노드 1  ]-[  노드 2  ]-[  노드 3  ]-[  꼬리  ]

                                      ↑  

                                findNode (찾았다! 삭제!)

 

[  머리  ]-[  노드 1  ]-                 [  노드 3  ]-[  꼬리  ]

 

 

오잉? 노드 1이 가리키는 존재가 우주 저멀리로 날아갔다. 이 말은 선형적인 연결리스트가 두 동강 나버렸다는 것이다.

단일 연결리스트의 단점(?)인 앞으로 나아감에 있어서 [노드 3]으로의 접근은 사실상 불가능하게 되었다.

 

그렇기에 findNode 바로 전의 노드에 대한 정보를 가지는 변수가 필요하다.

 

058:         Node *prevNode;

바로 이것의 정체이다.

 

064:         while(findNode->next!=tailNode)
065:         {
066:                 prevNode=findNode;
067:                 findNode=findNode->next;
068:
069:                 if(findNode->data==data)
070:                 {
071:                         prevNode->next=findNode->next;
072:                         free(findNode);
073:                         return 1;
074:                 }
075:         }

66, 67번은 findNode 가 앞으로 나아가면 prevNode 는 바로 전의 findNode의 주소를 가지고 있는다.

 

그러다 삭제할 데이터를 찾으면 (69번줄) prevNode의 포인터는 findNode의 다음 노드를 가리킨다. (71번줄)

그리고 free(findNode)로 영원한 안식과 삭제했다는 의미로 return 1 로 함수를 빠져나간다.

 

이제 끝이다. 메인함수를 보도록 하자.

 

082: int main()
083: {
084:         InitnextedList();
085:
086:         InsertData(1);
087:         InsertData(2);
088:         InsertData(3);
089:         InsertData(4);
090:         InsertData(5);
091:
092:         printList();
093:
094:         DeleteData(1);
095:         DeleteData(3);
096:
097:         printList();
098:
099:         return 0;
100: }

 

초기화 해주고, 삽입하고, 출력하고, 삭제하고, 출력한다.

 

'COMPUTER TECH > C, C++ 참고자료' 카테고리의 다른 글

stl - map사용법  (1) 2010.08.13
AVL 트리  (0) 2010.08.13
단순 연결리스트  (0) 2010.08.13
이중 연결리스트  (0) 2010.08.13
스택과 큐  (0) 2010.08.13
이진탐색트리(Binary Search Tree)  (0) 2010.08.13
Posted by ... XJAPAN

단일 연결리스트의 단점은 바로 앞으로 나아가는 단일 방향성이다. 앞, 뒤로 양방향으로 나아가는 방법은 없을까?

없긴 왜 없어. 컴퓨터로 안 되는건 없다.

 

우리에게는 포인터라는 막강한 존재가 있기 때문에 이중 연결리스트를 구현하는 것은 식은 죽 먹기다.

 

004: typedef struct Node
005: {
006:         int              data;
007:         struct Node *prev;
008:         struct Node *next;
009: }Node;

 

우선 단일 연결리스트와의 차이는 바로 prev 가 추가된 것이다. 왜 구조체 내에 구조체 포인터가 있냐고?

'단일 연결리스트'를 다시 읽고 오길 바란다.

 

011: Node *headNode, *tailNode;
012:
013: void InitnextedList()
014: {
015:         headNode=(Node*)malloc(sizeof(Node));
016:         tailNode=(Node*)malloc(sizeof(Node));
017:
018:         headNode->next=tailNode;
019:         headNode->prev=headNode;
020:         tailNode->next=tailNode;
021:         tailNode->prev=headNode;
022: }

뒤의 노드로도 갈 수 있다보니 이에 대한 설정을 해줘야 한다. 단일 연결리스트에서 꼬리의 다음은 꼬리를 가리킨다고 했다.

이중 연결리스트에서의 머리의 이전 노드는 머리를 가리킨다. 밑줄을 보면 쉽게 이해가 될 것이다.

 

다음은 출력하는 머리부터 출력하는 함수(전진)와 꼬리부터 출력하는 함수(후진)를 기록하겠다.

 

024: void printList_PreOrder()
025: {
026:         Node    *findNode;
027:         findNode=headNode;
028:
029:         while(findNode->next!=tailNode)
030:         {
031:                 findNode=findNode->next;
032:                 printf("%d ",findNode->data);
033:         }
034:         printf("\n");
035: }

이건 무슨 이야기인지 이미 언급했다.

 

037: void printList_PostOrder()
038: {
039:         Node    *findNode;
040:         findNode=tailNode;
041:        
042:         while(findNode->prev!=headNode)
043:         {
044:                 findNode=findNode->prev;
045:                 printf("%d ",findNode->data);
046:         }
047:         printf("\n");
048: }

이제는 뒤로 가는 것이다!  친히 초록색으로 밑줄까지 그어줬다.  무슨 의미인지 쉽게 알 수 있을 것이다.

이제 데이터를 삽입하는 함수를 보도록 하자. 이번에도 맨 끝에다 넣도록 했다.

 

051: int InsertData(int data)
052: {
053:         Node *tempNode;
054:         Node *findNode;
055:
056:         if( (tempNode=(Node*)malloc(sizeof(Node)))
057:                 ==NULL )
058:         {
059:                 printf("Can't allocate memory \n");
060:                 return -1;
061:         }
062:         else tempNode->data=data;
063:
064:         findNode=headNode;
065:         while(findNode->next!=tailNode)
066:                 findNode=findNode->next;
067:
068:         tempNode->next=tailNode;
069:         tempNode->prev=findNode;
070:
071:         findNode->next=tempNode;
072:         tailNode->prev=tempNode;
073:
074:         return 1;
075: }

여기서 68번부터 72번까지가 단일 연결리스트와 다르다. 뒤로 가는 개념이 존재하기 때문에

 

임의로 메모리 할당한 연결리스트를 맨끝으로 넣어준다.(68번줄)

하지만 기존의 리스트의 맨 끝 요소였던 findNode를 가리키던 tailNode->prev 에는 tempNode를 가리키도록 한다.

 

[  머리  ]-[  노드1  ]-[  노드2  ]-[  노드3  ]-[  꼬리  ]

 

지금까지는 아래와 같았다.

 

노드3->next = 꼬리

꼬리->prev = 노드3

 

 

[  노드4  ] 삽입하면,

 

[  머리  ]-[  노드1  ]-[  노드2  ]-[  노드3  ]-   -[  노드4  ]-    -[  꼬리  ]

 

노드3->next = 꼬리 노드4

꼬리->prev = 노드3 노드4

 

가 되어야 하고 새롭게 추가된 노드4는 자신의 next와 prev에 대한 주소를 지정함으로써 연결리스트를 완성해야한다.

 

노드4->next = 꼬리

노드4->prev = 노드3

 

합체가 완료되면 아래와 같이 된다.

 

[  머리  ]-[  노드1  ]-[  노드2  ]-[  노드3  ]-[  노드4  ]-[  꼬리  ]

 

그것의 관한 코드가 바로 68번부터 72번까지이다.

 

068:         tempNode->next=tailNode;
069:         tempNode->prev=findNode;
070:
071:         findNode->next=tempNode;
072:         tailNode->prev=tempNode;

 

 

이중 연결리스트를 이해하면 포인터에 대해서는 하수를 벗어나는 수준이 된다.

(초급은 트리와 그래프를 이해하면 벗어나고, 중급은 AVL, 고급은 B-트리)

 

이제 삭제 함수에 대해 알아보자.

 

077: int DeleteData(int data)
078: {
079:         Node *findNode;
080:         Node *prevNode;
081:
082:         if(headNode->next==tailNode) return -1;
083:
084:         findNode=headNode;
085:
086:         while(findNode->next!=tailNode)
087:         {
088:                 prevNode=findNode;
089:                 findNode=findNode->next;
090:
091:                 if(findNode->data==data)
092:                 {
093:                         prevNode->next=findNode->next;
094:                         findNode->next->prev=prevNode;
095:
096:                         free(findNode);
097:                         return 1;
098:                 }
099:         }
100:
101:         printf("Not exists the data. \n");
102:         return -1;
103: }

여기서 중요한 것은 93, 94번줄이겠다. 삭제하려는 노드(findNode) 이전의 노드가 다음(next)로 가리키는 노드는

삭제하려는 노드의 다음노드(findNode->next)가 되어야 한다.

 

[  머리  ]-[  노드1  ]-[  노드2  ]-[  노드3  ]-[  노드4  ]-[  꼬리  ]

                                                ↑(삭제대상)   

                                ↑          findNode        ↑

                       findNode->prev             findNode->next

 

 

일단 앞, 뒤로 줄이 달린 상자들을 머릿속으로 한 번 그려보길 바란다.

중간에 하나를 잘라내고 다시 한 줄로 연결하려면 어떻게 되는지를.

 

그렇기에 아래와 같은 코드로 표현이 가능하다.

 

093:                         prevNode->next=findNode->next;
094:                         findNode->next->prev=prevNode;

 

여기까지가 바로 삭제 함수에 관한 것이다. 여기서 질문,

prevNode의 존재는 무엇 때문에 있는 것인가에 대해 '단일 연결리스트'에서 거론했을까?

 

바로 단일 연결리스트는 앞으로 나아갈 수 밖에 없는 구조이기 때문에 대상을 찾아서 삭제시 붕 떠버릴 수 있다고 했다.

그러나 이중 연결리스트에서는 앞, 뒤로 나아가는 구조이기 때문에 사실상 prevNode는 필요없기도 하다.

 

prevNode는 findNode->prev 와 같은 역할이다. 쉽게 인식을 하기 위해 그냥 납두는 것도 괜찮지만

아래와 같이 표현이 가능하다는 것도 알아두면 포인터를 이해하는데 조금 더 도움이 될 것이다.

 

077: int DeleteData(int data)
078: {
079:         Node *findNode;
080:         /*Node *prevNode;*/
081:
082:         if(headNode->next==tailNode) return -1;
083:
084:         findNode=headNode;
085:
086:         while(findNode->next!=tailNode)
087:         {
088:                 findNode=findNode->next;
089:
090:                 if(findNode->data==data)
091:                 {
092:                         findNode->prev->next=findNode->next;
093:                         findNode->next->prev=findNode->prev;
094:
095:                         free(findNode);
096:                         return 1;
097:                 }
098:         }
099:
100:         printf("Not exists the data. \n");
101:         return -1;
102: }

 

참 쉽죠잉? 마지막으로 이를 사용하는 메인함수를 표현하자.

 

105: int main()
106: {
107:         InitnextedList();
108:
109:         InsertData(1);
110:         InsertData(2);
111:         InsertData(3);
112:         InsertData(4);
113:         InsertData(5);
114:
115:         printList_PreOrder();
116:         printList_PostOrder();
117:
118:         printf("\n");
119:
120:         DeleteData(1);
121:         DeleteData(3);
122:
123:         printList_PreOrder();          //머리부터 발끝까지 다~ 사랑스러워
124:         printList_PostOrder();        //발끝부터 머리까지 다........
125:
126:         return 0;
127: }

 

'COMPUTER TECH > C, C++ 참고자료' 카테고리의 다른 글

AVL 트리  (0) 2010.08.13
단순 연결리스트  (0) 2010.08.13
이중 연결리스트  (0) 2010.08.13
스택과 큐  (0) 2010.08.13
이진탐색트리(Binary Search Tree)  (0) 2010.08.13
힙(Heap) 트리와 정렬 (우선순위 큐)  (0) 2010.08.13
Posted by ... XJAPAN
이전버튼 1 2 이전버튼