[C언어로 쉽게 풀어쓴 자료구조] 6장 연결 리스트 문제 풀이

01. 다음 중 NULL pointer가 존재 하지 않는 구조는?

→ (2) 원형 연결 리스트

    원형 연결리스트에서는 마지막 노드가 첫번째 노드를 가리키므ㄹ, null포인트가 존재하지 않는다.

 

02. 리스트의 n번째 요소를 가장 빠르게 찾을 수 있는 구현 방법은 무엇인가?

→ (1) 배열

    배열에서는 인덱스 n번째에 바로 접근 가능하므로, 시간복잡도 O(1)로 가장 빠르다.

 

03. 단순 연결 리스트에서 포인터 last가 마지막 노드를 가리킨다고 할 떄 다음 수식 중, 참인 것은?

→ (3) last->link == NULL

    

04. 단순 연결 리스트의 노드들을 포인터 p로 방문하고자 한다. 현재 p가 가리키는 노드에서 다음노드로 가려면 어떤 코드를 사용해야하는가?

→ (c) p=p->link;

    

→ p=p->link;

→ q=p;

 

 

→ D

    현재 노드가 가르키는 링크가 NULL일때까지 탐색하므로, 최종적으로는 마지막 노드를 가리키게 된다.

 

→ (4) deleteLast 연산: 덱의 마지막 원소를 삭제

    마지막 원소를 삭제한 후, last 포인터가 다시 마지막 노드를 가리키기 위해서는 첫번째 노드부터 다시 탐색해야 하므로 O(n)의 시간 복잡도가 소요된다.

#include <stdio.h>
#include <stdlib.h>
#define max_list_size 100

typedef int element;

typedef struct ListNode{
    element data;
    struct ListNode* link;
}ListNode;

void insert_node(ListNode**phead, ListNode* p, ListNode* new_node){
    if(*phead == NULL){
        new_node->link = NULL;
        *phead = new_node;
    }
    else if (p == NULL){
        new_node->link = *phead;
        *phead = new_node;
    }
    else{
        new_node->link = p->link;
        p->link = new_node;
    }
    return;
}
void insert_node_back(ListNode** pgead, ListNode* new_node){
    if(*phead == NULL){
        new_node -> link = NULL;
        *phead = new_node;
    }
    else{
        new_node->link =NULL;
        ListNode *p = *phead;
        while (p->link !=NULL)
            p = p->link;
        p->link= new_node;
    }
}

void remove_node(ListNode** phead, ListNode* p, ListNode* removed){
    if(p==NULL)
        *phead=(*phead)->link;
    else
        p->link = removed->link;
    free(removed);
    return;
}

ListNode* create_node(elemnet data){
    ListNode* new_node;
    new_node = (ListNode*)malloc(sizeof(new_node));
    new_node->data = data;
    new_node->link = NULL;
    return new_node;
}

void display(ListNode* head){
    ListNode*p = head;
    while(p != NULL){
        printf("%d", p->data);
        p = p->link;
    }
    printf("\n");
}

int main(void) {
	ListNode* list1 = {};
	int n, t;
	printf("노드의 개수 : ");
	scanf_s("%d", &n);
	for (int i = 0; i < n; i++) {
		printf("노드 #%d 데이터  : ", i + 1);
		scanf_s("%d", &t);
		insert_node_back(&list1, create_node(t));
	}
	printf("생성된 연결 리스트 : ");
	display(list1);
}

 

 

int get_count(ListNode* head){
    int count =0;
    ListNode* p = head;
    while (p != NULL){
        count++;
        p = p->link;
    }
    return count;
}

 

 

int get_sum(ListNode* head){
    int sum = 0;
    ListNode* p = head;
    while(p != NULL){
        sum += p->data;
        p=p->link;
    }
    return sum;
}

 

 

 

int fund_element(ListNode* head, element item){
    ListNode* p;
    p = head;
    int count = 0;
    while (p!= NULL){
        if(p->data ==item)
            count++;
        p = p->link;
    }
    return count;
}

 

