그룹

각각 상이한 카테고리에 속하는 데이터원소들을 표현하기 위한 자료구조.
리스트ADT를 확장하여 구현.

설계방안 및 구현방법 개요

• 레코드의 리스트
  • 구조체의 1차원배열로 구현
  • 이중연결리스트로 구현
• 부리스트의 리스트
  • 2차원배열로 구현
  • 이중연결리스트의 배열로 구현

레코드의 리스트

레코드 : 몇 개 필드의 복합으로 이루어진 원소

• 방법 : elem, group 2개 필드로 구성된 레코드의 리스트 사용
• 장점 : 단순한 구조이므로 이해와 사용 쉬움
• 단점 : 특정 그룹에 관한 작업을 위해 전체 레코드 순회 필요 = O(n)

작업	구조체 1차원배열	이중연결리스트
init	$O(1)$	$O(1)$
traverseGroup	$O(n)$	$O(n)$
addLastRecord	$O(1)$	$O(1)$
removeGroup	$O(n^2)$	$O(n)$

구현1 : 구조체의 1차원배열

• 방법 : 레코드의 1차원 배열로 구현

• 장점 : 기억장소 낭비 없음 (N만큼의 공간을 언젠가 모두 사용한다고 가정)

• 기본 구성요소

  • 레코드의 배열 V
  • 배열V의 크기 N
  • 레코드 : 원소 elem, 그룹 group, 개수 n

• 그룹 초기화 : O(1)

  Alg initGroup()
    input array V, integer N, integer n
    output an empty array V of size n
  1. n ← 0
  2. return

  #include <stdio.h>
  
  typedef struct _Record {
    char elem;
    char group;
  } Record;
  
  Record* init(int N, int* n){
    *n = 0;
    Record* V = (Record*)malloc(sizeof(Record)*N);
  
    return V;
  }
  
  int main(){
    Record* V;
    int N, n; // 배열크기N, 레코드 개수n
  
    scanf("%d", &N);
    V = init(N, &n);
    /*
    addRecord(V, N, &n, 'a', 'x');
    addRecord(V, N, &n, 'b', 'x');
    addRecord(V, N, &n, 'f', 'y');
    printGroup(V, n, 'x'); // [PRINT : group x ] a b
    printGroup(V, n, 'y'); // [PRINT : group y ] f
  
    removeGroup(V, &n, 'x');
    printGroup(V, n, 'x'); // [PRINT : group x ] 
    printGroup(V, n, 'y'); // [PRINT : group y ] f
    */
    return 0;
  }  

• 그룹 순회 : O(n)

  Alg traverseGroup(g)
    input array V, group g, integer n
    output none
  1. for i ← 0 to n-1
       if(V[i].group == g)
         visit(V[i].elem)
  2. return

  void printGroup(Record* V, int n, char g){
    printf("[PRINT : group %c ] ", g);
    for(int i=0; i<n; i++){
      if(V[i].group == g)
        printf("%c ", V[i].elem);
    }  
    printf("\n");
  }

• 맨 뒤에 레코드 삽입 : O(1)

  Alg addRecord(e, g)
    input array V, group g, element e, integer N, integer n
    output none
  1. if(n==N)
       fullListException()
  2. r ← getRecord()
  3. r.elem ← e
  4. r.group ← g
  5. V[n] ← r
  6. n ← n+1
  7. return

  void addRecord(Record* V, int N, int* n, char e, char g){
    if(*n==N){
      printf("full list exception\n");
      return;
    }
  
    V[*n].elem = e;
    V[*n].group = g;
    *n += 1;
  }  

• 그룹 삭제 : O($n^2$)

  Alg removeGroup()
    input array V, group g, integer N, integer n
    output none
  1. i ← 0
  2. while(i<n)
       if(V[i].group == g)
         remove(i)
         n ← n-1
       else
         i ← i+1
  3. return
  
  Alg remove(i)
    input array V, integer n, integer i
    output none
  1. for k ← i to n-2
       V[i] ← V[i+1]
  2. return

  void removeRecord(Record* V, int n, int i){
    for(int k=i; k<n-1; k++){
      V[k] = V[k+1];
    }
  }
  
  void removeGroup(Record* V, int* n, char g){
    int i = 0;
    while(i<(*n)){
      if(V[i].group == g){
        removeRecord(V, *n, i);
        *n -= 1;
      } else {
        i += 1;
      }
    }
  }  

