예상문제라고 해서 한번 풀어봤다.

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

이진탐색트리 (삽입, 삭제) 구현.  (0) 2010.08.12
map, vector, list 연습  (0) 2010.08.12
선문비트 단기반 최종시험 C++ 실기  (0) 2010.08.12
피보나치 수열 작성  (0) 2010.08.12
동적 알고리즘 코딩자료  (0) 2010.08.12
직렬화  (0) 2010.08.12
Posted by ... XJAPAN

댓글을 달아 주세요


#include <stdio.h>
int f[30];

void fibonacci(int i)
{
   if(i == 1 || i ==2)
   {
    f[i] = 1;
    printf("%d\n", f[i]);
   }
   else
   {
    f[i] = f[i-1] + f[i-2];
    printf("%d\n", f[i]);
   }
}

void main()
{
 for(int i=1;i<=30;i++)
 {
  fibonacci(i);
 }
}

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

map, vector, list 연습  (0) 2010.08.12
선문비트 단기반 최종시험 C++ 실기  (0) 2010.08.12
피보나치 수열 작성  (0) 2010.08.12
동적 알고리즘 코딩자료  (0) 2010.08.12
직렬화  (0) 2010.08.12
배열  (0) 2010.08.12
Posted by ... XJAPAN

댓글을 달아 주세요


// Dynamic.h: interface for the Dynamic class.
//
//////////////////////////////////////////////////////////////////////

#pragma warning(disable:4786)
#if !defined(AFX_DYNAMIC_H__A4ADC6F8_316B_46FE_8C8E_DA43F48439D1__INCLUDED_)
#define AFX_DYNAMIC_H__A4ADC6F8_316B_46FE_8C8E_DA43F48439D1__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000
#include "Eistream.h"
#include "Eostream.h"
#include <stack>
#include <time.h>
#include <conio.h>
using namespace Ehlib;
typedef stack<char> stack_int;

class Dynamic 
{
 char *A;
 char *B;
 stack_int s; // 스택
 int tonum; // 랜덤해서 만들어진 숫자
 char result[255+1];
 int pushcount;
 int popcount;
 int p; // testing 에서 쓰는 카운트 변수
 int q; // testing 에서 쓰는 카운트 변수
 BOOL check;
public:
 Dynamic();
 virtual ~Dynamic();
 void Input();
 void MakeB();
 void InputB();
 void Calculation(int pushcount, int popcount, char * result);
 void testing(char * stemp);
};

#endif // !defined(AFX_DYNAMIC_H__A4ADC6F8_316B_46FE_8C8E_DA43F48439D1__INCLUDED_)



// Dynamic.cpp: implementation of the Dynamic class.
//
//////////////////////////////////////////////////////////////////////

#include "Dynamic.h"

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
int temp[255] = {0, };
void main()

 Dynamic *app = new Dynamic();
 delete app;
}

Dynamic::Dynamic()
{
 srand( (unsigned)time( NULL ) ); // srand 쓰기
 memset(result, 0, 255);
 pushcount=0;
 popcount=0;
 p=0;
 q=0;
 check = TRUE;
 Input();
 Calculation(pushcount, popcount, result);
 if(check)
  cout << "답이 없는 문자열입니다.";
}

Dynamic::~Dynamic()
{
 delete[] A;
 delete[] B;
}

//사용자에게 문자열 A 를 입력받음.
void Dynamic::Input()
{
 char tempA[255+1]="";
 eout << "**************************************" << endl;
 eout << "문자열을 입력하세요 = ";
 ein.GetStr(tempA, 255);
 eout << "**************************************" << endl;
 eout << endl;

 //일단 넣은거
 A = new CHAR[strlen(tempA)+1];
 strcpy(A, tempA); // 받은거 문자열로

 MakeB();
}

