DataStructure] C언어로 쉽게 풀어쓴 자료구조 4장 - 2

DataStructure] C언어로 쉽게 풀어쓴 자료구조 4장 - 2

C언어로 쉽게 풀어쓴 자료구조

4장 Exercise 문제들이다.

필자가 학교 다니면서 자료구조론 수업을 들었는데,

과제로 제출했던 것들이고,

난항을 겪고 있는 사람들에게 참고가 되었으면 하는 마음으로 올린다.

자고로, 버그가 존재할 수 있으니 디버깅 작업은 필수다.

14. 단순 연결 리스트에 정수가 저장되어 있다. 단순 연결 리스트의 모든 데이터 값을 더한 합을 출력하는 프로그램을 작성하여라.

 

15. 단순 연결 리스트에서 특정한 데이터 값을 갖는 노드의 개수를 계산하는 함수를 작성하라.

 

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

 

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

 

18. 두 개의 단순 연결 리스트 A, B가 주어져 있을 경우, alternate 함수를 작성하라. alternate 함수는 A와 B로부터 노드를 번갈아 가져와 새로운 리스트 C를 만드는 연산이다. 만약 입력 리스트 중에서 하나가 끝나게 되면, 나머지 노드들을 전부 C로 옮긴다. 함수를 구현하여 올바르게 작동하는지 테스트하라. 작성된 함수의 시간 복잡도를 구하라.

<SingleLinkedList.h>

#ifndef __SINGLE_LINKED_LIST_H__
#define __SINGLE_LINKED_LIST_H__
 
#define TRUE 1
#define FALSE 0
 
typedef int element;
typedef struct ListNode{
element data;
struct ListNode *link;
} ListNode;
 
// 리스트 삽입 삭제
void insert_node(ListNode **phead, ListNode *p, ListNode *new_node);
void remove_node(ListNode **phead, ListNode *p, ListNode *removed);
 
// 리스트 전체 출력
void display(ListNode *head);
// 에러 출력
void error(char *message);
 
// 리스트 동적 생성
ListNode *create_node(element data, ListNode *link);
 
/* 14번 */
void print_sum(ListNode *head);
/* 15번 */
int count_element(ListNode *head, element item);
/* 16번 */
void remove_specific_data(ListNode **phead, element item);
/* 17번 */
void remove_oddnode(ListNode **phead);
 
/* 18번 */
void insert_alternate(ListNode **phead, element item);
ListNode *alternate(ListNode *list1, ListNode *list2);
 
#endif

 

<SingleLinkedList.c>

#include <stdio.h>
#include <stdlib.h>
#include "SingleLinkedList.h"
 
// phead : head pointer's pointer
// p : previous node
// new_node : insert node
void insert_node(ListNode **phead, ListNode *p, ListNode *new_node)
{
    if (*phead == NULL) { // if list empty,
        new_node->link = NULL;
        *phead = new_node;
    }
    else if (p == NULL) { // 1st node
        new_node->link = *phead;
        *phead = new_node;
    }
    else { // general
        new_node->link = p->link;
        p->link = new_node;
    }
}
 
// phead : head pointer's pointer
// p : previous node
// removed : remove node
void remove_node(ListNode **phead, ListNode *p, ListNode *removed)
{
    if (p == NULL) // 1st node
        (*phead) = (*phead)->link;
    else // general
        p->link = removed->link;
    free(removed); // memeory free
}
 
// print element
void display(ListNode *head)
{
    ListNode *p = head;
    while (p != NULL) {
        printf("%d -> ", p->data);
        p = p->link;
    }
    printf("\n");
}
 
void error(char *message)
{
    fprintf(stderr, "%s\n", message);
    exit(1);
}
 
