Chinaunix首页 | 论坛 | 博客

丫叩酱的ChinaUnix博客yakou.blog.chinaunix.net

首页　| 　博文目录　| 　关于我

丫叩酱

  • 博客访问： 474966
  • 博文数量： 112
  • 博客积分： 2436
  • 博客等级： 大尉
  • 技术积分： 2769
  • 用 户 组： 普通用户
  • 注册时间： 2012-03-04 19:48
文章分类

全部博文（112）

文章存档

2013年（7）

2012年（105）

我的朋友
最近访客
推荐博文
相关博文
文件操作_链表_练习_0309

分类： C/C++

2012-03-22 15:37:34


点击(此处)折叠或打开

  1. //Josephus.c

  3. //链表实现约瑟夫环问题
  4. //先建立一个单链表，在其最后，tail->next = head;

  6. #include <stdio.h>
  7. #include <stdlib.h>
  8. #define PERSONS 10
  9. #define COUNTER 4

  11. typedef struct node
  12. {
  13.     int data;
  14.     struct node *next;
  15. }node_t;

  17. node_t *create(node_t *head)
  18. {
  19.     int i;
  20.     node_t *cur, *tail;

  22.     for (i = 0; i < PERSONS; i++)
  23.     {
  24.         cur = malloc(sizeof(node_t));
  25.         if(cur == NULL)
  26.         {
  27.             printf("malloc fail\n");
  28.             exit(1);
  29.         }

  31.         cur->data = i + 1;
  32.         cur->next = NULL;
  33.     
  34.         if(head == NULL)
  35.             head =tail = cur;
  36.         else
  37.         {
  38.             tail->next = cur;
  39.             tail = cur;
  40.         }
  41.     }

  43.     tail->next = head;
  44.     return head;
  45. }

  47. void Josephus(node_t *head)
  48. {
  49.     node_t *pre, *cur, *del;
  50.     int remain = PERSONS, step= 1;

  52.     pre = cur = head;
  53.     while(remain > 1 )
  54.     {
  55.         if(step != COUNTER)
  56.         {
  57.             step ++;
  58.             pre = cur;
  59.             cur = cur->next;
  60.         }
  61.         else
  62.         {
  63.             step = 1;
  64.             printf("killed %d\n", cur->data);

  66.             del = cur;
  67.             pre->next = cur = cur->next;
  68.             free(del);
  69.             remain--;
  70.         }
  71.     }

  73.     printf("\nsurvived %d\n", cur->data);
  74.     free(cur);
  75. }

  77. void show(node_t *head)
  78. {
  79.     node_t *cur;

  81.     for(cur = head; cur->next != head; cur = cur->next)
  82.     {
  83.         printf("-%d-", cur->data);
  84.     }
  85.     printf("-%d-", cur->data);
  86.     putchar('\n');
  87. }

  89. void myfree(node_t *head)
  90. {
  91.     node_t *cur, *nextp;

  93.     for(cur = head; cur->next != head; cur = nextp)
  94.     {
  95.         nextp = cur->next;
  96.         free(cur);
  97.     }
  98.     free(cur);
  99. }

  101. int main(int argc, const char *argv[])
  102. {
  103.     node_t *head = NULL;
  104.     
  105.     head = create(head);
  106.     show(head);
  107.     myfree(head);

  109.     head = NULL;
  110.     head = create(head);
  111.     Josephus(head);
  112.     return 0;
  113. }

