#include <iostream>

 

using namespace std;

 

class Node{ // Node Class

public:

        Node(int n);

        Node* nextNode;

        Node* prevNode;

        int data;

};

 

Node::Node(int n)

{

        data = n;

        nextNode = NULL;

        prevNode = NULL;

}

 

class Queue{ // Queue

public:

        Queue();

        void enQueue(int n);

        void deQueue();

        void printQueue();

        int QueueSize();

private:

        int size;

        Node* front;

        Node* rear;

};

Queue::Queue()

{

        size = 0;

        front = NULL;

        rear = NULL;

}

void Queue::enQueue(int n)

{

        Node* NewNode = new Node(n);

        if(size==0) // r == f

        {

               front = NewNode;

               rear = NewNode;

        }

        else // r != f

        {

               Node* temp = rear;

               rear = NewNode;

               rear->nextNode = temp;

               temp->prevNode = rear;

        }

        size++;

}

void Queue::deQueue()

{

        Node* temp = front;

        front = temp->prevNode;

        delete temp;

        size--;

}

 

int Queue::QueueSize() { return size; }

 

void Queue::printQueue()

{

        Node* temp = front;

        cout << "Queue List" << " (Queue Size : " << QueueSize() << " )" << endl;

        while(1)

        {

               cout << temp->data << endl;

               if(temp->prevNode == NULL)

                       break;

               temp = temp->prevNode;

        }

}

int main()

{

        Queue q;

        q.enQueue(3);

        q.enQueue(4);

        q.enQueue(5);

        q.deQueue();

        q.printQueue(); // 4 5

        q.enQueue(7);

        q.enQueue(2);

        q.deQueue();

        q.enQueue(1);

        q.printQueue(); // 5 7 2 1

        return 0;

}

 


신고

'Data Structure' 카테고리의 다른 글

List로 구현한 Queue  (0) 2013.01.31
Binary Trees  (0) 2012.11.07
CircularArray(환형 배열, queue)  (0) 2012.10.24
간단한 리스트 구현(단방향)  (0) 2012.09.08
Linked List(링크드 리스트)  (0) 2012.03.24
큐(Queue)  (0) 2012.03.02

ㅎㅎ 학교과제로 쌈박한 트리구현이 나와버렸어요

어차피 과제 제출기간도 끝났으니 포스팅해볼게여 ㅋㅋ

그전에 잠시 Binary Tree(이진 트리)에 대해 설명해볼게요

이진 트리(binary tree)란 한 노드가 최대 두 개의 자식 노드를 가지는 트리를 뜻합니다. 보통 첫 번째 노드를 부모 노드라고 하며 자식 노드는 왼쪽(left)과 오른쪽(right)으로 불린다. 이진 트리는 이진 탐색 트리와 이진 힙의 구현에 흔히 쓰입니다.

그림으로 보시면 이해가 빠르실거에요

자 이제 여기서 자식의 수가 가변적인 일반 트리구조와 가장 큰 차이점은 바로 자식노드가 2개라는 점인데요.

일반적으로 자식의 수가 정해져 있다면 구현상으로 더 쉬울듯합니다(아님말구요...)

그러면 일반 트리에서 이진 트리로 바꾸는 방법이 있을텐데요. 네 있습니다.


공식 : 현재(자기자신) 노드에서 Left는 자신의 자식(Child), Right는 자신의 형제(Sibling이라고 표현하기도 합니다.)로 둡니다. 


자 그러면 공식을 배웠으니 적용해볼까요?ㅎㅎㅎㅎㅎㅎ

      


짜자잔


    


위쪽은 일반트리, 아래쪽은 일반트리를 이진트리로 바꾼 구조입니다.

쉽죠?ㅋㅋㅋㅋ

다음 포스팅에는 구체적으로 바이너리트리를 이용한 회원관리 프로그램을 설명하도록 하겠습니다.

이것만 알면 쉽게 트리를 구현할수 있어요

신고

'Data Structure' 카테고리의 다른 글

List로 구현한 Queue  (0) 2013.01.31
Binary Trees  (0) 2012.11.07
CircularArray(환형 배열, queue)  (0) 2012.10.24
간단한 리스트 구현(단방향)  (0) 2012.09.08
Linked List(링크드 리스트)  (0) 2012.03.24
큐(Queue)  (0) 2012.03.02