//B 문자열 만들기
void Dynamic::MakeB()
{
 tonum = strlen(A);

 for (int i=0;i<tonum;i++)
 {
  while(1)
  {
   BOOL test = TRUE;
   int ran = rand()%strlen(A);
   temp[i] = ran;
   for(int j=0;j<i;j++)
   {
    if(temp[j] == ran)
     test = FALSE; 
   }
   if(test)
    break;
  }
 }
 InputB();
}

//B 문자열 집어넣기
void Dynamic::InputB()
{
 char tempB[255+1]="";
 for (int i=0;i<tonum;i++)
  tempB[i] = A[temp[i]];
 //일단 넣은거

 B = new CHAR[strlen(tempB)+1];
 strcpy(B, tempB);
 
 cout<< "랜덤으로 생성된 문자열 =  ";
 for(i=0;i<strlen(B);i++)
  cout << B[i];
 cout << endl;
 cout << "탐색을 시작합니다.." << endl;

 pushcount = strlen(A);
 popcount = pushcount;
 getch();
 cout << endl;
 eout << "**************************************" << endl;
}

//시작
void Dynamic::Calculation(int pushcount, int popcount, char * result)
{
 char * stemp = new CHAR[strlen(A)*2+1];
 strcpy(stemp, result);

 if(pushcount > 0)
 {
  result[(strlen(A) *2) - (pushcount + popcount)] = '1';
  Calculation(pushcount-1, popcount, result);
 }

 if(popcount > 0)
 {
  if(popcount > pushcount)
  {
   result[(strlen(A) *2) - (pushcount + popcount)] = '0';
   Calculation(pushcount, popcount-1, result);
  }
 }

 if(pushcount ==  0 && popcount == 0)
 {
  testing(stemp);
 }
 delete[] stemp;
}

void Dynamic::testing(char * stemp)
{
 char K[255] = "";
 for(int i=0;i<strlen(stemp)+1;i++)
 {
  if(stemp[i]=='1')
  {
   s.push(A[p++]);
  }
  else if (stemp[i]=='0')
  {
   K[q++] = s.top();
   s.pop();
  }
 }
 p=0;q=0;
 if(strcmp(B, K)==0)
 {
  cout << "문자열 = " << A << " 랜덤 = " << B << " 동작 = " << stemp << endl;
  check = FALSE;
 }
}



****************** 설명 **********************

동적 알고리즘 문제

- 문자열 A를 입력받는다.
- 문자열 A의 내부 문자의 순서가 랜덤한 순서로 변형된 문자열 B를 생성한다.(모든 문자가 들어 있을 필요는 없다.)

다음의 1과 2의 작업은 랜덤한 순으로 진행된다.
1. 문자열 A의 문자들을 stack에 push한다.
2. stack의 문자를 pop해 온다. (pop해온 문자를 문자열 K(i)에 보관한다.


위의 작업을 하다가 문자열 K(i)와 B가 동일한 것들을 출력한다.

 

예)
입력 문자열 A: hello
생성한 문자열 B: loleh


출력결과:
push push push pop push push pop pop pop pop
push push push push pop push pop pop pop pop

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

선문비트 단기반 최종시험 C++ 실기  (0) 2010.08.12
피보나치 수열 작성  (0) 2010.08.12
동적 알고리즘 코딩자료  (0) 2010.08.12
직렬화  (0) 2010.08.12
배열  (0) 2010.08.12
자료구조 프로그래밍  (0) 2010.08.12
Posted by ... XJAPAN

댓글을 달아 주세요

2010. 8. 12. 23:48

< 직 렬 화 >


프로세스의 정보들을 물리장치에 보관하는 등의 작업을 직렬화라고 함.

파일 , 소켓으로도 사용.


개체정보 -> 물리장치로 (직렬화)

물리적인 장치 -> 프로세스로 (역 직렬화)


ex)

*************************************************************************************

class stu

{

 const int num;

 char * name;

public :

 void Serialize(ofstream &of); // ofstream 출력 스트림. // 직렬화

