實驗名稱：動态分區配置設定方式模拟

實驗目的

進一步加深對動态分區配置設定管理方式的了解；掌握動态分區配置設定方式使用的資料結構、配置設定算法和回收算法

實驗内容

編寫C語言程式，模拟實作首次/最佳/最壞适應算法的記憶體塊配置設定和回收，要求每次配置設定和回收後顯示出空閑分區和已配置設定分區的情況。假設初始狀态下，可用的記憶體空間為640K。

資料結構設計

空閑分區表：Unallocated Table

index	address	end	size
639	640

已配置設定分區表：Allocated Table

index	address	end	size
630	639	10

配置設定算法設計

首次适應算法
最佳适應算法
最差适應算法

根據選擇的配置設定算法決定空閑分區表的排序方式

回收算法設計

實驗名稱：動态分區配置設定方式模拟

上下都無空分區
有上空分區無下空分區
無上空分區有下空分區
上下分區都為空分區

代碼：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<ctype.h>
#define MAX 640

struct node  //定義分區
{
  int address, size;
  struct node *next;
};
typedef struct node RECT;

/*-----函數定義-------*/
void firstfit(RECT *head,int application); //針對首次适應配置設定算法配置設定分區
void bestfit(RECT *head,int application);  //針對最佳适應配置設定算法配置設定分區
void worstfit(RECT *head,int application);  //針對最壞适應配置設定算法配置設定分區
int backcheck(RECT *head,RECT *back1); //合法性檢查
void recycle(RECT *head,RECT *heada,RECT *back1); //回收分區
void print(RECT *head);   //輸出已配置設定分區表或空閑分區
/*-----變量定義-------*/
RECT *head,*heada,*back,*assign1,*p;
int application1,maxblocknum;
char way;  //用于定義配置設定方式：首先适應(f)、最佳适應(b)、最差适應(w)
int main()
{
  char choose;
  int check;
  RECT *allocated;  //
  head=malloc(sizeof(RECT)); //建立空閑分區表的初始狀态
  p=malloc(sizeof(RECT));
  head->size=MAX;
  head->address=0;
  head->next=p;
  maxblocknum=1; //初始隻有一塊空閑區
  p->size=MAX;
  p->address=0;
  p->next=NULL;
  print(head);  //輸出空閑分區表的初始狀态
  printf("Enter the way (first, best or worst (f/b/w))\n");
  scanf("%c",&way);
  heada=malloc(sizeof(RECT)); //建立已配置設定分區表的初始狀态
  heada->size=0;
  heada->address=0;
  heada->next=NULL;
  //print(heada);  //輸出空閑分區表的初始狀态
  //way='f';
  do
  {
    printf("Enter the allocate or reclaim (a/r),or press other key to exit.\n");
    scanf(" %c",&choose);     //選擇配置設定或回收
    if(tolower(choose)=='a')                 //a為配置設定
    {
      printf("Input application:\n");
      scanf("%d",&application1);              //輸入申請空間大小
        if(tolower(way)=='f')
          firstfit(head,application1);    //首先适應算法配置設定
        else if(tolower(way)=='b')
          bestfit(head,application1);     //調用最佳适應配置設定算法函數配置設定記憶體
        else
          worstfit(head,application1);    //最壞适應算法配置設定
      if (assign1->address==-1)               //配置設定不成功
        printf("Too large application! Allocation fails! \n\n");
      else{//配置設定成功
          printf("Allocation Success! ADDRESS=%5d\n",assign1->address);
        printf("\n*********Unallocated Table**********\n");
        print(head);  //輸出
        printf("\n*********Allocated Table************\n");
          print(heada);
      }
    }
    else if (tolower(choose)=='r')          //回收記憶體
    {
      back=malloc(sizeof(RECT));
      printf("Input address and Size:\n");
      scanf("%d%d",&back->address,&back->size);//輸入回收位址和大小
      check=backcheck(head,back);
      if (check==1)
      {
        recycle(head,heada,back);
        printf("\n*********Unallocated Table**********\n");
        print(head);  //輸出
        printf("\n*********Allocated Table************\n");
        print(heada);
       }
    }
  }while(tolower(choose)=='a'||tolower(choose)=='r');
  exit(0);
} //main() end.

