Data-Structure4

Before：JaneZ换了一家咖啡店，人在Manner Coffee ,身后10米有一只孔雀（附上图片🥶🥶🥶 ）

Data Structure 4 约瑟夫环 动态内存分配

约瑟夫环问题

约瑟夫环是一个很经典的循环链表问题，初次见于OJ上一道经典的题——春樱对决（ ACMOJ1088 ）
下面给出约瑟夫环问题一个最简单的例子（报到3倍数击毙）

构建循环链表

head = p  new node(0);
for(int i = 1 ; i < n ; i ++){
    p = p -> next = new node(i);
}
p -> next = head; //首尾相连

删除结点（也就是击毙的操作）

q = head;
while(q -> next != q){
    p = q -> next;
    q = p -> next;
    //删除q
    p -> next = q -> next;
    delete q;
    q = p -> next;
}

动态内存分配

动态变量

• 存储在内存中一个被称为堆的区域中，由一个堆管理器进行管理
• new 操作时分配一块空间，delete 操作时回收一块空间
  但是不断的 new delete 操作会导致内存空间的碎片化，应该如何管理这些内存片段呢？😢

动态内存管理

• 所有的空闲片段形成一个集合，按地址顺序排列就得到了线性表，故堆空间的管理实际上就是在维护一个线性表
• 由于该线性表经常需要删除操作（就是 new ）,并且delete操作时可能需要把一些潜在的相邻的闲置空间进行合并，所以用双链表比较合适

模拟动态内存管理的memory类（感觉这种理解很有意思）

class memory{
    struct node{
        int start; //起始地址
        int end; //终止地址
        node *prev; 
        node *next;
        node(int s, int e,node *p = nullptr,node *n = nullptr){
            start = s;
            end = e;
            prev = p;
            next = n;
        }
        node(){
            prev = nullptr;
            next = nullptr;
        }
    };
    node *head;
    node *tail;

    public:
        memory(int capacity);
        int malloc(int size); //申请一块大小为size的空间，返回起始地址
        void free(int start,int size); //释放从start开始、大小为size的空间
        ~memory();
};

memory::memory(int capacity){
    head = new node;
    head -> next = new node(0 , capacity - 1, head);
    head -> next -> next = tail = new node;
    tail -> prev = head -> next;
}

memory::~memory(){
    node *p = head;
    node *q;
    while(p != nullpter){
        q = p -> next;
        delete p;
        p = q;
    }
}

int malloc(int size){
    node *p = head -> next;
    int returnValue;
    while(p != tail && p -> end - p -> start + 1 < size){
        p = p -> next;
    }
    if(p == tail){
        return -1; //没有找到
    }
    returnValue = p -> start;
    if(p -> end - p -> start + 1 == size){
        p -> prev -> next = p -> next;
        p -> next -> prev = p -> prev;
        delete p;
    }else{
        p -> start += size;
    }
    return returnValue;
}

void memory::free(int start, int size){
    node *p = head -> next;
    node *np;
    while(p != tail && p -> start < start){
        p = p -> next;
    }
    if(p != tail && start + size == p -> start){
        p -> start = start;
        np = p;
    }else{
        np = new node(start , start + size - 1 ,p -> prev, p );
        p -> prev -> next = np;
        p -> prev = np;
    }
    p = np -> prev;
    if(p -> end + 1 == np -> start){
        p -> next = np -> next;
        p -> end == start + size - 1;
        delete np;
    }
}