 stu(ifstream &ifs)// 역직렬화를 제공 해야함(메소드가 존재하지 않음.)

 // 생성자의 시그니쳐가 stream 내부에 제공되어 있음.

private :

 int Read(ifstream &ifs);

}

//(ofstream,= ifstream).< (iofstream) < (fstream)

*************************************************************************************

ofstream of("data.txt"); // data.txt를 write 모드로 open 까지 해줌.

of.write(프로세서의 주소, 저장할 byte 수) //(저장할 variable, byte 수)

ex) a를 write 하면 a라는 객체와 동일한 객체를 복사할수있음.

of.close();

*************************************************************************************

직렬화를 하는 이유 - 역직렬화를 위해서.(개체정보를 저장했다가 다시 불러오기 위함.)

*************************************************************************************

stu::Serialize(ostream &of) // 이 코드가 있다는건 ofstream이 이미 열려있다는 전제.

{

 of.write(&num, sizeof(num));

 of.write(&name, sizeof(name)); // 이름 같은 경우 이름의 내용이 중요함.

 위의 내용을 of.write(name, strlen(name)+1);로 써야함.

 //이름은 용량이 얼마나 될지 모르는 가변적인 요소이기 때문에

 int len = strlen(name)+1;

 of.write(&len, sizeof(len));

 of.write(name, len);

 // 이렇게 써줄 경우의 예제는

 (27 , 6 , Hello) // 숫자 27을 받고 6칸의 배열공간을 만들고 Hello를 대입

 // 가변적인 요소는 저장해놓아야 함.

}

*************************************************************************************

// ex)생성자의 시그니쳐

stu::stu(ifstream &ifs) : num(Read(ifs)) // 리턴 결과가 num 과 같은 것이매개변수로..

{

 int len;

 ifs.read(&len, sizeof(len));

 name = new char[len]; // 포인터 자체는 storage 가 아님.

 ifs.read(name, len);

}

*************************************************************************************

ex) private 에 있는 Read 함수사용 예

int stu::Read(ifstream &ifs)

{

 int temp;

 ifs.read(&temp.sizeof(temp)); // num이 const 이기 때문에 이와같이 사용.

 return temp;

}

*************************************************************************************

ofstream, ifstream 을 사용하려면

#include <fstream>

using namespace std;

using std::ifstream;

using std::ofstream;

라고 명시를 해야 함. 하지 않을시엔 컴파일 오류가 발생함.

*************************************************************************************


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

피보나치 수열 작성  (0) 2010.08.12
동적 알고리즘 코딩자료  (0) 2010.08.12
직렬화  (0) 2010.08.12
배열  (0) 2010.08.12
자료구조 프로그래밍  (0) 2010.08.12
배열을 순차적으로 사용할 경우  (0) 2010.08.12
Posted by ... XJAPAN

댓글을 달아 주세요

2010. 8. 12. 23:48

< 배열 >

*************************************************************************************

언어 : 동일한 형식의 여러개의 원소를 하나의 관리명으로 관리하는 변수형식.

stu * arr[10][5]; // stu * [5] 의 형식의 arr[10]를 가지고 있다는 의미

*************************************************************************************

ex 1) 언어에서의 배열

int arr[10];

int *p;

int foo(int);

// 명명한 형식 뒤에 [] 나 ()가 있다면 []이 있을시 배열, ()가 있을시 함수,

// 뒤에 [] () 가 없을 때 앞에 * 가 있다면 포인터인것을 의미

ex 2)

<int (*a)[10]>; // 포인터 (a 가 묶여져 있음 근데 * 가 있기 때문에 포인터배열)

             // int [10]의 형식.

*************************************************************************************

int arr[5][10]; // arr은 원소형식에 대한 주소를 가지고있음.

int ar2[10][10];

int ar3[7][10];

총합을 구하고싶다면..

foo(int (*base)[10], int asize)