点击(此处)折叠或打开

  1. //Josephus.c

  3. //建第一个节点时，将head->next = head; tail = head;
  4. //再将新的节点插入到tail后，tail->next = cur; cur->next = head; tail = cur;
  5. #include <stdio.h>
  6. #include <stdlib.h>

  8. #define PERSONS 10
  9. #define COUNTER 4

  11. typedef struct node
  12. {
  13.     int data;
  14.     struct node *next;
  15. }node_t;

  17. node_t *create(node_t *head)
  18. {
  19.     node_t *cur, *tail;
  20.     int i;

  22.     for(i = 0; i < PERSONS; i++)
  23.     {
  24.         cur = malloc(sizeof(node_t));

  26.         if(cur == NULL)
  27.         {
  28.             printf("malloc fail\n");
  29.             exit(1);
  30.         }

  32.         cur->data = i + 1;
  33.         if(head == NULL)
  34.         {
  35.            head = cur;
  36.            tail = head;
  37.            head->next = head;
  38.         }
  39.         else
  40.         {
  41.             tail->next = cur;
  42.             tail = cur;
  43.         }
  44.         cur->next = head;
  45.     }

  47.     return head;
  48. }

  50. void Josephus2(node_t *head)
  51. {
  52.     node_t *pre, *cur, *del;
  53.     int remain = PERSONS, step = 1;

  55.     pre = cur = head;
  56.     while(remain > 1)
  57.     {
  58.         if(step != COUNTER)
  59.         {
  60.             step ++;
  61.             pre = cur;
  62.             cur = cur->next;
  63.         }
  64.         else
  65.         {
  66.             remain --;
  67.             step = 1;
  68.             printf("kill %d\n", cur->data);

  70.             del = cur;
  71.             pre->next = cur = cur->next;
  72.             free(del);
  73.         }
  74.     }
  75.     printf("\nsurvived %d\n", cur->data);
  76.     free(cur);
  77. }

  79. void show(node_t *head)
  80. {
  81.    node_t *cur;
  82.    for(cur = head; cur->next != head; cur = cur->next)
  83.    {
  84.         printf("-%d-", cur->data);
  85.    }
  86.    printf("-%d-", cur->data);
  87.    putchar('\n');
  88. }

  90. void myfree(node_t *head)
  91. {
  92.     node_t *cur, *nextp;

  94.     for(cur = head; cur->next != head; cur = nextp)
  95.     {
  96.         nextp = cur->next;
  97.         free(cur);
  98.     }
  99.     free(cur);
  100. }
  101. int main(void)
  102. {
  103.     node_t *head = NULL;

  105.     head = create(head);
  106.     show(head);
  107.     myfree(head);

  109.     head = NULL;
  110.     head = create(head);
  111.     Josephus2(head);
  112.     return 0;
  113. }

点击(此处)折叠或打开

  1. //is_ring_link.c

  3. //判断一个链表是否有环

  5. #include <stdio.h>
  6. #include <stdlib.h>

  8. #define NUM 10

  10. typedef struct node
  11. {
  12.     int data;
  13.     struct node *next;
  14. }node_t;

  16. node_t *create(node_t *head)
  17. {
  18.     node_t *cur, *tail;
  19.     int i;

  21.     for(i = 0; i < NUM; i++)
  22.     {
  23.         cur = malloc(sizeof(node_t));
  24.         if(cur == NULL)
  25.         {
  26.             printf("malloc fail\n");
  27.             exit(1);
  28.         }

  30.         cur->data = i + 1;

  32.         if(head == NULL)
  33.             head = tail = cur;
  34.         else
  35.         {
  36.             tail->next = cur;
  37.             tail = cur;
  38.         }
  39.         cur->next = NULL;
  40.     }
  41.     cur->next = head;

  43.     return head;
  44. }

  46. void is_ring(node_t *head)
  47. {
  48.     node_t *pre, *cur;

  50.     pre = cur = head;
  51.     while(1)
  52.     {
  53.         pre = pre->next;
  54.         cur = cur->next->next;

  56.         if(pre == NULL || cur == NULL)
  57.         {
  58.             printf("no ring\n");
  59.             break;
  60.         }
  61.         if(pre == cur)
  62.         {
  63.             printf("is ring\n");
  64.             break;
  65.         }
  66.     }

  68. }

  70. void show(node_t *head)
  71. {
  72.     node_t *cur;
  73.     for(cur = head; cur->next != head; cur = cur->next)
  74.     {
  75.         printf("-%d-", cur->data);
  76.     }
  77.     printf("-%d-\n", cur->data);
  78. }

  80. void myfree(node_t *head)
  81. {
  82.     node_t *cur, *nextp;

  84.     for(cur = head; cur->next != head; cur = nextp)
  85.     {
  86.         nextp = cur->next;
  87.         free(cur);
  88.     }
  89.     free(cur);
  90. }
  91. int main(int argc, const char *argv[])
  92. {
  93.     node_t *head = NULL;

  95.     head = create(head);
  96.     is_ring(head);
  97.     show(head);
  98.     myfree(head);
  99.     return 0;
  100. }

阅读(813) | 评论(0) | 转发(2) |
0

上一篇：文件操作_练习_0305

下一篇：排序_查找 _0310

给主人留下些什么吧！~~
关于我们 | 关于IT168 | 联系方式 | 广告合作 | 法律声明 | 免费注册

Copyright 2001-2010 ChinaUnix.net All Rights Reserved 北京皓辰网域网络信息技术有限公司. 版权所有

感谢所有关心和支持过ChinaUnix的朋友们

16024965号-6