首页 > 代码库 > 通用块状链表

通用块状链表

在这里写下模板。以后方便用

#include <iostream>#include <stdio.h>#include <string.h>#include <math.h>#include <stdlib.h>#define max_size 3000using namespace std;const int best_size = max_size - 20;struct node{    int size;    int date[max_size];    struct node * next;}block_list;//创建节点 struct node * createnode(){    struct node * temp = (struct node *)malloc(sizeof(struct node));    temp->next = NULL;    temp->size = 0;    return temp;} //初始化块状数组 //n为块状数组存储的数据总数//block_size为每一块初始存入的数据个数 一般为sqrt(n)//date为数据源 ,从0开始计数 void init(int n, char * date, int block_size){    struct node * temp = &block_list;    struct node * temp2 = temp;    int i;    int k;    for(i = 0, k = 0; k < n; i++,k++)    {        if(i == block_size)        {            temp2 = temp;             temp = temp->next;            i = 0;        }        if(temp!= NULL)        {            temp->date[i] = date[k];            temp->size ++;        }        else        {            temp = createnode();            temp2 ->next = temp;            temp->date[i] = date[k];            temp->size ++;        }    }}//向块状插入数据//pos为插入位置 date为数据bool insertdate(int pos, int date){    struct node * temp = &block_list;    struct node * temp2 = temp;    int sum = block_list.size;    int flag;        while(sum<pos)    {        temp2 = temp;        temp = temp->next;        if(temp == NULL)        {             temp2 -> date[temp2 -> size] = date;             temp2 ->size ++;             return true;        }        sum += temp->size;    }        for(flag = temp -> size ; flag >= (temp -> size - (sum - pos)); flag --)    {        temp -> date[flag] = temp -> date[flag-1];    }         temp -> date[flag] = date;        temp -> size ++;        return true;}//删除位置为pos的数据 bool deletedate(int pos){    struct node * temp = &block_list;    int sum = block_list.size;    int flag;        while(sum<pos)    {        temp = temp->next;        if(temp == NULL)            return false;        sum += temp->size;    }        for(flag = temp->size - (sum - pos)-1 ; flag < temp -> size -1; flag ++)    {        temp -> date[flag] = temp -> date[flag+1];    }        temp -> size --;        return true;}//分割一个块//参数为这个块的地址 bool splitnode(struct node * aim){    int size = aim -> size;    struct node * temp  = createnode();    temp -> next = aim -> next;    aim -> next = aim;        for(int i = best_size, k = 0; i < size; i++, k++)    {        aim -> date[i] = temp -> date[k];        aim -> size --;        temp -> size ++;    }        return true;}//合并两个节点 //必须为两个相邻的节点!!!! bool combinenode(struct node * aim1, struct node * aim2){    if( aim1 -> size + aim2 -> size > best_size)        return false;        for(int i = aim1 -> size, j = 0; j < aim2 -> size; j++, i++)    {        aim1 -> date[i] = aim2 -> date[j];        aim1 -> size ++;    }        aim1-> next = aim2 ->next;        free(aim2);    return true;}int selectdate(int pos){    struct node * temp = &block_list;    int sum = block_list.size;    int flag;        while(sum<pos)    {        temp = temp->next;        if(temp == NULL)            return false;        sum += temp->size;    }            return temp -> date[temp -> size - (sum - pos)-1];    }/*char test[1000001];int main(){    char t[2];    int num;    int pos;    char d[2];    scanf("%s",test);    int len = strlen(test);    init(len,test,sqrt(len));    scanf("%d",&num);        for(int i=0;i<num;i++)    {        scanf("%s",t);        if(t[0] == ‘Q‘)        {            scanf("%d",&pos);            printf("%c\n",selectdate(pos));        }        else        {            scanf("%s %d",d,&pos);            insertdate(pos,d[0]);        }    }    }*/

去掉注释的代码可以直接A掉2887题目

通用块状链表