在一段连续空间里面，维护N个stack 的回帖
程序2个优化 函数一个有问题 一个还要重写。。排序的函数 不知道哪里出了错误 当全部出栈了时候 再压栈的时候当时没有问题。但测试函数去测试的时候会崩溃。
找了好就没有找出来。算了， 大概程序的思路 开始我就有了。可能是那地方的细节没有处理好吧。。
因为各种原因，我就没有在那张帖子回帖
问题：在一段连续的内存空间里面，维护N个stack, 并且每个stack可以独立push 和pop,只要整个空间还有空余，都可以做push, 当然被维护的stack空了，是不可以pop的.
我的程序只有了一个栈测试，但是没有影响一样的是可以测试。
思路：2个链表。 一个是空闲表 和一个是占用表。
空闲表： 保存那块内存可以用的内存。
占用块： 保存占用内存块的地址和大小信息（这样就可以不需要在那块内存里面保存一些不必要的信息）
_malloc 函数： 给栈分配内存的函数（是那块固定的内存）
_free 函数; 给栈释放内存 主要是修改空闲表 占用表的信息 再调用SortMem是空闲表从小到大排序。在用merge()函数合并能够掐前后在一起的内存块。
由于排序 我的有BUG 所以 合并函数 我要重写。
所以这2个函数都有问题。我就把他们注释掉了。
但这样也可以满足要求，但这样内存碎片就会很多。 所以这样的程序，效率就不高了。由于找了好久错误，没有找出来。
加上这个程序 我思路基本都有了。所以不想浪费继续找出错了。 如果你能指点一下，那我非常感谢你。
思路 来之以前写的malloc 和free() 函数模拟来的。。。。。。
manage.h
程序代码：#ifndef MANAGE_H_INCLUDED
#define MANAGE_H_INCLUDED
#include "stack.h"
#define Stack_N 2
#define MINI_SIZE 8 // 相差最下的范围 8字节
extern const int valume;//1000个字节大小
extern char room[]; //内存最小单位是一个字节 可以把这块内存分成valume块
typedef struct tagMem_block
{
int size; //内存空闲块的大小
void *addr; //放的地址
struct tagMem_block *next;
struct tagMem_block *pre;
}mem_block;
typedef struct tagun_block
{
int size;
void *addr;
struct tagun_block* next;
}un_block;
extern un_block *un_head;//放已经分配的信息
//un_head->next = NULL;
typedef struct tagManage
{
mem_block head;
mem_block *tail;
int availible; //剩下可以利用的内存大小 单位字节
}Manage;
extern Manage ma;
extern int isInit;
void Init();
void SortMem();//把空闲块的大小排序从小到大排序
void* _malloc(int size);
void _free(void* p);
void merge();//优化函数
int GetInfo(void* p); //获得释放指针的大小信息
void UnListAdd(void* p,int size); //占用表的处理
void MemListAdd(void* p, int size); //空闲表的处理
/*****************************测试函数************************************/
void TraUnBlock();
void TraMemBlock();
#endif // MANAGE_H_INCLUDED
stasck.h
程序代码：#ifndef STACK_H_INCLUDED
#define STACK_H_INCLUDED
#include <stdio.h>
#include <stdlib.h>
#define datetype int
typedef struct tagStackNode
{
datetype date;
struct tagStackNode* next;
}StackNode;
typedef struct tagStack
{
StackNode* head;
StackNode* tail;
int num;
}Stack;
//创建栈
void CreateStack(Stack* s);
//进栈
void Push(Stack* s,datetype date);
//出栈
datetype Pop(Stack* s);
#endif // STACK_H_INCLUDED
manage.cpp
程序代码：#include "manage.h"
un_block *un_head = NULL ;
Manage ma;
int isInit = 0;
const int valume = 64*sizeof(char);
char room[valume];
void Init()
{
ma.availible = valume;
ma.head.addr = room;
ma.head.next = NULL;
ma.head.size = valume;
ma.tail = &ma.head;
ma.tail->next = NULL;
}
//次函数功能 分配对应的内存。
//把这块内存的信息添加到占用表中
//然后求剩下的空闲表
void *_malloc(int size)
{
if(0 == isInit)
{
Init();
isInit = 1;
}
if(ma.availible < size)
{
return NULL; //分配内存失败
}
//printf("ma 的信息 size %d",ma.head.size);
mem_block *p; //指向空闲内存块的指针
//un_block* pt; //指向占用块内存的指针
//这里还要处理ma.head 中的东西啊
//开始的时候空闲块就是我们提供的那块全部的内存块
for(p = &ma.head;p;p=p->next)
{
if(p->size - size <0)
{
puts("内存不足");
continue;//当当前结点不满足需要的内存，如是寻找下一个结点
}
if(p->size - (size)>0)//我的空闲块的顺序是按大小排序的
{ //当前，内存块大小满足时候
p->size -= size; //但要判断是否正好相等与
ma.availible -= size;
//printf("内存减少到%d",ma.availible);
void *tp = p->addr;
void* pp=(char*)(p->addr)+size; //移动size个字节
p->addr = pp;
//puts("这里分配的内存1");
UnListAdd(tp,size); //占用表的处理
return tp; //因为相等和不想等处理方式是一样的
} //但当空闲块大小大于需要的内存块的时候
else //只要把这个空闲块的大小改掉就可以了
if(p->size - size ==0)
{
//当空闲块大小相等于的时候，我需要把这个
//保存空闲块的链表的结点释放掉。
//当这里就有一个特殊情况了，正好整个空闲块的大小变为
//0的时候，空闲块的指针要怎么表示的问题，
//ma.head 赋值为空。
if(NULL!=p->next) //当前结点不是最后一个结点的时候
{
puts("这里分配的内存2");
if(p!=&ma.head)
{
UnListAdd(p->addr,size); //占用表的处理
p->pre->next = p->next; //当不是最后一个空闲块的时候
p->next->pre = p->pre;
void *pp = p->addr;
free(p); // 释放掉结点
ma.availible -= size;
//printf("内存减少到%d",ma.availible);
return pp;
}
else
{
//添加到占用表里面
// puts("这里分配的内存3");
UnListAdd(p->addr,size);
//把空闲表的头指针后移动下一个结点
ma.head = *ma.head.next; //
free(ma.head.next);
ma.availible -= size;
// printf("内存减少到%d",ma.availible);
return p->addr;
}}
else
{
//当是最后一个结点的时候
UnListAdd(p->addr,size);
//是为尾结点的但不是剩下的最后一个空闲块的时候
if(p!=&ma.head)
{
// puts("这里分配的内存4");
ma.tail->pre->next = NULL;
void* pp = ma.tail;
ma.tail = ma.tail->pre;
ma.availible -= size;
//printf("内存减少到%d",ma.availible);
free(pp);
}
else
{
//剩下最后一个空闲块的时候
// puts("这里的分配的内存5");
//puts("是这里出了问题吗");
void* pp = ma.head.addr;
ma.tail = NULL;
ma.availible = 0;
ma.head.addr =NULL;
ma.head.size = 0;
//printf("内存减少到%d",ma.availible);
return pp;
}
}
//这里要处理相等于的特殊情况
//当是第一个空闲块的时候是一个特殊情况
}
}
return NULL;
}
//必须判断是否为占用表的地址 不是的做出assert 处理
void _free(void* p) //p 是地址
{
int size = GetInfo(p);
//添加到链表的最后
//printf("获得size %d\n",size);
MemListAdd(p,size);
//SortMem(); //空闲表排序
//merge();//合并
//下面对占用表做出相应的处理
un_block *pre;
un_block *cur;
cur = un_head;
pre = NULL;
while(cur)
{
if(cur->addr == p)
{
if(cur!=un_head)
{
pre->next = cur->next; //释放该结点
ma.availible+=size;
free(cur);
return;
}
else
{
if(cur->next== NULL) //当为最后一个占用的结点的时候
{
free(un_head);
ma.availible+=size;
un_head = NULL;
return;
}
else
{
void *t = cur;
cur = cur->next;
un_head = cur; //一定要修改这全局变量
ma.availible+=size;
free(t);
return; //不要掉了reutrn; 不然下面还要运算 导致非法指针 我调试了好久啊
}
}
}
pre = cur;
cur = cur->next;
}
}
//释放地址的时候，把这个地址与空闲表中的地址进行对比进行优化
void merge()
{
mem_block* ptr,*pre;
char* addr;
for(ptr = &ma.head;pre = ptr,ptr = ptr->next;)
{
addr = (char*)ptr->addr;
addr += ptr->size;
if(addr == ptr->addr)
{
if(ptr->next)
{
pre = ptr->next;
ptr->next->pre = pre;
pre->size+= ptr->size;
free(ptr);
}
else
{
pre->size+=ptr->size;
pre->next = NULL;
free(ptr);
}
}
}
}
void SortMem()
{
mem_block* p;
mem_block* p1;
mem_block* min,*t1;
int i,j;
void* addr;
void* t;
int k =1;
for(p = &ma.head; p; p = p->next)
{
i = p->size;
addr = p->addr;
for(p1 = p; p1; p1 = p1->next)
{
if(i > (p1->size))
{
j = i;
i = p1->size;
p1->size = j;
t = addr;
addr = p1->addr;
p1->addr = t;
}
}
p->size = i;
p->addr = addr;
}
/* for(p = &ma.head;p;p=p->next)
{
i = p->size;
//puts("在排序");
addr = (void*)(p->addr);
for(p1 = p; p1; p1=p1->next)
{
if(i>(p1->size))
{
//puts("交换中");
j = i;
i = p1->size;
p1->size = j;
t = addr;
addr = (void*)p1->addr;
p1->addr = t;
}
}
p->size = i;
p->addr = addr;
//printf("交换%d次 size %d , 地址 %d",k++,i, addr);
}*/
}
int GetInfo(void* p)
{
un_block * ptr;
for(ptr = un_head;ptr;ptr = ptr->next)
{
if(ptr->addr == p)
{
return ptr->size;
}
}
return 0;
}
void TraUnBlock()
{
un_block* p;
for(p = un_head; p; p = p->next)
{
printf("当前的结点的大小 %d\t",p->size);
printf("当前的地址是%d\t",p->addr);
printf("我保存的数据%d\n",*(int*)p->addr); //我因为定义的是整形
}
}
void TraMemBlock()
{
mem_block* p;
if(ma.head.addr==0)
{
puts("空闲表为空");
return;
}
printf("总共空闲块的大小：%d \n",ma.availible);
printf("空闲链表的第一个块的地址 %d\n",ma.head.addr);
for(p = &ma.head; p; p = p->next)
{
printf("pp %d",p);
printf("空闲块的大小:%d\n",p->size);
printf("空闲块的地址:%d\n",p->addr);
}
}
void UnListAdd(void* p,int size)
{
if(NULL == un_head) //当链表头还没有分配空间的时候
{
un_head =(un_block*)malloc(sizeof(un_block));
if(NULL == un_head)
{
puts("占用表的内存申请失败1");
return;
}
un_head->addr = p;//保存当前的内存块的地址
un_head->size = size; //保存内存块大小的信息
un_head->next = NULL;
}
else //当占用块的链表的头已经处理的时候
{
un_block* pt;
pt = (un_block*)malloc(sizeof(un_block));
if(NULL == pt)
{
puts("占用表的内存申请失败2");
return;
}
//保存占用块的信息
pt->size = size;
pt->addr = p;
//头部添加的方法
pt->next = un_head;
un_head = pt;
}
}
void MemListAdd(void* p, int size)
{
if(ma.head.addr == NULL) //我在结构中给head 是定义不是指针;
{
ma.head.addr = p;
ma.head.next =NULL;
//ma.availible = size; //当空闲链表没有空闲的时候
ma.tail = &ma.head;
ma.tail->next = NULL;
ma.head.size = size;
return;
}
else
{
mem_block* ptr;
ptr = (mem_block*)malloc(sizeof(mem_block));
if(ptr == NULL)
{
puts("MemListAdd 内存申请失败");
return;
}
ptr->addr = p;
ptr->size = size;
ptr->next = NULL;
ptr->pre = ma.tail;
ma.tail->next = ptr;
ma.tail = ptr; //指向最后一个结点
//ma.availible+= size;
}
}
stack.cpp
程序代码：#include "stack.h"
#include "manage.h"
void CreateStack(Stack* s)
{
s->head = NULL;
s->tail = NULL;
s->num = 0;
}
void Push(Stack* s,datetype da)
{
//StackNode* Ptr = (StackNode*)malloc(sizeof(StackNode));
StackNode* Ptr = (StackNode*)_malloc(sizeof(StackNode)); //_malloc 返回的是自己给他的内存块地址
//printf("malloc 后的地址 un_head %d",un_head);
if(NULL == Ptr)
{
puts("内存申请失败");
return;
}
//puts("内存申请成功一个");
//getchar();
Ptr->date = da;
Ptr->next = NULL;
if(NULL == s->head)
{
s->head = Ptr;
s->tail = Ptr;
s->num++;
s->head->next = NULL;
s->tail->next = NULL;
}
else
{
Ptr->next = s->head;
s->head = Ptr;
s->num++;
}
}
datetype Pop(Stack* s)
{
void *p;
if(0 == s->num)
{
puts("栈已经全部为空");
return -1;
}
else
{
//printf("\nu_head add %d\n",un_head);
datetype da;
da = s->head->date;
p = (void*)s->head;
//printf("pp pp %d",p);
//getchar();
s->head= s->head->next;
s->num--;
//printf("s->head %d\n",s->head);
//printf("\n head is %d\n",p);
//printf("\n head is %d\n",p);
//printf("\nu_head add %d\n",un_head);
//free(p); //鎴戣繕娌″摕鍐欏ソ_free()锛?
_free(p);
return da;
}
}
main.cpp
程序代码：#include <iostream>
#include "stack.h"
#include "manage.h"
using namespace std;
int main()
{
Stack s;
CreateStack(&s);
printf("room %d\n",room);
//Init();
// for(int i = 0; i < 5; i++)
// {
// Push(&s,i);
// }
// Push(&s,23);
// Push(&s,34);
// Push(&s,231);
// puts("11111111");
// TraMemBlock();
// Pop(&s);
// puts("22222222");
// TraMemBlock();
// Push(&s,1314);
//
// TraUnBlock();
// TraMemBlock();
Push(&s,1);
Push(&s,2);
Pop(&s);
Push(&s,12);
Push(&s,1246);
Pop(&s);
TraMemBlock();
Push(&s,345);
TraMemBlock();
TraUnBlock();
// Push(&s,3434);
// TraUnBlock();
// int k = Pop(&s);
// printf("hh k %d\n",k);
//TraUnBlock();
// TraUnBlock();
// while(s.num)
// {
// datetype k;
// k = Pop(&s);
// cout<<k<<endl;
// }
//
// TraMemBlock();
// TraUnBlock();
return 0;
}
[ 本帖最后由 小鱼儿c 于 2012-3-19 18:09 编辑 ]
