#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#define N 10000
int n1//空闲分区的个数
int n2//作业区的个数
struct kongxian
{
int start //起址
int end //结束
int length //长度
}kongxian[N]
struct zuoye
{
int start //起址
int end //结束
int length //长度
}zuoye[N]
int cmp1(const void *a, const void *b)
{
return (*(struct kongxian *)a).start - (*(struct kongxian *)b).start
}
int cmp2(const void *a, const void *b)
{
return (*(struct zuoye *)a).start - (*(struct zuoye *)b).start
}
void init()
{
n1 = 1 //初始时只有一个空闲区
n2 = 0 //初始没有作业
kongxian[0].start = 0
kongxian[0].end = 511
kongxian[0].length = 512
}
void print1() //打印空闲分区
{
int i
for (i = 0 i<n1 i++)
printf("空闲分区ID:%d 起止:%d 结束:%d 长度:%d\n", i, kongxian[i].start, kongxian[i].end, kongxian[i].length)
}
void print2() //打印作业分区
{
int i
for (i = 0 i<n2 i++)
printf("作业分区ID：%d 起止:%d 结束:%d 长度:%d\n", i, zuoye[i].start, zuoye[i].end, zuoye[i].length)
}
int main()
{
int i, j, t, len, flag, id
int front, middle, behind
int t1, t2
init()
print1()
printf("输入1装入新作业，输入0回收作业，输入-1结束\n")
while (scanf("%d", &t) != EOF)
{
if (t == 1) //装入新作业
{
printf("请输入作业的占用空间的长度 ")
scanf("%d", &len)
flag = 0
for (i = 0 i<n1 i++)
{
if (kongxian[i].length >= len) //首次适应算法
{
flag = 1
break
}
}
if (!flag)
{
printf("内存分配失败\n")
}
else
{
//将该作业加入作业区里
zuoye[n2].start = kongxian[i].start
zuoye[n2].end = zuoye[n2].start + len
zuoye[n2].length = len
n2++ //作业数加1
if (kongxian[i].length == len) //该分区全部用于分配，删除该空闲分区
{
for (j = i j<n1 - 1 j++)
{
kongxian[j].start = kongxian[j + 1].start
kongxian[j].end = kongxian[j + 1].end
kongxian[j].length = kongxian[j + 1].length
}
n1--
}
else //该空闲分区部分用于分配，剩余的留在空闲分区中
{
kongxian[i].start += len
kongxian[i].length -= len
}
}
}
else if (t == 0)
{
printf("输入要回收的作业ID ")
scanf("%d", &id)
front = middle = behind = 0
for (i = 0 i<n1 i++)
{
if (kongxian[i].start>zuoye[id].end)
break
if (kongxian[i].end == zuoye[id].start) //待回收的作业上面有空闲分区
{
front = 1
t1 = i
}
if (kongxian[i].start == zuoye[id].end) //待回收的作业下面有空闲分区
{
behind = 1
t2 = i
}
}
if (!front&&!behind) //待回收的作业上下均没有空闲分区
{
kongxian[n1].start = zuoye[id].start
kongxian[n1].end = zuoye[id].end
kongxian[n1].length = zuoye[id].length
n1++ //空闲分区增加一个
qsort(kongxian, n1, sizeof(struct kongxian), cmp1) //插入空闲分区后排序
for (j = id j<n2 - 1 j++) //在作业分区中删除该作业
{
zuoye[j].start = zuoye[j + 1].start
zuoye[j].end = zuoye[j + 1].end
zuoye[j].length = zuoye[j + 1].length
}
n2--
}
if (front &&behind) //待回收的作业上下均有空闲分区
middle = 1
if (front&&!middle) //合并待回收的作业和上面的空闲分区
{
kongxian[t1].end += zuoye[id].length
kongxian[t1].length += zuoye[id].length
for (j = id j<n2 - 1 j++) //在作业分区中删除该作业
{
zuoye[j].start = zuoye[j + 1].start
zuoye[j].end = zuoye[j + 1].end
zuoye[j].length = zuoye[j + 1].length
}
n2--
}
if (middle) //合并待回收的作业和上下的空闲分区
{
kongxian[t1].end = kongxian[t2].end
kongxian[t1].length += (zuoye[id].length + kongxian[t2].length)
//删除空闲分区t2
for (j = t2 j<n1 - 1 j++)
{
kongxian[j].start = kongxian[j + 1].start
kongxian[j].end = kongxian[j + 1].end
kongxian[j].length = kongxian[j + 1].length
}
n1--
for (j = id j<n2 - 1 j++) //在作业分区中删除该作业
{
zuoye[j].start = zuoye[j + 1].start
zuoye[j].end = zuoye[j + 1].end
zuoye[j].length = zuoye[j + 1].length
}
n2--
}
if (behind &&!middle) //合并待回收的作业和下面的分区
{
kongxian[t2].start -= zuoye[id].length
kongxian[t2].length += zuoye[id].length
for (j = id j<n2 - 1 j++) //在作业分区中删除该作业
{
zuoye[j].start = zuoye[j + 1].start
zuoye[j].end = zuoye[j + 1].end
zuoye[j].length = zuoye[j + 1].length
}
n2--
}
}
else
{
printf("操作结束\n")
break
}
print1()
print2()
}
return 0
}
0） 穷举法穷举法简单粗暴，没有什么问题是搞不定的，只要你肯花时间。同时对于小数据量，穷举法就是最优秀的算法。就像太祖长拳，简单，人人都能会，能解决问题，但是与真正的高手过招，就颓了。
1） 贪婪算法
贪婪算法可以获取到问题的局部最优解，不一定能获取到全局最优解，同时获取最优解的好坏要看贪婪策略的选择。特点就是简单，能获取到局部最优解。就像打狗棍法，同一套棍法，洪七公和鲁有脚的水平就差太多了，因此同样是贪婪算法，不同的贪婪策略会导致得到差异非常大的结果。
2） 动态规划算法
当最优化问题具有重复子问题和最优子结构的时候，就是动态规划出场的时候了。动态规划算法的核心就是提供了一个memory来缓存重复子问题的结果，避免了递归的过程中的大量的重复计算。动态规划算法的难点在于怎么将问题转化为能够利用动态规划算法来解决。当重复子问题的数目比较小时，动态规划的效果也会很差。如果问题存在大量的重复子问题的话，那么动态规划对于效率的提高是非常恐怖的。就像斗转星移武功，对手强它也会比较强，对手若，他也会比较弱。
3）分治算法
分治算法的逻辑更简单了，就是一个词，分而治之。分治算法就是把一个大的问题分为若干个子问题，然后在子问题继续向下分，一直到base cases，通过base cases的解决，一步步向上，最终解决最初的大问题。分治算法是递归的典型应用。
4） 回溯算法
回溯算法是深度优先策略的典型应用，回溯算法就是沿着一条路向下走，如果此路不同了，则回溯到上一个
分岔路，在选一条路走，一直这样递归下去，直到遍历万所有的路径。八皇后问题是回溯算法的一个经典问题，还有一个经典的应用场景就是迷宫问题。
5） 分支限界算法
回溯算法是深度优先，那么分支限界法就是广度优先的一个经典的例子。回溯法一般来说是遍历整个解空间，获取问题的所有解，而分支限界法则是获取一个解（一般来说要获取最优解）。