환형 큐(이하 Circular Queue)에 대해서 간략히 설명해보겠습니다.

보통 스택이나 큐 같은 자료구조는 선형모양의 구조를 가지고 있는데요...

하지만 큐로 단순히 선형모양의 구조를 이용해 구현하게 된다면 문제점이 발생하죠..

바로 Front, rear사이에서 dequeue(앞 노드를 삭제)가 계속 이루어지고 enqueue(맨 뒤에 노드를 추가)작업을 하게되면 초기 배열의 N값을 넘어가게되면 추가를 못하게 되고 이전에 dequeue를 작업했던 front 앞의 배열공간들을 사용하지 못한다는게 단점인데요. 이 단점을 극복하고자 만들어진 구조가 바로 Circular queue가 되겠습니다.


사실은 별거 없구...

Enqueue 수행 시 => rear = (rear+1) Mod N

Dequeue 수행 시 => front = (front+1) Mod N

이것만 기억해두고 소스를 보시면 쉽게 이해하실 듯 합니다.


/*

Circular_Array.cpp

Made by hahahia

*/

#include <iostream>

#include <string>

using namespace std;

 

class CircularArray{

private:

        int N;

        string data[5];

        int n; // ArraySize

        int f; // front

        int r; // rear

public:

        CircularArray() : f(0), r(0), n(0), N(5) {} // Constructor

        void Enqueue(string str); // Insert

        void Dequeue(); // Remove

        bool isEmpty(); // Empty check

        void elemAtRank(int i); // at

        int size(); // size

        string front();

};

 

bool CircularArray::isEmpty(){

        return (n==0);

}

 

int CircularArray::size(){

        return n;

}

 

string CircularArray::front(){

        if(isEmpty())

        {

               cout << "error" << endl;

               return 0;

        }

        return data[f];

}

void CircularArray::Enqueue(string str){

        if(size() == N){

               cout << "error!!" << endl;

               return;

        }

        data[r] = str;

        r = (r+1)%N;

        n++;

        return;

}

 

void CircularArray::Dequeue(){

        if(isEmpty())

        {

               cout << "error" << endl;

               return;

        }

        string temp;

        temp = data[f];

        f = (f+1)%N;

        n--;

        cout << "delete : " << temp << endl;

}

void CircularArray::elemAtRank(int i){

        if(i>n-1)

        {

               cout << "error" << endl;

               return;

        }

        else cout << data[(i + f) % N] << endl;

}

int main(){

        CircularArray A;

        A.Enqueue("hahahia");

        A.Enqueue("qwerty");

        A.Enqueue("Inha");

        A.Enqueue("Computer Science");

        cout << A.front() << endl;

        A.elemAtRank(3);

        A.Dequeue();

        A.elemAtRank(0);

        A.elemAtRank(2);

        A.Enqueue("Science");

        A.Dequeue();

        A.elemAtRank(2);

        A.elemAtRank(3); // error

        A.Enqueue("tas");

        A.elemAtRank(3);

        A.Enqueue("asdf");

        A.elemAtRank(4);

        A.Dequeue();

        A.elemAtRank(0);

        return 0;

}

 

신고

'Data Structure' 카테고리의 다른 글

List로 구현한 Queue  (0) 2013.01.31
Binary Trees  (0) 2012.11.07
CircularArray(환형 배열, queue)  (0) 2012.10.24
간단한 리스트 구현(단방향)  (0) 2012.09.08
Linked List(링크드 리스트)  (0) 2012.03.24
큐(Queue)  (0) 2012.03.02

사실 이번학기 자료구조를 수강하는데 첫시간부터 리스트 구현을 했어요...ㅎㅎ

제 블로그 보시면 이전에 더블 링크드 리스트 구현을 했었는데 기억도 가물가물하고

복습할 겸 다시 포스팅해봐요 ㅎㅎ

간단한 기능부터 시작해서 추가 기능을 구현하는 식으로 포스팅 할께요.


일단 음... 단방향 리스트부터 ㅋㅋ

