map과 multimap은 '연관 컨테이너'입니다. 모든 연관 컨테이너(set, multiset, map, multimap)는 '노드 기반 컨테이너'입니다. 또 모든 연관 컨테이너는 균형 2진 트리로 구현됩니다. 균형 2진 트리는 보통 레드-블랙 트리를 사용합니다. map은 key와 value의 쌍으로 구성된 데이터 셋의 집합입니다. 여기서 key는 유니크합니다. multiset도 map과 같이 key와 value의 쌍으로 구성된 데이터 셋의 집합입니다. 단, multiset은 map과 달리 중복된 key가 존재할 수 있습니다.

 


set과 map은 데이터의 key가 유니크합니다.

 


multiset과 multimap은 같은 key값의 데이터를 컨테이너에 저장할 수 있습니다.

 

map, multimap의 주요 특징과 함수

 map도 set처럼 데이터를 추가하는 push_? 류의 함수를 가지고 있지 않습니다. 삽입(insert)한다는 의미에서 insert() 함수를 가지고 있습니다.

map의 특징은 key와 value의 쌍으로 데이터를 저장합니다. 그리고 key값을 이용하여 빠르게 value값을 찾을 수 있습니다. 연관 컨테이너에서 유일하게 [] 연산자 중복을 제공합니다.

 

기본적인 map 예제

#include <iostream>
#include <map>
using namespace std;
void main( )
{
    map<int , int > m;

    m[5] = 100;
    m[3] = 50;
    m[7] = 80;
    m[2] = 100;
    m[4] = 100;

    cout << m[5] << endl;
    cout << m[3] << endl;
    cout << m[7] << endl;
    cout << m[2] << endl;
    cout << m[4] << endl;
}
  1. 100
    50
    80
    100
    100

map은 key와 value의 쌍으로 구성된 데이터들의 집합입니다. []연산자의 인덱스는 key이며 인덱스가 가리키는 메모리 값이 value입니다.

주의할 점은 m[5] = 100 연산에서 5라는 key가 없으면 노드 '추가'가되며 5라는 key가 있으면 '갱신'이 됩니다. 아래에서 공부합니다.



map의 key값 5로 value를 접근


 

 map은 key와 value의 쌍을 pair 객체로 저장합니다. STL의 쌍을 이루는 모든 요소는 pair 객체를 사용합니다.

위 예제는 insert()함수를 사용하여 아래 예제로 바꿀 수 있습니다.

#include <iostream>
#include <map>
using namespace std;
void main( )
{
    map<int , int > m;

    m.insert( pair<int,int>( 5, 100) );
    m.insert( pair<int,int>( 3, 50) );
    m.insert( pair<int,int>( 7, 80) );
    m.insert( pair<int,int>( 2, 100) );
    pair<int,intpr( 4, 100);
    m.insert( pr );

    cout << m[5] << endl;
    cout << m[3] << endl;
    cout << m[7] << endl;
    cout << m[2] << endl;
    cout << m[4] << endl;
}

  1. 100
    50
    80
    100
    100

 map은 key, value를 pair 객체로 각각 first와 second에 저장합니다.


 

 

반복자를 사용한 모든 key, value 출력 예제

#include <iostream>
#include <map>
using namespace std;

void main( )
{
    map<int , int > m;

    m[5] = 100;
    m[3] = 50;
    m[7] = 80;
    m[2] = 100;
    m[4] = 100;

    map<intint>::iterator iter;
    for( iter = m.begin(); iter != m.end() ; iter++)
        cout << "m["<<(*iter).first <<"]: " << (*iter).second << endl;

    cout << "==============" << endl;
    for( iter = m.begin(); iter != m.end() ; iter++)
        cout << "m["<<iter->first <<"]: " << iter->second << endl;
}
  1. m[2]: 100
    m[3]: 50
    m[4]: 100
    m[5]: 100
    m[7]: 80
    ==============
    m[2]: 100
    m[3]: 50
    m[4]: 100
    m[5]: 100
    m[7]: 80

 map도 양방향 반복자를 제공합니다.


 

 

