随笔-91  评论-137  文章-0  trackbacks-0

我们知道对于一个数据堆,有申请内存块,释放内存块等操作.

应此我们给出3个数组,分别为内存堆,标记数组,使用是否数组和一个变量用于表示内存堆内剩余空间数.
1     CHAR HeapData[HEAP_LENGTH];
2     CHAR HeapApplyed[HEAP_LENGTH];
3     CHAR HeapUsed[HEAP_LENGTH];
4 
5     int HeapLeft;                            // 剩余Heap大小
初始化时将3个数组全部设为0.
1         memset(HeapData,0,HEAP_LENGTH);
2         memset(HeapApplyed,0,HEAP_LENGTH);
3         memset(HeapUsed,0,HEAP_LENGTH);
然后我们需要一个New操作来申请一块尚未使用的内存块.
 1     CHAR* New(const int Size)
 2     {
 3         if(Size > HeapLeft) throw HEAP_OVERFLOW;
 4         int iEmpty = GetEmptyLeft(Size);
 5 
 6         memset(HeapApplyed + iEmpty,1,Size); // 将内存块标记
 7 
 8         HeapLeft -= Size;
 9         return HeapData + iEmpty;
10     }
一个Free操作来释放一个内存块.
1     BOOL Free(const int Offset,const int Size)
2     {
3         if(!Apply(Offset,Size)) throw HEAP_NOTAPPLY;
4         memset(HeapApplyed + Offset,0,Size);    // 设置为未标记
5         memset(HeapUsed + Offset,0,Size);        // 标记为未使用
6         HeapLeft += Size;
7         return TRUE;
8     }
一个GetEmptyAddr操作来获得第一个符合指定大小的空闲内存卡块.
 1     CHAR* GetEmptyAddr(const int Size)
 2     {
 3         for(int i=0;i<HEAP_LENGTH;i++)
 4             if(HeapApplyed[i] && !HeapUsed[i]) // 已标记并未使用
 5             {
 6                 BOOL bContinue = FALSE;
 7                 for(int j=i;j<Size;j++)
 8                     if(!HeapApplyed[j] || HeapUsed[j]) // 未标记或已使用
 9                     {
10                         bContinue = TRUE;
11                         break;
12                     }
13                 if(bContinue) continue;
14                 return HeapData + i;
15             }
16         return 0;
17     }
和一个SetData操作来设置数据.
1     BOOL SetData(const int Offset,const Type* Data,const int Size)
2     {
3         if(!Apply(Offset,Size)) throw HEAP_NOTAPPLY;
4         memcpy(HeapData + Offset,Data,Size);    // 拷贝数据
5         memset(HeapUsed + Offset,1,Size);        // 标记为已使用
6         return TRUE;
7     }
最后我们来测试一下这个堆结构.
 1     try
 2     {
 3         Heap<CHAR> heap;
 4         heap.New(9000);
 5 
 6         int i = 1000;
 7         heap.Free(0,100);
 8         printf("EmptyAddr:%X\n",heap.GetEmptyAddr(sizeof(int)));
 9 
10         int* Addr1 = (int*)heap.GetEmptyAddr(sizeof(int));
11         heap.SetData((CHAR*)Addr1 - *heap,(CHAR*)&i,sizeof(int));
12 
13         printf("The Data In Heap:%d\n",*Addr1);
14 
15         heap.New(100);
16         printf("EmptyAddr:%X\n",heap.GetEmptyAddr(sizeof(int)));
17 
18         CHAR str[] = "aaaaa";
19         CHAR* Addr2 = heap.GetEmptyAddr(strlen(str));
20         heap.SetData(Addr2 - *heap,str,strlen(str));
21 
22         printf("The Data In Heap:%s\n",Addr2);
23 
24         printf("EmptyAddr:%X\n",heap.GetEmptyAddr(sizeof(int)));
25     }
26     catch(int i)
27     {
28         switch(i)
29         {
30         case HEAP_OVERFLOW:
31             printf("堆溢出\n");
32             break;
33         case HEAP_NOTAPPLY:
34             printf("错误的地址\n");
35             break;
36         }
37     }
测试结果:
1 EmptyAddr:4EFB0
2 The Data In Heap:1000
3 EmptyAddr:4EF4C
4 The Data In Heap:aaaaa
5 EmptyAddr:4EF51

下面给出完整代码
posted on 2011-02-15 20:59 lwch 阅读(2058) 评论(3)  编辑 收藏 引用 所属分类: 数据结构

评论:
# re: 简单的堆结构实现 2011-02-16 09:31 | 战魂小筑
GetEmptyAddr用for也太慢了吧,改成堆栈好些  回复  更多评论
  
# re: 简单的堆结构实现 2011-02-17 13:20 | 淘宝皇冠店
好  回复  更多评论
  
# re: 简单的堆结构实现 2013-05-03 15:57 | tb
拿来练手一下  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理