노드 추가 및 삭제(오직 head 부분에서만) 그리고 현재 리스트 출력, 리스트 길이 출력 기능


/* 단방향 리스트 구현

made by hahahia

*/

 

#include <iostream>

using namespace std;

 

class Node{ // node class

        public:

               int value;

               Node* Next;

               Node(int input){

                       value = input;

               }

};

class List{ // list class

        public:

               List();

               ~List();

               bool empty() const;

               const int& front() const;

               void addFront(int val);

               void deleteFront();

               void PrintList();

               int ListLength();

private:

        int count;

        Node* head;

};

 

List::List() : head(NULL), count(0) {} // constructor

List::~List(){ while(!empty()) deleteFront(); }

bool List::empty() const { return head==NULL; }

const int& List::front() const { return head->value; } // return first value

void List::addFront(int val){ // only front

        Node* NewNode = new Node(val);

        NewNode->Next = head;

        head = NewNode;

        count++;

        cout << "input complete" << endl;

}

void List::deleteFront(){ // only front

        Node* NowNode = head;

        head = NowNode->Next;

        delete NowNode;

        count--;

        cout << "delete complete" << endl;

}

int List::ListLength() { return count; } // check length

void List::PrintList(){ // print list

        Node* NowNode = head;

        for(int i=0; i<count; i++){

               cout << i+1 << " Node Data : " << NowNode->value << endl;

               NowNode = NowNode->Next;

        }

}

 

int main(){

        List list1;

        list1.addFront(3);

        list1.addFront(4);

        list1.addFront(7);

        list1.deleteFront(); // delete 7

        list1.addFront(5);

        list1.PrintList();

        return 0;

}

 

출력화면



구현해놓고 나니깐 왠지 스택 구조가 된거같아요 ㅋㅋ

신고

'Data Structure' 카테고리의 다른 글

Binary Trees  (0) 2012.11.07
CircularArray(환형 배열, queue)  (0) 2012.10.24
간단한 리스트 구현(단방향)  (0) 2012.09.08
Linked List(링크드 리스트)  (0) 2012.03.24
큐(Queue)  (0) 2012.03.02
스택(stack)  (0) 2012.02.19

           

/* linkedlist.cpp */

#include <iostream>

using namespace std;

 

class Node

{

public:

        Node* prevNode;

        Node* nextNode;

        int nodeData;

        int nodeIndex;

 

        Node()

        {

               prevNode = NULL;

               nextNode = NULL;

               nodeData = 0;

               nodeIndex = 0;

        }

        Node(int _data)

        {

               prevNode = NULL;

               nextNode = NULL;

               nodeData = _data;

               nodeIndex = 0;

        }

};

 

class LinkedList{

private:

        int count;

        Node* first;

public:

        LinkedList()

        {

               count = 0;

               first = new Node();

        }

        void insert(int add)

        {

               Node* NewNode = new Node(add);

               if(first->nextNode == NULL) // 삽입하려는 노드가 첫번째 노드일 경우

               {

                       first->nextNode = NewNode;

                       NewNode->prevNode = first;

                       NewNode->nodeIndex = count;

               }

               else // 삽입하려는 노드가 첫번째 노드가 아닐 경우

               {

                       Node* NowNode = first;

                       while(NowNode->nextNode != NULL) // NowNode nextNode NULL 경우까지 계속해서 search

                       {         

                              NowNode = NowNode->nextNode;

                       }

                       NowNode->nextNode = NewNode; // NowNode 다음노드에 새로 삽입하려는 노드가 들어감.

                       NewNode->prevNode = NowNode; // 새로 삽입하려는 노드의 prevNode NowNode 가르켜야한다.

                       NewNode->nodeIndex = count;

               }

               count++;

        }

        void showAll()

        {

               Node* NowNode = first;

               if(NowNode->nextNode == NULL)

               {

                       cout << "데이터가 하나도 없습니다. " << endl;

                       return;

               }

               while(NowNode->nextNode != NULL)

               {

                       NowNode = NowNode->nextNode; // nownode 이용하여 노드 데이터들을 출력!!

                       cout << NowNode->nodeData << "\t";

               }

        }

        void remove(int index)

