c 언어 구현 유 니 버 설 데이터 구조 (1): 유 니 버 설 링크

문득 2 년 전에 C 언어 를 배 울 때 C 언어 로 통용 되 는 데이터 구 조 를 쓴 적 이 있다 는 것 이 생각 났 다.주로 링크, 대열, 추, HashSet, 그리고 HashMap 을 실현 했다.당시 에는 표준 C 언어 에 이 방면 의 라 이브 러 리 가 없다 는 것 만 알 았 을 뿐, 나중에 야 제3자 의 이와 유사 한 라 이브 러 리 가 많다 는 것 을 알 게 되 었 다.잔말 말고 코드 부터 붙 여.
아래 에 실 현 된 것 은 유 니 버 설 링크 입 니 다. 링크 에 포인터 만 저장 되 어 있 고 실제 데 이 터 를 저장 하지 않 았 습 니 다.
헤더 파일
/*************************
*** File myList.h
**************************/

#ifndef MYLIST_H_INCLUDED
#define MYLIST_H_INCLUDED
#include 


typedef struct myNode
{
    void * data;
    struct myNode *next;
} MyNode;

typedef struct myList
{
    MyNode * first;
    MyNode * last;
    int count;
    int (*equal)(void * a, void * b);
} MyList;

typedef struct myListIterator
{
    MyNode * p;
    int count;
    int allSize;
} MyListIterator;

//    
MyList * createMyList();

//    ,      ,    
MyList * createMySearchList(int(*equal)(void * a, void * b));

//    
void freeMyList(MyList * list);

//     
void myListInsertDataAtLast(MyList* const list, void* const data);

//     
void myListInsertDataAtFirst(MyList * const list, void* const data);

//  
void myListInsertDataAt(MyList * const list, void* const data, int index);

//     
void* myListRemoveDataAtLast(MyList* const list);

//     
void* myListRemoveDataAtFirst(MyList * const list);

//  
void* myListRemoveDataAt(MyList* const list, int index);

//    ,        
int myListRemoveDataObject(MyList* const list, void * data);

//  
int myListGetSize(const MyList * const list);

//  
void myListOutput(const MyList * const list, void(*pt)(const void * const));

//    
void* myListGetDataAt(const MyList * const list, int index);

//       
void* myListGetDataAtFirst(const MyList * const list);

//        
void* myListGetDataAtLast(const MyList * const list);

//         ,  equal    ,    ,    equal  
//       -1,    ,          
int myListFindDataIndex(const MyList * const list, void * data);

//     
MyListIterator* createMyListIterator(const MyList * const list);

//     
void freeMyListIterator(MyListIterator* iterator);

//           
int myListIteratorHasNext(const MyListIterator* const iterator);

//           
void * myListIteratorNext(MyListIterator* const iterator);

#endif // MYLIST_H_INCLUDED

원본 파일
/*************************
*** File myList.c
**************************/

#include "myList.h"
#include 
//    
MyList * createMyList()
{
    MyList * re = (MyList *) malloc(sizeof(MyList));
    re->count = 0;
    re->first = NULL;
    re->last = NULL;
    re->equal = NULL;
    return re;
}

//    
void freeMyList(MyList * list)
{
    MyNode * p;
    while (list->first)
    {
        p = list->first->next;
        free(list->first);
        list->first = p;
    }
    free(list);
}

//     
void myListInsertDataAtLast(MyList * const list, void* const data)
{
    MyNode * node = (MyNode *) malloc(sizeof(MyNode));
    node->data = data;
    node->next = NULL;
    if (list->count)
    {
        list->last->next = node;
        list->last = node;
    }
    else
    {
        list->first = node;
        list->last = node;
    }
    (list->count)++;
}

//     
void myListInsertDataAtFirst(MyList * const list, void* const data)
{
    MyNode * node = (MyNode *) malloc(sizeof(MyNode));
    node->data = data;
    node->next = NULL;

    if (list->count)
    {
        node->next = list->first;
        list->first = node;
    }
    else
    {
        list->first = node;
        list->last = node;
    }
    (list->count)++;
}

//  
int myListGetSize(const MyList * const list)
{
    return list->count;
}

//  
void myListOutput(const MyList * const list, void(*pt)(const void * const))
{
    MyNode * p = list->first;
    while (p)
    {
        (*pt)(p->data);
        p = p->next;
    }
}

//     
void* myListRemoveDataAtLast(MyList* const list)
{
    if (list->count == 1)
    {
        return myListRemoveDataAtFirst(list);
    }
    MyNode * p = list->first;
    while (p->next != list->last)
    {
        p = p->next;
    }
    void *re = list->last->data;
    free(list->last);
    p->next = NULL;
    list->last = p;
    (list->count)--;
    return re;
}

