[게임알고리즘] 3-2강 링크 리스트

3-1강에서 구현한 링크 리스트에서

- 추가하거나 삭제할때 노드 총 수를 반복적으로 구하는것을 피하고

- 메모리를 관리할 수 있도록 변경

- 사용하기 편하도록 객체화

 

NodeMgt nm이 main에서 벗어나는 순간, 추가된 문자열이 출력되고 삭제되는것을 확인 가능함.

#include "NodeMgt.h"
 
void cb(void* data)
{
    const char* s = (const char*)data;
    printf("cb[%s]\n", s);
    delete s;
}
 
int main() {
    
    NodeMgt nm(cb);
    
    const char* str[] = { "Hi", "world", "!!" };
    for(int i=0; i<3; i++)
    {
        const char* t = str[i];
        int len = strlen(t);
        char* s = new char[len + 1];
        //strcpy(s, t);
        memcpy(s, t, sizeof(char) * len);
        s[len] = 0;
        
        nm.add(s);
    }
    
    const char* t = str[0];
    int len = strlen(t);
    char* s = new char[len + 1];
    strcpy(s, t);
    //nm.add(s);
    nm.add(0, s);
    
    //delNode(2);
    //delNode(str[0]);
    
    for(int i=0; i<nm.count; i++)
    {
        printf("nm[%d].data[%s]\n", i, (const char*)nm.at(i));
    }
 
    return 0;
}

 

 

 

NodeMgt.h

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
 
struct Node
{
    void* data;
    Node* prev;
};
 
typedef void (*MethodNodeMgt)(void* data);
 
struct NodeMgt
{
    Node* last;
    int count;
    MethodNodeMgt method;
    
    NodeMgt(MethodNodeMgt m);
    virtual ~NodeMgt();
    
    void add(void* data);
    void add(int index, void* data);
    
    void del(int index);
    bool del_(void* data);
    void del(void* data);
    void delAll();
    
    void* at(int index);
};
 

 

 

NodeMgt.cpp

#include "NodeMgt.h"
 
NodeMgt::NodeMgt(MethodNodeMgt m)
{
    last = NULL;
    count = 0;
    method = m;
}
 
NodeMgt::~NodeMgt()
{
    delAll();
}
 
void NodeMgt::add(void* data)
{
    Node* n = new Node;
    n->data = data;
    n->prev = last;
    
    last = n;
    count++;
}
    
void NodeMgt::add(int index, void* data)
{
    int i = count - 1;
    if( index==i )
    {
        add(data);
        return;
    }
    for(Node* p = last; p; p = p->prev, i--)
    {
        if(i==index)
        {
            Node* n = new Node;
            n->data = data;
            n->prev = p->prev;
            
            p->prev = n;
            count++;
            return;
        }
    }
    printf("failed to insert node\n");
}
    
void NodeMgt::del(int index)
{
    int i = count - 1;
    for(Node* p = last,* back = NULL; p; 
        back = p, p = p->prev, i--)
    {
        if(i==index)
        {
            if( back )
                back->prev = p->prev;
            else// if( last==NULL )
                last = p->prev;
            if( method )
                method(p->data);
            delete p;
            count--;
            return;
        }
    }
}
 
#if 0
 
bool NodeMgt::del_(void* data)
{
    for(Node* p = last, * back = NULL; p;
        back = p, p = p->prev)
    {
        if( p->data==data )
        {
            if( back )
                back->prev = p->prev;
            else
                last = p->prev;
            if( method )
                method(p->data);
            delete p;
            count--;
            return true;
        }
    }
    return false;
}
void NodeMgt::del(void* data)
{
    while(del_(data));
}
 
#else
 
void NodeMgt::del(void* data)
{
    for(Node* p = last, * back = NULL; p;)
        //back = p, p = p->prev)
    {
        if( p->data==data )
        {
            if( back )
                back->prev = p->prev;
            else
                last = p->prev;
            //back = back;// 000
            Node* bk = p->prev;// 111
            if( method )
                method(p->data);
            delete p;
            p = bk;
            count--;
        }
        else
        {
            back = p;// 000
            p = p->prev;// 111
        }
    }
}
#endif
    
void NodeMgt::delAll()
{
    for(Node* p = last; p; )
    {
        Node* bk = p->prev;
        if( method )
            method(p->data);
        delete p;
        p = bk;
    }
    last = NULL;
    count = 0;
}
 
void* NodeMgt::at(int index)
{
    int i = count - 1;
    for(Node* p = last; p; p = p->prev, i--)
    {
        if( i==index )
            return p->data;
    }
    return NULL;
}

 

매일매일 열심히 게임개발하고 있습니다