#include "iostream.h"
#define NULL 0
enum {
    TOTAL_SIZE = 14,    //内存单元大小
};

struct alloc
{
    int    allocSize;    //已占用的内存单元
    int    needSize;     //还需要分配的内存单元
    int    name;         //用户名
    struct alloc * next;
};

/*
 *    资源情况的初始化
 */
struct alloc *initBankSource(struct alloc *head)
{
    cout<<"资源总数："<<TOTAL_SIZE<<endl;
    cout<<"用户名  占有资源  需要资源"<<endl;
    struct alloc * p = new     struct alloc;
    cin>>p->name;
    cin>>p->allocSize;
    cin>>p->needSize;
    p->next          = NULL;
    head             = p;
    while(1)
    {
        struct alloc * q = new     struct alloc;
        cin>>q->name;
        cin>>q->allocSize;
        cin>>q->needSize;
        q->next          = NULL;
        if(0 > q->allocSize)
        {
            break;
        }
        p->next          = q;
        p                = q;
    }
    return head;
}

/*
 *   根据每个用户的已占有的资源allocSize和申请分配的资源needSize的总和降序排列
 *   因为如果allocSize + needSize在能满足条件的前提下，即：needSize < remainSize,
 *   能够释放的内存越大越好
 */

struct alloc * resort(struct alloc *head)
{
    if(NULL == head)
    {
        return NULL;
    }
    struct alloc * p = head;
    struct alloc * q = p->next;
    p->next          = NULL;
    while (NULL != q)
    {
        p = q->next;

        //将q按allocSize + needSize递减的顺序插入以head为头指针的链表中 start
        if (q->allocSize + q->needSize > head->allocSize + head->needSize)
        {
            q->next = head;
            head = q;
            q = p;
            continue;
        }
        
        struct alloc * r       = head;
        struct alloc * r_prior = NULL;  //用于指向r的前驱
        while (NULL != r && q->allocSize + q->needSize <=  r->allocSize + r->needSize)
        {
            r_prior   = r;
            r         = r->next;
        }
        r_prior->next = q;
        q->next       = NULL;
        //将q按allocSize + needSize递减的顺序插入以head为头指针的链表中 end

        q = p;
    }
    return head;
}

/*
 *    统计银行的除去借贷的资源之外的剩余资源，
 *    如为负数则表明无法实现分配
 */
int getRemainSource(struct alloc *head)
{
    int remainSource = TOTAL_SIZE;
    struct alloc * p = head; 
    while(NULL != p)
    {
        remainSource = remainSource - p->allocSize;
        p = p->next;
    }

    return remainSource;
}

/*
 *    单资源银行家算法
 */
void BankerAlgorithm(struct alloc *head)
{
    int remainSource = getRemainSource(head);
    if (0 > remainSource)
    {
        cout<<"分配空间不够，无法实现分配！"<<endl;
        return;
    }

    head = resort(head);
    while (NULL != head)
    {
        struct alloc * p = head;
        while(NULL != p && remainSource < p->needSize)
        {
            p = p->next;
        }
        if (NULL == p)
        {
            cout<<"分配空间不够，无法实现分配！"<<endl;
            return;
        }

        //将p从链表中删除 start
        if (p == head)
        {
            cout<<"现有资源:"<<getRemainSource(head)<<endl;
            cout<<"分配给用户"<<p->name<<endl;
            head = p->next;
            delete p;
            p    = NULL;
        }
        else
        {
            struct alloc * q = head;
            while (q->next != p)
            {
                q = q->next;
            }
            cout<<"现有资源:"<<getRemainSource(head)<<endl;
            cout<<"分配给用户"<<p->name<<endl;
            q->next      = p->next;
            remainSource = remainSource + p->allocSize;
            delete p;
            p            = NULL;
        }
        //将p从链表中删除 end
    }
    cout<<"资源分配成功！"<<endl;
}

void main()
{
    struct alloc *head = NULL;
    head = initBankSource(head);
    BankerAlgorithm(head);
}