/*-------記憶體回收函數,back1為回收節點到位址-------*/
void recycle(RECT *head,RECT *heada,RECT *back1)
{
  RECT *before, *after, *back2;
  int insert = 0, del;
  back2 = malloc(sizeof(RECT));
  back2->address = back1->address;
  back2->size = back1->size;
  back2->next = back1->next;
  before = head;
  after = head->next;

  if (head->next == NULL) // 沒有空閑區，直接回收
  {
    head->size = back1->size;
    head->next = back1;
    maxblocknum++;
    back1->next = NULL;
  }
  else
  {
    while (!insert&&after!=NULL)                                 // 周遊空閑區
    {
      if (back1->address == after->size + after->address) /*要回收的記憶體在目前空閑區之後，與上一塊合并*/
      {//第一種情況，回收區與相鄰低位址合并
        after->size+=back1->size;
        insert=1;
        // before->next = after->next;
        // back->size = after->size + back1->size;
        // free(after);
        // after = NULL;
      }else if(back1->address+back1->size==after->address)
      { //第二種情況，回收區與相鄰高位址合并
        after->size+=back1->size;
        after->address=back1->address;
        insert=1;
      }else if(before->address<back1->address&&after->address>back1->address)
      { //第三種情況，回收區與相鄰的高位址、低位址合并，被夾在中間
        before->size+=back1->size+after->size;
        insert=1;
      }
        after = after->next;
        before = before->next;
    }

    //第四種情況，回收區獨自一塊，需要在空閑表中新增一項
    before = head; /*将回收節點插入到合适到位置*/
    after = head->next;
    do
    {
      if (after == NULL)
      {
        before->next = back1;
        back1->next = after;
        insert = 1;
      }
      else
      {
        before = before->next;
        after = after->next;
      }
    } while (!insert);

    if (head->size < back1->size) /*修改最大塊值和最大塊數*/
    {
      head->size = back1->size;
      maxblocknum++;
    }
    else
    {
      if (head->size == back1->size)
        maxblocknum++;
    }
  }

  // 修改已配置設定分區表，删除相應節點
  before = heada;
  after = heada->next;
  del = 0;
  while (!del &&after != NULL) // 1，循環在已删除或者周遊結束時退出，将回收區從已配置設定分區表中删除
  {
    if ((after->address == back2->address) && (after->size == back2->size))
    {
      before->next = after->next;
      free(after);
      del = 1;
    }
    else
    {
      before = before->next;
      after = after->next;
    }
  }
  heada->size--;
}

/*------------------首次适應配置設定算法------------*/
void firstfit(RECT *head,int application)
{
  RECT *after, *before, *assign;
  assign = malloc(sizeof(RECT)); // 申請配置設定空間
  assign->size = application;
  assign->next = NULL;
  if (application > head->size || application < 0)
    assign->address = -1; // 申請無效
  else
  {
    before = head;
    after = head->next;
    while (after->size < application) // 周遊連結清單，查找合适到節點
    {
      before = before->next;
      after = after->next;
    }
    if (after->size == application) // 若節點大小等于申請大小則完全配置設定
    {
      if (after->size == head->size)
        maxblocknum--;
      before->next = after->next;       // 指向後面的空閑區
      assign->address = after->address; // 将這個同樣大小的位址直接賦給配置設定的對象
      free(after);
    }
    else
    {
      if (after->size == head->size) // 這個可配置設定空間等于剩餘總的空閑空間
        maxblocknum--;
      after->size = after->size - application;        // 大于申請空間則截取相應大小配置設定
      assign->address = after->address + after->size; // 配置設定靠後的位址
    }

    if (maxblocknum == 0) // 修改最大數和頭節點
    {
      before = head;
      head->size = 0;
      maxblocknum = 1;
      while (before != NULL) // 周遊空閑區
      {
        if (before->size > head->size)
        {
          head->size = before->size;
          maxblocknum = 1;
        }
        else if (before->size == head->size)
          maxblocknum++;
        before = before->next;
      }
    }
  }
  assign1 = assign;

  // 修改已配置設定分區表，添加節點
  after = heada;
  while (after->next != NULL)
    after = after->next;
  after->next = assign;
  heada->size++;
}