{

 int sum = 0;

 int I=0;

 for(i=0;i<asize;i++)

 {

  sum = foo2(base[i], 10); // base[i] = *(base + i); 를 나타냄.

 }

}

// 배열명은 원소형식에 대한 포인터를 나타낸다!!!!!!!!!!!!!!!!!!!!!!!!

// 배열명은 상수


ex) foo(arr, 5);

    foo(ar2, 10);

    foo(ar3, 7);

ex) int arr[10];

arr+3 (이것은 인트 포인터 형식)

arr[2] (이것은 인트 형식)

*************************************************************************************

int *b[10];  // 배열

int *c[10][10]; //

<int (*d(int))(int); // *d는 함수 int 는 매개변수,  함수포인터가 리턴형식임.>

<int (*d(int))(int); // d : 함수명, 입력매개변수 : 1개, 리턴형식 : int (*)(int);

*************************************************************************************

int a(int); // 함수명은 코드메모리주소의 시작번지를 가지고있음.

int b(int);

int c(int);

// signiture 자체가 원소형식이 됨.

*************************************************************************************

ex) 

int (*GetProcAddress)(int num)

{

 return arr[num];

}

*************************************************************************************

int (*arr[3])(int) = {a,b,c};


int (*e[4])(int, Int);

void (*f(int, void (*num)(int)))(int); // 두 번째 매개변수는 함수포인터

// 실제로 있는 signal 이라는 유닉스 함수 (리눅스??)


typedef int g; // int 형식을 g 라고 부름

typedef int(*h)[10]; int(*)[10]의 타입을 h 라고 명명함

typedef int(*i)(int, int) : int(*)(int, int)의 타입을 I 라고 명명함.

*************************************************************************************

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

동적 알고리즘 코딩자료  (0) 2010.08.12
직렬화  (0) 2010.08.12
배열  (0) 2010.08.12
자료구조 프로그래밍  (0) 2010.08.12
배열을 순차적으로 사용할 경우  (0) 2010.08.12
알고리즘이란??  (0) 2010.08.12
Posted by ... XJAPAN

댓글을 달아 주세요


자료구조(프로그래밍):동일한 형태의 원소 item을 연속적인(논리적) 메모리에 관리하는 기법

*************************************************************************************

int *base;

int asize;

asize = 10;

base = (int *)malloc(sizeof(int)*asize);

// 자료구조에선 base 를 배열이라고 명함.

*************************************************************************************

//c++개념으로 생각한다면

base = new int[asize] 와 base = (int*)malloc(sizeof(int)*asize) 는 같은 개념

// 배열명은 원소형식에 대한 주소를 가지고 있음.

// 사용할 때

base[i]= 7 식으로 둘다 사용하는 법이 같음.

*************************************************************************************

(int *)malloc(sizeof(int)*asize) << 런타임 시에 공간이 확보 (동적배열)

int base[10] << 런타임 전에 공간확보 (정적배열)

//공간을 확보 한 후에는 둘다 같은 의미. 공간을 확보하는 방법이 다른것 뿐이다!!!

//유효한 공간을 가리키느냐 아니냐를 중요하게 봐야함.

*************************************************************************************

// 의미가 없는 값으로 초기화 해놓고 사용해야 함.

int *base = 0;

// 조건문을 사용해서 비교를 하고 사용 (유효값을 가지고있는지 아닌지 확인하기 위해서)

if (base)

{

 base = 0; 사용이 끝났을 시 다시 0으로 초기화.

}

*************************************************************************************

#define MAX_STU 50

#define MAX_STU 50

Stu base[50];//선언된 위치에서 할당

Stu *base[MAX_STU];//시작시 비어있음

int max_stu;

int max_stu;

Stu *base;

Stu *base;

학생 50명을 관리함!!

학생개체 50개를 관리함!!


//데이터가 현재 있는지 없는지에 대한 flag 가 있어야 함.Stu 안에 정보가 있어야 함.

