자료구조: 삽입정렬 - C를 이용하여 연결 리스트 상에서 구현

C를 이용하여 연결 리스트 상에서 구현한 삽입정렬

○ 소스코드

#define NULL '\0'

typedef struct _node *listptr;
typedef struct _node
{
int data;
listptr link;
} node;


void push(listptr* head, int data)
{
listptr tmp;
tmp = (listptr)malloc(sizeof(node));
tmp->data = data;

if (*head)
{
tmp->link = *head;
*head = tmp;
}
else
{
*head = tmp;
tmp->link = NULL;
}
}

void bulidList(listptr *head, int n)
{
int i;
for (i=0; i<n; i++)
{
push(head,i);

}
}

void printListAll(listptr head)
{
printf("head");
  while(1)
{
if (head == NULL)
{
printf("-||\n");
break;
}
else
{
printf("->%d",head ->data);
}
head = head->link;
}
}












void sortedInsertver1(listptr *head, listptr newNode)
{
listptr current = *head;
printf("processing node data is %d\n",newNode->data);
if (*head == NULL || (*head)->data >= newNode->data )
{
newNode->link = *head;
*head = newNode;
}
else
{
while(current->link != NULL && (current->link < newNode->data))
{
current = current->link;
}
newNode->link = current->link;
current->link = newNode;
}
}


void insertSort(listptr *head)
{
listptr current = *head;
listptr result = NULL;
listptr next;

while(current != NULL)
{
next= current->link;
sortedInsertver1(&result, current);
printListAll(result);
current = next;
}

*head = result;
}


int main()
{
int n = 6;
int i, count;

listptr head = NULL;
listptr tmp;

bulidList(&head, n);
printListAll(head);


tmp = (listptr)malloc(sizeof(node));
tmp->data = 100;
tmp->link = NULL;
sortedInsert(&head, tmp);
printListAll(head);

insertSort(&head);

printListAll(head);

return 0;
}