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

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

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

4장 Exercise 문제들이다.

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

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

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

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

29번. 이중 연결 리스트를 이용하여 숫자들을 항상 정렬된 상태로 유지하는 리스트 SortedList를 구현하여보라.

앞의 문제의 연산들을 구현하면 된다.

 

<SortedList.h>

#ifndef __SORTED_LIST_H__
#define __SORTED_LIST_H__
#define TRUE 1
#define FALSE 0
typedef int element;
typedef struct ListNode
{
    element data;
    struct ListNode* rlink;
    struct ListNode* llink;
} ListNode;
// 노드 초기화
void Init(ListNode* head);
// 노드 개수 카운트
int get_length(ListNode* const head);
// item이 리스트 안에 있는지 검사
int is_in_list(ListNode* const head, int item);
// 리스트 비었는지 확인
int is_empty(ListNode* const head);
// 정렬된 리스트에 추가
void AddNode(ListNode* head, int item);
// 리스트에서 삭제
void DeleteNode(ListNode* head, int item);
// 출력
void display(ListNode* const head);
// 동적 노드 생성
ListNode* CreateNode(int item);
// 리스트 클리어
void Clear(ListNode* head);
#endif

<SortedList.cpp>

#include <stdio.h>
#include <stdlib.h>
#include "SortedList.h"
// 노드 초기화
void Init(ListNode* head)
{
    head->llink = head;
    head->rlink = head;
}
// 노드 개수 카운트
int get_length(ListNode* const head)
{
    ListNode* p = head;
    int cnt = 0;
    while (p->rlink != head)
    {
        cnt++;
        p = p->rlink;
    }
    return cnt;
}
// item이 리스트 안에 있는지 검사
int is_in_list(ListNode* const head, const int item)
{
    ListNode* p = head;
    while (p->rlink != head)
    {
        if (p->rlink->data == item)
            return TRUE;
        p = p->rlink;
    }
    return FALSE;
}
// 리스트 비었는지 확인
int is_empty(ListNode* const head)
{
    return (head == head->rlink) && (head==head->rlink);
}
// 정렬된 리스트에 추가
void AddNode(ListNode* head, int item)
{
    ListNode* p = head;
    ListNode* new_node = CreateNode(item);
    // 리스트에 아무것도 없을 때
    if (is_empty(p))
    {
        new_node->rlink = p;
        new_node->llink = p;
        p->rlink = new_node;
        p->llink = new_node;
        return;
    }
    // 리스트에 노드가 하나 이상 있을 때,
    p = p->rlink;
    while (p != head)
    {
        if (p->data >= item)
        {
            new_node->rlink = p;
            new_node->llink = p->llink;
            p->llink->rlink = new_node;
            p->llink = new_node;
            return;
        }
        p = p->rlink;
    }
    // 추가되는 노드가 리스트의 어느 값들보다 클 경우(말단에 추가)
    new_node->rlink = p;
    new_node->llink = p->llink->rlink;
    p->llink->rlink = new_node;
    p->llink = new_node;
}
// 리스트에서 삭제
void DeleteNode(ListNode* head, int item)
{
    ListNode* p = head;
    ListNode* pn;
    
    if (is_empty(p))
        return;
    pn = p->rlink;
    while (pn != head)
    {
        if (pn->data == item)
        {
            pn->llink->rlink = pn->rlink;
            pn->rlink->llink = pn->llink;
            free(pn);
            return;
        }
        pn = pn->rlink;
    }
}
void display(ListNode* const head)
{
    ListNode* p = head;
    if (is_empty(p))
        printf("Empty Node\n");
    while (p->rlink != head)
    {
        printf(" <- %d -> \n", p->rlink->data);
        p = p->rlink;
    }
}
ListNode* CreateNode(int item)
{
    ListNode* new_node = (ListNode*)malloc(sizeof(ListNode));
    new_node->data = item;
    new_node->llink = new_node;
    new_node->rlink = new_node;
    return new_node;
}
// 리스트 클리어
void Clear(ListNode* head)
{
    ListNode* pn;
    ListNode* p = head;
    if (head == head->rlink)
        return;
    p = p->rlink;
    pn = p;
    while (1)
    {
        p->llink->rlink = p->rlink;
        p->rlink->llink = p->llink;
        pn = p->rlink;
        free(p);
        p = pn;
        if (p == head)
            break;
    }
}

<main.cpp>

#include <stdio.h>
#include "SortedList.h"
int main(void)
{
    ListNode list1;
    Init(&list1);
    AddNode(&list1, 50);
    AddNode(&list1, 60);
    AddNode(&list1, 30);
    AddNode(&list1, 20);
    AddNode(&list1, 10);
    AddNode(&list1, 40);
    AddNode(&list1, 70);
    display(&list1);
    printf("%d\n", get_length(&list1));
    printf("%d", is_in_list(&list1, 10));
    DeleteNode(&list1, 30);
    printf("\n");
    display(&list1);
    Clear(&list1);
    printf("%d\n", get_length(&list1));
    display(&list1);
}