//그러기 위해선 if(base[i]){} 을 통해서 함. 그러기 위해선 0으로 초기화 해야 함.

//실질적으로 추가하기 위해선 base[i] = new Stu(); 로 해야함

//학생 한명 각각이 독립적인 구조!!!!!!!


void InitStorage()

{

 max_stu = GetMaxStu(); // 몇 명을 관리할지 입력받음

 base = (stu *)malloc(sizeof(stu)*max_stu);

 //max_stu 만큼의 메모리가 잡히게 됨.

}


// 차이점은 초기화하는 함수!!!!! 와 해제하는 함수!!!!!!! 일 뿐이다..

// 나머지는 동일함!! 코드가 일치함!!!

*************************************************************************************

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

직렬화  (0) 2010.08.12
배열  (0) 2010.08.12
자료구조 프로그래밍  (0) 2010.08.12
배열을 순차적으로 사용할 경우  (0) 2010.08.12
알고리즘이란??  (0) 2010.08.12
정렬을 하는 알고리즘의 예  (0) 2010.08.12
Posted by ... XJAPAN

댓글을 달아 주세요


< 배열을 순차적으로 사용할 경우 >

*************************************************************************************

ex) 

T arr[MAX];

int usage;

0 ~ usage 를 제외한 공간에 초기화 할 의무가 없다.

*************************************************************************************

만약, 정적인 배열이 아니라면?

!! 배열의 원소 개수가 반드시 결정될 필요는 없다. !!

정적, 동적, 확장 배열 모두 선택 할 수 있다는 뜻이다!!

*************************************************************************************

Hash 에 의해 보관할 때

공간을 만들었다면, 그 공간에 대해서 초기화 할 의무가 있다.

*배열의 원소 개수는 Max_Hash 값에 의해 결정되어진다.

Maximam Hash 값을 안다면 정적배열 가능

아닐경우에 확장배열을 사용가능

Index 에 의해 작업을 제공함.

중요한점 !!

Hash 에서는 usage 가 의미가 약하다.

배열 생성 후 공간(컨테이너)을 확장해서는 안된다.

처음 생성되었던 크기가 유지 되어야 함.

*************************************************************************************

정적인 배열을 만들 때

컨테이너 사이즈가 라이브러리 개발자에 의해 결정 되어 있다.

시작시 컨테이너 사이즈를 정할 수 없을때, 정적인 형태의 라이브러리를 사용할 개연성이 적다.


동적인 형태의 라이브러리를 만들어야 함!!

정적, 동적인 것 보다는 (확장 가능한 배열을 사용)!!!

*************************************************************************************

ex) vector<int> vi(100, 0)

크기가 100인 것일뿐 안에 들어있는 것은 없다.

0 을 써준 이유는 의미없는 값으로 초기화 할 의무가 있기 때문이다. //보관여부판별

정, 동적 으로 사용하기 위해 사용.

*************************************************************************************

 

< 특정 키순으로 보관 >

*************************************************************************************

값을 삽입할 때 특정 키순으로 삽입할 경우를 위한 함수가 insert 이다.


<비교 표>

 

순차

특정 key 순

Hash

보관

push_back

insert

[ ]

삭제

erase

erase

[ ]

탐색

iterator

iterator

[ ]


*************************************************************************************

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

배열  (0) 2010.08.12
자료구조 프로그래밍  (0) 2010.08.12
배열을 순차적으로 사용할 경우  (0) 2010.08.12
알고리즘이란??  (0) 2010.08.12
정렬을 하는 알고리즘의 예  (0) 2010.08.12
연결리스트  (0) 2010.08.12
Posted by ... XJAPAN

댓글을 달아 주세요


< 알고리즘 >

*************************************************************************************

알고리즘 - 어떠한 문제를 해결해 나가는 논리의 집합

*************************************************************************************

< 일반적인 알고리즘 >