구현2 : 이중연결리스트

• 방법 : 레코드 노드의 이중연결리스트로 구현

• 장점 : 기억장소 사용 최소화 (배열보다도)

• 기본 구성요소

  • 리스트 L에 대한 헤더H 및 트레일러T
  • 리스트 크기 n

• 그룹 초기화 : O(1)

  Alg initGroup()
    input none
    output an empty doubly linked list L with header H, trailer T
  1. H ← getNode()
  2. T ← getNode()
  3. H.next ← T
  4. T.prev ← H
  5. n ← 0
  6. return

  #include <stdio.h>
  
  typedef struct _Node {
    char elem;
    char group;
    struct _Node* prev;
    struct _Node* next;
  } Node;
  
  Node* getNode(){
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->prev = NULL;
    newNode->next = NULL;
    return newNode;
  }
  
  void putNode(Node* p){
    free(p);
  }
  
  Node* init(Node** H, Node** T, int* n){
    (*H) = getNode();
    (*T) = getNode();
    (*H)->next = (*T);
    (*T)->prev = (*H);
    *n = 0;
    
    return *H;
  }
  
  int main(){
    Node* H;
    Node* T;
    int n;
    
    Node* L = init(&H, &T, &n);
    /*
    addNode(T, &n, 'a', 'x');
    addNode(T, &n, 'b', 'x');
    addNode(T, &n, 'c', 'x');
    addNode(T, &n, 'f', 'y');
    addNode(T, &n, 'g', 'y');
    printGroup(L, 'x'); // [PRINT Group x] a b c 
    printGroup(L, 'y'); // [PRINT Group y] f g 
  
    removeGroup(L, &n, 'x');
    printGroup(L, 'x'); // [PRINT Group x]
    printGroup(L, 'y'); // [PRINT Group y] f g 
    removeGroup(L, &n, 'y');
    printGroup(L, 'x'); // [PRINT Group x]
    printGroup(L, 'y'); // [PRINT Group y]
    */
    return 0;
  }

• 그룹 순회 : O(n)

  Alg traverseGroup(g)
    input list L, group g
    output none
  1. p ← H.next
  2. while(p != T)
       if(p.group == g)
         visit(p.elem)
       p ← p.next
  3. return

  Node* printGroup(Node* H, char g){
    Node* p = H->next;
  
    printf("[PRINT Group %c] ", g);
    while(p->next != NULL){
      if(p->group == g)
        printf("%c ", p->elem);
      p = p->next;
    }
    printf("\n");
  }

• 맨 뒤에 레코드 노드 삽입 : O(1)

  Alg addNode()
    input list L, element e, group g
    output new node q
  1. p ← T
  2. q ← getNode()
     q.elem = e
     q.group = g
     q.prev = p.prev
     q.next = p
  3. (p.prev).next = q
     p.prev = q
  4. n ← n+1
  5. return

  void addNode(Node* T, int* n, char e, char g){
    Node* newNode = getNode();
    newNode->elem = e;
    newNode->group = g;
    newNode->next = T;
    newNode->prev = T->prev;
    (T->prev)->next = newNode;
    T->prev = newNode;
  
    *n += 1;
  }

• 그룹 삭제 : O(n)

  Alg removeGroup(g)
    input list L, group g
    output none
  1. p ← H.next
  2. while(p!=T)
       next ← p.next
       if(p.group==g)
         removeNode(p)
         n ← n-1
       p ← next
  3. return
  
  Alg removeNode()
    input list L, node p 
    output
  1. (p.next).prev = p.prev
     (p.prev).next = p.next
  2. putNode(p)
  3. return

  void removeNode(Node* p){
    (p->prev)->next = p->next;
    (p->next)->prev = p->prev;
    putNode(p);
  }
  void removeGroup(Node* H, int* n, char g){
    Node* p = H;
    while(p->next != NULL){
      Node* next = p->next;
      if(p->group == g){
        removeNode(p);
        *n -= 1;
      }
      p = next;
    }
  }

부리스트의 리스트

• 방법 : 리스트로 그룹 표현. 각 리스트는 원소를 표현하는 부리스트를 가짐.
  • 리스트 = 그룹
  • 부리스트 = 원소들
• 장점 : 특정 그룹관련 격리처리 가능 (특정 그룹원소만 바로 골라볼 수 있다.)

