網頁

2011年1月8日 星期六

Linked List (5)

Sort a Linked List so that its items are arranged from small to large
void Sort1(Node **head)
{
if (head == NULL)
return;

int i, j, n, temp, swap_time;
Node *p1, *p2;
n = Length1(*head); // Bubble Sort: need to know length

for (i = 1; i <= n - 1 && swap_time; i++) { // if swap_time == 0, break and return
p1 = *head; // start to swap from the beginning of the linked list
p2 = (*head)->next;

for (j = 1, swap_time = 0; j <= n - i; j++) {
if (p1->data > p2->data) { // if p1 > p2 then swap, if p1 = p2 don't swap -> stable
temp = p2->data;
p2->data = p1->data;
p1->data = temp;
swap_time++; // count swap time
}
p1 = p1->next;
p2 = p2->next;
}
}
}

Node* Sort2(Node *head)
{
Node *p1 = head;
int cnt = 0, i, j, tmp, swap_time;
while (p1 != NULL) {
cnt++;
p1 = p1->next;
}
for (i = 1; i < cnt; i++) {
p1 = head;
swap_time = 0;
for (j = 0; j < cnt - i; j++) {
if (p1->data > p1->next->data) {
tmp = p1->data;
p1->data = p1->next->data;
p1->next->data = tmp;
swap_time++;
}
p1 = p1->next;
}
if (!swap_time)
break;
}
return head;
}

Merge 2 Linked Lists into 1, and so that its items are arranged from small to large
Node* Merge(Node *h1, Node *h2)
{
Node *new, *p1, *p2, *p3;
if ((new = (Node*)malloc(sizeof(Node))) == NULL) {
printf("fail to allocate memory\n");
return NULL;
}
p1 = h1; p2 = h2; p3 = new;
while (p1 != NULL && p2 != NULL) {
if (p1->data <= p2->data) {
p3->next = p1;
p1 = p1->next;
}
else {
p3->next = p2;
p2 = p2->next;
}
p3 = p3->next;
}
if (p1 == NULL)
p3->next = p2;
else
p3->next = p1;

p3 = new->next;
free(new);
return p3;
}

Split 1 Linked List to 2, so that all items which are larger than "pivot" go to L1, and all items which are smaller than "pivot" go to L2
void split(node *head, int pivot, node** lt, node** gt)
{
if (head == NULL)
return;

node *p1, *p2, *p3;
p1 = head;
*
lt = (node*)malloc(sizeof(node));
*
gt = (node*)malloc(sizeof(node));
p2 = lt;
p3 = gt;

while (p1 != NULL) {
if (p1->value <= pivot) {
p2->next = p1;
p2 = p2->next;
}
else {
p3->next = p1;
p3 = p3->next;
}
p1 = p1->next;
}

p2->next = NULL;
p3->next = NULL;

p2 = *lt;
p3 = *gt;
*
lt = *lt->next;
*
gt = *gt->next;

free(p2);
free(p3);
}

沒有留言:

張貼留言