/*-----------------最佳适應配置設定算法--------------*/
void bestfit(RECT *head,int application)
{
  RECT *after, *before, *assign;
  assign = malloc(sizeof(RECT)); // 申請配置設定空間
  assign->size = application;
  assign->next = NULL;
  if (application > head->size || application < 0)
    assign->address = -1; // 申請無效
  else
  {
    before = head;
    RECT* ptr = head->next;
    int tmp=0;
    //找到第一塊最合适的空閑分區，即空間大于application的最小分區
    while (ptr!=NULL) // 周遊連結清單，查找合适到節點
    {
      if(ptr->size>=application){
        if(!tmp||ptr->size<tmp){
          after=ptr;
          tmp=ptr->size;
        }
      }
      ptr=ptr->next;
    }
    if (after->size == application) // 若節點大小等于申請大小則完全配置設定
    {
      if (after->size == head->size)
        maxblocknum--;
      before->next = after->next;       // 指向後面的空閑區
      assign->address = after->address; // 将這個同樣大小的位址直接賦給配置設定的對象
      free(after);
    }
    else
    {
      if (after->size == head->size) // 這個可配置設定空間等于剩餘總的空閑空間
        maxblocknum--;
      after->size = after->size - application;        // 大于申請空間則截取相應大小配置設定
      assign->address = after->address + after->size; // 配置設定靠後的位址
    }

    if (maxblocknum == 0) // 修改最大數和頭節點
    {
      before = head;
      head->size = 0;
      maxblocknum = 1;
      while (before != NULL) // 周遊空閑區
      {
        if (before->size > head->size)
        {
          head->size = before->size;
          maxblocknum = 1;
        }
        else if (before->size == head->size)
          maxblocknum++;
        before = before->next;
      }
    }
  }
  assign1 = assign;

  // 修改已配置設定分區表，添加節點
  after = heada;
  while (after->next != NULL)
    after = after->next;
  after->next = assign;
  heada->size++;
}


/*-----------------最壞适應配置設定算法--------------*/
void worstfit(RECT *head,int application)
{
RECT *after, *before, *assign;
  assign = malloc(sizeof(RECT)); // 申請配置設定空間
  assign->size = application;
  assign->next = NULL;
  if (application > head->size || application < 0)
    assign->address = -1; // 申請無效
  else
  {
    before = head;
    RECT* ptr = head->next;
    int tmp=0;
    //找到最大的空閑分區進行配置設定
    while (ptr!=NULL) // 周遊連結清單，查找合适到節點
    {
      if(ptr->size>=application){
        if(ptr->size>tmp){
          after=ptr;
          tmp=ptr->size;
        }
      }
      ptr=ptr->next;
    }
    if (after->size == application) // 若節點大小等于申請大小則完全配置設定
    {
      if (after->size == head->size)
        maxblocknum--;
      before->next = after->next;       // 指向後面的空閑區
      assign->address = after->address; // 将這個同樣大小的位址直接賦給配置設定的對象
      free(after);
    }
    else
    {
      if (after->size == head->size) // 這個可配置設定空間等于剩餘總的空閑空間
        maxblocknum--;
      after->size = after->size - application;        // 大于申請空間則截取相應大小配置設定
      assign->address = after->address + after->size; // 配置設定靠後的位址
    }

    if (maxblocknum == 0) // 修改最大數和頭節點
    {
      before = head;
      head->size = 0;
      maxblocknum = 1;
      while (before != NULL) // 周遊空閑區
      {
        if (before->size > head->size)
        {
          head->size = before->size;
          maxblocknum = 1;
        }
        else if (before->size == head->size)
          maxblocknum++;
        before = before->next;
      }
    }
  }
  assign1 = assign;

  // 修改已配置設定分區表，添加節點
  after = heada;
  while (after->next != NULL)
    after = after->next;
  after->next = assign;
  heada->size++;
}