13. 단순 연결 리스트에서의 탐색함수를 참고하여 특정한 데이터 값을 갖는 노드를 삭제하는 함수를 작성하여라

void remove_element_node(ListNode** head, element item){
    ListNode* p = NULL, *removed = *head;
    while (removed->data != item){
        p = removed;
        removed = removed->link;
    }
    if(p == NULL)
        *head = (*head)->link;
    free(removed);
    return;
}

 

 

typedef struct ListNode{
    char mane[20] = {};
    int age = {};
    double heigh = {};
    struct ListNode* link;
}ListNode;

 

 

15. 단순 연결 리스트가 정렬되지 않은 정수들의 리스트를 저장하고 있다. 리스트에서 최대값과 최소값을 찾는 프로그램을 작성하라.

int find_max(ListNode* head){
    ListNode* p = head;
    int ans = MIN;
    while(p != NULL){
        if(p->data > ans)
            ans = p->data;
        p = p->link;
    }
    return ans;
}
int find_min(ListNode* head){
    ListNode* p = head;
    int ans = MAX;
    while (p!= NULL){
        if(p->data <ans)
            ans = p->data;
        p = p->link;
    }
    return ans;
}

 

16. 단순 연결 리스트의 헤드 포인터가 주어져있을 떄, 첫 번째 노드에서부터 하나씩 건너서 있는 노드를 전부 삭제하는 함수를 작성하라. 즉 홀수번째 있는 노드들이 전부 삭제된다.

void remove_odd_node(ListNode** head){
    *head = (*head)->link;
    ListNode* p = NULL, * remobed = *head;
    while (removed->link != NULL){
        p = removed;
        removed = removed->link;
        p->link = removed->link;
        if(removed->link != NULL)
            removed = removed->link;
        else
            break;
    }
    return;
}

// 시간 복잡도는 연결리스트 A,B의 크기를 a, b라고 한다면 O(a+b)가 된다.
ListNode* alternate(ListNode* A, ListNode* B){
    ListNode* p = A, * q = B, *t = NULL;
    while (p!=NULL || q != NULL){
        if(p != NULL){
            insert_node_back(&t, create_node(p->data));
            p = p->link;
        }
        if(q != NULL){
            insert_node_back(&t, create_node(q->data));
            q = q->link;
        }
    }
    return t;
}

 

 

18. 2개의 단순 연결 리스트를 병합하는 함수를 조금 변경하여 보자, 두개의 연결리스트가 데이터 값의 오름차순으로 노드들이 정렬되어 있는 경우, 이러한 정렬상태를유지하면서 합병을 하여 새로운 연결리스트를 만드는 알고리즘 merge를 작성하라. a와  b에 있는 노드들은 전부 새로운 연결 리스트로 옮겨진다. 작성된 알고리즘의 시간 복잡도도 구하여라.

ListNode* merge(ListNode* A, ListNode *b){
    ListNode* p = A, *q = B, *t = NULL;
    while (p!= NULL && q != NULL){
        if(p->data < q->data){
            insert_node_back(&t, create_node(p->data));
            p = p->link;
        }
        else{
            insert_node_back(&t, create_node(q->data));
            q = q->link;
        }
    }
    while (p != NULL){
        insert_node_back(&t, create_node(p->data));
        p = p->link;
    }
    while (q != NULL){
        insert_node_back(&t, create_node(q->data));
        q = q->link;
    }
    return t;
}

// 시간 복잡도: 두 연결리스트의 크기를 각각 n1,n2라고 하면 O(n1+n2)가ㅏ 된다.

 

19. 단순 연결 리스트 c를 두개의 단순 연결리스트 A와 B로 분리하는 함수 split를 작성하여 보자. C의 홀수 번쨰 노드들은 모두 A로 이동되고 C의 짝수번째 노드들은 모두 B로 이동된다. 이 함수가 C를 변경하여서는 안된다. 작성된 알고리즘의 시간 복잡도를 구하고 구현하여 수행하여 보아라

