动态内存分配算法实验报告

动态内存分配算法实验报告院系:计算机与通信工程学院班级:计科08-1班姓名:胡太祥学号:200807010112一．实验题目：动态内存分配算法二、实验目的深入了解动态分区存储管理方式内存分配与回收的实现三、实验要求熟悉存储管理中动态分区的管理方式及Windows环境下，VC++程序设计方法四、实验内容1，确定定内存空闲分配表和进程内存分配表2，采用首次适应算法完成内存空间的分配3，采用最佳适应算法完成内存空间的分配4，采用最坏适应算法完成内存空间的分配5，实现内存回收功能五、实验结果首次适应算法结果最佳适应算法最坏适应算法六、实验总结首次适应算法：从表头指针开始查找课利用空间表，将找到的第一个大小不小于“请求”的空闲块的一部分分配给用户。最佳适应算法：将可利用空间表中一个大小不小于“请求”且最接近“请求”的空闲块的一部分分配给用户。最坏适应算法：将可利用空间表中一个大小不小于“请求”且是链表中最大的空闲块的一部分分配给用户。以上是动态内存分配的三种算法思想，算法采用数据结构中的双向链表实现。附录（算法代码）：#includeiostream.h#includestdlib.h#defineFree0//空闲状态#defineUsed1//已用状态#defineOK1//完成#defineERROR0//出错#defineMAX_length32767//最大内存空间为32767KBtypedefintStatus;//typedef将标识符Status定义成一个数据型标识符intn=0;typedefstructfreearea{//定义一个结构体freearea,并对这个空闲分区进行说明intID;//分区号longsize;//分区大小longaddress;//分区地址intstate;//当前状态}ElemType;typedefstructDuLNode{//doublelinkedlist//线性表的双向链表存储结构ElemTypedata;structDuLNode*prior;//前趋指针structDuLNode*next;//后继指针}DuLNode,*DuLinkList;DuLinkListfree_list;//空闲链表DuLinkListalloc_list;//已分配链表Statusalloc(int);//内存分配voidfree_memory(intID,intmethod);//内存回收Statusfirst_fit(intID,intsize);//首次适应算法Statusbest_fit(intID,intsize);//最佳适应算法Statusworst_fit(intID,intsize);//最坏适应算法voidfirst_fit_insert(DuLNode*insert);//首次适应插入排序voidbest_fit_insert(DuLNode*insert);//最佳适应插入排序voidworst_fit_insert(DuLNode*insert);//最坏适应插入排序DuLNode*independent_node(DuLNode*node);//断开节点node与相邻节点的联系，使其孤立//将节点node分割，返回分配的节点信息，node为剩余内存信息//node为双指针形式，因为可能需要对node的值进行修改DuLNode*slice_node(DuLNode**node,intID,intsize);voidshow();//查看分配StatusInitblock();//开创空间表StatusInitblock()//开创带头节点的内存空间链表，头节点不用{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;returnOK;}//将所插入节点按首址从小到大顺序插入到空闲链表中voidfirst_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;//搜索下一个节点}}//最佳适应插入排序：//将所插入节点按空间从小到大插入链表voidbest_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.size){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;//搜索下一个节点}}//最坏适应插入排序：//将所插入节点按空间从大到小插入链表voidworst_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.size){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;//搜索下一个节点}}//断开节点node与相邻节点间的联系，使其孤立//返回孤立后的节点指针DuLNode*independent_node(DuLNode*node){if(node!=NULL){if(node-prior!=NULL){node-prior-next=node-next;}if(node-next!=NULL){node-next-prior=node-prior;}node-prior=node-next=NULL;}returnnode;}//将节点node分片，其中一片allocnode为为用户所分配的内存片，//另一片为分配后原node节点所剩余的内存片，放到node中//若node节点原来大小等于所要开辟的大小，则node赋值为NULL//返回分配结果DuLNode*slice_node(DuLNode**node,intID,intsize){DuLNode*allocnode=NULL;//node的大小正好等于所要分配的大小，//则直接将该节点放到分配链表中，node赋值为NULLif((*node)-data.size==size){//将node从空闲链表中分出来independent_node((*node));//得到所分配的内存片allocnode=(*node);allocnode-data.ID=ID;allocnode-data.state=Used;//没有剩余空间,这个地方导致必须用双重指针(*node)=NULL;}elseif((*node)-data.sizesize){//node的大小大于所需的大小，故将node分为两片//一片为所分配的内存片，分配地址和空间allocnode=(DuLNode*)malloc(sizeof(DuLNode));allocnode-data.size=size;allocnode-data.address=(*node)-data.address;allocnode-data.ID=ID;allocnode-data.state=Used;allocnode-prior=allocnode-next=NULL;//另一片为分配后剩下的内存片，修改内存地址和大小(*node)-data.address+=size;(*node)-data.size-=size;}//返回分配结果returnallocnode;}//按不同的分配方法归还内存voidfree_memory(intID,intmethod)//内存回收{DuLNode*p,*prior,*next,*freenode;p=prior=next=freenode=NULL;//从已分配链表中找到所要归还的内存信息p=alloc_list-next;while(p){if(p-data.ID==ID){//找到所要归还的内存信息freenode=p;freenode-data.state=Free;freenode-data.ID=Free;break;}p=p-next;//继续查找}//将freenode从已分配链表中分离出来independent_node(freenode);if(freenode==NULL){//没有所要归还的内存return;}//合并空闲内存片p=free_list-next;while(p){//找到先前合并内存节点priorif(p-data.address+p-data.size==freenode-data.address){prior=p;}elseif(freenode-data.address+freenode-data.size==p-data.address){//找到向后合并内存节点nextnext=p;//在这儿，如果是首次适应算法可以直接中断循环了}p=p-next;//继续查找}//向前合并节点存在，则进行合并if(prior!=NULL){independent_node(prior);//将pr