include stdio include stdlib struct elem struct elem prev next int str

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <stdio.h>
#include <stdlib.h>
struct elem
{
struct elem *prev, *next;
int v;
};
struct elem* initdoublelinkedlist()
{
struct elem *list = (struct elem*)malloc(sizeof(struct elem));
list -> prev = list;
list -> next = list;
}
void insertafter(struct elem *x, struct elem *y)
{
struct elem *z;
z = x -> next;
x -> next = y;
y -> prev = x;
y -> next = z;
z -> prev = y;
}
void delete(struct elem *x)
{
struct elem *y, *z;
y = x -> prev,
z = x -> next;
y -> next = z;
z -> prev = y;
x -> prev = NULL;
x -> next = NULL;
}
void insert_sort(struct elem *x)
{
struct elem *y;
struct elem *z;
y = x -> next -> next;
while(y != x) {
z = y -> prev;
while(z != x && y -> v < z -> v) {
z = z -> prev;
}
delete(y);
insertafter(z, y);
y = y -> next;
}
}
int main()
{
struct elem *x = initdoublelinkedlist();
struct elem *y;
int i, n;
scanf("%d", &n);
scanf("\n");
for (i = 0; i < n; i ++) {
y = initdoublelinkedlist();
scanf("%d", &y -> v);
insertafter(x, y);
}
insert_sort( x );
y = x -> next;
while (y != x) {
printf("%d ", y -> v);
printf("\n");
y = y -> next;
}
y = x -> next;
while (y != x) {
free(y);
y = y -> next;
}
free(x);
return 0;
}