//     
void* myListRemoveDataAtFirst(MyList * const list)
{
    MyNode *p = list->first;
    list->first = p->next;
    void * re = p->data;
    free(p);
    (list->count)--;
    if (list->count == 0)
    {
        list->last = NULL;
    }
    return re;
}

//  
void myListInsertDataAt(MyList * const list, void* const data, int index)
{
    if (index == 0)
    {
        myListInsertDataAtFirst(list, data);
        return;
    }
    if (index == list->count)
    {
        myListInsertDataAtLast(list, data);
        return;
    }
    MyNode * node = (MyNode *) malloc(sizeof(MyNode));
    node->data = data;
    node->next = NULL;

    MyNode * p = list->first;
    for (int i = 0; i < index - 1; i++)
    {
        p = p->next;
    }
    node->next = p->next;
    p->next = node;

    (list->count)++;
}

//  
void* myListRemoveDataAt(MyList* const list, int index)
{
    if (index == 0)
    {
        return myListRemoveDataAtFirst(list);
    }
    if (index == list->count - 1)
    {
        return myListRemoveDataAtLast(list);
    }

    MyNode * p = list->first;
    for (int i = 0; i < index - 1; i++)
    {
        p = p->next;
    }
    MyNode *tp = p->next;
    p->next = p->next->next;
    void * re = tp->data;
    free(tp);
    (list->count)--;
    return re;
}

//    
void* myListGetDataAt(const MyList * const list, int index)
{
    if (index == list->count - 1)
    {
        return myListGetDataAtLast(list);
    }
    MyNode * p = list->first;
    for (int i = 0; i < index; i++)
    {
        p = p->next;
    }
    return p->data;
}

//       
void* myListGetDataAtFirst(const MyList * const list)
{
    return list->first->data;
}

//        
void* myListGetDataAtLast(const MyList * const list)
{
    return list->last->data;
}

//         ,  equal    ,    ,    equal  
//       -1,    ,          
int myListFindDataIndex(const MyList * const list, void * data)
{
    MyNode * p = list->first;
    int re = 0;
    if (list->equal)
    {
        while (p)
        {
            if (p->data == data || (*(list->equal))(p->data, data))
            {
                return re;
            }
            re++;
            p = p->next;
        }

    }
    else
    {
        while (p)
        {
            if (p->data == data)
            {
                return re;
            }
            re++;
            p = p->next;
        }
    }
    return -1;
}

//    ,      ,    
MyList * createMySearchList(int(*equal)(void * a, void * b))
{
    MyList * re = createMyList();
    re->equal = equal;
    return re;
}

//     
MyListIterator* createMyListIterator(const MyList * const list)
{
    MyListIterator * re = (MyListIterator *) malloc(sizeof(MyListIterator));
    re->p = list->first;
    re->allSize = list->count;
    re->count = 0;
    return re;
}

//     
void freeMyListIterator(MyListIterator* iterator)
{
    free(iterator);
}

//           
int myListIteratorHasNext(const MyListIterator* const iterator)
{
    return iterator->count < iterator->allSize;
}

//           
void * myListIteratorNext(MyListIterator* const iterator)
{
    void * re = iterator->p->data;
    iterator->p = iterator->p->next;
    (iterator->count)++;
    return re;
}

//    ,        
int myListRemoveDataObject(MyList* const list, void * data)
{
    MyListIterator * it = createMyListIterator(list);
    int a = 0;
    while (myListIteratorHasNext(it))
    {
        void * ld = myListIteratorNext(it);
        if (data == ld || (list->equal != NULL && (*(list->equal))(ld, data)))
        {
            a = 1;
            break;
        }
    }
    if (a)
    {
        myListRemoveDataAt(list, it->count - 1);
    }
    return a;
}

테스트 파일
/*************************
*** File main.c
*** test for MyList
**************************/
#include 
#include 
#include "myList.h"

typedef struct a
{
    int i;
    char c;
} A;

void ppt(const void* const p)
{
    A * pp= p;
    printf("%d(%c) ", pp->i, pp->c);
}


int main()
{
    const int S =10;

    //        
    A * data= malloc(sizeof(A)*S);
    for (int i=0; i< S; i++)
    {
        data[i].i=i;
        data[i].c=(char)('A'+0);
    }

    //    
    MyList * list= createMyList();

    //        
    myListInsertDataAtLast( list, &data[0]);
    myListInsertDataAtFirst( list, &data[4]);
    myListInsertDataAt(list, &data[1], 1 );


    //    
    int index = myListFindDataIndex(list, &data[2]);
    printf("%d
", index); index = myListFindDataIndex(list, &data[4]); printf("%d
", index); // myListOutput(list, ppt ); puts(""); // MyListIterator * it = createMyListIterator(list); while(myListIteratorHasNext(it)) { A * pp = myListIteratorNext(it); printf("%d[%c] ", pp->i, pp->c); } puts(""); // freeMyListIterator(it); // freeMyList(list); // free(data); return 0; }

좋은 웹페이지 즐겨찾기