#include
#include
#define?Free?0?//空閑狀態(tài)
#define?Used?1?//已用狀態(tài)
#define?OK?1????//完成
#define?ERROR?0?//出錯
#define?MAX_length?32767?//最大內(nèi)存空間為32767KB
typedef?int?Status;???//typedef將標(biāo)識符Status定義成一個數(shù)據(jù)型標(biāo)識符
int?n?=?0;
typedef?struct?freearea?{?//定義一個結(jié)構(gòu)體freearea并對這個空閑分區(qū)進(jìn)行說明
????int?ID;???????//分區(qū)號
????long?size;????//分區(qū)大小
????long?address;?//分區(qū)地址
????int?state;????//當(dāng)前狀態(tài)
}?ElemType;

typedef?struct?DuLNode?{?//double?linked?list????//?線性表的雙向鏈表存儲結(jié)構(gòu)
????ElemType?data;
????struct?DuLNode?*prior;?//前趨指針
????struct?DuLNode?*next;?//后繼指針
}?DuLNode?*DulinkList;

DulinkList?free_list;??//空閑鏈表
DulinkList?alloc_list;?//已分配鏈表

Status?alloc（int）;//內(nèi)存分配
void?free_memory（int?ID?int?method）;?//內(nèi)存回收

Status?first_fit（int?ID?int?size）;?//首次適應(yīng)算法
Status?best_fit（int?ID?int?size）;?//最佳適應(yīng)算法
Status?worst_fit（int?ID?int?size）;?//最壞適應(yīng)算法

void???first_fit_insert（DuLNode?*insert）;?//首次適應(yīng)插入排序
void???best_fit_insert（DuLNode?*insert）;??//最佳適應(yīng)插入排序
void???worst_fit_insert（DuLNode?*insert）;?//最壞適應(yīng)插入排序

DuLNode?*independent_node（DuLNode?*node）;?//斷開節(jié)點node與相鄰節(jié)點的聯(lián)系，使其孤立
//將節(jié)點node分割，返回分配的節(jié)點信息，node為剩余內(nèi)存信息
//node為雙指針形式，因為可能需要對node的值進(jìn)行修改
DuLNode?*slice_node（DuLNode?**node?int?ID?int?size）;?

void?show（）;//查看分配
Status?Initblock（）;//開創(chuàng)空間表

Status?Initblock（）//開創(chuàng)帶頭節(jié)點的內(nèi)存空間鏈表，頭節(jié)點不用
{
????alloc_list?=?（DulinkList）malloc（sizeof（DuLNode））;
????free_list?=?（DulinkList）malloc（sizeof（DuLNode））;
????//頭節(jié)點不用
????alloc_list->prior?=?alloc_list->next?=?NULL;
????free_list->prior?=?free_list->next?=?NULL;
????//空閑列表初始為整個內(nèi)存大小，放到node節(jié)點中
????DuLNode?*node?=?（DuLNode*）malloc（sizeof（DuLNode））;
????node->data.address?=?0;
????node->data.size?=?MAX_length;
????node->data.ID?=?0;
????node->data.state?=?Free;
????//將node節(jié)點放到空閑鏈表中
????node->prior?=?free_list;
????node->next?=?NULL;
????free_list->next?=?node;

????return?OK;
}
//將所插入節(jié)點按首址從小到大順序插入到空閑鏈表中
void???first_fit_insert（DuLNode?*insert）?//首次適應(yīng)插入排序
{
????DuLNode?*p?=?free_list->next;

????//空閑鏈表為空，則將節(jié)點放到頭節(jié)點后
????if?（p?==?NULL）?{
????????free_list->next?=?insert;
????????insert->prior?=?free_list;
????????return;
????}

????//按首址從小到大的順序插入節(jié)點
????while?（p）?{
????????//找到插入位置:?p之前
????????if?（insert->data.address?<=?p->data.address）?{
????????????insert->next?=?p;
????????????insert->prior?=?p->prior;
????????????p->prior->next?=?insert;
????????????p->prior?=?insert;
????????????break;
????????}

????????//插入位置為鏈表尾
????????if?（p->next?==?NULL）?{
????????????p->next?=?insert;
????????????insert->prior?=?p;
????????????break;??//還是提前退出循環(huán)的好，不然會再次進(jìn)入循環(huán)
????????}

????????p?=?p->next;?//搜索下一個節(jié)點
????}
}
//最佳適應(yīng)插入排序：
//將所插入節(jié)點按空間從小到大插入鏈表
void???best_fit_insert（DuLNode?*insert）
{
????DuLNode?*p?=?free_list->next;

????//空閑鏈表為空，則插入到頭節(jié)點后
????if?（p?==?NULL）?{
????????free_list->next?=?insert;
????????insert->prior?=?free_list;
????????return;
????}

????//按空間從小到大插入節(jié)點
????while?（p）?{
????????//在p前插入
????????if?（insert->data.size?<=?p->data.s

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????目錄???????????0??2010-07-16?22:29??內(nèi)存分配算法\
?????文件??????408339??2010-07-16?06:55??內(nèi)存分配算法\2010操作系統(tǒng)課程設(shè)計.doc
?????文件???????14495??2010-07-16?22:29??內(nèi)存分配算法\memalloc.cpp
?????文件????????3425??2010-07-16?15:25??內(nèi)存分配算法\memalloc.dsp
?????文件?????????541??2010-07-16?15:25??內(nèi)存分配算法\memalloc.dsw