연결리스트에서 정렬하기...
글쓴이: hurryon / 작성시간: 토, 2003/09/13 - 2:42오후
냠냠...오래간만에 자료구조 책을 열어 놓고 보고 있습니다만...역시 어렵네요. 아마도...머리가 영...
단순 연결리스트입니다. 단순 연결리스트로 만들어진 녀석들을 정렬하고 싶은데...잘 안되네요. 오름차순이든 내림차순이든 정렬해 보려고 하는데...아마도 응용력이 상당히 떨어지는 듯.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/time.h>
struct data
{
int index;
int number;
struct data *next;
};
typedef struct data link;
typedef link *node;
node head;
int get_random()
{
unsigned char ran, mask, i;
struct timeval now_time;
ran = 0;
for(i = 0 ; i < 1 ; i++)
{
gettimeofday(&now_time, 0);
mask = now_time.tv_usec / 2;
mask <<= i;
ran |= mask;
}
return(ran);
}
void node_init()
{
node tmp;
int i;
printf("Function: %s Start!\n", __func__);
for(i = 0; i < 10; i++)
{
tmp = (link *)malloc(sizeof(link));
if(tmp == NULL)
{
fprintf(stdout, "Out of memory, node_init\n");
exit(1);
}
else
{
tmp->index = i;
tmp->number = get_random();
printf("index: %2d number: %4d\n", tmp->index, tmp->number);
tmp->next = head;
head = tmp;
}
}
}
void node_sort()
{
node previous;
node current;
struct data *next;
previous = NULL;
current = head;
printf("Function: %s Start!\n", __func__);
while(current != NULL)
{
if(previous == NULL)
{
previous = current;
}
else
{
if(previous->number > current->number)
{
printf("%d %d\n", previous->number, current->number);
next = current->next;
previous->next = next;
current->next = previous->next;
current = current->next;
}
else
{
current = current->next;
}
}
}
}
void node_print()
{
node tmp;
tmp = head;
printf("Function: %s Start!\n", __func__);
while(tmp != NULL)
{
printf("index: %2d number: %4d\n", tmp->index, tmp->number);
tmp = tmp->next;
}
}
int main()
{
if((head = (link *)malloc(sizeof(link))) == NULL)
{
fprintf(stdout, "Out of memory\n");
exit(1);
}
head = NULL;
node_init();
node_print();
node_sort();
node_print();
return(0);
}
결과는 다음과 같이 나옵니다.
[hurryon@localhost ~/c/0909]$ ./simple_link Function: node_init Start! index: 0 number: 114 index: 1 number: 236 index: 2 number: 88 index: 3 number: 193 index: 4 number: 42 index: 5 number: 146 index: 6 number: 12 index: 7 number: 119 index: 8 number: 224 index: 9 number: 72 Function: node_print Start! index: 9 number: 72 index: 8 number: 224 index: 7 number: 119 index: 6 number: 12 index: 5 number: 146 index: 4 number: 42 index: 3 number: 193 index: 2 number: 88 index: 1 number: 236 index: 0 number: 114 Function: node_sort Start! 72 12 72 42 Function: node_print Start! index: 9 number: 72 index: 3 number: 193 index: 2 number: 88 index: 1 number: 236 index: 0 number: 114 [hurryon@localhost ~/c/0909]$
으흠. 이중 연결리스트로 해결하는 방법을 원하는게 아닙니다. 흐.
Forums:
퀵소트를 이용해서 짜봤습니다.[code:1]node quickso
퀵소트를 이용해서 짜봤습니다.
node quicksort_helper(node h) { node pivot = h; node left=NULL,right=NULL; if(pivot==NULL) return NULL; h = h->next; while(h!=NULL) { node *which_side; node tmp; if(h->number > pivot->number) which_side = &right; else which_side = &left; tmp = h; h = h->next; tmp->next = *which_side; *which_side = tmp; } left = quicksort_helper(left); right = quicksort_helper(right); pivot->next = right; if(left==NULL) h = pivot; else { h = left; while(left->next!=NULL) left = left->next; left->next = pivot; } return h; } void node_quicksort() { head = quicksort_helper(head); }리스트 크기가 별로 크지 않다면 insertion sort도 괜찮을 것 같네요.
댓글 달기