动态内存分配算法（源代码&报告）DynamicAllocate

#include <stdio.h> #include <stdlib.h> const int MAX=100; const int MINSIZE=1; struct Node { int ADDRESS; //一个未分配块的起始地址 int SIZE; // 一个未分配块的长度 struct Node *NEXT; //指向下一块地址 }; typedef struct Node *List; List Initlist(); //分配内存函数 void print(List head); //打印内存空闲链信息函数 void printram(List head); //打印内存正在运行信息函数 void Allocate(List head, int size); //分配内存函数 void Reclaim(List head,int size,int address); //释放内存函数 void SpaceOrder(List head); //空闲分区链表按分区大小递增排序 void AddrOrder(List head); //空闲分区链表按分区地址递增排序 //按地址大小排序 void AddrOrder(List head) { List front;//当前指针的前驱 List current,pointer;//当前指针 List temp; int move=0; current=head->NEXT; if(!(current==NULL||current->NEXT==NULL))//注意必须是current==NULL在current->NEXT==NULL前面 { while(current!=NULL) { pointer=head->NEXT; front=head; while(pointer!=current->NEXT) { if(current->NEXT->ADDRESS < pointer->ADDRESS) { temp=current->NEXT; current->NEXT=temp->NEXT; temp->NEXT=pointer; front->NEXT=temp; move=1; break; } else { front=front->NEXT; pointer=pointer->NEXT; } } if(move==1) move=0; else current=current->NEXT; if(current->NEXT==NULL) break; } } } //空闲分区链表按分区大小递增排序 void SpaceOrder(List head) { List front;//当前指针的前驱 List current,pointer;//当前指针 List temp; int move=0; current=head->NEXT; if(!(current==NULL||current->NEXT==NULL))//注意必须是current==NULL在current->NEXT==NULL前面 { while(current!=NULL) { pointer=head->NEXT; front=head; while(pointer!=current->NEXT) { if(current->NEXT->SIZE < pointer->SIZE) { temp=current->NEXT; current->NEXT=temp->NEXT; temp->NEXT=pointer; front->NEXT=temp; move=1; break; } else { front=front->NEXT; pointer=pointer->NEXT; } }//while(pointer!=current->NEXT) if(move==1) move=0; else current=current->NEXT; if(current->NEXT==NULL) break; }//while(current!=NULL) }//if(!(current->NEXT==NULL||current==NULL)) } //打印内存空闲链信息函数 void print(List head) { List front;//当前指针的前驱 List current;//当前指针 front=head; current=head->NEXT; if(current==NULL) printf("内存空间已满!!"); else { printf("当前空闲分区链的信息: 空间大小 首地址 尾地址\n"); while(current!=NULL) { printf("\t\t\t%dk\t\t%dk\t\t%dk\n",current->SIZE,current->ADDRESS,current->SIZE+current->ADDRESS); current=current->NEXT; } printf("******************************************************************\n"); } } void printram(List head) { List front;//当前指针的前驱 List current;//当前指针 int size=0,address=0; AddrOrder(head); front=head; current=head->NEXT; if(current==NULL) printf("整个内存空间都被占用!!"); else { printf("正在被占用的分区信息: 空间大小 首地址 尾地址\n"); if(current->ADDRESS!=0) { size=current->ADDRESS; printf("\t\t\t%dk\t\t%dk\t\t%dk\n",size,0,size); current=current->NEXT; } while(current->NEXT!=NULL) { address=current->ADDRESS + current->SIZE; size=current->NEXT->ADDRESS-address; printf("\t\t\t%dk\t\t%dk\t\t%dk\n",size,address,size+address); current=current->NEXT; } if(current->ADDRESS<1024) { size=1024-(current->SIZE+current->ADDRESS); address=current->ADDRESS + current->SIZE; printf("\t\t\t%dk\t\t%dk\t\t%dk\n",size,address,1024); } printf("******************************************************************\n"); } } //初始化空闲区链表函数 List Initlist() { List Pointer; List Head; List NewNode; //设置头结点 Head=(List)malloc(sizeof(Node)); Head->ADDRESS=0; Head->SIZE=0; Pointer=Head; Pointer->NEXT=NULL; NewNode=(List)malloc(sizeof(Node));//首地址150k，空间大小40k NewNode->ADDRESS=150; NewNode->SIZE=40; NewNode->NEXT=Pointer->NEXT; Pointer->NEXT=NewNode; Pointer=Pointer->NEXT; NewNode =(List)malloc(sizeof(Node));//首地址590k，空间大小40k NewNode->ADDRESS=590; NewNode->SIZE=40; NewNode->NEXT=Pointer->NEXT; Pointer->NEXT=NewNode; Pointer=Pointer->NEXT; NewNode=(List)malloc(sizeof(Node));//首地址0k，空间大小70k NewNode->ADDRESS=0; NewNode->SIZE=70; NewNode->NEXT=Pointer->NEXT; Pointer->NEXT=NewNode; Pointer=Pointer->NEXT; NewNode=(List)malloc(sizeof(Node));//首地址750k，空间大小90k NewNode->ADDRESS=750; NewNode->SIZE=90; NewNode->NEXT=Pointer->NEXT; Pointer->NEXT=NewNode; Pointer=Pointer->NEXT; NewNode=(List)malloc(sizeof(Node));//首地址260k，空间大小240k NewNode->ADDRESS=260; NewNode->SIZE=240; NewNode->NEXT=Pointer->NEXT; Pointer->NEXT=NewNode; Pointer=Pointer->NEXT; return Head;//返回头指针 } //分配内存函数 void Allocate(List head, int size) { List front; //当前指针的前驱 List current; //当前指针 SpaceOrder(head); front=head; current=head->NEXT; int FLAG=0; //判断是否找到所要的分区 //从头结点开始查找 while(current!=NULL && FLAG==0) { if(current->SIZE >= size) { if(current->SIZE - size <= MINSIZE) { printf("将该整个分区分配给请求者,并把此空闲区从链表内移出.\n"); printf("被分配的该分区的信息:首地址:%d,空间大小:%dk\n" ,current->ADDRESS,current->SIZE); //移出链表 front->NEXT=current->NEXT; free(current); } //从新划分 else { printf("从当前分区(首地址:%dk,空间大小:%dk)中划出大小为%dK的内存空间给请求者\n" ,current->SIZE,current->ADDRESS,size); current->SIZE = current->SIZE - size; current->ADDRESS=current->ADDRESS + size; } FLAG=1; //FLAG标志空闲区大小足够，则出循环 } else //空闲区空间大小不够，则指针下移 { current=current->NEXT; front=front->NEXT; //向下移动指针 } } //打印当前内存空闲区链表信息 if(FLAG==0) printf("不能够找到足够大小的分区分配该程序!\n"); SpaceOrder(head); } //释放内存函数 void Reclaim(List head,int size,int address) { List front;//当前指针的前驱 List current;//当前指针 List temp,Q; int first=1; //标志释放的内存与高地址空闲区链结 int second=1; //标志释放的内存与低地址空闲区链结 SpaceOrder(head); //初始化front和current front=head; current=head->NEXT; //查找释放的内存是否与空闲区链结 if(current->ADDRESS==0&&current->SIZE==1024) printf("\n*****不能再释放内存，内存已全部释放!******\n"); else { while((current!=NULL)&&(first||second)) { if(address==(current->ADDRESS + current->SIZE)) { current->SIZE=current->SIZE + size; temp=current; first=0; current=current->NEXT; front=front->NEXT; } else { if(address+size == current->ADDRESS) { if(first==0) { temp->SIZE=current->SIZE + temp->SIZE; Q=current; front->NEXT=current->NEXT; free(Q); } else { current->ADDRESS=address; current->SIZE=current->SIZE + size; } second=0; } else { current=current->NEXT; front=front->NEXT; } }//else }//while SpaceOrder(head); }//if(current->ADDRESS=0&&current->SIZE=1024;) } void main() { int size; int address; char ch; int out=1,in=0; List LinkList; //内存初始化 LinkList=Initlist(); //打印内存初始化信息 printf("\n***********************\n"); printf("****内存初始化信息*****\n"); printf("***********************\n"); AddrOrder(LinkList); print(LinkList); printram(LinkList);