双向链表遍历

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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef struct Node {
int data;
struct Node* next, * pre;
}Node;
typedef struct DList {
Node head;
int length;
}DList;
Node* getNewNode(int val) {
Node* p = (Node*)malloc(sizeof(Node));
p->data = val;
p->next = p->pre = NULL;
return p;
}
DList* init_list() {
DList* l = (DList*)malloc(sizeof(DList));
l->head.next = NULL;
l->length = 0;
return l;
}
int insert(DList* l, int ind, int val) {
if (l == NULL) return 0;
if (ind < 0 || ind > l->length) return 0;
Node* p = &(l->head), * node = getNewNode(val);
while (ind--) p = p->next;
node->next = p->next;
p->next = node;
node->pre = p;
if (node->next != NULL) node->next->pre = node;
l->length += 1;
return 1;
}
void l_output(DList* l) {
if (l == NULL) return;
printf("l_output(%d) : ", l->length);
for (Node* p = l->head.next; p; p = p->next) {
printf("%d->", p->data);
}
printf("NULLn");
return;
}
void r_output(DList* l) {
if (l == NULL) return;
printf("r_output(%d) : ", l->length);
int ind = l->length;
Node* p = &(l->head);
while (ind--)
p = p->next;
for (; p != &(l->head); p = p->pre) {
printf("%d->", p->data);
}
printf("headn");
return;
}
int erase(DList* l, int ind) {
if (l == NULL) return 0;
if (ind < 0 || ind >= l->length) return 0;
Node* p = &(l->head), * q;
while (ind--) p = p->next;
q = p->next;
p->next = q->next;
if (q->next != NULL) q->next->pre = p;
free(q);
l->length -= 1;
return 1;
}
void clear(DList* l) {
if (l == NULL) return;
Node* p = l->head.next, * q;
while (p != NULL) {
q = p->next;
free(p);
p = q;
}
free(l);
return;
}
int main() {
srand(time(0));
#define MAX_OP 20
DList* l = init_list();
for (int i = 0; i < MAX_OP; i++) {
int op, ind, val;
op = rand() % 4;
ind = rand() % (l->length + 3) - 1;
val = rand() % 100;
switch (op) {
case 0:
case 1:
case 2:
printf("insert %d at %d to list
= %dn", val, ind, insert(l, ind, val));
break;
case 3:
printf("erase a item at %d from list = %dn", ind, erase(l, ind));
}
l_output(l);
r_output(l);
}
return 0;
}