#include
#include
#define?Free?0?//空閑狀態
#define?Used?1?//已用狀態
#define?OK?1????//完成
#define?ERROR?0?//出錯
#define?MAX_length?32767?//最大內存空間為32767KB
typedef?int?Status;???//typedef將標識符Status定義成一個數據型標識符
int?n?=?0;
typedef?struct?freearea?{?//定義一個結構體freearea并對這個空閑分區進行說明
????int?ID;???????//分區號
????long?size;????//分區大小
????long?address;?//分區地址
????int?state;????//當前狀態
}?ElemType;

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

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

Status?alloc（int）;//內存分配
void?free_memory（int?ID?int?method）;?//內存回收

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

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

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

void?show（）;//查看分配
Status?Initblock（）;//開創空間表

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

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

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

????//按首址從小到大的順序插入節點
????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;??//還是提前退出循環的好，不然會再次進入循環
????????}

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

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

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

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