연관 컨테이너는 모두 동일한 함수군을 가지며 동작 방식도 같습니다.

map의 검색 함수들입니다.

#include <iostream>
#include <map>
using namespace std;

void main( )
{
    map<int , int > m;

    m[5] = 100;
    m[3] = 50;
    m[7] = 80;
    m[2] = 100;
    m[4] = 100;

    map<intint >::iterator iter;

    iter = m.find( 5 );
    if( iter == m.end() )
        cout << "없음!" << endl;
    else
        cout << "m["<<iter->first <<"]: " << iter->second << endl;

    iter = m.lower_bound( 5 );
    if( iter == m.end() )
        cout << "없음!" << endl;
    else
        cout << "m["<<iter->first <<"]: " << iter->second << endl;

    iter = m.upper_bound( 5 );
    if( iter == m.end() )
        cout << "없음!" << endl;
    else
        cout << "m["<<iter->first <<"]: " << iter->second << endl;

    pair< map<intint>::iterator, map<intint>::iterator> iter_pair;
    iter_pair = m.equal_range(5);

    if( (iter_pair.first) == m.end() && (iter_pair.second == m.end()) )
        cout << "없음!" << endl;
    else
    {
        cout << "m["<< iter_pair.first->first <<"]: " << iter_pair.first->second <<" ~ ";
        cout << "m["<< iter_pair.second->first <<"]: " << iter_pair.second->second <<endl;
    }
}
  1. m[5]: 100
    m[5]: 100
    m[7]: 80
    m[5]: 100 ~ m[7]: 80

 동작은 set에서 설명했으므로 패스~!


 

 

 

마지막으로 multimap 예제입니다.

map과 다른 점은 [] 연산자가 없으며 key 값이 중복될 수 있습니다.

#include <iostream>
#include <map>
using namespace std;

void main( )
{
    multimap<int , int > m;

    m.insert( pair<int,int>( 5, 100) );
    m.insert( pair<int,int>( 3, 50) );
    m.insert( pair<int,int>( 7, 80) );
    m.insert( pair<int,int>( 2, 100) );
    m.insert( pair<int,int>( 4, 100) );
    m.insert( pair<int,int>( 7, 200) );
    m.insert( pair<int,int>( 7, 300) );

    pair<multimap<int,int>::iterator, multimap<intint>::iterator > iter_pair;
    iter_pair = m.equal_range( 7 );
    multimap<int,int>::iterator iter;
    for( iter = iter_pair.first ; iter != iter_pair.second ; iter++)
        cout << "m["<< iter->first <<"]: " << iter->second <<' ';
    cout << endl;

}
  1. m[7]: 80 m[7]: 200 m[7]: 300

 설명은 multiset과 같습니다.


'Programing > 자료구조' 카테고리의 다른 글

STL find함수 사용  (0) 2016.12.01
이중연결리스트 노드 cpp  (0) 2016.12.01
이중연결리스트 노드클래스  (0) 2016.12.01
이중연결리스트.cpp  (0) 2016.12.01
단일연결리스트.cpp  (0) 2016.11.30

InIt find(InIt first, InIt last, const T& val);


ex)

#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

using namespace std;

 

void main()

{

     string names[]={"김정수","구홍녀","문병대",

          "김영주","임재임","박미영","박윤자"}

;

     vector<string> as(&names[0],&names[7]);

 

     vector<string>::iterator it;

     it=find(as.begin(),as.end(),"안순자");

     if (it==as.end()) {

          cout << "없다" << endl;

     } else {

          cout << "있다" << endl;

     }

}




InIt find_if(InIt first, InIt last, UniPred F);


ex)

#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

using namespace std;

 

bool HasYoung(string who)

{

     return (who.find("영") != string::npos);

}

 

void main()

{

     string names[]={"김정수","구홍녀","문병대",

          "김영주","임재임","박미영","박윤자"};

     vector<string> as(&names[0],&names[7]);

 

     vector<string>::iterator it;

     for (it=as.begin();;it++) {

          it=find_if(it,as.end(),HasYoung);

          if (it==as.end()) break;

          cout << *it << "이(가) 있다." << endl;

     }

}




