写在前面
1.这是我的个人博客,我写的内容仅针对我自己的开发经历。而且写博客仅是爱好,不是义务。
2.受能力所限,我的方法并不是最优解。
3.我会放出自己的代码供大家参考,我相信各位是纯洁的。但防小人不防君子,禁止大片剽窃代码。
4.由于大作业并没有显著的性能需求,所以代码中可能存在的内存泄漏的问题没有完全修复。
初拿到这个项目可能没有主意,这很正常。
先不要把课题想那么复杂,仅选取最基本的模块,文件输入->文件输出,就是一个OJ题,之后的命令行动画、窗口动画都只是陪衬。
当我拿到订单的时候,我会想些什么
订单读入后,总能够按照时间递增排好序。而对于同一时刻,算法要做的无非就是
1.遍历骑手,如果骑手抵达食客位置,则执行结算。
2.把订单派出去(将餐馆、食客两个点按序插入到骑手路径的合适位置)。
3.将骑手移动到下一个位置。
4.将当前状态按要求写入文件。
5.(可选)更新画面内容,无论是命令行还是窗口动画。
这便是最粗浅的步骤安排。
数据结构
其实如果是OOP,用类肯定是简单直接,可惜主代码锁死了只让用C。
单个骑手和单个订单都可以用结构体来实现自定义。
而存储骑手总表和订单总表时,链表的*度肯定会高一些,但是操作和debug的难度更大。我选择了使用链表。
文件组织
总体来说,将公用的结构体定义放在头文件中,然后在所有的.c源程序中#include该头文件,.c源程序之间使用extern沟通变量和函数。
总体文件分布为
- define.h 存储公用结构体
- main.c 主控程序
- strategy.c 算法部分
- file.c 文件IO部分
- display.c 命令行动画部分
- animate.c 窗口动画部分
数据结构示例
我设置的最基本的坐标单位叫锚点(Anchor),Stopby用于存储骑手停靠时的信息。
需要注意的是,Stopby设置为数组是无奈之举,因为当时没有时间再修了,所幸测试数据中,骑手附近同时出现的Anchor数目没有超过4个。
Stopby的status数组存储着0,1,2,3槽位的停靠情况(不停靠、餐馆、食客),slot数组存储着该锚点的坐标信息,两者同步变化。
status数组的每个元素有
enum STOPBYSTATUS{
NOSTOPPING,RESTRAURANT,CUSTOMER
};
这些状态。
具体定义如下:
typedef struct _anchor
{
int x;
int y;
struct _order *from;//指向锚点来自订单及结构体
struct _anchor *nextPtr;//节点域,用于将锚点串成链表
}Anchor;
typedef struct _order
{
int id;//订单id
int time;
Anchor *src;
Anchor *dst;
struct _order *nextPtr;
}Order;
typedef struct _stopby
{
int status[4];
Anchor slot[4];
}Stopby;
typedef struct _rider
{
int nodeCnt;
Anchor *pos;
Anchor *path;//path为带头结点的链表的哨兵头结点
Stopby stopby;
struct _rider *nextPtr;//将骑手串成链表
}Rider;