/*-----------------列印輸對外連結表--------------*/
void print(RECT *output)
{
  RECT *before;
  int index;
  before=output->next;
  index=0;
  if(output->next==NULL)
    printf("NO part for print!\n");
  else
  {
    printf("index****address****end*****size**** \n");
    while(before!=NULL)
    {
      printf("------------------------------------\n");
      printf(" %-9d%- 9d%- 9d%- 9d\n",index,before->address,before->address+before->size-1,before->size);
      printf("------------------------------------\n");
      index++;
      before=before->next;
    }
  }
}

/*檢查回收塊到合法性，back1為要回收到節點位址*/
int backcheck(RECT *head,RECT *back1)
{
  RECT *before;
  int check=1;
  if(back1->address<0 || back1->size<0) check=0;  //位址和大小不能為負數
  before=head->next;
  while((before!=NULL)&&check) //位址不能和空閑區表中節點出現重疊
  if(((back1->address<before->address)&&(back1->address+back1->size>before->address))||((back1->address>=before->address)&&(back1->address<before->address+before->size)))
    check=0;
  else
    before=before->next;
  if(check==0) printf("Error input!\n");
  return check;
}

實驗名稱：動态分區配置設定方式模拟

實驗名稱：動态分區配置設定方式模拟

實驗目的

實驗内容

資料結構設計

配置設定算法設計

回收算法設計

繼續閱讀

楊鳴懶惰導緻莫蘭德被驅逐，可能被禁賽，直接出現2個蝴蝶效應

提前晉級遼籃隔岸觀火！楊鳴再收意外驚喜，三連冠路上坐收漁翁利

CBA總冠軍後衛傷愈歸來，郭艾倫重拾信心，楊鳴杜鋒争冠有變

趕緊搶人！CBA自由市場4位實力派球員，楊鳴杜鋒迎補強好時機

CBA季後賽大變天，郭艾倫深夜宣布重要決定，球迷力挺，楊鳴遺憾

CBA勁爆遼粵大戰終于來了？胡明軒張鎮麟強強對決？杜峰楊鳴大PK

遼粵大戰賽程來了，周琦缺席G1，楊鳴杜鋒大鬥法，拼實力更拼演技

争議！球迷賽後批評杜鋒：知道為什麼之前楊鳴害怕許鐘豪了吧？

萬衆觸目！CBA季後賽上演遼粵大戰杜鋒能阻擋楊鳴沖擊三連冠嗎？

遼粵大戰倒計時！杜鋒收3好1壞消息，郭艾倫深夜報喜，楊鳴攤牌

第二個離隊！遼籃後衛場均1.3分，不如00後小将，楊鳴無力拯救

中午12點，遼粵大戰賽程出爐，杜鋒連遭重大打擊，楊鳴振奮不已！

CBA半決賽遼粵大戰賽程出爐！楊鳴收兩喜訊，杜鋒周琦不裝攤牌了

萬衆矚目！遼粵大戰！楊鳴坐收兩大喜訊，杜鋒周琦謹慎對待！

遼粵大戰，遼籃12人名單出爐，楊鳴迎郭艾倫回歸，預計4月底複出

重磅！楊鳴深夜迎來好消息，郭艾倫歸期确定，滿血歸來成抗粵