// node alloating dynamic
ListNode *create_node(element data, ListNode *link)
{
    ListNode *new_node;
    new_node = (ListNode*)malloc(sizeof(ListNode));
    if (new_node == NULL)
        error("Cannot Allocate Memeory");
    new_node->data = data;
    new_node->link = link;
    return new_node;
}
/* 14번 */
// Print sum
void print_sum(ListNode *head)
{
    ListNode *p = head;
    int sum = 0;
 
    while (p != NULL) { // 다음 노드가 없을 때까지,
        sum += p->data; // 노드의 데이터를 더함
        p = p->link; // 다음 노드로 이동
    }
    printf("모든 데이터의 합 : %d\n", sum);
}
/* 15번 */
// Count node having specific data value
int count_element(ListNode *head, element item)
{
    ListNode *p = head;
    int cnt = 0;
 
    while (p != NULL) { // 다음 노드가 없을 때까지,
        if (p->data == item) // 노드의 데이터가 일치하면,
            cnt++;
        p = p->link; // 다음 노드로 이동
    }
    return cnt;
}
/* 16번 */
// Remove node having specific data value
void remove_specific_data(ListNode **phead, element item)
{
    /* ph(헤드포인터), prev(삭제노드 바로 이전의 노드 = 선행노드) */
    ListNode *ph, *prev=NULL;
    ph = *phead;
 
    while (ph != NULL) {
        if (ph->data == item) { // 특정 데이터 값을 찾았으면
            remove_node(phead, prev, ph); // 노드 삭제 진행
            
            if (prev != NULL) // 선행노드가 존재하는 경우
                ph = prev->link;
            else // 선행 노드가 존재하지 않으면,
                ph = *phead;
        }
        else { // 데이터 값을 찾지 않은 경우, 다음 노드로 이동
            prev = ph;
            ph = ph->link;
        }
    }
}
/* 17번 */
// Remove Odd Node
void remove_oddnode(ListNode **phead)
{
    ListNode *ph, *prev = NULL;
    int cnt = 0;
    ph = *phead;
 
    while (ph != NULL) {
        if (cnt % 2 == 0){
            remove_node(phead, prev, ph); // 노드 삭제 진행
 
            if (prev != NULL) // 선행노드가 존재하는 경우
                ph = prev->link;
            else // 선행 노드가 존재하지 않으면,
                ph = *phead;
        }
        else { // 데이터 값을 찾지 않은 경우, 다음 노드로 이동
            prev = ph;
            ph = ph->link;
        }
        cnt++;
    }
}
 
/* 18번 */
// list 이어나감
void insert_alternate(ListNode **phead, element item)
{
    /* 노드의 말단에 연결해나간다. */
    ListNode *alt_node = create_node(item, NULL); // 노드 동적 생성
    
    if (*phead == NULL) // 헤드포인터가 없는 경우
        *phead = alt_node;
    else { // 헤드 포인터 있는 경우,
        ListNode *p = *phead; // 선행노드 시작을 헤드포인터로 지정
        while (p->link != NULL) // 노드의 말단까지 이동
            p = p->link;
        p->link = alt_node; // 새로운 노드 연결
    }
 
}
 
// 교차하며 리스트 연결
ListNode *alternate(ListNode *list1, ListNode *list2)
{
    ListNode *list3 = NULL;
    ListNode *ph1, *ph2, *ph3 = NULL;
    
    if (list1 == NULL) // list1이 비어 있을 경우, list3=list2
        return list2;
    
    else if (list2 == NULL) // list2가 비어 있을 경우, list3=list1
        return list1;
 
    else { // list1, list2에 노드가 존재하는 경우
        ph1 = list1; // list1을 가리킴
        ph2 = list2; // list2를 가리킴
 
        while (ph1 != NULL || ph2 != NULL) { 
            // 1. list1, list2 노드가 모두 있는 동안 교차하며 리스트 생성
            // 2. 둘 중 하나가 비어버리면, 남은 리스트로 리스트 생성
            if (ph1 != NULL) {
                insert_alternate(&list3, ph1->data);
                ph1 = ph1->link;
            }
            if (ph2 != NULL) {
                insert_alternate(&list3, ph2->data);
                ph2 = ph2->link;
            }
        }
    }
    return list3;
}

<main.c>

#include <stdio.h>
#include "SingleLinkedList.h"
int main(void)
{
    ListNode *list1 = NULL, *list2 = NULL, *list3 = NULL;
    int i;
    // list1 = 60->50->40->30->20->10
    for (i = 10; i <= 60; i += 10)
        insert_node(&list1, NULL, create_node(i, NULL));
    printf("리스트 1\n");
    display(list1);
 
    // list2 = 50->70->60->50->80->70->60->50
    for (i = 50; i <= 80; i += 10)
        insert_node(&list2, NULL, create_node(i, NULL));
    for (i = 50; i <= 70; i += 10)
        insert_node(&list2, NULL, create_node(i, NULL));
    insert_node(&list2, NULL, create_node(50, NULL));
    printf("리스트 2\n");
    display(list2);
    printf("\n");
 
    printf("리스트 1 ");
    print_sum(list1);
    printf("리스트 2 ");
    print_sum(list2);
    printf("\n");
 
    printf("리스트 1에서 데이터 값 10을 갖는 노드의 수 : %d\n", count_element(list1, 10));
    printf("리스트 2에서 데이터 값 50을 갖는 노드의 수 : %d\n", count_element(list2, 50));
    printf("\n");
 
    remove_specific_data(&list2, 50);
    printf("리스트 2에서 50을 갖는 노드 삭제\n");
    printf("리스트 2\n");
    display(list2);
    printf("\n");
 
    remove_oddnode(&list1);
    printf("리스트 1에서 홀수번째 노드 삭제\n");
    printf("리스트 1\n");
    display(list1);
    printf("\n");
 
    printf("리스트 3 생성\n");
    list3=alternate(list1, list2);
    printf("리스트 3\n");
    display(list3);
    printf("\n");
}