Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <stdlib.h>
- #include <time.h>
- #ifndef NNODES
- #define NNODES 16
- #endif
- /*
- * non-list misc functions
- */
- /** rand_int for use with shuffle */
- static int rand_int (int n)
- {
- int limit = RAND_MAX - RAND_MAX % n, rnd;
- rnd = rand();
- for (; rnd >= limit; )
- rnd = rand();
- return rnd % n;
- }
- /** shuffle integer array of size 'n'
- * (using fisher-yates method)
- */
- void shuffle (int *a, int n)
- {
- int i, tmp;
- while (n-- > 1) {
- i = rand_int (n + 1);
- tmp = a[i];
- a[i] = a[n];
- a[n] = tmp;
- }
- }
- /*
- * list structs and functions
- */
- typedef struct node_t { /* list node */
- int data;
- struct node_t *prev, *next;
- } node_t;
- typedef struct { /* list wrapper with head & tail pointers */
- node_t *head, *tail;
- } list_t;
- /** create new node initialize all members */
- node_t *createnode (int v)
- {
- node_t *node = malloc (sizeof *node); /* allocate node */
- if (!node) { /* validate allocation */
- perror ("malloc-node");
- return NULL;
- }
- node->data = v; /* initialize members values */
- node->prev = node->next = NULL;
- return node; /* return new node */
- }
- /** add node at end of list, update tail to end */
- node_t *add (list_t *l, int v)
- {
- node_t *node = createnode (v); /* allocate node */
- if (!node) /* validate allocation */
- return NULL;
- if (!l->head) /* if 1st node, node is head/tail */
- l->head = l->tail = node;
- else { /* otherwise */
- node->prev = l->tail; /* set prev to tail */
- l->tail->next = node; /* add at end, update tail pointer */
- l->tail = node;
- }
- return node; /* return new node */
- }
- /** add node in-order */
- node_t *add_ordered (list_t *l, int v)
- {
- node_t **ppn = &l->head; /* pointer to pointer */
- node_t *pn = l->head; /* pointer to node */
- node_t *node = createnode (v); /* allocate node */
- if (!node) /* validate allocation */
- return NULL;
- if (!l->head) { /* if 1st node, node is head/tail */
- l->head = l->tail = node;
- return l->tail;
- }
- while (pn) { /* iterate over list */
- if (v < pn->data) { /* if new node goes before current */
- node->prev = (*ppn)->prev; /* set node prev to current prev */
- *ppn = node; /* set current address to node */
- pn->prev = node; /* set next->prev to current */
- node->next = pn; /* set current->next to next */
- return node;
- }
- ppn = &pn->next; /* get address of next node */
- pn = pn->next; /* get next node pointer */
- }
- node->prev = l->tail;
- l->tail->next = node; /* node goes at end, update tail pointer */
- l->tail = node;
- return node;
- }
- /** print all nodes in list */
- int prn (list_t *l)
- {
- if (!l->head) {
- puts ("list-empty");
- return 0;
- }
- for (node_t *n = l->head; n; n = n->next)
- printf (" %d", n->data);
- putchar ('\n');
- return 1;
- }
- /** print all nodes in list in reverse */
- int prnrev (list_t *l)
- {
- if (!l->tail) {
- puts ("list-empty");
- return 0;
- }
- for (node_t *n = l->tail; n; n = n->prev)
- printf (" %d", n->data);
- putchar ('\n');
- return 1;
- }
- /** delete node with value v from list (for loop) */
- int del_node (list_t *l, int v)
- {
- if (!l->head) {
- puts ("list-empty");
- return 1;
- }
- node_t **ppn = &l->head; /* pointer to pointer */
- node_t *pn = l->head; /* pointer to node */
- for (; pn; ppn = &pn->next, pn = pn->next) {
- if (pn->data == v) {
- *ppn = pn->next; /* set node at address to next */
- if (pn != l->tail) /* prev is next prev */
- (*ppn)->prev = pn->prev;
- else /* deleting tail, set tail to prev */
- l->tail = pn->prev;
- free (pn); /* free current */
- pn = NULL;
- break;
- }
- }
- return 0;
- }
- /** delete all nodes in list */
- void del_nodes (list_t *l)
- {
- node_t *n = l->head;
- while (n) {
- node_t *victim = n;
- n = n->next;
- free (victim);
- }
- l->head = l->tail = NULL;
- }
- int main (void) {
- list_t l = { NULL, NULL }; /* initialize list pointers NULL */
- int a[NNODES]; /* array to shuffle */
- srand (time (NULL)); /* seed random number generator */
- for (int i = 0; i < NNODES; i++) { /* fill array with NNODES int */
- add (&l, i+1);
- a[i] = i+1;
- }
- shuffle (a, NNODES); /* shuffle array for random removal */
- prn (&l); /* print list forward */
- prnrev (&l); /* print list reverse */
- putchar ('\n');
- for (int i = 0; i < NNODES; i++) { /* remove all nodes in random order */
- printf ("deleting : %d\n", a[i]);
- del_node (&l, a[i]); /* delete node with random value a[i] */
- if (prn (&l)) { /* print list forward if nodes remain */
- prnrev (&l); /* print list reverse if nodes remain */
- putchar ('\n'); /* tidy up with a '\n' */
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement