![点击分享此内容可以赚币 分享](/master/images/share_but.png)
伙伴系统.doc
《伙伴系统.doc》由会员分享,可在线阅读,更多相关《伙伴系统.doc(8页珍藏版)》请在咨信网上搜索。
1、#include #include #include #include /*数据结构C语言版 伙伴系统算法8.2 P205编译环境:Dev-C+ 4.9.9.2日期:2011年2月9日 */ 可利用空间总容量1024字的2的幂次,子表的个数为m+1#define m 10 / 伙伴系统可利用空间表的结构typedef struct WORDstruct WORD *llink;/ 指向前驱结点 int tag;/ 块标志,0:空闲,1:占用 int kval;/ 块大小,值为2的幂次k struct WORD *rlink;/ 头部域,指向后继结点 WORD, head, *Space;/ W
2、ORD:内存字类型,结点的第一个字也称为head typedef struct HeadNodeint nodesize;/ 该链表的空闲块的大小 struct WORD *first;/ 孩链表的表头指针 FreeListm+1;/ 表头向量类型 #define N 100/ 占用块个数的最大值 Space r;/ r为整个生成空间的首地址,全局量 /*算法8.2 P205avail0.m为可利用空间表,n为申请分配量,若有不小于n的空闲块, 则分配相应的存储块,并返回其首地址;否则返回NULL。*/Space AllocBuddy(FreeList *avail, int n)int i,
3、k;Space pa,pi,pre,suc;/ 查找满足分配要求的子表即空闲块大小大于n的表for(k = 0;k = m & (*avail)k.nodesize m)printf(分配失败!n);return NULL;else / 进行分配 pa = (*avail)k.first;/ 指向可分配子表的第一个结点 pre = pa-llink;/ 指向前驱 suc = pa-rlink;/ 指向后继 if(pa = suc)/ 相同的 (*avail)k.first = NULL;/ 分配后该子表变成空表 else/ 从子表删去*pa结点(分配的) pre-rlink = suc;suc
4、-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);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)的块的伙伴
5、地址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);/ 伙伴系统的回收算法 将p所指的释放块回收到可利用空间表pav中void Reclaim(FreeList *pav,Space *p) Space s;/ 伙伴块的起始地址s = buddy(*p); / printf(回收的过程演示:n伙伴块的起始地址:%un,s);/ 归并伙伴块,s = r & s = r
6、& s tag = 0)/ 从链表上删除该结点 if(s-llink = s & s-rlink = s)/ 链表上仅此一个结点 (*pav)s-kval.first = NULL;/ 置此链表为空 else/ 链表上不止一个结点,则将该结点s删除 s-llink-rlink = s-rlink; / 前驱的后继为该结点的后继 s-rlink-llink = s-llink;/ 后继的前驱为该结点的前驱 if(*pav)s-kval.first = s)/ s是链表的第一个结点 (*pav)s-kval.first = s-rlink; / 表头指向下一个结点 / 修改结点头部 if( (*p
7、-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)-kval.first = (*p)-llink = (*p)-rlink = *p;else / 插在表头 (*p)-rlink
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 完整 word 伙伴 系统
![提示](https://www.zixin.com.cn/images/bang_tan.gif)
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【天****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【天****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。