자료구조 6(연결리스트)

---

- 리스트

항목들이 차례대로 저장되어 있는 자료구조

---

- 순서리스트

특정 기준으로 순서가 유지되는 객체들의 순서 집합

---

- 순차리스트

순서리스트 중 컴퓨터 메모리에 저장할 때 객체들의 논리 순서와 메모리의 실제 저장 순서를 일치시키는 방법 → 원소들의 순서대로 연속 저장되므로 시작 위치와 원소의 크기를 알면 특정 원소의 위치를 알 수 있다. (배열을 사용하는 리스트)

---

- 리스트의 추상자료형

create : 리스트 생성

insert : 리스트에 데이터 입력

delete : 리스트에 데이터 삭제

get_length: 리스트의 길이 반환

is_empty : 리스트가 공백상태인지 확인

is_full : 리스트가 포화상태인지 확인

print_list : 리스트를 출력

---

- 배열로 구현된 간단한 순차리스트

#include <stdio.h>
#define MAX 10


typedef struct linear_list{
    int data[MAX];
    int length;
}List;

void insert_data(List *A, int i, int data) {    //i번째 배열에 데이터를 넣는 함수
    int j;
    for(j = A->length; j > i; j--)
        A->data[j+1] = A->data[j];
    
    A->data[i] = data;
    A->length++;
}

void insert_data_L(List *A, int data) {    //마지막 배열에 데이터를 넣는 함수
    A->data[++(A->length)] = data;
}

int delete_data(List *A, int i) {    //i번째 원소를 삭제하는 함수
    int j;
    int tmp;
    tmp = A->data[i];
    
    for(j = i; j < A->length; j++)
        A->data[j] = A->data[j+1];
    
    A->length--;
    return tmp;
}

int main(void) {
    List A;
    A.length = -1;    //순차리스트를 초기화
    int i;
    
    insert_data_L(&A, 123);
    insert_data_L(&A, 456);
    
    for(i = 0; i <= A.length; i++)
        printf("[%d] ", A.data[i]);
    printf("\n");
    
    printf("delete_data(A) : [%d]\n", delete_data(&A, 1));
    
    for(i = 0; i <= A.length; i++)
        printf("[%d] ", A.data[i]);
    printf("\n");
}

실행결과

---

- 연결리스트

물리적으로 흩어져 있는 자료들을 서로 연결하여 하나로 묶는 방법을 연결리스트라고 하며 연결선은 포인터로 구현을 한다.

---

- 단순 연결리스트의 구현

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

typedef struct linked_list {    //노드의 구현
    int data;
    struct linked_list *link;
}Node;

void insert_data_first(Node *head, int data) {    //헤드노드 바로 뒤에 노드를 추가하는 함수
    Node *new_node = (Node *)malloc(sizeof(Node));
    new_node->data = data;
    
    if(head->link == NULL) {    //첫번째 노드를 추가할때
        head->link = new_node;
        new_node->link = NULL;
    }
    else {
        new_node->link = head->link;
        head->link = new_node;
    }
}

int delete_node_first(Node *head) {    //첫번째 노드를 삭제하는 함수
    int remove;
    Node *tmp;
    tmp = head->link;
    remove = tmp->data;
    head->link = tmp->link;
    free(tmp);
    return remove;
}

void print_node(Node *head) {    //전체노드를 출력하는 함수
    Node *p;
    
    for(p = head->link; p != NULL; p = p->link)
        printf("[%d]-> ", p->data);
    printf("\n");
}

int main(void) {
    Node *head = (Node *)malloc(sizeof(Node));
    head->link = NULL;
    
    insert_data_first(head, 1);
    insert_data_first(head, 2);
    insert_data_first(head, 3);
    insert_data_first(head, 4);
    insert_data_first(head, 5);
    
    print_node(head);
    printf("\ndelete_node_first : [%d]\n\n", delete_node_first(head));
    print_node(head);
    
    
    free(head);
    return 0;
}

실행화면

---

- 이중 연결리스트의 구현

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

typedef struct double_linked_list {
    int data;
    struct double_linked_list *llink;    //왼쪽노드와 연결된 링크
    struct double_linked_list *rlink;    //오른쪽노드와 연결된 링크
}Node;

void insert_data(Node **dlist, Node *now, int data) {    //now뒤에 새로운 노드를 추가하는 함수
    Node *tmp = (Node *)malloc(sizeof(Node));
    
    tmp->data = data;
    if(now == NULL) {    //첫번째 노드에 추가할때
        tmp->llink = NULL;
        tmp->rlink = *dlist;
        *dlist = tmp;
    }
    else {
        tmp->rlink = now->rlink;
        tmp->llink = now;
    }
}

