[C언어로 쉽게 풀어쓴 자료구조] Chapter 6 - 연결 리스트 1

// 배열로 리스트 구현하기

// 배열로 구현한 리스트
#include <stdio.h>
#include <stdlib.h>

#define MAX_LIST_SIZE 100

typedef int element; // 리스트 요소 선언
typedef struct {
    element array[MAX_LIST_SIZE]; // 배열 선언
    int size; // 리스트 크기
} ArrayListType;

// 오류처리 함수
void error(char *message)
{
    fprintf(stderr, "%s\n", message);
    exit(1);
}

// 리스트 초기화 함수
void init(ArrayListType *L)
{
    L->size = 0;
}

// 리스트 공백 상태 함수 , 리스트가 비어있다면 1을 반환 , 그렇지 않다면 0을 반환
int is_empty(ArrayListType *L)
{
    return L->size == 0;
}

// 리스트 포화 상태 함수 , 포화상태 1반환 , 아니면 0만환
int is_full(ArrayListType *L)
{
    return L->size == MAX_LIST_SIZE;
}

// 리스트 요소 반환 함수
element get_entry(ArrayListType *L, int pos)
{
    if (pos<0 || pos>=L->size)
        error("위치 오류");
    // pos가 가리키를 element를 반환
    return L->array[pos];
}

// 리스트 출력
void print_list(ArrayListType *L)
{
    printf("리스트 출력 : ");
    for (int i=0 ; i<L->size ; i++)
    {
        printf("%d->", L->array[i]);
    }
    printf("\n");
}

// 리스트 삽입 함수 1 (리스트 맨끝에 항목 추가)
void insert_last(ArrayListType *L, element item)
{
    if(L->size >= MAX_LIST_SIZE) {
        error("리스트 오버플로우");
    }
    L->array[L->size++] = item;
}

// 리스트 삽입 함수 2 (리스트 원하는 자리에 항목 추가)
void insert(ArrayListType *L, int pos, element item)
{
    if (!is_full(L) && (pos >= 0) && (pos <= L->size)) {
        for (int i = (L->size - 1); i>= pos; i--)
            L->array[i + 1] = L->array[i];
        L->array[pos] = item;
        L->size++;
    }
}

// 리스트 삭제 함수 (원하는 자리의 항목을 삭제 후 해당 항목 반환)
element delete(ArrayListType *L, int pos)
{
    element item;

    if (pos < 0 || pos >= L->size)
        error("위치 오류");
    item = L->array[pos];
    // 삭제 할 항목을 리스트에서 메워준다.
    for (int i = pos; i<(L->size - 1); i++)
        L->array[i] = L->array[i+1];
    L->size--;
    return item; // 삭제된 항목 반환
}

/* clear(list), replace(list, pos, item), get_length(list) 함수 구현하기 */
// 모든 요소 제거
void clear(ArrayListType *L)
{

    if (is_empty(L))
        error("리스트는 이미 공백상태 입니다.");
    int beforesize = L->size;
    for(int i=0; i<beforesize; i++)
        delete(L, 0);
}

// 교환함수 (list의 pos자리에 item을 배치, 기존에 배치된 항목이 있으면 덮어씌우기)
void replace(ArrayListType *L, int pos, element item)
{
    if (pos > 0 || pos < L->size){
        L->array[pos] = item;
    }
}

// 리스트 크기 반환 함수
int get_length(ArrayListType *L)
{
    return L->size;
}
/* ****************************** */


int main()
{
    ArrayListType list;

    init(&list);
    insert(&list, 0, 10);
    print_list(&list);
    insert(&list, 0, 20);
    print_list(&list);
    insert(&list, 0, 30);
    print_list(&list);
    insert_last(&list, 40);
    print_list(&list);
    delete(&list, 0);
    print_list(&list);

    // clear , replace , get_length 사용
    printf("\n***********************\n");
    replace(&list, 1, 50);
    print_list(&list);
    printf("리스트 크기 : %d\n", get_length(&list));
    clear(&list);
    print_list(&list);
    return 0;
}

/* 출력값
리스트 출력 : 10->
리스트 출력 : 20->10->
리스트 출력 : 30->20->10->
리스트 출력 : 30->20->10->40->
리스트 출력 : 20->10->40->

***********************
리스트 출력 : 20->50->40->
리스트 크기 : 3
리스트 출력 :
*/

 

// 연결된 표현 (linked representation) : 동적으로 크기가 변할 수 있고, 삭제나 삽입 시에 데이터를 이동할 필요가 없는것 

