자료구조 06 : 리스트ADT 확장 - 공유

LeeWonjin·2022년 4월 25일

[학부]자료구조/알고리즘

목록 보기

6/18

상이한 그룹에 의해 공유되는 데이터 원소들을 표현하기 위한 자료구조
리스트ADT를 확장하여 구현

공유의 예시

그룹 x y와 원소 a b c가 있다고 할 때,
아래와 같이 한 원소가 2개이상의 그룹에 속한 경우를 다룬다.

원소	속한 그룹
a	x, y
b	y
c	x, y

설계방안 및 구현방법 개요

레코드의 리스트
- 구조체의 1차원 배열
- 이중연결리스트
포인터의 리스트
- 그룹별 1차원 배열
- 그룹별 이중연결리스트
다중리스트
- 2차원 배열
- 다중연결리스트

레코드의 리스트

방법 : elem, group필드로 구성된 레코드의 리스트 사용
단점 : 특정 원소 및 특정 그룹 관련 작업을 위해 전체 순회 필요 (특정 원소가 속한 그룹, 특정 그룹이 갖고있는 원소를 바로 찾아볼 수 없음)

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

구조체의 1차원 배열

방법 : 레코드를 구조체로 표현. 이 구조체의 1차원배열로 구현
장점 : 기억장소 낭비 없음 (메모리를 N만큼 모두 사용할 예정이라면)
기본 구성요소
- 크기 N의 배열 V
- elem, group필드를 갖는 n개의 구조체
초기화

#include <stdio.h>

typedef struct _Record {
  char elem;
  int group;
} Record;

Record* init(int N, int* n){
  Record* arr = (Record*)malloc(sizeof(Record)*N);
  *n = 0;

  return arr;
}

int main(){
  int N = 10;
  int n;
  Record* V = init(N, &n);  

  addRecord(V, N, &n, 'a', 0);
  addRecord(V, N, &n, 'a', 1);
  addRecord(V, N, &n, 'b', 0);
  addRecord(V, N, &n, 'c', 0);
  addRecord(V, N, &n, 'c', 1);
  addRecord(V, N, &n, 'c', 2);
  addRecord(V, N, &n, 'd', 2);
  addRecord(V, N, &n, 'e', 2);
  printGroupsOfElement(V, n, 'a');
  printGroupsOfElement(V, n, 'b');
  printGroupsOfElement(V, n, 'c');
  printGroupsOfElement(V, n, 'd');
  printGroupsOfElement(V, n, 'e');
  printElementsOfGroup(V, n, 0);
  printElementsOfGroup(V, n, 1);
  printElementsOfGroup(V, n, 2);

  printf("----------------------\n");
  removeGroup(V, &n, 0);
  removeGroup(V, &n, 2);
  printElementsOfGroup(V, n, 0);
  printElementsOfGroup(V, n, 1);
  printElementsOfGroup(V, n, 2);
	
  return 0;
}

그룹의 원소들, 원소의 그룹들 순회

void printElementsOfGroup(Record* V, int n, int group){
  printf("[Elements of a Group - %d] ", group);  
  for(int i=0; i<n; i++){
    if(V[i].group == group)
      printf("%c ", V[i].elem);
  }
  printf("\n");
}

void printGroupsOfElement(Record* V, int n, char elem){
  printf("[Groups of a Element - %c] ", elem);
  for(int i=0; i<n; i++){
    if(V[i].elem == elem)
      printf("%d ", V[i].group);
  }
  printf("\n");
}

레코드 추가

void addRecord(Record* V, int N, int* n, char elem, int group){
  if((*n)>=N){
    printf("Full List Exception\n");
    return;
  }
  V[*n].elem = elem;
  V[*n].group = group;
  *n += 1;
}

그룹 삭제

void removeRecord(Record* V, int n, int idx){
  for(int i=idx; i<n-1; i++){
    V[i] = V[i+1];
  }
}

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

이중연결리스트

방법 : 레코드 노드를 갖는 이중연결리스트로 구현
장점 : 기억장소 낭비 최소화
기본 구성요소
- 헤더H와 트레일러T를 갖는 이중연결리스트 L
초기화

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

typedef struct _Node {
	char elem;
	int group;
	struct _Node* prev;
	struct _Node* next;
} Node;

Node* getNode() {
	Node* p = (Node*)malloc(sizeof(Node));
	p->prev = NULL;
	p->next = NULL;

	return p;
}

void putNode(Node* p) {
	free(p);
}

void init(Node** H, Node** T) {
	*H = getNode();
	*T = getNode();
	(*H)->next = *T;
	(*T)->prev = *H;
}

