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

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

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

9장 Exercise 문제다.

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

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

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

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

21. 삽입 정렬에서 입력과 출력이 모두 동적 연결 리스트로 주어지는 경우의 삽입 정렬 함수를 구현하라.

<SingledLinkedList.h>

#ifndef __SINGLE_LINKED_LIST_H__
#define __SINGLE_LINKED_LIST_H__
 
typedef int element;
typedef struct ListNode
{
    element data;
    struct ListNode* link;
} ListNode;
typedef struct
{
    int size;
    ListNode* head;
} ListType;
 
void Init(ListType* list);
 
void InsertNode(ListNode** phead, ListNode* p, ListNode* newnode);
void AddNode(ListType* list, int pos, element x);
 
ListNode* GetNode(ListType* list, int pos);
int GetSize(ListType* list);
void PrintList(ListType* list);
 
#endif

<SingledLinkedList.cpp>

#include <stdio.h>
#include <stdlib.h>
#include "SingleLinkedList.h"
 
void Init(ListType* list)
{
    list->size = 0;
    list->head = NULL;
}
 
void AddNode(ListType* list, int pos, element x)
{
    ListNode* p;
        
    if (pos >= 0 && pos <= list->size)
    {
        ListNode* node = (ListNode*)malloc(sizeof(ListNode));
        node->data = x;
 
        p = GetNode(list, pos - 1);
        InsertNode(&(list->head), p, node);
        list->size++;
    }
}
void InsertNode(ListNode** phead, ListNode* p, ListNode* newnode)
{
    if (phead == NULL)
    {
        newnode->link = NULL;
        *phead = newnode;
    }
    else if (p == NULL)
    {
        newnode->link = NULL;
        *phead = newnode;
    }
    else
    {
        newnode->link = p->link;
        p->link = newnode;
    }
}
 
ListNode* GetNode(ListType* list, int pos)
{
    int i;
    ListNode* tmp = list->head;
 
    if (pos < 0)
        return NULL;
 
    for (i = 0; i<pos; i++)
        tmp = tmp->link;
    return tmp;
}
 
int GetSize(ListType* list)
{
    return list->size;
}
void PrintList(ListType* list)
{
    ListNode* p = list->head;
 
    printf("(");
    while (p != NULL)
    {
        if (p->link == NULL)
            printf("%d", p->data);
        else
            printf("%d, ", p->data);
        p = p->link;
    }
    printf(")\n");
}

<main.cpp>

#include <stdio.h>
#include <stdlib.h>
#include "SingleLinkedList.h"
 
#define SWAP(a,b) {element t; t=a; a=b; b=t;}
 
 
void InsertionSorting(ListType* list, int n)
{
    ListNode* cur = list->head;
    ListNode* insertion;
 
    while (!cur==NULL)
    {
        insertion = list->head;
        
        while(1)
        {
            if (insertion == cur)
                break;
            if (insertion->data > cur->data)
                SWAP(insertion->data, cur->data);
            insertion = insertion->link;
        }
        cur = cur->link;
    }
}
int main(void)
{
    int n;
    element ar;
 
    printf("입력 데이터의 수 : ");
    scanf_s("%d", &n);
 
    ListType list;
    Init(&list);
 
    printf("배열의 내용 입력 : ");
    for (int i = 0; i < n; i++)
    {
        scanf_s("%d", &ar);
        AddNode(&list, GetSize(&list), ar);
    }
 
    printf("정렬 이전의 배열 내용 : ");
    PrintList(&list);
 
    InsertionSorting(&list, n);
 
    printf("정렬 이후의 배열 내용 : ");
    PrintList(&list);
}