iterative - 반복적

recursive - 재귀적

greedy - 탐욕적 (눈앞에 보이는 최선의 선택을 함)

dynamic - 동적 (경험적인 지식기반으로 문제를 해결해 나가는 방법)

NP-Problem - 문제를 해결해야할 요소가 n 개 있다면 n제곱 등 방정식 등 지수적인 성향을 지닐 때 ex)인공지능, 의사결정.

*************************************************************************************

< iterative 에서의 중요한 점!! >


반복적인 방법을 통해서 해결이 가능한가에 대한 입증이 필요!!


ex)


문제의 Domain         : 정렬

초기 조건              : n 개의 정렬되지 않은 원소들이 배열에 있다.

Loop 탈출 조건        : Loop을 수행했을 때 이전보다 Loop 탈출조건에 근접함증명.

Loop 불변성           : Loop를 수행할 때마다 변하지 않는것이 무엇인지에 대함..

Loop 변성             : Loop를 수행할 때마다 변하는 것이 무엇인지에 대함..

종료 조건              :

*************************************************************************************

선택 정렬 (배열의 시작 주소, 배열의 원소 개수)


Loop : 원소의 개수가 1보다 클동안


(1) 제일 작은 원소의 위치를 찾는다.

(2) 맨 앞의 요소와 찾은 위치의 요소를 교환한다.

(3) 시작 주소 증가

(4) 원소 개수 감소

시작 주소 앞에있는 요소들은 위치가 지정되어있고 더 이상 바뀌지 않는다. -_-??????

*************************************************************************************ex)

void SelectSort(void **base, int asize)

{

 void **min = 0;

 while(asize>1)

 {

  GetMinPos(base, asize, com);

  Swap(base, min);

  base++;

  asize--;

 }

}

*************************************************************************************

최소 위치 찾기 ( 배열 시작 주소, 원소개수)


최소 위치에 배열 시작 주소를 assign한다.

원소개수 감소

배열 시작 주소 증가

Loop : 원소 개수가 0보다 클 동안

최소 위치에 원소와 시작 주소 원소를 비교했을 때 > 라면 최소 위치에 배열 시작 주소 assign

원소개수 감소

배열시작 주소 증가

불변성 : 이전 ~ 최소 위치 사이에 최소값의 위치를 알고있게 된다.

*************************************************************************************

ex)

typedef int (*Compare)(void *, void *);

void **GetMinPos(void **base, int asize, Compare com)

{

 void **min = base;

 asize--;

 base++;

 while(asize)

 {

  if(Com(*min, *base)>0)

  {

   min = base;

  }

  asize--;

  base++;

 }

}

int ComByNum(Stu * a, Stu * b)

{

 return strcmp(a->num, b->num);

}

SelectSort(arr, 10, CompareByNum);

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

자료구조 프로그래밍  (0) 2010.08.12
배열을 순차적으로 사용할 경우  (0) 2010.08.12
알고리즘이란??  (0) 2010.08.12
정렬을 하는 알고리즘의 예  (0) 2010.08.12
연결리스트  (0) 2010.08.12
의사결정 알고리즘.  (0) 2010.08.12
Posted by ... XJAPAN

댓글을 달아 주세요


< 정렬을 하는 알고리즘의 예 >

*************************************************************************************

7 5 23 9 6 5 8 12 (n 개의 숫자)

============================

T(n) = T'(n)+1 + T'(n-1)+1 + ... + T'(2) + 1

     = (n-1+1) + (n-2+1)+ ... 1

     = n(n-1)/2 = n2-n/2 = n2

*************************************************************************************

< 버블 정렬 >

*************************************************************************************

2 7 5 8 4 9 12 16

n-1, n-2, n-3 ~ 1

맨 끝에는 최대값이 들어감. 마지막 값을 제외하고 계속 비교. 그 중에서 마지막값을 제외.. 계속 반복하게 됨.