int main() {
	Node* H;
	Node* T;
	init(&H, &T);

	addLastNode(T, 'a', 0); // element 'a' of group 0
	addLastNode(T, 'a', 1);
	addLastNode(T, 'a', 2);
	addLastNode(T, 'b', 1);
	addLastNode(T, 'b', 2);
	addLastNode(T, 'c', 1);
	printGroupsOfElement(H, 'a');
	printGroupsOfElement(H, 'b');
	printGroupsOfElement(H, 'c');
	printElementsOfGroup(H, 0);
	printElementsOfGroup(H, 1);
	printElementsOfGroup(H, 2);

	printf("-------\n");
	removeGroup(H, 0);
	removeGroup(H, 2);
	printElementsOfGroup(H, 0);
	printElementsOfGroup(H, 1);
	printElementsOfGroup(H, 2);

	return 0;
}

그룹 / 원소 순회

void printGroupsOfElement(Node* H, char elem) {
	Node* p = H->next;
	printf("[Groups of a Element %c] ", elem);
	while (p->next != NULL) {
		if (p->elem == elem)
			printf("%d ", p->group);
		p = p->next;
	}
	printf("\n");
}

void printElementsOfGroup(Node* H, int group) {
	Node* p = H->next;
	printf("[Elements of a Group %d] ", group);
	while (p->next != NULL) {
		if (p->group == group)
			printf("%c ", p->elem);
		p = p->next;
	}
	printf("\n");
}

노드 추가

void addLastNode(Node* T, char elem, int group) {
	Node* n = (Node*)malloc(sizeof(Node));
	n->elem = elem;
	n->group = group;
	n->next = T;
	n->prev = T->prev;
	(T->prev)->next = n;
	T->prev = n;
}

그룹 삭제

void removeNode(Node* p) {
	(p->next)->prev = p->prev;
	(p->prev)->next = p->next;
	putNode(p);
}

void removeGroup(Node* H, int group) {
	Node* p = H->next;
	while (p->next != NULL) {
		Node* next = p->next;
		if (p->group == group) 
			removeNode(p);
		p = next;
	}
}

포인터의 리스트

방법 : 원소들은 별도의 메모리에 저장, 각 그룹별로 메모리에 저장된 원소를 참조하는 포인터의 리스트를 가짐.
장점 : 단순하고 기억장소 사용 최소화 가능
단점 : 특정 원소 관련작업의 격리 처리 불가 (어떤 원소가 속한 그룹을 바로 찾을 수 없다.)

작업	1차원 포인터배열	포인터의 이중연결리스트
init	$O(1)$	$O(1)$
traverse	$O(n)$	$O(n)$
addLastRecord	$O(1)$	$O(1)$
removeGroup	$O(1)$	$O(n)$

그룹별 1차원 포인터배열

방법 : 각 그룹을 그룹에 속한 원소를 참조하는 포인터의 배열로 구현한다.
초기화

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

typedef struct _Group {
	char groupName;
	int num;
	char** arr;
} Group;

Group* init(char groupName, int N) {
	Group* g = (Group*)malloc(sizeof(Group));

	g->groupName = groupName;
	g->num = 0;
	g->arr = (char**)malloc(sizeof(char*) * N);

	return g;
}

int main() {
	char elements[] = {'a', 'b', 'c', 'd', 'e', 'f', 'g'};
	int N = 5;
	Group* x = init('x', N); // group name 'x'
	Group* y = init('y', N);
	Group* z = init('z', N);

	addLastRecord(x, N, &elements[0]);
	addLastRecord(x, N, &elements[1]);
	addLastRecord(x, N, &elements[2]);
	addLastRecord(y, N, &elements[2]);
	addLastRecord(y, N, &elements[3]);
	addLastRecord(z, N, &elements[1]);
	addLastRecord(z, N, &elements[2]);
	addLastRecord(z, N, &elements[4]);
	printElementsOfGroup(x);
	printElementsOfGroup(y);
	printElementsOfGroup(z);

	printf("-------\n");
	removeGroup(x);
	removeGroup(y);
	printElementsOfGroup(x);
	printElementsOfGroup(y);
	printElementsOfGroup(z);

	return 0;
}

순회

void printElementsOfGroup(Group* g) {
	char** arr = (g->arr);

	printf("[Elements of a Group %d] ", g->groupName);
	for (int i = 0; i < g->num; i++) {
		printf("%c ", *(arr[i]));
	}
	printf("\n");
}

그룹에 원소 추가

