#include <stdio.h>
#include <stdlib.h>
typedef struct Node
{
int data;
struct Node *next;
struct Node *prev;
} Node;
Node* SortedInsert(Node *head,int data)
{
Node
*p
= malloc(sizeof(*p
)), **pp
= &head
; p->data = data;
p->prev = NULL;
while (*pp && (*pp)->data < data)
{
p->prev = *pp;
pp = &(*pp)->next;
}
// whatever *pp is, its our next pointer
p->next = *pp;
if (*pp)
(*pp)->prev = p;
// this is always set to the new node
*pp = p;
return head;
}
void print_list(const Node *head)
{
while (head)
{
if (head->prev)
printf("%d,", head
->prev
->data
); else
if (head->next)
printf("%d) ", head
->next
->data
); else
head = head->next;
}
}
void free_list(Node* head)
{
while (head)
{
Node *tmp = head;
head = head->next;
}
}
int main()
{
int ar[] = { 3,1,5,4,6,8,7,9,2 }, i;
Node *head = NULL;
// ordered insertion
for (i=1; i<=9; ++i)
head = SortedInsert(head, i);
print_list(head);
free_list(head);
head = NULL;
// reverse insertion
for (i=9; i>=1; --i)
head = SortedInsert(head, i);
print_list(head);
free_list(head);
head = NULL;
// unordered insertion
for (i=0; i<sizeof(ar)/sizeof(*ar); ++i)
head = SortedInsert(head, ar[i]);
print_list(head);
free_list(head);
head = NULL;
return 0;
}
I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdGRsaWIuaD4KCnR5cGVkZWYgc3RydWN0IE5vZGUKewogICAgaW50IGRhdGE7CiAgICBzdHJ1Y3QgTm9kZSAqbmV4dDsKICAgIHN0cnVjdCBOb2RlICpwcmV2Owp9IE5vZGU7CgpOb2RlKiBTb3J0ZWRJbnNlcnQoTm9kZSAqaGVhZCxpbnQgZGF0YSkKewogICAgTm9kZSAqcCA9IG1hbGxvYyhzaXplb2YoKnApKSwgKipwcCA9ICZoZWFkOwogICAgcC0+ZGF0YSA9IGRhdGE7CiAgICBwLT5wcmV2ID0gTlVMTDsKICAgIAogICAgd2hpbGUgKCpwcCAmJiAoKnBwKS0+ZGF0YSA8IGRhdGEpCiAgICB7CiAgICAgICAgcC0+cHJldiA9ICpwcDsKICAgICAgICBwcCA9ICYoKnBwKS0+bmV4dDsKICAgIH0KICAgIAogICAgLy8gd2hhdGV2ZXIgKnBwIGlzLCBpdHMgb3VyIG5leHQgcG9pbnRlcgogICAgcC0+bmV4dCA9ICpwcDsKICAgIGlmICgqcHApCiAgICAgICAgKCpwcCktPnByZXYgPSBwOwogICAgCiAgICAvLyB0aGlzIGlzIGFsd2F5cyBzZXQgdG8gdGhlIG5ldyBub2RlCiAgICAqcHAgPSBwOwogICAgcmV0dXJuIGhlYWQ7Cn0KCnZvaWQgcHJpbnRfbGlzdChjb25zdCBOb2RlICpoZWFkKQp7CiAgICB3aGlsZSAoaGVhZCkKICAgIHsKICAgICAgICBwcmludGYoIiVkKCIsIGhlYWQtPmRhdGEpOwogICAgICAgIAogICAgICAgIGlmIChoZWFkLT5wcmV2KQogICAgICAgICAgICBwcmludGYoIiVkLCIsIGhlYWQtPnByZXYtPmRhdGEpOwogICAgICAgIGVsc2UKICAgICAgICAgICAgcHJpbnRmKCJudWxsLCIpOwogICAgICAgIAogICAgICAgIGlmIChoZWFkLT5uZXh0KQogICAgICAgICAgICBwcmludGYoIiVkKSAiLCBoZWFkLT5uZXh0LT5kYXRhKTsKICAgICAgICBlbHNlCiAgICAgICAgICAgIHByaW50ZigibnVsbCkgIik7CiAgICAgICAgCiAgICAgICAgaGVhZCA9IGhlYWQtPm5leHQ7CiAgICB9CiAgICBwcmludGYoIlxuIik7Cn0KCnZvaWQgZnJlZV9saXN0KE5vZGUqIGhlYWQpCnsKICAgIHdoaWxlIChoZWFkKQogICAgewogICAgICAgIE5vZGUgKnRtcCA9IGhlYWQ7CiAgICAgICAgaGVhZCA9IGhlYWQtPm5leHQ7CiAgICAgICAgZnJlZSh0bXApOwogICAgfQp9CgppbnQgbWFpbigpCnsKICAgIGludCBhcltdID0geyAzLDEsNSw0LDYsOCw3LDksMiB9LCBpOwogICAgTm9kZSAqaGVhZCA9IE5VTEw7CiAgICAKICAgIC8vIG9yZGVyZWQgaW5zZXJ0aW9uCiAgICBmb3IgKGk9MTsgaTw9OTsgKytpKQogICAgICAgIGhlYWQgPSBTb3J0ZWRJbnNlcnQoaGVhZCwgaSk7CiAgICAKICAgIHByaW50X2xpc3QoaGVhZCk7CiAgICBmcmVlX2xpc3QoaGVhZCk7CiAgICBoZWFkID0gTlVMTDsKICAgIAogICAgLy8gcmV2ZXJzZSBpbnNlcnRpb24KICAgIGZvciAoaT05OyBpPj0xOyAtLWkpCiAgICAgICAgaGVhZCA9IFNvcnRlZEluc2VydChoZWFkLCBpKTsKICAgIAogICAgcHJpbnRfbGlzdChoZWFkKTsKICAgIGZyZWVfbGlzdChoZWFkKTsKICAgIGhlYWQgPSBOVUxMOwogICAgCiAgICAvLyB1bm9yZGVyZWQgaW5zZXJ0aW9uCiAgICBmb3IgKGk9MDsgaTxzaXplb2YoYXIpL3NpemVvZigqYXIpOyArK2kpCiAgICAgICAgaGVhZCA9IFNvcnRlZEluc2VydChoZWFkLCBhcltpXSk7CiAgICAKICAgIHByaW50X2xpc3QoaGVhZCk7CiAgICBmcmVlX2xpc3QoaGVhZCk7CiAgICBoZWFkID0gTlVMTDsKICAgIAogICAgcmV0dXJuIDA7Cn0=
1(null,2) 2(1,3) 3(2,4) 4(3,5) 5(4,6) 6(5,7) 7(6,8) 8(7,9) 9(8,null)
1(null,2) 2(1,3) 3(2,4) 4(3,5) 5(4,6) 6(5,7) 7(6,8) 8(7,9) 9(8,null)
1(null,2) 2(1,3) 3(2,4) 4(3,5) 5(4,6) 6(5,7) 7(6,8) 8(7,9) 9(8,null)