#include "iostream.h"
#define NULL 0
enum {
    TOTAL_SIZE = 14,    //內(nèi)存單元大小
};

struct alloc
{
    int    allocSize;    //已占用的內(nèi)存單元
    int    needSize;     //還需要分配的內(nèi)存單元
    int    name;         //用戶名
    struct alloc * next;
};

/*
 *    資源情況的初始化
 */
struct alloc *initBankSource(struct alloc *head)
{
    cout<<"資源總數(shù)："<<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;
}

/*
 *   根據(jù)每個用戶的已占有的資源allocSize和申請分配的資源needSize的總和降序排列
 *   因為如果allocSize + needSize在能滿足條件的前提下，即：needSize < remainSize,
 *   能夠釋放的內(nèi)存越大越好
 */

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的前驅(qū)
        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;
}

/*
 *    統(tǒng)計銀行的除去借貸的資源之外的剩余資源，
 *    如為負(fù)數(shù)則表明無法實現(xiàn)分配
 */
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<<"分配空間不夠，無法實現(xiàn)分配！"<<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<<"分配空間不夠，無法實現(xiàn)分配！"<<endl;
            return;
        }

        //將p從鏈表中刪除 start
        if (p == head)
        {
            cout<<"現(xiàn)有資源:"<<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<<"現(xiàn)有資源:"<<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);
}