작업	2차원배열	이중연결리스트의 배열
initGroup	$O(M)$	$O(M)$
traverseGroup	$O(n[g])$	$O(│g│)$
addLastElement/Node	$O(1)$	$O(1)$
removeGroup	$O(1)$	$O(│g│)$

구현1 : 2차원 배열

• 방법 : $M×N$ 2차원 배열로 구현

  • M : 리스트 - 그룹 개수
  • N : 부리스트 - 한 그룹이 최대로 가질 수 있는 원소 개수

• 단점 : 기억장소 낭비 우려 (N이 원소가 가장 많은 그룹의 크기를 커버해야함)

• 기본 구성요소

  • $M×N$크기의 2차원 배열 V : 그룹과 원소 표현
  • $M×1$ 크기의 1차원 배열 n : 원소 개수 관리

• 그룹 초기화 : O(1)

  Alg initGroup()
    input array V, array n, integer M, integer N
    output array n of size M
  1. for i ← 1 to M-1
       n[i] ← 0
  2. return

  #include <stdio.h>
  
  void init(char*** V, int** n, int M, int N){
    *V = (char**)malloc(sizeof(char*)*M);
    *n = (int*)malloc(sizeof(int)*M);
    for(int i=0; i<M; i++){
      (*V)[i] = (char*)malloc(sizeof(char)*N);
      (*n)[i] = 0;
    }
  }
  
  int main(){
    char** V;
    int* n;
    int M, N; // The Number of : list(group) M, sublist(elem) N
    M = 3;
    N = 10;
    
    init(&V, &n, M, N);
    /*
    addLastElement(V, n, N, 0, 'a');
    addLastElement(V, n, N, 0, 'b');
    addLastElement(V, n, N, 0, 'c');
    addLastElement(V, n, N, 1, 'f');
    addLastElement(V, n, N, 2, 'x');
    addLastElement(V, n, N, 2, 'y');
    printGroup(V, n, 0);
    printGroup(V, n, 1);
    printGroup(V, n, 2);
  
    removeGroup(n, 0);
    printf("\nremoved group 0\n");
    printAllGroup(V, n, M);
    
    removeGroup(n, 1);
    printf("\nremoved group 1\n");
    printAllGroup(V, n, M);
    
    removeGroup(n, 2);
    printf("\nremoved group 2\n");
    printAllGroup(V, n, M);
    */
    return 0;
  }

• 그룹 순회 : O( n[g] )

  Alg traverseGroup(g)
    input array V, array n, group g
    output none
  1. for i ← 0 to n[g]-1
       visit(V[g, i])
  2. return

  void printGroup(char **V, int* n, int g){
    char* sublist = V[g];
    int sublistNum = n[g];
    
    printf("[Group %d] ", g);
    for(int i=0; i<sublistNum; i++){
      printf("%c ", sublist[i]);
    }
    printf("\n");
  }
  
  void printAllGroup(char **V, int* n, int M){
    for(int i=0; i<M; i++){
      printGroup(V, n, i);
    }
  }

• 맨 뒤에 원소 추가 : O(1)

  Alg addLastElement(g, e)
    input array V, array n, integer N, group g, element e
    output new element
  1. if (n[g]>=N)
       fullListException()
  2. V[g, n[g]] ← e
  3. return

  void addLastElement(char **V, int* n, int N, int g, char e){
    char* sublist = V[g];
    int sublistNum = n[g];
  
    if(sublistNum>=N){
      printf("full list exception\n");
      return;
    }
  
    sublist[sublistNum] = e;
    n[g]++; // ref of sublistNum
  }

• 그룹 삭제 : O(1)

  Alg removeGroup(g)
    input array n, group g
    output none
  1. n[g] ← 0
  2. return

  void removeGroup(int* n, int g){
    n[g] = 0; // ref of sublistNum
  }

구현2 : 이중연결리스트의 배열

• 방법 : 헤더/트레일러를 가리키는 1차원배열과, 그 배열의 원소에 각각 묶인 이중연결리스트로 구현

  • 1차원배열 H : 리스트 - 그룹 표현, 해당 그룹의 이중연결리스트 헤더를 가리킴
  • 1차원배열 T : 리스트 - 그룹 표현, 해당 그룹의 이중연결리스트 트레일러를 가리킴
  • 이중연결리스트 : 부리스트 - 원소 표현, H[g]와 T[g]는 각각 이 부리스트의 헤더, 트레일러로 연결됨.

