[자료구조] ep3-1) 단일연결리스트(Single Linked List)

ㅁ리스트 ADT: 여러 개의 노드들이 순차적으로 연결된 형태를 갖는 자료구조

응용 예: 스택, 큐, 집합 / 소규모 db(주소록 등) or 더 복잡한 데이터구조 재료

 

※노드(node): 커다란 자료구조의 일부분 하나 하나를 의미

e.g. 리스트의 노드, 트리의 노드

노드의 구조

 

 

리스트는 배열과 쓰임새가 비슷해 보통 많이들 비교한다

배열 vs 연결리스트 O(n) 성능 비교

 

 

 

 

ㅇ단일연결리스트: 노드 간의 링크가 하나

단일연결리스트의 전체 구조

 

 

 

 

 

활용) 다항식을 표현하는 연결리스트

한 개의 다항식(polynomial)을 한 개의 헤더 단일연결리스트로 표현하는 방식

(연결리스트의 각 노드는 차수의 내림차순으로 유지하고, 계수가 0인 항의 노드는 유지하지 않음)

 

여기서 다항식의 덧셈을 구하는 프로그램을 만들자

test case

 

 

 

(전체 코드)

#include <stdio.h>
#include <stdlib.h>
#pragma warning (disable : 4996)

// 다항식의 각 항을 표현하는 구조체
typedef struct NODE {
    int coef;   // 계수
    int exp;    // 차수
    struct NODE* next;
} NODE;

void appendTerm(NODE* head, int c, int e);
NODE* addPoly(NODE* x, NODE* y);
void print(NODE* head);

int main() {
    int n;
    int c, e;
    NODE* poly1 = (NODE*)malloc(1 * sizeof(NODE));
    poly1->next = NULL;
    NODE* poly2 = (NODE*)malloc(1 * sizeof(NODE));
    poly2->next = NULL;
    NODE* head;
    NODE* ans;

    scanf("%d", &n);
    head = poly1;
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &c, &e);
        appendTerm(head, c, e);
        head = head->next;
    }
    scanf("%d", &n);
    head = poly2;
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &c, &e);
        appendTerm(head, c, e);
        head = head->next;
    }
    // 두 다항식 더하기
    ans = addPoly(poly1, poly2);
    // 최종출력
    print(ans);
    // 메모리 해제
    while (poly1 != NULL) {
        NODE* temp = poly1;
        poly1 = poly1->next;
        free(temp);
    }
    while (poly2 != NULL) {
        NODE* temp = poly2;
        poly2 = poly2->next;
        free(temp);
    }
    while (ans != NULL) {
        NODE* temp = ans;
        ans = ans->next;
        free(temp);
    }
    return 0;
}

// 다항식에 항 추가하는 함수
void appendTerm(NODE* head, int c, int e) {
    NODE* newNode = (NODE*)malloc(1 * sizeof(NODE)); // 새 노드 생성
    newNode->coef = c;
    newNode->exp = e;
    newNode->next = NULL;

    head->next = newNode; // 새 노드를 마지막 노드로 연결

    return;
}

// 두 다항식을 더하는 함수
NODE* addPoly(NODE* x, NODE* y) {
    NODE* res = (NODE*)malloc(1 * sizeof(NODE));
    res->next = NULL;
    NODE* head = res;
    NODE* i = x->next; // x 다항식 구조체 헤드포인터 (헤더 skip)
    NODE* j = y->next; // y 다항식 구조체 헤드포인터 (헤더 skip)

    int sum;
    while (i != NULL && j != NULL) {
        if (i->exp > j->exp) {
            appendTerm(head, i->coef, i->exp);
            i = i->next;
        }
        else if (i->exp < j->exp) {
            appendTerm(head, j->coef, j->exp);
            j = j->next;
        }
        else if (i->exp == j->exp) {
            sum = i->coef + j->coef;
            if (sum == 0) {
                i = i->next;
                j = j->next;
                continue; // 항 추가 skip
            }
            appendTerm(head, sum, i->exp);
            i = i->next;
            j = j->next;
        }
        head = head->next; // 항 추가
    }
    // 남은 항들 추가
    while (i != NULL) {
        appendTerm(head, i->coef, i->exp);
        i = i->next;
        head = head->next;
    }
    while (j != NULL) {
        appendTerm(head, j->coef, j->exp);
        j = j->next;
        head = head->next;
    }

    return res;
}

void print(NODE* head) {
    while (head->next != NULL) {
        head = head->next;
        printf(" %d %d", head->coef, head->exp);
    }
}

/*
3
5 3 3 2 3 1
3
2 6 2 3 1 0

2
2 7 3 0
3
-3 10 3 7 -3 0
*/

 

 

 

 

 

 

 

 

 

 

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