typedef struct {
    node* list1;
    node* list2;
} list;

list split(node* head){
    list l = {NULL, NULL};
    node* p = head;

    while (p)
    {
        l.list1 = insert_last(l.list1, p->data);
        p = p->list;

        if(!p)
            break;
        l.list2 = insert_last(l.list2, p->data);
        p = p->list;
    }
    return l;
}

 

20. 두개의 다항식이 다음과 같이 주어졌다. 이들을 연결 리스트를 이용하여 나타내고 본문의 프로그램을 이용하여 두 다항식의 합을 구해보시오

1. 연결 리스트를 이용하여 다항식을 표현
   • ListNode 구조체를 정의하여 계수(coef)와 차수(expon)를 저장
   • ListHeader 구조체를 사용하여 리스트의 길이, head, tail 관리
2. 연결 리스트를 생성하고 노드를 추가하는 함수 작성
   • init()으로 리스트를 초기화
   • insert_node_last()로 리스트 끝에 항을 추가
3. 두 다항식의 덧셈 수행
   • poly_add()를 사용하여 차수를 비교하며 덧셈 수행
   • 같은 차수인 경우 계수를 더하고, 다르면 높은 차수를 먼저 추가
4. 결과 출력
   • poly_print()를 이용하여 다항식 형태로 출력

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

// 다항식 노드 구조체 정의
typedef struct ListNode {
    int coef; // 계수
    int expon; // 차수
    struct ListNode* link;
} ListNode;

// 다항식 리스트 헤더 구조체 정의
typedef struct ListHeader {
    int length;
    ListNode* head;
    ListNode* tail;
} ListHeader;

// 리스트 초기화 함수
void init(ListHeader* plist) {
    plist->length = 0;
    plist->head = plist->tail = NULL;
}

// 다항식의 마지막에 노드 추가 함수
void insert_node_last(ListHeader* plist, int coef, int expon) {
    ListNode* temp = (ListNode*)malloc(sizeof(ListNode));
    temp->coef = coef;
    temp->expon = expon;
    temp->link = NULL;
    if (plist->tail == NULL) {
        plist->head = plist->tail = temp;
    } else {
        plist->tail->link = temp;
        plist->tail = temp;
    }
    plist->length++;
}

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

    while (a && b) {
        if (a->expon == b->expon) {
            sum = a->coef + b->coef;
            if (sum != 0)
                insert_node_last(plist3, sum, a->expon);
            a = a->link;
            b = b->link;
        } else if (a->expon > b->expon) {
            insert_node_last(plist3, a->coef, a->expon);
            a = a->link;
        } else {
            insert_node_last(plist3, b->coef, b->expon);
            b = b->link;
        }
    }
    while (a) {
        insert_node_last(plist3, a->coef, a->expon);
        a = a->link;
    }
    while (b) {
        insert_node_last(plist3, b->coef, b->expon);
        b = b->link;
    }
}

// 다항식 출력 함수
void poly_print(ListHeader* plist) {
    ListNode* p = plist->head;
    while (p) {
        printf("%d %d\n", p->coef, p->expon);
        p = p->link;
    }
}

int main(void) {
    ListHeader list1, list2, list3;
    init(&list1);
    init(&list2);
    init(&list3);

    // 첫 번째 다항식 삽입
    insert_node_last(&list1, 3, 6);
    insert_node_last(&list1, 7, 3);
    insert_node_last(&list1, -2, 2);
    insert_node_last(&list1, -9, 0);
    
    // 두 번째 다항식 삽입
    insert_node_last(&list2, -2, 6);
    insert_node_last(&list2, -4, 4);
    insert_node_last(&list2, 6, 2);
    insert_node_last(&list2, 6, 0);
    
    // 다항식 출력
    printf("Polynomial 1:\n");
    poly_print(&list1);
    printf("Polynomial 2:\n");
    poly_print(&list2);
    
    // 다항식 덧셈 수행
    poly_add(&list1, &list2, &list3);
    
    // 결과 출력
    printf("Sum:\n");
    poly_print(&list3);
    
    return 0;
}

 

 

