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