int delete_data(Node **dlist, Node *now) {    //now뒤에 있는 노드를 삭제하는 함수
    int remove;
    Node *tmp;
    
    if(now == NULL) {    //첫번째 노드를 삭제할때
        tmp = *dlist;
        *dlist = tmp->rlink;
        tmp->rlink->llink = NULL;
        remove = tmp->data;
        free(tmp);    //삭제할 노드의 할당해제
    }
    else {
        tmp = now->rlink;
        now->rlink = tmp->rlink;
        tmp->rlink->llink = now;
        remove = tmp->data;
        free(tmp);    //삭제할 노드의 할당해제
    }
    
    return remove;
}

void print_node(Node **dlist) {
    Node *p;
    for(p = *dlist; p != NULL; p = p->rlink)
        printf("[%d]-> ", p->data);
    printf("\n");
}

int main(void) {
    
    Node *dlist;
    Node *now;
    dlist = NULL;
    now = NULL;
    
    insert_data(&dlist, now, 1);
    insert_data(&dlist, now, 2);
    insert_data(&dlist, now, 3);
    insert_data(&dlist, now, 4);
    
    print_node(&dlist);
    printf("delete_data : [%d] \n", delete_data(&dlist, now));
    print_node(&dlist);
    
    return 0;
}

실행화면

---

- 원형 연결리스트의 구현

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

typedef struct circular_linked_list {
    int data;
    struct circular_linked_list *link;
}C_node;

void insert_data_fisrt(C_node **clist, int data) {
    C_node *tmp = (C_node *)malloc(sizeof(C_node));
    tmp->data = data;
    
    if(*clist == NULL) {    //첫번째 노드를 생성할때
        tmp->link = tmp;    //원형으로 만들기 위해
        *clist = tmp->link;
    }
    else {    //첫번째에 새로운 노드를 생성
        tmp->link = (*clist)->link;
        (*clist)->link = tmp;
    }
}

int delete_node_first(C_node **clist) {    //첫번째 노드를 삭제하는함수
    C_node *tmp;
    int remove;
    
    tmp = (*clist)->link;
    remove = tmp->data;
    (*clist)->link = tmp->link;
    
    free(tmp);
    return remove;
}

void print_node(C_node **clist) {
    C_node *p = (*clist)->link;
    while(1) {
        printf("[%d]-> ", p->data);
        p = p->link;
        
        if(p == *clist) {    //다시 처음으로 돌아왔을때
            printf("[%d]-> ", p->data);
            break;
        }
    }
}

int main(void) {
    C_node *clist;    //리스트의 마지막 리스트를 가르키는 변수
    clist = NULL;
    
    insert_data_fisrt(&clist, 1);
    insert_data_fisrt(&clist, 2);
    insert_data_fisrt(&clist, 3);
    insert_data_fisrt(&clist, 4);
    insert_data_fisrt(&clist, 5);
    
    print_node(&clist);
    printf("\n");
    printf("delete_node_first : [%d]\n", delete_node_first(&clist));
    print_node(&clist);
    printf("\n");
    
    return 0;
}

실행결과

---

- 연결리스트로 구현한 다항식 덧셈 프로그램

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

typedef struct listnode {    //단순히 식을가지고있는리스트
    int coef;    //계수
    int expon;    //지수
    struct listnode *link;
}Listnode;

typedef struct listtype {    //식을가르키는 리스트를 가르키는 헤더노드
    int size;
    Listnode *head;
    Listnode *tail;
}Listtype;

Listtype * create(void) {
    Listtype * plist = (Listtype *)malloc(sizeof(Listtype));
    plist->size = 0;
    plist->head = plist->tail = NULL;
    return plist;
}

void insert_last(Listtype *plist, int coef, int expon) {
    Listnode * tmp = (Listnode *)malloc(sizeof(Listnode));
    tmp->coef = coef;
    tmp->expon = expon;
    tmp->link = NULL;
    if(plist->tail == NULL)    //리스트가 비어있을때
        plist->head = plist->tail = tmp;
    else {
        plist->tail->link = tmp;    //헤더노드의 테일이 가르키는 즉 식이들어있는 마지막노드가 가르키는 값에다가 tmp의 주소를 입력
        plist->tail = tmp;    //헤더노드의 테일이 tmp를 가르키도록 입력 이런식으로 하지않으면 테일은 여전히 추가하기전의 마지막노드를 가르키고있음
    }
    plist->size++;
}

