#5. 단순연결리스트를 이용한 정렬리스트 만들기

문제

단순연결리스트를 이용해서 숫자를 삽입할 때 마다 오름차순으로 정렬되게 끔 하는 간단한 프로그램을 만드시오.

조건: 아래의 추상 자료형(ADT) 함수를 모두 이용하여 5개이상의 원소를 삽입할 것

풀이

중요한 부분이 총 3가지라고 생각합니다. (글로는 설명이 힘들어서 소스코드만 올립니다..)

1. 삽입함수

정확한 이해가 필요했습니다. 삽입할 때 마다 정렬되게끔 하려면 몇가지 경우를 고려해야하는데 ,

작은 단위( 원소가 하나일 때, 두개 일 때, 3개일 때 ..) 부터 노트에 그려서 규칙을 찾아보면 의외로 간단합니다.

2. 삭제함수

Delete함수는 대충 책에서도 비슷하게 설명이 되있기 때문에 조금만 생각해보면 되지만 Clear함수는 원소를 삭제하면서 

그 위치를 기억하는 temp변수가 필요하다는 아이디어를 구현하는데 시간을 많이 썼습니다. 

단순히 removed함수만을 이용해서 삭제과정을 거치면 free하는 과정에서 연결리스트가 끊겨버리므로 실행 시 오류가 뜹니다.

3. 리스트의 원소갯수 반환 함수

원소갯수를 필요로하는 함수에 인자로 len을 추가시켜서 즉각즉각 갱신하도록했습니다.

ListNode 구조체에 len변수를 추가하여 사용해보려고 했는데 잘 안풀려서 다시 한번 고민을 해봐야겠습니다.

코드

#pragma warning(disable:4996)
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct ListNode
{
    double data;
    struct ListNode* link;
}ListNode;
void Add(ListNode**list,double item)
{
    ListNode* temp = (ListNode*)malloc(sizeof(ListNode));
    temp->data = item; temp->link = NULL;
    ListNode* pos = *list;
    if (*list == NULL) {
        *list = temp;
    }
    //같은것도 삽입해야하므로"="붙여야함!
    else if (temp->data <= (*list)->data)
        {
        temp->link = *list;
        *list = temp;
        }
    else
    {
        while (1)
        {
             if (pos->link == NULL)
            {
                pos->link = temp;break;
            }
            else if (temp->data < pos->link->data)
            {
                temp->link = pos->link;
                pos->link = temp;
                break;
            }
            //어떤 경우도 아닐 때 ex) 3 4 5 7일때 6삽입
            pos = pos->link;
        }
    }
}
void Delete(ListNode** list, double item,int len)
{
    ListNode* removed;
    if ((*list)->link == NULL)
    {
        free((*list));
        *list = NULL;
    }
    else if ((*list)->data == item)
    {
        removed = *list;
        *list = (*list)->link;
        free(removed);
    }
    else {
        ListNode* pre = *list;
        for (pre; pre->link->data != item; pre = pre->link);
         removed = pre->link;
        pre->link = removed->link;
        free(removed);
    }
    len--;
    
}
void Clear(ListNode** list, int len)
{
    ListNode* removed;
        ListNode* temp = *list;
        while (1)
        {
            removed = temp;
            if (removed == NULL)break;
            *list = (*list)->link;
            temp = temp->link;
            free(removed);
            
        }
}
ListNode* is_in_list(ListNode* list, double item)
{
    ListNode* temp = list;
    for (temp; temp != NULL; temp = temp->link)
        if (temp->data == item)
            return temp;
 
        return temp;
}
int get_length(ListNode* list)
{
    int len = 0;
    ListNode* temp = list;
    for (temp; temp != NULL; temp = temp->link)
        len++;
    return len;
}
int is_empty(ListNode* list)
{
    return list == NULL;
}
void display(ListNode* list)
{
    ListNode* temp = list;
    for (temp; temp != NULL; temp = temp->link)
        printf("%.0lf ", temp->data);
        printf("\n");
}
int main()
{
    double item;
    int len = 0;
    ListNode* head = NULL;
    ListNode* temp = NULL;
    //비었는지 검사, 1:비어있음 0:비어있지않음
    printf("리스트가 비었는지 검사: %d\n", is_empty(head));
    //최초에 무작위숫자 7개를 오름차순으로삽입시킴
    printf("7개의 원소를 삽입합니다.\n");
    for (int i = 0; i < 7; i++) {
        scanf("%lf", &item);
        Add(&head, item);
    }
    printf("리스트의 길이를 출력합니다.%d\n",get_length(head));
    printf("리스트의 모든 요소를 출력합니다.\n");
    display(head);
    //특정 값이 리스트에 있는지 탐색해본다.
        printf("리스트에 존재하는지 조사할 숫자: ");
        scanf("%lf", &item);
        temp = is_in_list(head,item);
        if (temp == NULL)printf("없음\n");
        else printf("%.0lf이(가)있습니다.\n", temp->data);
    
    //리스트에있는 원소중 한개 제거
        printf("리스트의 원소 중 제거하고 싶은 숫자: ");
        scanf("%lf", &item);
        temp = is_in_list(head, item);
        if (temp == NULL)printf("없음\n");
        else
        {
            Delete(&head, temp->data,len);
            printf("제거되었습니다.\n");
        }
        //삭제하고 나서 요소 확인
        printf("리스트의 모든 요소를 출력합니다.\n");
        display(head);
        printf("남아있는 원소의 갯수는 %d개입니다.\n", get_length(head));
        //모두 제거하기 
        printf("리스트의 원소를 모두 제거하겠습니다.\n");
        Clear(&head,len);
        printf("리스트에 남아있는 원소를 출력합니다.\n");
        display(head);
        
        printf("리스트가 비었는지 검사: %d\n", is_empty(head));
}

결과