        {

               Node* NowNode = first;

               if(NowNode->nextNode == NULL) // 노드가 없는 경우

               {

                       cout << "데이터가 하나도 없습니다." << endl;

               }

               else

               {

                       while(NowNode->nextNode != NULL)

                       {

                              NowNode = NowNode->nextNode;

                              if(NowNode->nodeIndex == index) // 삭제하려는 노드의 인덱스 찾기

                              {

                                      NowNode = NowNode->prevNode;

                                      if(NowNode->nextNode->nextNode == NULL) // 만약에 지우려는 노드가 마지막 노드일 경우

                                      {

                                             delete NowNode->nextNode; // 노드 삭제

                                             NowNode->nextNode = NULL; // NULL처리

                                      }

                                      else

                                      {

                                             NowNode->nextNode = NowNode->nextNode->nextNode; // 삭제하려는 노드를 지우고 사이를 다시 이어주는 과정

                                             delete NowNode->nextNode->prevNode; //

                                             NowNode->nextNode->prevNode = NowNode;

                                      }

                                      break;

                              }

                       }

                       while(NowNode->nextNode != NULL)

                       {

                              NowNode = NowNode->nextNode; // 하나가 줄었으니 밑의 노드들의 인덱스 하나씩 감소

                              NowNode->nodeIndex -= 1;

                       }

                       count--;

               }

        }

        int getCount()

        {

               return count;

        }

        ~LinkedList() // 링크드리스트 삭제

        {

               Node* NowNode = first;

               if(NowNode->nextNode == NULL)

               {

                       return;

               }

               NowNode = NowNode->nextNode;

               while(NowNode->nextNode != NULL)

               {

                       NowNode = NowNode->nextNode;

                       delete NowNode->prevNode;

               }

               delete NowNode;

        }

};

 

int main()

{

        LinkedList list;

        int op=0;

        int tempNum;

 

        cout <<"============== List Manager ============== " << endl;

        while(1)

        {

               cout << "--------------------------" << endl;

               cout << "1. Insert " << endl;

               cout << "2. Remove " << endl;

               cout << "3. Show " << endl;

               cout << "4. 현재 데이터 개수 출력" << endl;

               cout << "5. 종료" << endl;

               cin >> op;

               switch(op)

               {

               case 1:

                       cout << "\n추가할 정수 입력 : " ;

                       cin >> tempNum;

                       list.insert(tempNum);

                       break;

               case 2:

                       cout << "\n제거할 노드의 인덱스 입력(0부터) : " ;

                       cin >> tempNum;

                       if(tempNum < 0 || tempNum >= list.getCount())

                       {

                              cout << "error!!" << endl;

                              break;

                       }

                       list.remove(tempNum);

                       break;

               case 3:

                       cout << endl;

                       list.showAll();

                       cout << endl;

                       break;

               case 4:

                       cout << "현재 노드의 개수는 " << list.getCount() << " 개입니다." << endl;

                       break;

               case 5:

                       return 0;

               default:

                       cout << "error!! 올바른 숫자를 입력해주세요 " << endl;

                       break;

               }

        }

        return 0;

}

 


신고

'Data Structure' 카테고리의 다른 글

Binary Trees  (0) 2012.11.07
CircularArray(환형 배열, queue)  (0) 2012.10.24
간단한 리스트 구현(단방향)  (0) 2012.09.08
Linked List(링크드 리스트)  (0) 2012.03.24
큐(Queue)  (0) 2012.03.02
스택(stack)  (0) 2012.02.19
어느 한쪽으로는 데이터의 입력이 이루어지고, 다른 한 쪽에서 데이터의 삭제가 이루어지는 구조. 
선입선출(FIFO; First-In First-Out)구조라고도 함.
큐를 표현하기 위한 조건
- 전위 포인터(front pointer) : 큐의 실제 위치보다 1이 작은 위치를 가리킨다.
- 후위 포인터(rear pointer) : 큐에 마지막으로 삽입된 원소를 가리킨다
- 큐의 공백조건 : front = rear
- overflow 조건 : rear >= n(큐가 원소를 저장할 수 있는 개수)
- 초기 조건 : front = rear = 0 

