《数据结构c语言版 伙伴系统》由会员分享，可在线阅读，更多相关《数据结构c语言版 伙伴系统（11页珍藏版）》请在金锄头文库上搜索。
1、数据结构数据结构 C C 语言版语言版 伙伴系统伙伴系统数据结构 C 语言版 伙伴系统.txt 爱，就大声说出来，因为你永远都不会知道，明天和意外，哪个会先来！石头记告诉我们：凡是真心爱的最后都散了，凡是混搭的最后都团圆了。你永远看不到我最寂寞的时候，因为在看不到你的时候就是我最寂寞的时候！#include #include #include /*数据结构 C 语言版 伙伴系统算法 8.2 P205编译环境：Dev-C+ 4.9.9.2日期：2011 年 2 月 9 日 */ 可利用空间总容量 1024 字的 2 的幂次,子表的个数为 m+1#define m 10 / 伙伴系统可利用空间表的
2、结构typedef struct WORDstruct WORD *llink;/ 指向前驱结点 int tag;/ 块标志,0:空闲,1:占用 int kval;/ 块大小,值为 2 的幂次 k struct WORD *rlink;/ 头部域,指向后继结点 WORD, head, *Space; / WORD:内存字类型,结点的第一个字也称为 head typedef struct HeadNodeint nodesize;/ 该链表的空闲块的大小 struct WORD *first;/ 孩链表的表头指针 FreeListm+1;/ 表头向量类型 #define N 100/ 占用块个数
3、的最大值 Space r;/ r 为整个生成空间的首地址,全局量 /*算法 8.2 P205avail0.m为可利用空间表,n 为申请分配量,若有不小于 n 的空闲块, 则分配相应的存储块,并返回其首地址;否则返回 NULL。*/Space AllocBuddy(FreeList *avail, int n)int i,k;Space pa,pi,pre,suc;/ 查找满足分配要求的子表即空闲块大小大于 n 的表for(k = 0;k m)printf(“分配失败！n“);return NULL;else / 进行分配 pa = (*avail)k.first; / 指向可分配子表的第一个结
4、点 pre = pa-llink;/ 指向前驱 suc = pa-rlink;/ 指向后继 if(pa = suc)/ 相同的 (*avail)k.first = NULL;/ 分配后该子表变成空表 else/ 从子表删去*pa 结点(分配的) pre-rlink = suc;suc-llink = pre;(*avail)k.first = suc;/ 将块(*avail)k的剩余块分成按由大到小（2 的 k-i 次幂）的顺序/ 依次插入相应大小的子表中 for(i = 1; (*avail)k-i.nodesize = n+1; +i)pi = pa + (int)pow(2, k-i);
5、pi-rlink = pi;pi-llink = pi;pi-tag = 0;pi-kval = k-i;(*avail)k-i.first = pi; pa-tag = 1;pa-kval = k-(-i);return pa;/ 返回相对起始地址为 p,块大小为 pow(2,k)的块的伙伴地址Space buddy(Space p) if(p - r) % (int)pow(2,p-kval+1) = 0)/ p 为前块 return p + (int)pow(2, p-kval);else / p 为后块 return p - (int)pow(2, p-kval);/ 伙伴系统的回收算
6、法 将 p 所指的释放块回收到可利用空间表pav 中void Reclaim(FreeList *pav,Space *p) Space s;/ 伙伴块的起始地址s = buddy(*p); / printf(“回收的过程演示：n 伙伴块的起始地址：%un“,s);/ 归并伙伴块,s = r / 置此链表为空 else/ 链表上不止一个结点，则将该结点 s 删除 s-llink-rlink = s-rlink; / 前驱的后继为该结点的后继 s-rlink-llink = s-llink;/ 后继的前驱为该结点的前驱 if(*pav)s-kval.first = s)/ s 是链表的第一个结点
7、 (*pav)s-kval.first = s-rlink; / 表头指向下一个结点 / 修改结点头部 if( (*p-r) % (int)pow(2,(*p)-kval+1) = 0) / p 为前块 (*p)-kval+;else / p 为后块 s-kval = (*p)-kval+1;*p = s; / p 指向新块首地址 s = buddy(*p); / 下一个伙伴块的起始地址 / printf(“伙伴块的起始地址：%un“,s);/ 将 p 插到可利用空间表中 (*p)-tag = 0;if(*pav)(*p)-kval.first = NULL) / 该链表空 (*pav)(*p
8、)-kval.first = (*p)-llink = (*p)-rlink = *p;else / 插在表头 (*p)-rlink = (*pav)(*p)-kval.first;(*p)-llink = (*p)-rlink-llink;(*p)-rlink-llink = *p;(*p)-llink-rlink = *p;(*pav)(*p)-kval.first = *p;*p = NULL;/ 输出 p 中所有可利用空间表void Print(FreeList p) int i;Space h;printf(“可利用空间：n“);for(i = 0; i kval),h); / 输出
9、结点信息 printf(“块标志=%d(0:空闲 1:占用)n“, h-tag);h = h-rlink; / 指向下一个结点的头部域(首地址) while(h != pi.first); / 没到循环链表的表尾 printf(“n“);/ 输出 p 数组所指的已分配空间void PrintUser(Space p) int i;printf(“已利用空间：n“);for(i = 0; i kval);printf(“ 块标志=%d(0:空闲 1:占用)n“, pi-tag);printf(“n“);int main()int i,n;FreeList a;Space qN = NULL ;
10、/ q 数组为占用块的首地址 printf(“这里假设的内存空间的单位是 WORD 结构的字节数.n“);printf(“WORD 的大小=%un“, sizeof(WORD); printf(“可分配的总空间(int)pow(2,%d) = %un“,m,(int)pow(2,m);for(i = 0; i llink = r-rlink = r; / 初始化该结点 r-tag = 0;r-kval = m;Print(a);PrintUser(q);n = 100;printf(“申请%d 个字后:n“,n);/ 向 a 申请 100 个 WORD 的内存(实际获得 128 个 WORD
11、因为/ 10064 Print(a);PrintUser(q);n = 200;printf(“申请%d 个字后:n“,n);/ 向 a 申请 200 个 WORD 的内存(实际获得 256 个 WORD)q1 = AllocBuddy( Print(a);PrintUser(q);n = 220;printf(“申请%d 个字后:n“,n);/ 向 a 申请 220 个 WORD 的内存(实际获得 256 个 WORD)q2 = AllocBuddy( Print(a);PrintUser(q);printf(“回收 q1后:n“);Reclaim( / 回收 q1，伙伴不空闲 Print(
12、a);PrintUser(q);printf(“回收 q0后:n“);Reclaim( / 回收 q0，伙伴空闲 Print(a);PrintUser(q);printf(“回收 q2后:n“);Reclaim( / 回收 q2，伙伴空闲，生成一个大结点 Print(a);PrintUser(q);elseprintf(“分配失败！n“);system(“pause“);return 0;/*输出效果：这里假设的内存空间的单位是 WORD 结构的字节数.WORD 的大小=16可分配的总空间(int)pow(2,10) = 1024起始地址 r 为：3420912可利用空间：块的大小=1024
13、块的首地址=3420912 块标志=0(0:空闲 1:占用)已利用空间：申请 100 个字后:可利用空间：块的大小=128 块的首地址=3422960 块标志=0(0:空闲 1:占用)块的大小=256 块的首地址=3425008 块标志=0(0:空闲 1:占用)块的大小=512 块的首地址=3429104 块标志=0(0:空闲 1:占用)已利用空间：占用块 0 的首地址=3420912 块的大小=128 块标志=1(0:空闲 1:占用)申请 200 个字后:可利用空间：块的大小=128 块的首地址=3422960 块标志=0(0:空闲 1:占用)块的大小=512 块的首地址=3429104 块
14、标志=0(0:空闲 1:占用)已利用空间：占用块 0 的首地址=3420912 块的大小=128 块标志=1(0:空闲 1:占用)占用块 1 的首地址=3425008 块的大小=256 块标志=1(0:空闲 1:占用)申请 220 个字后:可利用空间：块的大小=128 块的首地址=3422960 块标志=0(0:空闲 1:占用)块的大小=256 块的首地址=3433200 块标志=0(0:空闲 1:占用)已利用空间：占用块 0 的首地址=3420912 块的大小=128 块标志=1(0:空闲 1:占用)占用块 1 的首地址=3425008 块的大小=256 块标志=1(0:空闲 1:占用)占用
15、块 2 的首地址=3429104 块的大小=256 块标志=1(0:空闲 1:占用)回收 q1后:可利用空间：块的大小=128 块的首地址=3422960 块标志=0(0:空闲 1:占用)块的大小=256 块的首地址=3425008 块标志=0(0:空闲 1:占用)块的大小=256 块的首地址=3433200 块标志=0(0:空闲 1:占用)已利用空间：占用块 0 的首地址=3420912 块的大小=128 块标志=1(0:空闲 1:占用)占用块 2 的首地址=3429104 块的大小=256 块标志=1(0:空闲 1:占用)回收 q0后:可利用空间：块的大小=256 块的首地址=3433200 块标志=0(0:空闲 1:占用)块的大小=512 块的首地址=3420912 块标志=0(0:空闲 1:占用)已利用空间：占用块 2 的首地址=3429104 块的大小=256 块标志=1(0:空闲 1:占用)回收 q2后:可利用空间：块的大小=1024 块的首地址=3420912 块标志=0(0:空闲 1:占用)已利用空间：请按任意键继续. . . */
