blob: b4d58363434a1f74070dd1d8be8f04864004e091 (
plain) (
blame)
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
|
/*
* Train represented using linked list by lisp-like constructs.
* This is free and unencumbered software released into the public domain.
*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "construct.h"
#define N 7
#define LEN_MAX 42
#define PSNGR_MAX 5 /* this raises the chance of empty vehicle */
struct vehicle {
int passengers;
char *name;
};
void free_vehicle(struct vehicle *v)
{
free(v->name);
free(v);
}
struct vehicle *mkvehicle(int passengers, char *name)
{
struct vehicle *v = malloc(sizeof(struct vehicle));
v->passengers = passengers;
v->name = name;
return v;
}
struct vehicle *rand_vehicle()
{
int len = rand() % LEN_MAX + 2; /* avoid empty name */
char *name = malloc(len--);
for (int j = 0; j < len; ++j)
name[j] = 'a' + rand() % 26;
name[len] = 0;
return mkvehicle(rand() % PSNGR_MAX, name);
}
void print_vehicle(struct vehicle *v)
{
printf("%s (%d passengers)\n", v->name, v->passengers);
}
void print_train(construct *train)
{
if (train == NULL)
return;
print_vehicle(car(train));
print_train(cdr(train));
}
/* Remove empty vehicles */
construct *optimize_train(construct *train)
{
if (train == NULL)
return NULL;
struct vehicle *first = car(train);
construct *rest = cdr(train);
free(train);
if (first->passengers)
return cons(first, optimize_train(rest));
free_vehicle(first);
return optimize_train(rest);
}
int main()
{
construct *train = NULL;
srand(time(NULL));
for (int i = 0; i < N; ++i)
train = cons(rand_vehicle(), train);
puts("Initial train:");
print_train(train);
putchar(10);
train = optimize_train(train);
puts("Optimized train:");
print_train(train);
putchar(10);
int index = rand() % length(train);
struct vehicle *v = rand_vehicle();
while (!v->passengers) {
free(v);
v = rand_vehicle();
}
train = insert(v, train, index);
printf("Train after inserting a new one at index %d:\n", index);
print_train(train);
return 0;
}
|