연결 리스트(linked list) : 물리적으로 흩어져 있는 자료들을 서로 연결하여 하나로 묶는 방법

장점 : 리스트 중간에 데이터를 삽입할 때, 다른 데이터를 이동할 필요가 없다.

데이터를 삽입할 공간이 필요할 때 마다 동적으로 공간을 만들어 쉽게 추가 할 수 있다.

 

단점 : 데이터를 저장할 뿐만 아니라 포인터도 함께 저장해야 함으로 저장공간 차지가 늘어남

i 번째 데이터를 찾기 위해서 1번 데이터 부터 순차적으로 탐색해야 한다.

 

[Data field][Link field]-->[Data field][Link field]--> .... [Data field][Link field]-->[Data field][NULL]

Link field의 포인터는 "포인터 = malloc(sizeof(자료형))" 으로 생성한다.

 

연결리스트는 3가지 종류가 있다.

1. 단순 연결 리스트 : 헤드 포인트 부터 시작 ... 마지막 포인터는 NULL(아무도 가리키지 않음)

2. 원형 연결 리스트 : 단순 연결리스트와 나머지는 동일 , 마지막 포인터가 첫번째 포인터를 가리킴

3. 이중 연결 리스트 : 인접한 노드를 서로 가리키는 왕복 차선이 있음

 

// 단순 연결 리스트 프로그램

// 단순 연결 리스트
#include <stdio.h>
#include <stdlib.h>

typedef int element;
typedef struct LinkNode {
    element data;
    struct ListNode *link;
} ListNode; // 노드 타입을 구조체를 이용해 정의

// 삽입 함수 1(리스트 처음에 새로운 노드를 추가)
ListNode* insert_first(ListNode *head, int value)
{
    ListNode *p = (ListNode *)malloc(sizeof(ListNode)); // 삽입할 노드 p todtjd
    p->data = value; // 입력하고자 하는 데이터
    p->link = head; // 기존 head가 가리키던 값을 복사
    head = p; // head를 p로 변경 (head가 삽입된 노드를 가리키도록)
    return head; // 변경된 head를 반환
}

// 삽입 함수 2 (리스트 중간(원하는 곳)에 새로운 노드를 추가) // pre : 선행노드
ListNode* insert(ListNode *head, ListNode *pre, int value)
{
    ListNode *p = (ListNode *)malloc(sizeof(ListNode)); // 새로운 노드 p 생성
    p->data = value; // p의 데이터 필드에 value를 저장
    p->link = pre->link; // 선행노드가 기존에 가리키던 위치를 p가 가리키도록 저장
    pre->link = p; // 선행노드는 p를 가리키도록 저장
    return head; // 변경된 head 포인터 반환
}

// 삭제 함수 1 (리스트의 첫번째 노드를 삭제)
ListNode* delete_first(ListNode *head)
{
    ListNode *removed;
    // head가 NULL이라면 (빈 연결리스트 라면)
    if (head == NULL) return NULL;
    removed = head;
    head = removed->link; // 지워질 노드가 가리키던 노드를 head가 가리키도록
    free(removed); // removed의 동적 메모리 반환
    return head;
}

// 삭제 함수 2 (리스트의 중간(원하는)노드 삭제)
ListNode* delete(ListNode *head, ListNode *pre)
{
    ListNode *removed;
    removed = pre->link; // 선행노드를 이용해 삭제할 노드를 설정
    pre->link = removed->link; // 선행노드가 삭제할 노드가 가리키던 노드를 가리키도록
    free(removed); // removed의 동적 메모리 반환
    return head;
}

// 연결 리스트 출력
void print_list(ListNode *head)
{
    for (ListNode *p = head; p != NULL; p = p->link)
        printf("%d->", p->data);
    printf("NULL \n");
}

// index 번쨰의 데이터를 찾아 반환한다.
element get_entry(ListNode *L, int index)
{
    int count=0;
    ListNode *thing;
    for (ListNode *p = L; p != NULL; p = p->link){
        count++;
        if (index == count){
            thing = p;
            break;
        }
    }
    return thing->data;
}

int main()
{
    ListNode *head = NULL;

    for (int i=0; i<5; i++){
        head = insert_first(head, i);
        print_list(head);
    }
    printf("\n3번째 데이터 출력 : %d\n\n",get_entry(head, 3));
    for (int i=0; i<5; i++){
        head = delete_first(head);
        print_list(head);
    }
    return 0;
}