void addLastRecord(Group* g, int N, char* elem) {
	if (g->num >= N) {
		printf("full list exception\n");
		return;
	}

	(g->arr)[g->num] = elem;
	(g->num)++;
}

그룹 삭제

void removeGroup(Group* g) {
	g->num = 0;
}

그룹별 이중연결리스트

방법 : 각 그룹을 그룹에 속한 원소를 참조하는 포인터 노드의 이중연결리스트로 구현한다.
초기화

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

typedef struct _Node {
	char* elem;
	struct _Node* prev;
	struct _Node* next;
} Node;

typedef struct _Group {
	char groupName;
	struct _Node* H;
	struct _Node* T;
} Group;

Node* getNode() {
	Node* p = (Node*)malloc(sizeof(Node));
	p->prev = NULL;
	p->next = NULL;

	return p;
}

void putNode(Node* p) {
	free(p);
}

Group init(char groupName) {
	Group g;
	g.groupName = groupName;
	g.H = getNode();
	g.T = getNode();
	(g.H)->next = (g.T);
	(g.T)->prev = (g.H);

	return g;
}

int main() {
	char elements[] = {'a', 'b', 'c', 'd', 'e', 'f', 'g'};
	Group x = init('x'); // group name 'x'
	Group y = init('y'); 
	Group z = init('z');

	addLastNode(x, &elements[0]);
	addLastNode(x, &elements[1]);
	addLastNode(x, &elements[2]);
	addLastNode(y, &elements[2]);
	addLastNode(y, &elements[3]);
	addLastNode(z, &elements[1]);
	addLastNode(z, &elements[2]);
	addLastNode(z, &elements[4]);
	printElementsOfGroup(x);
	printElementsOfGroup(y);
	printElementsOfGroup(z);

	printf("-------\n");
	removeGroup(x);
	removeGroup(y);
	printElementsOfGroup(x);
	printElementsOfGroup(y);
	printElementsOfGroup(z);

	return 0;
}

순회

void printElementsOfGroup(Group g) {
	Node* p = (g.H)->next;

	printf("[Elements of a Group %d] ", g.groupName);
	while (p->next != NULL) {
		printf("%c ", *(p->elem));
		p = p->next;
	}
	printf("\n");
}

그룹에 원소 추가

void addLastNode(Group g, char* elem) {
	Node* T = g.T;

	Node* n = (Node*)malloc(sizeof(Node));
	n->elem = elem;
	n->next = T;
	n->prev = T->prev;
	(T->prev)->next = n;
	T->prev = n;
}

그룹 삭제

void removeNode(Node* p) {
	(p->next)->prev = p->prev;
	(p->prev)->next = p->next;
	putNode(p);
}

void removeGroup(Group g) {
	Node* p = (g.H)->next;
	while (p->next != NULL) {
		Node* next = p->next;
		removeNode(p);
		p = next;
	}
}

다중리스트

다중리스트 : 리스트가 상호 교차하는 형태

방법 : 원소 리스트와 그룹 리스트의 교차점으로, 원소가 그룹에 속했는지 여부를 표현
장점 : 특정 원소 및 특정 그룹 작업 격리처리 가능
- 이 원소가 어떤 그룹들에 속했는지 --> 바로 알 수 있다.
- 이 그룹에 어떤 원소들이 속해있는지 --> 바로 알 수 있다.

2차원 배열

방법 : 행이 원소를, 열이 그룹을 의미하는 2차원 논리배열로 구현
단점 : 원소-그룹 관계가 희소한 경우 기억장소 낭비 우려
기본 구성요소
- $M×N$ 크기의 배열 V
초기화

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

bool** init(int M, int N) {
	bool** arr = (bool**)calloc(M, sizeof(bool*));
	for (int i = 0; i < M; i++)
		arr[i] = (bool*)calloc(N, sizeof(bool));

	return arr;
}

int main() {
	int M = 4; // 행 (원소의 갯수) : 원소의 종류는 0,1,2,3 = 4가지
	int N = 3; // 열 (그룹의 갯수) : 그룹의 종류는 0,1,2 = 3가지
	bool** V = init(M, N);
	printV(V, M, N);

	addRelation(V, 0, 0);
	addRelation(V, 0, 1);
	addRelation(V, 0, 2);
	addRelation(V, 1, 1);
	addRelation(V, 2, 0);
	addRelation(V, 2, 1);
	addRelation(V, 3, 2);
	printV(V, M, N);

	removeGroup(V, M, 0);
	printV(V, M, N);
	removeGroup(V, M, 1);
	printV(V, M, N);
	removeGroup(V, M, 2);
	printV(V, M, N);

	return 0;
}

그룹 순회

void printElementsOfGroup(bool** V, int M, int group) {
	printf("[Elements of a Group %d] ", group);
	for (int i = 0; i < M; i++) {
		if (V[i][group] == true)
			printf("%d ", i);
	}
	printf("\n");
}

void printGroupsOfElement(bool** V, int N, int elem) {
	printf("[Groups of a Element %d] ", elem);
	for (int i = 0; i < N; i++) {
		if (V[elem][i] == true)
			printf("%d ", i);
	}
	printf("\n");
}

void printV(bool** V, int M, int N) {
	printf("==================\n[ Array V ]\ngroup\t");
	for (int i = 0; i < N; i++)
		printf("%d ", i);
	printf("\n\nelem\n");

	for (int i = 0; i < M; i++) {
		printf("%d\t", i);
		for (int j = 0; j < N; j++) {
			int value = (V[i][j] == true) ? 1 : 0;
			printf("%d ", value);
		}
		printf("\n");
	}
	printf("==================\n");
}

원소-그룹 관계 추가

void addRelation(bool** V, int elem, int group) {
	V[elem][group] = true;
}

그룹 삭제

void removeRelation(bool** V, int elem, int group) {
	V[elem][group] = false;
}

void removeGroup(bool** V, int M, int group) {
	for (int i = 0; i < M; i++)
		removeRelation(V, i, group);
}

다중연결리스트

방법
- 리스트 헤더를 가리키는 포인터의 1차원배열 2개를 선언. (하나는 원소 표현을 위해, 하나는 그룹 표현을 위해)
- 원소배열의 요소 e와 그룹배열의 요소 g가 관계가 있다면
  ---> 리스트 e와 g의 교차점에 노드를 생성 (다중연결리스트)
장점 : 기억장소 낭비 최소화
기본 구성요소
- 헤더 H를 갖는 다중연결리스트 L
- 크기 NE의 1차원배열 E
- 크기 NG의 1차원배열 G
초기화

Alg initShare()
  input array E, array G, integer NE, integer NG
  output empty multilinked 
1. for i ← 0 to NE-1
     H ← getNode()
     H.nextGroup ← H		{ 헤더노드의 초기 next는 자기자신 }
     E[i].header ← H
     
2. for i ← 0 to NG-1
     H ← getNode()
     H.nextElement ← H
     G[i].header ← H
3. reutrn

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

typedef struct _Node {
	struct _Node* nextElement;
	struct _Node* nextGroup;
} Node;

typedef struct _Item {
	Node* header;
	char name;
} Item;

Node* getNode() {
	Node* n = (Node*)malloc(sizeof(Node));
	n->nextElement = NULL;
	n->nextGroup = NULL;
	return n;
}

void putNode(Node* p) {
	free(p);
}

void init(Item** E, Item** G, int NE, int NG, char* nameE, char* nameG) {
	(*E) = (Item*)malloc(sizeof(Item) * NE);
	(*G) = (Item*)malloc(sizeof(Item) * NG);

	for (int i = 0; i < NE; i++) {
		Node* p = getNode();
		p->nextGroup = p;
		(*E)[i].header = p;
		(*E)[i].name = nameE[i];
	}
	for (int i = 0; i < NG; i++) {
		Node* p = getNode();
		p->nextElement = p;
		(*G)[i].header = p;
		(*G)[i].name = nameG[i];
	}
}

int getIndexByName(Item* arr, int N, char name) {
	for (int i = 0; i < N; i++) {
		if (arr[i].name == name)
			return i;
	}
	return -1;
}

int main() {
	Item *E, *G;
	int NE = 4, NG = 3;
	char nameE[] = { 'a', 'b', 'c', 'd' };
	char nameG[] = { 'X', 'Y', 'Z' };
	init(&E, &G, NE, NG, nameE, nameG);
	
	addShare(E, G, NE, NG, 'a', 'X');
	addShare(E, G, NE, NG, 'a', 'Y');
	addShare(E, G, NE, NG, 'a', 'Z');
	addShare(E, G, NE, NG, 'b', 'X');
	addShare(E, G, NE, NG, 'b', 'Z');
	addShare(E, G, NE, NG, 'c', 'Y');
	addShare(E, G, NE, NG, 'd', 'X');
	
	printShareElement(E, G, NE, NG, 'X');
	printShareElement(E, G, NE, NG, 'Y');
	printShareElement(E, G, NE, NG, 'Z');

  removeGroup(G, NG, 'Y');
	printShareElement(E, G, NE, NG, 'X');
	printShareElement(E, G, NE, NG, 'Y');
	printShareElement(E, G, NE, NG, 'Z');
	return 0;
}