• 장점 : 기억장소 사용 최소화

• 기본 구성요소

  • 그룹의 개수 M = $|g|$
  • $M$크기의 1차원배열 H : 해당 그룹 이중연결리스트의 헤더를 가리킴
  • $M$크기의 1차원배열 T : 해당 그룹 이중연결리스트의 트레일러를 가리킴
  • $M$개의 이중연결리스트 : 각 그룹별 원소를 담고 있음.

• 그룹 초기화 : O(1)

  Alg initGroup()
    input array H, array T, integer M
    output array H, array T of pointers to header/trailer
  1. for i ← 0 to M-1
       h ← getNode()
       t ← getNode()
       h.next ← t		{ 헤더 }
       t.prev ← h
       H[i] ← h		{ 헤더를 가리키는 배열 H }
       T[i] ← t

  #include <stdio.h>
  
  typedef struct _Node{
    char elem;
    struct _Node* prev;
    struct _Node* next;
  } Node;
  
  Node* getNode(){
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->prev = NULL;
    newNode->next = NULL;
  
    return newNode;
  }
  
  void putNode(Node* p){
    free(p);
  }
  
  int main(){
    Node** H;
    Node** T;
    int M = 3;
    init(&H, &T, M);
    /*
    addLastNode(T, 0, 'A');
    addLastNode(T, 1, 'F');
    addLastNode(T, 1, 'G');
    addLastNode(T, 2, 'X');
    addLastNode(T, 2, 'Y');
    addLastNode(T, 2, 'Z');
    printGroup(H, 0);
    printGroup(H, 1);
    printGroup(H, 2);
  
    printf("\nremoved group 0\n");
    removeGroup(H, T, 0);
    printAllGroup(H, M);
    
    printf("\nremoved group 1\n");
    removeGroup(H, T, 1);
    printAllGroup(H, M);
    
    printf("\nremoved group 2\n");
    removeGroup(H, T, 2);
    printAllGroup(H, M);
    */
    return 0;
  }

• 그룹 순회 : O($|g|$)

  Alg traverseGroup(g)
    input array H, array T, group g
    output none
  1. p ← H[g].next
  2. while(p!=T[g])
       visit(p.elem)
       p ← p.next
  3. return

  void printGroup(Node** H, int g){
    Node* p = H[g]->next;
  
    printf("[Group %d] ", g);
    while(p->next != NULL){
      printf("%c ", p->elem);
      p = p->next;
    }
    printf("\n");
  }
  
  void printAllGroup(Node** H, int M){
    for(int i=0; i<M; i++){
      printGroup(H, i);
    }
  }

• 맨 뒤에 원소 추가 : O(1)

  Alg addLastNode(g, e)
    input array T, group g, element e
    output new node of group g
  1. p ← T[g]
  2. q ← getNode()
     q.elem ← e
     q.prev ← p.prev
     q.next ← p
  3. (p.prev).next ← q
     p.prev ← q
  4. return

  void addLastNode(Node** T, int g, char e){
    Node* trailer = T[g];
    Node* newNode = getNode();
    newNode->elem = e;
    newNode->next = trailer;
    newNode->prev = trailer->prev;
    (trailer->prev)->next = newNode;
    trailer->prev = newNode;
  }

• 그룹 삭제 : O($|g|$)

  Alg removeGroup()
    input array H, array T, group g
    output none
  1. removeAll(H[g], T[g])
  2. return
  
  Alg removeAll(h, t)
    input header h, trailer t
  1. p ← h.next
  2. while(p!=t)
       next ← p.next
       removeNode(p)
       p ← next
       
  Alg removeNode(p)
    input node p
    output none
  1. (p.next).prev ← p.prev
     (p.prev).next ← p.next
  2. putNode(p)
  3. return

  void removeNode(Node* p){
    (p->prev)->next = p->next;
    (p->next)->prev = p->prev;
    putNode(p);
  }
  
  void removeAll(Node* header, Node* trailer){
    Node* p = header->next;
    while(p->next != NULL){
      Node* next = p->next;
      removeNode(p);
      p = next;
    }
  }
  
  void removeGroup(Node** H, Node** T, int g){
    removeAll(H[g], T[g]);
  }