// Queue.cpp 배열을 이용하여 구현
#include <stdio.h>
#include <stdlib.h>
#define MAX 5
typedef struct {
int key; // 큐의 구조
} element;

element queue[MAX]; // 큐 구조 배열 선언

int rear = -1; // queue를 가동할 index 변수
int front = -1;

void InsertQ(element item);
element DeleteQ();
void queue_full(element item);
element queue_empty();

void main()
{
int n, i;
element item;
while(1)
{
printf("\n 1. Insert 2. Delete (stop : otherwise) = ");
scanf("%d", &n);
switch(n)
{
case 1:
printf("\nInsert item = ");
scanf("%d", &item);
InsertQ(item);
break;
case 2:
printf("\nDelete item = %d", DeleteQ());
break;
default : exit(0);
}
// 현재 queue내용 출력
printf("\n\nQueue List");
for(i=front+1; i<=rear; i++)
{
printf("\nQueue[%d] = %d", i, queue[i]);
}
}
}
void InsertQ(element item)
{
// queue의 공간이 가득차면, overflow 함수 호출
if(rear == (MAX-1))
{
queue_full(item);
return;
}

queue[++rear] = item;
return;
}

element DeleteQ()
{
// queue의 공간에 자료가 없다면, empty 함수 호출
if(front==rear)
{
return queue_empty();
}
//큐의 자료를 삭제(front의 내용을 반환)
return queue[++front];
}
void queue_full(element item)
{
// 빈 공간이 있으면 앞쪽으로 자료를 이동하여 최적화시킴
int i;
// front쪽에도 빈 공간이 없으면 가득찼다는 메시지 출력
if(front==(-1))
{
printf("Queue is Full!");
return;
}
rear = rear-front;
for(i=0; i<rear; i++)
queue[i] = queue[++front];
front = -1;
queue[rear] = item;
return;
}
element queue_empty()
{
element err;
err.key = NULL;
printf("Queue is Empty !!");
return (err);
신고

'Data Structure' 카테고리의 다른 글

Binary Trees  (0) 2012.11.07
CircularArray(환형 배열, queue)  (0) 2012.10.24
간단한 리스트 구현(단방향)  (0) 2012.09.08
Linked List(링크드 리스트)  (0) 2012.03.24
큐(Queue)  (0) 2012.03.02
스택(stack)  (0) 2012.02.19
입력과 출력 작업이 리스트의 한 쪽 끝에서만 이루어지는 선형 리스트의 한 형태
선입후출의 구조(FILO; First-In Last-Out)
/* stack.cpp 배열을 사용한 스택 구현 */

#include <stdio.h> 
#define size 10
char stack[size];
int top = 0; // stack pointer
int i = 0;
void push(char ch); // push
char pop(); // pop
void printstack(); // 현재 stacklist 출력
void push(char ch)
{
if(top==size) // stack overflow
{
printf("stack is full\n");
return;
}
stack[top] = ch; // 스택에 한 문자 삽입
printf("push stack[%d]=%c\n", top, stack[top]);

top++; // stack pointer 1 증가
}

char pop()
{
if(top==0) // 스택이 underflow인경우
{
printf("stack is empty\n");
return 0;
}
top--; // stack pointer 1감소
return stack[top];
}
void printstack()
{
for(i=0;i<top; i++)
{
printf("stack[%d] = %c\n", i, stack[i]); 
}
}
void main()
{
push('a');  // stack에 a, b, c, d, e, f 노드 삽입
push('b');
push('c');
push('d');
push('e');
push('f');
printstack();
for(i=0; i<3; i++)
{
printf("pop stack[%d] = %c\n", top, pop()); // 스택에서 f, e, d를 삭제
}
printstack();


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


저작자 표시
신고

'Data Structure' 카테고리의 다른 글

Binary Trees  (0) 2012.11.07
CircularArray(환형 배열, queue)  (0) 2012.10.24
간단한 리스트 구현(단방향)  (0) 2012.09.08
Linked List(링크드 리스트)  (0) 2012.03.24
큐(Queue)  (0) 2012.03.02
스택(stack)  (0) 2012.02.19

+ Recent posts

티스토리 툴바