/*출력값
0->NULL
1->0->NULL
2->1->0->NULL
3->2->1->0->NULL
4->3->2->1->0->NULL

3번째 데이터 출력 : 2

3->2->1->0->NULL
2->1->0->NULL
1->0->NULL
0->NULL
NULL
*/

 

 

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

// 연결 리스트의 응용 : 다항식

#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;

// 오류 함수
void error(char *message)
{
    fprintf(stderr, "%s\n", message);
    exit(1);
}

// 리스트 헤더 생성 함수
ListType* create()
{
    // plist : 연결 리스트의 헤더를 가리키는 포인터
    ListType *plist = (ListType *)malloc(sizeof(ListType));
    plist->size = 0; // 아직 연결 리스트 사이즈 초기값
    plist->head = plist->tail = NULL; // 초기값
    return plist;
}

// 연결 리스트에 말단에 항목 추가하기
// plist(연결 리스트의 헤더를 가리키는 포인터), coef : 계수, expon : 지수
void insert_last(ListType* plist, int coef, int expon)
{
    ListNode* temp =
		(ListNode *)malloc(sizeof(ListNode));
    if (temp == NULL) error("메모리 할당 에러");
    temp->coef = coef;
	temp->expon = expon;
	temp->link = NULL;
    if (plist->tail == NULL) {// 연결 리스트에 처음 추가 되는 항 이라면
        plist->head = plist->tail = temp;
    }
    else{
        plist->tail->link = temp; // 연결 리스트 헤더의 tail의 link가 가리키는 것
        plist->tail = temp; // 연결 리스트 헤더의 tail이 가리키는 것
    }
    plist->size++;
}

// list3 = list1 + list2
// 다항식 덧셈 함수
void poly_add(ListType* plist1, ListType* plist2, ListType* plist3)
{
    ListNode* a = plist1->head;
	ListNode* b = plist2->head;
    int sum;

    while (a && b){ // a와 b의 모든 항을 탐색
        if (a->expon == b->expon) { // 차수가 같다면,
            sum = a->coef + b->coef; // sum에 계수의 합을 저장
            if (sum != 0) insert_last(plist3, sum, a->expon); // 계수가 0이 아니라면 더한 항을 다항식 합계 연결 리스트에 추가
            a = a->link; b = b->link; // 다항식 a와 다항식 b가 다음 항을 가리키게함
        }
        else if (a->expon > b->expon) { // a의 차수 > b의 차수
            insert_last(plist3, a->coef, a->expon); // 그대로 c에 해당 항을 추가
            a = a->link; // 다항식 a의 다음 항을 가리킴
        }
        else { // a의 차수 < b의 차수
            insert_last(plist3, b->coef, b->expon);
            b = b->link;
        }
    }

    // a와 b중의 하나가 먼저 끝나게 되면, 남은 항은 그대로 c에 추가 / c : 결과 다항식
    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("polynomial = ");
    for (; p; p = p->link) {
        printf("%dX^%d + ", p->coef, p->expon);
    }
    printf("\n");
}

int main()
{
    ListType *list1, *list2, *list3;

    list1 = create(); // 다항식 a
    list2 = create(); // 다항식 b
    list3 = create(); // 다항식 c

    // 다항식 a = 3X^12 + 5X^10 + 7X^3 + 7X^0
    insert_last(list1, 3, 12);
    insert_last(list1, 5, 10);
    insert_last(list1, 7, 3);
    insert_last(list1, 7, 0);

    // 다항식 b = 3X^10 + 5X^9 + 3X^3 + 2X^1 + 5X^0
    insert_last(list2, 3, 10);
    insert_last(list2, 5, 9);
    insert_last(list2, 3, 3);
    insert_last(list2, 2, 1);
    insert_last(list2, 5, 0);

    // 다항식 출력
    printf("A ");
    poly_print(list1);
    printf("B ");
    poly_print(list2);

    // C = A + B
    poly_add(list1 , list2 , list3);
    printf("C ");
    poly_print(list3);

    // 동적 메모리 반환
    free(list1);
    free(list2);
    free(list3);
}

/*출력값
A polynomial = 3X^12 + 5X^10 + 7X^3 + 7X^0 +
B polynomial = 3X^10 + 5X^9 + 3X^3 + 2X^1 + 5X^0 +
C polynomial = 3X^12 + 8X^10 + 5X^9 + 10X^3 + 2X^1 + 12X^0 +
*/