[关闭]
@coder-pig 2019-05-31T14:06:44.000000Z 字数 2442 阅读 1986

小猪的数据结构辅助教程——2.6 经典例子:魔术师发牌问题和拉丁方阵问题

数据结构


本节引言:

本节继续带来的是循环链表的两个经典例子,分别是魔术师发牌问题和拉丁方阵问题!


1.魔术师发牌问题

问题描述

魔术师利用一副牌中的13张黑桃牌,预先将他们排好后叠放在一起,牌面朝下。对观众说:“我不看牌,只数数就可以次熬到每张牌是什么,我大声数数,你们听,不信?现场演示。”魔术师将牌堆最上面的哪张排数为1,把他翻过来正好是黑桃A,将黑桃A从牌堆抽出放在桌子上,第二次数1、2,将第一张放在牌堆最下面,第二张翻开,正好是黑桃2,也将它抽出放在桌子上。这样依次进行将13将牌全部翻出,准确无误。问牌最开始的顺序是怎样排的。
简单点说:把13张牌按照一定的顺序排好,然后依次取牌,将每次取到的牌放在最下面,情形如下:
数一次,取牌,黑桃1,放牌堆最下面
数两次,取牌,黑桃2,放牌堆最下面
数三次,取牌,黑桃3,放牌堆最下面
数四次,取牌,黑桃4,放牌堆最下面
...直到取到最后的黑桃13(黑桃K),表演结束!

问题思路

这里我们可以用到循环链表,先初始化13个结点,全设置为0,然后开始数数,数到对应的结点,判断是否
为0,为0的话插牌,不为0的话,继续后移!一时半伙也说不清楚,用表格阐述下吧,可能更容易理解

代码实现

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #define CARD_NUM 13
  4. typedef struct LNode
  5. {
  6. int data;
  7. struct LNode *next;
  8. }LNode;
  9. typedef struct LNode *LinkList;
  10. //定义一个初始化链表的方法
  11. LinkList ListCreate()
  12. {
  13. LinkList head = NULL,p,q = head;
  14. int i;
  15. for(i = 1;i <= CARD_NUM;i++)
  16. {
  17. p = (LinkList)malloc(sizeof(LNode));
  18. p ->data = 0;
  19. if(head == NULL)head = p;
  20. else q ->next = p;
  21. q = p;
  22. }
  23. q ->next = head;
  24. return head;
  25. }
  26. //计算发牌顺序(核心)
  27. void deal(LinkList L)
  28. {
  29. LinkList p;
  30. int j;
  31. int countNum = 2; //记录当前应该到哪张牌
  32. p = L;
  33. p ->data = 1; //第一张牌嘛,肯定是1
  34. while(1)
  35. {
  36. for(j = 0;j <countNum;j++)
  37. {
  38. p = p ->next;
  39. if(p ->data != 0) //不为0说明这个位置已经有牌了,后移
  40. {
  41. p ->next;
  42. j--;
  43. }
  44. }
  45. if(p->data == 0) //不为0说明这个位置没牌,那么将牌插入,牌+1
  46. {
  47. p ->data = countNum;
  48. countNum++;
  49. if(countNum == 14)break; //13张牌放置完毕,退出循环
  50. }
  51. }
  52. }
  53. int main()
  54. {
  55. LinkList p = NULL;
  56. int i;
  57. p = ListCreate();
  58. deal(p);
  59. printf("牌的放置顺序为:\n\n");
  60. for(i = 0;i < CARD_NUM;i++)
  61. {
  62. printf("黑桃%d\t",p ->data);
  63. p = p ->next;
  64. }
  65. printf("\n\n");
  66. return 0;
  67. }

运行截图


2.拉丁方阵问题

问题描述

拉丁方阵是一种n×n的方阵,方阵中恰有n种不同的元素,每种元素恰有n个,
并且每种元素在一行和一列中恰好出现一次。著名数学家和物理学家欧拉使用拉
丁字母来作为拉丁方阵里元素的符号,拉丁方阵因此而得名。
BB那么久,可能连题目都看不懂,没事,我们列下3 x 3,4 x 4,5 x 5的拉丁方阵给大家体验下
大家就知道了!
拉丁方阵图例子图:

不知道你发现这样一个规律没?
比如3 x 3的拉丁方阵,第一行是1,2,3,第二行好像都向前移了一位,然后第一个元素跑到了最后面...
用循环链表不就刚好么?非常简单,下面撸下代码~

代码实现

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. typedef struct LNode
  4. {
  5. int data;
  6. struct LNode *next;
  7. }LNode;
  8. typedef struct LNode *LinkList;
  9. //定义一个初始化链表的方法
  10. LinkList ListCreate(int n)
  11. {
  12. LinkList head = NULL,p,q = head;
  13. int i;
  14. for(i = 1;i <= n;i++)
  15. {
  16. p = (LinkList)malloc(sizeof(LNode));
  17. p ->data = i;
  18. if(head == NULL)head = p;
  19. else q ->next = p;
  20. q = p;
  21. }
  22. q ->next = head;
  23. return head;
  24. }
  25. int main()
  26. {
  27. LinkList p,q;
  28. int i,num = 0;
  29. printf("请输入您要构建的拉丁方针的规模(比如3*3,输入3即可)\n");
  30. scanf("%d",&num);
  31. p = ListCreate(num);
  32. printf("%d * %d 的拉丁方阵构建完毕,输出结果:\n\n",num,num);
  33. for(i = 0;i < num;i++)
  34. {
  35. q = p;
  36. while(1)
  37. {
  38. printf("%d ",p ->data);
  39. p = p ->next;
  40. if(p == q)break; //已经走完一轮了
  41. }
  42. p = p ->next;
  43. printf("\n");
  44. }
  45. printf("拉丁方阵打印完毕~~\n\n");
  46. return 0;
  47. }

运行截图

还是蛮简单的,看不懂的话,代码撸一遍,画图,会更加帮助你理解,动手!动手!动手!


3.本节代码下载:

https://github.com/coder-pig/Data-structure-auxiliary-tutorial/blob/master/List/magician.c
https://github.com/coder-pig/Data-structure-auxiliary-tutorial/blob/master/List/lading.c

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注