之前的博文谈到了蚂蚁问题，现在考虑其变形，要求输出从开始到所有蚂蚁离杆这段时间内的各时间段内的碰撞情况，有碰撞输出所有碰撞，没有则提示未发生碰撞，最后输出碰撞总次数，若整个过程没有发生任何碰撞则提示没有发生碰撞。
代码如下(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); /*输入第i+1个蚂蚁的初始方向,1表示向右,0表示向左,不允许出现t=0时刻即一开始就有蚂蚁离开木杆的情况,即最左端蚂蚁方向向左,最右端蚂蚁方向向右*/ scanf_s("%d", p1 + i); printf("pleaase input the position of %dnd ant\n", i + 1); /*输入第i+1个蚂蚁的初始位置,杆长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,则程序运行结果如下:
)
