fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <assert.h>
  4. /* #define DEBUG*/
  5. #if defined(DEBUG)
  6. #include "qzmalloc.h"
  7. #else
  8. #define qzmallocdump()
  9. #define qzmalloc(a, b) malloc(a)
  10. #define qzfree(a, b) free(a)
  11. #endif
  12.  
  13.  
  14. #define ID_NODE 1001
  15. #define ID_DATA 1002
  16.  
  17. /*=========================================================================*/
  18. /* 双方向リスト*/
  19. struct node {
  20.   void *data;
  21.   struct node *next;
  22.   struct node *before;
  23. };
  24. /*=========================================================================*/
  25.  
  26. int add_node(struct node **root, void *data) {
  27.   struct node *new_node;
  28.   if (root == 0)
  29.     return 0;
  30.   if (*root == 0) {
  31.     if ((new_node = qzmalloc(sizeof(struct node), ID_NODE)) != 0) {
  32.       new_node->next = new_node->before = new_node;
  33.       *root = new_node;
  34.       new_node->data = data;
  35.       return 1;
  36.     } else {
  37.       return 0;
  38.     }
  39.   } else {
  40.     if ((new_node = qzmalloc(sizeof(struct node), ID_NODE)) != 0) {
  41.       (*root)->before->next = new_node;
  42.       new_node->before = (*root)->before;
  43.       (*root)->before = new_node;
  44.       new_node->next = *root;
  45.       (*root) = new_node;
  46.       new_node->data = data;
  47.       return 1;
  48.     } else
  49.       return 0;
  50.   }
  51. }
  52.  
  53. void dump(struct node *root, void (*dump_data)(void *)) {
  54.   if (root == 0) {
  55.     printf("<null>\n");
  56.     return;
  57.   }
  58.   if (root != 0) {
  59.     struct node *p = root;
  60.     do {
  61.       if (p->data) (*dump_data)(p->data);      
  62.       assert(p->next->before == p);
  63.       assert(p->before->next == p);
  64.       p = p->next;
  65.     } while (p != root);
  66.   }
  67.   putchar('\n');
  68. }
  69.  
  70. void release(struct node **root, void(*release_data)(void *)) {
  71.   if (*root == 0)
  72.     return;
  73.   struct node *p = *root, *q;
  74.   do {
  75.     if (p->data != 0) {
  76.       release_data(p->data);
  77.       p->data = 0;
  78.     }
  79.     p->next->before = 0;
  80.     p->before = 0;
  81.     q = p;
  82.     p = p->next;
  83.     q->next = 0;
  84.     qzfree(q, ID_NODE);
  85.   } while (p != *root);
  86.   *root = 0;
  87. }
  88.  
  89.  
  90. struct node *search(struct node *root, int (*cmp_data)(void *, void *), void *data) {
  91.   if (root == 0)
  92.     return 0;
  93.   struct node *p = root;
  94.   do {
  95.     if ((*cmp_data)(p->data, data) == 1)
  96.       return p;
  97.     p = p->next;
  98.   } while (p != root);
  99.   return 0;
  100. }
  101.  
  102. /*=========================================================================*/
  103. /* リンクリストの要素数にかかわらず、O(1) でノードを削除する */
  104. void delete(struct node **root, struct node *del_node, void (*release_data)(void *)) {
  105.   if (root == 0)
  106.     return;
  107.   if (*root != del_node) {
  108.     del_node->before->next = del_node->next;
  109.     del_node->next->before = del_node->before;
  110.     del_node->next = del_node->before = 0;
  111.     release_data(del_node->data);
  112.     del_node->data = 0;
  113.     qzfree(del_node, ID_NODE);
  114.     del_node = 0;
  115.   } else {
  116.     assert(del_node == *root);
  117.     del_node = del_node->next;
  118.     (*root)->before->next = (*root)->next;
  119.     (*root)->next->before = (*root)->before;
  120.     (*root)->next = (*root)->before = 0;
  121.     release_data((*root)->data);
  122.     (*root)->data = 0;
  123.     qzfree(*root, ID_NODE);
  124.     if (del_node == *root) {
  125.       *root = 0;
  126.     } else {
  127.       *root = del_node;
  128.     }
  129.   }
  130. }
  131. /*=========================================================================*/
  132. int add_node_data(struct node **root, int data) {
  133.   int *data_pack;
  134.   if ((data_pack = qzmalloc(sizeof(struct node), ID_DATA)) != 0) {
  135.   } else {
  136.  
  137.     fprintf(stderr, "Cannnot allocate data-area.\n");
  138.     return 0;
  139.   }
  140.   *data_pack = data;
  141.   if (add_node(root, data_pack) == 0) {
  142.     fprintf(stderr, "Cannnot allocate node.\n");
  143.     qzfree(data_pack, ID_DATA);
  144.     return 0;
  145.   }
  146.   return 1;
  147. }
  148.  
  149. void dump_data(int *data_pack) { printf("<%d>", *data_pack); fflush(stdout); }
  150. void release_data(int *data_pack) { qzfree(data_pack, ID_DATA); }
  151. int cmp_data(int *a, int *b) { return (a == 0) ? 0 : (b == 0) ? 0 : (*a == *b) ? 1 : 0; }
  152.  
  153. int main() {
  154.   struct node *root = 0;
  155.   int data_set[] = {31, 41, 59, 26, 53, 58, 97, 93, 23, 84, 62, -1};
  156. /*  int data_set[] = {62, -1}; */
  157.   for (int i = 0; data_set[i] > 0; i++) {
  158.     printf("add data: %d\n", data_set[i]);
  159.     add_node_data(&root, data_set[i]);
  160.   }
  161.   dump(root, (void (*)(void *))dump_data);
  162.  
  163.   /*-----------------------------------------------------*/
  164.   /* 削除するノードを探す。この部分は O(N) なのは当然である. */
  165.  
  166.   struct node *node;
  167.   int target = 62;
  168.   if ((node = search(root, (int (*)(void *, void *))cmp_data, &target)) != 0) {
  169.     printf("found & deleting! : %d\n", *(int *)node->data);
  170.   } else {
  171.     printf("not found..\n");
  172.   }
  173.  
  174.   /*-----------------------------------------------------*/
  175.   /* リンクリストの要素数にかかわらず、O(1) でノードを削除する */
  176.   delete(&root, node, (void (*)(void *))release_data);
  177.  
  178.   /*-----------------------------------------------------*/
  179.   dump(root, (void (*)(void *))dump_data);
  180.  
  181.   release(&root, (void (*)(void *))release_data);
  182.   qzmallocdump();
  183.   return 0;
  184. }
  185. /* end */
  186.  
Success #stdin #stdout 0s 5380KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
add data: 31
add data: 41
add data: 59
add data: 26
add data: 53
add data: 58
add data: 97
add data: 93
add data: 23
add data: 84
add data: 62
<62><84><23><93><97><58><53><26><59><41><31>
found & deleting! : 62
<84><23><93><97><58><53><26><59><41><31>
https://ideone.com/xnPCz0
language:
C (gcc 8.3)
created:
2 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!