순회

Alg traverseShareElement(g)
  input array G, group g
  output none
1. H ← G[g].header
2. p ← H.nextElement
3. while(p!=H)
     visit(p)
     p ← p.nextElement
4. return

Alg traverseShareGroup(e)
  input array E, element e
  output none
1. H ← E[e].header
2. p ← H.nextGroup
3. while(p!=H)
     visit(p)
     p ← p.nextGroup
4. return

void printShareElement(Item* E, Item* G, int NE, int NG, char group) {
	int idx = getIndexByName(G, NG, group);
	Node* HG = G[idx].header;
	Node* p = HG->nextElement;
  
	printf("[ Elements of a Group %c ] ", group);
	while (p != HG) {
		char elem = getElementName(E, NE, p);
		printf("%c ", elem);
		p = p->nextElement;
	}
	printf("\n");
}

void printShareGroup(Item* E, Item* G, int NE, int NG, char elem) {
	int idx = getIndexByName(E, NE, elem);
	Node* HE = E[idx].header;

	Node* p = HE;
	printf("[ Groups of a Element %c ] ", elem);
	while (p != HE) {
		char group = getGroupName(G, NG, p);
		printf("%c ", group);
		p = p->nextGroup;
	}
	printf("\n");
}

노드의 그룹명/원소명 얻기

Alg getGroupName(p)
  input array G, node p, integer NG
  output group name
1. q ← p
2. while(q!=H)
     q ← q.nextElment
3. for i ← 0 to NG-1
     if(G[i]==p)
       groupname ← p.name
       break
4. return groupname

Alg getElementName(p)
  input array E, node p, integer NE
  output element name
1. q ← p
2. while(q!=H)
     q ← q.nextGroup
3. for i ← 0 to NE-1
     if(E[i]==p)
       elemname ← p.name
       break
4. return elemname

char getElementName(Item* E, int NE, Node* p) {
	Node* q = p->nextGroup;
	while (q->nextElement != NULL){
		q = q->nextGroup; // find header node
  }
	for (int i = 0; i < NE; i++) {
		if (E[i].header == q){
			return E[i].name;
    }
	}

	return 0;
}

char getGroupName(Item* G, int NG, Node* p) {
	Node* q = p->nextElement;
	while (q->nextGroup != NULL)
		q = q->nextElement; // find header node

	for (int i = 0; i < NG; i++) {
		if (G[i].header == q)
			return G[i].name;
	}

	return 0;
}

관계 삽입

Alg addFirstShare(e, g)
  input Array E, array G, element e, group g
  output none
1. HE ← E[e].header
   HG ← G[g].header
2. p ← getNode()
   p.nextGroup ← HE.nextGroup
   p.nextElement ← HG.nextElement
3. HE.nextGroup ← p
   HG.nextElement ← p
4. return

void addShare(Item* E, Item* G, int NE, int NG, char elem, char group) {
	int idxG = getIndexByName(G, NG, group);
	int idxE = getIndexByName(E, NE, elem);
	Node* HG = G[idxG].header;
	Node* HE = E[idxE].header;

	Node* n = getNode();
	n->nextElement = HG->nextElement;
	n->nextGroup = HE->nextGroup;
	HG->nextElement = n;
	HE->nextGroup = n;
}

그룹 삭제

Alg removeGroup(g)
  input array E, array G, group g
  output none
1. HG ← G[g].header
2. p ← HG.nextElement
3. while(p!=HG)
	 nextG ← p.nextGroup
     q ← nextG
     while(q.nextGroup!=p)
       q ← q.nextGroup
     q.nextGroup ← nextG
     
     nextE ← p.nextElement
     q ← nextE
     while(q.nextElement!=p)
       q ← q.nextElement
     q.nextElement ← nextE
     
     putNode(p)
4. return

void removeNode(Node* target) {
	Node* p;
	
	Node* nextE = target->nextElement;
	p = nextE;
	while (p->nextElement != target)
		p = p->nextElement;
	p->nextElement = nextE;
  
	Node* nextG = target->nextGroup;
	p = nextG;
	while (p->nextGroup != target)
		p = p->nextGroup;
	p->nextGroup = nextG;
  
	putNode(target);
}

void removeGroup(Item* G, int NG, int group) {
	int idx = getIndexByName(G, NG, group);
	Node* HG = G[idx].header;
	Node* p = HG->nextElement;

	while (p != HG) {
    Node* next = p->nextElement;
	  removeNode(p);
    p = next;
	}
}