21. 다항식을 연결 리스트로 표현할 수 있음을 보였다. 다항식이 연결 리스트로 표현되어 있고, p를 다항식으로 가리키는 포인터라고 할 때, 어떤 실수 x에 대하ㅏ여 이 다항식의 값을 계싼하ㅏ는 함수 poly_eval을 작성하여라, 즉 다항식이 x^3+2x+6이고 x=2이면 2^3+2*2+6를 계산 하는 함수를 작성하여보아라

 

→ 

다항식의 각 항(term)은 계수(coef)와 지수(expon)로 표현되며, 이를 단순 연결 리스트로 관리합니다.

주어진 poly_eval 함수는 다음과 같은 방식으로 동작합니다:

1. sum 변수를 0으로 초기화합니다.
2. 연결 리스트의 각 노드를 순회하면서,
   • (x^expon) * coef 값을 계산하여 sum에 더합니다.
3. 최종적으로 sum을 반환하여 다항식의 값을 출력합니다.

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

// 연결 리스트 노드 정의
typedef struct ListNode {
    int coef;   // 계수
    int expon;  // 지수
    struct ListNode* link;
} ListNode;

// 다항식을 담는 리스트 구조체
typedef struct {
    ListNode* head;
} List;

// 다항식 계산 함수
int poly_eval(List* plist, int x) {
    if (!plist || !plist->head) return 0; // 빈 리스트 예외 처리

    int sum = 0;
    ListNode* a = plist->head;

    while (a) {
        sum += a->coef * pow(x, a->expon); // pow 함수 사용하여 지수 연산 수행
        a = a->link;
    }
    return sum;
}

 

22. 배열을 이용하여 숫자들을 입력 받아 항상 오름차순으로 정렬된 상태로 유지하는 리스트 sort-edlist를 구현하여 보라. 다음의 연산들을 구현하면 된다.

• 객체: n 개의 element 형으로 구성된 순서있는 모임
• 연산:
  • add(list, item) : 정렬된 리스트에 요소를 추가
  • delete(list, item) : 정렬된 리스트에서 item을 제거
  • clear(list) : 리스트의 모든 요소를 제거
  • is_in_list(list, item) : item이 리스트안에 있는지를 검사
  • get_length(lsit) : 리스트의 길이를 구함
  • is_empty(list) : 리스트가 비었는지 확인
  • is_full(list) :  리스트가 꽉찼는지 검사
  • display(list) : 리스트의 모든 요소를 표시

#include<stdio.h>
#include<stdlib.h>
#define MAX_LIST_SIZE 100

typedef struct{
    int list[MAX_LIST_SIZE];
    int length;
} ArrayListType;

void init(ArrayListType *L){
    L->length = 0;
}
bool is_empty(ArrayListType* L){
    return L->length == 0;
}
bool is_full(ArrayListType*L){
    return L->length == MAX_LIST_SIZE;
}
void add_item(ArrayListType*L, int item){
    if(is_full(L)){
        printf("이미 배열이 가득 참");
        return;
    }
    int i = 0;
    for (i=0; i<L->length; i++){
        if(item < L->list[i]){
            for (int j = L->length; j >i; j--)
                L->list[j] = L->list[j -1];
            break;
        }
    }
    L->list[i] = item;
    L->length++;
}
void delete_item(ArrayListType*L, int item){
    int i;
    for(i=0; i<L->length; i++){
        if(item == L->list[i]){
            for (int j=i; j< L->length; j++){
                L->list[j] = L->list[j+1];
            }
        }
    }
    L->length--;
}
void clear_list(ArrayListType*L, int item){
    L->length =0;
}

bool is_in_list(ArrayListType*L, int item){
    for (int i = 0; i < L->length; i++)
        if(L->list[i] == item)
            return true;
    return false;
}

int get_length(ArrayListType* L){
    return L->length;
}
void display(ArrayListType * L){
    for (int i=0; i < L->length; i++)
        printf("%d", L->list[i]);
    printf("\n");
}

 

 