void poly_add(Listtype *plist1, Listtype *plist2, Listtype *plist3) {
    Listnode *a = plist1->head;
    Listnode *b = plist2->head;
    int sum;
    
    while(a != NULL && b != NULL) { //a와b가 둘다 널이아닐때? 하나라도 널이라면 종료
        if(a->expon == b->expon) {
            sum = a->coef + b->coef;
            if(sum != 0) {
                insert_last(plist3, sum, a->expon);
                a = a->link;
                b = b->link;
            }
        }
        else if(a->expon > b->expon) {
                insert_last(plist3, a->coef, a->expon);
                a = a->link;
            }
        else if(a->expon < b->expon) {
                insert_last(plist3, b->coef, b->expon);
                b = b->link;
            }
    }
    
    //둘중 하나가 남았을때 진행
    
    for(; a != NULL; a = a->link)
        insert_last(plist3, a->coef, a->expon);
    for(; b != NULL; b = b->link)
        insert_last(plist3, b->coef, b->expon);
}

void poly_print(Listtype *plist) {
    Listnode *p = plist->head;
    printf("다항식 = ");
    for(; p; p = p->link)    //p가 널이아닐때까지반복
        printf("%d^%d + ", p->coef, p->expon);
    printf("\n");
}

int main(void) {
    Listtype *list1, *list2, *list3;
    
    list1 = create();
    list2 = create();
    list3 = create();
    
    insert_last(list1, 3, 12);
    insert_last(list1, 2, 8);
    insert_last(list1, 1, 0);
    
    insert_last(list2, 8, 12);
    insert_last(list2, -3, 10);
    insert_last(list2, 10, 6);
    
    poly_print(list1);
    poly_print(list2);
        
    poly_add(list1, list2, list3);
    poly_print(list3);

    free(list1);
    free(list2);
    free(list3);
    
    return 0;
}

실행결과

---

- 이중연결리스트와 원형연결리스트가 혼합된 MP3 재생 프로그램 구현

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


typedef struct d_node {
    char data[100];
    struct d_node *hlink;
    struct d_node *tlink;
}D_node;

D_node *current;

void print_node(D_node *head) {
    D_node *p;
    for(p = head->tlink; p != NULL; p = p->tlink) {
        if(p == current)
            printf("<-|# %s #|-> ", p->data);
        else
            printf("<-| %s |-> ", p->data);
    }
    printf("\n");
}

void d_insert(D_node *before, char data[]) {    //before의 오른쪽에 노드를 추가하는함수
    D_node *new_node = (D_node *)malloc(sizeof(D_node));
    strcpy(new_node->data, data);
    
    if(strcmp(before->data, "\0") == 0) {   //head가 입력되었을때
        new_node->hlink = NULL;
        new_node->tlink = before->tlink;
        
        if(before->tlink != NULL)    //head와 연결된 노드가 있었다면
            before->tlink->hlink = new_node;    //원래head뒤에 있던노드와 새로운노드 연결
            
        before->tlink = new_node;    //head를 새로운 노드와 연결
    }
    else {
        new_node->hlink = before;
        new_node->hlink = before->tlink;
        before->tlink->hlink = new_node;
        before->tlink = new_node;
    }
}

void d_delete(D_node *head, D_node *remove) {
    if(remove->hlink == NULL) { //삭제할노드가 첫번째노드일‹š때
        if(remove->tlink == NULL) { //첫번째노드이자 마지막노드일때
            printf("마지막 노드를 삭제했습니다. \n");
            head->tlink = NULL;
            free(remove);
        }
        else {
            head->tlink = remove->tlink;
            remove->tlink->hlink = NULL;
            free(remove);
        }
    }
    else {
        remove->hlink->tlink = remove->tlink;
        remove->tlink->hlink = remove->hlink;
        free(remove);
    }
}

int main(void) {
    char ch;
    D_node *head = (D_node *)malloc(sizeof(D_node));
    D_node *p;
    head->hlink = head->tlink = NULL;
    strcpy(head->data, "\0");
    
    d_insert(head, "Mamamia");
    d_insert(head, "Dancing Queen");
    d_insert(head, "Fernando");
    
    current = head->tlink;
    p = head->tlink;
    while(p->tlink != NULL)    //p가 마지막값을가르킬때까지 반복
        p = p->tlink;

    print_node(head);
    do {
        printf("\n\n명령어를 입력하세요 (<,>,q) : ");
        ch = getchar();
        getchar();
        printf("\n");
        if(ch == '<') {
            if(current->hlink == NULL)
                current = p;
            
            else
                current = current->hlink;
        }
        else if(ch == '>') {
            current = current->tlink;
            if(current == NULL)
                current = head->tlink;
        }
        print_node(head);
    }while(ch != 'q');
    
    free(head);
    
    return 0;
}

실행결과

---