즉. Arraysize 보다 뒤쪽은 고정적이고 큰 수가 오게 됨.

*************************************************************************************

< 함수 객체 >


함수객체 - 함수처럼 사용되는 객체

*************************************************************************************

ex) 

Foo foo;

a = foo(2,3);

class Foo

{

public:

 int operator() (int a, int b)

 {

  return a+b;

 }

};

// 인스턴스를 함수명처럼 사용 가능함.

*************************************************************************************

template <class T, class F>

void Sort(T*base, int asize, F fun)

{

 T * min = 0;

 while(asize > 1)

 {

  GetMinPos(base, asize, fun)

  Swap(min, base);

  base++;

  asize--;

 }

}


template <class T, class F>

T *GetMinPos(T *base, int asize, F fun)

{

 T * min = base;

 base ++;

 asize --;

 while (asize)

 {

  if (fun(min, *base)>0)

  {

   min = base;

  }

 base++;

 asize--;

 }

 return min;

}


class FunStu

{

public:

 int operator(Stu *s, stu *녀)

 {

  return s->GetNum() = s2->GetNum();

 }

};

 

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

배열을 순차적으로 사용할 경우  (0) 2010.08.12
알고리즘이란??  (0) 2010.08.12
정렬을 하는 알고리즘의 예  (0) 2010.08.12
연결리스트  (0) 2010.08.12
의사결정 알고리즘.  (0) 2010.08.12
병합정렬  (0) 2010.08.12
Posted by ... XJAPAN

댓글을 달아 주세요


<연결리스트 >

*************************************************************************************

선형 구조.

연결리스트는 데이터 하나를 보관할 수 있는 노드가 있음.

노드 = 데이터 + 링크

링크 = 다른 노드의 위치 정보


1. 단일 연결 리스트

2. 이중 연결 리스트


맨 앞의 위치 정보를 가지고 있는 것 head (링크)

맨 뒤의 위치 정보를 가지고 있는 것 tail (링크)

<Tip> 연결리스트를 그릴 때 tail 노드의 뒤편을 가리키게 그리자!


<더미가 있는 연결리스트 >

*************************************************************************************

dum - 추가, 보조, 쓸데없는 것 이라는 의미를 가지고 있음.

더미 노드에 있는 데이터는 의미가 없다.

더미노드 = 사용자의 데이터를 가지고 있지 않은 노드. 링크가 의미가 있음.


< 이런식으로 코딩함>

*************************************************************************************

MyLinkedList::Node *now = new MyLinkedList::Node();


class MyLinkedList

{

 class Node

 {

  T nd;

  Node * after;

  Node * before;

 };

 Node * head;

 Node * tail;

 MyLinkedList() // 런타임시에 증가하는 타입

 {

  head에 더미노드를 생성하여 assign

  tail에 더미노드를 생성하여 assign

  head의 after에 tail을 assign

  tail의 before에 head를 assign

 }

 void push_back(T in){} // 테일 앞에 보관

 insert(tail, in)

 void insert(iterator at, T in); // 위치정보, 자료

 void clean();

}

ex)

now->before = at->before;

now->after = at;

at->before->after = now;

at->before = now;


비어있을 때를 생각해야함.

맨 앞을 지울 때 begin.()

맨 뒤를 지울때는 iterator 를 찾아서 감.


출력도 iterator.

clean 은 head 의 after 가 테일인지 비교. 아닐시에 after 를 erase

마지막에 delete head, delete tail

*************************************************************************************

 

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

알고리즘이란??  (0) 2010.08.12
정렬을 하는 알고리즘의 예  (0) 2010.08.12
연결리스트  (0) 2010.08.12
의사결정 알고리즘.  (0) 2010.08.12
병합정렬  (0) 2010.08.12
암호!  (0) 2010.08.12
Posted by ... XJAPAN

댓글을 달아 주세요

이전버튼 1 2 3 4 이전버튼