之前的博文谈到了蚂蚁问题现在考虑其变形要求输出从开始到所有蚂蚁离杆这段时间内的各时间段内的碰撞情况有碰撞输出所有碰撞没有则提示未发生碰撞最后输出碰撞总次数若整个过程没有发生任何碰撞则提示没有发生碰撞。代码如下(C语言):#include stdio.h #include malloc.h #include stdlib.h struct collision //碰撞节点 { int sign; //参与碰撞的蚂蚁标号 double t; //碰撞时间 double p; //碰撞位置 struct collision* next; }; void insertCollisionNode(collision* psnew1, collision* head1, collision* t1, collision* q1, int t, bool flag) { if (psnew1 ! NULL)//生成了新的碰撞节点按碰撞时间对碰撞节点执行插入排序将碰撞节点插入到碰撞链表中/// { if (head1-next NULL) { head1-next psnew1; psnew1-next NULL; if (flag) q1 psnew1; } else { t1 head1-next; if ((psnew1-t) (t1-t)) { psnew1-next head1-next; head1-next psnew1; } else { if ((psnew1-t) (t1-t)) { if (q1-next ! NULL) { while (q1-next ! NULL) { q1 q1-next; } } psnew1-next NULL; } else { if (psnew1-t t || !(q1-next ! NULL || q1-t t)) { psnew1-next NULL; } else { if (q1-next NULL) { q1 head1-next; t1 q1-next; while ((q1-t) (t1-t)) { q1 q1-next; t1 t1-next; } } psnew1-next q1-next; } } q1-next psnew1; if (flag) q1 psnew1; } } } } void main() { int t, i, flag; int number; int* p1; int* p2; struct collision* head1, * psnew1, * q1, * t1; typedef struct collision node1; struct ant //蚂蚁节点 { struct ant* next; struct ant* before; short direction; //当前时间点的蚂蚁方向 int position; //当前时间点的蚂蚁位置 short direction1; //上一时间点的蚂蚁方向 int position1; //上一时间点的蚂蚁位置 int sign; //蚂蚁标号 }; struct ant* psnew, * q, * head, * front, * after, *tail; typedef struct ant node; printf(please input the number of ants in stick\n); /*输入位于杆上的蚂蚁个数,不能为0,数量不超过27*/ scanf_s(%d, t); p1 (int*)malloc(t * sizeof(int)); p2 (int*)malloc(t * sizeof(int)); for (i 0; i t; i) { printf(please input the direction of %dnd ant\n, i 1); /*输入第i1个蚂蚁的初始方向,1表示向右,0表示向左,不允许出现t0时刻即一开始就有蚂蚁离开木杆的情况,即最左端蚂蚁方向向左,最右端蚂蚁方向向右*/ scanf_s(%d, p1 i); printf(pleaase input the position of %dnd ant\n, i 1); /*输入第i1个蚂蚁的初始位置,杆长27cm,位置为蚂蚁所在处距杆左端的长度,只能为正整数,即位置只能为0cm,1cm,2cm,3cm---,26cm,27cm,位置需按照蚂蚁编号从小到大输入*/ scanf_s(%d, p2 i); } head (node*)malloc(sizeof(node)); q head; //初始化存放各蚂蚁节点的链表 head-next NULL; head-before NULL; for (i 0; i t; i) { psnew (node*)malloc(sizeof(node)); psnew-next NULL; psnew-direction p1[i]; psnew-direction1 p1[i]; //创建存放各蚂蚁节点的链表 psnew-position p2[i]; psnew-position1 p2[i]; psnew-sign i 1; q-next psnew; psnew-before q; q psnew; } tail q; head1 (node1*)malloc(sizeof(node1)); q1 head1; //初始化碰撞链表 head1-next NULL; number 0; //初始化碰撞计数变量 t 0; //时间初始化 while (1) { t; /*时间进一过度到下一个时间点*/ q head-next; while (q ! NULL) /*检测当前节点对应的蚂蚁的方向,根据方向调整蚂蚁的位置*/ { if (q-direction) q-position q-position 1; /*这种位置调整方式存在漏洞.若某时刻前一蚂蚁与后一蚂蚁位置相隔1,前一蚂蚁向右运动,后一蚂蚁向左运动,则按这种方式时间进一后前一蚂蚁将爬到后一蚂蚁前面一格,换言之两只蚂蚁位置交换了*/ else /*换言之两只蚂蚁互相穿过了对方,这是不可能的,实际上时间进一后两只蚂蚁仍在原来的位置,两只蚂蚁在他们原来两个位置的中点相碰又回到了原来的位置,并且此时他们的方向应该和原来方向相反*/ q-position q-position - 1; /*因此需要对两只蚂蚁的位置方向进行修正,此外若时间进一所有蚂蚁按照各自的方向移动一格后,两只蚂蚁位置相同,即他们相对碰撞,则碰撞后蚂蚁运动方向和原来相反,因此也需要修正方向.*/ q q-next; } psnew head-next; /*psnew指向第一个节点*/ if (psnew-next ! NULL) /*判断第一个节点是否为尾节点,若不是说明有两只以上蚂蚁,则进行碰撞检测,修正蚂蚁运动方向,以及对发生相互穿越错误的一对蚂蚁的位置方向进行修正*/ { q psnew; psnew head; flag 1; do { psnew psnew-next; q q-next; if ((psnew-position) (q-position)) /*检测发生相互穿越错误的一对蚂蚁并对其位置和方向进行修正*/ { i psnew-direction; psnew-direction q-direction; q-direction i; i psnew-position; psnew-position q-position; q-position i; front psnew-before; if (front-before ! NULL) { if (front-position psnew-position) /*进行碰撞检测,对碰撞后蚂蚁的方向进行修正*/ { i front-direction; front-direction psnew-direction; psnew-direction i; if (q-next ! NULL) { after q-next; if (after-position q-position) { i after-direction; after-direction q-direction; q-direction i; flag 0; } } } } } else { if (((psnew-position) (q-position)) flag) { i psnew-direction; psnew-direction q-direction; q-direction i; } else flag 1; } } while (q-next ! NULL); } q head-next; /*蚂蚁的方向位置都修正完毕后对首尾节点对应的蚂蚁的位置进行检测,判断蚂蚁是否爬下杆子*/ if ((q-position 1) || (q-position 27)) { if (q tail) { tail head; } head-next q-next; if (q-next ! nullptr) //如果首位处蚂蚁离杆则删除对应节点 { q-next-before head; } free(q); } if (tail ! head (tail-position 1) || (tail-position 27)) { q tail-before; free(tail); q-next nullptr; tail q; } if (head tail) /*判断线性链表是否为空链表,从而判断是否全部的蚂蚁都爬下了杆子,若是退出循环输出t,否则继续循环*/ { printf(time%d to time%d not including time%d\n, t - 1, t, t - 1); printf(There is no collision happening from time%d to time%d not including time%d\n, t - 1, t, t - 1); printf(\n); break; } else { q head-next; if (q-next NULL) { printf(time%d to time%d not including time%d\n, t - 1, t, t - 1); if ((q-direction) ! (q-direction1)) { number; if ((!(q-direction1)) (q-direction)) { printf(The %dnd collision happens at position%.1f at time%.1f between the%dnd ant and the%dnd ant\n, number, q-position - 0.5, t - 0.5, q-sign - 1, q-sign); printf(\n); } else { printf(The %dnd collision happens at position%.1f at time%.1f between the%dnd ant and the%dnd ant\n, number, q-position 0.5, t - 0.5, q-sign, q-sign 1); printf(\n); } } else { printf(There is no collision happening from time%d to time%d not including time%d\n, t - 1, t, t - 1); printf(\n); } q-direction1 q-direction; q-position1 q-position; } else //当前蚂蚁链表有两个以上蚂蚁节点开始创建碰撞链表 { while (1) { psnew1 NULL; if ((q-direction) ! (q-direction1)) { if ((q-position) (q-position1)) { if ((!(q-direction1)) (q-direction)) { psnew1 (node1*)malloc(sizeof(node1)); psnew1-sign q-sign; psnew1-t (t - 0.5); psnew1-p (q-position - 0.5); } } else { if ((q-position1) (q-position)) { psnew1 (node1*)malloc(sizeof(node1)); psnew1-sign q-sign; psnew1-t t; psnew1-p q-position; } } } else { if ((q-position) (q-position1)) { psnew1 (node1*)malloc(sizeof(node1)); psnew1-sign q-sign; if (q-direction1) { psnew1-t t; psnew1-p q-position; } else { psnew1-t (t - 0.5); psnew1-p (q-position - 0.5); } } } insertCollisionNode(psnew1, head1, t1, q1, t, true); //生成了新的碰撞节点按碰撞时间对碰撞节点执行插入排序将碰撞节点插入到碰撞链表中/// if (q-next NULL) break; q q-next; } psnew1 NULL; if ((q-direction) ! (q-direction1)) //处理蚂蚁链表中尾节点代表的蚂蚁的碰撞 { if ((q-position) (q-position1)) { if ((q-direction1) (!(q-direction))) { psnew1 (node1*)malloc(sizeof(node1)); psnew1-sign (q-sign 1); psnew1-t (t - 0.5); psnew1-p (q-position 0.5); } } else { if ((q-position1) (q-position)) { psnew1 (node1*)malloc(sizeof(node1)); psnew1-sign (q-sign 1); psnew1-t t; psnew1-p q-position; } } } else { if ((q-position) (q-position1)) { psnew1 (node1*)malloc(sizeof(node1)); psnew1-sign (q-sign 1); if (q-direction1) { psnew1-t (t - 0.5); psnew1-p (q-position 0.5); } else { psnew1-t t; psnew1-p q-position; } } } insertCollisionNode(psnew1, head1, t1, q1, t, false); //新的碰撞节点生成和以上操作类似对碰撞节点执行插入排序 printf(time%d to time%d not including time%d\n, t - 1, t, t - 1); //碰撞链表生成完毕输出(t-1 t] 时间段内的碰撞 if (head1-next ! NULL)//碰撞链表不空 { q1 head1-next; while (q1 ! NULL) //输出当前时间段内的所有碰撞 { number; printf(The %dnd collosion happens at position%.1f at time%.1f between the %dnd ant and the %dnd ant\n, number, q1-p, q1-t, q1-sign - 1, q1-sign); q1 q1-next; } printf(\n); q1 head1; //清空碰撞链表 while (q1-next ! NULL) { t1 q1-next; q1-next t1-next; free(t1); } } else //碰撞链表为空当前时间段内没有碰撞 { printf(There is no collision happening from time%d to time%d not including time%d\n, t - 1, t, t - 1); printf(\n); } q head-next; while (q ! NULL) //用当前时间点的位置方向更新上一时间点的位置方向 { q-direction1 q-direction; q-position1 q-position; q q-next; } } } } if (number 0) //没有发生任何碰撞 printf(No collsion happens at the whole process\n); printf(There are %d collisions in total\n, number); //输出碰撞总数 } /*用线性链表实现解决蚂蚁问题,若干蚂蚁位于一长杆上,杆长27cm,蚂蚁初始方向可以任意,运动速度1cm/s,蚂蚁从初始位置出发,两蚂蚁若相碰不能穿过对方,只能相碰后各自掉头,求蚂蚁全部爬出杆子所需时间*/若初始时刻杆上共有三只蚂蚁第一第二第三只蚂蚁初始方向位置分别为1(右),2 1(右),3 0(左),4,则程序运行结果如下: