[자료구조] ep3-3) 다중연결리스트(Multi Linked List)

리스트의 확장: 공유 개념

두 개의 배열을 이용하여 원소 및 그룹 리스트를 각각 구현한다

 

ㅇ다중연결리스트: 양방향 및 다중 방향 검색이 가능한 연결리스트

다중연결리스트의 전체 구조

 

 

 

 

 

활용) 인터넷 쿠폰 사이트 '쿠몬'

• 쿠폰의 총 가입자 수는 NG 명이며, 제공되는 쿠폰의 종류는 NE 종이다. 초기 데이터구조는 가입자의 배열 Groups(크기 NG)와 쿠폰의 배열 Elements(크기 NE)로 구성된다. 어떤 가입자 g가 어떤 쿠폰 e를 구매하면 삽입 알고리즘을 통해 다중연결리스트 내에 (e, g) 노드가 생성된다.

• 쿠폰의 보유는 가입자 당 종별 최대 1 매로 제한한다.

• NG = 5, NE = 4를 사용하고 가입자명은 [A,B,C,D,E]를 쿠폰 명은 [1,2,3,4]를 사용하시오.

• 주함수에서 반복적으로 사용자의 명령코드 a(dd) 또는 r(emove)에 따라 해당 메쏘드를 호출하여 처리하는 방식으로 작성하시오. 추가로 e(traverseShareElements)와 g(traverseShareGroups) 명령코드도 수행하도록 작성하시오.

• 예를 들어, “a 5 B” 명령은 addShare(5,B)를 호출하여 가입자 B가 쿠폰 5를 구매함에 따른 (e, g) 노드 삽입을, “r 2 C” 명령은 removeShare(2, C)를 호출하여 가입자 C가 쿠폰 2를 구매 취소하거나 사용 완료함에 따른 (e, g) 노드 삭제를 각각 수행하며, “e B” 명령은 B가 보유한 쿠폰을 열람하고 “g 2” 명령은 쿠폰 2를 보유한 가입자를 열람한다.

• q(uit) 명령이 입력되면 프로그램은 종료한다.

test case

 

모식도

 

 

 

 

(전체코드)

// 멀티 링크드 리스트로 구현 (요소와 그룹의 리스트를 두 개의 배열을 사용하여 구현 - 리스트의 공유 개념)
// 헤더, 트레일러, 단일 또는 이중 링크드 리스트의 사용은 선택 사항
// 교안 62p, 63p 그림 참고
#include <stdio.h>
#include <stdlib.h>
#pragma warning (disable : 4996)

#define NE 4
#define NG 5

typedef struct NODE {
    int e; // 쿠폰 (요소)
    char g; // 가입자 (그룹)
    struct NODE* next_e; // 다음 쿠폰 (요소)
    struct NODE* next_g; // 다음 가입자 (그룹)
} NODE;

NODE Elements[NE]; // 쿠폰 배열
NODE Groups[NG];   // 가입자 배열

void initShare();
void traverseShareElements(char g);
void traverseShareGroups(int e);
void addShare(int e, char g);
void removeShare(int e, char g);

int main() {
    char cmd;
    int e;
    char g;

    initShare();
    while (1) {
        scanf(" %c", &cmd);
        if (cmd == 'q') {
            break;
        }
        else if (cmd == 'a') {
            scanf(" %d %c", &e, &g);
            addShare(e, g);
            printf("OK\n");
        }
        else if (cmd == 'r') {
            scanf(" %d %c", &e, &g);
            removeShare(e, g);
            printf("OK\n");
        }
        else if (cmd == 'e') {
            scanf(" %c", &g);
            traverseShareElements(g);
        }
        else if (cmd == 'g') {
            scanf(" %d", &e);
            traverseShareGroups(e);
        }
    }

    return 0;
}

void initShare() { // 초기화
    for (int i = 0; i < NE; i++) {
        Elements[i].next_e = NULL;
    }
    for (int i = 0; i < NG; i++) {
        Groups[i].next_g = NULL;
    }
}

void traverseShareElements(char g) {
    // 요소 리스트 탐색
    int f = 0;
    for (int i = 0; i < NE; i++) {
        NODE* cur = &Elements[i];
        while (cur->next_e != NULL) {
            cur = cur->next_e; // NODE Elements[i]의 헤더는 비어있으므로
            if (cur->g == g) {
                printf("%d ", cur->e);
                f = 1;
            }
        }
    }
    if (f == 0) {
        printf("0");
    }
    printf("\n");
}

void traverseShareGroups(int e) {
    // 그룹 리스트 탐색
    int f = 0;
    for (int i = 0; i < NG; i++) {
        NODE* cur = &Groups[i];
        while (cur->next_g != NULL) {
            cur = cur->next_g; // NODE Groups[i]의 헤더는 비어있으므로
            if (cur->e == e) {
                printf("%c ", cur->g);
                f = 1;
            }
        }
    }
    if (f == 0) {
        printf("0");
    }
    printf("\n");
}

void addShare(int e, char g) { // 쿠폰 구독 추가
    NODE* cur;

    NODE* newNode_e = (NODE*)malloc(1 * sizeof(NODE));
    newNode_e->e = e;
    newNode_e->g = g;
    newNode_e->next_e = NULL;
    cur = &Elements[e - 1];
    while (cur->next_e != NULL) {
        cur = cur->next_e;
    }
    cur->next_e = newNode_e;

    NODE* newNode_g = (NODE*)malloc(1 * sizeof(NODE));
    newNode_g->e = e;
    newNode_g->g = g;
    newNode_g->next_g = NULL;
    cur = &Groups[g - 'A'];
    while (cur->next_g != NULL) {
        cur = cur->next_g;
    }
    cur->next_g = newNode_g;
}

void removeShare(int e, char g) { // 쿠폰 구독 제거
    NODE* cur;

    NODE* prev_e = &Elements[e - 1];
    cur = prev_e->next_e;
    while (cur != NULL) {
        if (cur->g == g) {
            prev_e->next_e = cur->next_e; // cur노드 링크 수정
            free(cur);
            break;
        }
        prev_e = cur;
        cur = cur->next_e;
    }

    NODE* prev_g = &Groups[g - 'A'];
    cur = prev_g->next_g;
    while (cur != NULL) {
        if (cur->e == e) {
            prev_g->next_g = cur->next_g;
            free(cur);
            break;
        }
        prev_g = cur;
        cur = cur->next_g;
    }
}

/*
입력)
a 1 C
a 4 A
a 4 E
a 4 D
e A
g 4
a 2 A
e A
r 4 A
g 4
e A
g 1
r 1 C
e C
g 1
g 3

출력)
OK
OK
OK
OK
4
A D E // 출력 순서는 상관 없음
OK
2 4 // 출력 순서는 상관 없음
OK
D E // 출력 순서는 상관 없음
2
C
OK
0
0
0
*/

 

 

 

 

 

 

 

 

 

 

참고 및 출처: 데이터 구조 원리와 응용(국형준교수님), C언어로 쉽게 풀어 쓴 자료구조(천인국)