【题目】数据分发系统设计题

有一套若干设各组成的系统，每个设备既能产生、也能发送和接收数据，系统保证每个设备新产生的数据编号唯一。请实现如下功能：
DataMachineSystemCreate(int num) ---- 初始化系统设备数量为num（编号1~num）。
DataMachineSystemTransferData(int machineA, int machineB, int dataId) ---- 设备machineA点到点发送编号为dataId的数据给设备machineB。若machineB已经有此数据，则不接受并返回0。
否则接收该数据，并返回1。
注意：如果machineA没有该数据，则自己产生编号为dataId的数据再发送。
DataMachineSystemTransferDataToAll(int machine, int dataId) ---- 设备machine群发编号为dataId的数据给所有的设备。已经有此数据的设备不接受，请返回发送后接收了此数据的设备数量。
发送后，machine和接收到此数据的设备都会留存数据dataId。
注意：如果machineA没有该数据，则自己产生编号为dataId的数据再发送。
DataMachineSystemQueryContribution(int machineA) ---- 查询设备的贡献值
贡献值的计算规则如下：对于每个接收到的设备，其发送方都增加贡献量10；对于群发，发送方增加贡献量为接收到此数据的设备数量*10；
贡献会传递，如果发送方的数据来源于另一个设备，那么该设备的贡献值也加10；贡献继续传递，直到数据的产生方。如，一直a, b, c, d四个设备，对同一数据依次做如下3次数据发送：
a->b: a发送数据给b，a增加10贡献值；
b->c: b发送数据给c，则a，b都增加10贡献值；
c->d: c发送数据给d，则a，b, c都增加10贡献值；
最后，a，b，c的贡献值分别是30,20,10.

/*
1.数据分发系统的机构可以抽象理解为一棵树的结构。
2.利用数组下标和数组值，可以巧妙的实现一颗树
*/
#define MAX_MACHINE 1001
#define MAX_ID 1001
#define CONTRIBUTION_UNIT 10

typedef struct {
    int machineId;
    int contribution;
    int idTable[MAX_ID]; // -1表示无数据，0表示自己产生，dataId表示传递接收的。
} DataMachineSystem;

// 初始化：建立一个大的结构体数组，i从1开始，与number号一一对应。
DataMachineSystem *DataMachineSystemCreate(int num)
{
    DataMachineSystem *obj = malloc(sizeof(DataMachineSystem) * (num + 1));
    for (int i = 1; i < num + 1; i++) {
        obj[i].machineId = i;
        obj[i].contribution = 0;
        for (int j = 0; j < MAX_ID; j++) {
            obj[i].idTable[j] = -1;
        }
    }

    return obj;
}

// 单播
// machineX为-1，表示该位置还未曾产生过数据，所以给它置0，表示数据的源头，直接产生数据；
// 如果machineX不为-1，说明是间接传递过来的，通过while一直追溯到源头，同时累计贡献值。
int DataMachineSystemTransferData(DataMachineSystem *obj, int machineA, int machineB, int dataId)
{
    if (obj[machineB].idTable[dataId] >= 0) { // 如果machineB已有，则不接收，且返回0.
        return 0;
    }

    obj[machineB].idTable[dataId] = machineA;
    obj[machineA].contribution += CONTRIBUTION_UNIT; // A传递给B，则A的贡献加10

    int machineX = obj[machineA].idTable[dataId]; // 同时，根据dataId是A自己产生还是从其它机器接收来的，做两种处理。
    if (machineX == -1) { // 说明未产生数据过
        obj[machineA].idTable[dataId] = 0;
    } else { // 说明已经有数据了
        while (machineX != 0) { // 这个while太牛了
            obj[machineX].contribution += CONTRIBUTION_UNIT;
            machineX = obj[machineX].idTable[dataId];
        }

    }

    return 1;
}

// 广播
// -1表示当前设备无此数据; 0，表示当前设备是源头并生产数据。
// while的使用同上，这个while使用的太妙了。
int DataMachineSystemTransferDataToAll(DataMachineSystem *obj, int machine, int dataId)
{
    if (obj[machine].idTable[dataId] == -1) { // 如果machine没有这个id，则自己创建
        obj[machine].idTable[dataId] = 0;
    }

    int res = 0;
    for (int i = 1; i < MAX_ID; i++) { // 已经有此dataId的，则不接收。-1表示无此dataId
        if (obj[i].idTable[dataId] == -1) {
            obj[i].idTable[dataId] = machine;
            res++
        }
    }

    if (res) { // 更新贡献值
        obj[machine].contribution += res * CONTRIBUTION_UNIT; // 先更新当前的,翻倍乘

        int machineX = obj[machine].idTable[dataId]; // 再更新传递的。
        while (machineX != 0) {
            obj[machineX].contribution += res * CONTRIBUTION_UNIT; // 翻倍乘
            machineX = obj[machineX].idTable[dataId];
        }
    }

    return res;
}

// 查询贡献值
int DataMachineSystemQueryContribution(DataMachineSystem *obj, int machine)
{
    return obj[machine].contribution;
}

// 释放
void DataMachineSystemFree(DataMachineSystem *obj)
{
    free(obj);
}