23. 단순 연결 리스트를 이용하여 숫자들을 항상 오름차순으로 정렬된 상태로 유지하는 리스트 sortedList를 구현해보라. 앞의 문제의 연산들을 구현하면 된다.

→ 

이 문제에서는 단순 연결 리스트를 사용하여 숫자들이 항상 오름차순으로 정렬된 상태를 유지하는 sortedList를 구현하는 것입니다.
즉, 숫자가 삽입될 때마다 리스트가 정렬된 상태를 유지해야 합니다.

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

typedef int element;
typedef struct ListNode {
    element data;
    struct ListNode* link;
} ListNode;

// 새로운 노드를 생성하는 함수
ListNode* create_node(element data) {
    ListNode* new_node = (ListNode*)malloc(sizeof(ListNode));
    if (new_node == NULL) {
        printf("메모리 할당 실패\n");
        exit(1);
    }
    new_node->data = data;
    new_node->link = NULL;
    return new_node;
}

// 오름차순 정렬된 상태를 유지하면서 노드를 삽입하는 함수
void add_element(ListNode** phead, ListNode* new_node) {
    if (*phead == NULL || new_node->data < (*phead)->data) {
        new_node->link = *phead;
        *phead = new_node;
        return;
    }

    ListNode* c = *phead;
    while (c->link != NULL && c->link->data < new_node->data) {
        c = c->link;
    }
    new_node->link = c->link;
    c->link = new_node;
}

// 리스트에서 특정 원소 삭제
void delete_element(ListNode** head, element item) {
    if (*head == NULL) return; // 빈 리스트 예외 처리

    ListNode* p = NULL, *removed = *head;
    
    while (removed != NULL && removed->data != item) {
        p = removed;
        removed = removed->link;
    }

    if (removed == NULL) return; // item이 리스트에 없는 경우

    if (p == NULL) { // 첫 번째 노드 삭제
        *head = removed->link;
    } else {
        p->link = removed->link;
    }
    free(removed);
}

// 리스트 초기화 (모든 노드 삭제)
void clear(ListNode** head) {
    ListNode* temp;
    while (*head != NULL) {
        temp = *head;
        *head = (*head)->link;
        free(temp);
    }
}

// 리스트에서 특정 값이 존재하는지 확인
bool is_in_list(ListNode* head, element item) {
    ListNode* p = head;
    while (p != NULL) {
        if (p->data == item) return true;
        p = p->link;
    }
    return false;
}

// 리스트 길이 반환
int get_length(ListNode* head) {
    int count = 0;
    ListNode* p = head;
    while (p != NULL) {
        count++;
        p = p->link;
    }
    return count;
}

// 리스트가 비어있는지 확인
bool is_empty(ListNode* head) {
    return head == NULL;
}

// 리스트가 가득 찼는지 확인 (메모리 할당이 가능한지 테스트)
bool is_full(ListNode* head) {
    ListNode* temp = (ListNode*)malloc(sizeof(ListNode));
    if (temp == NULL) return true;
    free(temp);
    return false;
}

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

// 테스트용 메인 함수
int main() {
    ListNode* sortedList = NULL;

    add_element(&sortedList, create_node(5));
    add_element(&sortedList, create_node(3));
    add_element(&sortedList, create_node(8));
    add_element(&sortedList, create_node(1));
    add_element(&sortedList, create_node(6));

    printf("오름차순 정렬된 리스트: ");
    display(sortedList);

    delete_element(&sortedList, 3);
    printf("3 삭제 후: ");
    display(sortedList);

    printf("리스트 길이: %d\n", get_length(sortedList));
    printf("6이 리스트에 존재하는가? %s\n", is_in_list(sortedList, 6) ? "Yes" : "No");
    printf("리스트가 비었는가? %s\n", is_empty(sortedList) ? "Yes" : "No");

    clear(&sortedList);
    printf("리스트 초기화 후: ");
    display(sortedList);

    return 0;
}