FwdIt adjacent_find(FwdIt first, FwdIt last [, BinPred F]);

ex)

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

 

void main()

{

     int ari[]={1,9,3,6,7,5,5,8,1,4};

     vector<int> vi(&ari[0],&ari[9]);

 

     vector<int>::iterator it;

     it=adjacent_find(vi.begin(),vi.end());

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

          printf("두 요소가 인접한 값은 %d입니다.\n",*it);

     }

}


FwdIt1 find_first_of(FwdIt1 first1, FwdIt1 last1, FwdIt2 first2, FwdIt2 last2 [, BinPred F]);

ex)

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

 

void main()

{

     int ar1[]={3,1,4,1,5,9,2,6,5,3,5,8,9,7,9,3,2,3,8,4,6,2,6,4,3};

     int ar2[]={2,4,6,8,0};

 

     int *p=find_first_of(&ar1[0],&ar1[25],&ar2[0],&ar2[4]);

     if (p!=&ar1[25]) {

          printf("최초의 짝수는 %d번째의 %d입니다.\n",p-ar1,*p);

     }



'Programing > 자료구조' 카테고리의 다른 글

STL 컨터이네(map,multimap)  (0) 2016.12.01
이중연결리스트 노드 cpp  (0) 2016.12.01
이중연결리스트 노드클래스  (0) 2016.12.01
이중연결리스트.cpp  (0) 2016.12.01
단일연결리스트.cpp  (0) 2016.11.30
#include "Node.h"

Node::Node(int num, Node *n,Node*p)
{
data = num;
next = n;
prev = p;

}
Node::Node(int num)
{

data = num;
next = NULL;
prev = NULL;
}
Node *Node::getPrev()
{
return prev;
}
Node * Node::getNext()
{
return next;
}

void Node::setNext(Node *n)
{
next = n;
}
void Node::setPrev(Node *p)
{
prev = p;
}

int Node::get_data()
{
return data;
}
void Node::set_data(Node *p)
{
data = p->data;
}


'Programing > 자료구조' 카테고리의 다른 글

STL 컨터이네(map,multimap)  (0) 2016.12.01
STL find함수 사용  (0) 2016.12.01
이중연결리스트 노드클래스  (0) 2016.12.01
이중연결리스트.cpp  (0) 2016.12.01
단일연결리스트.cpp  (0) 2016.11.30
#pragma once

#include <iostream>
class Node
{
private :
int data;
Node *prev;
Node *next;
public :
Node(int num, Node *n,Node* p);
Node(int num);

Node * getNext();
Node * getPrev();
int get_data();

void setNext(Node *n);
void setPrev(Node *p);
void set_data(Node *p);
};


'Programing > 자료구조' 카테고리의 다른 글

STL find함수 사용  (0) 2016.12.01
이중연결리스트 노드 cpp  (0) 2016.12.01
이중연결리스트.cpp  (0) 2016.12.01
단일연결리스트.cpp  (0) 2016.11.30
단일연결리스트.h  (0) 2016.11.30

/*****************************************************************************
*  ------------------------------- dlist.c --------------------------------  *
*****************************************************************************/
#include <stdlib.h>
#include <string.h>
#include "dlist.h"
/*****************************************************************************
*  ------------------------------ dlist_init ------------------------------  *
*****************************************************************************/
void dlist_init(DList *list, void (*destroy)(void *data)) {
 /*****************************************************************************
 *  Initialize the list.                                                      *
 *****************************************************************************/
 list->size = 0;
 list->destroy = destroy;
 list->head = NULL;
 list->tail = NULL;
 return;
}
/*****************************************************************************
*  ---------------------------- dlist_destroy -----------------------------  *
*****************************************************************************/
void dlist_destroy(DList *list) {
 void               *data;
 /*****************************************************************************
 *  Remove each element.                                                      *
 *****************************************************************************/
 while (dlist_size(list) > 0) {
  if (dlist_remove(list, dlist_tail(list), (void **)&data) == 0 && list->
   destroy != NULL) {
    /***********************************************************************
    *  Call a user-defined function to free dynamically allocated data.    *
    ***********************************************************************/
    list->destroy(data);
  }
 }
 /*****************************************************************************
 *  No operations are allowed now, but clear the structure as a precaution.   *
 *****************************************************************************/
 memset(list, 0, sizeof(DList));
 return;
}
/*****************************************************************************
*  ---------------------------- dlist_ins_next ----------------------------  *
*****************************************************************************/
int dlist_ins_next(DList *list, DListElmt *element, const void *data) {
 DListElmt          *new_element;
 /*****************************************************************************
 *  Do not allow a NULL element unless the list is empty.                     *
 *****************************************************************************/
 if (element == NULL && dlist_size(list) != 0)
  return -1;
 /*****************************************************************************
 *  Allocate storage for the element.                                         *
 *****************************************************************************/
 if ((new_element = (DListElmt *)malloc(sizeof(DListElmt))) == NULL)
  return -1;
 /*****************************************************************************
 *  Insert the new element into the list.                                     *
 *****************************************************************************/
 new_element->data = (void *)data;
 if (dlist_size(list) == 0) {
  /**************************************************************************
  *  Handle insertion when the list is empty.                               *
  **************************************************************************/
  list->head = new_element;
  list->head->prev = NULL;
  list->head->next = NULL;
  list->tail = new_element;
 }
 else {
  /**************************************************************************
  *  Handle insertion when the list is not empty.                           *
  **************************************************************************/
  new_element->next = element->next;
  new_element->prev = element;
  if (element->next == NULL)
   list->tail = new_element;
  else
   element->next->prev = new_element;
  element->next = new_element;
 }
 /*****************************************************************************
 *  Adjust the size of the list to account for the inserted element.          *
 *****************************************************************************/
 list->size++;
 return 0;
}
/*****************************************************************************
*  ---------------------------- dlist_ins_prev ----------------------------  *
*****************************************************************************/
int dlist_ins_prev(DList *list, DListElmt *element, const void *data) {
 DListElmt          *new_element;
 /*****************************************************************************
 *  Do not allow a NULL element unless the list is empty.                     *
 *****************************************************************************/
 if (element == NULL && dlist_size(list) != 0)
  return -1;
 /*****************************************************************************
 *  Allocate storage to be managed by the abstract data type.                 *
 *****************************************************************************/
 if ((new_element = (DListElmt *)malloc(sizeof(DListElmt))) == NULL)
  return -1;
 /*****************************************************************************
 *  Insert the new element into the list.                                     *
 *****************************************************************************/
 new_element->data = (void *)data;
 if (dlist_size(list) == 0) {
  /**************************************************************************
  *  Handle insertion when the list is empty.                               *
  **************************************************************************/
  list->head = new_element;
  list->head->prev = NULL;
  list->head->next = NULL;
  list->tail = new_element;
 }
 else {
  /**************************************************************************
  *  Handle insertion when the list is not empty.                           *
  **************************************************************************/
  new_element->next = element; 
  new_element->prev = element->prev;
  if (element->prev == NULL)
   list->head = new_element;
  else
   element->prev->next = new_element;
  element->prev = new_element;
 }
 /*****************************************************************************
 *  Adjust the size of the list to account for the new element.               *
 *****************************************************************************/
 list->size++;
 return 0;
}
/*****************************************************************************
*  ----------------------------- dlist_remove -----------------------------  *
*****************************************************************************/
int dlist_remove(DList *list, DListElmt *element, void **data) {
 /*****************************************************************************
 *  Do not allow a NULL element or removal from an empty list.                *
 *****************************************************************************/
 if (element == NULL || dlist_size(list) == 0)
  return -1;
 /*****************************************************************************
 *  Remove the element from the list.                                         *
 *****************************************************************************/
 *data = element->data;
 if (element == list->head) {
  /**************************************************************************
  *  Handle removal from the head of the list.                              *
  **************************************************************************/
  list->head = element->next;
  if (list->head == NULL)
   list->tail = NULL;
  else
   element->next->prev = NULL;
 }
 else {
  /**************************************************************************
  *  Handle removal from other than the head of the list.                   *
  **************************************************************************/
  element->prev->next = element->next;
  if (element->next == NULL)
   list->tail = element->prev;
  else
   element->next->prev = element->prev;
 }
 /*****************************************************************************
 *  Free the storage allocated by the abstract data type.                     *
 *****************************************************************************/
 free(element);
 /*****************************************************************************
 *  Adjust the size of the list to account for the removed element.           *
 *****************************************************************************/
 list->size--;
 return 0;
}



'Programing > 자료구조' 카테고리의 다른 글

이중연결리스트 노드 cpp  (0) 2016.12.01
이중연결리스트 노드클래스  (0) 2016.12.01
단일연결리스트.cpp  (0) 2016.11.30
단일연결리스트.h  (0) 2016.11.30
이중연결리스트  (0) 2016.11.30

/*****************************************************************************
*  ------------------------------- dlist.h --------------------------------  *
*****************************************************************************/
#ifndef DLIST_H
#define DLIST_H
#include <stdlib.h>
/*****************************************************************************
*  Define a structure for doubly-linked list elements.                       *
*****************************************************************************/
typedef struct DListElmt_ {
 void               *data;
 struct DListElmt_  *prev;
 struct DListElmt_  *next;
} DListElmt;
/*****************************************************************************
*  Define a structure for doubly-linked lists.                               *
*****************************************************************************/
typedef struct DList_ {
 int                size;
 int                (*match)(const void *key1, const void *key2);
 void               (*destroy)(void *data);
 DListElmt          *head;
 DListElmt          *tail;
} DList;
/*****************************************************************************
*  --------------------------- Public Interface ---------------------------  *
*****************************************************************************/
void dlist_init(DList *list, void (*destroy)(void *data));
void dlist_destroy(DList *list);
int dlist_ins_next(DList *list, DListElmt *element, const void *data);
int dlist_ins_prev(DList *list, DListElmt *element, const void *data);
int dlist_remove(DList *list, DListElmt *element, void **data);
#define dlist_size(list) ((list)->size)
#define dlist_head(list) ((list)->head)
#define dlist_tail(list) ((list)->tail)
#define dlist_is_head(element) ((element)->prev == NULL ? 1 : 0)
#define dlist_is_tail(element) ((element)->next == NULL ? 1 : 0)
#define dlist_data(element) ((element)->data)
#define dlist_next(element) ((element)->next)
#define dlist_prev(element) ((element)->prev)
#endif



/*****************************************************************************
*  -------------------------------- list.c --------------------------------  *
*****************************************************************************/
#include <stdlib.h>
#include <string.h>
#include "list.h"
/*****************************************************************************
*  ------------------------------- list_init ------------------------------  *
****************************************************************************/
void list_init(List *list, void (*destroy)(void *data)) {
 /*****************************************************************************
 *  Initialize the list.                                                      *
 *****************************************************************************/
 list->size = 0;
 list->destroy = destroy;
 list->head = NULL;
 list->tail = NULL;
 return;
}
/*****************************************************************************
*  ----------------------------- list_destroy -----------------------------  *
*****************************************************************************/
void list_destroy(List *list) {
 void               *data;
 /*****************************************************************************
 *  Remove each element.                                                      *
 *****************************************************************************/
 while (list_size(list) > 0) {
  if (list_rem_next(list, NULL, (void **)&data) == 0 && list->destroy != NULL) {
   /***********************************************************************
   *  Call a user-defined function to free dynamically allocated data.    *
   ***********************************************************************/
   list->destroy(data);
  }
 }
 /*****************************************************************************
 *  No operations are allowed now, but clear the structure as a precaution.   *
 *****************************************************************************/
 memset(list, 0, sizeof(List));
 return;
}
/*****************************************************************************
*  ----------------------------- list_ins_next ----------------------------  *
*****************************************************************************/
int list_ins_next(List *list, ListElmt *element, const void *data) {
 ListElmt           *new_element;
 /*****************************************************************************
 *  Allocate storage for the element.                                         *
 *****************************************************************************/
 if ((new_element = (ListElmt *)malloc(sizeof(ListElmt))) == NULL)
  return -1;
 /*****************************************************************************
 *  Insert the element into the list.                                         *
 *****************************************************************************/
 new_element->data = (void *)data;
 if (element == NULL) {
  /**************************************************************************
  *  Handle insertion at the head of the list.                              *
  **************************************************************************/
  if (list_size(list) == 0)
   list->tail = new_element;
  new_element->next = list->head;
  list->head = new_element;
 }
 else {
  /**************************************************************************
  *  Handle insertion somewhere other than at the head.                     *
  **************************************************************************/
  if (element->next == NULL)
   list->tail = new_element;
  new_element->next = element->next;
  element->next = new_element;
 }
 /*****************************************************************************
 *  Adjust the size of the list to account for the inserted element.          *
 *****************************************************************************/
 list->size++;
 return 0;
}
/*****************************************************************************
*  ----------------------------- list_rem_next ----------------------------  *
*****************************************************************************/
int list_rem_next(List *list, ListElmt *element, void **data) {
 ListElmt           *old_element;
 /*****************************************************************************
 *  Do not allow removal from an empty list.                                  *
 *****************************************************************************/
 if (list_size(list) == 0)
  return -1;
 /*****************************************************************************
 *  Remove the element from the list.                                         *
 *****************************************************************************/
 if (element == NULL) {
  /**************************************************************************
  *  Handle removal from the head of the list.                              *
  **************************************************************************/
  *data = list->head->data;
  old_element = list->head;
  list->head = list->head->next;
  if (list_size(list) == 1)
   list->tail = NULL;
 }
 else {
  /**************************************************************************
  *  Handle removal from somewhere other than the head.                     *
  **************************************************************************/
  if (element->next == NULL)
   return -1;
  *data = element->next->data;
  old_element = element->next;
  element->next = element->next->next;
  if (element->next == NULL)
   list->tail = element;
 }
 /*****************************************************************************
 *  Free the storage allocated by the abstract data type.                     *
 *****************************************************************************/
 free(old_element);
 /*****************************************************************************
 *  Adjust the size of the list to account for the removed element.           *
 *****************************************************************************/
 list->size--;
 return 0;
}



'Programing > 자료구조' 카테고리의 다른 글

이중연결리스트 노드클래스  (0) 2016.12.01
이중연결리스트.cpp  (0) 2016.12.01
단일연결리스트.h  (0) 2016.11.30
이중연결리스트  (0) 2016.11.30
단일연결리스트 head만 사용  (0) 2016.11.30

/*****************************************************************************
*  -------------------------------- list.h --------------------------------  *
*****************************************************************************/
#ifndef LIST_H
#define LIST_H
#include <stdlib.h>
/*****************************************************************************
*  Define a structure for linked list elements.                              *
*****************************************************************************/
typedef struct ListElmt_ {
 void               *data;
 struct ListElmt_   *next;
} ListElmt;
/*****************************************************************************
*  Define a structure for linked lists.                                      *
*****************************************************************************/
typedef struct List_ {
 int                size;
 int                (*match)(const void *key1, const void *key2);
 void               (*destroy)(void *data);
 ListElmt           *head;
 ListElmt           *tail;
} List;
/*****************************************************************************
*  --------------------------- Public Interface ---------------------------  *
*****************************************************************************/
void list_init(List *list, void (*destroy)(void *data));
void list_destroy(List *list);
int list_ins_next(List *list, ListElmt *element, const void *data);
int list_rem_next(List *list, ListElmt *element, void **data);
#define list_size(list) ((list)->size)
#define list_head(list) ((list)->head)
#define list_tail(list) ((list)->tail)
#define list_is_head(list, element) ((element) == (list)->head ? 1 : 0)
#define list_is_tail(element) ((element)->next == NULL ? 1 : 0)
#define list_data(element) ((element)->data)
#define list_next(element) ((element)->next)
#endif



'Programing > 자료구조' 카테고리의 다른 글

이중연결리스트.cpp  (0) 2016.12.01
단일연결리스트.cpp  (0) 2016.11.30
이중연결리스트  (0) 2016.11.30
단일연결리스트 head만 사용  (0) 2016.11.30
단일 연결리스트 더미노드  (0) 2016.11.30
//******************************************************************************
// 이중연결리스트 !!
//******************************************************************************
// 단일연결리스트 -> 단방향성
//*****************************5*************************************************
#include <stdio.h>
#include <malloc.h>
//******************************************************************************
// 구조체 선언
//******************************************************************************
typedef struct _Node
{
int data; // data
struct _Node * next; //다음 링크
struct _Node * prev; //이전 링크
}Node;
//******************************************************************************
//head , tail 더미 노드 활용 !!
//******************************************************************************
Node *head;
//******************************************************************************
// Utill
//******************************************************************************
Node *CreateNode(int data) //노드 생성
{
Node *Newnode = (Node *)malloc(sizeof(Node));
Newnode->data = data;
Newnode->next = NULL;
Newnode->prev = NULL;
return Newnode;
}
//******************************************************************************
void init()
{
head = CreateNode(0);
head->next = NULL;
head->prev = head;
}
//******************************************************************************
// 삽입연산 함수들
//******************************************************************************
void push_back(int data)
{
Node *Newnode = CreateNode(data);
Newnode->next = NULL;
tail->prev->next = Newnode;
Newnode->prev = tail->prev;
tail->prev = Newnode;
}
void push_front(int data)
{
Node * Newnode = CreateNode(data);
Newnode->prev = head;
head->next->prev = Newnode;
Newnode->next = head->next;
head->next = Newnode;
}
void insert(int key, int data)
{
Node *p = head->next;
Node *Newnode = CreateNode(data);
while(p != tail){
if(p->data == key){
Newnode->next = p->next;
Newnode->prev = p;
p->next->prev = Newnode;
p->next = Newnode;
return;
}
else{
p = p-> next;
}
}
Newnode->next = tail;
tail->prev->next = Newnode;
Newnode->prev = tail->prev;
tail->prev = Newnode;
}
//******************************************************************************
//삭제연산 함수들
//******************************************************************************
void pop_back()
{
Node *p = tail->prev;
if(tail->prev == head){
printf("list empty !!!");
}
else{
p->prev->next = tail;
tail->prev = p->prev;
free(p);
}
}
void pop_front()
{
Node *p = head->next;
if(head->next == tail){
printf("list empty");
}
else{
head->next = p->next;
free(p);
}
}
void erase(int key)
{
Node *p = head->next;
Node *s;
while(p != tail){
if(p->data == key){
p->prev->next = p->next;
p->next->prev = p->prev;
s = p->next;
free(p);
p = s;
//return;
}
else{
p = p-> next;
}
}
}
//******************************************************************************
void show()
{
Node *p = head->next;
while(p != tail)
{
printf("%d-->", p->data); 
p = p->next;
}
puts("");
}


void main()
{
init();
push_back(30);
show();
push_back(50);
show();
push_front(30);
show();
push_front(30);
show();
push_front(50);
show();
push_front(30);
show();
erase(30);
show();
}


'Programing > 자료구조' 카테고리의 다른 글

단일연결리스트.cpp  (0) 2016.11.30
단일연결리스트.h  (0) 2016.11.30
단일연결리스트 head만 사용  (0) 2016.11.30
단일 연결리스트 더미노드  (0) 2016.11.30
자료구조  (0) 2016.11.30
//****************************************************************************
//단일 연결리스트 head노드만을 이용 !!
//****************************************************************************

#include <stdio.h>
#include <stdlib.h>

typedef struct _Node
{
int data;
struct _Node *next;
}Node;
//****************************************************************************
Node * head;
//****************************************************************************
Node *CreateNode(int data)
{
Node * newnode = (Node *)malloc(sizeof(Node));
newnode->data = data;
newnode->next = NULL;
return newnode;
}//노드 생성 함수 !!
//****************************************************************************
void init()
{
head = CreateNode(0);
}
//****************************************************************************
// 삭제 함수
//****************************************************************************
//맨 뒤의 노드를 삭제 !!
//****************************************************************************
void pop_back()
{
Node *p, *s;
if(head->next == NULL){
puts("list empty !!");
}
else{
s= head;
p = head->next;
while(p->next != NULL){
s = p;
p = p->next;
}
}
s ->next = NULL;
free(p);
}
//****************************************************************************
//맨 앞의 노드를 삭제 !!
//****************************************************************************
void pop_front()
{
Node *p;
if(head->next == NULL){
printf("list empty !! \n");
}
else{
p = head->next;
head->next = p->next;
free(p);
}
}
//****************************************************************************
// data에 해당하는 노드 삭제!!
//****************************************************************************
void erase_value(int data)
{
Node *p,*s;
p = head->next;
s = head;
while(p->next != NULL){
if(p->data == data){
s->next = p->next;
free(p);
return;
}
else{
s=p;
p = p->next;
}
}
printf("No date");
puts("");
}
//****************************************************************************
// 1번째 3번째
//****************************************************************************
void erase_idx(int idx)
{
Node *p,*s;
p = head->next;
s = head;
int i=0;
while(p->next != NULL){
if(i == idx-1){
s->next = p->next;
free(p);
return;
}
else{
s = p;
p = p->next;
}
i++;
}
printf("No date");
puts("");

}
//****************************************************************************
//****************************************************************************
//입력 함수들
//****************************************************************************
void push_back(int data)
{
Node * p = head;
Node * newnode = CreateNode(data);
while(p->next != NULL)
{
p = p->next;
}
p ->next = newnode;
}
void push_front(int data)
{
Node *newnode = CreateNode(data);
newnode->next = head->next;
head->next = newnode;
}
void insert(int key, int data)
{
Node * p = head->next;
while(p->next != NULL){
if(p->next->data == key) {
Node * newnode =CreateNode(data);
newnode->data = data;
newnode->next = p->next;
p->next = newnode;
return;
}
else{
p = p->next;
}
}
push_back(data);
}
void insert_back(int key, int data)
{
Node *p = head->next;
while(p->next !=NULL){
if(p->data == key){
Node *newnode = CreateNode(data);
p->next->data = data;
newnode->next = p->next;
p->next = newnode;
return;
}
else{
p = p->next;
}
}
push_back(data);
}
void show()
{
Node * p = head->next;
while(p != NULL){
printf("%d --> ",p->data);
p = p->next;
}
puts("");
}
int Find_Number(int num)
{
Node *p=head;
while(p->next != NULL)
{
if(p->data == num)
{
printf("%d\n",p->data);
return p->data;
}
else
{
p = p->next;
}
}
puts("nonono");
return 0;
}
int Fine_idx(int data)
{
int i=0;
Node *p=head;
while(p->next != NULL){
if(i == data){
printf("%d\n",p->data);
return p->data;
}
else{
p = p->next;
}
i++;
}
puts("nonono");
return NULL;
}
int Fine_Back()
{
Node *p = head;
while(p->next != NULL){
p = p->next;
}
printf("%d\n",p->data);
return p->data;
}
int Fine_Start()
{
Node *p = head->next;
if(p){
printf("%d\n",p->data);
return p->data;
}
else{
puts("empty data");
}
return 0;
}

void main()
{
init();
push_back(5);
show();
push_back(4);
show();
push_front(2);
show();
push_front(15);
show();
push_front(17);
show();
insert(2,40);
show();
insert_back(15,33);
show();
Find_Number(2);
Fine_idx(1);

}


'Programing > 자료구조' 카테고리의 다른 글

단일연결리스트.cpp  (0) 2016.11.30
단일연결리스트.h  (0) 2016.11.30
이중연결리스트  (0) 2016.11.30
단일 연결리스트 더미노드  (0) 2016.11.30
자료구조  (0) 2016.11.30

+ Recent posts