연결리스트 - 정렬

#include <stdio.h> 

#include <string.h> 

#include <stdlib.h>

// 노드 구조체를 node로 재정의

typedef struct node node;

// 노드 구조체의 포인터 pnode

typedef struct node *pnode;

// 노드 구조체 값, 다음 구조체 포인터 next 

struct node { 

    int   value; 

    pnode next; 

}; 

// 연결리스트 구조체를 List로 재정의

typedef struct nodeList List;

// 연결리스트 구조체의 포인터 pList

typedef struct nodeList *pList;

// 연결리스트 구조체 : head와 tail을 가지고 있다.

struct nodeList {

    pnode head;

    pnode tail;

};  

// 새노드를 만들고 포인터를 NULL로 초기화 시킨다.

pnode makeNode();

// 노드들은 입력받은 순서대로 되어있다.

void insertNode(pList);

// 오름차순으로 정렬한다. 

void sortList(pList); 

// 리스트를 보여준다.

void showList(pList); 

// 모든 노드들을 삭제한다.

void quitList(pList); 

int main() { 

    // 노드 리스트 list

    pList list;

    // 메뉴선택을 위한 변수, 7을 입력하면 종료한다.

    // 리스트를 초기화한다. 더미 노드를 한개 만들어서 head와 tail이 이 노드를 가리키게 한다.

    // 이렇게 해서 항상 실제로 가리키기를 원하는 노드 보다 앞의 노드를 가지고 찾아다니면

    // 어떤 위치에서든디 삽입과 삭제를 할 수 있다.

    // 또 이중 포이터를 사용해야하는 번거러움을 피할 수가 있다.

    // head는 리스트의 시작하는 노드(항상 더미노드)를 가리킨다.

    // tail은 리스트의 맨 마지막 노드를 가리킨다. 처음에는 더미노드를 가리키다가,

    // 실제로 노드가 삽입되면 가장 나중에 삽입된 노드를 가리키게 된다.

    // tail 을 이용해서 우리는 새로 삽입되는 노드를 가장 뒤에 바로 삽일할 수 있다.

    list=(pList)malloc(sizeof(List));

    list->head=makeNode();

    list->tail=list->head;

    insertNode(list); 

    showList(list);

    sortList(list); 

    showList(list); 

    quitList(list); 

    // 마지막으로 list를 free시킨다.

    free(list);

    return 0;

} 

// 새노드를 만든다.

pnode makeNode() { 

    pnode p;

    p=(pnode)malloc(sizeof(node));

    p->value=0;

    p->next=NULL;

    return p;

}

// 수를 계속 입력받아 새노드를 삽입한다.

void insertNode(pList list) {

    pnode t=list->head; 

    pnode newnode; 

    int x;

    

    while(1) {

        printf("정수입력 : "); 

        scanf("%d", &x);

        // -1을 입력하면 입력을 끝낸다.

        if(x==-1) break;

        newnode = makeNode();

        newnode->value=x;

        list->tail->next=newnode;

        list->tail=newnode;

    }

} 

// 오름차순 정렬을 한다.

void sortList(pList list) {

    pnode first = list->head;

    pnode rest;

    pnode s, t=NULL;

    if(first->next!=NULL) {

        t=first->next->next;

    } 

    first->next->next=NULL;

    // 리스트의 길이가 0인 경우

    if(t==NULL) return;

    rest=t->next;

    t->next=NULL;

 

    while(t) {

        s=first;

        while(s->next) {

            if(t->value<s->next->value) {

                t->next=s->next;

                s->next=t;

                t=rest;

                if(rest) rest=rest->next;

                if(t) t->next=NULL;

                break;

            } else {

                s=s->next;

            }

        }

        if(s->next==NULL) {

            s->next=t;

            t=rest;

            if(rest) rest=rest->next;

            if(t) t->next=NULL;

        }

    }

} 

// 전체 리스트를 출력한다.

void showList(pList list) {

    pnode t = list->head; 

    while(t->next) {

        printf("%d ", t->next->value); 

        t = t->next; 

    } 

    printf("\n");

} 

// 리스트의 모든 노드를 삭제한다.

void quitList(pList list) { 

    pnode t=list->head;

    pnode temp;

  

    t=t->next;

    while(t) {

        temp = t;

        t=t->next; 

        free(temp); 

    } 

    free(list->head);

}