0

```
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
struct node {
int data;
struct node *right;
struct node *down;
};
struct list {
struct node *head;
int level;
};
/*
Naive example function
Don't use in production code
*/
int rand_level(int limit)
{
int i = 1;
while (rand() < RAND_MAX / 2 && i < limit) {
++i;
}
return i;
}
struct node *make_node(int data, struct node *right, struct node *down)
{
struct node *node = malloc(sizeof *node);
if (node == NULL) {
return NULL;
}
node->data = data;
node->right = right;
node->down = down;
return node;
}
void destroy_node(struct node *node)
{
free(node);
}
struct node *is_full(struct node *x)
{
struct node *root = NULL;
int i;
if (x->down != NULL) {
struct node *it = x->down;
for (i = 0; it != NULL && i < 3; i++) {
it = it->right;
}
if (it != NULL && i == 3) {
if ((it->right == NULL && x->right == NULL)
|| (it->right != NULL && x->right != NULL)
&& (it->right->data == x->right->data))
{
root = x->down->right->right;
}
}
}
return root;
}
int insert_node(struct list *list, int data)
{
struct node *x, *root, *node;
/* Empty list */
if (list->head == NULL) {
node = make_node(0, NULL, make_node(0, NULL, list->head));
if (node == NULL) {
return 0;
}
list->head = node;
}
/* Grow list */
if ((root = is_full(list->head)) != NULL) {
node = make_node(root->data, list->head->right, root);
if (node == NULL) {
return 0;
}
list->head->right = node;
node = make_node(0, NULL, list->head);
if (node == NULL) {
return 0;
}
list->head = node;
}
x = list->head->down;
while (x != NULL) {
while (x->right != NULL && data > x->right->data) {
x = x->right;
}
if (x->right == NULL || data != x->right->data) {
if ((root = is_full(x)) != NULL) {
node = make_node(root->data, x->right, root);
if (node == NULL) {
return 0;
}
x->right = node;
}
if (x->down == NULL) {
node = make_node(data, x->right, NULL);
if (node == NULL) {
return 0;
}
x->right = node;
break;
}
}
x = x->down;
}
return 1;
}
int remove_node(struct list *list, int data)
{
int ret = 0;
struct node *x, *save;
x = list->head->down;
while (x != NULL) {
while (x->right != NULL && data > x->right->data) {
x = x->right;
}
if (x->right != NULL && data == x->right->data) {
save = x->right;
x->right = save->right;
destroy_node(save);
ret = 1;
}
x = x->down;
}
while (list->head->down != NULL && list->head->down->right == NULL) {
save = list->head->down;
list->head->down = list->head->down->down;
destroy_node(save);
}
return ret;
}
void list_structure(struct list *list)
{
struct node *x, *y, *z;
for (x = list->head; x != NULL; x = x->down) {
for (z = list->head; z->down != NULL; z = z->down) {
}
for (y = x; y != NULL; y = y->right) {
for (; z != NULL && z->data != y->data; z = z->right) {
printf("-");
if (z->right != NULL && z->right->data != y->data) {
printf("--");
}
}
printf("%02d", y->data);
}
printf("\n");
}
}
int main(void)
{
struct list list = {0};
int i;
srand((unsigned int)time(NULL));
for (i = 0; i < 25; i++) {
int r = rand() % 99 + 1;
printf("Insert %d, returned %d\n", r, insert_node(&list, r));
list_structure(&list);
printf("\n-------------------------\n");
getchar();
}
return 0;
}
```